Skip to main content

The Nagel-Schreckenberg Model

Module 6: Explorables and Discrete Models

NoteReading
  • Compulsory: Nagel and Schreckenberg (1992).
  • Recommended: Boccara (2010), Chapter 6.
  • Guide to the paper: What Nagel and Schreckenberg Did reports what the paper defines, measures and finds, and checks its numbers by simulation.

Nagel and Schreckenberg proposed a cellular automaton for single-lane freeway traffic (Nagel and Schreckenberg 1992). The road is a ring of \(L\) cells. Each cell is empty or holds one car. Each car \(n\) has a position \(x_n\) and an integer speed \(v_n \in \{0, 1, \ldots, v_{\max}\}\), measured in cells per time step. The model is agent-based: every car carries its own state and reacts to the car in front.

From cellular automata to agents

In an elementary cellular automaton every cell follows the same binary rule. The traffic model keeps discrete time and a one-dimensional road, but enriches the state (Nagel and Schreckenberg 1992; Wilensky and Rand 2015):

  • Occupied cells correspond to cars.
  • Each car stores a speed.
  • The update depends on the gap ahead and on a random slowdown.

The update is still local. It is more expressive, because agents now carry internal state.

Why call this agent-based if the road is still a grid? Because each occupied cell corresponds to an individual car with its own speed. You write the update from the point of view of each car and its local environment, not as an equation for a global density field.

The road is periodic: the first and last cells are neighbours. This removes boundary effects and makes the congestion dynamics easier to interpret. The page Boundary Conditions shows what an open edge does to Rule 184.

The four rules

Let \(d_n\) be the number of empty cells between car \(n\) and the car ahead. At every time step, all cars apply the following rules in this order, in parallel (Nagel and Schreckenberg 1992):

  1. Acceleration. \(v_n \leftarrow \min(v_n + 1,\ v_{\max})\).
  2. Braking. \(v_n \leftarrow \min(v_n,\ d_n)\).
  3. Randomization. With probability \(p\), \(v_n \leftarrow \max(v_n - 1,\ 0)\).
  4. Motion. \(x_n \leftarrow x_n + v_n\).

Rule 2 guarantees that cars never collide. Cars never overtake, so their order on the ring never changes. The number of cars is conserved on the ring, and the density is \(\rho = N/L\).

The paper words the first rule as a condition: a car with \(v < v_{\max}\) accelerates only if the distance to the next car, counted as the difference of site indices, is larger than \(v + 1\). This gives the same new speed as the two-line form above. We checked it on 20 000 random configurations with shared random numbers (see What Nagel and Schreckenberg Did). The paper also allows open boundaries and uses them in its bottleneck experiment.

The role of the randomization step

Without rule 3 (\(p = 0\)) the model is deterministic. From a random start it reaches a stationary state with flow

\[ q(\rho) = \min\big(\rho\, v_{\max},\ 1 - \rho\big), \]

so every car moves at \(v_{\max}\) for \(\rho < 1/(v_{\max}+1)\) and jams only appear above that density (Chowdhury et al. 2000). In the jammed regime the stationary pattern of cars is shifted one cell backwards per time step, against the traffic, as the paper observes (Nagel and Schreckenberg 1992). In our simulations (\(v_{\max} = 5\), \(p = 0\), \(\rho = 0.3\), \(0.4\) and \(0.5\)) the occupancy after each step was exactly the previous occupancy shifted by one cell to the left. In free flow the pattern instead moves forward with the cars.

With \(p > 0\) three things change (Nagel and Schreckenberg 1992; Chowdhury et al. 2000):

  • drivers fluctuate in speed, even on an empty road;
  • a car that brakes randomly forces the car behind to brake, which can start a jam in free traffic, with no external cause;
  • jams move backwards, against the direction of traffic.

With \(v_{\max} = 1\) and \(p = 0\) the model reduces to the elementary Rule 184 (Chowdhury et al. 2000).

Figure 1: Space-time diagrams on a ring of 200 cells at density 0.15, v_max = 5. Left: p = 0, all cars move freely after a transient. Right: p = 0.3, jams form spontaneously and travel backwards. Cars move to the right; time runs downward.

Scales

In the original interpretation one cell corresponds to 7.5 m, the space a car occupies in a jam, and one time step to about 1 s. Then \(v_{\max} = 5\) corresponds to \(5 \times 7.5\) m/s \(= 135\) km/h. The paper fixes the time step differently: free traffic moves at \(4.5\) cells per step, which is \(v_{\max} - p\) for \(p = 0.5\) (the value of \(p\) is inferred, see What Nagel and Schreckenberg Did), and this should correspond to about 120 km/h. Then one step lasts \(7.5 \times 4.5 / (120/3.6) \approx 1\) s (Nagel and Schreckenberg 1992).

NoteExercise

Why must the braking rule come before the randomization rule? What could go wrong if you apply randomization first and braking second?

Let \(v'\) be the speed after acceleration. If randomization comes first, a car whose gap is smaller than \(v'\) is slowed down to \(v' - 1 \ge d_n\) and then braked to \(d_n\) anyway, so the random slowdown has no effect on it. Fluctuations then only act on cars with at least \(v'\) empty cells ahead. In the original order the random slowdown acts after braking, on every moving car, including cars that follow closely. This is what lets one random slowdown propagate backwards as a jam. The effect is large. On a ring of 500 cells with \(v_{\max} = 5\) and \(p = 0.3\) we measured the flow for both orders (random start, 2000 burn-in steps, 4000 steps averaged, one seed):

\(\rho\) 0.1 0.2 0.3 0.5
braking before randomization (paper) 0.463 0.438 0.393 0.296
randomization before braking 0.466 0.621 0.488 0.347

At \(\rho = 0.1\) cars rarely brake and the orders agree. At higher density the swapped order has a much higher flow. Test it yourself: swap the two rules in your code and compare the space-time diagrams.

NoteExercise

Show that for \(v_{\max} = 1\) and \(p = 0\) the model is the elementary Rule 184 with cars moving to the right.

With \(v_{\max} = 1\), a car has speed 1 after acceleration, and braking sets it to 0 only if the next cell is occupied. So a car moves exactly when the cell ahead is empty. Write the neighbourhood as (left, centre, right). A cell is occupied in the next step if (a) it is occupied and the cell to its right is occupied, since the car cannot move, or (b) it is empty and the cell to its left is occupied, since that car moves in. This gives the new states \(1,0,1,1,1,0,0,0\) for the neighbourhoods \(111,110,101,100,011,010,001,000\), which read \(10111000_2 = 184\). A numerical check on 200 random rings of 50 cells found that one step of nasch_step() with \(v_{\max} = 1\) and \(p = 0\) equals one step of Rule 184 every time.

References

Boccara, Nino. 2010. Modeling Complex Systems. 2nd ed. Graduate Texts in Physics. Springer. https://doi.org/10.1007/978-1-4419-6562-2.
Chowdhury, Debashish, Ludger Santen, and Andreas Schadschneider. 2000. “Statistical Physics of Vehicular Traffic and Some Related Systems.” Physics Reports 329 (4–6): 199–329. https://doi.org/10.1016/S0370-1573(99)00117-9.
Nagel, Kai, and Michael Schreckenberg. 1992. “A Cellular Automaton Model for Freeway Traffic.” Journal de Physique I 2 (12): 2221–29. https://doi.org/10.1051/jp1:1992277.
Wilensky, Uri, and William Rand. 2015. An Introduction to Agent-Based Modeling: Modeling Natural, Social, and Engineered Complex Systems with NetLogo. MIT Press.