Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-22T18:54:49.077Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient Dynamic Floor Field Methods for Microscopic Pedestrian Crowd Simulations

Published online by Cambridge University Press:  03 June 2015

Dirk Hartmann  and
Peter Hasel
Dirk Hartmann*
Affiliation:
Siemens AG, Corporate Technology, 80200 Munich, Germany
Peter Hasel*
Affiliation:
Siemens AG, Corporate Technology, 80200 Munich, Germany
*
Corresponding author.Email:[email protected]
Email:[email protected]
Get access

Abstract

Floor field methods are one of the most popular medium-scale navigation concepts in microscopic pedestrian simulators. Recently introduced dynamic floor field methods have significantly increased the realism of such simulations, i.e. agreement of spatio-temporal patterns of pedestrian densities in simulations with real world observations. These methods update floor fields continuously taking other pedestrians into account. This implies that computational times are mainly determined by the calculation of floor fields. In this work, we propose a new computational approach for the construction of dynamic floor fields. The approach is based on the one hand on adaptive grid concepts and on the other hand on a directed calculation of floor fields, i.e. the calculation is restricted to the domain of interest. Combining both techniques the computational complexity can be reduced by a factor of 10 as demonstrated by several realistic scenarios. Thus on-line simulations, a requirement of many applications, are possible for moderate realistic scenarios.

Keywords

