Sparse Roadmap Spanners for Asymptotically NearOptimal Motion Planning
Submitted by bekris on Wed, 06/26/2013  22:17
Title  Sparse Roadmap Spanners for Asymptotically NearOptimal Motion Planning 
Publication Type  Journal Article 
Year of Publication  2014 
Authors  Dobson, A, Bekris, KE 
Journal  International Journal of Robotics Research (IJRR) 
Volume  33 
Issue  1 
Pagination  1847 
Date Published  01/2014 
Abstract  Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as the number of iterations increases. Roadmaps with this property, however, may grow too large for storing on resourceconstrained robots and for achieving efficient online query resolution. By relaxing optimality, asymptotically nearoptimal planners produce sparser graphs by not including all edges. The idea
stems from graph spanners, which produce sparse subgraphs that guarantee nearoptimality. Existing asymptotically optimal and nearoptimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinitesize graphs have the desired properties. To address this limitation, this work describes SPARS, an algorithm that returns a sparse roadmap spanner. The method provides the following properties: (a) probabilistic completeness, (b) asymptotic nearoptimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. The last point suggests that finitesize data structures with asymptotic nearoptimality in continuous spaces may indeed exist. The approach builds simultaneously a dense graph similar to PRM* and its
roadmap spanner, meaning that upon construction an infinitesize graph is still needed asymptotically. An extension of SPARS is also presented, termed SPARS2, which removes the dependency on building a dense graph for constructing the sparse roadmap spanner and for which it is shown that the same desirable properties hold.
Simulations for rigid body motion planning show that algorithms for constructing sparse roadmap spanners indeed provide small data structures and result in faster query resolution. The rate of node addition is shown to decrease over time and practically the quality of solutions is considerably better than the theoretical bounds. Upon construction, the memory requirements of SPARS2 are significantly
smaller but there is a small sacrifice in the size of the final spanner relative to SPARS.

URL  http://www.cs.rutgers.edu/~kb572/pubs/spars_ijrr.pdf 