# Shortest Path for Forward and Reverse Motion of a Car

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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 (June 13)

Open content licensed under CC BY-NC-SA

## 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.

## Snapshots

## Permanent Citation