Introduction

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.

Connect Two Poses

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.

<!-- Reeds-Shepp path demo — canvas with start/goal arrows, the optimal maneuver, and a segment list -->
<p class="hint">The car starts at the blue marker. Click anywhere to set a new goal (position + heading). The demo tries every Reeds-Shepp pattern — arcs and straight segments driven forward or in reverse — and draws the shortest one: solid green means forward, dashed red means reverse.</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">Random goal</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout for the Reeds-Shepp demo */
* { 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; }

/* Reeds-Shepp shortest-path solver (CSC + CCC families) plus canvas renderer */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

/* Minimum turning radius in canvas pixels */
const R = 55;

/* Initial car state (start) and goal state */
let start = { x: 90, y: H / 2, th: 0 };
let goal  = { x: W - 90, y: H / 2, th: 0 };
let best  = null;

/* Normalize an angle to [0, 2*pi) */
const TAU = 2 * Math.PI;
function mod2pi(a) { let v = a % TAU; if (v < 0) v += TAU; return v; }
function polar(x, y) { return [Math.hypot(x, y), Math.atan2(y, x)]; }

/* Base L+S+L+ formula (all-forward), Reeds-Shepp/Dubins closed form */
function baseLSL(x, y, phi) {
  const sphi = Math.sin(phi), cphi = Math.cos(phi);
  const [u, t] = polar(x - sphi, y - 1 + cphi);
  const v = mod2pi(phi - t);
  return [mod2pi(t), u, v];
}
/* Base L+S+R+ formula (all-forward) */
function baseLSR(x, y, phi) {
  const sphi = Math.sin(phi), cphi = Math.cos(phi);
  const [u1, t1] = polar(x + sphi, y - 1 - cphi);
  const sq = u1 * u1 - 4;
  if (sq < 0) return null;
  const u = Math.sqrt(sq);
  const theta = Math.atan2(2, u);
  const t = mod2pi(t1 + theta);
  const v = mod2pi(t - phi);
  return [t, u, v];
}
/* Base L+R-L+ formula (turn-reverse-turn, no straight) */
function baseLRL(x, y, phi) {
  const sphi = Math.sin(phi), cphi = Math.cos(phi);
  const xi = x - sphi, eta = y - 1 + cphi;
  const [u1, theta] = polar(xi, eta);
  if (u1 > 4) return null;
  const A = Math.acos(u1 / 4);
  const t = mod2pi(theta + Math.PI / 2 + A);
  const u = mod2pi(Math.PI - 2 * A);
  const v = mod2pi(phi - t - u);
  return [t, u, v];
}

/* Build all 8 CSC candidates (LSL, RSR, LSR, RSL) x (forward, reverse) via reflection and time-flip symmetries */
function buildCSC(x, y, phi) {
  const out = [];
  function tryVariant(base, baseTypes, gx, gy, gphi, reflect, timeflip) {
    const sol = base(gx, gy, gphi);
    if (!sol) return;
    let types = baseTypes.slice();
    let signs = [1, 1, 1];
    if (timeflip) signs = signs.map((s) => -s);
    if (reflect) types = types.map((t) => (t === 'L' ? 'R' : t === 'R' ? 'L' : 'S'));
    out.push({ types, lengths: sol, signs });
  }
  tryVariant(baseLSL, ['L', 'S', 'L'], x, y, phi, false, false);
  tryVariant(baseLSL, ['L', 'S', 'L'], x, -y, -phi, true, false);
  tryVariant(baseLSL, ['L', 'S', 'L'], -x, y, -phi, false, true);
  tryVariant(baseLSL, ['L', 'S', 'L'], -x, -y, phi, true, true);
  tryVariant(baseLSR, ['L', 'S', 'R'], x, y, phi, false, false);
  tryVariant(baseLSR, ['L', 'S', 'R'], x, -y, -phi, true, false);
  tryVariant(baseLSR, ['L', 'S', 'R'], -x, y, -phi, false, true);
  tryVariant(baseLSR, ['L', 'S', 'R'], -x, -y, phi, true, true);
  return out;
}
/* Build all 4 CCC candidates (LRL, RLR) x (forward, reverse) the same way */
function buildCCC(x, y, phi) {
  const out = [];
  function tryVariant(gx, gy, gphi, reflect, timeflip) {
    const sol = baseLRL(gx, gy, gphi);
    if (!sol) return;
    let types = ['L', 'R', 'L'];
    let signs = [1, -1, 1];
    if (timeflip) signs = signs.map((s) => -s);
    if (reflect) types = types.map((t) => (t === 'L' ? 'R' : 'L'));
    out.push({ types, lengths: sol, signs });
  }
  tryVariant(x, y, phi, false, false);
  tryVariant(x, -y, -phi, true, false);
  tryVariant(-x, y, -phi, false, true);
  tryVariant(-x, -y, phi, true, true);
  return out;
}

