Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners

TitleAsymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners
Publication TypeJournal Article
Year of Publication2013
AuthorsMarble, J, Bekris, KE
JournalIEEE Transactions on Robotics

Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. A recently proposed roadmap-based method, the PRM* approach, provides this desirable property and minimizes the computational cost of generating the roadmap. Even for this method, however, the roadmap can be slow to construct and quickly grows too large for storage or fast online query resolution, especially for relatively high-dimensional instances. In graph theory there are algorithms that produce sparse subgraphs, known as graph spanners, which guarantee near-optimal paths. This work proposes different alternatives for interleaving graph spanners with the asymptotically optimal PRM* algorithm. The first alternative follows a sequential approach, where a graph spanner algorithm is applied on the output roadmap of PRM*. The second one is an incremental method, where during the construction of the roadmap, certain edges are not considered as they are not necessary for the construction of a roadmap spanner. The result in both cases is an asymptotically near-optimal motion planning solution. Theoretical analysis and experiments performed on typical, geometric motion planning instances show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality through roadmap spanners.

Refereed DesignationRefereed