Improved Heuristic Search for Sparse Motion Planning Data Structures

Sampling-based methods provide efficient, flexible solutions for motion planning, even for complex, high-dimensional systems. Asymptotically optimal planners ensure convergence to the optimal solution, but produce dense structures. This work shows how to extend sparse methods achieving asymptotic near-optimality using multiple-goal heuristic search during graph constuction. The resulting method produces identical output to the existing Incremental Roadmap Spanner approach but in an order of magnitude less time.

Authors

• Andrew Dobson
• Kostas E. Bekris

Keywords

• Motion Planning
• Sparse Structures
• Asymptoic Near-Optimality
• Multi-goal A*