A jam that comes from nowhere

A road where nobody overtakes found a traffic model in the list of elementary cellular automata. Rule 184 moves every car one cell forward if the cell ahead is empty and leaves it otherwise; cars are conserved, jams below half density dissolve within a lap, and above half density a fixed share of cars is always stopped. Everything about it can be computed exactly, including its fundamental diagram — the flow of cars against their density — which is a tent: rising in a straight line to half density and falling symmetrically after.

Real motorways do something rule 184 cannot. On a road with no accident, no lane closure and no bottleneck, traffic moving freely at moderate density can suddenly clot into a jam that travels backwards down the road, with drivers emerging from its front unable to say what caused it. In 1992 Kai Nagel and Michael Schreckenberg added two things to rule 184 — more than one speed, and a small chance of slowing down for no reason — and the phantom jam appeared.

The figure shows twenty-nine cars on a ring road, time running down the page, each car’s colour giving its speed. The freely moving cars travel as diagonals from upper left to lower right. The red streaks are stopped cars: jams. They form in the middle of free traffic, they slant the other way — backwards, from upper right to lower left — and they persist, dissolving at their front as cars pull away and growing at their back as cars arrive.

Four rules and one of them random #

The model has four steps, applied to every car at once each tick of the clock.

Accelerate. If the car’s speed is below the maximum, five cells per step, it increases by one.

Keep a distance. If the gap to the car ahead is smaller than the speed, the speed is reduced to the gap. This rule alone guarantees there are no collisions.

Dawdle. With probability $p$, a moving car’s speed is reduced by one — a driver who eases off, looks at the scenery, or overreacts to the car in front.

Move. Each car advances by its speed.

The first two rules are deterministic and reasonable: drivers want to go fast and do not want to crash. The third is the only source of randomness, and it is small: at $p = 0.25$, a car is slightly slower than it could be on one step in four. The figures check that no two cars ever occupy the same cell, which the second rule ensures, and that the number of cars never changes, which is the conservation law the whole of a road where nobody overtakes turned on.

A jam from perfectly even traffic #

The clearest demonstration starts from the most orderly traffic possible.

Thirty-two cars on a ring of 160 cells, each five cells behind the next, all moving at four cells per step. Without dawdling this is a steady state: every car keeps exactly its gap forever, and the figure confirms that no car ever stops. With dawdling at $p = 0.15$, a car eases off by one; the car behind, closing in, must brake to the reduced gap; the car behind that brakes harder, because by the time it responds the gap in front has closed further. Within ten steps a car has come to a complete stop, and a jam is born.

The mechanism is amplification. A single dawdle reduces one car’s speed by one cell per step. The following cars cannot respond until the gap has shrunk, and each responds to a smaller gap than the one before, so the disturbance grows as it passes backwards through the traffic. At low density the gaps are large enough to absorb it; above a critical density they are not, and the disturbance grows into a standing jam. That is the same instability that experiments on real roads have reproduced: in 2008 Yuki Sugiyama and colleagues drove twenty-two cars round a circular track 230 metres long, asked the drivers to keep a steady speed, and watched a jam form and travel backwards within minutes.

What chance costs the road #

The price of dawdling is visible in the fundamental diagram.

With no dawdling, the model’s flow is exactly $\min(5\rho,\, 1 - \rho)$ once the traffic has settled: at low density every car moves at full speed and the flow is five times the density; at high density the flow is limited by the gaps, one car’s worth of movement per empty cell. The peak is at density $\tfrac16$, where the two lines meet, and the figure checks the measured flow against the formula at every density drawn.

With dawdling, the peak falls and rounds off. At $p = 0.25$ the best flow the road carries is about $0.55$ cars per cell per step, a third less than without; at $p = 0.5$ it is less than half. The peak also moves to lower density, because jams start forming earlier. A small amount of randomness at the level of single drivers costs a large share of the road’s capacity, and none of the loss is caused by the road.

