key: cord-0045611-q6pgdh8b
authors: Bazior, Grzegorz; Pałka, Dariusz; Wąs, Jarosław
title: Using Cellular Automata to Model High Density Pedestrian Dynamics
date: 2020-05-26
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50371-0_36
sha: 795e9cfbf05508057b9cb15800c4ad8d559acc3d
doc_id: 45611
cord_uid: q6pgdh8b

The article presents a model of pedestrian dynamics based on Cellular Automata, dedicated especially for high density conditions. Using the proposed representation, it is possible to map different behaviors of agents in various conditions. The article describes mechanisms of a pedestrian’s movement for different pedestrian’s shapes when a pedestrian occupies multiple cells, compared to the classical representation where a pedestrian occupies a single square cell. A greater number of cells per pedestrian can describe a pedestrian with e.g. a backpack, a suitcase on wheels, or on a bicycle more precisely than when s/he is represented by one cell. More accurate discretizations are particularly useful when high density of pedestrians occurs. The article focuses on the following aspects of a pedestrian’s movement: changing direction, movement speed, a passing scheme, and an overtaking scheme.

Dense crowd modeling is currently perceived as a significant challenge. On the one hand, continuous methods allow for precise calculations of the superposition of the acting forces, and, on the other hand, agent-based models operating within the Cellular Automata framework [7, 8] are highly efficient. The classical approach [2] , in which a pedestrian is represented as a single cell, is often insufficient in modeling high pedestrian densities in a given area using two-dimensional cellular automaton. An interesting solution was proposed in [3] , when sub-mesh configuration was proposed as a complement of standard mesh (lattice) in order to handle higher values of maximum density of simulation of dense crowds. Simultaneously, different concepts of finer discretization were presented: namely in [4] an idea of placing two pedestrians in one cell or the application of a dense triangular grid presented in [5] .

In the classic approach, the size of a cell is usually equal to 40 cm × 40 cm [2] . However, in situations when more pedestrians should be placed in a singular cell (even until 10 pers/m 2 ), as in Predtechensky & Milinski experimental research [9] , such granulation is insufficient. For example, the width of typical door openings differs by 10 cm, and in a situation of the high pedestrian flow (e.g. fire evacuation) the difference between 60 cm, 70 cm and 80 cm door throughput is important, as was confirmed by empirical results of competitive and non-competitive evacuation in [6] . This article presents an approach aimed at increasing the accuracy of modeling pedestrian dynamics in case of high crowd density, as a continuation of a previous study by the authors [1] . This approach is based on the density of nesting grids and the introduction of additional mechanisms of pedestrians' behavior, which can be described using CA lattice density. The article presents the methods of adaptation of the original mechanisms for dense grids proposed in the study [2] and the consequences of these adaptations.

The presented model is developed on the reduced size of individual cells. In order to maintain symmetry at rotations, it is recommended that densifying is made an odd number of times (3, 5, 7, ...) in the direction of each axis of the reference system ( Fig. 1 ). In case of a grid 3 times denser, the cell size is about 13 cm × 13 cm, while in case of a grid 5 times denser, the cell size is about 8 cm × 8 cm, which is usually sufficient for accurate modeling of space and pedestrian dynamics even for dense crowds.

In case of the basic model [2] , a pedestrian occupies one cell, so the shape of a pedestrian (in the projection to a floor plane) is a square. In reality, however, this shape is similar to an ellipse [11] , where the longer half axis coincides with the axis of the arms (left-right), while the shorter half axis coincides with the axis of the front-back. Thanks to the densifying of the grid, it is possible to represent a pedestrian using a more complex shape (e.g. a rectangle instead of a square) - Fig. 2 . A dense grid also allows for representing more complex shapes, such as a pedestrian with a backpack, a suitcase on wheels, a bag, etc., which can be seen in Figs. 3, 4, 5. In case of the standard pedestrian flow, these additional elements have a little influence on the pedestrian movement, however, in case of high density of pedestrians (e.g. during competitive evacuation), they become important.

To maintain compatibility with the basic model, it is assumed that a pedestrian, regardless of his/her orientation, always occupies the same cell in the basic grid (marked in the drawings with thick black lines). The second assumption is that the area occupied by a pedestrian in the projection to a floor plane (i.e. the number of occupied cells) should not depend on the pedestrian's orientation (rotation inside the basic cell).

The proposed scheme of transitions of the individual cells included in the basic cell as a result of rotation is shown in Fig. 6 . The remaining orientations are created in the same manner.

