Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. A recently proposed roadmap-based method, i.e., the$\hbox{\tt 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, which are known as graph spanners, that guarantee near-optimal paths. This paper proposes different alternatives for interleaving graph spanners with the asymptotically optimal$\hbox{\tt PRM}^{*}$algorithm. The first alternative follows a sequential approach, where a graph spanner algorithm is applied to the output roadmap of$\hbox{\tt PRM}^{*}$. The second one is an incremental method, where certain edges are not considered during the construction of the roadmap as they are not necessary for 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.

An exciting recent development is the definition of sampling-based motion planners which guarantee asymptotic optimality. Nevertheless, roadmaps with this property may grow too large and lead to longer query resolution times. If optimality requirements are relaxed, existing asymptotically near-optimal solutions produce sparser graphs by removing redundant edges. Even these alternatives, however, include all sampled configurations as nodes in the roadmap. This work proposes a method, which can reject redundant samples but does provide asymptotic coverage and connectivity guarantees, while keeping local path costs low. Not adding every sample can significantly reduce the size of the final roadmap. An additional advantage is that it is possible to define a reasonable stopping criterion for the approach inspired by previous methods. To achieve these objectives, the proposed method maintains a dense graph that is used for evaluating the performance of the roadmap with regards to local path costs. Experimental results show that the method indeed provides small roadmaps, allowing for shorter query resolution times. Furthermore, smoothing the final paths results in an even more advantageous comparison against alternatives with regards to path quality.

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.