Pedestrian crowd dynamics have been in the focus of quite different fields of study for many decades now: Sociologists and psychologists investigated the behaviour of individuals whereas physicists, mathematicians and software engineers tried to transfer the conclusions of the former into models for simulation. The virtual reality scene as well as the games and film industry used the results to imitate realistic group behaviour. Finally, architects attempted to improve building design.

One of the probably most important fields of application is that of evacuation dynamics. Simulations can play a decisive role for analysis and risk management, helping to prevent dangerous situations in huge crowds, improving the overall evacuation performance.

In my master thesis a model based on a cellular automaton approach was developed to simulate crowd dynamics and orderly evacuations.

Irrational behaviour and panics as well as cognitive aspects or hazards like fire or smoke were - however - beyond the scope of this thesis.

Before we devote ourselfs to the question of how the behaviour of pedestrians can be imitated, we have to ask why we believe that this is possible at all. There are numerous movement patterns or so-called self-organization phenomena observed during empirical studies and video evaluations like e.g. lane formation and oscillations at narrowings, stripe formation in intersecting streams or clogging and arching in case of an evacuation situation. Self-organization or emergence in this context means, that the behaviour shown by the crowd neither arise from the intention of the ones involved to show such behaviour nor due to direct communication. Caused by non-linear interactions it rather appears automatically.

Fig. 1, Schematic views of observed self-organization phenomena: From left to right: (a) By forming lanes of uniform walking direction instead of being equally distributed over the sidewalk/corridor, the number of encounters, braking and avoidance maneuvers between opposing pedestrians in counterflows are minimized. Therefore, the average walking speed, which is a measure for the global walking efficiency, is maximized. (b) If pedestrians of opposite walking directions meet at a narrow place, one direction of movement shows itself as dominant, while the pedestrians of the other have to wait. With time, oscillatory changes of the flow direction can be observed, since it is easier to walk with than contrary to the flow. That is why groups of people rather than single pedestrians will pass the bottleneck contemporaneous. (c) In crossing streams, stripe formation can be observed. The stripes move into the direction of the sum vector of the two directional vectors and fray perpendicular to it. This allows the continuous mutual penetration of the pedestrian flows without any major obstructions. Thus, the number of necessary interactions is minimized. (d) With people escaping from a closed room, having velocities exceeding a certain threshold, arch-like traffic jams at the exit will occur, since the particles mutually prevent themselves from leaving, because of frictional interactions and a bottleneck diameter being too small.

But how to explain these recurring patterns, when each individual has its own preferences, intentions, and goals? Well, although human behaviour sometimes appears to be somehow chaotic, it shows certain regular patterns and is not completely random. There are patterns of behaviour everybody unconsciously tends to and which are executed rather automatically. For instance, an experienced car driver does not have to reflect on his behaviour while turning, changing gears, or accelerating.

Usually, the behaviour of a pedestrian is driven by utility maximization. This means, that he tries to walk in the most convenient way, to minimize detours and to take the optimal path to the target. As far as this is possible, he will try to keep a certain distance to others, to walls and to obstacles. And he will walk with an individually desired walking speed pleasant to him, which corresponds to the one with minimal energy consumption.

These optimized behavioural strategies have been learned in course of time by trial and error. They provide the most successful reaction on a given situation and can be determined by simulating the learning behaviour of pedestrians with evolutionary algorithms. But although we can assume that pedestrians to behave in such an optimal way, there always will be fluctuations in the movement of individuals. Therefore, simulation results are uncertain to some extent. However, if the simulated crowd is large enough and the simulation repeated several times, the uncertainty due to the behaviour of the individuals is averaged out at a macroscopic level of description.

As mentioned above, the concept of cellular automata (CA) was used for simulating crowd dynamics. The first mathematical concepts regarding CA were developed in the late 1940’s and at the beginning of the 1950’s, when John Louis von Neumann used the human brain as an example for designing comparable automatic computing machines. With the increasing complexity of such systems a greater need for reliability evolved. Therefore, von Neumann concentrated his investigations on self-reproducing structures that should be able to repair themselves. In contrast to von Neumann’s constructs, modern CA are no longer physical systems but computer programs.

CA, which received the name from their grid structure and the fact that each cell can be seen as a finite state automaton, can be characterized by some fundamental properties: First of all, they consist of a theoretically infinite regular discrete lattice of cells. What is a regular lattice? Well, a regular polygon is a shape with sides of the same length and equal angles. If only one type of such regular polygons is placed vertex to vertex without any sliding, hole or overlapping, we call this a regular tiling/tesselation. Generally, a CA can be defined with any number of dimensions. But usually two dimensions are used. In 2D only squares, equilateral triangles, and regular hexagons build up regular tilings. Pentagons, heptagons, octagons etc. produce irregular ones. Due to their complicated visualization triangular structures, where two alternately oriented triangles are needed to construct the tiling, rarely are used for pedestrian simulations. Within a defined grid structure pedestrians hop from one site to another to pass through a building. Each cell receives a state from a finite set of possible states: It may be empty or occupied by a pedestrian, it may represent an obstacle like a wall or it may be an exit. The overall state is called the global configuration. Similar to space, CA also introduce a time scale. With every time step the cell states are synchronously updated (parallel) according to the defined transition rules. Or, to put it briefly, the configuration is changed. The rules only depend on the momentary state of the cell and a finite number of neighbours (the neighbourhood relation). They are identical for all cells. Most frequently only adjacent cells are used to define a neighbourhood relation, although it is also possible to introduce arbitrary ones.

