2.3 Representation of Space: Discrete vs. Continuous

With respect to the representation of space in a microscopic model, there are two basic approaches (see fig. 2.2): discrete or continuous. If space is represented in a discrete fashion, usually a regular lattice is used. This notion is quite familiar in statistical mechanics and is often used for modeling systems with restricted degrees of freedom such as solids (lattice gas, Ising-model, percolation models). In reality, the degrees of freedom for pedestrian movement are not restricted in this way, though. Whether to use a discrete or continuous representation of space is closely connected to the implementation (similar to models for road traffic). A strong argument in favor of discrete models is that they are simple and can be used for large scale simulations. Additionally, for pedestrian motion and behavior there is a finite reaction time, which introduces a time scale. If the

2.3 Representation of Space: Discrete vs. Continuous 13

Table 2.1. Examples for microscopic models, classified with respect to the dynamics of pedes- motion. Δt is the time step, a is the length of a quadratic cell, hence ρmax = 1/a 2 for a square grid. If the cell length a is not specified, ρmax cannot be compared to empirical data (denoted by n.a. for not applicable in the third column).

type characteristics ρmax vmax 1 lattice gas biased random walk n.a. 1 cell/Δt [Muramatsu et al., 1999]

time is chosen to be discrete in the model, too, this naturally (but not necessarily) leads to a discrete representation of space. Firstly, the continuous approach will be outlined, and then the main aspects concerning the discrete or grid-based models are introduced. One special class of the discrete models are the so called Cellular Automata (CA) models. Their properties will be discussed in depth (together with a specific model for pedestrian dynamics in egress simulations) in chapter 3.

2.3.1 Continuous Models

Even though the major topic of this work are two-dimensional CA models, reference will be made at various places to continuous models for pedestrian dynamics. Due to this and the importance of continuous models as the alternative approach towards representing space, this section describes the social force model and some of its properties in some detail [Helbing et al., 2002, Helbing and Molnar, 1995]. Further models belonging to this class are those of Hoogendoorn [2000], Hoogendoorn and Bovy [2001], Hoogendoorn et al. [2002] and (for the case of evacuation simulation) Thompson et al. [1996]. The former provides a generalization of the social force model where the way finding is based on an extremal principle, whereas the latter is a full scale implementation covering also complex geometries like floor-plans of large office buildings or passenger vessels. The social force model is based on continuous space and time:

dd x i (t)

= v i (t) , (2.3)

dt

where x i denotes the position and v i the velocity of pedestrian i. The pedestrians are represented as disks with radii r i . The sum of forces pedestrian i is subject to is called ξ i (t) are individual fluctuations. The equation of motion is then given by: dd v i

= ξ i (t) . (2.4) m i

dt

ξ i (t). The resulting system of partial differential equations can be solved numerically (e.g, by applying methods of Molecular Dynamics

2.3 Representation of Space: Discrete vs. Continuous 15

2.3.2 Discrete (Grid-based) Models

Especially for the reasons stated above, discrete models are appealing for simulations of large complex structures. Another factor is simulation speed, since cellular automata are per construction well suited for efficient implementation. The Nagel-Schreckenberg model [Nagel and Schreckenberg, 1992] is a very well understood model for the simulation of road traffic and can therefore provide insights into some aspects of models for crowd movement. Due to its simplicity, it provides a good starting point for relating fundamental properties of the model to its characteristics. 3 For the sake of completeness, the definition of the Nagel-Schreckenberg (NaSch) model is included here. The rule set (parallel update) for t → t + Δt is:

i → min(v max , v t 1. Accelerate: v t i + 1),

i → min(v t

Fig. 2.4. Definitions and notations in the Nagel-Schreckenberg model. The numbers in the cells give the current velocity, gi denotes the gap between car i and its predecessor. The cell size in the standard model is 7.5 m which leads for Δt = 1 s to a maximum velocity of 135 km/h and an acceleration of 7.5 m/s 2 .

The results obtained for the NaSch model concerning the influence of v max and funda- flow-density-relations are important for understanding the generalization to two dimensions, where similar decisions concerning the cell size, the type of the update, and v max have to be made. Exact results can be obtained for the case v max = 1, where the NaSch model is equivalent to the asymmetric simple exclusion process [Rajewsky et al., 1998]. In this case, the backward sequential update (against the direction of motion) produces the highest flow 6 , which is given by

1 − ρ J ← (ρ, p) = pρ . (2.11)

1 − pρ

p is the hopping probability 7 and J grows with p. If p is set to 1, then J = ρ, i.e., all cars always move. The density for which the flow takes its maximum is shifted to the right when p is increased. This is different for the parallel update:

1

1 − 1 − 4pρ(1 − ρ) J || (ρ, p) = .

2.3 Representation of Space: Discrete vs. Continuous 17

Fig. 2.5. Particle-hole symmetry holds for vmax = 1 but does not for vmax > 1. Left: the dynamics remains the same, if holes move instead of particles in the opposite direction but according to the same rules. Right: For vmax > 1 this does not hold, since the one but leftmost hole would have to move together with the leftmost one, which is not allowed for a parallel update. The particle-hole symmetry leads to a symmetry in the fundamental diagram as can be seen from eq. 2.15 and is shown in fig. 3.17.

j ↑ denotes the flow in the direction of motion (of the particles) and j ↓ against the direction of motion (for the parallel update). For ρ particles = 1/2+x, ρ holes = 1/2−x, and therefore

j particles,↑ (1/2 − x) = j particles,↑ (1/2 + x). (2.15)

Please note that particle hole symmetry does never hold for an interaction range larger than 1 cell, i.e., neither for v max > 1 (cf. fig. 2.5) nor for...