Computing spanners of asymptotically optimal probabilistic roadmaps

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.

I. Introduction

Roadmap planners [1] utilize an off-line phase to build up knowledge about the configuration space (-space) before queries can be answered in complex -spaces. Path quality can be measured in terms of length, clearance, or smoothness [2]. Traditionally, many techniques focus on feasibility and may return paths of low quality; considerably different from the optimum ones. Smoothing can be used to improve some measures of path quality and algorithms exist that produce roadmaps with paths that are deformable to optimal ones [3], [4]. Hybridization graphs [5] combine multiple solutions into a higher quality one that uses the best portions of each input path. These techniques, however, can be expensive for the online resolution of a query, especially when multiple queries must be answered.