Computing Spanners of Asymptotically Optimal Probabilistic Roadmaps

TitleComputing Spanners of Asymptotically Optimal Probabilistic Roadmaps
Publication TypeConference Paper
Year of Publication2011
AuthorsMarble, J, Bekris, KE
Conference NameIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11)
Date Published25-30 Sept.
Conference LocationSan Francisco, CA

Asymptotically optimal motion planning algorithms guarantee solutions 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, \nao 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.

Refereed DesignationRefereed