# Phase Diagram Of The Biham-Middleton-Levine Traffic Model In Three Dimensions

## I Introduction

With the ever increasing computational power, simulating traffic in the microscopic level by means of cellular automaton becomes a real possibility. One of the simplest model for city traffic of this kind is the so-called Biham-Middleton-Levine (BML) traffic model .

The one-dimensional BML model is simply the elementary binary CA rule 184 operating on a one-dimensional lattice with periodic boundary condition. The asymptotic car speed $`v`$ in this one-dimensional model is exactly known, and is given by

$$v=\{\begin{array}{cc}1\hfill & \text{if }\rho 1/2,\hfill \\ \frac{1}{\rho }1\hfill & \text{if }1/2<\rho 1,\hfill \end{array}$$
(1)   
where $`\rho `$ is the car density in the system . In other words, in the one dimensional BML model, traffic jam occurs only when the car density $`\rho `$ is equal to $`1\rho _c^{(1)}`$ and all cars move in full speed whenever $`\rho 1/2`$.

The two-dimensional BML model considers the motions of north- and east-bound cars in a two-dimensional square lattice with periodic boundary conditions in both the north-south and east-west directions. (We shall give the exact rules for the two-dimensional BML model in Section II.) Although we lack an exact analytical expression for the average asymptotic car speed $`v`$ as a function of car density $`\rho `$ in the two-dimensional BML model, extensive numerical simulations  as well as mean field theory studies  have been carried out. Their results strongly suggest a fluctuation-induced first order phase transition in $`v`$. Moreover, the average asymptotic car speed is likely to follow

$$v=\{\begin{array}{cc}1\hfill & \text{for }0\rho <\rho _c^{(2)},\hfill \\ 0\hfill & \text{for }\rho >\rho _c^{(2)},\hfill \end{array}$$
(2)   
where the critical density $`\rho _c^{(2)}`$ is numerically found to be about 0.31  and is analytically proven to be less than 1/2 . In addition, Tadaki and Kikuchi found a more subtle phase transition related to the final jamming pattern. Their numerical study showed that jamming patterns for car density $`\rho `$ less than about 0.52 are very well self-organized. On the other hand, when $`\rho `$ is greater than 0.52, the jamming patterns are random .

Extension of the BML model to higher dimensions can be regarded as a highly simplified model for computer network communication in a hypercube. And from the physics point of view, it is natural to investigate the phase diagram as well as the upper critical dimension of the BML model in higher dimensions. As a pioneer study, we report the result of an extensive numerical study of the BML model in three dimensions in this paper. We find that the three dimensional model has a richer phase diagram than that in one and two dimensions. In addition to the fluctuation-induced first order phase transition in $`v`$, we also observe a low (but non-zero) speed phase.

To begin, we first introduce the higher dimensional generalization of the BML model in section II. Then, we report our simulation results in section III and present our analysis of results in section IV. Finally, we draw our conclusions in section V.

## II The BML Model

Let us introduce the modified BML model in $`n`$-dimensions below. Consider an $`n`$-dimensional $`N_1\times N_2\times \mathrm{}\times N_n`$ square lattice with periodic boundary conditions. Each lattice site will either contain no car (that is, an empty site) or contain exactly one car moving in the $`\widehat{e}_i`$ direction. We denote $`\rho _i`$ the density of cars moving along $`\widehat{e}_i`$. (That is, $`\rho _i`$ equals the number of cars moving along the $`\widehat{e}_i`$ direction divided by the total number of cars in the system.) We denote the total car density of the system by $`\rho \rho _i`$ and we define the car density vector by $`\stackrel{}{\rho }(\rho _1,\rho _2,\mathrm{},\rho _n)`$. Initially, cars are placed randomly and independently onto the $`n`$-dimensional square lattice according to a pre-determined car density vector $`\stackrel{}{\rho }`$.

The dynamics of the cars are governed by the following rules. Each $`\widehat{e}_1`$-moving car advances one site along the $`\widehat{e}_1`$ direction provided that no car blocks its way. Otherwise, that $`\widehat{e}_1`$-moving car stays in its present location. Parallel update is taken for all $`\widehat{e}_1`$-moving cars. After this, each $`\widehat{e}_2`$-moving car advances one site along the $`\widehat{e}_2`$ direction if no car blocks its way. Otherwise, that $`\widehat{e}_2`$-moving car stays in its present location. Again, parallel updating is used. This process goes on until each $`\widehat{e}_n`$-moving car is given a chance to move. This marks the end of one timestep and the above car moving process is repeated over and over again.

At each timestep, the car speed is defined as the ratio of number of cars moved to the total number of cars in the lattice system. And the average asymptotic car speed $`v`$ is defined as the car speed averaged over both the cycle time and initial car configurations. Since we are interested in the behavior of the system in thermodynamic limit, so we only consider the limit when $`N_1,N_2,\mathrm{},N_n`$ all tend to infinity while keeping the aspect ratio between each side fixed.

We define the $`n`$-dimensional BML traffic model to be the one with aspect ratio between each of the $`n`$ sides being fixed to one. That is to say, $`N_1=N_2=\mathrm{}=N_n`$. Also, an $`n`$-dimensional BML traffic model is called homogeneous if and only if $`\rho _i=\rho _j`$ for all $`i,j`$ . In this paper, we concentrate on the homogeneous three-dimensional BML traffic model. So for simplicity, we shall simply call it the three-dimensional BML model whenever confusion is not possible. From this definition, it is clear that the average asymptotic car speed $`v`$ is a function of $`\stackrel{}{\rho }`$ only and its value lies between zero and one.

## III Simulation Results Of The Three-Dimensional BML Model

Our simulation is performed on a variety of machines including clusters of Sun Sparc and Dec Alpha workstations, various Pentium-based PCs and Power PCs as well as the SP2 supercomputer. The estimated total CPU time is about 300 mips years. Even so, owing to our CPU time limitations, we can only systematically simulate up to a lattice size of $`100\times 100\times 100`$. Nonetheless, we have also simulated for the cases of very small and very large car densities up to a lattice size of $`1000\times 1000\times 1000`$ before finally drawing our conclusions.

Fig. 1 shows the $`\rho `$ vs. $`v`$ curve for the BML model in a $`100\times 100\times 100`$ lattice. Each data point in the figure represents the average asymptotic car speed over an ensemble of random initial configurations. For $`\rho <0.1`$ as well as $`\rho >0.22`$, the value of $`v`$ is obtained by averaging over $`1000`$ initial configurations. In contrast, $`v`$ for $`0.1\rho 0.22`$ is obtained by averaging over only $`50`$ random initial configuration because the long relaxation time prevents us from obtaining more samples. Fig. 1 tells us that $`v=1`$ when the car density $`\rho 0.0051/2N`$. We call this region the “full speed phase”. Moreover, recurrent states in the car density region are cycles of period $`100=N`$. (The dependence of various parameters on $`N`$ here and hereafter are based on our simulation results in various lattice sizes up to $`1000\times 1000\times 1000`$, including various odd, even and prime values of $`N`$.) As $`\rho `$ increases to about $`0.011/N`$, $`v`$ begins to drop. The recurrent states form cycles with periods several ten times the linear lattice size $`N`$. As the car density $`\rho `$ reaches about $`0.022/N`$, $`v`$ drops to the value $`N/(N+1)=100/1010.99099`$ and stays constant until $`\rho `$ reaches about $`0.10`$. In this car density region, recurrent states form cycles of period $`101=N+1`$. In other words, in the recurrent state, each car in the system will be blocked exactly once in each cycle. For the $`100\times 100\times 100`$ lattice, $`v`$ is slightly greater than $`N/(N+1)`$ as $`0.10\rho 0.17`$. A similar but much smaller bump in $`v`$ is also observed in the $`200\times 200\times 200`$ lattice. Hence, we conclude that the bump is due to finite size effect of the lattice. Typical recurrent states in this car density region are cycles of period $`100N`$. Moreover, the typical relaxation time for a random configuration in this range of car density appears to scale exponentially with $`N`$. In fact, the long relaxation time forbids us from performing systematic simulation with lattice size greater than $`100\times 100\times 100`$. Clearly, the exponentially long relaxation time signals a critical slow-down.

As the car density reaches about $`\rho _{c_1}^{(3)}=0.18\pm 0.01`$, $`v`$ drops abruptly to about $`0.015`$. Since the asymptotic car speeds in all our simulation data are either greater than or equal to $`N/(N+1)`$ or less than $`0.03`$, we strongly believe that the observed sudden drop in $`v`$ is a result of a first order phase transition. Interestingly, the periods of the recurrent configurations of all these low but non-zero speed states are equal to $`N`$. When we further increase the car density $`\rho `$, $`v`$ gradually decreases until it finally reaches zero at $`\rho _{c_2}^{(3)}=0.32\pm 0.02`$.

In summary, our simulation tells us that for a finite $`N\times N\times N`$ lattice, the system exhibits a non-trivial “high speed region” with $`v=N/(N+1)`$ as well as a non-trivial “low speed region” with $`v0.03`$. Thus, in the thermodynamic limit, the three-dimensional BML model has a full speed phase, a low speed phase and a completely jammed phase. (Moreover, just like the two-dimensional case, the completely jammed phase may further be divided into the self-organized jamming and the random jamming regions.) The transition from the full speed to the low speed phase is first order in nature and the transition from the low speed phase to the completely jammed phase is smooth. That is to say, this transition is at least second order.

## IV Analysis Of Our Simulation Results

### A The Full Speed Phase

In addition to the systematic trend that the critical car density from the high to low speed phase strictly decreases with spatial dimension, we observe an interesting feature in the high speed phase of the three-dimensional BML model. Unlike the one- and two-dimensional models, the recurrent configurations for any finite $`N\times N\times N`$ lattice in the high speed region with $`\rho 1/N`$ form cycles of period $`N+1`$. A typical high speed recurrent configuration in a $`5\times 5\times 5`$ lattice is shown in Fig. 2 as an illustration. Readers may verify that cars in these high speed configurations will be blocked once per cycle period . Unfortunately, we do not have a good explanation why this $`v=N/(N+1)`$ recurrent state is preferred over the $`v=1`$ recurrent state in three dimensions.

### B The Transition To Low Speed Phase

Since we cannot find any intermediate speed asymptotic configurations in our simulation, the transition from the high to low speed phase is likely to be first order. To further investigate to the nature of this transition, we drive the system by slowly adding cars to or removing cars from the system. That is to say, starting from $`\rho =0`$, we increase the car density by a fixed small amount $`\mathrm{\Delta }\rho `$ by randomly introducing cars to the empty sites in the system. And then, we evolve the system until it relaxes to a recurrent state. We repeat the process until $`\rho `$ reaches one. After this, we decrease the car density of the system by $`\mathrm{\Delta }\rho `$ by randomly removing cars from the system. And then, we evolve the system until it reaches a recurrent state. We repeat this process until $`\rho `$ becomes zero. The $`\rho `$ vs. $`v`$ graph obtained in this way on a $`100\times 100\times 100`$ lattice with $`\mathrm{\Delta }\rho =0.001`$ is shown in Fig. 3. Clearly, as we slowly increase the car density $`\rho `$, transition to the low speed phase occurs at car density around $`0.22`$, which is slightly higher than the critical car density $`\rho _{c_1}^{(3)}0.18`$. More dramatically, as we slowly decrease the car density, transition to the high speed phase occurs at car density around $`0.07`$, which is much smaller than the critical car density $`\rho _{c_1}^{(3)}`$. The observed hysteresis loop confirms the hypothesis that this is a first order phase transition. And since the only nonlinearity in the model comes from the exclusion volume effect, we conclude that the phase transition is fluctuation induced.

### C The Low Speed Phase And The Completely Jamming Phase

Unlike its one- and two-dimensional counterparts, the three-dimensional BML model has a low speed phase with $`0<v0.03`$. Similar to the completely jamming configurations, we find that the recurrent configurations in the low speed phase contain (directed) percolating clusters of cars. But unlike the completely jamming configurations, we found a small number of residual freely moving cars in the low speed phase. Hence, the period of these recurrent states equals the linear system size $`N`$. And since most cars are already jammed by colliding into the percolating cluster, the average asymptotic car speed is low. A typical low speed recurrent configuration in a $`5\times 5\times 5`$ lattice is shown in Fig. 4 as an illustration .

Recall that a percolating backbone is essentially an one-dimensional object. Therefore, if the background lattice is one- or two-dimensional, all other moving cars will eventually merge into the percolating backbone leading to a completely jamming configuration. The situation is completely different when the background lattice is at least three-dimensional. In this case, since both the trajectories of moving cars and the percolating backbone are essentially one-dimensional objects, trajectories of some moving cars may not intersect with the percolating cluster. Thus, if the car density is small enough, some residual freely moving cars may present in a recurrent configuration giving rise to the observed low speed phase.

As the car density gradually increases in the low speed phase, the size of the percolating cluster in the recurrent configuration increases. It becomes more and more difficult for the system to accommodate residual freely moving cars. Hence, $`v`$ gradually decreases until it eventually reaches zero. The transition from the low speed phase to the completely jamming phase is, therefore, smooth.

## V Conclusions And Outlook

In summary, we study the phase diagram of the three-dimensional BML model. Similar to the two-dimensional model, a fluctuation-induced first order phase transition in asymptotic average car density $`v`$ is observed at car density $`\rho _{c_1}^{(3)}=0.18\pm 0.01`$. We also discover a new low speed phase which is absent in one- and two-dimensional models. We argue that the existence of this low speed phase is geometrical in nature, and hence this phase will exist in higher dimensional BML models as well. It is instructive to numerically verify our claims in the four-dimensional model. Unfortunately, the amount of computation involved will probably be too high for us at this moment. Finally, our simulation suggests that the transition from the low speed phase to the completely jamming phase is smooth and occurs at car density $`\rho _{c_2}^{(3)}=0.32\pm 0.02`$.

A number of open questions remain. For instance, we do not understand why the $`v=N/(N+1)`$ high speed states are preferred over the $`v=1`$ full speed states in the three-dimensional model. And it is meaningful to investigate if this behavior persists in higher dimensions.

###### Acknowledgements.

We would like to thank P. M. Hui, K.-t. Leung, L. W. Siu and K. K. Yan for their useful comments.