Details

This Demonstration is based on a simplified mathematical model of a car that can move in the - plane [1]. The car's coordinates are the center of the rear axle and its orientation . The car cannot move sideways because the rear wheels would have to slide instead of roll. The model stipulates that the car has a maximum steering angle that translates into a minimum turning radius . Circles showing the minimum turning radius are drawn as thin gray lines tangent to the curved sections of the path.

The changes of coordinates with velocity are given by

,

,

,

with the steering constraint limits . The task is to minimize the length of the curve traced out by the center of the rear axle as it moves from the start to the goal [2]. That path is the bounded-curvature shortest path. Reeds and Shepp proved that the shortest path consists of no more than five segments, where in each segment is either , or and the car is moving either forward or backward [3]. The optimal path is one of 48 different path types. The Reeds–Shepp path can be used as a metric for the configuration of a car. The distance does not change if you swap the start and goal positions.

The Dubins car has only six possible path types [3]. Because it can only move forward, the Dubins path is never shorter than the Reeds–Shepp path. The Dubins path is not a metric, and often the distance changes if the start and goal positions are swapped [4].

This Reeds–Shepp implementation is based on the Python code [5].

References

[1] K. M. Lynch and F. C. Park, Modern Robotics: Mechanics, Planning, and Control, Cambridge, UK: Cambridge University Press, 2017.

[2] L. E. Dubins, "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents," American Journal of Mathematics, 79(3), 1957 pp. 497–516. doi:10.2307/2372560.

[3] J. A. Reeds, III and L. A. Shepp. "Optimal Paths for a Car That Goes Both Forwards and Backwards," Pacific Journal of Mathematics, 145(2), 1990 pp. 367–393. doi:10.2140/pjm.1990.145.367.

[4] P. Souères and J.-P. Laumond, "Shortest Paths Synthesis for a Car-Like Robot," IEEE Transactions on Automatic Control, 41(5), 1996 pp. 672-688. doi:10.1109/9.489204.

[5] nathanlct and benjaminbecker. "reeds-shepp_curves." (Dec 23, 2022) github.com/nathanlct/reeds-shepp-curves/blob/master/reeds_shepp.py.