The Biham-Middleton-Levine
traffic model
Recent Progress:
(Summary of the first two articles below, featured as a highlight of the NSF Mathematical Sciences Institutes).
(Discovery of intermediate phases)
(First rigourous proof for BML. Shows that for densities close to one, the system must jam).
(Review article, highlighting BML -- including a new, asynchronous version -- Bootstrap percolation, and the Rotor-router.)
(On an NxN lattice, if there are fewer than N/2 cars the BML model will self organize to attain speed one.)
(A simplified version studying a single junction. They show that similar phenomena of self-organization and phase transition still occur.)
Older movies.
(Warning: currently these are wmv file, which only play with windows media player)
(MAC OS X users, download flip4mac, a free wmv player.)
Background
The BML traffic model, Introduced in 1992, is perhaps the simplest system exhibiting phase transitions and self-organization. Moreover, it is an underpinning to extensive modern studies of traffic flow. The general belief is that the system exhibits a sharp phase transition from free flowing to fully jammed, as a function of initial density of cars. The existence of this sharp transition has been cited in the scientific literature several hundreds of times.
However, we discover intermediate stable phases, where jams and free flowing traffic coexist. The geometric structure of such phases is highly regular, with bands of free flowing traffic intersecting at jammed wavefronts that propagate smoothly through the space. These intermediate states have a crisp, well defined geometric structure, which is a consequence of the finite size and aspect ratio of the underlying lattice. Aside from discovering these intermediate states, we derive a set of equations based on the underlying geometric constraints imposed by the lattice, and correctly predict the observed velocities.
Definition of the model
Two species of particles, "blue" and "red", are initialized at random sites of a 2-d square lattice with toriodal boundary conditions. On even timesteps, all blue particles simultaneously attempt to move one site to the north. They succeed unless the site they wish to occupy is non-empty, in which case they are "blocked" and stay stationary for that timestep. On odd timesteps the red particles undergo an analogous process, only attempting to move towards the east.
Particles are initialized at random locations, in accordance with some overall density, r. After the random initialization step, the dynamics is fully deterministic.
Conventional Belief
The belief has been that the BML model exhibits a sharp phase transition. When initiated at low density, the cars self-organize ultimately ending up on non-interacting lattices of red and blue, which move freely for all further time (as shown on the left). But initialized at high density, the cars all quickly become blocked and involved in one global jam and remain unable to move ever again (as shown on the right). The belief has been that a sharp transition between the two asymptotic states happens at a critical value of density, r-c.
r < r-c: free flow:
r > r-c: fully jammed:
But in reality, periodic intermediate States exist, with crisp regular geometry and short recurrence times!!
Stripes of red and blue cars wind along the lattice. Cars move freely except at the intersection of the stripes where instead there are Jammed wavefronts (the dark regions). As the system evolves in time the wavefronts move uniformly through the space, resembling solitons. (View a movie!)
These periodic structures were thought to exist only on relatively prime lattices
The following two systems are almost identical, except on the right hand side, the x-axis is smaller by one cell.
Crisp order requires relatively prime axis ratio: If not relatively prime, the final state has some disorder.
L x L' = 769 x 256 L x L' = 768 x 256
(i.e., L = 3L' +1) (i.e., L = 3L')
| [Home] |