The Biham-Middleton-Levine traffic model

  • The latest movies (made by Nicholas J. Linesch, Aug 2007.)
  • And manuscript: N. J. Linesch and R. M. D'Souza, "Periodic States, Local Effects and Coexistence in the BML Traffic Jam Model" (arXiv:0709.3604), Physica A, 387, 6170-6176, 2008.

  • Recent Progress:   (Summary of the first two articles below, featured as a highlight of the NSF Mathematical Sciences Institutes).

  • R. M. D'Souza, "Coexisting phases and lattice dependence of a cellular automata model for traffic flow", Physical Review E, Volume 71, 0066112, 2005.
    (Discovery of intermediate phases)

  • 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.
    (First rigourous proof for BML. Shows that for densities close to one, the system must jam).

  • R. M. D'Souza, "BML revisited: Statistical physics, computer simulation and probability", Complexity, 12, (2), 30-39, 2006.
    (Review article, highlighting BML -- including a new, asynchronous version -- Bootstrap percolation, and the Rotor-router.)

  • Tim Austin and Itai Benjamini, "For what number of cars must self organization occur in the Biham-Middleton-Levine traffic model from any possible starting configuration?", arXiv:math/0607759v3, 2006.
    (On an NxN lattice, if there are fewer than N/2 cars the BML model will self organize to attain speed one.)

  • Itai Benjamini, Ori Gurel-Gurevich, Roey Izkovsky, "The Biham-Middleton-Levine traffic model for a single junction", arXiv:math/0703201v1, 2007.
    (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.)


    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')    

    But, recently we have found them on conventional square lattices (Physica A, 387, 6170-6176, 2008.)

    Thus periodic structures co-exist at the same density as fully jammed structures, showing that density is not the only control parameter sufficient to determine the jamming outcome.