Reeds-Shepp Paths

Dubins paths answer a clean question: what is the shortest route for a car with a minimum turning radius that only ever drives forward? In 1990, mathematicians Jerome Reeds and Lawrence Shepp asked the obvious follow-up — what if the car can also reverse, the way every real car does?

The answer is not just "a small tweak." Letting the car back up can make the shortest path dramatically shorter, especially when the goal is behind the car or facing the wrong way. Anyone who has ever three-point-turned into a driveway already knows this intuitively: sometimes backing up first gets you there faster than any amount of forward-only looping.

Reeds and Shepp proved that, just like the Dubins case, the optimal path is never some wild freeform curve. It is always built from a short list of circular arcs and straight segments, each one driven either forward or in reverse. The surprising part is how few patterns you ever need — and that a computer can still find the best one instantly.

The car starts at the green marker, facing the direction of its arrow. Click anywhere on the canvas to set a new goal position; drag from the goal to set its heading. The demo searches every Reeds-Shepp pattern and animates the shortest one it finds.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<canvas id="canvas" width="480" height="320"></canvas>
<div class="status" id="status"></div>
<div class="segs" id="segs"></div>
<div class="btns">
  <button id="btn-random" type="button">{{btn_random}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f4f7fa; cursor: crosshair; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0 .3rem; min-height: 1.4em; color: #1d3557; }
.segs { font: 600 13px ui-monospace, monospace; color: #444; margin: 0 0 .6rem; min-height: 1.3em; }
.segs .fwd { color: #2d6a4f; }
.segs .rev { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the segment list update below the canvas: solid arcs and lines are driven forward, dashed ones are driven in reverse. Try placing the goal directly behind the car, facing the same way it started — notice how the winning maneuver almost always includes at least one reverse segment, because looping all the way around forward would be far longer.

Adding a reverse gear seems like it should blow up the search space — now every segment can be driven two ways, forward or backward, on top of turning left, right, or going straight. It does grow the list of candidates, but not without limit.

• Same building blocks, signed. Every path is still a sequence of at most five pieces, each a circular arc of the minimum turning radius $r$ (Left or Right) or a straight Segment, exactly like Dubins. The only change is that each piece now carries a direction: $+$ for forward, $-$ for reverse.
• 48 words, not infinitely many. Reeds and Shepp showed the optimal path is always one of 48 specific patterns (grouped into families such as CSC, CCC, CCCC and CCSC), each with its own closed-form formula for segment lengths given the start and goal poses.
• Still solvable in constant time. Evaluating all 48 candidate formulas and keeping the shortest one is $O(1)$ arithmetic — no search tree, no iteration. Later, Sussmann and Tang (1991) simplified the case analysis, and modern motion-planning libraries reduce the practical set to around a dozen formulas that cover every case after applying symmetries (reflection, time-reversal).
• A genuinely different optimum. Unlike Dubins, the Reeds-Shepp optimum can involve a cusp — a point where the car stops and switches from forward to reverse (or back). The number of cusps in an optimal path is always small (at most two for most cases), but a single well-placed cusp can shorten the route enormously compared to any forward-only alternative.

So the reversing version of the problem is exactly as tractable as the forward-only one — the geometry is just richer, expressed with

$$L^{\pm}, R^{\pm}, S^{\pm}$$

segments instead of the three unsigned primitives Dubins needed. It remains a fully solved problem: no NP-hardness, no heuristics required, just a bigger — but still finite and enumerable — table of formulas. Compare this with routing problems like the traveling salesman problem, where adding a small amount of extra structure to the movement rules does not save you from combinatorial explosion.

Anything that steers like a car but is also allowed to back up reaches for Reeds-Shepp paths as its basic building block:

• Automated parking systems: the tight, awkward geometry of parallel and perpendicular parking is exactly the case where reversing shortens the maneuver the most.
• Warehouse and factory robots: car-like AGVs (automated guided vehicles) navigating narrow aisles routinely need to back up to reach a dock or turn around in a confined space.
• Sampling-based motion planners: algorithms like RRT and RRT* use Reeds-Shepp (or Dubins) paths as the local "steering function" that connects two nearby sample points with a kinematically valid curve.
• Search-and-rescue and agricultural robots: field robots operating around obstacles in tight outdoor spaces benefit from the shorter reversing maneuvers whenever a straight forward approach is blocked.

Whenever a real design decision is "should this vehicle reverse right now, or loop around instead," a Reeds-Shepp computation is quietly answering it — instantly and exactly, without any trial and error.

Reeds and Shepp took Dubins's elegant six-family answer and asked what happens once a car is allowed to do what every real car does: back up. The result is a bigger table — 48 patterns instead of 6 — but the same spirit of a completely solved problem. No search, no approximation, just arcs and straight lines, some forward and some in reverse, evaluated by formula and compared in an instant.

The next time an assisted-parking system slots a car into a tight space with one smooth forward-reverse-forward wiggle, you are watching this exact 1990 result at work — proof that even a problem enriched with a whole new kind of motion can still have a clean, complete, closed-form answer.