Probabilistic Roadmap Method in 3D
This Demonstration uses the probabilistic roadmap method (PRM) to plan a motion path for a three-link robot in a 3D configuration space that avoids collisions with a blue and a yellow sphere. If a path from the initial configuration to the goal configuration is found, it can be traversed by moving the "progress" slider. To generate a new roadmap, click "restart" and then click "add 100 vertices" to randomly sample configurations and calculate if they collide with obstacles (red points) or are safe (green points). If no path is found, continue adding vertices or increase the "radius" value to try to connect safe vertices less than radius distance apart into a roadmap. Although the PRM does not need to calculate the configuration space obstacles, you can make them visible with a checkbox.
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 of the robot. This Demonstration uses a three-link robot with three rotational joints that can each rotate from 0 to . The joints can each rotate independently either clockwise or counterclockwise. Obstacles in the robot's workspace map to obstacle regions in a 3D configuration space. The robot's joint angles are specified by , and . You can adjust the two obstacle positions in 3D. The "restart" button removes all the sampled configurations, and the "new goal" button randomly assigns a new goal position.
Changing the obstacle positions requires rebuilding the roadmap. Longer radius values require more computation but result in a denser roadmap and shorter paths.
PRM was developed in 1996 by Lydia Kavraki et al. . PRMs generate a roadmap that can be reused for subsequent motion-planning queries. PRM was designed for high-dimension configuration spaces (dimensions of 5 or more), but this Demonstration uses three dimensions for ease of visualization.
 L. E. Kavraki, P. Svestka, J-C. Latombe and Mark 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.