Dubins Paths

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 $r$) 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.

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.

<!-- {{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="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; 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; }

// Code not found

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.

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

$$\dot{x} = \cos\theta,\quad \dot{y} = \sin\theta,\quad \dot{\theta} = u, \quad |u| \le \frac{1}{r}$$

Here $(x, y)$ is position, $\theta$ is heading, and $u$ is the steering input (curvature). Minimizing arc length subject to this constraint forces the optimal control $u$ 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:

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 $(x_0, y_0, \theta_0)$ and goal $(x_1, y_1, \theta_1)$, you can compute the length of all six candidates in $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.

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.

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.