It is of paramount importance to ensure safe and fast evacuation routes in cities in case of natural disasters, environmental accidents or acts of terrorism. The same applies to large-scale events such as concerts, sport events and religious pilgrimages as airports and to traffic hubs such as airports and train stations. The prediction of pedestrian is notoriously difficult because it varies depending on circumstances (age group, cultural characteristics, etc.). In this study, the Ensemble Kalman Filter (EnKF) data assimilation technique, which uses the updated observation data to improve the accuracy of the simulation, was applied to improve the accuracy of numerical simulations of pedestrian flow.
The EnKF, one of the data assimilation techniques, was applied to the in-house numerical simulation code for pedestrian flow. Two cases were studied in this study. One was the simplified one-directional experimental pedestrian flow. The other was the real pedestrian flow at the Kaaba in Mecca. First, numerical simulations were conducted using the empirical input parameter sets. Then, using the observation data, the EnKF estimated the appropriate input parameter sets. Finally, the numerical simulations using the estimated parameter sets were conducted.
The EnKF worked on the numerical simulations of pedestrian flow very effectively. In both cases: simplified experiment and real pedestrian flow, the EnKF estimated the proper input parameter sets which greatly improved the accuracy of the numerical simulation. The authors believe that the technique such as EnKF could also be used effectively in other fields of computational engineering where simulations and data have to be merged.
This technique can be used to improve both design and operational implementations of pedestrian and crowd dynamics predictions. It should be of high interest to command and control centers for large crowd events such as concerts, airports, train stations and pilgrimage centers.
To the authors’ knowledge, the data assimilation technique has not been applied to a numerical simulation of pedestrian flow, especially to the real pedestrian flow handling millions pedestrian such as the Mataf at the Kaaba. This study validated the capability and the usefulness of the data assimilation technique to numerical simulations for pedestrian flow.
Togashi, F., Misaka, T., Löhner, R. and Obayashi, S. (2018), "Using ensemble Kalman filter to determine parameters for computational crowd dynamics simulations", Engineering Computations, Vol. 35 No. 7, pp. 2612-2628. https://doi.org/10.1108/EC-03-2018-0115Download as .RIS
Emerald Publishing Limited
Copyright © 2018, Emerald Publishing Limited
It is of paramount importance to ensure safe and fast evacuation routes in cities in case of natural disasters, environmental accidents or acts of terrorism. The same applies to large-scale events such as concerts, sport events and religious pilgrimages as airports and to traffic hubs such as airports and train stations. Experimental approaches are inevitable to estimate traffic/pedestrian flows and behavior. However, the cost in time, space and personnel could pose a bottleneck in large areas. Numerical simulation approaches can be considered as an alternative. During the past decade, research on pedestrian and traffic flows has attracted a lot of attention (Fruin, 1971; Helbing et al., 2002; Helbing et al., 2007; Helbing and Johansson, 2009; Averill, 2011; Schadschneider et al., 2009; Weidmann et al., 2014; The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference, 2014; The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference, 2016). With the aid of supercomputers, one can consider a large number of scenarios in a short period of time. However, human behavior has individual variability, so typical models end up having many empirical parameters. Generalization of these parameters, which determine the human behavior that is ultimately simulated, could be very challenging to determine as they vary depending on circumstances (age group, cultural characteristics, etc.). The aim of the present study is to determine these parameters in an efficient and automatic way from experiments. One promising candidate for such an automatic parameter estimation is the Ensemble Kalman Filter (EnKF) methodology (Houtekamer et al., 1996; Houtekamer and Mitchell, 1998; Houtekamer and Mitchell, 2001; Hamill and Snyder., 2000; Hamill et al., 2001; Anderson, 2001). EnKF, which is a type of data assimilation methodology, has been developed in the field of weather forecast where the atmospheric condition varies hour by hour. EnKF has the ability to dynamically estimate more appropriately the parameters or boundary/initial conditions, which will then yield a more accurate numerical simulation based on the updated measured data. Thus, we consider EnKF a promising tool in numerical simulation of pedestrian flows, which are notoriously difficult to predict. In this study, our objective is to confirm the usefulness of the EnKF in estimating the proper parameters based on the updated observation data. Two test cases were used to test EnKF. The first case was an experimental pedestrian flow: the unidirectional flow in the straight corridor (Zhang et al., 2014). The second case was the pedestrian flow of the Mataf at the Kaaba in Mecca (Löhner et al., 2018).
2. Pedestrian flow modeling
Pedestrian flow modeling has been an active field of research for the past 20 years. In its first years, papers and monograms appeared in many different journals. The PED-series of Conferences (The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference, 2014; The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference, 2016) summarizes nicely the work done so far. One can distinguish between continuum and micro-models. In the former case, the `pedestrian flow’ is treated as a continuum and appropriate partial differential equations are derived. In the case of micro-models, each individual is treated separately. Common micro-models are based on cellular automata, social force models and/or agent-based techniques. The PEDFLOW model (Zhang et al., 2014; Löhner et al., 2018; Löhner, 2010; Isenhour and Löhner, 2014; Löhner and Haug, 2014; Löhner et al., 2016, 2018), which was developed over the past two decades, combines social force and agent-based methodology to achieve realistic pedestrian motion. The basic concept is based on Newton’s laws of motion; pedestrians follow (via will forces) “global movement targets”. At the local movement level, the motion also considers the presence of other individuals or obstacles via avoidance forces (also a type of will force) and, if applicable, contact forces. In what follows, we briefly outline the main forces modeled in PEDFLOW to define the empirical parameters that will be determined via EnKF.
2.1 Will force
A pedestrian’s will force is obtained as:
One can see that the crucial parameter here is the “relaxation time”, tr, which governs the initial acceleration and “time to desired velocity”. The relaxation time clearly depends on the individual size, personality, current state of stress, desire to reach a goal, climate, signals, noises, etc.
An individual will have as its goal a desired position xd(td) that he/she would like to reach at a certain time td. Given the current position x, the direction of the velocity is:
For members of groups, the goal is always to stay close to the leader. Thus, xd(td) becomes the position of the leader. In the case of evacuation, the direction is given by the gradient of the perceived time to exit τe to the closest perceived exit:
2.2 Pedestrian avoidance forces
PEDFLOW models the desire to avoid collisions with other individuals by first checking if a collision will occur. The forces are applied in the direction normal and tangential to the intended motion:
2.3 Wall avoidance forces
Any pedestrian modelling software requires a way to input geographical information such as walls, entrances, stairs, etc. In PEDFLOW, this is accomplished via triangulation, also known as background mesh. A distance to wall map (i.e. a function dw(x) is constructed using fast marching techniques on unstructured grids), and a wall avoidance force is defined as:
Note that . The default maximum wall avoidance force is fmax = O(8) fmax(will).
2.4 Contact force
When contact occurs, the forces can increase noticeably. Unlike will forces, contact forces are symmetric. Defining:
These forces are modeled as follows:
2.5 Motion inhibition
A key requirement for humans to move is the ability to put one foot in front of the other. This requires space. Given the comfortable walking frequency of v = 2 Hz, one is able to limit the comfortable walking velocity by computing the distance to nearest neighbors and seeing which one of these is the most “inhibiting”.
2.6 Psychological factors
PEDFLOW also incorporates a number of psychological factors that, among the many tried over the years, have emerged as important for realistic simulations. For example:
Determination/pushiness: Some people exhibit a more polite behavior than others to avoid collision (determination) or ‘pushier’ individuals.
Comfort zone: In some cultures, pedestrians want to maintain some minimum distance between one another.
3. Ensemble Kalman filter (EnKF)
EnKF is a type of sequential data assimilation methodology which has been developed from the Kalman Filter (Kalman, 1960; Kalman and Bucy, 1961). In the Kalman Filter, the model is integrated forward in time, and whenever the observation data become available, it is used to update the model prediction before the integration continues. The weight matrix called the Kalman gain is calculated from:
The optimum state vector based on both the system model and the observation model is given by:
In this study, the parameter set and observation data correspond to x and y in Equation (15), respectively. Namely:
H is the operator to convert the input signal to the observation data. Hence, in this study, H and Hx represent the solver and the computed values at the observation locations, respectively. Namely:
Thus, VH and HVHT are calculated as follows:
The experimental noise matrix is prepared as:
where ev2 denotes the measurement error variance.
More details of Kalman Filter can be found in many references (Houtekamer et al., 1996; Houtekamer and Mitchell, 1998; Houtekamer and Mitchell, 2001; Hamill and Snyder, 2000; Hamill et al., 2001; Anderson, 2001; Evensen, 2003 and Kalnay, 2003).
In EnKF, an “ensemble” of data assimilation cycles is performed simultaneously. The ensemble members are generated by adding random perturbations to the center of the ensemble. The same observation data are used for all the assimilation cycles. However, different sets of random perturbations are added to the observations to maintain independence. By conducting data assimilation by an ensemble, the result covers the perturbations/errors in the initial or boundary conditions. The methodology is often used in the field of weather forecast (Houtekamer et al., 1996; Houtekamer and Mitchell, 1998; Houtekamer and Mitchell, 2001; Hamill and Snyder, 2000; Hamill et al., 2001; Anderson, 2001; Evensen, 2003 and Kalnay, 2003).
4. Experiment of unidirectional pedestrian flow
In this study, the experiment of unidirectional flow in straight corridors was utilized as the observation data.
A total of 28 runs were performed in corridors with widths of 1.8, 2.4 and 3.0 m. To regulate the pedestrian density in the corridors, the widths of the entrance and the exit were changed in each run. In this way, the inflow and outflow of the corridors are controlled by the entrance and exit. The pedestrian trajectories were extracted from video recordings semi automatically and with high precision using the software PeTrack (Boltes et al., 2008). The details of exit and entrance width in the experiment setting can be found in Zhang et al. (2014). Figure 1 shows the snapshots from the experimental run. In the experiment, averaged pedestrian density, velocity in the corridors and evacuation time (time until the last pedestrian reached the exit) were measured.
5. Numerical simulation of unidirectional pedestrian flow
Numerical simulations were conducted for all 28 runs. Figure 2 shows the blueprint of the numerical simulation and the computed result. The pedestrians are represented by the dots in the numerical simulation. The comparisons of the evacuating time between the experiment and the computations are shown in Figure 3. The comparisons indicate that the cases with less number of pedestrians, such as Runs 1, 10 and 20 agree well with the experiment, while the cases with a higher number of pedestrians, such as Runs 9, 18 and 28, the disagreement with the experiment is higher. The worst case was number 28. Figures 4 and 5 show the measured and computed pedestrian density and velocity histories for that case.
6. Application of EnKF and result of unidirectional pedestrian flow
From the computed results described above, the focus was on improving the input parameters for run 28. EnKF was applied to improve eight empirical parameters, namely, desired pedestrian velocity, variability of velocity, relaxation time to achieve desired velocity, variability of relaxation time, variability of pedestrian radius, pushiness (min/max) and comfort zone as shown in Table I. The measured pedestrian density and velocity were used as the observation data for EnKF. Figure 6 shows the comparison of the density and velocity history comparison between the computation using the original parameters and estimated parameters by EnKF and the measurement in case 28. In all, 20 parameter sets were prepared as the initial ensemble members. The initial error variance: σ2, measurement error variance: ev2 and inflation factor: ρ2 were set to 0.25, 1e-3 and 1.2. The filtering was conducted five times. Thus, (Nens = 20) × (Nite = 5) = 100 full model analyses were required. Figure 7 shows the density and velocity variances at first, second, third and fifth filtering. The ensemble members (color lines) converged into the measurement (black line) as shown in Figure 7. The convergence was monitored by evaluating and tracking the cost function, which is given by:
The convergence was also confirmed by observing the estimated parameter variances in Figure 8.
The total computational time was a few hours using a laptop, or about 7 minutes using 576 cores of the SGI ICE X system. The filtering processes took a few seconds. Most of the computational time was for the numerical simulations.
After applying EnKF, both histories in the run using estimated parameters were improved. Finally, the new parameter set was applied to all 28 cases. The evacuation time comparisons of all runs were shown in Figure 9. Remarkably, using the new parameters improved the computed evacuation times for all of the runs (Table I).
7. Mataf at the Kaaba in Mecca
In the second case, the real observation data of pilgrims around the Kaaba was used to improve the accuracy of the numerical simulation. Figure 10 shows the snapshot of the numerical simulation using the original parameter set. Pilgrims enter from a gate on the left, walk around the Kaaba 7 times and, after Sunna prayer, exit at the gate on the right. In the numerical simulation using the original parameter set, the pilgrim distribution is not uniform as shown in Figure 10.
The observation data for the EnKF in this study was pilgrim density along the distance from the Kaaba, which was observed at 14 different points. The values of the 14 points were averaged, and these averaged values were used for the EnKF targets. In addition to the eight parameters which were handled in Case 1, two more parameters were added for improvement: the pilgrim’s will force and tolerance to high densities. In all, 32 parameter sets were prepared as the initial ensemble members. The initial error variance: σ2, measurement error variance: ev2 and inflation factor: ρ2 was 0.16, 1e-3 and 1.2, respectively. We conducted seven filtering iterations. Thus, (Nens = 32) × (Nite = 7) = 224 full model analyses were required. The total computational time was about 20 hours using 576 cores of the SGI ICE X system. The time for filtering process was less than 5 seconds. Almost all the computational time was for the numerical simulations.
8. Result of EnKF application to real pedestrian flow
Figure 11 shows the snapshot of the numerical simulation using the estimated parameter set by the EnKF. The computed pilgrim distribution using the new parameter set was uniform as shown in Figure 11. Figure 12 shows the comparison of the pilgrim density along the distance from the Kaaba for the observation, the computed result using the original parameter set and the computed result using the estimated parameter set. The computed result agreed very well with the observed data even when using the original parameter set. However, there were underestimations at around 30-40 m. The computed result using the estimated parameter sets by the EnKF shows an excellent agreement with the observation. Figures 13 and 14 show the computed density and estimated parameter variances after first, second, third and seventh filtering, respectively. Ensemble members (color lines) converged into the measurement (black line) during the filtering process.
Figure 15 shows the comparison of the estimated parameter sets between the unidirectional experimental case and the Mataf in the Kaaba case. Most of the estimated parameters showed different values. It is natural that people walk in different ways in an experiment and in a religious event.
9. Concluding remarks
EnKF was applied to estimate the empirical parameters required by the pedestrian and crowd dynamics simulation code PEDFLOW. The new runs using the estimated parameter set provided much closer results to the experimental data than the results using the original parameters.
The advantage of the EnKF is the capability of dynamically utilizing the observation data. Parameters, initial conditions and boundary conditions are updated whenever the new observation data is available. Thus, the accuracy of the numerical simulation keeps improving along the environmental conditions, such as season, weather, time, temperature, etc.
The application of EnKF to pedestrian flow simulation will be a useful approach for future pedestrian flow simulations.
Parameters’ descriptions and ranges
|Parameter #||Parameter description||Range|
|1||Desired pedestrian velocity||0.8-2.0 [m/s]|
|2||Variability of velocity||0-20 [%]|
|3||Relaxation time to achieve desired velocity||0.1-1.0 [s]|
|4||Variability of relaxation time||0-10 [%]|
|5||Variability of pedestrian radius||0-10 [%]|
|6||Minimum pushiness||0.0-0.3 [−]|
|7||Maximum pushiness||0.2-1.2 [−]|
|8||Comfort zone||0.1-0.4 [m]|
|9||Pilgrim’s will force *Mataf run only||0.2-1.2 [−]|
|10||Pilgrim’s tolerance to high densities *Mataf run only||1.0-4.0 [p/m2]|
Anderson, J.L. (2001), “An ensemble adjustment kalman filter for data assimilation”, Monthly Weather Review, Vol. 129 No. 12, pp. 2884-2903.
Averill, J.D. (2011), “Five grand challenges in pedestrian and evacuation dynamics”, Pedestrian and Evacuation Dynamics, Springer, Boston, MA, pp. 1-11.
Boltes, M., Seyfried, A., Steffen, B. and Schadschneider, A. (2010), “Automatic extraction of pedestrian trajectories from video recordings”, Pedestrian and Evacuation Dynamics 2008, Springer, Berlin, Heidelberg, pp. 43-54.
Evensen, G. (2003), “The ensemble Kalman filter: theoretical formulation and practical implementation”, Ocean Dynamics, Vol. 53 No. 4, pp. 343-367.
Fruin, J.J. (1971), Pedestrian Planning and Design, No. 206.
Hamill, T.M. and Snyder, C. (2000), “A hybrid ensemble kalman filter – 3D variational analysis scheme”, Monthly Weather Review, Vol. 128 No. 8, pp. 2905-2919.
Hamill, T.M., Whitaker, J.S. and Snyder, C. (2001), “Distance-dependent filtering of background error covariance estimates in an ensemble kalman filter”, Monthly Weather Review, Vol. 129 No. 11, pp. 2776-2790.
Helbing, D., Farkas, I.J., Molnar, P. and Vicsek, T. (2002), “Simulation of pedestrian crowds in normal and evacuation situations”, Pedestrian and Evacuation Dynamics, Vol. 21 No. 2, pp. 21-58.
Helbing, D. and Johansson, A. (2009), “Pedestrian, crowd and evacuation dynamics”, Encyclopedia of Complexity and Systems Science, Springer, New York, NY, pp. 6476-6495.
Helbing, D., Johansson, A. and Al-Abideenm, H.Z. (2007), “Dynamics of crowd disasters: an empirical study”, Physical Review E, Vol. 75 No. 4, pp. 046109.
Houtekamer, P.L., Lefaivre, L., Derome, J., Ritchie, H. and Mitchell, H.L. (1996), “A system simulation approach to ensemble prediction”, Monthly Weather Review, Vol. 124 No. 6, pp. 1225-1242.
Houtekamer, P.L. and Mitchell, H.L. (1998), “Data assimilation using an ensemble kalman filter technique”, Monthly Weather Review, Vol. 126 No. 3, pp. 796-811.
Houtekamer, P.L. and Mitchell, H.L. (2001), “A sequential ensemble kalman filter for atmospheric data assimilation”, Monthly Weather Review, Vol. 129 No. 1, pp. 123-137.
Isenhour, M.L. and Löhner, R. (2014), “Verification of a pedestrian simulation tool using the NIST recommended test cases”, Transportation Research Procedia, Vol. 2, pp. 237-245.
Kalman, R.E. (1960), “A new approach to linear filtering and prediction problems”, Journal of Basic Engineering, Vol. 82 No. 1, pp. 35-45.
Kalman, R.E. and Bucy, R.S. (1961), “New results in linear filtering and prediction theory”, Journal of Basic Engineering, Vol. 83 No. 1, pp. 95-108.
Kalnay, E. (2003), “Atmospheric modeling”, Data Assimilation and Predictability, Cambridge university press, Cambridge.
Löhner, R. (2010), “On the modeling of pedestrian motion”, Applied Mathematical Modelling, Vol. 34 No. 2, pp. 366-382.
Löhner, R., Baqui, M., Haug, E. and Muhamad, B. (2016), “Real-time micro-modelling of a million pedestrians”, Engineering Computations, Vol. 33 No. 1, pp. 217-237.
Löhner, R. and Haug, E. (2014), “On critical densities and velocities for pedestrians entering a crowd”, Transportation Research Procedia, Vol. 2, pp. 394-399.
Löhner, R., Haug, E., Zinggerling, C. and Oñate, E. (2018), “Real-time micro-modelling of city evacuations”, Computational Particle Mechanics, Vol. 5 No. 1, pp. 71-86.
Löhner, R., Muhamad, B., Dambalmath, P. and Haug, E. (2018), “Fundamental diagrams for specific very high density crowds”, Collective Dynamics, Vol. 2, pp. 1-15.
Schadschneider, A., Klüpfel, H., Kretz, T., Rogsch, C. and Seyfried, A. (2009), “Fundamentals of pedestrian and evacuation dynamics”, Multi-Agent Systems for Traffic and Transportation Engineering, IGI Global, pp. 124-154.
The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference (2014), edition was in Delft, The Netherlands; see Transportation Research Procedia.
The Conference on Pedestrian and Evacuation Dynamics, a Biannual Conference (2016), edition was in Hefei, China; see Song, W., Ma, J. and Fu, L. (Eds) University of Science and Technology Press, Hefei, China.
Weidmann, U., Kirsch, U. and Schreckenberg, M. (Eds) (2014), Pedestrian and Evacuation Dynamics 2012, Springer Science and Business, Berlin.
Zhang, J., Britto, D., Chraibi, M., Löhner, R., Haug, E. and Gawenat, B. (2014), “Quantitative validation of PEDFLOW for description of unidirectional pedestrian dynamics”, Transportation Research Procedia, Vol. 2, pp. 733-738.