Probabilistic Roadmaps - Putting It All Together

Lucia K. Dale
Mathematics & Computer Science
University of the South
Sewanee, TN 37383-1000
ldale D0T sewanee D0T edu
Nancy M. Amato
Computer Science
Texas A&M University
College Station, TX 77843-3112


Given a robot and a workspace, probabilistic roadmap planners (PRM's) build a roadmap of paths sampled from the workspace. A roadmap node is a single collision--free robot configuration, randomly generated. A roadmap edge is a sequence of collision--free robot configurations which interpolate the path from one roadmap node to another. Queries to the roadmap are (start, goal) pairs. If both the start and goal of a pair can be connected to the same connected component of the roadmap, the query is solved.

Many promising variants of the PRM have been proposed, each with their own strengths and weaknesses. We propose a meta--planner for using many PRM's in such a way that the strengths are combined and the weaknesses offset.

Our meta--planner will perform the combination in the following manner.

We present experimental results for four characterization measures. A general technique we call `filtering' is presented for keeping roadmaps compact.

In Proceedings of the 2001 IEEE International Conference on Robotics and Automation (ICRA'01), 2001. Full Paper (postscript)