Probabilistic Roadmap Method

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration uses the probabilistic roadmap method (PRM) to connect configurations from an initial configuration (shown by a Locator) to a goal configuration. First, click the button "add 50 vertices" to randomly sample configurations and calculate if they collide with obstacles (red) or are safe (green). Next, select a "radius" value to try and connect safe vertices less than the radius distance into a roadmap. If a path from the initial to the goal configuration is found, it can be traversed using the "progress" slider. Although the PRM does not need to calculate the configuration space obstacles, you can make them visible by clicking the checkbox.

Contributed by: Aaron T. Becker and Yitong Lu (January 2020)
Open content licensed under CC BY-NC-SA


Details

The goal of robot motion planning is to find a continuous path from an initial configuration to a goal configuration that is collision-free. A configuration is a complete specification of every point on the robot. This Demonstration assumes the configuration of the robot is specified by two angles, each from 0 to . The resulting configuration space is shaped like a toroid, and so wraps from to 0 on the edges of the plot shown. Obstacles in the robot's workspace map to obstacle regions in the configuration space, but computing these regions is computationally expensive.

Instead, the probabilistic roadmap method (PRM) attempts to solve the motion planning problem by building a graph that represents the connectivity of the configuration space. This avoids the need to explicitly compute the configuration space obstacles, and changes the motion-planning problem into a graph-search problem. It requires (a) being able to determine whether a configuration is in collision with any obstacle; and (b) a "local planner" that can quickly determine if two configurations can be joined by a collision-free path. Typically this local planner checks if a straight-line path in the configuration space is possible.

The PRM has three parts:

(1) Generate random points in the configuration space and calculate if they are in the free configuration space (green points) or in collision with obstacles (red points).

(2) Attempt to connect points in the free configuration space to their nearest neighbors less than radius distance apart using the local planner. Parts (1) and (2) generate the roadmap.

(3) The local planner attempts to connect the initial configuration to the nearest point in the roadmap and the goal configuration to the nearest point in the roadmap. Then a graph search is used (A* search in this Demonstration) to find the shortest path in the roadmap.

PRM was developed in 1996 by Lydia Kavraki et al. [1]. PRMs generate a roadmap that can be reused for subsequent motion planning queries. PRM was designed for high-dimension configuration spaces (dimensions of five or more), but this Demonstration uses two dimensions for ease of visualization.

Reference

[1] L. E. Kavraki, P. Svestka, J.-C. Latombe and M. H. Overmars, "Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces," IEEE Transactions on Robotics and Automation, 12(4), 1996 pp. 566–580. doi:10.1109/70.508439.


Snapshots



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send