Determining handoff checkpoints for low-resolution robot planning

• US 9,689,696 B1
• Filed: 09/22/2015
• Issued: 06/27/2017
• Est. Priority Date: 09/22/2015
• Status: Active Grant

• Current Assignee: Intrinsic Innovation LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Russell, Jared Stephen
• Primary Examiner(s): Soofi, Yazan
• Application Number:
  US14/861,852
• Time in Patent Office: 644 Days
• Field of Search: 701527
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40437 Local, directly search robot workspace
• CPC Class Codes: G05B 2219/40444 Hierarchical planning, in levels
• CPC Class Codes: G05D 1/0287 involving a plurality of land vehicles, e.g. fleet or convoy travelling traffic control systems for road vehicles G08G1/00, particularly anticollision systems G08G1/16
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

Methods, apparatus, systems, and computer-readable media are provided for determining and assigning intermediate handoff checkpoints for low-resolution robot planning. In various implementations, a global path planner may identify a task to be performed by a robot in an environment. In various implementations, the global path planner may determine, based at least in part on one or more attributes of the environment or the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task. In various implementations, the global path planner may determine that a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies a reactivity threshold. In various implementations, the global path planner may provide, to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint.

Claims

1. A method comprising:

identifying, by a global path planner implemented by a computing system, a task to be performed by a robot in an environment;

determining, by the global path planner, based at least in part on one or more attributes of the environment or the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task, wherein the determining includes determining that a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies a reactivity threshold; and

transmitting, by the global path planner over one or more networks, to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint;

wherein the transmitting causes operation of one or more operational components of the robot to reach the intermediate handoff checkpoint by the scheduled time.

2. The method of claim 1, wherein the determining further comprises calculating the measure of reactivity.

3. The method of claim 2, further comprising adjusting, by the global path planner, the reactivity threshold in response to a detected change in the environment.

4. The method of claim 3, wherein the detected change in the environment comprises a degradation of a communication channel between the global path planner and the local path planner.

5. The method of claim 1, wherein the determining further comprises:

calculating a probability that the robot will be able to meet the intermediate handoff checkpoint by the scheduled time; and

determining that the probability satisfies a reachability threshold.

6. The method of claim 5, wherein the probability is calculated based on the one or more attributes of the environment or the task.

7. The method of claim 1, wherein the one or more attributes of the environment or task comprise a latency associated with a communication channel between the global path planner and the local path planner.

8. The method of claim 1, wherein the one or more attributes of the environment or task comprises dropoff characteristics associated with a communication channel between the global path planner and the local path planner.

9. The method of claim 1, wherein the intermediate handoff checkpoint comprises a next handoff checkpoint, the scheduled time comprises a next scheduled time, and the transmitting comprises transmitting data indicative of the next handoff checkpoint to the local path planner so that the local path planner receives the data indicative of the next handoff checkpoint prior to the robot reaching a current handoff checkpoint by a current scheduled time while the robot performs the task, wherein the current handoff checkpoint immediately precedes the next handoff checkpoint.

10. The method of claim 1, further comprising including, by the global path planner, in the data indicative of the intermediate handoff checkpoint, an amount of precision about how the local path planner is to operate the robot to reach the intermediate handoff checkpoint by the scheduled time, wherein the amount of precision is commensurate with an amount of knowledge the global path planner has about the one or more attributes of the environment or the task.

11. The method of claim 1, wherein the local path planner is implemented by one or more processors of the robot, and the one or more processors of the robot are in wireless communication with the computing system that implements the global path planner.

12. A robot management system comprising memory and one or more processors operable to execute instructions stored in the memory, comprising instructions to:

identify a task to be performed by a robot in an environment;

determine, based at least in part on one or more attributes of the environment or the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task, wherein a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies a reactivity threshold; and

transmit, over one or more networks to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint;

wherein based on receipt of the data indicative of the intermediate handoff checkpoint, one or more operational components of the robot are operated to reach the intermediate handoff checkpoint by the scheduled time.

13. The system of claim 12, wherein the system further comprises instructions to calculate the measure of reactivity.

14. The system of claim 12, further comprising instructions to adjust the reactivity threshold in response to a detected change in the environment.

15. The system of claim 14, wherein the detected change in the environment comprises a degradation of a communication channel between the system and the local path planner.

16. The system of claim 14, wherein the detected change in the environment comprises a change in entropy detected in the environment.

17. The system of claim 12, further comprising instructions to:

calculate a probability that the robot will be able to meet the handoff checkpoint by the scheduled time based on the one or more attributes of the environment or the task; and

determine that the probability satisfies a reachability threshold.

18. The system of claim 12, wherein the one or more attributes of the environment or task comprise one or more of a latency associated with a communication channel between the system and the local path planner and dropoff characteristics associated with the communication channel.

19. The system of claim 12, further comprising instructions to include, in the data indicative of the intermediate handoff checkpoint, an amount of precision about how the local path planner is to operate the robot to reach the intermediate handoff checkpoint by the scheduled time, wherein the amount of precision is commensurate with an amount of knowledge the system has about the one or more attributes of the environment or the task.

20. At least one non-transitory computer-readable medium comprising instructions that, in response to execution of the instructions by a computing system, cause the computing system to:

identify one or more attributes of a task to be performed by a robot in an environment;

identify one or more attributes of the environment;

determine a reactivity threshold based on the one or more attributes of the environment or the one or more attributes of the task;

determine, based at least in part on one or more attributes of the environment and the one or more attributes of the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task, wherein a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies the reactivity threshold; and

transmit, over one or more networks to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint;

wherein based on receipt of the data indicative of the intermediate handoff checkpoint, one or more operational components of the robot are operated to reach the intermediate handoff checkpoint by the scheduled time.

21. A method comprising:

identifying, by a global path planner implemented by a computing system, a task to be performed by a robot in an environment;

determining, by the global path planner, based at least in part on one or more attributes of the environment or the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task, wherein the determining includes determining that a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies a reactivity threshold;

providing, by the global path planner, to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint; and

operating one or more operational components of the robot to reach the intermediate handoff checkpoint by the scheduled time.

22. A system comprising memory and one or more processors operable to execute instructions stored in the memory, comprising instructions to:

identify a task to be performed by a robot in an environment;

determine, based at least in part on one or more attributes of the environment or the task, an intermediate handoff checkpoint for the robot to reach by a scheduled time while the robot performs the task, wherein a measure of reactivity that would be attributable to the robot upon the robot being assigned the intermediate handoff checkpoint satisfies a reactivity threshold;

provide, to a local path planner associated with the robot, data indicative of the intermediate handoff checkpoint; and

operate one or more operational components of the robot to reach the intermediate handoff checkpoint by the scheduled time.