Asymptotically Near-Optimal is Good Enough for Motion Planning

TitleAsymptotically Near-Optimal is Good Enough for Motion Planning
Publication TypeConference Paper
Year of Publication2011
AuthorsMarble, J, Bekris, KE
Conference NameProc. of the 15th International Symposium on Robotics Research (ISRR-11)
Date Published28. Aug. - 1 Sep
Conference LocationFlagstaff, AZ

Asymptotically optimal motion planning algorithms guarantee solutions approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can be slow to construct and grow too large for storage or fast online query resolution. From graph theory, there are many algorithms that produce sparse subgraphs, known as spanners, which can guarantee near-optimal paths. In this work, a method for interleaving an incremental graph spanner algorithm with an asymptotically optimal motion planning algorithm is described. The result is an asymptotically near-optimal motion planning algorithm. Theoretical analysis and experiments performed on typical, geometric problems show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality. If smoothing is applied, the results are even more favorable for the near-optimal solution.

Refereed DesignationRefereed