Anytime Solution Optimization for Sampling-Based Motion Planning

Authors

Ryan Luna, Ioan A. Sucan, Mark Moll, Lydia E. Kavraki

Year

2013

Conference Paper

Source

IEEE International Conference on Robotics and Automation (ICRA)

Identifiers

DOI 10.1109/ICRA.2013.6631301

Abstract¶

Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shortening techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.

Summary¶

Anytime algorithm that progressively improves path quality after an initial solution is found, combining random shortcutting with path hybridization. Algorithm 1 gives a particularly clear presentation of the shortcutting procedure.