The model’s diagram has the shape measured on motorways: a steep rise in the free-flow regime, a rounded maximum, and a long falling branch where jams live, with the measured points scattered widely there. Rule 184’s diagram, by comparison, is sharp.

Rule 184 is the simplest corner #

The two models are not merely similar. One contains the other exactly.

Set the top speed to one and the dawdling probability to nought. Then a car accelerates to speed one if it is stopped, keeps speed one unless the cell ahead is occupied, and moves one cell — which is rule 184’s rule exactly. The figure runs both from the same random start for seventy steps and compares every cell of every row; they agree everywhere.

So the Nagel–Schreckenberg model is a family with two dials, top speed and dawdling, and rule 184 sits at the corner where both are turned down. Turning either one up changes the character of the model. Raising the top speed alone moves the peak of the fundamental diagram and makes it asymmetric but keeps it sharp, since the model stays deterministic. Adding chance alone, at top speed one, rounds the corner: for that case the flow is known exactly,

$$J = \tfrac12\left(1 - \sqrt{1 - 4(1 - p)\rho(1 - \rho)}\right),$$

which is a rounded version of rule 184’s tent. It is the combination — several speeds and chance — that produces jams from free flow.

Why several speeds and chance together #

The two ingredients do different jobs, and the jam needs both.

Chance supplies the trigger: without it, a steady state of evenly spaced cars never changes. Several speeds supply the amplifier: when a car can drop from five to four to three, each following car has room to overreact, braking to a gap that has already shrunk, and the disturbance grows. With only one speed there is nothing to amplify — a car is either moving or stopped, and a single dawdle creates a gap that simply travels backwards without growing. With several speeds but no chance, the evenly spaced state is stable and nothing ever triggers it.

This is the pattern a difference too small to draw found in deterministic chaos, in a different form: a small disturbance amplified by the dynamics into a large effect. Here the amplification is local and the system is noisy, and the result is not chaos but a new collective object, the jam, that has a life of its own — a speed, a direction and a lifetime — independent of the cars that pass through it.

The front of a jam is a random walk #

The randomness has a second effect, beyond triggering jams: it makes each jam’s life uncertain. In rule 184 a jam’s length changes deterministically, one car leaving from the front and one arriving at the back per step while the density stays fixed. In the random model, cars leave the front only when they choose not to dawdle while starting, and arrive at the back at irregular intervals, so the jam’s length goes up and down by chance from step to step.

That makes the length of a jam a random walk, with a drift set by whether cars arrive faster than they leave. Below the critical density the drift is towards shrinking and every jam eventually dissolves; above it, towards growing, and jams merge into long ones. Near the critical density the drift is almost nought, and the jam’s length wanders like the walks of a walk that comes home: it returns to nought with certainty but can take an extremely long time to do so, which is why jams near the critical density have lifetimes spread over many orders of magnitude.

The same picture explains why real congestion is so variable. Two days with the same traffic volume can produce very different jams, because the volume sets the drift and chance sets everything else.

The flow curve predicts which way a jam moves #

There is a way to read the direction of a jam straight off the fundamental diagram, and it predates cellular automata by decades. In 1955 James Lighthill and Gerald Whitham, and independently Paul Richards, treated traffic as a fluid whose flow $J$ depends only on its density $\rho$. Conservation of cars then says that a small change in density travels along the road at speed $J'(\rho)$, the slope of the flow curve.

On the rising branch of the curve, where traffic is free, the slope is positive and disturbances travel forwards with the cars. On the falling branch, where traffic is congested, the slope is negative and disturbances travel backwards. For rule 184 the falling branch is $J = 1 - \rho$, of slope $-1$, and jams move backwards exactly one cell per step, as a road where nobody overtakes observed. For the random model the falling branch is less steep, and the jams in the figures drift back somewhat more slowly than one cell per step.

A jam moves backwards because it lives on the falling branch: inside it the density is high, and on that side of the peak every added car reduces the flow. The same reasoning says why a jam’s front and back behave differently. Where cars leave a jam, density drops through the peak of the curve and the transition spreads out smoothly; where they arrive, density rises from the free branch to the congested one and the transition stays sharp, a shock. That asymmetry, visible in the figures as ragged fronts and sharp backs on the red streaks, is a property of any flow curve with a single peak.

