Probabilistic roadmaps - Putting it all together

L. K. Dale, Nancy Marie Amato

Research output: Contribution to journalConference articlepeer-review


Given a robot and a workspace, probabilistic roadmap planners (PRMs) 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 PRMs in such a way that the strengths are combined and the weaknesses offset. Our meta-planner will perform the combination in the following manner, i) Provide a framework in which different motion planners are available and to which new ones are easily added. ii) Characterize subregions (possibly overlapping) based on sample characteristics and connection results. iii) Assign subregions to one or more planners which are judged promising. iv) Provide stopping criteria for roadmap construction. We present experimental results for four characterization measures. A general technique we call 'filtering' is presented for keeping roadmaps compact.

Original languageEnglish (US)
Pages (from-to)1940-1947
Number of pages8
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 2001
Externally publishedYes
Event2001IEEE International Conference on Robotics and Automation (ICRA) - Seoul, Korea, Republic of
Duration: May 21 2001May 26 2001

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Probabilistic roadmaps - Putting it all together'. Together they form a unique fingerprint.

Cite this