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 of the robot. This Demonstration uses a two-link robot with two rotational joints that can each rotate from 0 to 2. The resulting configuration space can be represented as a toroid, and so wraps from 2 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.

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. [1]. 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 two dimensions for ease of visualization.

[1] 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.