Circling Back: Dubins set Classification Revisited

Abstract

Dubins paths are commonly used in robot motion planning for generating minimal-length fixed-curvature motions between two states. Existing analytical approaches generate the Dubins set - the set of paths consisting of different sequences of arcs and straight lines that contains the optimal solution for travelling between a state pair. Typically, the length for each path in the set is evaluated and the shortest path is selected. Dubins set classification approaches use an additional pre-calculation phase to further reduce the Dubins set before evaluating path length. This can significantly reduce computational costs, especially for sampling based planners in the Dubins space that perform many path length evaluations during a search. This paper addresses the issue of degenerate solutions from the Dubins set classification method presented in~\cite{shkel_classication_2001} when solving for a shortest path using Dubins paths. The results show that a Dubins set classification approach can result in 58$\%$ reduced computation time for computing a Dubins path but still return the optimal path when compared to evaluating the full Dubins set.