MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (10504729), 1024-1031
- https://doi.org/10.1109/robot.1999.772448
Abstract
Probabilistic roadmap planning methods have been shown to perform well in a number of practical situations, but their performance degrades when paths are required to pass through narrow passages in the free space. We propose a new method of sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. We give algorithms that perform this retraction while avoiding explicit computation of the medial axis, and we show that sampling and retracting in this manner increases the number of nodes found in small volume corridors in a way that is independent of the volume of the corridor and depends only on the characteristics of the obstacles bounding it. Theoretical and experimental results are given to show that this improves performance on problems requiring traversal of narrow passages.Keywords
This publication has 6 references indexed in Scilit:
- Enhancing GJK: computing minimum and penetration distances between convex polyhedraPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Mathematical theory of medial axis transformPacific Journal of Mathematics, 1997
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Distance Metrics on the Rigid-Body Motions with Applications to Mechanism DesignJournal of Mechanical Design, 1995
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Robot Motion PlanningPublished by Springer Nature ,1991