next up previous
Next: Dynamics on a graph Up: Cellular automata models for Previous: Introduction

Subsections


CA rules for traffic

In CA models for traffic, space is typically coarse-grained to the length a car occupies in a jam ( $\ell = 1/\rho_{jam} \approx 7.5$ m), and time typically to one second (which can be justified by reaction-time arguments [1]). One of the side-effects of this convention is that space can be measured in ``cells'' and time in ``time steps'', and usually these units are assumed implicitly and thus left out of the equations. A speed of, say, $v=5$, means that the vehicle travels five cells per time step, or 37.5 m/s, or 135 km/h, or approx. 85 mph.

Deterministic traffic CA

Typical CA for traffic represent the single-lane road as a 1-dimensional array of cells of length $\ell$, each cell either empty or occupied by a single vehicle. Vehicles have integer velocities between zero and $v_{max}$. A possible update rule is [2]

\begin{displaymath}
\let\green=\black
\begin{tabular}{\vert l\vert l\vert}
\hlin...
...Movement: & $x_{t+1} = x_t + v_{t+1}$\ \\
\hline
\end{tabular}\end{displaymath}

The first rule describes deterministic car-following: try to accelerate by one velocity unit except when the gap is too small or when the maximum velocity is reached. $g$ is the gap, i.e. the number of empty cells between the vehicle under consideration and the vehicle ahead, and $v$ is measured in ``cells per time step''.

This rule is similar to the CA rule 184 in the Wolfram classification [3]; indeed, for $v_{max}=1$ it is identical. This model has some important features of traffic, such as start-stop waves, but it is unrealistically ``stiff'' in its dynamics.

For this CA, it turns out that, after transients have died out, there are two regimes, depending on the system-wide density $\rho_L$ (Fig. 1):

The two regimes meet at $
\rho_c = 1 / (v_{max}+1) \hbox{ and } q_c = v_{max} / (v_{max}+1) \ ;
$ this is also the point of maximum flow.

Figure 1: Sequence of configurations of CA 184. Lines show configurations of a segment of road in second-by-second time steps; traffic is from left to right. Integer numbers denote the velocities of the cars. For example, a vehicle with speed ``3'' will move three sites (dots) forward. Via this mechanism, one can follow the movement of vehicles from left to right, as indicated by some example trajectories. TOP: Uncongested traffic. BOTTOM: Congested traffic.
\includegraphics[width=0.6\hsize]{184tty-fig.eps}


Stochastic traffic CA (STCA)

One can add noise to the CA model by adding a randomization term [4]:

\begin{displaymath}\let\green=\black
\begin{tabular}[c]{\vert l\vert l\vert}
\hl...
...ving:} &
$x_{t+1} = x_{t} + v_{t+1} $\ \\
\hline
\end{tabular}\end{displaymath}

$t$ and $t+1$ refer to the actual time-steps of the simulation; $t+\frac{1}{2}$ denotes an intermediate result used during the computation.

With probability $p_n$, a vehicle ends up being slower than calculated deterministically. This parameter simultaneously models effects of (i) speed fluctuations at free driving, (ii) over-reactions at braking and car-following, and (iii) randomness during acceleration periods.

This makes the dynamics of the model significantly more realistic (Fig. 2). $p_{noise}=0.5$ is a standard choice for theoretical work (e.g. [5]); $p_{noise} = 0.2$ is more realistic with respect to the resulting value for maximum flow (capacity), see Fig. 2 (right) [6].

Figure 2: Stochastic CA. LEFT: Jam out of nowhere leading to congested traffic. RIGHT: One-lane fundamental diagram as obtained with the standard cellular automata model for traffic using $p_{noise} = 0.2$; from [6].
= -2pt ......4.....1..2.....3...2....3..........5..........5.... ..5.......2..1...2......1..2.....4............4.......... .......3....1.2....2.....1...2.......4............4...... ..........1..1..3....2....1....2.........5............4.. .4.........1..2....2...3...2.....3............4.......... .....5......2...2....3....1..3......4.............5...... ..........3...3...3.....1..1....4.......4..............5. 4............3...2...3...2..1.......5.......4............ ....4...........2..2....1..1.1...........4......5........ ........4.........1..2...2..1.2..............5.......4... ..4.........4......2...3...1.1..2.................4...... ......5.........4....2....1.0.2...2...................4.. ...........5........2..3...01...2...2.................... 5...............4.....2...00.1....3...3.................. .....4..............2...0.01..2......3...3............... .5.......4............1.0.0.1...3.......3...3............ ......5......5.........00.1..2.....3.......3...4......... ...........5......3....00..1...3......3.......4....4..... ................4....0.01...1.....4......4........4....5. ....................01.0.1...2........4......5........4.. ....................1.00..1....3..........4.......4...... .....................000...2......3...........5.......4.. ....5................000.....3.......3.............5..... ..4......5...........001........3.......4...............5 ......5.......4......00.1..........3........5............ 5..........5......1..01..2............3..........5....... .....5..........2..1.0.2...3.............3............5.. ...4......4.......1.00...2....3.............3............ .......4......3....001.....2.....3.............3......... ...........5.....1.00.1......3......4.............4...... ..4.............1.000..1........3.......5.............5..
\includegraphics[width=\hsize]{fdiag-1lane-gz.eps}

