Biham-Middleton-Levine traffic model

An applet of a cellular automaton

Abstract

The Biham-Middleton-Levin model is a simple system to simulate traffic within a city. It consists of two types of agents (called cars) that can either move down (red) or right (blue). The traffic is controlled by traffic lights, so that in each time step only one type can move. The agent will not move, if it is blocked by an agent of different type or by an agent of the same type which is blocked itself. The system underlies periodic boundary conditions and the characteristics of the system is mainly determined by the density of agents and the random initial conditions. For a low density one will find a free flowing phase (e.g. system size $100$, density $20\%$), where no agent is blocked. For larger densities, a blocked phase (e.g. system size $100$, density $40\%$) is created, so that every agent is blocked. These phases can be observed after a transient period, which is determined by the system size, density and other parameters.

Simulation

Usage of the Applet

In the above applet there are two graphic window, the left one showing the simulation of the agents' movements, the right one depicting the percentage of performed movements per type. For the simulation of the Biham-Middleton-Levine model you can change a few parameters in the applet. The usage of the applet should be intuitively. Just try to run the simulation and change some values.

Theory

(a) flowing phase system (e.g. system size $100$, density $20\%$)

(b) flowing phase statistics

(c) blocked phase system (e.g. system size $100$, density $40\%$)

(d) blocked phase statistics

With this simulation the authors present three state cellular automaton based on the BML model of Biham, Middleton, and Levine [2]. Cellular automata are a well studied realm in the fields of dynamical systems, and they are often used to simulate traffic. This type of model is much easier and faster to implement than hydrodynamical traffic models. In this section we want to give the theoretical background of the above shown BML model (Field Mode) and describe our extension to the model (Crossing Mode).

BML Model

The set up for the BML model is a $N\times N$ square lattice of which each node can be either occupied by one agent or is empty. There are two different types of agents characterized by the direction of their movement, which can be seen as cars in the streets of a city. Here one type can move only to the right (blue), the other only moves down (red). The initial configuration of agents on the lattice is a random distribution with an total initial agent density $p$ (ratio of number of all agents with the number of available nodes on the lattice), the probability to find an agent of special type is therefore $p/2$.

(e) phase transition (from [2])

The system is constrained to periodic boundary conditions, which forces agents that leave the square on one edge will enter is again on the opposite site. Topologically this makes the square euqivalent to a torus. As described in their paper the dynamics of the system is controlled by traffic lights, so that a single time step only one type of agents will move. The update happens synchronously for all agents of a type. The movement of an agent follows the rule:
  • If the node infront (in the direction of movement) is empty, it will go there.
  • If the node infront is occupied by an agent of the other type, the agent is blocked.
  • If the node infront is occupied by an agent of the same type, the agent will move if the infront agent moves.
In the original system proposed in [2] the speed of the agents is limited to one mode per timestep ($v_1=v_2=1$). In the dynamical behaviour Biham et al. find to different asymptotic states. After a transient period which depends on the initial configuraiton and the system size $N$, the agents are either all moving infinitely long without being blocked (flowing phase) or the agents -- all or only a fraction -- is blocked for ever. In Fig. (a) the system is in the free flowing phase and in the corresponding diagramm in Fig. (b) one can see that after a short time all agents are moving. The blocked phase is depicted in Fig. (c) where the typical diagonal structure can be found. There the different types of agents block another and the diagramm Fig. (d) shows that the number of moving agents goes down to zero.

(f) statistics of an unstable intermediate phase going to a locked phase (e.g. system size $100$, density $30\%$)

In their publication Biham et al. measure the average ensemble velocity after the transient period to describe the system's state. They find that the average velocity depends on the initial density $p$ of agents and that a more or less sharp transition between flowing phase and fully blocked phase can be found. In Fig. (e) this transition is shown for different system sizes. The system state in which only a constant fraction of agents can move is called intermediate phase, and one can clearly see that this intermediate state vanishes for large system size. (Previous investigations have shown that a stable periodic intermediate state can hardly exist on a square lattice. This is more often to be found on a (non-square) rectangular lattice. On a square lattice unstable intermediate state occur close to the critical density, but they always end up in a blocked phase.)
So the transition between the two extreme states becomes very sharp and the critical density $p_c(N)$ where the transition happens, depends on the system size.
In the original publication the authors compare this second order transition to a percolation transition known from network theory. Up to the very day there is no rigorous analysis of this system except for some special cases of very high density.

Extended Pedestrian Model

This mode was introduced by the authors of this applet and is an extension to the original BML model. The main difference is that the system no longer has periodic boundary conditions but open boundaries. The system starts as before with a random initial distribution of agents of density $p_i$ (both types equally often represented) but whenever an agent leaves the field it is gone. On the entrance edge of each agent type, new agents are created randomly with certain probability $p_n$. To give the system the shape of a pedestrian crossing, some areas (black squares) are forbidden areas for the agents. In this way one can simulate the flow of pedestrians on a crossing when showing the behaviour of the BML model. As the boundaries are no more periodic, there won't be any jams, i.e. the fully blocking phase vanishes.

Code & Documentation

To understand the applet and the way it simulates the given model, the authors share the produced code and a detailled documentation on this.

Available Features

Acknowledgement, Authors & Contact

Acknowledgement The authors would like to thank the members of the group Prof. C. Gros for the great help when developing this applet. Especially we thank Prof. C. Gros, Rodrigo Echeveste and Bulcsú Sándor for discussing the model, giving good advice for its visualisation and helping to remove all kinds of technical problems.

About the authors Samuel Eckmann is a Bachelor's student in the group of Prof. C. Gros at Goethe University Frankfurt (Main).
Hendrik Wernecke is a Master's student in the group of Prof. C. Gros at Goethe University Frankfurt (Main). He did his Bachelor studies at Ulm University (2010-2013).

Contact For questions, suggestions or comments on this simulation, please contact wernecke@itp.uni-frankfurt.de.
Samuel Eckmann
Hendrik Wernecke

References & Further Reading

[1]
Wikipedia article Biham-Middelton-Levine traffic model
[2]
O. Biham, A. Middleton, and D. Levine: Self-organization and a dynamical transition in traffic-flow models, Phys. Rev. A 46, R6124(R), November 1992.
[3]
C. Gros: Complex and Adaptive Dynamical System - A Primer, Springer-Verlag, 2011.
[4]
J. Xie et al: Dynamical traffic light strategy in the Biham-Middleton-Levine model., Physical Review E 87.2 (2013): 022812.
[5]
Z. Ding, Xiao-Yan Sun, and B. Wang: Violating traffic light behavior in the Biham-Middleton-Levine traffic flow model, Procedia engineering 31 (2012): 1072-1076.
[6]
W. Huang et al.: Effect of Car Length in the Biham-Middleton-Levine Traffic Model, Future control and automation. Springer Berlin Heidelberg, 2012. 479-487.
[7]
Z. Ding, et al.: Effect of overpasses in the Biham-Middleton-Levine traffic flow model with random and parallel update rule, Physical Review E 88.2 (2013): 022809.

Legal note: We do not take any responsibility for
the content of the webPages linked here-in.