The comparison with the moment a giant appears is apt in one respect: there, a network’s largest cluster changes character at a critical density of links, as the traffic changes character at a critical density of cars. In both, the transition is sharp in the idealised model and blurred by randomness in the realistic one.

Jams have their own speed #

A jam in the model travels backwards at a characteristic speed, and it does not depend on the density or on how the jam was formed.

The reason is visible at the jam’s two ends. At the front, cars leave one at a time: each stopped car must wait until the car ahead has moved, then accelerate from zero. At the back, cars arrive at whatever rate the traffic behind delivers them. A jam in a steady state is one where these rates balance, and its front moves backwards by about one cell for every car that escapes, which happens at a rate fixed by the acceleration rule and the dawdling probability. In the figures, the red streaks slant at nearly the same angle wherever they appear.

Real jams behave the same way. Stop-and-go waves on German motorways, measured by Boris Kerner and others in the 1990s, travel upstream at about fifteen kilometres per hour almost regardless of conditions — a number the model reproduces in its own units when its cells and steps are given lengths and times. The jam is a property of the dynamics, not of any particular car.

One step per car, all at once #

The model updates every car simultaneously, from the state at the previous step, and that choice matters. Eight rules and a triangle introduced elementary automata with exactly this parallel update, and the traffic rules inherit it. If cars were updated one at a time in a random order instead, the model would behave differently: a car that happened to be updated after the car in front had already moved would see a larger gap and never need to brake, and much of the amplification would disappear.

This is one of the reasons cellular automata are good models of traffic and poor models of many other things. Drivers really do react to what they saw a moment ago rather than to what is happening now, and the delay built into a parallel update — every car responding to the previous step’s positions — is exactly the reaction time that turns a small slowdown into a jam. The jam lives in the delay, and a model without one would not produce it.

The locality is the other ingredient. Each car sees only the gap in front of it, never the traffic a hundred cells ahead, and so no car can anticipate a jam forming downstream. No local rule can count the votes showed how much a local rule cannot do; here the same locality is what lets a jam form, since a driver who could see the whole road would never brake so late.

What the figures can and cannot show #

Every run is seeded and every step obeys the rules. The figures check at every step that no two cars share a cell, and the fundamental diagram checks the no-dawdling flow against its exact formula; the dawdling curves are averages over a single long run at each density, which is why they wobble.

The ring is a convenience. Real roads have entrances, exits and more than one lane, and jams on them often do start at bottlenecks. The model shows that bottlenecks are not necessary, not that they are unimportant.

The rounded peak is measured, not derived. For top speed five with dawdling, no exact formula for the flow is known; the curves are simulation, and their shape near the peak depends slightly on the length of the ring and of the run.

Still open: whether the transition is sharp #

With no dawdling, the change from free flow to jammed flow happens at a single density, $\tfrac16$ for top speed five, and the flow has a sharp corner there. With dawdling, the corner rounds off — but whether there is still a genuine phase transition hidden inside the rounding, a density at which the character of the traffic changes abruptly in an infinitely long road, or only a smooth crossover, is a question that has been argued since the model was introduced.

Numerical studies find that for small dawdling probability the change looks sharp, with long-lived jams appearing suddenly above a critical density, while for large dawdling it looks gradual. Whether the sharpness survives as the road grows to infinite length, and whether the model has a true critical point for small $p > 0$, has not been settled: simulations point in different directions depending on how the transition is measured, and no exact solution is known once the top speed exceeds one.

A road that jams itself #

The habit worth keeping is to find the smallest ingredient that produces the effect.

Rule 184 is exactly solvable and never produces a phantom jam. Adding several speeds alone does not produce one, and adding chance alone does not either. The two together — a trigger and an amplifier — are enough, and with them a road with no obstacle anywhere produces jams that form from nothing, travel backwards at their own speed, and take a third of the road’s capacity with them.