Accelerated Reeds–Shepp and Underspecified Reeds–Shepp Algorithms for Mobile Robot Path Planning

Abstract

In this study, we present a simple and intuitive method for accelerating optimal Reeds–Shepp path computation. Our approach uses geometrical reasoning to analyze the behavior of optimal paths, resulting in a new partitioning of the state space and a further reduction in the minimal set of viable paths. We revisit and reimplement classic methodologies from literature, which lack contemporary open-source implementations, to serve as benchmarks for evaluating our method. In addition, we address the underspecified Reeds–Shepp planning problem where the final orientation is unspecified. We perform exhaustive experiments to validate our solutions. Compared to the modern C++ implementation of the original Reeds–Shepp solution in the Open Motion Planning Library, our method demonstrates a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$15\times$</tex-math></inline-formula> speedup, while classic methods achieve a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$5.79\times$</tex-math></inline-formula> speedup. Both approaches exhibit machine-precision differences in path lengths compared to the original solution. We release our proposed C++ implementations for both the accelerated and underspecified Reeds–Shepp problems as open-source code.