Reeds–Shepp paths: shortest car routes with reverse gear

A destination two meters behind a car creates a simple choice: drive a forward loop or reverse two meters. Both routes can finish at the same position and heading. Their lengths differ substantially.

Reeds–Shepp paths solve the shortest-distance connection between two car poses when forward and reverse travel are available and curvature has a fixed bound. This lesson keeps the plane free of obstacles so you can isolate what reverse gear changes.

Give the car a reverse gear

Start at pose (0, 0, 0) and finish at (−2, 0, 0). Coordinates use meters, and heading 0 points east. Both poses face east even though the goal lies west of the start.

At minimum turning radius ρ = 1 m, the Dubins solver finds a shortest forward-only route of 8.283185 m. Allow reverse travel and the car can keep heading 0 while backing directly to the goal. Its length is 2 m.

That reverse segment is globally shortest under this model: every route between the two positions has length at least their Euclidean separation, which is 2 m. The segment reaches this bound while matching both headings. It saves 6.283185 m.

There is no initial-gear requirement or cost for selecting reverse in this experiment. A route that stays in reverse throughout has zero gear changes along the route.

Separate body heading from travel direction

The pose remains q = (x, y, θ). Heading θ describes the car's body orientation. It does not flip when the driver selects reverse.

Use signed longitudinal speed v and steering curvature κ:

Positive v moves along the body's heading. Negative v moves opposite that heading. During reverse travel, the velocity direction differs from body heading by π radians.

For example, at θ = 0 with v = −1 m/s, the velocity is (−1, 0) m/s. If κ = +1 m⁻¹ at the same moment, the heading rate is −1 rad/s. Steering left while reversing makes the body rotate clockwise.

The nonholonomic motion restriction still applies: the car cannot slide sideways instantaneously. Reverse gear adds a direction along its existing longitudinal axis.

Read signed motion primitives

The solver combines straight segments and arcs of radius ρ. A letter records the steering choice; a sign records the travel direction.

Primitive	Steering	Travel
L+	Left, κ = +1/ρ	Forward
L−	Left, κ = +1/ρ	Reverse
R+	Right, κ = −1/ρ	Forward
R−	Right, κ = −1/ρ	Reverse
S+	Straight, κ = 0	Forward
S−	Straight, κ = 0	Reverse

Let ℓᵢ be a piece's signed length in meters. An arc changes body heading by κᵢℓᵢ. A negative length changes the sign of that rotation as well as the travel direction.

Distance traveled stays nonnegative:

Adding the signed lengths directly would let forward and reverse travel cancel. That sum would not measure distance traveled.

Search the complete candidate set

Reeds and Shepp's 1990 paper reduces this open-plane problem to a finite collection of straight and circular pieces, with at most five pieces and at most two gear reversals needed for a shortest route.

The candidate set includes CSC, CCC, CCCC, CCSC, CSCC, and CCSCC layouts, where C means an arc. Certain pieces have constrained angles, including quarter turns. Permitting arbitrary signs on the six Dubins families would miss required cases.

This experiment adapts the full OMPL ReedsSheppStateSpace construction. It includes all its formula groups and their reflection, time-flip, and backward-order cases. These symmetries cover mirrored turns, reversed travel, and connections constructed from the other endpoint. Formula-domain checks reject impossible candidates before cost comparison.

The implementation first transforms the goal into the start frame and divides position coordinates by ρ. It constructs candidates at unit radius, restores physical lengths, and chooses the smallest sum of absolute lengths. Numerical ties use a fixed order. Different equally short routes can have different primitive sequences.

OMPL's 18 unsigned layout indices organize its implementation. They do not count every distinct signed word. LaValle's overview explains the larger signed-word classification.

Calculate a three-arc turnaround

Keep the start and goal positions at (0, 0), but change the goal heading from 0 to π. Set ρ = 1 m. One shortest solution is:

The first piece changes heading by +π/3. The reverse right turn has κ = −1 m⁻¹ and ℓ₂ = −π/3 m, so it also changes heading by +π/3. The final left turn adds another +π/3. The final body heading is π.

Exact arc integration gives these joins:

After piece	Position, in meters	Body heading
L+	(√3/2, 1/2)	π/3
R−	(√3/2, −1/2)	2π/3
L+	(0, 0)	π

The total distance is π ≈ 3.141593 m. Reverse distance is π/3 ≈ 1.047198 m, and the route changes gear twice.