Rotation 45 deg Rotation 90 deg 

Thanks to the density of the grid, it is possible to model smaller movements (e.g. 13 cm, 8 cm) than in the basic model for which the minimum distance of movement is 40 cm. Such a reduction of movement granulation allows for reproducing phenomena occurring at high and very high crowd densities -for example, in the bottleneck area. To be able to maintain the maximum speed (which is distance divided by time) as in the basic model, the n-times reduction of the cell size must be accompanied by the n-times reduction of the time step.

Compared to the basic model, where only two speeds are possible within a basic cell: v max = cell size/time step and 0, densifying the grid n-times gives n + 1 possible speeds with which pedestrians can move:

where:

cell size -the size of a cell in the basic model (before densifying) time step -the time step in the basic model This allows for a better representation of the distribution of pedestrians' walking speed [11] , which depends on many factors such as, for example, the age of a pedestrian, his BMI, his personal preferences, etc. Also, in case of modeling crowd dynamics, the density of the crowd is a very important factor influencing pedestrians' speed. Generally, for high density only low speed motion is allowed.

This scheme is applicable to the situations in which two pedestrians are walking from the opposite directions in a narrow passage, e.g. on a train, bus, tram, theater hall, cinema, etc. In such scenarios, due to limited space, it is impossible for pedestrians to pass with their normal orientation (i.e the shorter half-axis of the ellipse describing the pedestrian is in line with the direction of his movement). However, after the rotation of 90 • , passing is possible -see Fig. 8 . Such a phenomenon cannot be described in the basic model, in which a pedestrian is symmetrical (square), but it is possible in the proposed model thanks to densifying the grid and a more accurate representation of geometry.

An overtaking situation occurs when pedestrians move in the same direction at different speeds. If the trajectories of both pedestrians overlap (e.g. due to movement in the same floor field), the faster pedestrian must change his trajectory in order to overtake the slower one.

The scenario involves two pedestrians marked accordingly: S -slower (marked in green in the figure), F -faster (marked in yellow in the figure) -see Fig. 9 .

Speed reduction Overtaking Return to the trajectory The proposed scheme consists of the following steps:

-the faster pedestrian F catches up with the slower one S (both pedestrians follow the same trajectory) -temporary reduction of pedestrian F's speed to follow pedestrian S -if there is free space on the side of the pedestrian S and there are no obstacles in front of him (or other pedestrians walking from the opposite direction), pedestrian's F speed is increased and the trajectory is changed (he overtakes pedestrian S on the left or right side) -in the last step pedestrian F returns to the original trajectory and reduces his speed to the initial value (from the first step) Figure 9 shows the flow of the overtaking scheme in the coordinate system associated with the slower pedestrian (S ). The speed of the slower pedestrian (marked as a black dot) is zero in this coordinate system. The relative speed of the faster pedestrian (F ) in this coordinate system is marked as a black arrow.

The solutions included in the proposed model and described above were tested by the pedestrian dynamic simulator we are developing (Fig. 10) . One of the main objectives of our system is to simulate the behaviour of the crowd in situations such as evacuation during a fire, storming stores by shoppers, etc. (Fig. 11) .

The comparison of the simulation results obtained using the basic model [2] and the proposed model with different cell densities is presented below. 

In this scenario, the pedestrians initially located on the left side of the scene move towards the exit on the right side of the scene. Because the exit is closed, a crowd is formed in front of it. The initial distribution of pedestrians is the same in all variants. The dashed rectangle represents the area occupied by the crowd at the end of the simulation.

The figures present the following:

