Finding narrow passages with probabilistic roadmaps: the small step retraction method
Authors:
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21530858,p. 622-627
Abstract
The efficiency of probabilistic roadmap (PRM) planners drops dramatically in spaces with narrow passages. This paper presents a new method - small-step retraction - that helps PRM planners find paths through such passages. The method consists of slightly fattening the robot's free space, constructing a roadmap in the fattened free space, and repairing colliding portions of this roadmap by retracting them out of collision. The fattened free space is not explicitly computed. Instead, the robot links and/or obstacles are thinned around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are used. The "optimist" strategy waits until a complete path has been found in fattened free space before repairing it. The "pessimist" strategy repairs the roadmap as it is being built. The former is faster, but the latter is more reliable. A simple combination yields an integrated planner that is both fast and reliable.Keywords
This publication has 15 references indexed in Scilit:
- Synthesizing animations of human manipulation tasks2004
- The bridge test for sampling narrow passages with probabilistic roadmap planners2004
- Constructing probabilistic roadmaps with powerful local planning and path optimization2003
- MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space2003
- Efficient distance computation between non-convex objects2002
- Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams2002
- A framework for using the workspace medial axis in PRM planners2000
- PATH PLANNING IN EXPANSIVE CONFIGURATION SPACESInternational Journal of Computational Geometry & Applications, 1999
- Analysis of probabilistic roadmaps for path planningIEEE Transactions on Robotics and Automation, 1998
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996