Probabilistic Roadmap Method

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.