Improved Heuristic Search for Sparse Motion Planning Data Structures

Authors

  • Andrew Dobson Rutgers University
  • Kostas Bekris Rutgers University

Keywords:

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

Abstract

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.

Downloads

Published

2021-09-01