Minimization of Mean-CVaR Evacuation Time of a Crowd using Rescue Guides: a Scenario-based Approach

Anton von Schantz; Harri Ehtamo; Simo Hostikka

doi:10.17815/CD.2021.112

Authors

Anton von Schantz School of Science, Aalto University, Espoo, Finland
Harri Ehtamo School of Science, Aalto University, Espoo, Finland
Simo Hostikka School of Engineering, Aalto University, Espoo, Finland

DOI:

https://doi.org/10.17815/CD.2021.112

Keywords:

evacuation, rescue guides, multi-agent system, scenario-based approach, bi-objective optimization, numerical simulation, genetic algorithm

Abstract

In case of a threat in a public space, the crowd in it should be moved to a shelter or evacuated without delays. Risk management and evacuation planning in public spaces should also take into account uncertainties in the traffic patterns of crowd flow. One way to account for the uncertainties is to make use of safety staff, or guides, that lead the crowd out of the building according to an evacuation plan. Nevertheless, solving the minimum time evacuation plan is a computationally demanding problem. In this paper, we model the evacuating crowd and guides as a multi-agent system with the social force model. To represent uncertainty, we construct probabilistic scenarios. The evacuation plan should work well both on average and also for the worst-performing scenarios. Thus, we formulate the problem as a bi-objective scenario optimization problem, where the mean and conditional value-at-risk (CVaR) of the evacuation time are objectives. A solution procedure combining numerical simulation and genetic algorithm is presented. We apply it to the evacuation of a fictional passenger terminal. In the mean-optimal solution, guides are assigned to lead the crowd to the nearest exits, whereas in the CVaR-optimal solution the focus is on solving the physical congestion occurring in the worst-case scenario. With one guide positioned behind each agent group near each exit, a plan that minimizes both objectives is obtained.

References

Haghani, M.: Optimising crowd evacuations: Mathematical, architectural and behavioural approaches. Safety Science 128, 104745 (2020). doi:10.1016/j.ssci.2020.104745

Wong, S.K., et al.: Optimized evacuation route based on crowd simulation. Computational Visual Media 3(3), 243-261 (2017). doi:10.1007/s41095-017-0081-9

Gwynne, S.M.V., Hulse, L.M., Kinsey, M.J.: Guidance for the model developer on representing human behavior in egress models. Fire Technology 52(3), 775-800 (2016). doi:10.1007/s10694-015-0501-2

Proulx, G.: Movement of people: the evacuation timing. In: DiNenno, P.J., et al. (eds.) SFPE Handbook of Fire Protection Engineering, pp. 342-366. the National Fire Protection Association (2002)

Heliövaara, S., Kuusinen, J.M., Rinne, T., Korhonen, T., Ehtamo, H.: Pedestrian behavior and exit selection in evacuation of a corridor-An experimental study. Safety Science 50(2), 221-227 (2012). doi:10.1016/j.ssci.2011.08.020

Helbing, D., Isobe, M., Nagatani, T., Takimoto, K.: Lattice gas simulation of experimentally studied evacuation dynamics. Physical Review E 67(6), 1-4 (2003). doi:10.1103/PhysRevE.67.067101

von Schantz, A., Ehtamo, H.: Minimizing the evacuation time of a crowd from a complex building using rescue guides (2020). URL https://arxiv.org/abs/2007.00509. arXiV:2007.00509v1 [physics.soc-ph]

Schultz, M., Fricke, H.: Managing passenger handling at airport terminals. In: 9th Air Traffic Management Research and Development Seminars (2011)

Ali, H., Guleria, Y., Alam, S., Duong, V.N., Schultz, M.: Impact of stochastic delays, turnaround time and connection time on missed connections at low cost airports. In: Proc. 13th USA/Eur. Air Traffic Manage. R&D Seminar (2019)

Bellomo, N., Piccoli, B., Tosin, A.: Modeling crowd dynamics from a complex system viewpoint. Mathematical Models and Methods in Applied Sciences 22(supp02), 1230004 (2012). doi:10.1142/S0218202512300049

Helbing, D., Molnar, P.: Social force model for pedestrian dynamics. Physical Review E 51(5), 4282 (1995). doi:10.1103/PhysRevE.51.4282

Burstedde, C., Klauck, K., Schadschneider, A., Zittartz, J.: Simulation of pedestrian dynamics using a two-dimensional cellular automaton. Physica A: Statistical Mechanics and its Applications 295(3-4), 507-525 (2001). doi:10.1016/S0378-4371(01)00141-8

Pelechano, N., Badler, N.I.: Modeling crowd and trained leader behavior during building evacuation. IEEE Computer Graphics and Applications 26(5), 1319-1332 (2012). doi:10.1109/MCG.2006.133

Wang, X., Cheng, Y.: Evacuation assistants: An extended model for determining effective locations and optimal numbers. Physica A: Statistical Mechanics and Its Applications 391(6), 2245-2260 (2012). doi:10.1016/j.physa.2011.11.051

McCormack, P., Chen, T.Y.: Optimizing leader proportion and behavior for evacuating buildings. In: Proceedings of the 2014 Symposium on Agent Directed Simulation, ADS '14, pp. 13:1-13:6. Society for Computer Simulation International, San Diego, CA, USA (2014)

