Robot coordination in a shared workspace

1. A method for coordinating movements of a plurality of robots configured to operate in a shared workspace, comprising:

for each robot in the plurality of robots:

identifying a set of tasks assigned to the robot;

generating a plurality of candidate motion plans, each candidate motion plan representing a different sequence of motions for the robot to execute in performing the set of tasks;

for each candidate motion plan:

(i) generating a 3D model that represents a volume of space through which the robot would move in executing a sequence of motions represented by the candidate motion plan, and

(ii) determining a score for the candidate motion plan, the score based at least on a characteristic of the sequence of motions represented by the candidate motion plan or a characteristic of the volume of space represented by the 3D model for the candidate motion plan;

determining that a conflict occurs between a pair of candidate motion plans for different respective robots, including using respective 3D models for the pair of candidate motion plans to determine that an intersection occurs between respective volumes of space generated for the pair of candidate motion plans for the different respective robots;

in response, removing, from the plurality of candidate motion plans, one or more of the pair of candidate motion plans having the conflict due to the intersection between the respective volumes of space generated for the pair of candidate motion plans;

selecting, for each robot in the plurality of robots from candidate motion plans that remain among the plurality of candidate motion plans after removing the one or more of the pair of candidate motion plans having the conflict, a respective candidate motion plan based on the scores computed for the candidate motion plans; and

scheduling execution of the set of tasks including assigning one or more selected candidate motion plans to each robot of the plurality of robots.

2. The method of claim 1 further comprising:

for each robot in the plurality of robots:

identifying a plurality of sets of tasks assigned to the robot;

generating a plurality of candidate motion plans for each set of tasks in the plurality of sets of tasks; and

selecting, for the robot, a motion plan from the plurality of candidate motion plans for each set of the plurality of sets of tasks.

3. The method of claim 1 wherein identifying a set of tasks assigned to each robot of the plurality of robots comprises:

generating a plurality of clusters of tasks by assigning each task in the set of tasks to one of the plurality of clusters; and

for each cluster of the plurality of clusters, identifying one or more candidate robots from the plurality of robots to perform the tasks in the cluster.

4. The method of claim 3 wherein generating the plurality of clusters of tasks by assigning each task in the set of tasks to one of the plurality of clusters comprises determining an approximate solution to the traveling salesman problem.

5. The method of claim 1 wherein the characteristic of the sequence of motions represented by the candidate motion plan includes an estimated duration of time to execute the candidate motion plan.

6. The method of claim 1 wherein the characteristic of the sequence of motions represented by the candidate motion plan includes an estimated complexity of a path traced by a corresponding robot during execution of the candidate motion plan.

7. The method of claim 1 wherein the characteristic of the volume of space represented by the 3D model for the candidate motion plan includes an amount of space encompassed by the 3D model.

8. The method of claim 1 , further comprising:

obtaining a workcell volume cost map, the workcell volume cost map describing costs associated with a robot occupying different portions of space in the shared workspace; and

wherein, for each robot in at least a subset of the plurality of robots and for each candidate motion plan in at least a subset of the plurality of candidate motion plans for the robot, determining the score for the candidate motion plan comprises:

determining various portions of space that the robot would move through in executing the sequence of motions represented by the candidate motion plan;

determining, using the workcell volume cost map, costs associated with the robot moving through the various portions of space; and

determining the score for the candidate motion plan based on the costs associated with the robot moving through the various portions of space.

9. The method of claim 1 wherein the plurality of candidate motion plans meet a minimum diversity requirement between a particular motion plan in the plurality of candidate motion plans and an alternative motion plan not in the plurality of candidate motion plans.

10. The method of claim 9 wherein the minimum diversity requirement measures a difference between an amount of space represented by a 3D model for the particular motion plan and an amount of space represented by a 3D model for the alternative motion plan.

11. The method of claim 9 wherein the minimum diversity requirement measures a difference between an estimated duration of time to complete the particular motion plan and an estimated duration of time to complete the alternative motion plan.

12. The method of claim 9 wherein generating the plurality of candidate motion plans comprises:

generating a first plurality of motion plans; and

sampling motion plans from the first plurality of motion plans for inclusion in the plurality of candidate motion plans based on the minimum diversity requirement.

13. One or more non-transitory computer-readable media having instructions stored thereon that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

for each robot in a plurality of robots configured to operate in a shared workspace:

identifying a set of tasks assigned to the robot;

generating a plurality of candidate motion plans, each candidate motion plan representing a different sequence of motions for the robot to execute in performing the set of tasks;

for each candidate motion plan:

