explainer
Dubins paths: shortest routes with a turning limit
Connect two robot poses with forward motion and a minimum turning radius. Compare all six Dubins path families, calculate arc lengths, and see why matching position alone misses the heading constraint.
What you will learn
- Specify both endpoint positions and headings for a vehicle connection.
- Translate a minimum turning radius into a curvature bound.
- Compare all six canonical families and identify geometric infeasibility.
- Calculate path length from circular arcs and straight segments.
- Explain which motion and obstacle constraints the Dubins model leaves out.
Before you start
Getting a robot to the right position can leave it facing the wrong direction. A forward-moving vehicle also needs enough space to turn into its final heading.
A Dubins path gives the shortest connection between two poses in an obstacle-free plane when the vehicle moves only forward and has a minimum turning radius. The connection uses straight segments and circular arcs. Here you can calculate one by hand, compare every candidate family, and inspect the endpoint heading.
Specify positions and headings
A planar pose has three coordinates:
q = (x, y, θ)
Measure x and y in meters. Measure θ counterclockwise from the positive x direction. The headings 0 and 2π describe the same orientation; wrapping an angle preserves that equivalence.
The worked example starts at (0, 0, 0) and ends at (4, 2, 0). Both poses face east. The direct line between their positions points about 26.6° above east, so following that line alone fails both heading conditions.
This pose space is SE(2): planar position plus rotation. The nonholonomic constraints lesson explains why an allowed destination and an allowed instantaneous direction are different questions.
Turn a radius into a motion constraint
Let s denote distance traveled along the route. For a forward-moving vehicle:
dx/ds = cos θ, dy/ds = sin θ
κ = dθ/ds, |κ| ≤ 1/ρ
Here ρ > 0 is the minimum turning radius. Curvature κ measures heading change per meter. With ρ = 1 m, the largest curvature magnitude is 1 m⁻¹. With ρ = 2 m, it falls to 0.5 m⁻¹.
A straight segment has κ = 0. A tight left turn has κ = +1/ρ; a tight right turn has κ = −1/ρ. Every arc in the candidate set uses that minimum radius. The model permits a straight segment or turn to have zero length.
The path parameter always moves forward. Stopping and turning the body while its position stays fixed would require an extra motion that this model excludes.
Compare six candidate families
For the open-plane problem, a shortest connection needs at most three primitives. Write L for a minimum-radius left arc, R for a minimum-radius right arc, and S for a straight segment. The six canonical families are:
| Family | Motion order |
|---|---|
| LSL | Left, straight, left |
| RSR | Right, straight, right |
| LSR | Left, straight, right |
| RSL | Right, straight, left |
| RLR | Right, left, right |
| LRL | Left, right, left |
The first four have the form CSC, where C means a circular arc. The last two have the form CCC. Construct each canonical candidate that exists, calculate its length, and select the smallest. LaValle's account of the Dubins result explains this six-family reduction.
Zero-length pieces let these words represent simpler routes. For example, LSL with both arcs of length zero is a straight line. Different family labels can therefore describe the same physical path. Distinct paths can also tie in length.
The family list applies to this particular objective and motion model. Adding obstacles changes the problem.
Construct tangent connections
At pose (x, y, θ), the centers of its left and right turning circles are:
c_L = (x − ρ sin θ, y + ρ cos θ)
c_R = (x + ρ sin θ, y − ρ cos θ)
A CSC path leaves its first circle along a tangent line and enters its final circle along the same heading. Let D be the distance between the chosen circle centers.
Same-turn circles, as in LSL, admit an external tangent with straight length D. When their centers coincide, a single arc can connect the poses directly. That case needs explicit handling because the direction between identical centers has no meaning.
Opposite-turn circles, as in LSR, need an internal tangent. Its straight length is:
ℓ_S = √(D² − 4ρ²), D ≥ 2ρ
The tangent and the 2ρ offset form a right triangle. Below that separation, this canonical CSC candidate is infeasible. At equality, its straight segment shrinks to zero.
The implementation translates and rotates into the start pose's frame, then divides distances by ρ. These operations make the start pose (0, 0, 0) and the working radius 1 without changing which family wins.
Calculate an offset connection
Use the start (0, 0, 0), goal (4, 2, 0), and ρ = 1 m. For LSR, the initial left-circle center is (0, 1). The final right-circle center is (4, 1). Their separation is D = 4 m.
The internal tangent triangle gives:
ℓ_S = √(16 − 4) = 2√3 m
α = arcsin(2/4) = π/6
Turn left by π/6 radians, travel 2√3 m along the tangent, then turn right by π/6. The heading rises from 0° to 30° and returns to 0°.
Each arc has length ρ multiplied by its angle in radians. The total is:
L_LSR = π/6 + 2√3 + π/6
L_LSR = π/3 + 2√3 ≈ 4.511299 m
The first arc ends near (0.5, 0.133975) m. The straight segment adds (3, 1.732051) m. The final arc adds about (0.5, 0.133975) m, arriving at (4, 2) m with heading 0°.
For comparison, LSL uses total turning angle 2π and straight length √20, costing 10.755321 m. Comparing all feasible candidates makes LSR the winner. The point-to-point lower bound √20 ≈ 4.472136 m ignores the required headings.
Turn around with three arcs
Some nearby poses favor a CCC connection. Its middle circle must sit 2ρ from both outer circle centers. Such a circle exists only when their separation satisfies D ≤ 4ρ.
For the canonical candidate, choose the longer middle arc, with angle from π through 2π at the limiting cases. In normalized units d = D/ρ:
β_middle = 2π − 2 arcsin(d/4), 0 ≤ d ≤ 4
Consider start (0, 0, 0) and goal (0, 0, π) at radius 1 m. The position stays the same while the requested heading reverses. The shortest RLR and LRL paths tie. Each uses arc angles π/3, 5π/3, π/3, so its length is:
L = 7π/3 ≈ 7.330383 m
For RLR, the signed heading change is −π/3 + 5π/3 − π/3 = π. The vehicle returns to its original position facing west after a forward loop. An in-place spin would solve a different motion problem.
At D = 4ρ, the middle arc reaches π. Coincident outer centers allow a full middle circle, a degenerate candidate that can lose to a simpler path. Identical endpoint poses have a zero-length optimum; the solver handles that through the zero-length CSC pieces.
Explore the candidates
The initial Offset, same heading view reproduces the 4.511299 m LSR calculation. Four canonical candidates are feasible. RLR and LRL fail their outer-circle separation test.
Choose Same position, opposite heading to compare the two 7.330383 m CCC paths. Select LSR to inspect an infeasible family: the route disappears and the status explains the missing tangent. Returning to Automatic shortest restores the winner.
Choose Quarter turn at radius 1 m. Its shortest path is one left arc of length π/2 ≈ 1.570796 m. Increase the radius to 2 m and the tight quarter-circle no longer fits the turning limit. A much longer LRL route of 14.286278 m wins.
Straight ahead has length 4 m. Identical poses has length zero. The table reports each canonical candidate, including ties and geometric infeasibility. The displayed endpoint errors come from integrating the primitives, without moving the last plotted point onto the goal by hand.
Measure arcs and check their joins
Compute path cost from its pieces. An arc with angle α has length ρα; a straight segment contributes its own distance. A polyline used to draw a circle cuts across the arcs and slightly underestimates their length, so the experiment never uses its drawing samples as the cost.
At each join, position and heading agree. Under an arc-length parameter, the tangent (cos θ, sin θ) therefore stays continuous: the path is C¹. Curvature can jump from +1/ρ to 0 or from one turning sign to the other.
This ideal model allows instantaneous steering changes. It supplies no steering-rate limit. A physical steering mechanism with a finite rate needs transitions that obey that limit, followed by another feasibility check. Timing also matters: at speed v, a turn demands lateral acceleration v²/ρ.
The implementation uses a 10⁻¹⁰ tolerance for normalized geometric boundaries and angle seams, plus an independent integrated endpoint check. It accepts finite poses, positive finite radius, and separation up to one million turning radii. These are numerical implementation choices. They do not establish a physical tracking tolerance.
Add the constraints your robot needs
This experiment has no obstacles, footprint, reverse gear, acceleration model, or steering-rate constraint. A successful Dubins connection establishes feasibility under the stated forward-motion and curvature rules.
A planning system must also check the swept robot footprint along the curved route. Testing the endpoints or a few drawing samples can miss a collision. OMPL's Dubins motion validator keeps motion validation separate from computing a Dubins connection and checks motions at a configured resolution.
If the open-plane shortest path hits an obstacle, rejecting it does not prove that the full planning problem has no solution. A planner can search for a route through intermediate poses and check every connection. A longer member of this six-candidate table also needs those checks before use.
A differential-drive robot can rotate in place under its ideal wheel model. A Dubins car cannot. A car that can reverse belongs to a different shortest-path problem; Reeds–Shepp paths include forward and backward motion, with explicit direction changes along the route.
These distinctions matter when smoothing a planned path. Replacing a corner with a circular connection changes geometry, heading, and possibly clearance. Choose the robot model before accepting that replacement.
Integrate two paths in Python
This Python 3 example uses only the standard library. It integrates the two candidates calculated above and prints their exact primitive lengths and final poses to six decimals. It takes the chosen segments as input; it does not construct or compare all six families as the interactive solver does.
For a nonzero constant curvature κ over length ℓ, heading changes by κℓ. Integrating cosine and sine gives the corresponding displacement. The straight case follows the existing heading.
from math import cos, sin, pi, sqrt
def advance(pose, kind, length, radius):
x, y, heading = pose
curvature = {"L": 1, "S": 0, "R": -1}[kind] / radius
end_heading = heading + curvature * length
if curvature == 0:
x += length * cos(heading)
y += length * sin(heading)
else:
x += (sin(end_heading) - sin(heading)) / curvature
y += (cos(heading) - cos(end_heading)) / curvature
return x, y, end_heading
def clean(value):
return 0.0 if abs(value) < 1e-10 else value
radius = 1.0
examples = [
("LSR", [pi / 6, 2 * sqrt(3), pi / 6]),
("RLR", [pi / 3, 5 * pi / 3, pi / 3]),
]
for family, lengths in examples:
pose = (0.0, 0.0, 0.0)
for kind, length in zip(family, lengths):
pose = advance(pose, kind, length, radius)
x, y, heading = pose
degrees = (heading * 180 / pi) % 360
if abs(degrees - 360) < 1e-10:
degrees = 0.0
print(f"{family}: length={sum(lengths):.6f} m; "
f"end=({clean(x):.6f}, {clean(y):.6f}) m; "
f"heading={clean(degrees):.6f} deg")
Expected output:
LSR: length=4.511299 m; end=(4.000000, 2.000000) m; heading=0.000000 deg
RLR: length=7.330383 m; end=(0.000000, 0.000000) m; heading=180.000000 deg
Try it yourself
Exercise 1. Scale the whole problem. Double every position coordinate in the worked offset example and increase the turning radius from 1 m to 2 m. What happens to its normalized geometry, winning family, and shortest length?
Check the scaled connection
The start stays (0, 0, 0), the goal becomes (8, 4, 0), and ρ becomes 2 m. Dividing distances by ρ restores the same normalized problem. LSR still wins, and every primitive length doubles. The total becomes 2π/3 + 4√3 ≈ 9.022598 m. Changing only the radius, as the slider does, would change the normalized endpoint separation.
Exercise 2. Explain the turnaround. Keep the start and goal at the origin but give the goal heading π. Use radius 2 m. What length do the tied RLR and LRL paths have? Why would a zero-length in-place turn violate the model?
Check the turnaround cost and constraint
The arc angles remain π/3, 5π/3, and π/3. Multiplying their sum by 2 m gives 14π/3 ≈ 14.660766 m. The curvature bound is 0.5 m⁻¹. Heading can change only as the vehicle travels forward along the path, so zero traveled distance cannot produce a heading change of π. Select the opposite-heading preset and radius 2 m to check the numbers.
Sources and further study
- L. E. Dubins, 1957: the original bounded-curvature shortest-path paper, American Journal of Mathematics 79(3), 497–516.
- Steven M. LaValle, Planning Algorithms, Section 15.3.1, for the six canonical words and the forward-only model.
- OMPL's DubinsStateSpace implementation, for an independent implementation of the normalized family formulas, with its cited Shkel–Lumelsky classification.
Continue with nonholonomic constraints to derive the local motion restriction that makes these heading-aware connections necessary.