Narrow passage sampling for probabilistic roadmap planning
- 5 December 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 21 (6), 1105-1115
- https://doi.org/10.1109/tro.2005.853485
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.Keywords
This publication has 22 references indexed in Scilit:
- Hybrid PRM Sampling with a Cost-Sensitive Adaptive StrategyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular MotionJournal of Computational Biology, 2003
- Visibility based probabilistic roadmapsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On Frictional Mechanical Systems and Their Computational PowerSIAM Journal on Computing, 2003
- Efficient distance computation between non-convex objectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Random Sampling Scheme for Path PlanningThe International Journal of Robotics Research, 1997
- Lower Bounds for Geometrical and Physical ProblemsSIAM Journal on Computing, 1996
- OBBTreePublished by Association for Computing Machinery (ACM) ,1996
- Robot Motion PlanningPublished by Springer Science and Business Media LLC ,1991
- Complexity of the mover's problem and generalizationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979