Patent ID: 11911908
Assignee: INTRINSIC INNOVATION LLC
Field: Control (Instruments)
Classification: CPC B  G | IPC B  G

Claim 10:
11. 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.