Probabilistic roadmaps for robot path planning

The Probabilistic RoadMap planner (PRM) has been applied with success to multiple planning problems involving robots with 3 to 16 degrees of freedom (dof) operating in known static environments. This paper describes the planner and reports on experimental and theoretical results related to its performance. PRM computation consists of a preprocessing and a query phase. Preprocessing, which is done only once for a given environment, generates a roadmap of randomly, but properly selected, collision-free configurations (nodes). Planning then connects any given initial and final configurations of the robot to two nodes of the roadmap and computes a path through the roadmap between these two nodes. The planner is able to find paths involving robots with 10 dof in a fraction of a second after relatively short times for preprocessing (a few dozen seconds). Theoretical analysis of the PRM algorithm provides bounds on the number of roadmap nodes needed for solving planning problems in spaces with certain geometric properties. A number of theoretical results are presented in this paper under a unified framework