1. School of Information Engineering, Zhengzhou University, Zhengzhou 450000, China;
2. Beijing Key Lab of Mobile Computing and Pervasive Devices, Institute of Computing Technology Chinese Academy of Sciences, Beijing 100190, China;
3. State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310058, China;
4. Department of Computer Science, University of Houston, Houston, TX 77204-3010, U. S. A.
Abstract This article surveys the state of the art crowd simulation techniques and their selected applications, with its focus on our recent research advances in this rapidly growing research field. We first give a concise overview on the mainstream methodologies of crowd simulation. Then, we describe our recent research advances on crowd evacuation, pedestrian crowds, crowd formation, traffic simulation, and swarm simulation. Finally, we offer our own perspectives on open crowd simulation research challenges and point out potential future directions in this area.
This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 61202207, 61100086, 61272298, 61210005, 61472370, 61170214, and 61328204, the National Key Technology Research and Development Program of China under Grant Nos. 2013BAH23F01, 2013BAK03B07, and 2013BAK03B0, the Postdoctoral Science Foundation of China under Grant Nos. 2012M520067 and 2013T60706, the National Nonprofit Industry Specific Program of China under Grant No. 2013467058, and the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20124101120005.
About author: Ming-Liang Xu is an associate
professor in the School of Information Engineering of Zhengzhou University, China, and the secretary
of the Virtual Reality Committee
for the China Society of Image and
Graphics. His research interests include computer animation, virtual
and augment reality, and mobile
computing. Xu got his Ph.D. degree
in computer science and technology from the State Key Lab
of CAD&CG at Zhejiang University in 2012.
Cite this article:
Ming-Liang Xu, Hao Jiang, Xiao-Gang Jin, Zhigang Deng.Crowd Simulation and Its Applications: Recent Advances[J] Journal of Computer Science and Technology, 2014,V29(5): 799-811
 Thalmann D, Musse S. Crowd Simulation (1st edition). Springer-Verlag, 2007. 808 J. Comput. Sci. & Technol., Sept. 2014, Vol.29, No.5  Hawe G I, Coates G, Wilson D T et al. Agent-based simulation for large-scale emergency response: A survey of usage and implementation. ACM Computing Surveys (CSUR), 2012, 45(1): Article No.8. Schelhorn T, O'Sullivan D, Haklay M et al. STREETS: An agent-based pedestrian model. In Proc. the 6th International Conference on Computers in Urban Planning and Urban Management, April 1999. Penn A, Turner A. Space syntax based agent simulation. In Proc. the 1st International Conference on Pedestrian and Evacuation Dynamics, 2001, pp.99-114. Turner A, Penn A. Encoding natural movement as an agentbased system: An investigation into human pedestrian behaviour in the built environment. Environment and Planning B: Planning and Design, 2002, 29(4): 473-490. Thompson P A, Marchant E W. A computer model for the evacuation of large building populations. Fire Safety Journal, 1995, 24(2): 131-148. He G Q, Yang Y, Chen Z H et al. A review of behavior mechanisms and crowd evacuation animation in emergency exercises. Journal of Zhejiang University SCIENCE C, 2013, 14(7): 477-485. Helbing D, Farkas I, Vicsek T. Simulating dynamical features of escape panic. Nature, 2000, 407: 487-490. Bohannon J. Directing the herd: Crowds and the science of evacuation. Science, 2005, 310(5746): 219-221. Henry J, Shum H, Komura T. Interactive formation control in complex environments. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2): 211-222. Wang X, Zhou L, Deng Z et al. Flock morphing animation. Computer Animation and Virtual Worlds, 2014, 25(3/4): 353-362. Henderson L. The statistics of crowd fluids. Nature, 1971, 229(5284): 381-383. MoussaÏd M, Helbing D, Theraulaz G. How simple rules determine pedestrian behavior and crowd disasters. Proceedings of the National Academy of Sciences, 2011, 108(17): 6884-6888. Pelechano N, Badler N I. Modeling crowd and trained leader behavior during building evacuation. IEEE Computer Graphics and Applications, 2006, 26(6): 80-86. Molnár P, Starke J. Control of distributed autonomous robotic systems using principles of pattern formation in nature and pedestrian behavior. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2001, 31(3): 433-435. McPhail C, Powers W T, Tucker C W. Simulating individual and collective action in temporary gatherings. Social Science Computer Review, 1992, 10(1): 1-28. Tucker C W, Schweingruber D, McPhail C. Simulating arcs and rings in gatherings. International Journal of HumanComputer Studies, 1999, 50(6): 581-588. Lin M C, Manocha D. Virtual cityscapes: Recent advances in crowd modeling and traffic simulation. Frontiers of Computer Science in China, 2010, 4(3): 405-416. Sewall J, Wilkie D, Merrell P et al. Continuum traffic simulation. Computer Graphics Forum, 2010, 29(2): 439-448. Lin M, Guy S, Narain R et al. Interactive modeling, simulation and control of large-scale crowds and traffic. In Proc. the 2nd International Workshop Motio in Games (MIG), Nov. 2009, pp.94-103. Lu X, Chen W, Xu M et al. AA-FVDM: An accidentavoidance full velocity difference model for animating realistic street-level traffic in rural scenes. Computer Animation and Virtual Worlds, 2014, 25(1): 83-97. Lu X, Xu M, Chen W et al. Adaptive-AR model with drivers' prediction for traffic simulation. International Journal of Computer Games Technology, 2013, 2013: Article ID 904154. Chao Q, Shen J, Jin X. Video-based personalized traffic learning. Graphical Models, 2013, 75(6): 305-317. Shen J, Jin X. Detailed traffic animation for urban road networks. Graphical Models, 2012, 74(5): 265-282. Wilkie D, Sewall J, Lin M C. Transforming GIS data into functional road models for large-scale traffic simulation. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(6): 890-901. Sewall J, van den Berg J P, Lin M C et al. Virtualized traf-fic: Reconstructing traffic flows from discrete spatiotemporal data. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(1): 26-37. Sewall J, Wilkie D, Lin M C. Interactive hybrid simulation of large-scale traffic. ACM Trans. Graph., 2011, 30(6): Article No.135. Wu J C, Popovi? Z. Realistic modeling of bird flight animations. ACM Transactions on Graphics (TOG), 2003, 22(3): 888-895. Klotsman M, Tal A. Animation of flocks flying in line formations. Artificial Life, 2012, 18(1): 91-105. Wang X, Jin X, Deng Z et al. Inherent noise-aware insect swarm simulation. Computer Graphics Forum, 2014. (to be appeared)  Tu X, Terzopoulos D. Artificial fishes: Physics, locomotion, perception, behavior. In Proc. the 21st ACM SIGGRAPH, July 1994, pp.43-50. Anderson E F, McLoughlin L, Liarokapis F et al. Developing serious games for cultural heritage: A state-of-the-art review. Virtual Reality, 2010, 14(4): 255-275. Schreckenberg M, Sharma S D. Pedestrian and Evacuation Dynamics. Springer-Verlag, 2002. Thalmann D. Populating virtual environments with crowds. In Proc. the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications, June 2006, p.11. Pelechano N, Allbeck J, Badler N I. Virtual Crowds: Methods, Simulation, and Control. Morgan and Claypool Publishers. Pettré J, Kallmann M, Lin M C. Motion planning and autonomy for virtual humans class notes. In Proc. ACM SIGGRAPH 2008 Classes, Aug. 2008, Article No.42. Shopf J, Barczak J, Oat C et al. March of the Froblins: Simulation and rendering massive crowds of intelligent and detailed creatures on GPU. In Proc. ACM SIGGRAPH 2008 Games, Aug. 2008, pp.52-101. Huerre S, Lee J, Lin M et al. Simulating believable crowd and group behaviors. In Proc. ACM SIGGRAPH Asia 2010 Courses, Dec. 2010, Article No.13. Zhou S, Chen D, Cai W et al. Crowd modeling and simulation technologies. ACM Transactions on Modeling and Computer Simulation (TOMACS), 2010, 20(4): Article No.20. Kapadia M, Badler N I. Navigation and steering for autonomous virtual humans. Wiley Interdisciplinary Reviews: Cognitive Science, 2013, 4(3): 263-272. Hughes R L. A continuum theory for the flow of pedestrians. Transportation Research Part B: Methodological, 2002, 36(6): 507-535. Hughes R L. The flow of human crowds. Annual Review of Fluid Mechanics, 2003, 35: 169-182. Treuille A, Cooper S, Popovic Z. Continuum crowds. In Proc. ACM SIGGRAPH 2006, July 2006, pp.1160-1168. Narain R, Golas A, Curtis S et al. Aggregate dynamics for dense crowd simulation. ACM Trans. Graph., 2009, 28(5): Article No. 122. Reynolds C W. Flocks, herds and schools: A distributed behavioral model. In Proc. the 14th ACM SIGGRAPH, July 1987, pp.25-34. Reynolds C W. Steering behaviors for autonomous characters. In Proc. Game Developers Conference, Mar. 1999. Ming-Liang Xu et al.: Crowd Simulation and Its Applications: Recent Advances 809  Helbing D, Molnar P. Social force model for pedestrian dynamics. Physical Review E, 1995, 51(5): 4282-4286. Cordeiro O C, Braun A, Silveria C B et al. Concurrency on social forces simulation model. In Proc. the 1st International Workshop on Crowd Simulation, Nov. 2005. Gayle R, Moss W, Lin M C et al. Multi-robot coordination using generalized social potential fields. In Proc. IEEE International Conference on Robotics and Automation, May 2009, pp.106-113. Pelechano N, Allbeck J M, Badler N I. Controlling individual agents in high-density crowd simulation. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2007, pp.99-108. HeÏgeas L, Luciani A, Thollot J et al. A physically-based particle model of emergent crowd behaviors. arXiv Preprint arXiv:1005.4405, 2010. Lakoba T I, Kaup D J, Finkelstein N M. Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution. Simulation, 2005, 81(5): 339-352. Sugiyama Y, Nakayama A, Hasebe K. 2-dimensional optimal velocity models for granular flows. In Pedestrian and Evacuation Dynamics, Schreckenberg M, Sharma SD (eds.), 2001, pp.155-160. Sud A, Gayle R, Anderson E et al. Real-time navigation of independent agents using adaptive roadmaps. In Proc. the 2007 ACM Symposium on Virtual Reality Software and Technology, Oct. 2007, pp.99-106. Guy S J, Kim S, Lin M C et al. Simulating heterogeneous crowd behaviors using personality trait theory. In Proc. the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2011, pp.43-52. DurupÏnar F, Pelechano N, Allbeck J M et al. How the ocean personality model affects the perception of crowds. IEEE Comput. Graph. App., 2011, 31(3): 22-31. Pelechano N, O'brien K, Badler N et al. Crowd simulation incorporating agent psychological models, roles and communication. In Proc. the 1st International Workshop on Crowd Simulation, Nov. 2005, pp.21-30. DurupÏnar F. From audiences to mobs: Crowd simulation with psychological factors [Ph.D. Thesis]. Institute of Engineering and Science, Bilkent University, 2010. Beltaief O, Hadouaj S, Ghedira K. Multi-agent simulation model of pedestrians crowd based on psychological theories. In Proc. the 4th International Conference on Logistics (LOGISTIQUA), May 31-June 3, 2011, pp. 150-156. Kim S, Guy S J, Manocha D et al. Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory. In Proc. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, March 2012, pp.55-62. Loscos C, Marchal D, Meyer A. Intuitive crowd behaviour in dense urban environments using local laws. In Proc. Theory of Practice of Computer Graphics 2003, June 2003, pp.122-129. Alexa M, Muller W. Representing animations by principal components. Computer Graphics Forum, 2000, 19(3): 411-418. Guy S J, Chhugani J, Curtis S et al. PLEdestrians: A leasteffort approach to crowd simulation. In Proc. the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 2010, pp.119-128. Guy S J, Curtis S, Lin M C et al. Least-effort trajectories lead to emergent crowd behaviors. Physical review E, 2012, 85(1): 016110. Musse S R, Thalmann D. A model of human crowd behavior: Group inter-relationship and collision detection analysis. In Proc. Eurographics Workshop on Computer Animation and Simulation, Sept. 1997, pp.39-51. Sung M, Gleicher M, Chenney S. Scalable behaviors for crowd simulation. Computer Graphics Forum, 2004, 23(3): 519-528. Fiorini P, Shiller Z. Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 1998, 17(7): 760-772. Sud A, Anderson E, Curtis S et al. Real-time path planning in dynamic virtual environments using multiagent navigation graphs. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(3): 526-538. van den Berg J, Patil S, Sewall J et al. Interactive navigation of multiple agents in crowded environments. In Proc. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D), Feb. 2008, pp.139-147. Guy S J, Chhugani J, Kim C et al. ClearPath: Highly parallel collision avoidance for multi-agent simulation. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), Aug. 2009, pp.177-187. van den Berg J, Lin M, Manocha D et al. Centralized path planning for multiple robots: Optimal decoupling into sequential plans. Robotics: Science and Systems (RSS), 2009. Zheng L, Zhao J, Cheng Y et al. Geometry-constrained crowd formation animation. Computers & Graphics, 2014, 38: 268-276. Golas A, Narain R, Lin M. Hybrid long-range collision avoidance for crowd simulation. In Proc. the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, March 2013, pp.29-36. Lv L, Mao T, Liu X et al. Optimization-based group performance deducing. Computer Animation and Virtual Worlds, 2014, 25(2): 171-184. Patil S, van den Berg J, Curtis S et al. Directing crowd simulations using navigation fields. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(2): 244-254. Pettré J, Ondrej J, Olivier A H et al. Experiment-based modeling, simulation and validation of interactions between virtual walkers. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2009, pp.189-198. Kim S, Guy S J, Manocha D. Velocity-based modeling of physical interactions in multi-agent simulations. In Proc. the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 2013, pp.125-133. Wilkie D, Sewall J, Lin M. Flow reconstruction for datadriven traffic simulation. ACM Trans. Graph, 2013, 32(4): Article No.89. Wolinski D, Guy S J, Olivier A H et al. Parameter estimation and comparative evaluation of crowd simulations. Computer Graphics Forum, 2014, 33(2): 303-312. Kapadia M, Singh S, Hewlett W et al. Egocentric affordance fields in pedestrian steering. In Proc. the 2009 Symposium on Interactive 3D Graphics and Games, Feb. 2009, pp.215-223. Yu Q, Terzopoulos D. A decision network framework for the behavioral animation of virtual humans. In Proc. the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2007, pp.119-128. Kulpa R, Olivier A H, Ondrej J et al. Imperceptible relaxation of collision avoidance constraints in virtual crowds. ACM Trans. Graph., 2011, 30(6): Article No.138. Ond?ej J, Pettre J, Olivier A H et al. A synthetic-vision based steering approach for crowd simulation. ACM Transactions on Graphics (TOG), 2010, 29(4): Article No.123. Metoyer R A, Hodgins J K. Reactive pedestrian path following from examples. The Visual Computer, 2004, 20(10): 635-649. Lee K H, Choi M G, Hong Q et al. Group behavior from video: A data-driven approach to crowd simulation. In Proc. the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2007, pp.109-118. 810 J. Comput. Sci. & Technol., Sept. 2014, Vol.29, No.5  Lerner A, Chrysanthou Y, Lischinski D. Crowds by example. Computer Graphics Forum, 2007, 26(3): 655-664. Li Y, Christie M, Siret O et al. Cloning crowd motions. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 2012, pp.201-210. Ju E, Choi M G, Park M et al. Morphable crowds. ACM Transactions on Graphics (TOG), 2010, 29(6): Article No.140. Flagg M, Rehg J M. Video-based crowd synthesis. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(11): 1935-1947. Sun L, Li X, Qin W. Simulating realistic crowd based on agent trajectories. Computer Animation and Virtual Worlds, 2013, 24(3/4): 165-172. Kwon T, Lee K H, Lee J et al. Group motion editing. ACM Transactions on Graphics (TOG), 2008, 27(3): Article No.80. Lerner A, Fitusi E, Chrysanthou Y et al. Fitting behaviors to pedestrian simulations. In Proc. the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2009, pp.199-208. Guy S J, van den Berg J, Liu W et al. A statistical similarity measure for aggregate crowd dynamics. ACM Transactions on Graphics (TOG), 2012, 31(6): Article No.190. Lai Y C, Chenney S, Fan S. Group motion graphs. In Proc. the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 2005, pp.281-290. Courty N, Corpetti T. Crowd motion capture. Computer Animation and Virtual Worlds, 2007, 18(4-5): 361-370. Paris S, Pettré J, Donikian S. Pedestrian reactive navigation for crowd simulation: A predictive approach. Computer Graphics Forum, 2007, 26(3): 665-674. Chenney S. Flow tiles. In Proc. the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug. 2004, pp.233-242. Pelkey C D, Allbeck J M. Populating virtual semantic environments. Computer Animation and Virtual Worlds, 2014, 24(3/4): 405-412. Kraayenbrink N, Kessing J, Tutenel T et al. Semantic crowds. Entertainment Computing, 2014. (to be appeared)  Golas A, Narain R, Lin M. Hybrid long-range collision avoidance for crowd simulation. In Proc. the 2013 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, March 2013, pp.29-36. Kim S, Guy S J, Lin M C et al. Predicting pedestrian trajectories using velocity-space reasoning. In Proc. the 10th Workshop on the Algorithm Foundations of Robotics, June 2012, pp. 609-623. Yeh H, Curtis S, Patil S et al. Composite agents. In Proc. the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 2008, pp. 39-47. Lemercier S, Jelic A, Kupla R et al. Realistic following behaviors for crowd simulation. Computer Graphics Forum, 2012, 31(2): 489-498. Karamouzas I, Overmars M. Simulating and evaluating the local behavior of small pedestrian groups. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(3): 394-406. Mao T, Jiang H, Xia S et al. Recent advances on human crowd simulation. International Journal of Virtual Reality, 2010, 9(3): 27-32. Jiang H, Xu W, Mao T et al. Continuum crowd simulation in complex environments. Computers & Graphics, 2010, 34(5): 537-544. Jiang H, Xu W, Mao T et al. Crowds flow in complex environment. In Proc. the 11th IEEE International Conference on Computer-Aided Design and Computer Graphics, Aug. 2009, pp. 54-57. Jiang H, Xu W, Mao T et al. A semantic environment model for crowd simulation in multilayered complex environment. In Proc. the 16th ACM Symposium on Virtual Reality Software and Technology, Nov. 2009, pp.191-198. Mao T, Ye Q, Jiang H et al. Evoking panic in crowd simulation. Transactions on Edutainment VI, Pan Z, Cheok A D, Müller W (Eds.), 2011, pp.79-88. Jin X, Xu J, Wang C C L et al. Interactive control of largecrowd navigation in virtual environments using vector fields. IEEE Computer Graphics and Applications, 2008, 28(6): 37-46. Jin X, Wang C C L, Huang S et al. Interactive control of real-time crowd navigation in virtual environment. In Proc. the 2007 ACM Symposium on Virtual Reality Software and Technology, Nov. 2007, pp.109-112. Gu Q, Deng Z. Context-aware motion diversification for crowd simulation. IEEE Computer Graphics and Applications, 2011, 31(5): 54-65. Gu Q, Deng Z. Generating freestyle group formations in agent-based crowd simulations. IEEE Computer Graphics and Applications, 2013, 33(1): 20-31. Zhang M, Xu M, Han L et al. Virtual Network Marathon with immersion, scientificalness, competitiveness, adaptability and learning. Computers & Graphics, 2012, 36(3): 185-192. Xu J, Jin X, Yu Y et al. Shape-constrained flock animation. Computer Animation and Virtual Worlds, 2008, 19(3/4): 319-330. Xu M, Wu Y, Ye Y. Smooth and efficient crowd transformation. In Proc. the 20th ACM International Conference on Multimedia, Oct. 2012, pp.1189-1192. Xu M, Wu Y, Ye Y et al. Collective crowd formation transform with mutual information based runtime feedback. Computer Graphics Forum, 2014. (to be appeared)  Aw A, Rascle M. Resurrection of \second order" models of traffic flow. SIAM Journal on Applied Mathematics, 2000, 60(3): 916-938.
Copyright 2010 by Journal of Computer Science and Technology