Biham-Middleton-Levine traffic model
Encyclopedia
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 move by one step if possible. 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
.
, A. Alan Middleton, and Dov Levine in 1992. 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. In the same year, Alexander Holroyd et al were the first to rigorously prove that for densities close to one, the system will always jam. 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.
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 top edge would reappear on the bottom edge.
There has also been research in rectangular lattices instead of square ones. For rectangles with coprime
dimensions, the periodic structures in the intermediate state are highly regular and ordered, whereas in non-coprime rectangles, the final state has a greater amount of disorder.
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.
dimensions, although in 2008 it was also observed in square lattices. Disordered intermediate phases, on the other hand, are more frequently observed and tend to dominate densities close to the transition region in square lattices.
s regarding the Biham-Middleton-Levine traffic model. Proofs so far have, however, been restricted to the extremes of traffic density. In 2005, Alexander Holroyd et al proved that for densities close to one, the system will always jam. 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.
It would be ideal, however, to formulate a rigorous method to predict the end result of any starting position, especially in the intermediate phases. To that end, this model has been the subject of research for several scientists.
Self-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
traffic flow model
Microscopic traffic flow model
Microscopic traffic flow models are a class of scientific models of vehicular traffic dynamics.In contrast to macroscopic models, microscopic traffic flow models simulate single vehicle-driver units, thus the dynamic variables of the models represent microscopic properties like the position and...
. 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 move by one step if possible. It may be considered the two-dimensional analogue of the simpler Rule 184
Rule 184
Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:...
model. It is possibly the simplest system exhibiting phase transitions and self-organization
Self-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
.
History
The Biham-Middleton-Levine traffic model was first formulated by Ofer BihamOfer Biham
Ofer Biham is a faculty member at the Racah Institute of Physics of the Hebrew University of Jerusalem in Israel. Biham received his Ph.D. for research on quasiperiodic systems at the Weizmann Institute of Science, under the supervision of Prof...
, A. Alan Middleton, and Dov Levine in 1992. 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. In the same year, Alexander Holroyd et al were the first to rigorously prove that for densities close to one, the system will always jam. 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.
Lattice space
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
equivalent to a torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
: that is, cars that move off the right edge would reappear on the left edge; and cars that move off the top edge would reappear on the bottom edge.
There has also been research in rectangular lattices instead of square ones. For rectangles with coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
dimensions, the periodic structures in the intermediate state are highly regular and ordered, whereas in non-coprime rectangles, the final state has a greater amount of disorder.
Phase transitions
Despite the simplicity of the model, it has two highly distinguishable phases — the jammed phase, and the free-flowing phase. For low numbers of cars, the system will usually organize itselfSelf-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
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.
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 and periodic. It was once thought that the periodic intermediate phase only exists in rectangular lattices with coprimeCoprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
dimensions, although in 2008 it was also observed in square lattices. Disordered intermediate phases, on the other hand, are more frequently observed and tend to dominate densities close to the transition region in square lattices.
Rigorous analysis
Despite the simplicity of the model, rigorous analysis is very nontrivial. There have, however, been mathematical proofMathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
s regarding the Biham-Middleton-Levine traffic model. Proofs so far have, however, been restricted to the extremes of traffic density. In 2005, Alexander Holroyd et al proved that for densities close to one, the system will always jam. 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.
It would be ideal, however, to formulate a rigorous method to predict the end result of any starting position, especially in the intermediate phases. To that end, this model has been the subject of research for several scientists.