This route also reaches a lower bound. The heading must change by at least π in magnitude, and the maximum heading change per meter traveled is 1/ρ. Any valid route therefore needs at least ρπ = π m. Matching that bound proves optimality for this example.

The matching Dubins problem costs 7π/3 ≈ 7.330383 m. Reversing reduces the turnaround distance by 4π/3 ≈ 4.188790 m.

Compare the routes

Give the car a reverse gear

Compare forward and reverse connections

Minimize distance between two poses with the same turning radius. Obstacles and gear-change delays are outside this experiment.

Reeds–Shepp pose presetDirectly behindSame position, opposite headingSideways parkingForward offsetIdentical poses

Reeds–Shepp turning radius

1.00 m

Start: (0, 0) m, heading 0°. Goal: (-2, 0) m, heading 0°. Arrows show body heading, including during reverse travel.

Two routes, one pair of poses

Chosen signed primitives

Piece	Travel	Signed length (m)
S	Reverse	-2.0000

L and R describe steering to the body's left or right. A minus sign means reverse travel. Zero-length pieces are omitted; only direction changes between moving pieces count as gear changes.

Motion sequence

S−

Shortest length

2.000000 m

Dubins length

8.283185 m

Distance saved

6.283185 m

Reverse length

2.000000 m

Gear changes

0

Endpoint position error

0.000000 m

Endpoint heading error

0.000000°

Allowing reverse travel gives a 2.000000 m route and saves 6.283185 m compared with Dubins. This solution has 0 gear changes. Equal-length alternatives can use different primitives.

Reset Reeds–Shepp experiment

The initial Directly behind preset shows the 2 m reverse straight path over the longer forward-only comparison. Black arrows show body heading. The car faces east at both ends while traveling west in reverse.

Select Same position, opposite heading to inspect the three-arc calculation. Blue solid pieces move forward, brown dashed pieces move in reverse, and black squares mark gear changes. The thin gray dashed line shows the Dubins route for the same two poses and radius.

Choose Sideways parking to connect (0, 0, 0) to (0, 2, 0). At radius 1 m, the chosen sequence is R+ → L− → R− → L+, with length 3.646953 m and two gear changes. The car reaches a lateral destination through turns; no primitive slides sideways.

Forward offset reproduces the earlier Dubins example: (0, 0, 0) to (4, 2, 0). Both models find 4.511299 m, using only forward motion. Identical poses requires no motion and has length zero.

The signed-piece table omits zero-length pieces. The endpoint readouts compare the integrated final position and body heading with the requested pose. Drawing samples never determine the reported path cost.

Count gear changes at cusps

A cusp marks a change between forward and reverse travel. The position and body heading remain continuous there, while the direction of travel reverses.

For L+ → R− → L+, the signs are +, −, +. There are two transitions, hence two cusps. For R+ → L− → R− → L+, the two middle pieces both travel in reverse. Their steering change creates no additional gear change, so this route also has two cusps.

Ignore zero-length pieces when counting. A zero-length arc between two reverse segments does not create a forward interval or require another shift.

Within a single-gear section, the route has a continuous tangent. At a cusp, the path's one-sided travel tangents point in opposite directions. The car's heading stays well defined, but the geometric route lacks a continuous travel tangent across that reversal.

A physical car with finite acceleration must pass through zero longitudinal speed to reverse direction. The geometric solver assigns no time or cost to this event.

Interpret the Dubins comparison

Every forward-only Dubins route is also allowed by the Reeds–Shepp model. Both models share the same turning radius and endpoint poses, so their shortest distances satisfy:

Equality occurs in the forward-offset preset. Reverse travel expands the available choices without forcing the solver to use them.

The reverse model also gives the same minimum distance when the start and goal exchange places. Reversing a feasible route preserves its geometric length. Dubins travel cannot generally make that reversal because it lacks a reverse gear.

Scaling both coordinates and radius by a positive factor scales every length by the same factor. Changing only the radius changes the normalized problem and can change the winning family. A larger radius imposes a tighter curvature bound, so the minimum distance cannot decrease when the endpoint poses stay fixed.

Add timing and obstacle checks

The objective here is distance. If forward and reverse travel share a fixed speed magnitude and gear changes take no time, minimizing distance also minimizes travel time. Slower reverse speed or a shift delay changes that relationship.

For a chosen path, a simple time estimate might be:

This expression can compare particular paths under those assumptions. It does not turn the distance-optimal candidate set into a complete solver for the new time objective. Penalizing reverse distance or each gear change also defines a different optimization problem.

