Dynamic probabilistic motion planning

Patent metadata

Field	Value
Publication number	US-11911908-B2
Application number	US-201816229484-A
Country	US
Kind code	B2
Filing date	Dec 21, 2018
Priority date	Dec 21, 2018
Publication date	Feb 27, 2024
Grant date	Feb 27, 2024

Abstract

Techniques and systems are disclosed for using swept volume profile data cached in association with a PRM to improve various aspects of motion planning for a robot. In some implementations, a first probabilistic road map representing possible paths to be travelled by a robot within a physical area is generated. An initial path for the robot within the first probabilistic road map is determined. Data indicating a second probabilistic road map representing a path to be travelled by a movable object within the physical area is obtained. A potential obstruction associated with one or more edges included in the subset of edges is detected. An adjusted path for the robot within the first probabilistic road map is then determined based on the potential obstruction.

First claim

The invention claimed is:

1. A method performed by one or more computers, the method 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.

2. The method of claim 1 , wherein determining that the intersection occurs comprises:
comparing the respective swept volume profiles of the robot that are associated with the first subset of edges specified by the first path during all of the respective first time intervals and the respective swept volume profiles of the movable object that are associated with the second subset of edges during all of the respective second time intervals corresponding to the respective first time intervals;
determining, based on the comparison, that at least one of the respective swept volume profiles of the robot that are associated with the first subset of edges specified by the first path intersects with at least one of the respective swept volume profiles of the movable object that are associated with the second subset of edges specified by the second path during an overlapping time period between one of the respective first time intervals and one corresponding second time interval of the respective second time intervals; and
determining that the intersection occurs based on the determination that the at least one of the respective swept volume profiles of the robot associated with the first subset of edges specified by the first path intersects with the at least one of the respective swept volume profiles of the movable object associated with the second subset of edges specified by the second path during the overlapping time period.

3. The method of claim 1 , wherein each swept volume profile included in the respective swept volume profiles of the robot for the first path specifies a maximum traversable area by the robot within a physical space in association with a particular edge of the first subset of edges.

4. The method of claim 1 , wherein each swept volume profile included in the respective swept volume profiles of the robot for the first path specifies a set of voxels representing the maximum traversable volume by the robot within a physical space in association with a particular edge of the first subset of edges.

5. The method of claim 1 , wherein the robot is a first robot, and wherein the movable object comprises a second robot that is planned to or expected to travel within the physical area while the first robot travels in the physical area.

6. The method of claim 1 , wherein generating the adjusted path for the robot using the first probabilistic road map comprises:
identifying a plurality of alternative paths corresponding to the first path, wherein: each alternative path within the plurality of alternative path includes (i) a first node representing a start point of the first path and (ii) a second node representing an end point of the first path, and
each alternative path includes a different set of intermediate edges between the first node and the second node; and
selecting a particular alternative path from the plurality of alternative paths as the adjusted path.

7. The method of claim 1 , wherein:
the method further comprises determining that a number of edges included in the first subset of edges that have respective swept volume profiles intersecting with respective swept volume profiles of the second path satisfies a predetermined threshold; and
generating another adjusted path for the robot using the first probabilistic road map comprises:
invalidating the first path based on the determination that the number of edges included in the first subset of edges that have respective swept volume profiles intersecting with respective swept volume profiles of the second path satisfies the predetermined threshold; and
recalculating a new path for the robot as the other adjusted path using the first probabilistic road map.

8. The method of claim 1 , comprising determining one or more intersections occur between one or more edges of the first subset of edges and one or more corresponding edges of the second subset of edges during one or more overlapping time periods between respective first time intervals and second time intervals corresponding to the respective first time intervals; and
wherein generating the adjusted path for the robot comprises re-routing travel of the robot such that the adjusted path omits the one or more edges of the first subset of edges and includes one or more of the plurality of collision-free alternative edge.

9. The method of claim 1 , wherein determining that the intersection occurs comprises:
determining a time synchronization for travel of the robot along the first path and travel of the movable object along the second path; and
selectively comparing swept volume profiles for respective edges of the first path and the second path based on the time synchronization.

10. The method of claim 1 , determining that the intersection occurs comprises:
identifying, for each of the respective first time intervals, one or more first edges of the first subset of edges that the robot is expected to travel along the first path during the first time interval;
identifying, for each of the respective second time intervals, one or more second edges of the second subset of edges that the movable object is expected to travel along the second path during the second time interval; and
comparing, for each overlapping time period between each of the respective first time intervals and each corresponding second time interval of the respective second time intervals, the respective swept volume profiles for the one or more first edges expected to be traveled by the robot and the one or more second edges expected to be traveled by the movable object during the overlapping time period to determine whether the intersection occurs.

Assignees

• Intrinsic Innovation Llc

Inventors

• Dupuis Jean-Francois
• Go Keegan
• Hemmer Michael

Classifications

• G05D1/246

  using environment maps, e.g. simultaneous localisation and mapping [SLAM] · CPC title

• B25J9/1666 Primary

  Avoiding collision or forbidden zones · CPC title

• G05D1/0214

  in accordance with safety or protection criteria, e.g. avoiding hazardous areas (monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13) · CPC title

• G05D1/0274

  using mapping information stored in a memory device (navigation using map-matching G01C21/30) · CPC title

• G05D1/0289

  with means for avoiding collisions between vehicles (vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93) · CPC title