Improving sparse roadmap spanners
- 1 May 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4106-4111
- https://doi.org/10.1109/icra.2013.6631156
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.Keywords
This publication has 12 references indexed in Scilit:
- The Open Motion Planning LibraryIEEE Robotics & Automation Magazine, 2012
- Computing spanners of asymptotically optimal probabilistic roadmapsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Sampling-based algorithms for optimal motion planningThe International Journal of Robotics Research, 2011
- Learning approximate cost-to-go metrics to improve sampling-based motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- A Little More, a Lot Better: Improving Path Quality by a Path-Merging AlgorithmIEEE Transactions on Robotics, 2011
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphsRandom Structures & Algorithms, 2006
- Measure theoretic analysis of probabilistic path planningIEEE Transactions on Robotics and Automation, 2004
- Useful cycles in probabilistic roadmap graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Visibility-based probabilistic roadmaps for motion planningAdvanced Robotics, 2000