The shortest route a vehicle can fly

Nine rungs of this anchor find a shortest path. Under the sphere’s metric it is a great circle; on the ellipsoid it is a geodesic and hard to compute; round an obstacle it wraps a cap; in a flow it is not the shortest at all.

Every one of them hands back a curve and stops. Nothing that travels can follow an arbitrary curve.

What a bounded turn changes #

An aircraft in a coordinated turn has a radius set by its speed and its bank angle. A ship has one set by its rudder and its hull. A railway has one set by the permitted lateral acceleration, and a road by the same thing plus what a driver will tolerate.

The moment a curvature bound exists, the shortest-path problem changes shape in a way worth stating precisely.

It acquires two more arguments. A geodesic is determined by two positions. A curvature-bounded path is determined by two positions and two headings, because the vehicle arrives on one heading and must leave on another, and neither can be changed instantly.

Its answer stops being a single family. Dubins proved in 1957 that the shortest curvature-bounded path in the plane is always one of exactly six: three arcs, or an arc, a straight and an arc, with the turns in each of the four sign combinations. The problem has a closed form and the closed form is a case analysis.

What was computed, and how #

Dubins’s six words, in Shkel and Lumelsky’s formulation, in normalised units where the turning radius is one. The construction is planar and is applied here in a chart centred on the leg — stated as an approximation rather than hidden, and legitimate here because the comparison is between two paths in the same chart, both of which the chart distorts identically.

Three checks run before any number is read.

A path whose headings are both along the line is the line. At four leg lengths from ten to a thousand kilometres, the excess is zero to 10⁻⁹ — the construction produces the geodesic when the geodesic is feasible, which a case analysis with a sign error in it would not.

No bounded path is ever shorter than the straight line. Over 576 combinations of two headings and three leg lengths, every excess is non-negative. A negative one would mean a word had been evaluated with the wrong branch of an inverse tangent.

All six words win somewhere. On a leg of 2.4 turning radii, over the whole heading plane, each of the six is the shortest somewhere — so the catalogue is not decoration.

The turning cost is fixed #

The absolute excess is the same number at every length, to the last digit. The turning cost is a fixed number of turning radii, decided by the two headings, and the distance between the points does not enter it — so the fraction falls as exactly one over the leg length and the fitted slope is −1.0000.

That is a small result with a sharp consequence. The place a geodesic is most obviously right — a short hop, where the great-circle correction to a rhumb line is negligible and nobody thinks twice — is exactly the place the curvature bound costs the most.

And the heading is worth more than the projection #

On a hundred-kilometre leg the excess runs from 0 to 16.2 kilometres depending only on which way the vehicle happens to be facing when it starts.

Sixteen per cent is a large number in this collection. Why Mercator exists prices the rhumb line’s excess over the great circle, which on a mid-latitude ocean crossing is a few per cent; the gnomonic companion prices what a chart can do about it. The heading is worth several times either, and it is not in any of the nine rungs below because none of them has a place to put it.

The chart’s own contribution #

The rung would be a piece of robotics and not cartography if it stopped there. It does not, because the vehicle’s constraint is a ground constraint and the plotting is done on a page.

A pilot holds a bank angle and traces a circle of stated radius on the ground. On the page that circle is the indicatrix — the same ellipse Tissot’s indicatrix has been drawing since the first essay in this collection — so:

A navigator plotting a turn with a pair of compasses is assuming a conformal chart. That is why every aeronautical and nautical chart in the world is conformal, and it is a much more concrete reason than the one usually given — that a conformal chart preserves angles, which matters for a bearing. It preserves shapes at a point, and a turning circle is a shape at a point.

The radius to set the compasses to is a second question, and the two conformal rows answer it differently: Mercator draws the same ground turn at ten kilometres and the Lambert conformal conic at five, because a conformal map fixes the ratio of the scales and not the scale. So the compasses need the local scale factor, which is what a scale bar is right about in one place.

