Lazy collision checking in asymptotically-optimal motion planning
- 1 May 2015
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2951-2957
- https://doi.org/10.1109/icra.2015.7139603
Abstract
Asymptotically-optimal sampling-based motion planners, like RRT*, perform vast amounts of collision checking, and are hence rather slow to converge in complex problems where collision checking is relatively expensive. This paper presents two novel motion planners, Lazy-PRM* and Lazy-RRG*, that eliminate the majority of collision checks using a lazy strategy. They are sampling-based, any-time, and asymptotically complete algorithms that grow a network of feasible vertices connected by edges. Edges are not immediately checked for collision, but rather are checked only when a better path to the goal is found. This strategy avoids checking the vast majority of edges that have no chance of being on an optimal path. Experiments show that the new methods converge toward the optimum substantially faster than existing planners on rigid body path planning and robot manipulation problems.Keywords
This publication has 13 references indexed in Scilit:
- Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Asymptotically near-optimal RRT for fast, high-quality, motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Sparse roadmap spanners for asymptotically near-optimal motion planningThe International Journal of Robotics Research, 2014
- Sampling heuristics for optimal motion planning in high dimensionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Sampling-based algorithms for optimal motion planningThe International Journal of Robotics Research, 2011
- Rapidly-exploring roadmaps: Weighing exploration vs. refinement in optimal motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- On Delaying Collision Checking in PRM Planning: Application to Multi-Robot CoordinationThe International Journal of Robotics Research, 2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Fully Dynamic Algorithms for Maintaining Shortest Paths TreesJournal of Algorithms, 2000
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996