Wolfram Demonstrations Project

This Demonstration shows the shortest paths for a car in forward and reverse motion, with a minimum turning radius

. Use the locators to change the start and goal positions and orientations. A car with both forward and reverse gears is often called a Reeds–Shepp car, while one with only a forward gear is a Dubins car, in honor of the mathematicians who first studied these problems.

Contributed by: Francesco Bernardini and Aaron T. Becker

Drag Locators
Slider Zoom
Gamepad Controls
Automatic Animation

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

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.