Narrow passage sampling for probabilistic roadmap planning

Zheng Sun*, D. Hsu, Tingting Jiang, H. Kurniawati, J. H. Reif

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

127 Citations (Scopus)


Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

Original languageEnglish
Pages (from-to)1105-1115
Number of pages11
JournalIEEE Transactions on Robotics
Issue number6
Publication statusPublished - Dec 2005
Externally publishedYes

Scopus Subject Areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Motion planning
  • Probabilistic roadmap (PRM) planner
  • Random sampling
  • Randomized algorithm
  • Robotics


Dive into the research topics of 'Narrow passage sampling for probabilistic roadmap planning'. Together they form a unique fingerprint.

Cite this