# Reversible Transitions in a Cellular Automata-Based Traffic Model with Driver Memory

Authors: Tomoko Sakiyama; Ikuo Arizono
Journal: Complexity
 (2019)

---

## Abstract

Here, we develop a new cellular automata-based traffic model. In this model, individual vehicles cannot estimate global traffic flows but can only detect the vehicle ahead. Each vehicle occasionally adjusts its velocity based on the distance to the vehicle in front. Our model generates reversible phase transitions in the vehicle flux over a wide range of vehicle densities, and the traffic system undergoes scale-free evolution with respect to the flux. We thus believe that our model reveals the relationship between the macro-level flows and micro-level mechanisms of multi-agent systems for handling traffic congestion, and illustrates how drivers’ decisions impact free and congested flows.


---

## Body

## 1. Introduction

Traffic jam theory is a well-studied type of collective behavior problem. In traffic systems, all the vehicles or cars interact with each other, making decisions using simple rules based on local information. Despite the simplicity of both the information and rules used for decision-making, complex traffic flows can occur that mix congested and free flow situations.Many models have been used in traffic jam theory studies [1–5]. In particular, microscopic cellular automata (CA) models are widely used in computer simulations due to their simplicity and flexibility. CA models are able to capture micro-level dynamics and illustrate their relationships to macro-level traffic flows. Nagel and his colleagues pioneered the use of CAs for traffic flow modeling [4]. Their models, called NS models, have since been extended by several others [6].It seems, however, that the system’s initial conditions determine the model’s dynamics; for example, traffic jams appear to occur when the vehicle density exceeds a certain value, indicating that they are generated by bottlenecks. By contrast, real traffic systems can experience congested flow situations without bottlenecks [7, 8]. Furthermore, based on empirical studies, Kerner classified congested flows into two different phases: synchronized flows and wide moving jams [9]. In this three-phase theory, phase transitions occur from free flows to synchronized flows and from synchronized flows to jams. Classical two-phase CA models may not be able to explain these empirical results.From the above, the most notable phenomena seen in traffic systems are phase transitions in the traffic state. Consequently, it is essential to model the time evolution of system transitions from one phase to another if we are to understand the complex behaviors of real traffic [10, 11]. In order to understand the mechanism by which traffic jams occur, we need to establish models that can reproduce phase transitions at fixed vehicle densities [12–15]. Such models will hopefully capture realistic and complex traffic patterns similar to those observed in real traffic systems. They deal with the effects of inertia in driving operations and the way drivers adaptively adjust their vehicles’ speed and spacing.Previous models simply aimed to capture vehicle physics or drivers’ passive responses to brake lights, such as the slow-start or braking propagation effects [16–20]. By contrast, these more recent models are based on the idea that vehicles autonomously coordinate their velocities by accelerating or decelerating, enabling them to simulate the spatiotemporal patterns and phase transitions seen in traffic flows [14, 15, 21–23]. Although there have been several competing approaches, coordinating vehicle velocities in response to the traffic spacing appears to be an important factor in representing phase transitions and reversible/complex traffic patterns [23–25]. However, few studies have investigated whether individual drivers use prior information to determine their chosen vehicle velocity and tendency to accelerate or decelerate.To address this question, we propose a new CA model in which the vehicles coordinate their responses to the current situation based on their prior experiences. In our model, each driver judges whether the nearby traffic congestion is a global or local congested flow and then responds based on information about prior events. Thus, each vehicle makes its own decision about whether to maintain or reduce the distance to the car in front. With this model, we successfully induce the system to exhibit reversible traffic flows and produce complex patterns by scale-free evolution.


## 2. Materials and Methods

