A circle for the first millimetre

A car with a curvature bound and no reverse gear is the most constrained mechanism in this field. It can be brought to any placement, as everything with a rolling constraint can, but the route is decided by two conditions rather than one — the sideways direction is forbidden, and the turning circle has a floor — and the combination has a consequence that a straightforward reading of the constraint does not predict.

The shortest such route between two placements is always one of six shapes. Not approximately six, not usually six: six, with each one a formula.

The six words #

Write L for a turn at full left lock, R for full right lock, and S for a straight. Dubins’ theorem says the shortest path is one of

$$\mathrm{LSL},\ \mathrm{RSR},\ \mathrm{LSR},\ \mathrm{RSL},\ \mathrm{RLR},\ \mathrm{LRL},$$

and in the three-arc cases the middle arc turns through more than a half-turn. Nothing else is ever shorter.

The reason it is a short list is worth a sentence, because it is the same reason a straight line is the shortest path in an unconstrained plane: the extremals of a length problem with a bounded control are bang-bang — the control sits at one of its limits, switching between them — with at most two switches. Full lock, or straight, and nothing in between; and never more than three segments.

That makes the shortest-path problem a classification rather than a search. Enumerate the six, evaluate each formula, discard the ones with no solution, take the shortest of the rest. There is no optimiser, no starting guess, and no local minimum to fall into. Given a start, a goal and a radius, the answer arrives in a few dozen floating-point operations.

Checking a closed form that has no obvious second route #

Six closed forms are exactly the situation where this site is most exposed. Every one is a page of trigonometric identities, all six can be transcribed with a sign wrong, and every one of them will still produce a path. The picture will look plausible whatever the algebra did.

The first check written here was worthless, and it is worth describing because the failure is the one this site keeps finding. It took each closed-form word, scaled its first arc by a few per cent, and asked whether the scaled version was ever shorter. It never was, and the check passed — and it passed because a scaled arc does not arrive at the goal, so the comparison set was empty. Nothing was ever compared with anything. The assertion reported success on evidence it had not collected, in the same way a solver seeded with its own closed form once agreed with it having never run.

What replaced it is a shooting solve. For a fixed word the three segment lengths are three unknowns and arriving at the goal is three equations, so it is a square root-finding problem: run Gauss–Newton on it from a grid of starting guesses, keep every solution with all three segments non-negative, and take the shortest. It shares nothing with the closed forms below the arc stepper, and it answers the same question by a route that could disagree.

Over sixty goal placements, thirteen of which have a three-arc path as their answer, the worst discrepancy between the closed forms’ shortest and the shooting solve’s shortest is

$$6\times10^{-15}.$$

What the search found that the formulas do not list #

The comparison turned up something the formulas are silent about, and it is a correction to how the six words should be read.

For the goal at $(2, 1)$ with a half-radian heading change, the closed forms return LRL at 11.249 and RLR at 9.073. The shooting solve finds an LRL path at 2.318 and an RLR path at 2.493 — far shorter, and they genuinely arrive.

Neither of those is a defect in the formulas. The three-arc formulas are written to return the branch whose middle arc exceeds a half-turn, because that is the branch Dubins’ theorem admits as a candidate for shortest. The shorter branches are perfectly good paths that are simply never optimal — and in this case they are not, since the LSR path at 2.256 beats both.

So the honest statement is not the six words are the paths. It is:

the six words are the paths that could be shortest, and there are others, and the others are never the answer.

That distinction is the sort of thing a check has to be able to notice, and the first version of the check could not have. A test that compares a formula against a slightly perturbed copy of itself cannot discover that a whole family of solutions exists outside the formula’s branch.

The result the essay is named after #

Ask for the cheapest way to end up directly to one side, at the same heading, a distance $\delta$ away. This is the manoeuvre a driver wants when the car is one lane over from where it should be, or half a metre from the kerb it needs to be against.

Below $\delta = 2.956\,R$ the answer is exactly

$$2\pi R + \delta,$$

