Paper Info
Title
Improving sparse roadmap spanners
Abstract
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.
Year
DOI
Venue
2013
10.1109/ICRA.2013.6631156
Robotics and Automation
Keywords
Field
DocType
data structures,graph theory,mobile robots,path planning,probability,SPARS method,asymptotic near-optimality,dense asymptotically-optimal roadmap,dense graph,motion planning queries,online query resolution,probabilistic completeness,sparse data structures,sparse roadmap spanners improvement
Graph theory,Motion planning,Data structure,Theoretical computer science,Probabilistic logic,Spanner,Completeness (statistics),Sparse matrix,Mathematics,Dense graph
Conference
Volume
Issue
ISSN
2013
1
1050-4729
ISBN
Citations 
PageRank 
978-1-4673-5641-1
9
0.63
References 
Authors
11
2
Name
Order
Citations
PageRank
Andrew Dobson1503.90
Kostas E. Bekris293899.49