Our model is defined as a one-dimensional field ofL sites with periodic boundary conditions, and each site is either empty or occupied by one vehicle. Each vehicle has a velocity between zero and the maximum velocity vmax. Unless stated otherwise, each trial involves 10,000 time steps, and the vehicles initially have velocities of 1.0 and are distributed randomly.Our model follows the NS model, in that it is a CA traffic model that deals with natural vehicle motion with a set maximum velocity. However, we also define three different vehicle states: a “normal” state, in which the vehicle increases speed in the same manner as in the NS model; a “calm” state, in which the vehicle never increases its speed; and a “harsh” state, in which the vehicle increases speed sharply. In this way, each state’s acceleration behavior is different. Note that all three states also have a “deceleration” function that applies when the vehicle is too close to the car in front. This model, which we call the multi-state NS model, does not consider collisions or vehicles passing each other. Each trial begins with all vehicles in a normal state.


### 2.1. Model Description

In the multi-state NS model, each iteration proceeds as follows.Step 1. Change state.Step 2. Accelerate or decelerate.Step 3. Randomize velocity.Step 4. Limit current velocity.Step 5: Update position, increment time from t to t+1, and return to Step 1.Note that a given vehicle cannot both accelerate and decelerate during the same iteration, and that all vehicles update their positions synchronously.


### 2.2. Model Functions

Accelerate.
Vehiclek updates its velocity vk as follows.
ifvk<vmaxanddnearestk>vk+1,
N
accel
k
→
N
accel
k
+
1, (regardless of the current state).
ifstatek=normal,
v
k
→
v
k
+
1
,
else ifstatek=harsh,
ifdnearestk>vk+2,
v
k
→
v
k
+
2
,
elsevk→vk,
else ifstatek=calm,
v
k
→
v
k
.
Here,dnearestk is the distance to the nearest vehicle in front of vehicle k and Naccelk is the number of times that vehicle k has accelerated.
We call the first two acceleration operations “normal acceleration” and “harsh acceleration,” respectively. The former corresponds to the usual NS model, while “harsh acceleration” only occurs if the vehicle is in a harsh state and the next vehicle is sufficiently far ahead. Finally, the velocityv never changes if the vehicle is in a calm state.Decelerate.
This function occurs if the following conditions are satisfied, regardless of the vehicle state.
ifdnearestk≦vkanddnearestk−1≧0,
v
k
→
d
nearest
k
−
1
,
N
slow
k
→
N
slow
k
+
1
.
Here,Nslowk is the number of times that vehicle k has decelerated.Randomize Velocity.
This function occurs if the following conditions are satisfied, regardless of the vehicle state.
ifvk>0,
v
k
→
v
k
−
1
with probability
p
.Limit Current Velocity.
If the updated velocityvk is above vmax, then it is reduced to vmax.
ifvk>vmax,
v
k
→
v
max
.Change State.
If the number of decelerationsNslowk has reached the threshold (threshold_slow), then the vehicle enters a calm state, regardless of its previous state. By contrast, if the number of accelerations Naccelk has reached the threshold (threshold_acceleration), then the vehicle enters a harsh state, regardless of its previous state. These changes are implemented as follows.
ifNslowk>threshold_slow,
s
t
a
t
e
k
→
c
a
l
m
,
N
slow
k
→
0
,
N
accel
k
→
0
.
ifNaccelk>threshold_acceleration,
s
t
a
t
e
k
→
h
a
r
s
h
,
N
slow
k
→
0
,
N
accel
k
→
0
.
Note here that bothNslowk and Naccelk are reset to zero when either of them exceeds the corresponding threshold, meaning that some vehicles may stay in harsh or calm states for long periods. Individual vehicles make subjective estimates of the global traffic flow based on how often they have accelerated or decelerated. When a vehicle enters a calm state, this implies that it believes the global flow to be congested. On the other hand, when it enters a harsh state, this implies that it believes the global flow not to be congested. In this way, individual vehicles coordinate their velocities based on the distance to the vehicle in front.Update Position.
Vehiclek updates its position xk based on its speed vk at the current time step.(1)xk→xk+vk.


### 2.3. Control Models