(i) generating a 3D model that represents a volume of space through which the robot would move in executing a sequence of motions represented by the candidate motion plan, and

(ii) determining a score for the candidate motion plan, the score based at least on a characteristic of the sequence of motions represented by the candidate motion plan or a characteristic of the volume of space represented by the 3D model for the candidate motion plan;

determining that a conflict occurs between a pair of candidate motion plans for different respective robots, including using respective 3D models for the pair of candidate motion plans to determine that an intersection occurs between respective volumes of space generated for the pair of candidate motion plans for the different respective robots;

in response, removing, from the plurality of candidate motion plans, one or more of the pair of candidate motion plans having the conflict due to the intersection between the respective volumes of space generated for the pair of candidate motion plans;

selecting, for each robot in the plurality of robots from candidate motion plans that remain among the plurality of candidate motion plans after removing the one or more of the pair of candidate motion plans having the conflict, a respective candidate motion plan based on the scores computed for the candidate motion plans; and

scheduling execution of the set of tasks including assigning one or more selected candidate motion plans to each robot of the plurality of robots.

14. The computer-readable media of claim 13 wherein the operations further comprise:

for each robot in the plurality of robots:

identifying a plurality of sets of tasks assigned to the robot;

generating a plurality of candidate motion plans for each set of tasks in the plurality of sets of tasks; and

selecting, for the robot, a motion plan from the plurality of candidate motion plans for each set of the plurality of sets of tasks.

15. The computer-readable media of claim 13 wherein identifying a set of tasks assigned to each robot of the plurality of robots comprises:

generating a plurality of clusters of tasks by assigning each task in the set of tasks to one of the plurality of clusters; and

for each cluster of the plurality of clusters, identifying one or more candidate robots from the plurality of robots to perform the tasks in the cluster.

16. The computer-readable media of claim 13 wherein the characteristic of the sequence of motions represented by the candidate motion plan includes an estimated duration of time to execute the candidate motion plan or an estimated complexity of a path traced by a corresponding robot during execution of the candidate motion plan.

17. The computer-readable media of claim 13 wherein the characteristic of the volume of space represented by the 3D model for the candidate motion plan includes an amount of space encompassed by the 3D model.

18. The computer-readable media of claim 13 , wherein the operations further comprise:

obtaining a workcell volume cost map, the workcell volume cost map describing costs associated with a robot occupying different portions of space in the shared workspace; and

wherein, for each robot in at least a subset of the plurality of robots and for each candidate motion plan in at least a subset of the plurality of candidate motion plans for the robot, determining the score for the candidate motion plan comprises:

determining various portions of space that the robot would move through in executing the sequence of motions represented by the candidate motion plan;

determining, using the workcell volume cost map, costs associated with the robot moving through the various portions of space; and

determining the score for the candidate motion plan based on the costs associated with the robot moving through the various portions of space.

19. The computer-readable media of claim 13 wherein the plurality of candidate motion plans meet a minimum diversity requirement between a particular motion plan in the plurality of candidate motion plans and an alternative motion plan not in the plurality of candidate motion plans.

20. A system for coordinating movements of a plurality of robots configured to operate in a shared workspace, the system comprising:

one or more computers; and

one or more computer-readable media having instructions stored thereon that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

for each robot in the plurality of robots:

identifying a set of tasks assigned to the robot;

generating a plurality of candidate motion plans, each candidate motion plan representing a different sequence of motions for the robot to execute in performing the set of tasks;

for each candidate motion plan:

(i) generating a 3D model that represents a volume of space through which the robot would move in executing a sequence of motions represented by the candidate motion plan, and

(ii) determining a score for the candidate motion plan, the score based at least on a characteristic of the sequence of motions represented by the candidate motion plan or a characteristic of the volume of space represented by the 3D model for the candidate motion plan;

determining that a conflict occurs between a pair of candidate motion plans for different respective robots, including using respective 3D models for the pair of candidate motion plans to determine that an intersection occurs between respective volumes of space generated for the pair of candidate motion plans for the different respective robots;

in response, removing, from the plurality of candidate motion plans, one or more of the pair of candidate motion plans having the conflict due to the intersection between the respective volumes of space generated for the pair of candidate motion plans;

selecting, for each robot in the plurality of robots from candidate motion plans that remain among the plurality of candidate motion plans after removing the one or more of the pair of candidate motion plans having the conflict, a respective candidate motion plan based on the scores for the candidate motion plans; and

scheduling execution of the set of tasks including assigning one or more selected candidate motion plans to each robot of the plurality of robots.