Path planning using lazy PRM
Top Cited Papers
- 1 January 2000
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729) , 521-528 vol.1
- https://doi.org/10.1109/robot.2000.844107
Abstract
Describes an approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning and hence minimize the running time of the planner. Our algorithm builds a roadmap in the configuration space, whose nodes are the user-defined initial and goal configurations and a number of randomly generated nodes. Neighboring nodes are connected by edges representing paths between the nodes. In contrast with PRMs, our planner initially assumes that all nodes and edges in the roadmap are collision-free, and searches the roadmap at hand for a shortest path between the initial and the goal node. The nodes and edges along the path are then checked for collision. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap. Our planner either finds a new shortest path, or first updates the roadmap with new nodes and edges, and then searches for a shortest path. The above process is repeated until a collision-free path is returned. Lazy PRM is tailored to efficiently answer single planning queries, but can also be used for multiple queries. Experimental results presented in the paper show that our lazy method is very efficient in practice.Keywords
This publication has 18 references indexed in Scilit:
- The Gaussian sampling strategy for probabilistic roadmap plannersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A randomized roadmap method for path and manipulation planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Interference detection between non-convex polyhedra revisited with a practical aimPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Motion planning with many degrees of freedom-random reflections at C-space obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Enhancing GJK: computing minimum and penetration distances between convex polyhedraPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A two-level search algorithm for motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other ArtifactsThe International Journal of Robotics Research, 1999
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Gross motion planning—a surveyACM Computing Surveys, 1992
- Robot Motion Planning: A Distributed Representation ApproachThe International Journal of Robotics Research, 1991