Asymptotically near-optimal is good enough for motion planning

James D. Marble, Kostas E. Bekris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. There is a recently proposed roadmap-based method that provides this desirable property, the PRM* approach, which minimizes the computational cost of generating the roadmap. Even for this method, however, the roadmap can be slow to construct and quickly grows 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 the asymptotically optimal PRM* algorithm is described. The result is an asymptotically near-optimal motion planning solution. Theoretical analysis and experiments performed on typical, geometric motion planning instances 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.

Original languageEnglish (US)
Title of host publicationRobotics Research - The 15th International Symposium ISRR
EditorsHenrik I. Christensen, Oussama Khatib
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783319293622
StatePublished - 2017
Externally publishedYes
Event15th International Symposium of Robotics Research, 2011 - Flagstaff, United States
Duration: Dec 9 2011Dec 12 2011

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Other15th International Symposium of Robotics Research, 2011
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Asymptotically near-optimal is good enough for motion planning'. Together they form a unique fingerprint.

Cite this