Yang, X., Dong, H., Yao, X., Sun, X., Wang, Q., Zhou, M.: Necessity of guides in pedestrian emergency evacuation. Physica A: Statistical Mechanics and its Applications 442, 397-408 (2016). doi:10.1016/j.physa.2015.08.020

Albi, G., Bongini, M., Christiani, E., D., K.: Invisible control of self-organizing agents leaving unknown environments. SIAM Journal on Applied Mathematics 76(4), 1683-1710 (2016). doi:10.1137/15M1017016

Zhou, M., Dong, H., Zhao, Y., Ioannou, P.A., Wang, F.Y.: Optimization of crowd evacuation with leaders in urban rail transit stations. IEEE Transactions on Intelligent Transportation Systems 20(12), 4476-4487 (2019). doi:10.1109/TITS.2018.2886415

Beyer, H.G., Sendhoff, B.: Robust optimization-a comprehensive survey. Computer Methods in Applied Mechanics and Engineering 196(33-34), 3190-3218 (2007)

Birge, J.R.: The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming 24(1), 314-325 (1982). doi:10.1007/BF01585113

Rockafeller, R.T., Uryasev, S.: Optimization of conditional value-at-risk. Journal of risk 2, 21-42 (2000). doi:10.21314/JOR.2000.038

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation 6(2), 182-197 (2002)

Sethian, J.A.: Level set methods and fast marching methods: Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science, vol. 3. Cambridge University Press (1999)

Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Boston, MA, USA (1989)

von Schantz, A., Ehtamo, H.: Pushing and overtaking others in a spatial game of exit congestion. Physica A: Statistical Mechanics and its Applications 527, 121151 (2019). doi:10.1016/j.physa.2019.121151

Fortin, F.A., Parizeau, M.: Revisiting the NSGA-II crowding-distance computation. In: Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp. 623-630. ACM (2013)

Bader, J., Zitzler, E.: HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation 19(1), 45-76 (2011)

Korhonen, T., Hostikka, S.: Fire dynamics simulator with evacuation: FDS+Evac: Technical reference and user's guide. Tech. rep., VTT Technical Research Centre of Finland (2009)

Oliphant, T., et al.: Numba: A high performance python compiler (2020). URL https://numba.pydata.org. Accessed: 2020-03-16

von Schantz, A.: The minimum time evacuation of a crowd using rescue guides: a scenario-based approach (article code, version 1.0) (2020). URL https://github.com/antonvs88/multiobj-guided-evac. Accessed: 2020-06-13

Steffen, B., Seyfried, A.: Methods for measuring pedestrian density, flow, speed and direction with minimal scatter. Physica A: Statistical mechanics and its applications 389(9), 1902-1910 (2010)

Smith, R.: Density, velocity and flow relationships for closely packed crowds. Safety science 18(4), 321-327 (1995)

Heliövaara, S., Korhonen, T., Hostikka, S., Ehtamo, H.: Counterflow model for agent-based simulation of crowd dynamics. Building and Environment 48, 89-100 (2012a). doi:10.1016/j.buildenv.2011.08.020

Cao, S., Song, W., Lv, W.: Modeling pedestrian evacuation with guiders based on a multi-grid model. Physics Letters A 380(4), 540-547 (2016). doi:10.1016/j.physleta.2015.11.028

Hou, L., Liu, J.G., Pan, X., Wang, B.H.: A social force evacuation model with the leadership effect. Physica A: Statistical Mechanics and its Applications 400, 93-99 (2014). doi:10.1016/j.physa.2013.12.049

Ma, Y., Yuen, R.K.K., Lee, E.W.M.: Effective leadership for crowd evacuation. Physica A: Statistical Mechanics and its Applications 450, 333-341 (2016). doi:10.1016/j.physa.2015.12.103

Wang, X., Guo, W., Cheng, Y., Zheng, X.: Understanding the centripetal effect and evacuation efficiency of evacuation assistants: Using the extended dynamic communication field model. Safety Science 74, 150-159 (2015). doi:10.1016/j.ssci.2014.12.007

Ma, Y., Lee, E.W.M., Shi, M.: Dual effects of guide-based guidance on pedestrian evacuation. Physics Letters A 381(22), 1837-1844 (2017). doi:10.1016/j.physleta.2017.03.050

Still, G.K.: Crowd dynamics. Doctoral disseration (2000)

Aubé, F., Shield, R.: Modeling the effect of leadership on crowd flow dynamics. In: Sloot, P.M.A., Chopard, B., Hoekstra, A.G. (eds.) Cellular Automata, pp. 601-611. Springer (2004). doi:10.1007/978-3-540-30479-1_62

Heliövaara, S., Ehtamo, H., Helbing, D., Korhonen, T.: Patient and impatient pedestrians in a spatial game for egress congestion. Physical Review E 87(1), 012802 (2013). doi:10.1103/PhysRevE.87.012802

Karamouzas, I., Sohre, N., Narain, R., Guy, S.J.: Implicit crowds: Optimization integrator for robust crowd simulation. ACM Transactions on Graphics (TOG) 36(4), 1-13 (2017)