- Figure 12 : the initial and final situation in the crowd-forming scenario for the basic model (cell size 40 × 40 cm, a pedestrian's shape is represented as a square 1 × 1 cell) - Figure 13 : as above for the model with 3-times densified grid and a pedestrian's shape -2 × 3 cells rectangle - Figure 14: as above for the model with 5-times densified grid and a pedestrian's shape -3 × 5 cells rectangle

One hundred executions were performed for each variant, and the results are reported in Table 1 .

The column 'final pedestrian density' presents the density of the crowd after simulation of its formation. As can be seen from the results, the densified grid of the cellular automata grid, which yields a more accurate description of the pedestrian's shape, allows for a higher density of people per square meter in the simulation. Such densities correspond to those found in real experiments (e.g. Fig. 11 ).

The column 'average execution time' shows the average time of execution of the simulation -as can be seen, increasing the density of the grid significantly increases the duration of the simulation. The theoretical influence of increasing the grid density on the time of execution of individual stages of the simulation is presented below. Shortening the Time Step. The reduction of the cell size by n-times also reduces the simulation time step n-times. Thus, in order to obtain the same pedestrian's movement (e.g. 1 m) it is necessary to perform n-times more time steps (simulation steps).

Initialisation. The most complex part of the scene preparation is static floor field initialization. During static floor field initialization for each cell in the scene all neighbours of each cell need to be checked in order to minimize the static floor field value. Thus, computational complexity of static floor field for the entire scene (C s ) is:

where:

-M -the number of neighbour cells for each cell in the scene n -the number of cells per scene For the k-times densified grid (in the direction of each axis) the number of operations would increase k 2 -times.

Pedestrian's Movements. According to [2] , the three following factors need to be considered in calculating movement:

-static floor field -dynamic floor field -cell occupation by another pedestrian or obstancle All these factors need to be considered for all neighbour cells around each pedestrian. So, for a pedestrian represented as a rectangle with N 1 × N 2 cells N 1 × N 2 cells need to be checked into each m direction. Thus, the complexity of each pedestrian's movement calculation (C p ) is:

where:

f -the number of factors considered in each cell (in our case they are: static floor field, dynamic floor field and cell occupation -so f=3) -m -the number of directions considered for a pedestrian's movement -N 1 × N 2 -cells per pedestrian So, for the k-times increasing side length of a pedestrian (due to grid densifying), the number of operations would increase to k-times.

After Movement Calculations. The most costly operation after each step of all pedestrians is recalculation of dynamic floor field, which must be done for each cell. The process of diffusion and decay of dynamic floor field is described in [2] . Thus, the complexity of dynamic floor field calculation (C d ) is:

where:

m -the number of neighbour cells for each cell n -the number of all cells per scene For k-times densified grid (in the direction of each axis) the number of operations would increase k 2 -times.

The model presented in the article allows for much more accurate representation of high density pedestrian dynamics than the basic model. However, the application of the model, as discussed earlier, is connected with increased computational complexity and thus with the increased time of the simulation. The use of the presented model is generally justified in situations with high pedestrian densities, as is the case, for example, during mass evacuation. One of the ways to improve the efficiency of the simulation may be to automatically switch the simulator working mode between the model (if the pedestrian density is low) and the model proposed in our article (if pedestrian density is medium or high). Such a model change may concern the whole scene that is being simulated or only the part of it with higher pedestrian density, leading to the concept of using hybrid models (combining different models within the same scene). This will be the subject of our further work related to the pedestrian dynamic simulator.

This work is a continuation of previous studies [1, 8] on CA-based agent models of the crowd. We wanted to create a model based on cellular automata which would allow for more accurate representations of pedestrian dynamics occurring at high crowd densities. It was developed for our pedestrian dynamics simulator (Fig. 10) , one of the objectives of which is to simulate the behavior of the crowd during situations such as evacuation from a building during a fire. The consequence of the proposed n-times densifying of the grid of the cellular automaton is an increase of space computational complexity n 2 times. In addition, the n-times reduction of a cell size requires the n-times reduction of the time step (in order to maintain the speed of the pedestrian's movement, which is distance divided by time) which leads to an additional n-times increase of time computational complexity. The hybrid model described in [10] can be a partial solution to the computation complexity problems. In the described model floor fields of some cells are grouped in order to decrease computation complexity, which can be helpful when simulation needs to be done for greater scenes.

However, thanks to the model proposed in this article, it is possible to map many situations in pedestrian dynamics in conditions of high density: a scheme of passing in a narrow corridor or an overtaking scheme. It should be stressed that thanks to a fine representation of pedestrians in a lattice it is possible to represent different shapes of pedestrians, their speed, etc. with greater precision.

Cellular automata based modeling of competitive evacuation

Simulation of pedestrian dynamics using a two-dimensional cellular automaton

An improved cellular automata model to simulate the behavior of high density crowd and validation by experimental data

The evacuation process study with the cellular automaton floor field on fine grid

A cellular automata model for high-density crowd evacuation using triangle grids

Simulation of competitive egress behavior: comparison with aircraft evacuation data

A review of cellular automata models for crowd evacuation

Cellular automata as the basis of effective and realistic agent-based models of crowd behavior

Translation of: Proektirovanie zhdanii s uchetom organizatsii dvizheniya lyudskikh potokov

A novel grid-based mesoscopic model for evacuation dynamics