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 boundedcurvature 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].
[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 CarLike Robot,"
IEEE Transactions on Automatic Control,
41(5), 1996 pp. 672688.
doi:10.1109/9.489204.