Crowd Science

Module 4, lesson 3 · 45 minutes

Cellular automata and floor fields

A chessboard of 40 cm cells, a 0.3 s clock, and two fields that tell each person where to step.

You’ll be able to

  • describe the floor-field cellular automaton: 40 cm cells and 0.3 s steps;
  • write the transition probability and compute it for a simple case;
  • explain kS (exit knowledge), kD (herding) and why evacuation time can be non-monotonic.

Introduction

Throw away forces. Cover the floor with squares 40 cm across and let each person hop at most one square every 0.3 s. That is 0.4 ÷ 0.3 ≈ 1.3 m/s, close to a free walking speed (our arithmetic). Burstedde and colleagues chose these numbers in 2001: cells of approximately 40 × 40 cm² and a time step of about 0.3 s at about 1.3 m/s. The result is a model that is fast, simple and, used carefully, surprisingly good.

Two floor fields and one probability

A cellular automaton is a grid of cells whose states update together, each step, by local rules. Here a cell is empty, occupied by one person, a wall or an exit. Each step, every person picks a neighbouring cell (or stays) with probability

pij = N · exp(kS Sij) · exp(kD Dij) · (1 − nij) · ξij

Sij
static floor field: higher nearer the exit
Dij
dynamic floor field: traces left by others
kS, kD
how strongly people follow each field
nij
1 if the cell is occupied
ξij
0 for a wall
N
normalises the probabilities to sum to 1

The static floor field encodes the building: here, minus the distance to the nearest exit. The dynamic floor field is a trace: a person leaves a “boson” in each cell they vacate, and bosons decay and diffuse each step, like a pheromone trail. This is the form of Kirchner and Schadschneider (2002), where kS measures knowledge of the exit and kD herding.

Worked example. A person with four free neighbours (von Neumann neighbourhood) can step forward (S rises by 1), back (S falls by 1), sideways (S about unchanged) or stay. With kS = 1 the weights are e¹ = 2.72, e⁻¹ = 0.37, 1, 1 and 1: forward 45%, back 6%, each other option 16%. With kS = 3: forward 83%, back 0.2%, each other option 4% (our arithmetic). An occupied neighbour simply drops out of the sum.

Updates are parallel. When two people choose the same cell, one wins at random; the sandbox adds an optional friction μ, the chance that nobody moves in such a conflict.

The sandbox: a grid that learns the way out

  1. Set kS to 0 and play: people random-walk and few find the exit.
  2. Set kS to 3, then 10. Watch everyone converge on the straight line to the exit.
  3. Press “Sweep k_S”. Compare the curves without and with friction.
  4. Set kS to 0.5 and raise kD. Do the traces help people find the exit, or lead them astray?

Without friction, more exit knowledge always helps until the exit passes people as fast as it can. With friction, too much knowledge hurts: everyone wants the same cells, and conflicts end with nobody moving. The sweep curve has a minimum.

Kirchner and Schadschneider report that evacuation time depends non-monotonically on the couplings, with minima at intermediate values. In our small sandbox the minimum in kS shows clearly only with friction: with 200 people, mean times without friction fall and level off from about kS = 4, while with μ = 0.8 they are lowest near kS = 1–2 and about a quarter higher at kS = 8 (our runs).

Strengths and weaknesses

Cellular automata are fast and easy to parallelise, so they suit large buildings and many repeated runs. Their weaknesses come from the grid. Movement has preferred directions, so diagonal routes are distorted. Density cannot exceed one person per cell: 1 ÷ 0.16 m² = 6.25 p/m² (our arithmetic), below the local densities recorded in real crushes. And there are no forces, so a cellular automaton cannot say anything about pressure in a crowd.

Why would a cellular automaton with 40 cm cells be a poor tool for reconstructing the Itaewon crush?

Its density is capped at 6.25 p/m², while the reconstruction estimated 10.74 p/m², and it has no forces, so it cannot represent compression or falls.
  • “Herding always helps.” Following traces helps only if the traces lead somewhere useful; in the sandbox strong herding usually slows evacuation.
  • “The grid size is a detail.” It sets the maximum density and, with the time step, the walking speed.