Therefore, a CA can be characterized by the three keywords parallelism, locality and homogeneity. The list of real world applications is long: Simulation of exciteable media like nerve or muscle tissue (Greenberg-Hastings automata), of prairie fires, chemical systems, traffic situations and of human interactions such as e.g. on the stock market - to name only a few.

Because of the introduced space dimensions and time evolution CA are useful for the description of any spatiotemporal phenomena. Due to of their discreteness they are ideally suited for large scale computations. On the other hand, they must be regarded as only an approximation to reality.

Which target cell of the possible ones a pedestrian chooses at a given time step mainly depends on two factors: The so-called static floor field S and the dynamic floor field D. The static floor field could best be desribed as an array holding scalar values - the potentials - providing information on the geometry of a building. It is used to specify regions of attraction as exits and repulsion such as walls. In case of an evacuation situation, S describes the shortest way to the next exit - seen from any site - by measuring the number of steps that are needed to reach the destination from the cell under consideration. If the pedestrians follow the gradient of the potential array, they automatically reach the exit, no matter at which site they are placed within the lattice.

As derivable from its name, the static floor field is time-independent and cannot be influenced by pedestrians. Calculated once before simulation it will remain fixed.

Fig. 2, The static floor field in 3D: On the left side of the figure, a building with three rooms, a corridor and an exit is shown, on the right side the accompanying static floor field. The differences in altitude and colour represent the different potentials according to the distance of the respective site to the exit. If pedestrians follow the gradient of potentials, they automatically reach the exit.

The dynamic floor field D is used to model the interactions between pedestrians. This field is developed from the idea of indirect communication based on changes in the local environment (stigmergy). It is inspired by nature, where insect societies like ant colonies use techniques of swarm intelligence to form self-organising, emergent systems. Ants continuously secrete chemical substances - the so-called pheromones - forming a trail and thereby attracting other ants which orientate themselves to these traces (chemotaxis). In this way, ants are able to return to their colony when striving around for food. Since the pheromones decay and diffuse, the formed trails are optimized within time. As a result, the shortest connection between the nest and a food source is established.

Fig. 3, The dynamic floor field in 3D: This figure shows an instant snapshot of the dynamic floor field at time step t. There is a corridor with two opposing pedestrian streams: The red ones are walking from left to right, the green ones from right to left. Each group has its own dynamic floor field. As can be seen from those fields, there is a tendency to lane formation already: The left diagram shows two major lanes for the red group, as the right one does for the green group. Altitude and colour represent the number of pheromones placed in the respective site. Whenever a pedestrian moves, he stores a pheromone in the cell left.

At present, the dynamic floor field is the only known way to enable CA to simulate collective effects such as lane formation or herding which are based on long-range interactions between pedestrians. Translating these long-range interactions into local ones but with memory, CA remains efficient. As explained above, the pedestrians in this model are equipped with as little intelligence as possible. This is one of the major differences to agent-based models.

Whenever a pedestrian is about to investigate his local neighbourhood in order to determine the next target cell, he will take a look into the static and the dynamic floor field to analyse the stored values. From these values transition probabilities are computed which are the probabilities of the considered sites for being chosen as the next destination cell.

As stated in the section discussing CA, all pedestrians synchronously move. Therefore, conflicts arise whenever two or more pedestrians try to move to the same target cell. Since a cell can be occupied by only one pedestrian (hard core exclusion), a conflict solution strategy is needed.

Principally, such a strategy would allow one pedestrian/particle, randomly chosen from the conflicting parties, to move while the others have to remain at their origin sites.

In order to illustrate the discussed theoretical concepts, a prototypical Java implementation ("Quo vadis?") was developed as part of the thesis. The program can be divided into two parts: Firstly, an editor in which scenarios can be defined, and secondly, a simulator in which these scene files will be computed.

The editor provides functionalities for modelling multi-storey buildings as well as corridors and crossings. The system is highly flexible: It is possible to switch on-the-fly between a square and a hexagonal lattice, as well as between a von Neumann or Moore neighbourhood relation. In order to support explorative learning an undo-/redo-functionality was also implemented.

Fig. 4, Egression from a single-storey building with four exits: The picture in the upper left corner shows the starting configuration for a single-storey building with four exits and 1000 pedestrians. On the upper right, a snapshot after 40s is shown with the corresponding dynamic floor field at the lower left. On the lower right, there is another snapshot of the evacuation run after 3m29s.

Having computed a given scenario, the simulator writes the results into a file. Consequently it is possible to repeatedly load them. The data can be played like a video visualising the evolution of the real space dynamics and the dynamic floor field as well as the density distribution as a function of time. A detailed statistical analysis can be performed after each run.

The model has proven to correctly imitate the collective movement patterns lane formation, herding and clogging/arching.