In order to investigate whether the multi-state NS model can generate complex patterns similar to those of real traffic, we developed two control models. One is the “harsh model,” in which vehicles never enter calm states, i.e.,threshold_slow is set to positive infinity. The other is the “calm model,” in which the vehicles never enter harsh states, i.e., threshold_acceleration is set to positive infinity. In both models, each vehicle’s state becomes fixed after it first enters a harsh/calm state.Then, we compared the results from our multi-stage NS model with those from the calm and harsh models in order to evaluate whether it was capable of generating complex patterns similar to those seen in real traffic situations.


### 2.4. Parameters

Table1 shows the parameter values used in the analysis. Unless otherwise noted, the trials involved 10,000 time steps. However, we ran certain analyses over 100,000 steps in order to evaluate the system’s long-term behavior. For all three models, all vehicles were initially in normal states.Table 1
Parameters used in the analyses.
Parameter
Value
Description
L
500
Field size
Time_length
10,000
Number of time steps per trial
p
0.01
Randomization probability
v
max
5
Maximum vehicle velocity
Threshold_slow
5
Number of previous decelerations required for a vehicle to judge the traffic flow to be congested
Threshold_acceleration
15
Number of previous accelerations required for a vehicle to judge the traffic to be free-flowing


## 2.1. Model Description

In the multi-state NS model, each iteration proceeds as follows.Step 1. Change state.Step 2. Accelerate or decelerate.Step 3. Randomize velocity.Step 4. Limit current velocity.Step 5: Update position, increment time from t to t+1, and return to Step 1.Note that a given vehicle cannot both accelerate and decelerate during the same iteration, and that all vehicles update their positions synchronously.


## 2.2. Model Functions

Accelerate.
Vehiclek updates its velocity vk as follows.
ifvk<vmaxanddnearestk>vk+1,
N
accel
k
→
N
accel
k
+
1, (regardless of the current state).
ifstatek=normal,
v
k
→
v
k
+
1
,
else ifstatek=harsh,
ifdnearestk>vk+2,
v
k
→
v
k
+
2
,
elsevk→vk,
else ifstatek=calm,
v
k
→
v
k
.
Here,dnearestk is the distance to the nearest vehicle in front of vehicle k and Naccelk is the number of times that vehicle k has accelerated.
We call the first two acceleration operations “normal acceleration” and “harsh acceleration,” respectively. The former corresponds to the usual NS model, while “harsh acceleration” only occurs if the vehicle is in a harsh state and the next vehicle is sufficiently far ahead. Finally, the velocityv never changes if the vehicle is in a calm state.Decelerate.
This function occurs if the following conditions are satisfied, regardless of the vehicle state.
ifdnearestk≦vkanddnearestk−1≧0,
v
k
→
d
nearest
k
−
1
,
N
slow
k
→
N
slow
k
+
1
.
Here,Nslowk is the number of times that vehicle k has decelerated.Randomize Velocity.
This function occurs if the following conditions are satisfied, regardless of the vehicle state.
ifvk>0,
v
k
→
v
k
−
1
with probability
p
.Limit Current Velocity.
If the updated velocityvk is above vmax, then it is reduced to vmax.
ifvk>vmax,
v
k
→
v
max
.Change State.
If the number of decelerationsNslowk has reached the threshold (threshold_slow), then the vehicle enters a calm state, regardless of its previous state. By contrast, if the number of accelerations Naccelk has reached the threshold (threshold_acceleration), then the vehicle enters a harsh state, regardless of its previous state. These changes are implemented as follows.
ifNslowk>threshold_slow,
s
t
a
t
e
k
→
c
a
l
m
,
N
slow
k
→
0
,
N
accel
k
→
0
.
ifNaccelk>threshold_acceleration,
s
t
a
t
e
k
→
h
a
r
s
h
,
N
slow
k
→
0
,
N
accel
k
→
0
.
Note here that bothNslowk and Naccelk are reset to zero when either of them exceeds the corresponding threshold, meaning that some vehicles may stay in harsh or calm states for long periods. Individual vehicles make subjective estimates of the global traffic flow based on how often they have accelerated or decelerated. When a vehicle enters a calm state, this implies that it believes the global flow to be congested. On the other hand, when it enters a harsh state, this implies that it believes the global flow not to be congested. In this way, individual vehicles coordinate their velocities based on the distance to the vehicle in front.Update Position.
Vehiclek updates its position xk based on its speed vk at the current time step.(1)xk→xk+vk.