52B1065D1868U0568U07Pedestrian dynamicscellular automataadaptive gridsfloor field methodsfast marching methodnavigation.
Type
Research Article
Information
Communications in Computational Physics , Volume 16 , Issue 1 , July 2014 , pp. 264 - 286
Copyright
Copyright © Global Science Press Limited 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Repka - Regional Evacuation: Planning, Control, and Adaptation. http://www.repka-evakuierung.de. Sponsored by Federal Ministry of Education and Research, Germany.Google Scholar
[2]Bellomo, N. and Abdelghani Bellouquid, A.On the modeling of crowd dynamics: Looking at the beautiful shapes of swarms. Netw. Heterog. Media, 6: 383–399, 2011.Google Scholar
[3]Bellomo, N. and Dodge, C.On the modeling of traffic and crowds: a survey of models, speculations, and perspectives. SIAM Rev., 53: 409–463, 2011.CrossRefGoogle Scholar
[4]Blue, V., Embrechts, M., and Adler, J.Cellular automata modeling of pedestrian movements. IEEE Int. Conf. on Syst., Man and Cybern., page 2320, 1997.Google Scholar
[5]Burstedde, C., Klauck, K., Schadschneider, A., and Tittartz, J.Simulation of pedestrian dynamics using a 2-dimensional cellular automaton. Physika A, 295: 507–525, 2001.Google Scholar
[6]Chacon, A. and Alexander Vladimirsky, A.Fast two-scale methods for eikonal equations. SIAM J. on Scientific Computing,, 34: 547–578, 2012.Google Scholar
[7]Chalons, C.Numerical approximation of a macroscopic model of pedestrian flows. SIAM J. Sci. Comput., 29:539V555, 2007.CrossRefGoogle Scholar
[8]Chraibi, M., Kemloh, U., Schadschneider, A., and Seyfried, A.Force-based models of pedestrian dynamics. Netw. Heterog. Media, 6: 425–442, 2011.Google Scholar
[9]Chraibi, M., Seyfried, A., and Schadschneider, A.Generalized centrifugal force model for pedestrian dynamics. Phys. Rev. E, 82:046111, 2010.CrossRefGoogle ScholarPubMed
[10]Cristiani, E., Piccoli, B., and Tosin, A.Multiscale modeling of granular flows with applications to crowd dynamics. Multiscale Model. Sim., 9(1): 155–182, 2011.Google Scholar
[11]Clawson, Z., Chacon, A., and Vladimirski, A.Casual domain restriction for Eikonal equations. SIAM J. on Scientiffic Computing, page submitted, 2013. http://arxiv.org/abs/1309.2884.Google Scholar
[12]Colombo, R. M. and Rosini, M. D.Pedestrian flows and nonclassical shocks. In Mathematical Methods in the Applied Sciences, page 13, 2005.Google Scholar
[13]Coscia, V. and Canavesio, C.First-order macroscopic modelling of human crowd dynamics. Math. Mod. Meth. Appl. S., 18: 1217–1247, 2008.Google Scholar
[14]Dijkstra, E.W.A note on two problems in connexion with graphs. Numer. Math., 1: 269–271, 1959.Google Scholar
[15]Ferguson, D. and Stentz, A.Using interpolation to improve path planning: The field D* algorithm. Journal of Field Robotics, 23: 79–101, 2006.Google Scholar
[16]Fukui, M. and Ishibashi, Y.Self-organized phase transitions in cellular automaton models for pedestrians. J. Phys. Soc. Jap., 68: 2861, 1999.Google Scholar
[17]Gottlich, S., Kuhn, S., Ohst, J., Ruzika, S., and Thiemann, M.Evacuation dynamics influenced by spreading hazardous material. Netw. Heterog. Media, 6: 443–464, 2011.Google Scholar
[18]Hamacher, H.W., Heller, S., and Rupp, B.Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning. Ann. Oper. Res., 207: 161–180, 2013.CrossRefGoogle Scholar
[19]Hamacher, H.W. and S., TjandraMathematical modeling of evacuation problems: State of the art. In Schreckenberg, M. and Sharma, S.D., editors, Pedestrian and Evacuation Dynamcis, pages 227–266. Springer, 2002.Google Scholar
[20]Hart, P. E., Nilsson, N. J., and Raphael, B.A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100V107, 1968.Google Scholar
[21]Hartmann, D.Adaptive pedestrian dynamics based on geodesics. New J. Phys., 12(4):043032, 2010.Google Scholar
[22]Helbing, D.A fluid-dynamic model for the movement of pedestrians. Complex systems, 6(6): 391–415, 1992.Google Scholar
[23]Helbing, D. and Johansson, A.Pedestrian, crowd and evacuation dynamics. Encyclopedia of Complexity and Systems Science, 16: 6476–6495, 2010.Google Scholar
[24]Helbing, D. and Molnar, P.Social force model for pedestrian dynamics. Phys. Rev. E, 51:4282V4286, 1995.Google Scholar
[25]Henderson, L. F.On the fluid mechanics of human crowd motion. Transport. Res., 8: 509–515, 1974.Google Scholar
[26]Huang, H.-J. and Guo, R.-Y.Static floor field and exit choice for pedestrian evacuation in rooms with internal obstacles and multiple exits. Phys. Rev., 78(2):021131, 2008.Google Scholar
[27]Huang, L., Wong, S.C., Zhang, M., Shu, C-W., and Lam, W.H.K.Revisiting hughes’ dynamic continuum model for pedestrian flow and the development of an efficient solution algorithm. Transport. Res. B - Meth., 43: 127–141, 2009.Google Scholar
[28]Hughes, R. L.A continuum theory for the flow of pedestrians. Transport. Res. B - Meth., 36: 507–535, 2002.Google Scholar
[29]Hughes, R. L.The flow of human crowds. Annu. Rev. Fluid Mech., 35: 169–182, 2003.Google Scholar
[30]Kachroo, P., Al-nasur, S. J., Wadoo, S. A., and Shende, A.Pedestrian Dynamics - Feedback Control of Crowd Evacuation. Springer, New York, 2008.Google Scholar
[31]Kimmel, R. and Sethian, J.A. J.A.Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. USA, 95:8431V–8435, 1998.Google Scholar
[32]Klupfel, H.A Cellular Automaton Model for Crowd Movement and Egress Simulation. PhD thesis, Universitat Duisburg-Essen, Duisburg, 2003.Google Scholar
[33]Kneidl, A., Hartmann, D., and Borrmann, A.Using a multi-scale model for simulating pedestrian behavior. In 6th International Conference on Pedestrian and Evacuation Dynamics, 2012.Google Scholar
[34]Koster, G., Hartmann, D., and Klein, W.Microscopic pedestrian simulations: From passenger exchange times to regional evacuation. In Operations Research - Mastering complexity, 2010.Google Scholar
[35]Koster, G., Seitz, M., Treml, F., Hartmann, D., and Klein, W.On modelling the influence of group formations in a crowd. Contemporary Social Science, 6(3): 397–414, 2011.Google Scholar
[36]Kretz, T.Pedestrian traffic: on the quickest path. J. Stat. Mech., page P03012,2009.Google Scholar
[37]Lakoba, T. I., Kaup, D. J., and Finkelstein, N. M.Modifications of the helbing-molnar-farkas-vicsek social force model for pedestrian evolution. Simulation, 81: 339–352, 2005.CrossRefGoogle Scholar
[38]Liddle, J., Seyfried, A., Klingsch, W., Rupprecht, T., Schadschneider, A., and Winkens, A.An experimental study of pedestrian congestions: Influence of bottleneck width and length. Preprint, 2013.Google Scholar
[39]Liddle, J., Seyfried, A., and Steffen, B.Analysis of bottleneck motion using voronoi diagrams. In Peacock, R.D., Kuligowski, E.D., and Averill, J.D., editors, Pedestrian and Evacuation Dynamics, pages 833–836. Springer, 2011.CrossRefGoogle Scholar
[40]Liseikin, V. D.Grid Generation Methods. Springer, 2009.Google Scholar
[41]Lohner, R.On the modelling of pedestrian motion. Appl. Math. Model., 34: 366–382, 2010.CrossRefGoogle Scholar
[42]Maury, D., Roudneff-Chupin, A., and Santambrogio, F.A macroscopic crowd motion model of the gradient-flow type. Mathematical Models and Methods in Applied Sciences, 20: 17871821, 2010.Google Scholar
[43]Nishinari, K., Kirchner, A., Namazi, A., and Schadschneider, A.Extended floor field CA model for evacuation dynamics. IEICE Trans. Inf. Syst, E87D:726–732, 2004.Google Scholar
[44]Oppenhauser, M.Realisierung und Potenzialanalyse von wissenschaftlichen Konzepten zur regionalen Evakuierung aus polizeilicher Sicht am Beispiel des Projektes REPKA. Master’s thesis, German Police University, Münster, 2011. http://opac.pfa-ms.de/onlinedokumente/masterarbeiten/2011/0ppenhaeuser_Markus.pdf.Google Scholar
[45]Parisi, D. R., Gilman, M., and Moldovan, H.A modification of the social force model can reproduce experimental data of pedestrian flows in normal conditions. Physica A, 388:3600V3608, 2009.CrossRefGoogle Scholar
[46]Pelechano, N., Allbeck, J. M., and Badler, N.Virtual crowds: Methods, simulation, and control. Morgan & Claypool Publishers, San Rafael, Calif., 2008.Google Scholar
[47]Peteres, C.Trajectory Planning for Autonomous Underwater Vehicles. PhD thesis, Heriot-Watt University, Edinburgh, 2007.Google Scholar
[48]Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., and Lane, D.Path planning for autonomous underwater vehicles. IEEE Transactions on Robotics, 23: 331–341, 2007.Google Scholar
[49]Peyre, G. and Cohen, L.D.Heuristically driven front propagation for geodesic paths extraction. In Paragios, N., Faugeras, O. D., Chan, T., and Schnrr, C., editors, Proc. of VLSM ‘05, pages 173–185. Springer, 2005.Google Scholar
[50]Peyre, G. and Cohen, L.D.Heuristically driven front propogation for fast geodesic path extraction. International Journal for Computational Vision and Biometrics, 1:55–67, 2008.Google Scholar
[51]Peyre, G. and Cohen, L.D. L.D.Landmark-based geodesic computation for heuristically driven path planning. In Proc. of CVPR ‘06, pages 2229–2236. IEEE Computer Society, 2006.Google Scholar
[52]Schadschneider, A., Klingsch, W., H.1Klüpfel, , Kretz, T., Rogsch, C., and Seyfried, A.Evacuation dynamics: Empirical results, modeling and applications. In Meyers, Robert A., editor, Encyclopedia of Complexity and System Science, volume 3, page 3142. Springer, 2009.Google Scholar
[53]Sedgewick, R. and Wayne, K.Algorithms. Addison Wesley, 4 edition, 2011.Google Scholar
[54]Sethian, J. A.Level Set Methods and Fast Marching Methods. Cambridge University Press, 1999.Google Scholar
[55]Sethian, J.A. and Vladimirsky, A..Fast methods for the eikonal and related hamilton-jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA, 97: 5699–5703, 2000.Google Scholar
[56]Varas, A., Cornejo, M. D., Mainemer, D., Toledo, B., Rogan, J., Munoz, V., and Valdivia, J. A.Cellular automaton model for evacuation process with obstacles. Physica A, 382(2):631–642, 2007.Google Scholar
[57]Weidmann, U.Transporttechnik für Fussganger. Schriftenreihe des IVT, 90, 1992.Google Scholar
[58]Xia, Y., Wong, S.C., and Shu, C.W.Dynamic continuum pedestrian flow model with memory effect. Phys. Rev. E, 79:066113,2009.Google Scholar
[59]Xia, Y., Wong, S.C., Zhang, M., Shu, C.W., and Lam, W.H.K.An efficient discontinuous galerkin method on triangular meshes for a pedestrian flow model. Int. J. Numer. Meth. Eng., 76:337V350,2008.CrossRefGoogle Scholar
[60]Yamamoto, K., Kokubo, S., and Nishinari, K.Simulation for pedestrian dynamics by real-coded cellular automata. Physica A, 379(2):654,2007.Google Scholar
[61]Yershov, D.S. and LaValle, S.M.Simplicial Dijkstra and A* algorithms for optimal feedback planning. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2011.Google Scholar
[62]Yershov, D.S. and LaValle, S.M.Simplicial Dijkstra and A* algorithms: From graphs to continuous spaces. Advanced Robotics, 26: 2065–2085, 2012.Google Scholar
[63]Yu, W. J., Chen, L. Y., Dong, R., and Dai, S. Q.Centrifugal force model for pedestrian dynamics. Phys. Rev. E, 72:026112,2005.Google Scholar