The Biham-Middleton-Levine Traffic Model

(See below for information about the pictures).

10% cars	30% cars	32% cars
32% cars	34% cars	80% cars

What is this?

The following simple model for traffic congestion was introduced in [2]. Each intersection of a square grid of streets contains either an East-facing car, a North-facing car, or an empty space. At each odd-numbered time step, all the North-facing cars simultaneously attempt to move one unit North; a car succeeds if there is already an empty space for it to move into. At each even-numbered time step, the East-facing cars attempt to move East in the same way.

Initially, cars are distributed at random: each intersection is independently assigned a car with probability p, or an empty space with probability 1 - p. Each is car is independently equally likely to be East-facing or North-facing.

The pictures show results of running the model for 20,000 steps on a 200x200 grid with "periodic boundary conditions" - that is, a car which falls of the East edge of the board immediately returns on the West edge, and a car which falls off the North returns on the South. The initial densities of cars p in the various pictures are 10%, 30%, 32% (two examples), 34%, and 80%. East-facing cars are red, North-facing cars blue.

Phase transition

Judging by the pictures, the behaviour of the model seems to depend drastically on the density of cars p. For high densities (e.g. 80%, 34%), after a while traffic becomes jammed, and no car can move at all. For low densities (e.g. 10%, 30%), after a while traffic is completely free flowing, and no car ever has to wait at all. For densities close to the cutoff between these two behaviours, the model appears to exhibit remarkable large-scale organisation; e.g. in the 34% picture there is a single jam spanning the entire grid, while in the 30% picture the cars have arranged themselves into wide diagonal bands which avoid each other. For densities very close to the cutoff, other types of "intermediate" behaviour are seen. In the two 32% pictures, all cars move some of the time and wait some of the time, and this is achieved by remarkable semi-regular geometic patterns of jams feeding into each other.

Mathematics

Although the model is very simple, rigorous analysis appears to be difficult. The only rigorous progress so far is a proof [1] that (with high probability as the box becomes large) traffic does indeed become fully jammed when the density of cars p is high enough. It is an open problem to prove anything about small p, even that traffic is not fully jammed when p is sufficiently small (uniformly in the size of the box).

More information on simulation is reported in [3],[4]; in particular, the mysterious "intermediate phases" are investigated there.

References

[1] O. Angel, A. E. Holroyd & J. B. Martin: The Jammed Phase of the Biham-Middleton-Levine Traffic Model. Electronic Communications in Probability, 2005, Vol 10, Paper 17, 167-178.

[2] O. Biham, A. A. Middleton & D. Levine: Self-organization and a dynamical transition in traffic-flow models . Phys Rev A, Vol 46, Issue 10, 1992, R6124-R6127

[3] R. M. D'Souza: Coexisting phases and lattice dependence of a cellular automata model for traffic flow, Physical Review E, Volume 71, 066112 (2005).

Alexander E. Holroyd 2005