## 2.3. Control Models

In order to investigate whether the multi-state NS model can generate complex patterns similar to those of real traffic, we developed two control models. One is the “harsh model,” in which vehicles never enter calm states, i.e.,threshold_slow is set to positive infinity. The other is the “calm model,” in which the vehicles never enter harsh states, i.e., threshold_acceleration is set to positive infinity. In both models, each vehicle’s state becomes fixed after it first enters a harsh/calm state.Then, we compared the results from our multi-stage NS model with those from the calm and harsh models in order to evaluate whether it was capable of generating complex patterns similar to those seen in real traffic situations.


## 2.4. Parameters

Table1 shows the parameter values used in the analysis. Unless otherwise noted, the trials involved 10,000 time steps. However, we ran certain analyses over 100,000 steps in order to evaluate the system’s long-term behavior. For all three models, all vehicles were initially in normal states.Table 1
Parameters used in the analyses.
Parameter
Value
Description
L
500
Field size
Time_length
10,000
Number of time steps per trial
p
0.01
Randomization probability
v
max
5
Maximum vehicle velocity
Threshold_slow
5
Number of previous decelerations required for a vehicle to judge the traffic flow to be congested
Threshold_acceleration
15
Number of previous accelerations required for a vehicle to judge the traffic to be free-flowing


## 3. Results and Discussion

