Informed Anytime Search for Continuous Planning Problems

Abstract

Navigating uncontrolled dynamic environments is a major challenge in robotics. Success requires solving many different technical problems and path planning is a key component of most autonomous solutions. Path planning is the task of finding a path through the environment that allows a robot to reach its desired position. This path must avoid obstacles and be executable by the robot while often also reducing a specified cost (e.g., path length). The difficulty of meeting these requirements reliably and quickly in continuous state spaces has made path planning an active area of research in robotics. Two popular path planning approaches are informed graph-based search and anytime sampling-based planning. Informed graph-based searches, such as A*, are efficient but use a priori approximations of the problem domain. If these approximations are chosen incorrectly, then the algorithms may be unable to find a (suitable) solution or take a prohibitively long time to do so. Anytime sampling-based planners, such as RRT*, continuously improve their approximations of the problem domain but perform inefficient searches. These searches simultaneously search the entire problem domain and can become prohibitively expensive in large or high-dimensional planning problems, such as when planning for high-DOF manipulation arms. This thesis demonstrates how planning in continuous planning problems can be improved by unifying the informed graph-based search and anytime sampling-based planning approaches. It investigates various ways to use heuristics to focus and order the search of almost-surely asymptotically optimal sampling-based planners. The theoretical and experimental advantages of this informed anytime sampling-based search are demonstrated through the planning algorithms, Informed RRT*, Batch Informed Trees (BIT*), and Sorted RRT* (SORRT*).