Improving sparse roadmap spanners

Andrew Dobson, Kostas Bekris

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

16 Scopus citations


Roadmap spanners provide a way to acquire sparse data structures that efficiently answer motion planning queries with probabilistic completeness and asymptotic near-optimality. The current SPARS method provides these properties by building two graphs in parallel: a dense asymptotically-optimal roadmap based on PRM* and its spanner. This paper shows that it is possible to relax the conditions under which a sample is added to the spanner and provide guarantees, while not requiring the use of a dense graph. A key aspect of SPARS is that the probability of adding nodes to the roadmap goes to zero as iterations increase, which is maintained in the proposed extension. The paper describes the new algorithm, argues its theoretical properties and evaluates it against PRM* and the original SPARS algorithm. The experimental results show that the memory requirements of the method upon construction are dramatically reduced, while returning competitive quality paths with PRM*. There is a small sacrifice in the size of the final spanner relative to SPARS but the new method still returns graphs orders of magnitudes smaller than PRM*, leading to very efficient online query resolution.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Number of pages6
StatePublished - Nov 14 2013
Event2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany
Duration: May 6 2013May 10 2013

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Other2013 IEEE International Conference on Robotics and Automation, ICRA 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Improving sparse roadmap spanners'. Together they form a unique fingerprint.

Cite this