Computing spanners of asymptotically optimal probabilistic roadmaps

Abstract

Asymptotically optimal motion planning algorithms guarantee solutions that approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can grow too large and unwieldy for fast online query resolution. In graph theory there are many algorithms that produce subgraphs, known as spanners, which have guarantees about path quality. Applying such an algorithm to a dense, asymptotically optimal roadmap produces a sparse, asymptotically near optimal roadmap. Experiments performed on typical, geometric problems in SE(3) show that a large reduction in roadmap edges can be achieved with a small increase in path length. Online queries are answered much more quickly with similar results in terms of path quality. This also motivates future work that applies the technique incrementally so edges that won't increase path quality will never be added to the roadmap and won't be checked for collisions.