Multi-agent coordination under sparse networking

• US 10,363,657 B2
• Filed: 12/23/2016
• Issued: 07/30/2019
• Est. Priority Date: 12/23/2016
• Status: Active Grant

• Current Assignee: Intrinsic Innovation LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Lalonde, Geoffrey, Anderson-Sprecher, Peter
• Primary Examiner(s): Tran, Khoi H
• Assistant Examiner(s): Peche, Jorge O
• Application Number:
  US15/390,013
• Publication Number:
  US 20180178376A1
• Time in Patent Office: 949 Days
• CPC Class Codes: B25J 9/0084 comprising a plurality of manipulators
• CPC Class Codes: B25J 9/1651 acceleration, rate control
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: B25J 9/1676 Avoiding collision or forbidden zones
• CPC Class Codes: G05D 1/0223 involving speed control of the vehicle vehicle fittings for automatically controlling, i.e. preventing speed from exceeding an arbitrarily established velocity or maintaining speed at a particular velocity, as selected by the vehicle operator B60K31/00
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G08G 1/163 involving continuous checking
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

A method includes receiving a first time-parameterized path for the first robotic device, and an indication of a second robotic device having a second time-parameterized path that overlaps with the first time-parameterized path at a first location. The method also includes executing, by the first robotic device, a first portion of the first time-parameterized path before reaching the first location, wherein execution of the first portion corresponds to a first rate of progress of the first robotic device along the first time-parameterized path. The first robotic device then receives a communication signal from the second robotic device indicating a second rate of progress of the second robotic device along the second time-parameterized path. The method then includes the first robotic device determining a difference between the first rate of progress and the second rate of progress, and modifying execution of the first time-parameterized path based on the determined difference.

Claims

1. A method comprising:

receiving, by a first robotic device, a first time-parameterized path for the first robotic device, wherein the first time-parameterized path comprises a first timeline of expected locations of the first robotic device;

receiving, by the first robotic device, an indication of a second robotic device having a second time-parameterized path that overlaps with the first time-parameterized path at a first location, wherein the second time-parameterized path comprises a second timeline of expected locations of the second robotic device;

executing, by the first robotic device, a first portion of the first time-parameterized path before reaching the first location, wherein execution of the first portion corresponds to a first rate of progress of the first robotic device along the first time-parameterized path;

receiving, by the first robotic device, a communication signal from the second robotic device indicating a second rate of progress of the second robotic device along the second time-parameterized path;

determining a difference in progress compared to a coordinated timeline between the first rate of progress and the second rate of progress; and

modifying, by the first robotic device, execution of the first time-parameterized path based on the determined difference in order to avoid a collision between the first robotic device and the second robotic device at the first location.

2. The method of claim 1, further comprising:

receiving, by the first robotic device, the second time-parameterized path; and

based on the second time-parameterized path, the first robotic device determining a location along the first time-parameterized path at which to establish communication with the second robotic device.

3. The method of claim 1, wherein the second rate of progress indicates that the second robotic device is behind schedule by a given time amount, and wherein modifying execution of the first time-parameterized path comprises modifying execution of the first time-parameterized path such that the first robotic device is behind schedule by the given time amount.

4. The method of claim 1, wherein modifying, by the first robotic device, execution of the first time-parameterized path comprises adding a delay to the execution of the first time-parameterized path.

5. The method of claim 1, wherein modifying, by the first robotic device, execution of the first time-parameterized path comprises stopping execution of the first time-parameterized path.

6. The method of claim 1, wherein modifying execution of the first time-parameterized path comprises the first robotic device back-tracking to a previous position along the first time-parameterized path.

7. The method of claim 1, further comprising transmitting an instruction from the first robotic device to the second robotic device, wherein the instruction causes the second robotic device to speed up execution of the second time-parameterized path based on the determined difference.

8. The method of claim 1, further comprising:

determining that the second rate of progress of the second robotic device along the second time-parameterized path is ahead of the first rate of progress of the first robotic device along the first time-parameterized path, wherein modifying, by the first robotic device, execution of the first time-parameterized path comprises speeding up the execution of the first time-parameterized path.

9. The method of claim 1, further comprising:

determining that the difference between the first rate of progress and the second rate of progress is greater than a threshold temporal padding; and