The model permits instantaneous steering changes and excludes acceleration limits, tire slip, obstacles, and the robot footprint. Ackermann steering geometry connects the chosen turning radius to a car's wheelbase and steering angles. A real steering mechanism may need extra transitions to respect its rate limit.

A planner must check the entire swept footprint along every forward and reverse piece. Valid endpoints cannot establish collision-free motion. Rejecting the open-plane shortest connection also cannot prove that no obstacle-avoiding route exists. Intermediate poses may provide another route.

The implementation accepts finite poses, a positive finite radius, and separation up to one million turning radii. It discards normalized pieces below 10⁻¹² and treats normalized costs within 10⁻¹⁰ as numerical ties. Those thresholds address floating-point calculations; they provide no physical clearance or tracking margin.

Integrate signed pieces in Python

This standard-library Python 3 example checks the two worked paths. It integrates given signed primitives and calculates their distance and gear changes. The interactive solver separately constructs the complete candidate set; this short script does not perform that search.

from math import cos, sin, pi


def advance(pose, kind, length, radius):
    x, y, heading = pose
    curvature = {"L": 1, "S": 0, "R": -1}[kind] / radius
    end = heading + curvature * length
    if curvature == 0:
        x += length * cos(heading)
        y += length * sin(heading)
    else:
        x += (sin(end) - sin(heading)) / curvature
        y += (cos(heading) - cos(end)) / curvature
    return x, y, end


def clean(value):
    return 0.0 if abs(value) < 1e-10 else value


examples = [
    ("behind", [("S", -2)]),
    ("turnaround", [("L", pi / 3), ("R", -pi / 3), ("L", pi / 3)]),
]
for name, pieces in examples:
    pose = (0.0, 0.0, 0.0)
    for kind, signed_length in pieces:
        pose = advance(pose, kind, signed_length, radius=1.0)
    signs = [1 if length > 0 else -1 for _, length in pieces if length != 0]
    shifts = sum(a != b for a, b in zip(signs, signs[1:]))
    total = sum(abs(length) for _, length in pieces)
    reverse = sum(max(0, -length) for _, length in pieces)
    x, y, heading = pose
    print(f"{name}: length={total:.6f}; reverse={reverse:.6f}; shifts={shifts}; "
          f"end=({clean(x):.6f}, {clean(y):.6f}, {clean(heading):.6f})")

Expected output, with lengths in meters and heading in radians:

behind: length=2.000000; reverse=2.000000; shifts=0; end=(-2.000000, 0.000000, 0.000000)
turnaround: length=3.141593; reverse=1.047198; shifts=2; end=(0.000000, 0.000000, 3.141593)

Try it yourself

Exercise 1. Increase the turning radius. Keep the turnaround poses fixed at (0, 0, 0) and (0, 0, π), but set ρ = 2 m. Calculate total length, reverse length, and gear changes for the scaled three-arc solution.

Check the larger turnaround

The signed lengths become (2π/3, −2π/3, 2π/3) m. Their absolute values sum to 2π ≈ 6.283185 m. Reverse distance is 2π/3 ≈ 2.094395 m, and the route still changes gear twice. Its heading changes remain π/3 per piece because each arc doubles its length and halves its steering curvature. Select the opposite-heading preset and radius 2 m to check these values.

Exercise 2. Add a shift delay to one comparison. For the radius-1 turnaround, suppose both travel directions use speed magnitude 1 m/s and each gear change adds 3 seconds. Ignore acceleration time for this arithmetic exercise. Compare the displayed Reeds–Shepp route with the Dubins route. Does the shorter route finish sooner under this estimate?

Check the time estimate

The Reeds–Shepp route needs π + 2 × 3 ≈ 9.141593 s. The Dubins route needs 7π/3 ≈ 7.330383 s with no gear changes. Dubins wins this comparison by about 1.811210 s. This compares two chosen paths; finding a globally fastest path with shift costs would require solving the changed objective.

Sources and further study

• J. A. Reeds and L. A. Shepp, 1990, original shortest-path paper, Pacific Journal of Mathematics 145(2), 367–393.
• Steven M. LaValle, Planning Algorithms, Section 15.3.2, for the car model, reversals, and signed-word classification.
• OMPL ReedsSheppStateSpace source, by Mark Moll. This lesson adapts its complete formula construction and preserves the Rice University BSD license notice.

Continue with Ackermann steering to translate a turning-radius requirement into the wheel geometry of a car-like robot.