Informed Anytime Search for Continuous Planning Problem

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*).