What a planner and an operator disagree about #

The fixed-cost result has a consequence for how routes are assessed, and it is the kind that is invisible until somebody flies one.

A planner tests on long legs, because those are where the interesting choices are — which great circle, which flight level, which weather. On a long leg the curvature bound costs a quarter of a per cent and is correctly ignored.

An operator flies short legs too, and on those the same bound costs a fifth of the distance. A departure, an approach, a hold, a diversion: each is a few turning radii long, and each pays the entire turning cost. That is the same asymmetry flying a curve in straight legs reports about discretisation, with the sign reversed: there the error is proportional to the leg and vanishes on short ones.

So a route library validated against long-leg statistics can be systematically optimistic about exactly the segments where fuel and time are being decided under pressure. The measurement above is what says by how much: the cost is 1.81 kilometres per manoeuvre in the stated case, it does not shrink with the leg, and the number to compare it against is the leg rather than the total.

Where the model stops #

The construction is planar. The genuine curvature-bounded shortest path on a sphere is not Dubins’s, and for legs comparable to the Earth’s radius the two differ. Everything measured here is on legs of tens to hundreds of kilometres against a turning radius of a few, where the chart’s own distortion over the leg is parts in a million and the planar construction is the right one.

Curvature is bounded and nothing else is. A real vehicle also has a bounded rate of change of curvature — a driver cannot snap the wheel over — which is why a railway curve has a transition spiral rather than meeting the straight at a tangent point — a curve whose own curvature grows linearly, and which is therefore not one of the six. The bounded-jerk problem has its own literature and its own longer answers.

And the turn radius is constant. An aircraft’s is a function of its speed, so a climbing or decelerating vehicle has a radius that changes along the route, and the shortest path is then a control problem rather than a case analysis.

Nothing here is a flight plan. A real route is constrained by airspace, by waypoints, by traffic and by fuel — the quickest route is not the shortest prices one of those — and a curvature bound is the smallest of them on a long leg and not on a short one.

Why the six words are six #

The catalogue is short for a reason worth one paragraph, because it is what makes the problem have a closed form at all rather than needing an optimiser.

The shortest curvature-bounded path is an optimal control problem with one control — the steering — bounded between two values. Pontryagin’s principle says the optimal control of such a problem is bang–bang: it sits at one limit or the other, with at most finitely many switches. At the limits the vehicle turns as hard as it can one way or the other; between them, if the control is at zero, it goes straight.

So every optimal path is a sequence of hard-left arcs, hard-right arcs and straights, and Dubins’s contribution is the bound on how many: at most three segments, of which the middle may be a straight and the others may not. That gives four words with a straight in the middle and two with an arc, which is six.

The straight-middle words are the long-leg cases and the arc-middle ones are the short-leg cases, which is the split the word chart above measures: RLR and LRL exist only when a straight segment between the two turning circles would be a detour, and that happens when the two points are close together relative to the turning radius.

The generalisation #

A shortest path is shortest within a class, and the class is usually left unstated.

Nine rungs of this anchor vary the metric — spherical, ellipsoidal, obstructed, flowing — and hold the class of admissible curves at “all of them”. This one holds the metric and varies the class, and the effect is of the same size as everything the metric does.

The collection has the same structure elsewhere. Every projection minimises something is the observation that an optimum is meaningless without the set it is an optimum over; not every distortion can be asked for is what happens when the class is empty. Here the class is non-empty, the optimum exists, and it is a different curve.

The transferable form: a route computed for a point is not a route for a vehicle, and the difference is a fixed cost per manoeuvre rather than a proportion of the distance — so it is invisible on the long legs a planner tests on and dominant on the short ones an operator flies.

What the six-word structure buys the chart #

One more consequence for the map, and it is the practical reason a chart matters here at all.

