Crowd modeling and simulation technologies

Abstract

As a collective and highly dynamic social group, the human crowd is a fascinating phenomenon that has been frequently studied by experts from various areas. Recently, computer-based modeling and simulation technologies have emerged to support investigation of the dynamics of crowds, such as a crowd's behaviors under normal and emergent situations. This article assesses the major existing technologies for crowd modeling and simulation. We first propose a two-dimensional categorization mechanism to classify existing work depending on the size of crowds and the time-scale of the crowd phenomena of interest. Four evaluation criteria have also been introduced to evaluate existing crowd simulation systems from the point of view of both a modeler and an end-user.

We have discussed some influential existing work in crowd modeling and simulation regarding their major features, performance as well as the technologies used in this work. We have also discussed some open problems in the area. This article will provide the researchers with useful information and insights on the state of the art of the technologies in crowd modeling and simulation as well as future research directions.

References

1. AG, S. S. 2009. Simwalk transport. White paper. http://www.simwalk.com/simwalk_transport/whitepapers/simwalk_trans_09_e.pdf.
2. Aguirre, B. E. 2005. Emergency evacuation, panic, and social psychology: Comment on understanding mass panic and other collective responses to threat and disaster. Psychiatry 68, 2.
3. Antonini, G., Bierlaire, M., and Weber, M. 2006. Discrete choice models of pedestrian walking behavior. Transport. Resear. Part B 40, 667--687.
4. Arentze, T. and Timmermans, H. 2009. A need-based model of multi-day, multi-party activity generation. Transport. Resear. Part B 43, 251--265.
5. Arentze, T., Timmermans, H., Janssens, D., and Wets, G. 2006. Modeling short-term dynamics in activity-travel patterns: from aurora to feathers. In Proceedings of the Innovations in Travel Demand Modeling Conference. 71--77.
6. Bandini, S., Federici, M. L., and Vizzari, G. 2007. Situated cellular agents approach to crowd modeling and simulation. Cybernetics Syst. 38, 7, 729--753.
7. Batty, M. 2009. Agent-based pedestrian modelling. http://eprints.ucl.ac.uk/237/1/paper61.pdf.
8. Batty, M., Desyllas, J., and Duxbury, E. 2003. The discrete dynamics of small-scale spatial events: Agent-based models of mobility in carnivals and street parades. Int. J. Geograph. Inform. Science 17, 7, 673--697.
9. Boston Dynamics. 2009. Di-guy. http://www.diguy.com/diguy/.
10. Braun, A., Bodmann, B. E. J., and Musse, S. R. 2005. Simulating virtual crowds in emergency situations. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology. 244--252.
11. Burstedde, C., Klauck, K., Schadschneider, A., and Zittartz, J. 2001. Simulation of pedestrian dynamics using a two-dimensional cellular automaton. Physica A: Stat. Mechanics Its Appl. 295, 3-4, 507--525.
12. Chenney, S. 2004. Flow tiles. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233--242.
13. Crowd Dynamics Pte Ltd. 2009a. Crowd disasters. http://www.crowddynamics.com/Main/Crowddisasters.html.
14. Crowd Dynamics Pte Ltd. 2009b. Crowd dynamics. http://www.crowddynamics.com/.
15. de Heras Ciechomski, P., Schertenleib, S., Maim, J., and Thalmann, D. 2005. Reviving the roman odeon of aphrodisias: Dynamic animation and variety control of crowds in virtual heritage. In Proceedings of the 11th International Conference on Virtual Systems and Multimedia.
16. Dechter, R. and Pearl, J. 1985. Generalized best-first search strategies and the optimality of a*. J. ACM 32, 3, 505--536.
17. Deffuant, G. 2006. Comparing extremism propagation patterns in continuous opinion models. J. Artif. Societies Social Simul. 9, 3.
18. Deffuant, G., Amblard, F., Weisbuch, G., and Faure, T. 2002. How can extremism prevail? a study based on the relative agreement interaction model. J. Artif. Societies Social Simul. 5, 4.
19. Fan, X., Sun, S., McNeese, M., and Yen, J. 2005. Extending recognition-primed decision model for human-agent collaboration. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS'05). 945--952.
20. Fang, Z., Yuan, J., Wang, Y., and Lo, S. 2008. Survey of pedestrian movement and development of a crowd dynamics model. Fire Safety J. 43, 459--465.
21. Festinger, L. 1954. A theory of social comparison processes. Human Relations 7, 2, 117--140.
22. Funge, J., Tu, X., and Terzopoulos, D. 1999. Cognitive modeling: knowledge, reasoning and planning for intelligent characters. In Proceedings of the 26th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'99). 29--38.
23. Galea, E. 1998. A general approach to validating evacuation models with an application to exodus. J. Fire Sciences 16, 6, 414--436.
24. Galea, E. R. and Galparsoro, J. M. P. 1993. Exodus: An evacuation model for mass transport vehicles. UK CAA Paper 93 006 ISBN 0 86039 543X. http://fseg.gre.ac.uk/exodus.
25. Gilbert, N. 2007. A generic model of collectivities. http://epubs.surrey.ac.uk/cress/14.
26. Gratch, J. and Marsella, S. 2004. A domain-independent framework for modeling emotion. J. Cognitive Syst. Resear. 5, 4, 269--306.
27. Helbing, D., Farkas, I., and Vicsek, T. 2000. Simulating dynamical features of escape panic. Letters to Nature 407, 487--490.
28. Hughes, R. L. 2003. The flow of human crowds. Ann. Rev. Fluid Mechanics 35, 169--182.
29. Kaminka, G. A. and Fridman, N. 2006. A cognitive model of crowd behavior based on social comparison theory. In Proceedings of the AAAI Workshop on Cognitive Modeling and Agent-Based Social Simulation.
30. Kisko, T. M., Francis, R. L., and Nobel, C. R. 1998. Evacnet4 user's guide. http://www.ise. ufl.edu/kisko/files/evacnet/EVAC4UG.HTM.
31. Klein, G. 1998. Sources of Power: How People Make Decisions. MIT Press, Cambridge, MA.
32. Klugl, F. 2008. A validation methodology for agent-based simulations. In Proceedings of the 23rd Annual ACM Symposium on Applied Computing (SAC'08). 39--43.
33. Klugl, F. and Rindsfuser, G. 2007. Large-scale agent-based pedestrian simulation. In Lecture Notes in Computer Science, vol. 4687, 145--156.
34. Klupfel, H. 2007. The simulation of crowds at very large events. In Traffic and Granular Flow'05. Springer, Berlin, 341--346.
35. Lebbink, H. J., Witteman, C. L. M., and Meyer, J.-J. C. 2005. Tutorial on agent-based modeling and simulation. In Proceedings of the Winter Simulation Conference. 2--15.
36. Lee, K. H., Choi, M. G., Hong, Q., and Lee, J. 2007. Group behavior from video: A data-driven approach to crowd simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'07). 109--118.
37. Lerner, A., Chrysanthou, Y., and Lischinski, D. 2007. Crowds by example. Comput. Graph. Forum 26, 3, 655--664.
38. Loewenstein, G. and Lerner, J. 2003. Handbook of Affective Science. Oxford University Press, Oxford, UK.
39. Luo, L., Zhou, S., Cai, W., Low, M. Y. H., Tian, F., Wang, Y., Xiao, X., and Chen, D. 2008. Agent-based human behavior modeling for crowd simulation. Comput. Anim. Virtual Worlds 19, 3-4, 271--281.
40. Maim, J., Haegler, S., Yersin, B., Muller, P., Thalmann, D., and Gool, L. V. 2007. Populating ancient pompeii with crowds of virtual romans. In Proceedings of the 8th International Symposium on Virtual Reality, Archeology and Cultural Heritage (VAST'07).
41. Massive Software. 2009. Massive. http://www.massivesoftware.com.
42. Mawson, A. R. 2005. Understanding mass panic and other collective responses to threat and disaster. Psychiatry 68, 2.
43. McDonald, D., Lazarus, R., Leung, A., and Hussain, T. 2006. Interoperable human behavior models for simulations. In Proceedings of the Behavior Representation in Modeling and Simulation Conference (BRIMS).
44. McKenzie, F. D., Nguyen, Q.-A. H., and Petty, M. D. 2004. Crowd federate architecture and api design. In Proceedings of the Fall Simulation Interoperability Workshop. 574--587.
45. Miller, J. H. and Page, S. E. 2007. Complex Adaptive Systems: An Introduction to Computational Models of Social Life. Princeton University Press, Princeton, NJ.
46. Morini, F., Yersin, B., Maim, J., and Thalmann, D. 2007. Real-time scalable motion planning for crowds. In Proceedings of the International Conference on Cyberworlds (CyberWorlds'07). 144--151.
47. Musse, S. R. and Thalmann, D. 2001. Hierarchical model for real time simulation of virtual human crowds. IEEE Trans. Visualiz. Comput. Graph. 7, 2, 152--164.
48. Nguyen, Q.-A. H., McKenzie, F. D., and Petty, M. D. 2005. Crowd behavior cognitive model architecture design. In Proceedings of the Conference on Behavior Representation in Modeling and Simulation (BRIMS). 55--64.
49. Ortony, A., Clore, G., and Collins, A. 1988. The Cognitive Structure of Emotion. Cambridge University Press, Cambridge, UK.
50. Pan, X., Han, C. S., and Law, K. H. 2005. A multi-agent based simulation framework for the study of human and social behavior in egress analysis. In Proceedings of the International Conference on Computing in Civil Engineering. 12--15.
51. Paris, S., Donikian, S., and Bonvalet, N. 2006. Environmental abstraction and path planning techniques for realistic crowd simulation. Computer Animat. Virtual Worlds 17, 3-4, 325--335.
52. Pelechano, N., Allbeck, J., and Badler, N. 2007. Controlling individual agents in high-density crowd simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'07). 99--108.
53. Pelechano, N., Allbeck, J. M., and Badler, N. I. 2008. Virtual Crowds: Methods, Simulation, and Control. Morgan & Claypool.
54. Pelechano, N. and Badler, N. 2006. Modeling crowd and trained leader behavior during building evacuation. IEEE Comput. Graphics and Appl. 26, 6.
55. Pelechano, N., Oùflbrien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. In Proceedings of the 1st International Workshop on Crowd Simulation (V-CROWDS'05).
56. Pettre, J., de Heras Ciechomski, P., Maim, J., Yersin, B., Laumond, J.-P., and Thalmann, D. 2006. Real-time navigating crowds: Scalable simulation and rendering. Comput. Anim. Virtual Worlds 17, 445--455.
57. Pettre, J., Grillon, H., and Thalmann, D. 2007. Crowds of moving objects: Navigation planning and simulation. In Proceedings of the IEEE International Conference on Robotics and Automation.
58. Petty, M. D., McKenzie, F. D., Gaskins, R. C., and Weisel, E. W. 2004. Developing a crowd federate for military simulation. In Proceedings of the Spring Simulation Interoperability Workshop (SIW). 483--493.
59. Petty, M. D., McKenzie, F. D., and III, R. C. G. 2003. Requirements, psychological models, and design issues in crowd modeling for military simulation. In Proceedings of the Huntsville Simulation Conference.
60. Presagis. 2009. Ai.implant. http://www.presagis.com/products/simulation/aiimplant/.
61. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. In Proceedings of the ACM SIGGRAPH Conference. 25--34.
62. Salzarulo, L. 2006. A continuous opinion dynamics model based on the principle of meta-contrast. J. Artif. Societies Social Simul. 9, 1.
63. Santos, G. and Aguirre, B. E. 2004. A critical review of emergency evacuation simulation models. In Proceedings of the NIST Workshop on Building Occupant Movement during Fire Emergencies. 25--50.
64. Seyfried, A., Steffen, B., and Klingsch, W. 2005. The fundamental diagram of pedestrian movement revisisted. J. Stat. Mechanics: Theory Exper.
65. Shao, W. and Terzopoulos, D. 2005a. Autonomous pedestrians. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Computer Animation. 19--28.
66. Shao, W. and Terzopoulos, D. 2005b. Environmental modeling for autonomous virtual pedestrians. In Proceedings of the SAE Symposium on Digital Human Modeling for Design and Engineering. 420--433.
67. Shao, W. and Terzopoulos, D. 2006. Populating reconstructed archaeological sites with autonomous virtual humans. In Proceedings of the 6th International Conference on Intelligent Virtual Agents (IVA'06). 420--433.
68. Silverman, B. G., Bharathy, G., O'Brien, K., and Cornwell, J. 2006. Human behavior models for agents in simulators and games: Part ii: Gamebot engineering with pmfserv. Presence 15, 2, 163--185.
69. Silverman, B. G., Johns, M., Cornwell, J., and O'Brien, K. 2006. Human behavior models for agents in simulators and games: Part i: Enabling science with pmfserv. Presence 15, 2, 139--162.
70. Singh, S., Kapadia, M., Faloutsos, P., and Reinman, G. 2009. Steerbench: A benchmark suite for evaluating steering behaviors. Comput. Anim. Virtual Worlds 20, 5-6, 533--548.
71. Sipser, M. 2005. Introduction to the Theory of Computation 2nd Ed. PWS Publishing Company, Boston, MA.
72. Stauffer, D. 2005. Sociophysics simulations ii: Opinion dynamics. http://www.citebase.org/abstract?id=oai:arXiv.org:physics/0503115.
73. Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Comput. Graph. Forum 23, 3, 519--528.
74. Ting, S. and Zhou, S. 2008. Snap: A time critical decision-making framework for mout simulations. Comput. Anim. Virtual Worlds 19, 3-4, 505--514.
75. Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. In Proceedings of the 33rd International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'06). 1160--1168.
76. Tu, X. and Terzopoulos, D. 1994. Artificial fishes: physics, locomotion, perception, behavior. In Proceedings of the 21st International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'94). 43--50.
77. Turner, J. C., Hogg, M. A., Oakes, P. J., Reicher, S. D., and Wetherell, M. S. 1989. Rediscovering the social group: A self-categorization theory. Amer. J. Sociol. 94, 1514--1516.
78. Turner, R. H. and Killian, L. M. 1987. Collective behavior. Prentice Hall, Englewood Cliffs.
79. Ulicny, B. and Thalmann, D. 2001. Crowd simulation for interactive virtual environments and vr training systems. In Proceedings of the Eurographics Workshop on Animation and Simulation. 163--170.
80. Yersin, B., Maim, J., de Heras Ciechomski, P., Schertenleib, S., and Thalmann, D. 2005. Steering a virtual crowd based on a semantically augmented navigation graph. In Proceedings of the 1st International Workshop on Crowd Simulation (V-CROWDS'05). 169--178.
81. Yersin, B., Pettre, J., and Thalmann, D. 2009. Crowd patches: Populating large-scale virtual environments for real-time applications. In Proceedings of the ACM/SIGRAPH Symposium on Interactive 3D graphics and games (I3D'09). 207--214.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Stochastic games

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

    • Simulation types and techniques

      • Simulation by animation

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design