Anytime solution optimization for sampling-based motion planning

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.

I. Introduction

The canonical motion planning problem involves computing a valid path for a robot to move from a given start to a given goal state while respecting a set of physical constraints [1]–[3]. This problem is motivated by an ever-growing number of practical applications such as autonomous exploration, search-and-rescue, robotic surgery, and warehouse management just to name a few. As robots become more mobile, articulated and dexterous, it is important to find not only a feasible plan for the robot, but also one that optimizes one or more criteria for a given high-level task. The quality metric is problem-specific, and this paper will consider optimizing path length. The method described, however, is applicable to many different metrics like smoothness or obstacle clearance.