Title: The Generalized Label Correcting Method for Optimal Kinodynamic Motion Planning,
Abstract: 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.