Biham–Middleton–Levine traffic model

The Biham–Middleton–Levine traffic model is a self-organizing cellular automaton traffic flow model. It consists of a number of cars represented by points on a lattice with a random starting position, where each car may be one of two types: those that only move downwards (shown as blue in this article), and those that only move towards the right (shown as red in this article). The two types of cars take turns to move. During each turn, all the cars for the corresponding type advance by one step if they are not blocked by another car. It may be considered the two-dimensional analogue of the simpler Rule 184 model. It is possibly the simplest system exhibiting phase transitions and self-organization.^[1]

History

The Biham–Middleton–Levine traffic model was first formulated by Ofer Biham, A. Alan Middleton, and Dov Levine in 1992.^[2] Biham et al found that as the density of traffic increased, the steady-state flow of traffic suddenly went from smooth flow to a complete jam. In 2005, Raissa D'Souza found that for some traffic densities, there is an intermediate phase characterized by periodic arrangements of jams and smooth flow.^[3] In the same year, Angel, Holroyd and Martin were the first to rigorously prove that for densities close to one, the system will always jam.^[4] Later, in 2006, Tim Austin and Itai Benjamini found that for a square lattice of side N, the model will always self-organize to reach full speed if there are fewer than N/2 cars.^[5]

Lattice space

The fundamental polygon of the torus, on which the cars move

The cars are typically placed on a square lattice that is topologically equivalent to a torus: that is, cars that move off the right edge would reappear on the left edge; and cars that move off the bottom edge would reappear on the top edge.

There has also been research in rectangular lattices instead of square ones. For rectangles with coprime dimensions, the intermediate states are self-organized bands of jams and free-flow with detailed geometric structure, that repeat periodically in time.^[3] In non-coprime rectangles, the intermediate states are typically disordered rather than periodic.^[3]

Phase transitions

Despite the simplicity of the model, it has two highly distinguishable phases – the jammed phase, and the free-flowing phase.^[2] For low numbers of cars, the system will usually organize itself to achieve a smooth flow of traffic. In contrast, if there is a high number of cars, the system will become jammed to the extent that no single car will move. Typically, in a square lattice, the transition density is when there are around 32% as many cars as there are possible spaces in the lattice.^[6]

A free-flowing phase observed on a 144×89 rectangular lattice with a traffic density of 28%

A globally jammed phase observed on a 144×89 rectangular lattice with a traffic density of 60%

A 512×512 lattice with density of 27% after 64000 iterations. Traffic is at a free-flowing phase.

A 512×512 lattice with density of 29% after 64000 iterations. Traffic is at a free-flowing phase.

A 512×512 lattice with density of 38% after 64000 iterations. Traffic is at a globally jammed phase.

Mobility with respect to time for above lattice. Mobility is defined as the number of cars that can move as a fraction of the total. (The points are in the upper-left corner of the image.)

Mobility with respect to time for above lattice. Mobility is defined as the number of cars that can move as a fraction of the total. (The points are on the left side of the image.)

Intermediate phase

The intermediate phase occurs close to the transition density, combining features from both the jammed and free-flowing phases. There are principally two intermediate phases – disordered (which could be meta-stable) and periodic (which are provably stable).^[3] On rectangular lattices with coprime dimensions, only periodic orbits exist.^[3] In 2008 periodic intermediate phases were also observed in square lattices.^[7] Yet, on square lattices disordered intermediate phases are more frequently observed and tend to dominate densities close to the transition region.

A periodic intermediate phase observed on a 144×89 rectangular lattice with a traffic density of 38%

A disordered intermediate phase observed on a 144×89 rectangular lattice with a traffic density of 39%

A 512×512 lattice with density of 31% after 64000 iterations. Traffic is at a disordered intermediate phase.

A 512×512 lattice with density of 33% after 64000 iterations. Traffic is at a disordered intermediate phase.

A 512×512 lattice with density of 37% after 64000 iterations. Traffic is at a disordered intermediate phase.

Mobility with respect to time for above lattice. Mobility is defined as the number of cars that can move as a fraction of the total.

Rigorous analysis

