Probabilistic Roadmap Method

The Probabilistic Roadmap (PRM) [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):566-580, June 1996.] method is a motion planning algorithm in robotics, which solves the problem of determining a path between a starting configuration of the robot and a goal configuration while avoiding collisions.

The basic idea behind PRM is to take random samples from the configuration space of the robot, testing them for whether they are in the free space, and use a local planner to attempt to connect these configurations to other nearby configurations. The starting and goal configurations are added in, and a graph search algorithm is applied to the resulting graph to determine a path between the starting and goal configurations.

PRM is provably probabilistically complete, meaning that as the number of sampled points increases without bound, the probability that the algorithm won't find a path if one exists approaches zero.

References

The probabilistic roadmap method consists of two phases:a construction and a query phase. In the construction phase, aroadmap (graph) is built, approximating the motions that canbe made in the environment. First, a random con�gurationis created. Then, it is connected to some useful neighbors. Aneighbor is useful if its distance to the new con�guration is lessthan a predetermined constant. Con�gurations and connectionsare added to the graph until the roadmap is dense enough.In the query phase, the start and goal con�gurations areconnected to the graph. The path is obtained by a Dijkstra'sshortest path query. See e.g. [Roland Geraerts and Mark H. Overmars. A Comparative Study of Probabilistic Roadmap Planners. In Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR'02), 2002, pp. 43-57. ] for a more extensive elaborationof the PRM method.