Introduction

Imagine you need to drive from one parking spot to another across an empty lot. In a perfect mathematical world you would draw a straight line and follow it. But your car has a minimum turning radius — the tightest circle it can make — and it cannot reverse. Suddenly the shortest path is no longer obvious.

This is the problem mathematician Lester Dubins solved in 1957. He asked: what is the shortest smooth curve connecting two points in the plane, given that the curve must have a bounded curvature (it cannot bend tighter than a fixed radius rr) and must be traversed in a fixed direction?

The answer is elegant and surprising. Dubins proved that the optimal path always belongs to one of exactly six families, each made of at most three segments. Every segment is either a straight line (S) or an arc of the minimum-radius circle (C — either a Left arc or a Right arc). The six types are LSL, RSR, LSR, RSL, LRL, and RLR. No matter where you start and where you need to go, the shortest legal route is always one of those six shapes.

The result was proved decades before autonomous cars existed, yet it is exactly what modern motion planners use today — from self-driving vehicles to drone waypoint navigation to robotic arms.

Park the Car

The car starts at the left, facing right. Click anywhere to set a new target parking spot (position and heading). The demo computes all six Dubins path candidates and draws the shortest one.

<!-- Dubins path demo — canvas with start/goal arrows and the optimal path -->
<p class="hint">A car cannot reverse and has a minimum turning radius. Click anywhere on the canvas to set the goal (position + heading). The demo finds the shortest Dubins path — always one of six three-segment types.</p>
<canvas id="canvas" width="480" height="320"></canvas>
<div class="status" id="status"></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 Dubins 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; min-height: 1.4em; color: #1d3557; }
.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; }

/* Dubins shortest-path solver + 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 = 60;

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

/* ── Normalize angle to [0, 2*pi) ── */
function mod2pi(a) { return ((a % (2 * Math.PI)) + 2 * Math.PI) % (2 * Math.PI); }

/* ── LSL candidate (Left arc - Straight - Left arc) ── */
function dubinsLSL(dx, dy, d, sa, ca, sb, cb) {
  const p2 = 2 + d * d - 2 * Math.cos(sa - sb) + 2 * d * (Math.sin(sa) - Math.sin(sb));
  if (p2 < 0) return null;
  const tmp = Math.atan2(cb - ca, d + sa - sb);
  const t = mod2pi(-sa + tmp);
  const p = Math.sqrt(p2);
  const q = mod2pi(sb - tmp);
  return { t, p, q, type: 'LSL', len: t + p + q };
}
/* ── RSR candidate (Right arc - Straight - Right arc) ── */
function dubinsRSR(dx, dy, d, sa, ca, sb, cb) {
  const p2 = 2 + d * d - 2 * Math.cos(sa - sb) + 2 * d * (Math.sin(sb) - Math.sin(sa));
  if (p2 < 0) return null;
  const tmp = Math.atan2(ca - cb, d - sa + sb);
  const t = mod2pi(sa - tmp);
  const p = Math.sqrt(p2);
  const q = mod2pi(-sb + tmp);
  return { t, p, q, type: 'RSR', len: t + p + q };
}
/* ── LSR candidate (Left arc - Straight - Right arc) ── */
function dubinsLSR(dx, dy, d, sa, ca, sb, cb) {
  const p2 = -2 + d * d + 2 * Math.cos(sa - sb) + 2 * d * (Math.sin(sa) + Math.sin(sb));
  if (p2 < 0) return null;
  const p = Math.sqrt(p2);
  const tmp = Math.atan2(-ca - cb, d + sa + sb) - Math.atan2(-2, p);
  const t = mod2pi(-sa + tmp);
  const q = mod2pi(-sb + tmp);
  return { t, p, q, type: 'LSR', len: t + p + q };
}
/* ── RSL candidate (Right arc - Straight - Left arc) ── */
function dubinsRSL(dx, dy, d, sa, ca, sb, cb) {
  const p2 = -2 + d * d + 2 * Math.cos(sa - sb) - 2 * d * (Math.sin(sa) + Math.sin(sb));
  if (p2 < 0) return null;
  const p = Math.sqrt(p2);
  const tmp = Math.atan2(ca + cb, d - sa - sb) - Math.atan2(2, p);
  const t = mod2pi(sa - tmp);
  const q = mod2pi(sb - tmp);
  return { t, p, q, type: 'RSL', len: t + p + q };
}
/* ── LRL candidate (Left - Right - Left, no straight) ── */
function dubinsLRL(dx, dy, d, sa, ca, sb, cb) {
  const tmp = (6 - d * d + 2 * Math.cos(sa - sb) + 2 * d * (Math.sin(sa) - Math.sin(sb))) / 8;
  if (Math.abs(tmp) > 1) return null;
  const p = mod2pi(2 * Math.PI - Math.acos(tmp));
  const t = mod2pi(-sa + Math.atan2(ca - cb, d - sa + sb) + p / 2);
  const q = mod2pi(sa - sb - t + p);
  return { t, p, q, type: 'LRL', len: t + p + q };
}
/* ── RLR candidate (Right - Left - Right, no straight) ── */
function dubinsRLR(dx, dy, d, sa, ca, sb, cb) {
  const tmp = (6 - d * d + 2 * Math.cos(sa - sb) + 2 * d * (Math.sin(sb) - Math.sin(sa))) / 8;
  if (Math.abs(tmp) > 1) return null;
  const p = mod2pi(2 * Math.PI - Math.acos(tmp));
  const t = mod2pi(sa - Math.atan2(ca - cb, d + sa - sb) + p / 2);
  const q = mod2pi(sa - sb - t + p);
  return { t, p, q, type: 'RLR', len: t + p + q };
}

