Improved Heuristic Search for Computing Sparse Data Structures for Motion Planning

TitleImproved Heuristic Search for Computing Sparse Data Structures for Motion Planning
Publication TypeConference Paper
Year of Publication2014
AuthorsDobson, A, Bekris, KE
Conference NameSymposium on Combinatorial Search (SoCS)
Date Published08/2014
Conference LocationPrague, Czech Republic
Abstract

Sampling-based motion planners provide efficient, flexible solutions
for computing motion, even for relatively complex systems operating in
high-dimensional spaces. Asymptotically optimal variants of these
planners ensure convergence to the optimal solution, but produce
prohibitively dense structures. This work shows how to extend sparse
methods achieving asymptotic near-optimality by performing
multiple-goal heuristic search during graph construction. The result
is an extension of an existing framework for sparse motion planning
roadmaps, the Incremental Roadmap Spanner, which produces identical
output, but does so in an order of magnitude less time.

URLhttp://www.aaai.org/ocs/index.php/SOCS/SOCS14/paper/viewFile/8919/8898