At the beginning of each trial, we randomly placed (number of cells × vehicle density) vehicles on the field. Figure1 illustrates the relationship between flux and vehicle density, where flux is defined as the average number of vehicles passing through each cell per unit time. We calculated the flux after each trial. When the vehicle velocities are high, the flux is also high because many vehicles pass through any given cell.Figure 1
Relationship between flux and vehicle density. (a) Mean flux for the multi-state NS model withp=0.01vmax=5, threshold_slow = 5, and threshold_acceleration = 15. The vertical bars indicate the standard deviation. (b) Fluxes from all trials for the multi-state NS model. (c) Fluxes from all trials for the calm model with p=0.01vmax=5, and threshold_slow = 5. (d) Fluxes from all trials for the harsh model with p=0.01vmax=5, and threshold_acceleration = 15.
(a)
(b)
(c)
(d)Figure1(a) plots average data from 10 trials for vehicle densities of up to 0.50 in the multi-state NS model, with a bin width of 0.01. Here, the flux appears to fluctuate for each trial even at high vehicle densities. In fact, according to Figure 1(b), which plots the fluxes for individual trials at different vehicle densities, the flux varies even with the same vehicle densities. By contrast, Figures 1(c) and 1(d), which plot the fluxes for individual trials at different vehicle densities for the calm and harsh models, respectively, appear to show fewer dots than we see in Figure 1(b). This is because the flux does not change with every trial in the calm and harsh models, unlike in the multi-state NS model. In addition, we see traffic jams in the calm model over a wide range of vehicle densities, perhaps because it does not allow for acceleration. Meanwhile, the traffic pattern in the harsh model exhibits a phase transition at a vehicle density of approximately 0.20. Please also see Figure S1 in the Supplementary Material, which illustrates the vehicle positions over time for different vehicle densities under the harsh model.Despite the fact that the system seems to gradually become more congested under the harsh model as the vehicle density increases beyond 0.20, traffic jams never occur. Therefore, the model is not realistic because it does not allow vehicles to enter calm states. Vehicles do not maintain their velocities, instead repeatedly accelerating and decelerating. In this sense, the multi-state NS model is better able to exhibit the complex patterns seen in real traffic.Next, we analyzed the behavior of the multi-state NS system in more detail. Figure2 shows an example of how the vehicle positions changed over time for a vehicle density of 0.40, with the vertical and horizontal axes representing the time step and vehicle position, respectively. This illustrates traffic congestion, where overcrowded regions are sometimes clearly separate from sparsely populated regions and sometimes not.Figure 2
Illustration of vehicle positions over 10,000 time steps for the multi-state NS model. Here, the vertical and horizontal axes indicate the time step and vehicle position, respectively, and each vehicle is shown as a black dot. The vehicle density is 0.40,p=0.01vmax=5, threshold_slow = 5, and threshold_acceleration = 15.Figure3 shows an example where the traffic appears to repeatedly fall into and out of a particular phase. To examine the different traffic phases in that system, we took some snapshots of the vehicle velocities. Figure S2 in the Supplementary Material shows the relationship between the vehicle velocity and position at a particular time step, for a vehicle density of 0.40. Here, we can see that the system exhibits multiple traffic states, with the phase transitioning back and forth from synchronized flow to traffic jam, i.e., that the multi-state NS system can exhibit reversible phase transitions.Figure 3
Changes in the flux over time for the multi-state NS model with a vehicle density of 0.40, showing. (a) All data for 100,000 time steps and (b) a subset of the data. Here,p=0.01, vmax=5, threshold_slow = 5, and threshold_acceleration = 15.
(a)
(b)Then, we investigated how the flux changed over time, focusing on severe traffic jams. Here we calculated the intervals between successive extreme traffic jams, where we defined an extreme traffic jam as a phase with a flux of less than 0.005. Figure4 shows the cumulative distribution for decreasing intervals between successive extreme traffic jams. Here, we plot 37 data points taken from one trial over 100,000 time steps, finding a slope μ of 1.21 and an Akaike information criterion (AIC) weight for a power-law versus an exponential-law distribution of 1.00. This figure indicates that the traffic system seems to frequently experience extreme traffic jams but is also able to escape that phase for long periods on rare occasions. In particular, the intervals’ cumulative distribution appears to follow a power-law distribution [26] where the lifetimes of extreme traffic jams are less than ten time steps, i.e., the events are transient and unstable. We therefore focused on these unique phenomena.Figure 4
Cumulative distribution of the intervals between severe jams for the multi-state NS model, showing data for 100,000 time steps. Here, the vehicle density is 0.40,p=0.01, vmax=5, threshold_slow = 5, and threshold_acceleration = 15.From Figures3 and 4, we can see that although the traffic system frequently suffers from extreme jams, it occasionally takes a long time, e.g., more than 10,000 steps, before it experiences such a jam. The fact that the intervals’ cumulative distribution appears to follow a power-law distribution reveals that the traffic system does not oscillate periodically with respect to the vehicle flux.In addition, to evaluate whether the system exhibits internal fluctuations, we calculated the relationship between the flux and the fluctuation functionσ as follows:(2)σi2=fi2−fi2.Here,fi denotes the flux at position i. Figure 5 shows that the slope is approximately 0.53≈0.50, indicating endogenous behavior determined by the system’s internal collective fluctuations (R2=0.98) [27–29]. Again, these data were obtained over 100,000 time steps.Figure 5
Relationship between the flux and the fluctuation function for the multi-state NS model, showing data for 100,000 time steps. Here, the vehicle density is 0.40,p=0.01, vmax=5, threshold_slow = 5, and threshold_acceleration = 15.After that, we evaluated the effects of different parameter values. First, we changed the vehicle density from 0.40 to 0.20 and examined the effects on the flux’s time evolution over 100,000 steps, to confirm that it still varied from trial to trial. FigureS3 in the Supplementary Material shows the relationship between the vehicle velocity and position for a particular time step with a vehicle density of 0.20. As for a density of 0.40, we see phase transitions from synchronized flow to jam and vice versa. Comparing Figures S4(a) and S4(b) with Figure 3, the system’s flux appears to be high when the vehicle density is low and jams still sometimes occur for periods of time, as was the case with a density of 0.40 (Figures S4(a) and S4(b)). Based on these results, we re-defined system phases with fluxes of less than 0.01 as extreme traffic jams. As Figure S4(c) shows, the cumulative distribution of the intervals between extreme jams again appears to follow a power-law distribution (1370 data points, μ=1.66, AIC weight for a power-law versus an exponential-law distribution of 1.00). In other words, we see no periodic oscillations in the traffic system over a range of densities.Next, we adjusted thethreshold_slow and threshold_acceleration parameters. Figures S5(a) and S5(b) in the Supplementary Material show the relationship between the flux and vehicle density for (threshold_slow, threshold_acceleration) values of (10, 30) and (10, 10), respectively. Here, we have plotted data from 10 trials for vehicle densities of up to 0.50, with a bin width of 0.01. The flux appears to fluctuate over a wide range of vehicle densities, regardless of the threshold values. However, threshold_acceleration must be higher than threshold_slow in order to generate a heavy traffic jam for an extended period of time (Figures S5(c) and S5(d)).Finally, we changed the parameterp from 0.01 to 0.1 and evaluated the effect on the flux’s time evolution over 100,000 time steps. Here, we can clearly see that the flux is low when p is large (Figures S6(a) and S6(b)). We also calculated the time intervals between extreme traffic jams, defining system phases with fluxes of less than 0.005 as extreme traffic jams. Again, the intervals’ cumulative distribution appears to follow a power-law distribution (20 data points, μ=1.23, AIC weight for a power-law versus an exponential-law distribution of 1.00). Thus, changing the randomization parameter has no impact on the traffic system’s nonperiodic oscillations.