/* ── Normalize to unit-radius frame, compute all six candidates, return shortest ── */
function computeDubins(s, g) {
  const dx = (g.x - s.x) / R, dy = (g.y - s.y) / R;
  const d = Math.hypot(dx, dy);
  const th = Math.atan2(dy, dx);
  const sa = mod2pi(s.th - th), sb = mod2pi(g.th - th);
  const ca = Math.cos(sa), cb = Math.cos(sb);
  const candidates = [
    dubinsLSL(dx, dy, d, sa, ca, sb, cb),
    dubinsRSR(dx, dy, d, sa, ca, sb, cb),
    dubinsLSR(dx, dy, d, sa, ca, sb, cb),
    dubinsRSL(dx, dy, d, sa, ca, sb, cb),
    dubinsLRL(dx, dy, d, sa, ca, sb, cb),
    dubinsRLR(dx, dy, d, sa, ca, sb, cb),
  ].filter(Boolean);
  if (!candidates.length) return null;
  return candidates.reduce((a, b) => (a.len < b.len ? a : b));
}

/* ── Sample points along a circular arc for drawing ── */
function sampleArc(cx, cy, radius, a0, a1, left, 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) });
  }
}

/* ── Walk the three segments of the winning path and collect canvas points ── */
function dubinsPoints(s, path) {
  const pts = [];
  let cx = s.x, cy = s.y, cth = s.th;

  function doSeg(type, len) {
    if (len < 1e-9) return;
    const arcLen = len * R;
    if (type === 'S') {
      pts.push({ x: cx, y: cy });
      cx += arcLen * Math.cos(cth);
      cy += arcLen * Math.sin(cth);
      pts.push({ x: cx, y: cy });
    } else {
      const left = (type === 'L');
      const sign = left ? 1 : -1;
      /* Center of the turning circle */
      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;
      sampleArc(ocx, ocy, R, a0, a1, left, pts);
      cx = ocx + R * Math.cos(a1);
      cy = ocy + R * Math.sin(a1);
      cth += dAngle;
    }
  }

  const t = path.type;
  /* Dispatch to the correct segment order based on path type */
  if (t === 'LSL') { doSeg('L', path.t); doSeg('S', path.p); doSeg('L', path.q); }
  else if (t === 'RSR') { doSeg('R', path.t); doSeg('S', path.p); doSeg('R', path.q); }
  else if (t === 'LSR') { doSeg('L', path.t); doSeg('S', path.p); doSeg('R', path.q); }
  else if (t === 'RSL') { doSeg('R', path.t); doSeg('S', path.p); doSeg('L', path.q); }
  else if (t === 'LRL') { doSeg('L', path.t); doSeg('R', path.p); doSeg('L', path.q); }
  else if (t === 'RLR') { doSeg('R', path.t); doSeg('L', path.p); doSeg('R', path.q); }
  return pts;
}

/* ── Draw a direction arrow with 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();
  /* Draw filled arrowhead */
  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 Dubins path */
  if (best) {
    const pts = dubinsPoints(start, best);
    ctx.save();
    ctx.strokeStyle = '#2d6a4f'; ctx.lineWidth = 3;
    ctx.setLineDash([]);
    ctx.beginPath();
    pts.forEach((p, i) => i === 0 ? ctx.moveTo(p.x, p.y) : ctx.lineTo(p.x, p.y));
    ctx.stroke();
    ctx.restore();
  }

  /* Show minimum turning radius circle around start */
  ctx.save();
  ctx.strokeStyle = '#b0c4d8'; ctx.lineWidth = 1; ctx.setLineDash([4, 4]);
  ctx.beginPath(); ctx.arc(start.x, start.y, R, 0, 2 * Math.PI); 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');
}

