AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (13.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Optimized evacuation route based on crowd simulation

"National Chiao Tung University", Taiwan, China.
Show Author Information

Abstract

An evacuation plan helps people move away from an area or a building. To assist rapid evacuation, we present an algorithm to compute the optimal route for each local region. The idea is to reduce congestion and maximize the number of evacuees arriving at exits in each time span. Our system considers crowd distribution, exit locations, and corridor widths when determining optimal routes. It also simulates crowd movements during route optimization. As a basis, we expect that neighboring crowds who take different evacuation routes should arrive at respective exits at nearly the same time. If this is not the case, our system updates the routes of the slower crowds. As crowd simulation is non-linear, the optimal route is computed in an iterative manner. The system repeats until an optimal state is achieved. In addition to directly computing optimal routes for a situation, our system allows the structure of the situation to be decomposed, and determines the routes in a hierarchical manner. This strategy not only reduces the computational cost but also enables crowds in different regions to evacuate with different priorities. Experimental results, with visualizations, demonstrate the feasibility of our evacuation route optimization method.

Keywords

crowd simulationevacuationpath planningoptimization

References

[1]
H. W. Hamacher,; S. A. Tjandra, Mathematical modelling of evacuation problems: A state of the art. Fraunhofer-Institut für Techno-und Wirtschaftsmathematik, 2001.
[2]
S.-K. Wong,; Y.-S. Wang,; P.-K. Tang,; T.-Y. Tsai, Optimized route for crowd evacuation. In: Pacific Graphics Short Papers. E. Grinspun,; B. Bickel,; Y. Dobashi, Eds. The Eurographics Association, 2016.
[3]
A. Schadschneider,; W. Klingsch,; H. Klüpfel,; T. Kretz,; C. Rogsch,; A. Seyfried, Evacuation dynamics: Empirical results, modeling and applications. In: Encyclopedia of Complexity and Systems Science. R. A. Meyers, Ed. Springer New York, 3142-3176, 2009.
Crossref
[4]
D. Dressler,; M. Groß,; J.-P. Kappmeier,; T. Kelter,; J. Kulbatzki,; D. Plümpe,; G. Schlechter,; M. Schmidt,; M. Skutella,; S. Temme, On the use of network flow techniques for assigning evacuees to exits. Procedia Engineering Vol. 3, 205-215, 2010.
Crossref Google Scholar
[5]
T. Hadzic,; N. Brown,; C. J. Sreenan, Real-time pedestrian evacuation planning during emergency. In: Proceedings of the IEEE 23rd International Conference on Tools with Artificial Intelligence, 597-604, 2011.
Crossref
[6]
A. Abdelghany,; K. Abdelghany,; H. Mahmassani,; W. Alhalabi, Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities. European Journal of Operational Research Vol. 237, No. 3, 1105-1118, 2014.
Crossref Google Scholar
[7]
H.-R. Wang,; Q.-G. Chen,; J.-B. Yan,; Z. Yuan,; D. Liang, Emergency guidance evacuation in fire scene based on pathfinder. In: Proceedings of the 7th International Conference on Intelligent Computation Technology and Automation, 226-230, 2014.
Crossref
[8]
A. Desmet,; E. Gelenbe, Capacity based evacuation with dynamic exit signs. In: Proceedings of the IEEE International Conference on Pervasive Computing and Communication Workshops, 332-337, 2014.
Crossref
[9]
H. Tang,; A. Elalouf,; E. Levner,; T. C. E. Cheng, Efficient computation of evacuation routes on a three-dimensional geometric network. Computers & Industrial Engineering Vol. 76, 231-242, 2014.
Crossref Google Scholar
[10]
G. Berseth,; M. Usman,; B. Haworth,; M. Kapadia,; P. Faloutsos, Environment optimization for crowd evacuation. Computer Animation and Virtual Worlds Vol. 26, Nos. 3-4, 377-386, 2015.
Crossref Google Scholar
[11]
B. Haworth,; M. Usman,; G. Berseth,; M. Kapadia,; P. Faloutsos, Code: Crowd optimized design of environments. In: Proceedings of the 29th International Conference on Computer Animation and Social Agents, 2016.
Crossref
[12]
B. Haworth,; M. Usman,; G. Berseth,; M. Kapadia,; P. Faloutsos, Evaluating and optimizing level of service for crowd evacuations. In: Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, 91-96, 2015.
Crossref
[13]
M. Moussaïd,; M. Kapadia,; T. Thrash,; R. W. Sumner,; M. Gross,; D. Helbing,; C. Hölscher, Crowd behaviour during high-stress evacuations in an immersive virtual environment. Journal of the Royal Society Interface Vol. 13, No. 122, 20160414, 2016.
Crossref Google Scholar
[14]
P. A. Thompson,; E. W. Marchant, A computer model for the evacuation of large building populations. Fire Safety Journal Vol. 24, No. 2, 131-148, 1995.
Crossref Google Scholar
[15]
G. G. Lovas, On the importance of building evacuation system components. IEEE Transactions on Engineering Management Vol. 45, No. 2, 181-191, 1998.
Crossref Google Scholar
[16]
N. Pelechano,; N. I. Badler, Modeling crowd and trained leader behavior during building evacuation. IEEE Computer Graphics and Applications Vol. 26, No. 6, 80-86, 2006.
Crossref Google Scholar
[17]
Y. Ma,; R. K. K. Yuen,; E. W. M. Lee, Effective leadership for crowd evacuation. Physica A: Statistical Mechanics and its Applications Vol. 450, 333-341, 2016.
Crossref Google Scholar
[18]
N. Dimakis,; A. Filippoupolitis,; E. Gelenbe, Distributed building evacuation simulator for smart emergency management. The Computer Journal Vol. 53, No. 9, 1384-1400, 2009.
Crossref Google Scholar
[19]
S. Rodriguez,; N. Amato, Behavior-based evacuation planning. In: Proceedings of the IEEE International Conference on Robotics and Automation, 350-355, 2010.
Crossref
[20]
J. Tsai,; N. Fridman,; E. Bowring,; M. Brown,; S. Epstein,; G. Kaminka,; S. Marsella,; A. Ogden,; I. Rika,; A. Sheel,; M. E. Taylor,; X. Wang,; A. Zilka,; M. Tambe, ESCAPES: Evacuation simulation with children, authorities, parents, emotions, and social comparison. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, Vol. 2, 457-464, 2011.
[21]
T. Kretz,; A. Grosse,; S. Hengst,; L. Kautzsch,; A. Pohlmann,; P. Vortisch, Quickest paths in simulations of pedestrians. Advances in Complex Systems Vol. 14, No. 5, 733-759, 2011.
Crossref Google Scholar
[22]
Y. Inoue,; A. Sashima,; T. Ikeda,; K. Kurumatani, Indoor emergency evacuation service on autonomous navigation system using mobile phone. In: Proceedings of the 2nd International Symposium on Universal Communication, 79-85, 2008.
Crossref
[23]
C.-Y. Chen, The design of smart building evacuation system. International Journal of Control Theory and Applications Vol. 5, No. 1, 73-80, 2012.
Google Scholar
[24]
D. Helbing,; P. Molnár, Social force model for pedestrian dynamics. Physical Review E Vol. 51, 4282-4286, 1995.
Crossref Google Scholar
[25]
J. Van den Berg,; M. Lin,; D. Manocha, Reciprocal velocity obstacles for real-time multi-agent navigation. In: Proceeding of the IEEE International Conference on Robotics and Automation, 1928-1935, 2008.
Crossref
[26]
I. Karamouzas,; P. Heil,; P. van Beek,; M. H. Overmars, A predictive collision avoidance model for pedestrian simulation. In: Motion in Games. A. Egges,; R. Geraerts,; M. Overmars, Eds. Springer-Verlag Berlin Heidelberg, 41-52, 2009.
Crossref
[27]
S. J. Guy,; J. Chhugani,; S. Curtis,; P. Dubey,; M. Lin,; D. Manocha, PLEdestrians: A least-effort approach to crowd simulation. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 119-128, 2010.
[28]
S. Curtis,; B. Zafar,; A. Gutub,; D. Manocha, Right of way. The Visual Computer Vol. 29, No. 12, 1277-1292, 2013.
Crossref Google Scholar
[29]
A. Johansson,; D. Helbing,; P. K. Shukla, Specification of the social force pedestrian model by evolutionary adjustment to video tracking data. Advances in Complex Systems Vol. 10, No. supp02, 271-288, 2007.
Crossref Google Scholar
[30]
K. H. Lee,; M. G. Choi,; Q. Hong,; J. Lee, Group behavior from video: A data-driven approach to crowd simulation. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 109-118, 2007.
[31]
F. Durupɩnar,; U. Güdükbay,; A. Aman,; N. I. Badler, Psychological parameters for crowd simulation: From audiences to mobs. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 9, 2145-2159, 2016.
Crossref Google Scholar
[32]
C. D. Boatright,; M. Kapadia,; J. M. Shapira,; N. I. Badler, Generating a multiplicity of policies for agent steering in crowd simulation. Computer Animation and Virtual Worlds Vol. 26, No. 5, 483-494, 2015.
Crossref Google Scholar
[33]
F.-S. Li,; S.-K. Wong, Animating agents based on radial view in crowd simulation. In: Proceedings of the 22nd ACM Conference on Virtual Reality Software and Technology, 101-109, 2016.
Crossref
[34]
M. Kapadia,; N. Pelechano,; J. Allbeck,; N. Badler, Virtual Crowds: Steps toward Behavioral Realism. Morgan & Claypool Publishers, 2015.
Crossref
[35]
R. Geraerts,; M. H. Overmars, The corridor map method: A general framework for real-time high-quality path planning. Computer Animation & Virtual Worlds Vol. 18, No. 2, 107-119, 2007.
Crossref Google Scholar
[36]
W. G. Van Toll; A. F. Cook IV,; R. Geraerts, Real-time density-based crowd simulation. Computer Animation & Virtual Worlds Vol. 23, No. 1, 59-69, 2012.
Crossref Google Scholar
[37]
M. Mekni, Hierarchical path planning for situated agents in informed virtual geographic environments. In: Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques, Article No. 30, 2010.
Crossref
[38]
M. Kallmann,; H. Bieri,; D. Thalmann, Fully dynamic constrained delaunay triangulations. In: Geometric Modeling for Scientific Visualization. G. Brunnett,; B. Hamann,; H. Müller,; L. Linsen, Eds. Springer-Verlag Berlin Heidelberg, 241-257, 2004.
Crossref
[39]
J. Pettré,; J. P. Laumond,; D. Thalmann, A navigation graph for real-time crowd animation on multilayered and uneven terrain. In: Proceedings of the 1st International Workshop on Crowd Simulation, Vol. 43, No. 44, 194, 2005.
[40]
O. B. Bayazit,; J. M. Lien,; N. M. Amato, Better group behaviors in complex environments using global roadmaps. Artificial Life 8 Vol. 8, 362, 2003.
Google Scholar
[41]
S. Patil,; J. van Den Berg,; S. Curtis,; M. C. Lin,; D. Manocha, Directing crowd simulations using navigation fields. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 2, 244-254, 2011.
Crossref Google Scholar
[42]
S.-K. Wong,; P.-K. Tang,; F.-S. Li,; Z.-M. Wang,; S.-T. Yu, Guidance path scheduling using particle swarm optimization in crowd simulation. Computer Animation & Virtual Worlds Vol. 26, Nos. 3-4, 387-395, 2015.
Crossref Google Scholar
[43]
M. Müller,; B. Heidelberger,; M. Hennix,; J. Ratcliff, Position based dynamics. Journal of Visual Communication and Image Representation Vol. 18, No. 2, 109-118, 2007.
Crossref Google Scholar
[44]
S. M. Donelson,; C. C. Gordon, 1995 matched anthropometric database of U.S. marine corps personnel: Summary statistics. Technical Report. Geo-Centers INC Newton Centre MA, 1996.
[45]
K. Aspelin, Establishing pedestrian walking speeds. Portland State University, 5-25, 2005.
[46]
TranSafety Inc. Study compares older and younger pedestrian walking speeds. Road Management & Engineering Journal, 1997.
Google Scholar
[47]
A. Bera,; S. Kim,; D. Manocha, Online parameter learning for data-driven crowd simulation and content generation. Computers & Graphics Vol. 55, 68-79, 2016.
Crossref Google Scholar
[48]
L. Yang,; K. Zhu,; S. Liu, Cellular automata evacuation model considering information transfer in building with obstacles. In: Pedestrain Dynamics and Evacuation. R. D. Peacock,; E. Kuligowski,; J. D. Averill, Eds. Springer Science+Business Media Springer, 317-326 2011.
Crossref
[49]
H. Hamacher,; S. Heller,; W. Klein,; G. Köster,; S. Ruzika, A sandwich approach for evacuation time bounds. In: Pedestrian and Evacuation Dynamics. R. Peacock,; E. Kuligowski,; J. Averill, Eds. Boston: Springer, 503-513, 2011.
Crossref
[50]
J. Zhong,; W. Cai,; L. Luo, Crowd evacuation planning using cartesian genetic programming and agent-based crowd modeling. In: Proceedings of the Winter Simulation Conference, 127-138, 2015.
Crossref
[51]
W.-C. Lin,; S.-K. Wong,; C.-H. Li,; R. Tseng, Generating believable mixed-traffic animation. IEEE Transactions on Intelligent Transportation Systems Vol. 17, No. 11, 3171-3183, 2016.
Crossref Google Scholar
[52]
T. Feng,; L.-F. Yu,; S.-K. Yeung,; K. Yin,; K. Zhou, Crowd-driven mid-scale layout design. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 132, 2016.
Crossref Google Scholar
Computational Visual Media
Volume 3 Issue 3,
September 2017
Pages 243-261
DOI: 10.1007/s41095-017-0081-9
Cite this article:
Wong S-K, Wang Y-S, Tang P-K, et al. Optimized evacuation route based on crowd simulation. Computational Visual Media, 2017, 3(3): 243-261. https://doi.org/10.1007/s41095-017-0081-9

821

Views

27

Downloads

36

Crossref

N/A

Web of Science

38

Scopus

0

CSCD

Altmetrics
Revised: 28 August 2016
Accepted: 10 March 2017
Published: 05 May 2017
© The Author(s) 2017

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.
Return