Despite the simplicity of the model, rigorous analysis is very nontrivial.^[6] Nonetheless, there have been mathematical proofs regarding the Biham–Middleton–Levine traffic model. Proofs so far have been restricted to the extremes of traffic density. In 2005, Alexander Holroyd et al proved that for densities sufficiently close to one, the system will have no cars moving infinitely often.^[4] In 2006, Tim Austin and Itai Benjamini proved that the model will always reach the free-flowing phase if the number of cars is less than half the edge length for a square lattice.^[5]

Non-orientable surfaces

The model is typically studied on the orientable torus, but it is possible to implement the lattice on a Klein bottle.^[8] When the red cars reach the right edge, they reappear on the left edge except flipped vertically; the ones at the bottom are now at the top, and vice versa. More formally, for every $y\in \lbrace 0,\ldots ,N-1\rbrace$ , a red car exiting the site $(N-1,y)$ would enter the site $(0,N-y-1)$ . It is also possible to implement it on the real projective plane.^[8] In addition to flipping the red cars, the same is done for the blue cars: for every $x\in \lbrace 0,\ldots ,N-1\rbrace$ , a blue car exiting the site $(x,N-1)$ would enter the site $(N-x-1,0)$ .

The behaviour of the system on the Klein bottle is much more similar to the one on the torus than the one on the real projective plane.^[8] For the Klein bottle setup, the mobility as a function of density starts to decrease slightly sooner than in the torus case, although the behaviour is similar for densities greater than the critical point. The mobility on the real projective plane decreases more gradually for densities from zero to the critical point. In the real projective plane, local jams may form at the corners of the lattice even though the rest of the lattice is free-flowing.^[8]

Randomization

A randomized variant of the BML traffic model, called BML-R, was studied in 2010.^[9] Under periodic boundaries, instead of updating all cars of the same colour at once during each step, the randomized model performs $L^{2}$ updates (where $L$ is the side length of the presumably square lattice): each time, a random cell is selected and, if it contains a car, it is moved to the next cell if possible. In this case, the intermediate state observed in the usual BML traffic model does not exist, due to the non-deterministic nature of the randomized model; instead the transition from the jammed phase to the free flowing phase is sharp.

Under open boundary conditions, instead of having cars that drive off one edge wrapping around the other side, new cars are added on the left and top edges with probability $\alpha$ and removed from the right and bottom edges $\beta$ respectively. In this case, the number of cars in the system can change over time, and local jams can cause the lattice to appear very different from the usual model, such as having coexistence of jams and free-flowing areas; containing large empty spaces; or containing mostly cars of one type.^[9]

References

^ D'Souza, Raissa. "The Biham–Middleton–Levine traffic model". Retrieved 4 January 2015.
^ ^a ^b Biham, Ofer; Middleton, A. Alan; Levine, Dov (November 1992). "Self-organization and a dynamical transition in traffic-flow models". Phys. Rev. A. 46 (10). American Physical Society: R6124–R6127. arXiv:cond-mat/9206001. Bibcode:1992PhRvA..46.6124B. doi:10.1103/PhysRevA.46.R6124. ISSN 1050-2947. PMID 9907993. S2CID 14543020. Archived from the original on 2013-02-24. Retrieved 14 December 2012.
^ ^a ^b ^c ^d ^e D'Souza, Raissa M. (2005). "Coexisting phases and lattice dependence of a cellular automaton model for traffic flow". Phys. Rev. E. 71 (6). The American Physical Society: 066112. Bibcode:2005PhRvE..71f6112D. doi:10.1103/PhysRevE.71.066112. PMID 16089825. Archived from the original on 24 February 2013. Retrieved 14 December 2012.
^ ^a ^b Angel, Omer; Holroyd, Alexander E.; Martin, James B. (12 August 2005). "The Jammed Phase of the Biham–Middleton–Levine Traffic Model". Electronic Communications in Probability. 10: 167–178. arXiv:math/0504001. Bibcode:2005math......4001A. doi:10.1214/ECP.v10-1148. ISSN 1083-589X. S2CID 10913106. Archived from the original on 2016-03-04. Retrieved 14 December 2012.
^ ^a ^b Austin, Tim; Benjamini, Itai (2006). "For what number of cars must self organization occur in the Biham–Middleton–Levine traffic model from any possible starting configuration?". arXiv:math/0607759.
^ ^a ^b Holroyd, Alexander E. "The Biham–Middleton–Levine Traffic Model". Retrieved 14 December 2012.
^ Linesch, Nicholas J.; D'Souza, Raissa M. (15 October 2008). "Periodic states, local effects and coexistence in the BML traffic jam model". Physica A. 387 (24): 6170–6176. arXiv:0709.3604. Bibcode:2008PhyA..387.6170L. doi:10.1016/j.physa.2008.06.052. ISSN 0378-4371. S2CID 18321146.
^ ^a ^b ^c ^d Cámpora, Daniel; de La Torre, Jaime; García Vázquez, Juan Carlos; Caparrini, Fernando Sancho (August 2010). "BML model on non-orientable surfaces". Physica A. 389 (16): 3290–3298. Bibcode:2010PhyA..389.3290C. doi:10.1016/j.physa.2010.03.037. hdl:11441/107117.
^ ^a ^b Ding, Zhong-Jun; Jiang, Rui; Wang, Bing-Hong (2011). "Traffic flow in the Biham–Middleton–Levine model with random update rule". Physical Review E. 83 (4): 047101. Bibcode:2011PhRvE..83d7101D. doi:10.1103/PhysRevE.83.047101. PMID 21599339.