Every optimal path is a sequence of circular arcs and straight segments. That is exactly the vocabulary a navigator has on paper: a pair of compasses and a straight edge. So a curvature-bounded route is constructible with the instruments on the chart table, which is not true of a geodesic on the ellipsoid, of a least-time track in a flow, or of anything else in this anchor.

The construction needs the arcs to be arcs, which needs the chart to be conformal, which is the table above. And it needs the turning radius in page units, which needs the local scale factor. Given both, the shortest flyable route between two headings is four compass swings and a ruled line — and the reason the classical chart table has exactly those instruments on it is not a coincidence.

One more measurement that follows from the fixed cost, and it is the one a scheduler would use. Because the turning penalty does not depend on distance, a route broken into k legs pays it k times: a direct crossing pays 1.81 kilometres and the same crossing through four waypoints pays four times that, whatever the waypoints are. So the cost of a waypoint is a constant, it is knowable before the waypoints are chosen, and it is not proportional to anything about the route.

Who found it, and when #

Lester Dubins proved the six-word theorem in 1957, in a paper about curves of bounded curvature rather than about vehicles; Reeds and Shepp extended it to vehicles that can reverse in 1990, and Shkel and Lumelsky gave the classification used here — which of the six to evaluate, without evaluating all of them — in 2001.

The cartographic half is older and is not usually stated as a theorem at all. Aeronautical charts have been conformal since there have been aeronautical charts, and the reason given is bearings. The turning-circle reason is at least as good and is sharper: a bearing is a single angle and can be corrected with a protractor and a note about convergence, while a turn plotted with compasses on a non-conformal chart is wrong in a way no correction table can carry, because the error depends on the direction the turn happens to be entered from.

What a constant waypoint cost decides #

The turning penalty being fixed rather than proportional is the finding with the most direct use, because it turns a planning question into a comparison of two numbers.

A waypoint is worth adding when it saves more than the penalty. The penalty is 1.81 kilometres, always, whatever the leg lengths and wherever the waypoint is. So the rule is arithmetic: compute the distance saved by routing through the point, compare it against 1.81 kilometres, and add it if it wins.

Which makes waypoints nearly free on a long route and expensive on a short one. On a five-thousand-kilometre crossing the penalty is four hundredths of a per cent, so a planner can add waypoints for weather, traffic separation, diversion airfields or airspace at essentially no cost in distance. On a two-hundred-kilometre sector the same four waypoints cost about three and a half per cent, which is a real number.

And the asymmetry is the opposite of the intuition. A long route feels like the one where every kilometre matters, because the total is large; a short one feels forgiving. The arithmetic says the reverse — a fixed cost is negligible against a large total and significant against a small one — and the fixed cost is the only thing the turning constraint contributes.

It also settles what a route optimiser should be searching over. If the penalty scaled with distance, the placement of a waypoint would trade against the turning cost and the optimisation would be genuinely two-dimensional. It does not, so the two decompose: choose the waypoints for the distance they save, and add a constant per waypoint at the end. The turning constraint never changes where a waypoint should go, only whether it is worth having.

There is one caveat that keeps the rule honest. The penalty is fixed for a vehicle of a given turn radius at a given speed, and both of those vary in flight — a heavier aircraft at a higher speed turns wider — so 1.81 kilometres is the figure for the case computed here rather than a universal constant. What generalises is the structure: whatever the vehicle, the penalty per waypoint does not depend on how far apart the waypoints are, and that is the property the decomposition rests on.

Which is worth stating because it is a negative result about a hard problem. Curvature-constrained path planning is difficult in general, and this particular constraint, on this particular kind of route, contributes a term that does not interact with anything.

Which is why the figure is quoted with the vehicle it belongs to.

Where the ladder goes next #

Ten rungs price a route’s metric, its obstacles, its flow, its instrument and now the thing travelling along it. What none of them prices is the route as a sequence of decisions: a real crossing is re-planned as the weather changes, so the route flown is a chain of shortest paths from moving starting points, and whether that chain is anywhere near the shortest path from the original start is a question no single optimisation answers.