Robot planning from process definition graph

A system comprising one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

• receiving a process definition graph, the process definition graph having a plurality of task nodes that represent tasks to be performed by a plurality of robots, wherein each task node is associated with a location at which the task will be performed;
• generating, from the process definition graph, an initial modified process definition graph associated with constraints that disallow conflicts between robot motion plans and swept volumes for the tasks represented by the plurality of task nodes, the swept volume for a particular task defining a region of space to be occupied by at least a portion of a robot performing the particular task;
• generating, from the initial modified process definition graph, a refined process definition graph, including iteratively:
• identifying an ordering of tasks indicating an order in which the tasks are to be assigned;
• and
• for each task and according to the ordering:
• assigning the task to a respective candidate robot for performing the task;
• and
• determining a candidate motion plan for the candidate robot performing the task, wherein the candidate motion plan defines a transition of the candidate robot that avoids the swept volumes for the tasks,
• wherein the refined process definition graph includes respective represents sets of candidate motion plans for the plurality of robots determined according to multiple different orderings of the tasks;
• and
• after generating the refined process definition graph:
• selecting, from the refined process definition graph, a particular set of candidate motion plans determined according to a particular ordering of the tasks of the multiple different orderings of the tasks;
• and
• generating a schedule for the plurality of robots to perform the tasks using the particular set of candidate motion plans, including assigning each task to be performed by a respective robot of the plurality of robots.

A non-transitory computer storage medium encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

• receiving a process definition graph, the process definition graph having a plurality of task nodes that represent tasks to be performed by a plurality of robots, wherein each task node is associated with a location at which the task will be performed;
• generating, from the process definition graph, an initial modified process definition graph associated with constraints that disallow conflicts between robot motion plans and swept volumes for the tasks represented by the plurality of task nodes, the swept volume for a particular task defining a region of space to be occupied by at least a portion of a robot performing the particular task;
• generating, from the initial modified process definition graph, a refined process definition graph, including iteratively:
• identifying an ordering of tasks indicating an order in which the tasks are to be assigned;
• and
• for each task and according to the ordering:
• assigning the task to a respective candidate robot for performing the task;
• and
• determining a candidate motion plan for the candidate robot performing the task, wherein the candidate motion plan defines a transition of the candidate robot that avoids the swept volumes for the tasks,
• wherein the refined process definition graph represents sets of candidate motion plans for the plurality of robots determined according to multiple different orderings of the tasks;
• and
• after generating the refined process definition graph:
• selecting, from the refined process definition graph, a particular set of candidate motion plans determined according to a particular ordering of the tasks of the multiple different orderings of the tasks;
• and
• generating a schedule for the plurality of robots to perform the tasks using the particular set of candidate motion plans, including assigning each task to be performed by a respective robot of the plurality of robots.