The Generalized Label Correcting Method for Optimal Kinodynamic Motion Planning
This work addresses the need for efficient, general-purpose motion planning algorithms for autonomous robots across various applications, though it appears incremental as it builds upon existing label correcting methods and heuristic optimization techniques.
The thesis tackles the problem of optimal kinodynamic motion planning for autonomous robots by presenting a resolution complete algorithm based on direct forward search, which eliminates the need for a local planning subroutine and includes a method for deriving admissible heuristics via a linear program and sum-of-squares relaxation.
Nearly all autonomous robotic systems use some form of motion planning to compute reference motions through their environment. An increasing use of autonomous robots in a broad range of applications creates a need for efficient, general purpose motion planning algorithms that are applicable in any of these new application domains. This thesis presents a resolution complete optimal kinodynamic motion planning algorithm based on a direct forward search of the set of admissible input signals to a dynamical model. The advantage of this generalized label correcting method is that it does not require a local planning subroutine as in the case of related methods. Preliminary material focuses on new topological properties of the canonical problem formulation that are used to show continuity of the performance objective. These observations are used to derive a generalization of Bellman's principle of optimality in the context of kinodynamic motion planning. A generalized label correcting algorithm is then proposed which leverages these results to prune candidate input signals from the search when their cost is greater than related signals. The second part of this thesis addresses admissible heuristics for kinodynamic motion planning. An admissibility condition is derived that can be used to verify the admissibility of candidate heuristics for a particular problem. This condition also characterizes a convex set of admissible heuristics. A linear program is formulated to obtain a heuristic which is as close to the optimal cost-to-go as possible while remaining admissible. This optimization is justified by showing its solution coincides with the solution to the Hamilton-Jacobi-Bellman equation. Lastly, a sum-of-squares relaxation of this infinite-dimensional linear program is proposed for obtaining provably admissible approximate solutions.