Dynamic probabilistic motion planning

A system comprising:

• one or more computers;
• and
• one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
• receiving, by the one or more computers, a first path in a first probabilistic road map for a robot to travel through a physical area, the first path specifying a first subset of edges in the first probabilistic road map, wherein each edge is associated with a respective swept volume profile representing a volume of space occupied by the robot while traversing the edge, wherein the first path assigns a respective first time interval to each edge of the first subset of edges;
• receiving, by the one or more computers, a second path in a second probabilistic road map for a movable object to travel through the physical area, the second path specifying a second subset of edges in the second probabilistic road map, wherein each edge is associated with a respective swept volume profile representing a volume of space occupied by the object while traversing the edge, wherein the second path assigns a respective second time interval to each edge of the second subset of edges;
• determining that an intersection occurs between i) a first volume of space represented by a swept volume profile for a first edge of the first subset of edges for the robot and ii) a second volume of space represented by a swept volume profile for a second edge of the second subset of edges for the movable object during an overlapping time period between a first time interval assigned to the first edge and a second time interval assigned to the second edge;
• in response, evaluating a plurality of collision-free alternative edges for the robot in the first probabilistic road map, each collision-free alternative edge having a respective swept volume profile in the first probabilistic road map representing a respective volume of space that does not intersect the second volume of space that the movable object will occupy during the overlapping time period, and
• based on the evaluation, adding a collision-free alternative edge to the first path to generate an adjusted path for the robot using the first probabilistic road map.

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

• receiving, by the one or more computers, a first path in a first probabilistic road map for a robot to travel through a physical area, the first path specifying a first subset of edges in the first probabilistic road map, wherein each edge is associated with a respective swept volume profile representing a volume of space occupied by the robot while traversing the edge, wherein the first path assigns a respective first time interval to each edge of the first subset of edges;
• receiving, by the one or more computers, a second path in a second probabilistic road map for a movable object to travel through the physical area, the second path specifying a second subset of edges in the second probabilistic road map, wherein each edge is associated with a respective swept volume profile representing a volume of space occupied by the object while traversing the edge, wherein the second path assigns a respective second time interval to each edge of the second subset of edges;
• determining that an intersection occurs between i) a first volume of space represented by a swept volume profile for a first edge of the first subset of edges for the robot and ii) a second volume of space represented by a swept volume profile for a second edge of the second subset of edges for the movable object during an overlapping time period between a first time interval assigned to the first edge and a second time interval assigned to the second edge;
• in response, evaluating a plurality of collision-free alternative edges for the robot in the first probabilistic road map, each collision-free alternative edge having a respective swept volume profile in the first probabilistic road map representing a respective volume of space that does not intersect the second volume of space that the movable object will occupy during the overlapping time period, and
• based on the evaluation, adding a collision-free alternative edge to the first path to generate an adjusted path for the robot using the first probabilistic road map.