External links

CUDA implementation by Daniel Lu
WebGL implementation by Jason Davies
JavaScript implementation by Maciej Baron

[dsouzaweb-1] D'Souza, Raissa. "The Biham–Middleton–Levine traffic model". Retrieved 4 January 2015.

[bml-2] Biham, Ofer; Middleton, A. Alan; Levine, Dov (November 1992). "Self-organization and a dynamical transition in traffic-flow models". Phys. Rev. A. 46 (10). American Physical Society: R6124–R6127. arXiv:cond-mat/9206001. Bibcode:1992PhRvA..46.6124B. doi:10.1103/PhysRevA.46.R6124. ISSN 1050-2947. PMID 9907993. S2CID 14543020. Archived from the original on 2013-02-24. Retrieved 14 December 2012.

[dsouzaPRE-3] D'Souza, Raissa M. (2005). "Coexisting phases and lattice dependence of a cellular automaton model for traffic flow". Phys. Rev. E. 71 (6). The American Physical Society: 066112. Bibcode:2005PhRvE..71f6112D. doi:10.1103/PhysRevE.71.066112. PMID 16089825. Archived from the original on 24 February 2013. Retrieved 14 December 2012.

[angel-4] Angel, Omer; Holroyd, Alexander E.; Martin, James B. (12 August 2005). "The Jammed Phase of the Biham–Middleton–Levine Traffic Model". Electronic Communications in Probability. 10: 167–178. arXiv:math/0504001. Bibcode:2005math......4001A. doi:10.1214/ECP.v10-1148. ISSN 1083-589X. S2CID 10913106. Archived from the original on 2016-03-04. Retrieved 14 December 2012.

[austin-5] Austin, Tim; Benjamini, Itai (2006). "For what number of cars must self organization occur in the Biham–Middleton–Levine traffic model from any possible starting configuration?". arXiv:math/0607759.

[Holroydweb-6] Holroyd, Alexander E. "The Biham–Middleton–Levine Traffic Model". Retrieved 14 December 2012.

[linesch-7] Linesch, Nicholas J.; D'Souza, Raissa M. (15 October 2008). "Periodic states, local effects and coexistence in the BML traffic jam model". Physica A. 387 (24): 6170–6176. arXiv:0709.3604. Bibcode:2008PhyA..387.6170L. doi:10.1016/j.physa.2008.06.052. ISSN 0378-4371. S2CID 18321146.

[campora-8] Cámpora, Daniel; de La Torre, Jaime; García Vázquez, Juan Carlos; Caparrini, Fernando Sancho (August 2010). "BML model on non-orientable surfaces". Physica A. 389 (16): 3290–3298. Bibcode:2010PhyA..389.3290C. doi:10.1016/j.physa.2010.03.037. hdl:11441/107117.

[bmlr-9] Ding, Zhong-Jun; Jiang, Rui; Wang, Bing-Hong (2011). "Traffic flow in the Biham–Middleton–Levine model with random update rule". Physical Review E. 83 (4): 047101. Bibcode:2011PhRvE..83d7101D. doi:10.1103/PhysRevE.83.047101. PMID 21599339.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]