Determining handoff checkpoints for low-resolution robot planning

• US 9,989,371 B1
• Filed: 05/23/2017
• Issued: 06/05/2018
• 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:
  US15/602,425
• Time in Patent Office: 378 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 given robot of a plurality of robots in an environment, wherein the plurality of robots are in communication with the global path planner;

determining, by the global path planner, a first intermediate handoff checkpoint for the given robot to reach while the given robot performs the task;

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

determining, by the global path planner, a second intermediate handoff checkpoint for the given robot to reach consecutively after the given robot meets the first intermediate handoff checkpoint while the given robot performs the task, wherein a spatial or temporal difference between the first and second intermediate handoff checkpoints is selected based on one or more attributes of the environment; and

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

wherein transmitting the first and second intermediate handoff checkpoints causes the given robot to operate in a manner in which the given robot consecutively reaches the first and second intermediate handoff checkpoints.

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

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

4. The method of claim 1, wherein the one or more attributes of the environment comprise a level of entropy in the environment.

5. The method of claim 1, wherein the one or more attributes of the environment comprise an observed change in a level of entropy in the environment.

6. The method of claim 1, wherein the one or more attributes of the environment comprise an observed change in the environment.

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

8. A system comprising one or more processors and memory operably coupled with the one or more processors, wherein the memory stores instructions that, in response to execution of the instructions by one or more processors, cause the one or more processors to implement a global path planner that performs the following operations:

identifying a task to be performed by a given robot of a plurality of robots in an environment, wherein the plurality of robots are in communication with the global path planner;

determining a first intermediate handoff checkpoint for the given robot to reach while the given robot performs the task;

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

determining a second intermediate handoff checkpoint for the given robot to reach consecutively after the given robot meets the first intermediate handoff checkpoint while the given robot performs the task, wherein a spatial or temporal difference between the first and second intermediate handoff checkpoints is selected based on one or more attributes of the environment; and

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

wherein transmitting the first and second intermediate handoff checkpoints causes the given robot to operate in a manner in which the given robot consecutively reaches the first and second intermediate handoff checkpoints.

9. The system of claim 8, wherein the one or more attributes of the environment comprise a latency associated with a communication channel between the global path planner and the local path planner.

10. The system of claim 8, wherein the one or more attributes of the environment comprise dropoff characteristics associated with a communication channel between the global path planner and the local path planner.

11. The system of claim 8, wherein the one or more attributes of the environment comprise a level of entropy in the environment.

12. The system of claim 8, wherein the one or more attributes of the environment comprise an observed change in a level of entropy in the environment.

13. The system of claim 8, wherein the one or more attributes of the environment comprise an observed change in the environment.

14. The system of claim 8, further comprising instructions to include, in the data indicative of the second intermediate handoff checkpoint, an amount of precision about how the local path planner is to operate the robot to reach the second intermediate handoff checkpoint, wherein the amount of precision is commensurate with an amount of knowledge the global path planner has about the environment or the task.

15. At least one non-transitory computer-readable medium comprising instructions that, in response to execution of the instructions by one or more processors, cause the one or more processors to implement a global path planner that performs the following operations:

identifying a task to be performed by a given robot of a plurality of robots in an environment, wherein the plurality of robots are in communication with the global path planner;

determining a first intermediate handoff checkpoint for the given robot to reach while the given robot performs the task;

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

determining a second intermediate handoff checkpoint for the given robot to reach consecutively after the given robot meets the first intermediate handoff checkpoint while the given robot performs the task, wherein a spatial or temporal difference between the first and second intermediate handoff checkpoints is selected based on one or more attributes of the environment; and

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

wherein transmitting the first and second intermediate handoff checkpoints causes the given robot to operate in a manner in which the given robot consecutively reaches the first and second intermediate handoff checkpoints.

16. The at least one non-transitory computer readable medium of claim 15, wherein the one or more attributes of the environment comprise a latency associated with a communication channel between the global path planner and the local path planner.

17. The at least one non-transitory computer readable medium of claim 15, wherein the one or more attributes of the environment comprise dropoff characteristics associated with a communication channel between the global path planner and the local path planner.

18. The at least one non-transitory computer readable medium of claim 15, wherein the one or more attributes of the environment comprise a level of entropy in the environment.

19. The at least one non-transitory computer readable medium of claim 15, wherein the one or more attributes of the environment comprise an observed change in a level of entropy in the environment.

20. The at least one non-transitory computer readable medium of claim 15, wherein the one or more attributes of the environment comprise an observed change in the environment.