/* Drive a candidate path from the origin to check where it actually ends up */
function simulateUnit(sol) {
  let x = 0, y = 0, theta = 0;
  for (let i = 0; i < sol.types.length; i++) {
    const type = sol.types[i], len = sol.lengths[i], dir = sol.signs[i];
    if (type === 'S') {
      x += dir * len * Math.cos(theta);
      y += dir * len * Math.sin(theta);
    } else {
      const turn = type === 'L' ? 1 : -1;
      const dtheta = dir * turn * len;
      const theta0 = theta;
      const cx = x - turn * Math.sin(theta0);
      const cy = y + turn * Math.cos(theta0);
      theta = theta0 + dtheta;
      x = cx + turn * Math.sin(theta);
      y = cy - turn * Math.cos(theta);
    }
  }
  return { x, y, theta: mod2pi(theta) };
}

/* Distance between a simulated candidate's end pose and the true goal pose */
function poseError(sol, target) {
  const end = simulateUnit(sol);
  const dx = end.x - target.x, dy = end.y - target.y;
  const raw = Math.abs(mod2pi(end.theta - target.theta));
  const dtheta = Math.min(raw, TAU - raw);
  return Math.hypot(dx, dy) + dtheta;
}

/* Transform the goal into the car's local frame, generate every candidate, keep only the ones that truly reach the goal, and return the shortest */
function bestReedsShepp(s, g) {
  const dx = (g.x - s.x) / R, dy = (g.y - s.y) / R;
  const c = Math.cos(-s.th), sn = Math.sin(-s.th);
  const x = dx * c - dy * sn, y = dx * sn + dy * c;
  const phi = mod2pi(g.th - s.th);
  let cands = [...buildCSC(x, y, phi), ...buildCCC(x, y, phi)];
  cands = cands.filter((c) => c.lengths.every((l) => isFinite(l) && l >= -1e-9));
  cands = cands.map((c) => ({ ...c, lengths: c.lengths.map((l) => Math.max(l, 0)) }));
  cands = cands.filter((c) => poseError(c, { x, y, theta: phi }) < 1e-6);
  if (!cands.length) return null;
  cands.sort((a, b) => sumLen(a) - sumLen(b));
  return cands[0];
}
function sumLen(sol) { return sol.lengths.reduce((a, b) => a + b, 0); }

/* Sample points along a circular arc for drawing */
function sampleArc(cx, cy, radius, a0, a1) {
  const pts = [];
  const steps = Math.max(2, Math.ceil(Math.abs(a1 - a0) / (Math.PI / 60)));
  for (let i = 0; i <= steps; i++) {
    const a = a0 + (a1 - a0) * (i / steps);
    pts.push({ x: cx + radius * Math.cos(a), y: cy + radius * Math.sin(a) });
  }
  return pts;
}

/* Walk the winning path's segments and collect drawable points, tagging each with its direction */
function pathSegments(s, sol) {
  const segs = [];
  let cx = s.x, cy = s.y, cth = s.th;
  for (let i = 0; i < sol.types.length; i++) {
    const type = sol.types[i], len = sol.lengths[i], dir = sol.signs[i];
    if (len < 1e-9) continue;
    if (type === 'S') {
      const arcLen = len * R * dir;
      const nx = cx + arcLen * Math.cos(cth);
      const ny = cy + arcLen * Math.sin(cth);
      segs.push({ pts: [{ x: cx, y: cy }, { x: nx, y: ny }], dir, type });
      cx = nx; cy = ny;
    } else {
      const turn = type === 'L' ? 1 : -1;
      const sign = turn * dir;
      const ocx = cx - sign * R * Math.sin(cth);
      const ocy = cy + sign * R * Math.cos(cth);
      const a0 = Math.atan2(cy - ocy, cx - ocx);
      const dAngle = sign * len;
      const a1 = a0 + dAngle;
      const pts = sampleArc(ocx, ocy, R, a0, a1);
      segs.push({ pts, dir, type });
      cx = ocx + R * Math.cos(a1);
      cy = ocy + R * Math.sin(a1);
      cth += dir * turn * len;
    }
  }
  return segs;
}