modifying, by the first robotic device, the execution of the first time-parameterized path based on the determination that the difference between the first rate of progress and the second rate of progress is greater than the threshold temporal padding.

10. The method of claim 1, further comprising:

establishing communication between the first robotic device and a third robotic device; and

transmitting, from the first robotic device to the third robotic device, an indication of the second rate of progress of the second robotic device along the second time-parameterized path.

11. The method of claim 1, further comprising:

transmitting, by the first robotic device to a third robotic device, a communication signal indicating the first rate of progress of the first robotic device along the first time-parameterized path; and

subsequent to modifying execution of the first time-parameterized path, (i) determining a modified rate of progress of the first robotic device and (ii) transmitting, by the first robotic device to the third robotic device, a communication signal indicating the modified rate of progress.

12. A system comprising:

a first robotic device; and

a second robotic device,

wherein the first robotic device is configured to;

receive a first time-parameterized path for the first robotic device, wherein the first time-parameterized path comprises a first timeline of expected locations of the first robotic device;

receive an indication of a second robotic device having a second time-parameterized path that overlaps with the first time-parameterized path at a first location, wherein the second time-parameterized path comprises a second timeline of expected locations of the second robotic device;

execute a first portion of the first time-parameterized path before reaching the first location, wherein execution of the first portion corresponds to a first rate of progress of the first robotic device along the first time-parameterized path;

receive a communication signal from the second robotic device indicating a second rate of progress of the second robotic device along the second time-parameterized path;

determine a difference in progress compared to a coordinated timeline between the first rate of progress and the second rate of progress; and

modify execution of the first time-parameterized path based on the determined difference in order to avoid a collision between the first robotic device and the second robotic device at the first location.

13. The system of claim 12, wherein the first robotic device is further configured to:

receive the second time-parameterized path; and

based on the second time-parameterized path, determine a location along the first time-parameterized path at which to establish communication with the second robotic device.

14. The system of claim 12, wherein the first robotic device is further configured to:

determine that the difference between the first rate of progress and the second rate of progress is greater than a threshold temporal padding; and

modify the execution of the first time-parameterized path based on the determination that the difference between the first rate of progress and the second rate of progress is greater than the threshold temporal padding.

15. The system of claim 12, further comprising a path planning system that is configured to provide the first time-parameterized path for the first robotic device and the second time-parameterized path for the second robotic device such that each of the first and second time-parameterized paths begin and end in locations with connectivity to the path planning system based on a predetermined connectivity map of an environment.

16. The system of claim 15, wherein the first location lacks connectivity with the path planning system, and wherein the first robotic device is further configured to report the second rate of progress of the second robotic device to the path planning system after passing the first location and entering a region with connectivity to the path planning system.

17. A non-transitory, computer-readable medium having instructions stored thereon that when executed, cause performance of a set of acts comprising:

receiving a first time-parameterized path for the first robotic device, wherein the first time-parameterized path comprises a first timeline of expected locations of the first robotic device;

receiving an indication of a second robotic device having a second time-parameterized path that overlaps with the first time-parameterized path at a first location, wherein the second time-parameterized path comprises a second timeline of expected locations of the second robotic device;

executing a first portion of the first time-parameterized path before reaching the first location, wherein execution of the first portion corresponds to a first rate of progress of the first robotic device along the first time-parameterized path;

receiving a communication signal from the second robotic device indicating a second rate of progress of the second robotic device along the second time-parameterized path;

determining a difference in progress compared to a coordinated timeline between the first rate of progress and the second rate of progress; and

modifying execution of the first time-parameterized path based on the determined difference in order to avoid a collision between the first robotic device and the second robotic device at the first location.

18. The non-transitory, computer-readable medium of claim 17, the set of acts further comprising:

receiving the second time-parameterized path; and

based on the second time-parameterized path, determining a location along the first time-parameterized path at which to establish communication with the second robotic device.

19. The non-transitory, computer-readable medium of claim 17, the set of acts further comprising:

determining that the difference between the first rate of progress and the second rate of progress is greater than a threshold temporal padding; and

modifying the execution of the first time-parameterized path based on the determination that the difference between the first rate of progress and the second rate of progress is greater than the threshold temporal padding.