## 4. Conclusions

We have developed a CA model, called the multi-state NS model, in which individual vehicles adjust their velocities based on experience and the distance to the vehicle in front. Each vehicle maintains its speed when it believes local jams will persist, but catches up to the vehicle ahead when it believes the local jam is temporary. We found that traffic flows in this system could be reversible over wide range of vehicle densities. The system sometimes experiences severe jams while maintaining some level of congested flow [14, 15]. In real traffic flows, the flux oscillates nonperiodically [23, 24], which may be related to the emergence of complex macro-level patterns. In our model, nonperiodic oscillations persist even after changing the parameters, suggesting that it is flexible with respect with to some parameter changes.On the other hand, we do not see this behavior when the vehicles’ states are fixed. For example, the system appears to experience severe jams for extended periods when the vehicles are fixed in calm.” states, but it behaves more like the traditional NS model when the vehicles are fixed in harsh.” states. By contrast, our multi-state NS model can reproduce the reversibility of traffic flows and nonperiodic oscillations in the system’s flux.Few studies have considered whether individual drivers’ experiences/memories produce differing responses to similar environments. By developing such a model, we have shown that the resulting traffic system follows a scale-free evolution with respect to the flux, behavior that is often observed when studying complex systems in biology, as well as in physical and social studies.According to previous studies, the distances between pairs of consecutive vehicles (gaps) are an important factor in representing congested or complex traffic patterns [14, 15, 21–23]. The proposed CA model can illustrate how drivers’ decisions, based on their individual memories, can affect the gaps and the dynamics of transitions between different flow states. Given this, we believe that it is important to understand the relationships between the macro-level emergent flows and micro-level mechanisms of traffic systems in order to develop traffic jam theories that reveal the mechanisms behind jammed flows and solve the problem of traffic congestion [17].



---

*Source: 1956521-2019-12-29.xml*