“Aggregate dynamics for dense crowd simulation”
Conference:
Type(s):
Title:
- Aggregate dynamics for dense crowd simulation
Session/Category Title: Physically based animation
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Large dense crowds show aggregate behavior with reduced individual freedom of movement. We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the continuous setting, we introduce a novel variational constraint called unilateral incompressibility, to model the large-scale behavior of the crowd, and accelerate inter-agent collision avoidance in dense scenarios. This approach makes it possible to simulate very large, dense crowds composed of up to a hundred thousand agents at near-interactive rates on desktop computers.
References:
1. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. 26, 3, 100. Google ScholarDigital Library
2. Bayazit, O. B., Lien, J.-M., and Amato, N. M. 2002. Better group behaviors in complex environments with global roadmaps. Proc. 8th Intl. Conf. Artificial Life, 362–370. Google ScholarDigital Library
3. Bridson, R., and Müller-Fischer, M. 2007. Fluid simulation. In ACM SIGGRAPH 2007 courses, 1–81. Google ScholarDigital Library
4. Chenney, S. 2004. Flow tiles. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233–242. Google ScholarDigital Library
5. Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., and Cavalheiro, G. G. 2005. Concurrency on social forces simulation model. First Intl. Workshop on Crowd Simulation.Google Scholar
6. Dostál, Z., and Schöberl, J. 2005. Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination. Comput. Optim. Appl. 30, 1, 23–43. Google ScholarDigital Library
7. Feurtey, F. 2000. Simulating the Collision Avoidance Behavior of Pedestrians. Master’s thesis, University of Tokyo, School of Engineering.Google Scholar
8. Fiorini, P., and Shiller, Z. 1998. Motion planning in dynamic environments using velocity obstacles. Intl. J. on Robotics Research 17, 7, 760–772.Google ScholarCross Ref
9. Funge, J., TU, X., and Terzopoulos, D. 1999. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proc. of ACM SIGGRAPH, 29–38. Google ScholarDigital Library
10. Gayle, R., Moss, W., Lin, M. C., and Manocha, D. 2009. Multi-robot coordination using generalized social potential fields. Proc. IEEE Conf. Robotics and Automation. Google ScholarDigital Library
11. Guy, S., Chhugani, J., Kim, C., Satish, N., Lin, M. C., Manocha, D., and Dubey, P. 2009. Clearpath: Highly parallel collision avoidance for multi-agent simulation. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
12. Harlow, F. H. 1963. The particle-in-cell method for numerical simulation of problems in fluid dynamics. In Proc. Symp. Appl. Math., vol. 15.Google Scholar
13. Heigeas, L., Luciani, A., Thollot, J., and Castagné, N. 2003. A physically-based particle model of emergent crowd behaviors. Proc. Graphikon ’03 2.Google Scholar
14. Helbing, D., and Molnár, P. 1995. Social force model for pedestrian dynamics. Physical Review E 51 (May), 4282.Google ScholarCross Ref
15. Helbing, D., Buzna, L., Johansson, A., and Werner, T. 2005. Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Sci. 39, 1–24. Google ScholarDigital Library
16. Hughes, R. L. 2003. The flow of human crowds. Annu. Rev. Fluid Mech. 35, 169–182.Google ScholarCross Ref
17. Kamphuis, A., and Overmars, M. 2004. Finding paths for coherent groups using clearance. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 19–28. Google ScholarDigital Library
18. Kerr, W., and Spears, D. 2005. Robotic simulation of gases for a surveillance task. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (Aug.), 2905–2910.Google Scholar
19. Lakoba, T. I., Kaup, D. J., and Finkelstein, N. M. 2005. Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution. SIMULATION 81, 339. Google ScholarDigital Library
20. Lamarche, F., and Donikian, S. 2004. Crowd of virtual humans: a new approach for real-time navigation in complex and structured environments. Computer Graphics Forum 23, 3, 509–518.Google ScholarCross Ref
21. Lin, M. C., Guy, S., Narain, R., Sewall, J., Patil, S., Chhugani, J., Golas, A., den Berg, J. V., Curtis, S., Wilkie, D., Merrell, P., Kim, C., Satish, N., Dubey, P., and Manocha, D. 2009. Interactive modeling, simulation and control of large-scale crowds and traffic. Proc. Workshop on Motion in Games (Springer-Verlag Lecture Notes in Computer Science Series). Google ScholarDigital Library
22. Loscos, C., Marchal, D., and Meyer, A. 2003. Intuitive crowd behaviour in dense urban environments using local laws. In Theory and Practice of Computer Graphics, 122–129. Google ScholarDigital Library
23. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Trans. Graph. 28, 3, 62. Google ScholarDigital Library
24. Metoyer, R. A., and Hodgins, J. K. 2003. Reactive pedestrian path following from examples. In Proc. 16th Int. Conf. Computer Animation and Social Agents, 149. Google ScholarDigital Library
25. Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 39–51.Google Scholar
26. Paris, S., Pettre, J., and Donikian, S. 2007. Pedestrian reactive navigation for crowd simulation: a predictive approach. Computer Graphics Forum 26, 3 (September), 665–674.Google ScholarCross Ref
27. Pelechano, N., O’Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. First Intl. Workshop on Crowd Simulation.Google Scholar
28. Pelechano, N., Allbeck, J. M., and Badler, N. I. 2008. Virtual Crowds: Methods, Simulation and Control. Morgan and Claypool Publishers.Google ScholarDigital Library
29. Pettré, J., Laumond, J.-P., and Thalmann, D. 2005. A navigation graph for real-time crowd animation on multilayered and uneven terrain. First Intl. Workshop on Crowd Simulation, 81–90.Google Scholar
30. Pettré, J., Kallmann, M., and Lin, M. C. 2008. Motion planning and autonomy for virtual humans. In ACM SIGGRAPH 2008 classes, 1–31. Google ScholarDigital Library
31. Pimenta, K., Michael, N., Mesquita, R., Pereira, G., and Kumar, V. 2008. Control of swarms based on hydrodynamic models. Proc. IEEE Int. Conf. Robotics and Automation (May), 1948–1953.Google Scholar
32. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH 21, 25–34. Google ScholarDigital Library
33. Reynolds, C. W. 1999. Steering behaviors for autonomous characters. Game Developers Conference 1999.Google Scholar
34. Schreckenberg, M., and Sharma, S. D. 2001. Pedestrian and Evacuation Dynamics. Springer.Google Scholar
35. Shao, W., and Terzopoulos, D. 2007. Autonomous pedestrians. Graph. Models 69, 5–6, 246–274. Google ScholarDigital Library
36. Shimizu, M., Ishiguro, A., Kawakatsu, T., Masubuchi, Y., and Doi, M. 2003. Coherent swarming from local interaction by exploiting molecular dynamics and Stokesian dynamics methods. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems 2 (Oct.), 1614–1619 vol. 2.Google Scholar
37. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2008. Globally coupled impulse-based collision handling for cloth simulation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
38. Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M., and Manocha, D. 2007. Real-time navigation of independent agents using adaptive roadmaps. In Proc. ACM Symp. Virtual Reality Software and Technology, 99–106. Google ScholarDigital Library
39. Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2008. Real-time path planning in dynamic virtual environments using multi-agent navigation graphs. IEEE Trans. Visualization and Computer Graphics 14, 3, 526–538. Google ScholarDigital Library
40. Sugiyama, Y., Nakayama, A., and Hasebe, K. 2001. 2-dimensional optimal velocity models for granular flows. In Pedestrian and Evacuation Dynamics, 155–160.Google Scholar
41. Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 (Sept), 519–528.Google ScholarCross Ref
42. Thalmann, D., O’Sullivan, C., Ciechomski, P., and Dobbyn, S. 2006. Populating Virtual Environments with Crowds. Eurographics 2006 Tutorial Notes.Google Scholar
43. Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. ACM Trans. Graph. 25, 3, 1160–1168. Google ScholarDigital Library
44. van den Berg, J., Lin, M. C., and Manocha, D. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. Proc. IEEE Conf. Robotics and Automation, 1928–1935.Google Scholar
45. van den Berg, J., Patil, S., Seawall, J., Manocha, D., and Lin, M. C. 2008. Interactive navigation of individual agents in crowded environments. Proc. ACM Symposium on Interactive 3D Graphics and Games, 139–147. Google ScholarDigital Library
46. van den Berg, J., Guy, S. J., Lin, M. C., and Manocha, D. 2009. Reciprocal n-body collision avoidance. Proc. Intl. Symposium on Robotics Research.Google Scholar
47. Yeh, H., Curtis, S., Patil, S., van den Berg, J., Manocha, D., and Lin, M. C. 2008. Composite agents. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
48. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. In Proc. ACM SIGGRAPH, 965–972. Google ScholarDigital Library