/* Draw a direction arrow with an optional label */
function drawArrow(x, y, th, color, label) {
  const len = 18, hw = 6;
  const ex = x + len * Math.cos(th), ey = y + len * Math.sin(th);
  ctx.save();
  ctx.strokeStyle = color; ctx.fillStyle = color; ctx.lineWidth = 2.5;
  ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(ex, ey); ctx.stroke();
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - hw * Math.cos(th - 0.4), ey - hw * Math.sin(th - 0.4));
  ctx.lineTo(ex - hw * Math.cos(th + 0.4), ey - hw * Math.sin(th + 0.4));
  ctx.closePath(); ctx.fill();
  if (label) {
    ctx.font = 'bold 12px system-ui, sans-serif';
    ctx.fillText(label, x + 2, y - 8);
  }
  ctx.restore();
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  /* Light background grid */
  ctx.save();
  ctx.strokeStyle = '#dde4ec'; ctx.lineWidth = 1;
  for (let x = 0; x < W; x += 40) { ctx.beginPath(); ctx.moveTo(x, 0); ctx.lineTo(x, H); ctx.stroke(); }
  for (let y = 0; y < H; y += 40) { ctx.beginPath(); ctx.moveTo(0, y); ctx.lineTo(W, y); ctx.stroke(); }
  ctx.restore();

  /* Draw the optimal maneuver — solid segments are forward, dashed segments are reverse */
  if (best) {
    const segs = pathSegments(start, best);
    segs.forEach((seg) => {
      ctx.save();
      ctx.strokeStyle = seg.dir > 0 ? '#2d6a4f' : '#c92f3c';
      ctx.lineWidth = 3;
      ctx.setLineDash(seg.dir > 0 ? [] : [7, 5]);
      ctx.beginPath();
      seg.pts.forEach((p, i) => (i === 0 ? ctx.moveTo(p.x, p.y) : ctx.lineTo(p.x, p.y)));
      ctx.stroke();
      ctx.restore();
    });
  }

  /* Draw start (blue) and goal (red) arrows */
  drawArrow(start.x, start.y, start.th, '#1d3557', 'Start');
  drawArrow(goal.x, goal.y, goal.th, '#e63946', 'Goal');
}

/* Human-readable label for a segment type */
function segmentLabel(type) {
  if (type === 'L') return 'Left arc';
  if (type === 'R') return 'Right arc';
  return 'Straight';
}

function updateStatus() {
  const statusEl = document.getElementById('status');
  const segsEl = document.getElementById('segs');
  if (!best) {
    statusEl.textContent = 'No valid path found.';
    segsEl.textContent = '';
    return;
  }
  const lenPx = Math.round(sumLen(best) * R);
  statusEl.textContent = i18nFmt('Shortest maneuver: %type% — length %len% px', { type: best.types.join(''), len: lenPx });
  /* Render the ordered list of segments with forward/reverse styling below the canvas */
  segsEl.innerHTML = best.lengths
    .map((l, i) => {
      if (l < 1e-9) return null;
      const dir = best.signs[i];
      const cls = dir > 0 ? 'fwd' : 'rev';
      const word = dir > 0 ? '(forward)' : '(reverse)';
      return '<span class="' + cls + '">' + segmentLabel(best.types[i]) + ' ' + word + '</span>';
    })
    .filter(Boolean)
    .join(' &rarr; ');
}

function recompute() {
  best = bestReedsShepp(start, goal);
  draw();
  updateStatus();
}

/* Click sets a new goal position; the heading points from the previous goal toward the click */
canvas.addEventListener('click', function (e) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const mx = (e.clientX - rect.left) * scaleX;
  const my = (e.clientY - rect.top) * scaleY;
  /* Aim the goal arrow toward the click, keeping the old heading if the click barely moved it */
  const dx = mx - goal.x, dy = my - goal.y;
  const th = Math.hypot(dx, dy) > 4 ? Math.atan2(dy, dx) : goal.th;
  goal = { x: mx, y: my, th };
  recompute();
});

document.getElementById('btn-random').addEventListener('click', function () {
  /* Place a random goal anywhere on the canvas with a random heading */
  goal = {
    x: 60 + Math.random() * (W - 120),
    y: 40 + Math.random() * (H - 80),
    th: (Math.random() * 2 - 1) * Math.PI
  };
  recompute();
});

document.getElementById('btn-reset').addEventListener('click', function () {
  goal = { x: W - 90, y: H / 2, th: 0 };
  recompute();
});

recompute();
Result
Console

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.

The Real Complexity

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 rr (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)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±,R±,S±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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reeds-shepp-paths/Content licensed under CC BY-NC 4.0.