Slow-to-start (s2s) rules/velocity-dependent randomization (VDR)

Real traffic has a strong hysteresis effect near maximum flow: When coming from low densities, traffic stays laminar and fast up to a certain density $\rho_2$. Above that, traffic ``breaks down'' into start-stop traffic. When lowering the density again, however, it does not become laminar again until $\rho < \rho_1$, which is significantly smaller than $\rho_2$, up to 30% [7,8]. This effect can be included into the above rules by making acceleration out of stopped traffic weaker than acceleration at all other speeds, for example by making the probability $p_n$ in the STCA velocity-dependent: If $p_n(v\!=\!0) > p_n(v\!\ge\!1)$, then the speed reduction through the randomization step is more often applied to vehicles with speed zero than to other vehicles. Such rules are called ``slow-to-start'' rules [9,10].


Time-oriented CA (TOCA)

A modification to make the STCA more realistic is the so-called time-oriented CA (TOCA) [11]. The motivation is to introduce a higher amount of elasticity in the car following, that is, vehicles should accelerate and decelerate at larger distances to the vehicle ahead than in the STCA, and resort to emergency braking only if they get too close. The rule set is easier to write in algorithmic notation, where $v := v+1$ means that the variable $v$ is increased by one at this line of the program. For the TOCA velocity update, the following operations need to be done in sequence for each car:

  1. if ( $g > v \cdot \tau_H$ ) then, with probability $p_{ac}$: $
v := \min\{ v+1, v_{max} \} \ ;
$

  2. $v := \min\{ v, g \}$

  3. if ( $g < v \cdot \tau_H$ ) then, with probability $p_{dc}$: $
v := \max\{ v-1, 0 \} \ .
$

Typical values for the free parameters are $(p_{ac},p_{dc},\tau_H) = (0.9,0.9,1.1)$. The TOCA generates more realistic fundamental diagrams than the original STCA, in particular when used in conjunction with lane-changing rules on multi-lane streets.


Dependence on the velocity of the car ahead

The above rules use gap alone as the controlled variable. More sophisticated rules will use more variables, for example the first derivative of the gap, which is the velocity difference. The idea is that if the car ahead is faster, then this adds to one's effective gap and one may drive faster than without this. In the CA context, the challenge is to retain a collision-free parallel update. Ref. [12] achieved this by going through the velocity update twice, where in the second round any major velocity changes of the vehicle ahead were included. Ref. [13] instead also looked at the gap of the vehicle ahead. The idea here is that, if we know both the speed and the gap of the vehicle ahead, and we make assumptions about the driver behavior of the vehicle ahead, then we can compute bounds on the behavior of the vehicle ahead in the next time step.

Traffic breakdown

An interesting topic is the transition from laminar to congested traffic. For the deterministic model, things are clear: The laminar regime is when all vehicles move at full speed; the congested regime is when at least one vehicle in the system does not move at full speed. Deterministic models can also display bi-stability, i.e. density ranges where both the laminar and the congested phase are stable. This is for example the case with deterministic slow-to-start models [14]. This characterization is the same as for deterministic fluid-dynamical models [15].

For stochastic models, things are less clear since even in the laminar regime there may be slow vehicles, their slowness caused by random fluctuations. Often, the analogy to a gas/liquid transition is used, meaning that traffic jams are droplets of the liquid phase interdispersed in the gaseous phase of laminar traffic. However, the question of a phase transition in stochastic models has not been completely settled [16,17,18]. The main problem seems to be that questions of meta-stability and of phase separation are not treated separately, although they should be, as our own recent investigations show [19].


Lane changing

Lane changing is implemented as an additional sub-timestep before the velocity update. Lane changing consists of two parts: the reason to change lanes, and the safety criterion. The first one can be caused by slow cars ahead, or by the desire to be in the correct lane for a turn at the end of a link. The safety criterion means that there should be enough empty space around a vehicle which changes lanes. A simple symmetric implementation of these principles is:


next up previous
Next: Dynamics on a graph Up: Cellular automata models for Previous: Introduction
Kai Nagel 2002-05-31