Improving Sparse Roadmap Spanners

TitleImproving Sparse Roadmap Spanners
Publication TypeConference Paper
Year of Publication2013
AuthorsDobson, A, Bekris, KE
Conference NameIEEE International Conference on Robotics and Automation (ICRA)
Date Published05/2013
Conference LocationKarlsruhe, Germany

Roadmap spanners have been proposed as a way to acquire sparse data structures that can efficiently answer path queries in continuous spaces with probabilistic completeness and asymptotic near-optimality guarantees. The current construction method, named SPARS, provides these properties by constructing in parallel a relatively dense asymptotically-optimal roadmap based on PRM*. This feature limits the method's benefits. This paper shows that it is possible to relax the conditions under which a sample is added to the spanner and provide the desired properties, 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 over increasing iterations, 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 suggest that the memory requirements of the method upon construction are dramatically reduced, while it returns competitive quality paths for the same construction time 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.

Refereed DesignationRefereed