“Implicit crowds: optimization integrator for robust crowd simulation”

Large multi-agent systems such as crowds involve inter-agent interactions that are typically anticipatory in nature, depending strongly on both the positions and the velocities of agents. We show how the nonlinear, anticipatory forces seen in multi-agent systems can be made compatible with recent work on energy-based formulations in physics-based animation, and propose a simple and effective optimization-based integration scheme for implicit integration of such systems. We apply this approach to crowd simulation by using a state-of-the-art model derived from a recent analysis of human crowd data, and adapting it to our framework. Our approach provides, for the first time, guaranteed collision-free motion while simultaneously maintaining high-quality collective behavior in a way that is insensitive to simulation parameters such as time step size and crowd density. These benefits are demonstrated through simulation results on various challenging scenarios and validation against real-world crowd data.

1. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’98). ACM, 43–54. Google ScholarDigital Library
2. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Transaction on Graphics (2014), 154:1–154:11.Google ScholarDigital Library
3. Panayiotis Charalambous and Yiorgos Chrysanthou. 2014. The PAG Crowd: A Graph Based Approach for Efficient Data-Driven Crowd Simulation. Computer Graphics Forum 33, 8 (2014), 95–108. Google ScholarDigital Library
4. Panayiotis Charalambous, Ioannis Karamouzas, Stephen J. Guy, and Yiorgos Chrysanthou. 2014. A Data-Driven Framework for Visual Crowd Analysis. Computer Graphics Forum 33, 7 (2014), 41–50. Google ScholarDigital Library
5. Teófilo Dutra, Ricardo Marques, Joaquim B. Cavalcante-Neto, Creto Augusto Vidal, and Julien Pettré. 2017. Gradient-based steering for vision-based crowd simulation algorithms. Computer Graphics Forum 36, 2 (2017). Google ScholarCross Ref
6. Paolo Fiorini and Zvi Shiller. 1998. Motion Planning in Dynamic Environments using Velocity Obstacles. The International Journal of Robotics Research 17, 7 (1998), 760–772. Google ScholarCross Ref
7. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A Practical Gauss-seidel Method for Stable Soft Body Dynamics. ACM Transaction on Graphics 35, 6 (2016), 214:1–214:9.Google ScholarDigital Library
8. Theodore F. Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M. Teran. 2015. Optimization Integrator for Large Time Steps. IEEE Transactions on Visualization and Computer Graphics 21, 10 (2015), 1103–1115. Google ScholarDigital Library
9. Herbert Goldstein. 1980. Classical Mechanics. Addison-Wesley.Google Scholar
10. Dirk Helbing, Illés Farkas, and Tamas Vicsek. 2000. Simulating dynamical features of escape panic. Nature 407, 6803 (2000), 487–490. Google ScholarCross Ref
11. Dirk Helbing and Péter Molnár. 1995. Social Force Model for Pedestrian Dynamics. Physical Review E 51 (1995), 4282–4286. Google ScholarCross Ref
12. Dirk Helbing, Péter Molnár, Illés J. Farkas, and Kai Bolay. 2001. Self-Organizing Pedestrian Movement. Environment and Planning B: Planning and Design 28, 3 (2001), 361–383. Google ScholarCross Ref
13. Rowan Hughes, Jan Ondřej, and John Dingliana. 2014. Holonomic Collision Avoidance for Virtual Crowds. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 103–111.Google Scholar
14. Rowan Hughes, Jan Ondřej, and John Dingliana. 2015. DAVIS: density-adaptive synthetic-vision based steering for virtual crowds. In Motion in Games. ACM, 79–84. Google ScholarDigital Library
15. Roger L. Hughes. 2002. A continuum theory for the flow of pedestrians. Transportation Research Part B: Methodological 36, 6 (2002), 507–535. Google ScholarCross Ref
16. Eunjung Ju, Myung Geol Choi, Minji Park, Jehee Lee, Kang Hoon Lee, and Shigeo Takahashi. 2010. Morphable crowds. ACM Transactions on Graphics 29 (2010), 140:1–140:10. Issue 6.Google ScholarDigital Library
17. Couro Kane, Jerrold E. Marsden, Michael Ortiz, and Matt West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Internat. J. Numer. Methods Engrg. 49, 10 (2000). Google ScholarCross Ref
18. Mubbasir Kapadia, Nuria Pelechano, Jan Allbeck, and Norm Badler. 2015. Virtual crowds: Steps toward behavioral realism. Synthesis Lectures on Visual Computing: Computer Graphics, Animation, Computational Photography, and Imaging 7, 4 (2015), 1–270. Google ScholarCross Ref
19. Mubbasir Kapadia, Shawn Singh, Brian Allen, Glenn Reinman, and Petros Faloutsos. 2009. Steerbug: an interactive framework for specifying and detecting steering behaviors. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 209–216. Google ScholarDigital Library
20. Mubbasir Kapadia, Shawn Singh, William Hewlett, Glenn Reinman, and Petros Faloutsos. 2012. Parallelized egocentric fields for autonomous navigation. The Visual Computer 28, 12 (2012), 1209–1227. Google ScholarCross Ref
21. Ioannis Karamouzas, Peter Heil, Pascal van Beek, and Mark H. Overmars. 2009. A Predictive Collision Avoidance Model for Pedestrian Simulation. In Motion in Games. 41–52. Google ScholarDigital Library
22. Ioannis Karamouzas, Brian Skinner, and Stephen J. Guy. 2014. Universal Power Law Governing Pedestrian Interactions. Physical Review Letters 113 (2014), 238701. Issue 23.Google ScholarCross Ref
23. Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive Nonlinearity for Collisions in Complex Rod Assemblies. ACM Transactions on Graphics 33, 4 (2014), 123:1–123:12.Google ScholarDigital Library
24. Liliya Kharevych, Weiwei Yang, Yiying Tong, Eva Kanso, Jerrold E. Marsden, Peter Schröder, and Matthieu Desbrun. 2006. Geometric, Variational Integrators for Computer Animation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 43–51.Google Scholar
25. Jongmin Kim, Yeongho Seol, Taesoo Kwon, and Jehee Lee. 2014. Interactive Manipulation of Large-scale Crowd Animation. ACM Transactions on Graphics 33, 4 (2014), 83:1–83:10.Google ScholarDigital Library
26. Alon Lerner, Yiorgos Chrysanthou, and Dani Lischinski. 2007. Crowds by example. Computer Graphics Forum 26 (2007), 655–664. Google ScholarCross Ref
27. Alon Lerner, Yiorgos Chrysanthou, Ariel Shamir, and Daniel Cohen-Or. 2010. Context-Dependent Crowd Evaluation. Computer Graphics Forum 29, 7 (2010), 2197–2206. Google ScholarCross Ref
28. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-spring Systems. ACM Transactions on Graphics 32, 6 (2013), 214:1–214:7.Google ScholarDigital Library
29. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards Real-time Simulation of Hyperelastic Materials. arXiv preprint arXiv:1604.07378 (2016).Google Scholar
30. Jerrold E. Marsden and Tudor Ratiu. 1999. Introduction to Mechanics and Symmetry. Springer. Google ScholarCross Ref
31. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based Elastic Materials. ACM Transactions on Graphics 30, 4 (2011), 72:1–72:8.Google ScholarDigital Library
32. Mehdi Moussaïd, Dirk Helbing, and Guy Theraulaz. 2011. How simple rules determine pedestrian behavior and crowd disasters. Proceedings of the National Academy of Sciences 108, 17 (2011), 6884–6888. Google ScholarCross Ref
33. Rahul Narain, Abhinav Golas, Sean Curtis, and Ming C. Lin. 2009. Aggregate Dynamics for Dense Crowd Simulation. ACM Transaction on Graphics 28, 5 (2009), 122:1–122:8.Google ScholarDigital Library
34. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 21–28.Google Scholar
35. Jorge Nocedal and Steve J. Wright. 2006. Numerical optimization. Springer.Google Scholar
36. Aline Normoyle, Maxim Likhachev, and Alla Safonova. 2014. Stochastic Activity Authoring with Direct User Control. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 31–38. Google ScholarDigital Library
37. Anne-Hélène Olivier, Antoine Marin, Armel Crétual, and Julien Pettré. 2012. Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers. Gait Posture 36, 3 (2012), 399–404. Google ScholarCross Ref
38. Jan Ondřej, Julien Pettré, Anne-Hélène Olivier, and Stéphane Donikian. 2010. A synthetic-vision based steering approach for crowd simulation. ACM Transactions on Graphics 29, 4 (2010), 1–9. Google ScholarDigital Library
39. Nuria Pelechano, Jan M. Allbeck, and Norman I. Badler. 2007. Controlling individual agents in high-density crowd simulation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 99–108.Google Scholar
40. Stefano Pellegrini, Andrea Ess, Konrad Schindler, and Luc Van Gool. 2009. You’ll never walk alone: Modeling social behavior for multi-target tracking. In IEEE International Conference on Computer Vision. 261–268. Google ScholarCross Ref
41. Julien Pettré, Jan Ondřej, Anne-Hélène Olivier, Armel Crétual, and Stéphane Donikian. 2009. Experiment-based Modeling, Simulation and Validation of Interactions between Virtual Walkers. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 189–198.Google ScholarDigital Library
42. Craig W. Reynolds. 1987. Flocks, herds, and schools: A distributed behavioral model. Computer Graphics 21, 4 (1987), 24–34. Google ScholarDigital Library
43. Craig W. Reynolds. 1999. Steering Behaviors For Autonomous Characters. In Game Developers Conference. 763–782.Google Scholar
44. Armin Seyfried, Oliver Passon, Bernhard Steffen, Maik Boltes, Tobias Rupprecht, and Wolfram Klingsch. 2009. New insights into pedestrian flow through bottlenecks. Transportation Science 43, 3 (2009), 395–406. Google ScholarDigital Library
45. Shawn Singh, Mubbasir Kapadia, Billy Hewlett, Glenn Reinman, and Petros Faloutsos. 2011a. A Modular Framework for Adaptive Agent-based Steering. In ACM Symposium on Interactive 3D Graphics and Games. 141–150. Google ScholarDigital Library
46. Shawn Singh, Mubbasir Kapadia, Glenn Reinman, and Petros Faloutsos. 2011b. Footstep navigation for dynamic crowds. Computer Animation and Virtual Worlds 22, 2–3 (2011), 151–158.Google ScholarDigital Library
47. Sybren Stuvel, Nadia Magnenat-Thalmann, Daniel Thalmann, A Frank van der Stappen, and Arjan Egges. 2016. Torso Crowds. IEEE Transactions on Visualization and Computer Graphics (2016).Google Scholar
48. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87). ACM, 205–214. Google ScholarDigital Library
49. Adrien Treuille, Seth Cooper, and Zoran Popović. 2006. Continuum crowds. ACM Transactions on Graphics 25, 3 (2006), 1160–1168. Google ScholarDigital Library
50. Jur van den Berg, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha. 2011. Reciprocal n-body Collision Avoidance. In International Symposium of Robotics Research. 3–19. Google ScholarCross Ref
51. Jur van den Berg, Ming C. Lin, and Dinesh Manocha. 2008. Reciprocal Velocity Obstacles for real-time multi-agent navigation. In IEEE International Conference on Robotics and Automation. 1928–1935. Google ScholarCross Ref
52. Huamin Wang and Yin Yang. 2016. Descent Methods for Elastic Body Simulation on the GPU. ACM Transaction on Graphics 35, 6 (2016), 212:1–212:10.Google ScholarDigital Library
53. Marcel Weiler, Dan Koschier, and Jan Bender. 2016. Projective Fluids. In ACM Motion in Games. 79–84. Google ScholarDigital Library
54. David Wolinski, Ming C. Lin, and Julien Pettré. 2016. WarpDriver: context-aware probabilistic motion prediction for crowd simulation. ACM Transactions on Graphics 35, 6 (2016), 164.Google ScholarDigital Library
55. Manqi Zhao and Venkatesh Saligrama. 2009. Anomaly detection with score functions based on nearest neighbor graphs. In Advances in neural information processing systems. 2250–2258.Google Scholar