Narrow passage sampling for probabilistic roadmap planning

Sun, Zheng, Hsu, David, Jiang, Tingting, Kurniawati, Hanna and Reif, John H. (2005) Narrow passage sampling for probabilistic roadmap planning. IEEE Transactions on Robotics, 21 6: 1105-1115. doi:10.1109/TRO.2005.853485

Author Sun, Zheng
Hsu, David
Jiang, Tingting
Kurniawati, Hanna
Reif, John H.
Title Narrow passage sampling for probabilistic roadmap planning
Journal name IEEE Transactions on Robotics   Check publisher's open access policy
ISSN 1552-3098
Publication date 2005-12-01
Sub-type Article (original research)
DOI 10.1109/TRO.2005.853485
Open Access Status Not yet assessed
Volume 21
Issue 6
Start page 1105
End page 1115
Total pages 11
Place of publication Piscataway, NJ, United States
Publisher Institute of Electrical and Electronics Engineers
Language eng
Formatted abstract
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.
Keyword Motion planning
Probabilistic roadmap (PRM) planner
Random sampling
Randomized algorithm
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 45 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 67 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 15 Apr 2014, 06:59:29 EST by Ms Kimberley Nunes on behalf of Centre for Medical Diagnostic Technologies in Qld