function updateStatus() {
  const el = document.getElementById('status');
  if (!best) { el.textContent = 'No valid path found.'; return; }
  const lenPx = Math.round(best.len * R);
  el.textContent = i18nFmt('Shortest path: %type% — length %len% px', { type: best.type, len: lenPx });
}

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

/* ── Click sets new goal; heading points away from previous goal position ── */
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 in the direction of the click movement */
  const dx = mx - goal.x, dy = my - goal.y;
  goal = { x: mx, y: my, th: Math.atan2(dy, dx) };
  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 - 80, y: H / 2, th: 0 };
  recompute();
});

recompute();
Result
Console

Notice that the path is always made of at most three pieces: an arc, then a straight segment, then another arc — or two arcs with a straight between them. Move the target very close and you will see the straight segment shrink to zero; move it far away and the arcs become tiny relative to the straight leg. The three-segment rule always holds.

The Geometry

Why only six families? The argument comes from optimal control theory, specifically the Pontryagin Minimum Principle applied to the unicycle model of a car:

x˙=cos⁡θ,y˙=sin⁡θ,θ˙=u,∣u∣≤1r\dot{x} = \cos\theta,\quad \dot{y} = \sin\theta,\quad \dot{\theta} = u, \quad |u| \le \frac{1}{r}

Here (x,y)(x, y) is position, θ\theta is heading, and uu is the steering input (curvature). Minimizing arc length subject to this constraint forces the optimal control uu to be bang-bang or zero: always at the maximum left turn, maximum right turn, or straight ahead. That gives exactly three primitive types — L, R, S — and the shortest path uses at most three of them in a row.

The six candidates are:

Type Description
LSL Left arc · Straight · Left arc
RSR Right arc · Straight · Right arc
LSR Left arc · Straight · Right arc
RSL Right arc · Straight · Left arc
LRL Left · Right · Left (no straight)
RLR Right · Left · Right (no straight)

The CCC types (LRL, RLR) appear only when start and goal are close and similarly oriented; for most configurations the winning type is one of the CSC family (with a straight segment).

This is a solved problem: given start (x0,y0,θ0)(x_0, y_0, \theta_0) and goal (x1,y1,θ1)(x_1, y_1, \theta_1), you can compute the length of all six candidates in O(1)O(1) arithmetic operations and pick the minimum. No search, no approximation — just a handful of trigonometric formulas. The Dubins path is as clean as a shortest path can get.

Where It Matters

Dubins paths show up whenever something moves forward along curves and cannot (or should not) reverse:

  • Autonomous vehicles: the path planner in a self-driving car computes Dubins or Reeds–Shepp paths (the reversing extension) to connect waypoints while respecting the vehicle's turning radius.
  • Fixed-wing drones and aircraft: a plane cannot hover, so autopilots use Dubins paths to connect survey waypoints at minimum flight distance.
  • Mobile robots: warehouse robots, lawn-mowers and field robots all have a finite turning radius; Dubins geometry is a standard sub-routine in their planners.
  • Surgical robotics and endoscopes: flexible instruments have a minimum bend radius; optimal routing through anatomy mirrors the same mathematics.
  • Racing-line optimization: competition drivers intuitively follow Dubins-like curves through corners — the math formalizes the instinct.

The key insight is that bounded curvature is a universal physical constraint. Anything with wheels, wings, or a body that bends has a minimum turning radius, and Dubins paths give the exact shortest route — not an approximation. See also dynamic programming for how planners chain many such segments together into longer routes.

Conclusion

Dubins paths answer a question that sounds almost trivial — what is the shortest route from here to there for a car? — and the answer turns out to be a beautiful piece of mathematics: exactly six curve families, each a sequence of at most three segments, each segment either a straight line or the tightest arc the vehicle can manage.

The result is completely solved. Given start and goal, a handful of trigonometric formulas hand you the optimal path with zero search. That is rare: most path-planning problems require heuristics or search trees. Dubins geometry is one of those lucky cases where a physical constraint — the minimum turning radius — carves the solution space down to a finite list of candidates, and the best one can be read off directly.

Next time you watch a drone smoothly curve toward its landing pad, or a self-driving car arc into a parking space, you are seeing a 1957 theorem doing its job.

Share this article

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

Comments

Loading comments...

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