and the reason is one sentence. Driving a complete circle returns a car to exactly where it started; inserting a straight of length $\delta$ into that circle, at the point where the car is pointing across the road, displaces the end by $\delta$ sideways and changes nothing else. So the manoeuvre is a full turn plus the offset, and the departure of the measured shortest path from that expression, at two hundred offsets below the crossover, is $10^{-9}$ m — which is the integration of the path rather than the formula.

The consequence is the striking part. As $\delta \to 0$ the cost does not go to zero; it goes to $2\pi R$. For a five-metre turning radius:

A car that may not reverse gets to a point twenty metres to the side for a metre less than it gets to a point one millimetre to the side. Both are a complete circle; the second has a straight inserted into it and the first does not.

At $\delta = 4R$ the answer is two half-circles with no straight between them — an S — which is $2\pi R$ exactly. And the cost is not monotonic in the distance: it rises from $2\pi R$ to a maximum of 46.198 m at the crossover and comes back down again. The most expensive lateral offset for a five-metre car is not the smallest one and it is not the largest; it is 14.78 m.

Where the crossover is, and what changes there #

The crossover is found by bisection rather than quoted: at $\delta/R = 2.9563$, the full-turn word and the three-arc words are equally long, at 46.1976 m for $R = 5$. Below it, going all the way round and inserting a straight wins; above it, a sequence of three arcs is shorter.

At the crossover four of the six words are simultaneously optimal — LSL, RSR, RLR and LRL all return 46.1976 — which is what a crossover between two families looks like when both families are symmetric about the same axis. A single tie would be a coincidence; four is a symmetry.

That is the kind of place this site’s singularities habit says to look, and here it is benign: nothing degenerates, no matrix loses rank, and the only thing that happens is that a discrete choice changes. It is worth marking anyway, because a design that computes a Dubins length and differentiates it with respect to the offset will find the derivative discontinuous there.

The reverse gear is worth 2πR #

Put this next to the shuffle, which is the same job done by a mechanism allowed to reverse.

Shuffling to gain $\delta$ with $s$ metres of room costs $2\delta R/s$ of driving. Going round costs $2\pi R + \delta$. At $R = 5$ and $s = 0.5$ the two are equal at $\delta = 1.65$ m: below that, shuffle; above it, drive round.

So the reverse gear is worth, at most, about $2\pi R$ — one complete circle — and it is worth that only for small offsets. For a large lateral move, reversing buys almost nothing, because the forward-only path is nearly as short as an unconstrained one. That is a quantitative version of something every driver knows and nobody states: reversing matters in car parks and not on roads.

It also explains a design decision that looks odd from outside. Aircraft do not reverse under their own power, and an aircraft on the ground is exactly this mechanism: a nose-wheel steering angle with a bound, no reverse, and a curvature limit. The taxiways are laid out so that no aircraft ever needs a small lateral offset — every movement is a large one, where the forward-only cost is close to the unconstrained cost — and where a small offset is unavoidable, a tug is brought.

Why the switch points are where they are #

One more property of the six words is worth stating, because it turns the classification from a list into something a reader can predict.

Every path in the list begins and ends with an arc at full lock, and the switch points are decided by tangency. The first arc is on a circle of radius $R$ tangent to the start placement — there are two such circles, one on each side, which is where L and R come from — and the last arc is on a circle tangent to the goal. A CSC path is then the common tangent between those two circles, and there are exactly four common tangents to two circles of equal radius: two external and two internal, giving LSL, RSR, LSR and RSL.

That is the whole enumeration, and it is a piece of school geometry. The internal tangents exist only when the two circles are far enough apart, which is exactly when the corresponding words return no solution; the three-arc words are what covers the case where they do not.

So the six are not a list to be memorised. They are two circles at each end and the ways of getting between them, and the count of ways is the count of common tangents plus the two three-arc cases.

The lower bound, which is the useful half #

For anyone laying out a space in which wheeled things have to move, the number that matters is not the shortest path between two given placements but the worst shortest path over a region — how much room to allow.

Two bounds fall out of the classification with no work.

The Dubins length is never less than the straight-line distance, obviously. It is also never more than the straight-line distance plus $2\pi R$: whatever the placements, a path exists that turns to face the goal, drives to it, and turns to the required heading, and the two turns together are less than a full circle. So

