Multi-agent coordination under sparse networking

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.