$$d \;\le\; \text{Dubins} \;\le\; d + 2\pi R,$$

and the upper bound is attained, at $d = 0$, by the case this essay is named after.

That is a complete answer to how much worse can it be, and its shape is worth noticing: the penalty for the constraint is additive and bounded, not multiplicative. A vehicle with a five-metre turning radius never travels more than 31.4 m further than a point-like one, however long the journey. Over a hundred-metre movement that is a third; over a kilometre it is negligible; over a metre it is everything.

A cost that is not monotonic in the distance #

The result the essay is named after has a consequence for anything that searches over these paths, and it is worth stating even though planning is not built here, because it explains why the classification is worth having beyond its own tidiness.

The cost of reaching a goal is not monotonic in how far away the goal is. A point one millimetre to the side costs 31.417 m and a point twenty metres to the side costs 31.416 m, so moving the goal further away made the journey shorter. Every search method that assumes otherwise — every method that treats closer as better and works by reducing a distance — is wrong on this mechanism, and wrong in the region where the goals are nearest.

That is not a subtlety. A greedy planner asked to reach the millimetre-offset goal will refuse the twenty-metre detour that is the answer, because every step of it increases the distance to the target and the planner has no representation in which that is progress. It will instead grind at the goal, find nothing, and report failure on a problem whose solution is a single circle.

A search with a heuristic behaves differently and is degraded rather than broken. Straight-line distance is a valid lower bound on Dubins length — that is the first of the two bounds above, and it is what makes such a heuristic admissible — so the search stays correct. What it loses is guidance: a heuristic of 0.001 m against a true cost of 31.4 m carries essentially no information, so the search expands nearly everything and the admissibility that keeps it correct is doing none of the work a heuristic is for.

The repair is the classification itself, and this is where the six words earn their keep outside geometry. The Dubins length is a closed form, computable between any two placements in the time it takes to evaluate six expressions and take a minimum. Used as the heuristic it is exact in the absence of obstacles, which means the search does no expanding at all on an empty space and expands only where an obstacle actually forces a detour. The difference between the two heuristics on the millimetre problem is the difference between a hopeless search and no search.

The upper bound does the complementary job and is the one that matters for laying out a space. Nothing costs more than the straight-line distance plus about $2\pi R$, and the excess is attained — so a designer can guarantee that any placement reachable at all is reachable for a bounded premium, and the premium is a property of the vehicle rather than of the layout. That is a stronger statement than an average and it is the kind a specification can be written against.

Both readings come from the same place, and it is worth naming what that is. A closed-form solution to a shortest-path problem is not primarily a way of computing one path; it is a way of computing distances, and a distance that is cheap and exact is what every other algorithm in the subject is built on. The six words are the mechanism’s metric, and the metric is the thing that gets used.

What is not claimed here #

The shortest path under a curvature bound is a geometric classification, and this site takes it as one. What it does not take is the subject that classification is a component of.

Planning is not here. Choosing a route through a car park with other cars in it, finding a sequence of manoeuvres that avoids obstacles, sampling a configuration space, building a roadmap — all of that is search, it belongs to whoever owns searches, and the same boundary was drawn when an arm’s configuration space was taken as a set rather than as something to look through. What is claimed is that between two placements in an empty plane the shortest path is one of six shapes, each with a formula, and that a numerical solve agrees.

Reeds and Shepp’s extension is named and not built. Allowing reverse turns the six words into a list of forty-eight, with cusps where the direction of travel changes, and the shortest path becomes a longer classification of the same kind. It is the natural next object and it is not here; what is here about reversing is the shuffle, which is a different question — repeatable gain rather than shortest route.

Nothing about speed, and nothing about comfort. A Dubins path has curvature discontinuities at its switch points, which a passenger feels as a jerk and a real vehicle cannot follow exactly at speed without a steering rate limit. Smoothing those is a design problem with its own literature and its own trade-offs, and every one of them is about how fast the steering can be turned — which is a rate, and this field’s arithmetic is about geometry.