Top

Published in:

2019 | OriginalPaper | Chapter

Fast Simulation of Crowd Collision Avoidance

Authors : John Charlton, Luis Rene Montana Gonzalez, Steve Maddock, Paul Richmond

Published in: Advances in Computer Graphics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Real-time large-scale crowd simulations with realistic behavior, are important for many application areas. On CPUs, the ORCA pedestrian steering model is often used for agent-based pedestrian simulations. This paper introduces a technique for running the ORCA pedestrian steering model on the GPU. Performance improvements of up to 30 times greater than a multi-core CPU model are demonstrated. This improvement is achieved through a specialized linear program solver on the GPU and spatial partitioning of information sharing. This allows over 100,000 people to be simulated in real time (60 frames per second).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Transferring Object Layouts from Virtual to Physical Rooms: Towards Adapting a Virtual Scene to a Physical Scene for VR

next chapter Improved Automatic Speed Control for 3D Navigation

Abe, Y., Yoshiki, M.: Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. In: Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180), vol. 3, pp. 1207–1212, October 2001. https://doi.org/10.1109/IROS.2001.977147

Barut, O., Haciomeroglu, M., Sezer, E.A.: Combining GPU-generated linear trajectory segments to create collision-free paths for real-time ambient crowds. Graph. Models 99, 31–45 (2018). https://doi.org/10.1016/j.gmod.2018.07.002MathSciNetCrossRef

van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE International Conference on Robotics and Automation, ICRA 2008, pp. 1928–1935, May 2008. https://doi.org/10.1109/ROBOT.2008.4543489

van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Pradalier, C., Siegwart, R., Hirzinger, G. (eds.) Robotics Research. Springer Tracts in Advanced Robotics, vol. 70, pp. 3–19. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19457-3_1CrossRef

Bleiweiss, A.: Multi agent navigation on the GPU. White paper, GDC, vol. 9 (2009)

Blue, V., Adler, J.: Emergent fundamental pedestrian flows from cellular automata microsimulation—request PDF. Transp. Res. Rec. J. Transp. Res. Board 1644, 29–36 (1998). https://doi.org/10.3141/1644-04CrossRef

Blue, V., Adler, J.: Cellular automata microsimulation of bidirectional pedestrian flows. Transp. Res. Rec. J. Transp. Res. Board 1678, 135–141 (1999). https://doi.org/10.3141/1678-17CrossRef

Charlton, J., Maddock, S., Richmond, P.: Two-dimensional batch linear programming on the GPU. J. Parallel Distrib. Comput. 126, 152–160 (2019). https://doi.org/10.1016/j.jpdc.2019.01.001CrossRef

Fickett, M., Zarko, L.: GPU Continuum Crowds. CIS Final Project Final report, University of Pennsylvania (2007)

10.

Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Int. J. Rob. Res. 17(7), 760–772 (1998). https://doi.org/10.1177/027836499801700706CrossRef

11.

Fulgenzi, C., Spalanzani, A., Laugier, C.: Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. In: Proceedings 2007 IEEE International Conference on Robotics and Automation, pp. 1610–1616. IEEE, Rome, April 2007. https://doi.org/10.1109/ROBOT.2007.363554

12.

Guy, S.J., et al.: ClearPath: highly parallel collision avoidance for multi-agent simulation. In: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA 2009, pp. 177–187. ACM, New York (2009). https://doi.org/10.1145/1599470.1599494

13.

He, L., Pan, J., Narang, S., Wang, W., Manocha, D.: Dynamic Group Behaviors for Interactive Crowd Simulation. arXiv:1602.03623 [cs], February 2016

14.

Helbing, D., Molnár, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51(5), 4282–4286 (1995). https://doi.org/10.1103/PhysRevE.51.4282CrossRef

15.

Karmakharm, T., Richmond, P.: Agent-based large scale simulation of pedestrians with adaptive realistic navigation vector fields. EG UK Theor. Pract. Comput. Graph. 10, 67–74 (2010)

16.

Kluge, B., Prassler, E.: Recursive probabilistic velocity obstacles for reflective navigation. In: Yuta, S., Asama, H., Prassler, E., Tsubouchi, T., Thrun, S. (eds.) Field and Service Robotics: Recent Advances in Research and Applications. Springer Tracts in Advanced Robotics, vol. 24, pp. 71–79. Springer, Berlin (2006). https://doi.org/10.1007/10991459_8CrossRef

17.

Li, B., Mukundan, R.: A Comparative Analysis of Spatial Partitioning Methods for Large-Scale, Real-Time Crowd Simulation. Václav Skala - UNION Agency (2013)

18.

Narain, R., Golas, A., Curtis, S., Lin, M.C.: Aggregate dynamics for dense crowd simulation. In: ACM SIGGRAPH Asia 2009 Papers, SIGGRAPH Asia 2009, pp. 122:1–122:8. ACM, New York (2009). https://doi.org/10.1145/1661412.1618468

19.

Nvidia: Tuning CUDA Applications for Maxwell (2018). http://docs.nvidia.com/cuda/maxwell-tuning-guide/index.html

20.

Pettré, J., Kallmann, M., Lin, M.C.: Motion planning and autonomy for virtual humans. In: ACM SIGGRAPH 2008 Classes, SIGGRAPH 2008, pp. 42:1–42:31. ACM, New York (2008). https://doi.org/10.1145/1401132.1401193

21.

Pettré, J., Pelechano, N.: Introduction to crowd simulation. In: Bousseau, A., Gutierrez, D. (eds.) EG 2017 - Tutorials. The Eurographics Association (2017). https://doi.org/10.2312/egt.20171029

22.

Richmond, P.: Flame GPU Technical Report and User Guide. Department of Computer Science Technical report CS-11-03, University of Sheffield (2011)

23.

Richmond, P., Romano, D.M.: A high performance framework for agent based pedestrian dynamics on GPU hardware. In: Proceedings of EUROSIS ESM 2008 (2008)

24.

Schönfisch, B., de Roos, A.: Synchronous and asynchronous updating in cellular automata. Biosystems 51(3), 123–143 (1999). https://doi.org/10.1016/S0303-2647(99)00025-8CrossRef

25.

Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6(3), 423–434 (1991). https://doi.org/10.1007/BF02574699MathSciNetCrossRefMATH

26.

Snape, J.: Optimal Reciprocal Collision Avoidance (C++). Contribute to snape/RVO2 development by creating an account on GitHub, March 2019

27.

Thalmann, D.: Populating virtual environments with crowds. In: Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications, VRCIA 2006, p. 11. ACM, New York (2006). https://doi.org/10.1145/1128923.1128925

28.

Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., Owens, J.D.: Gunrock: a high-performance graph processing library on the GPU. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, p. 11. ACM (2016)

29.

Xu, M.L., Jiang, H., Jin, X., Deng, Z.: Crowd simulation and its applications: recent advances. J. Comput. Sci. Technol. 29, 799–811 (2014). https://doi.org/10.1007/s11390-014-1469-yCrossRef

30.

Yang, Z., Pan, J., Wang, W., Manocha, D.: Proxemic group behaviors using reciprocal multi-agent navigation. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 292–297 (2016). https://doi.org/10.1109/ICRA.2016.7487147

Title: Fast Simulation of Crowd Collision Avoidance
Authors: John Charlton
Luis Rene Montana Gonzalez
Steve Maddock
Paul Richmond
Publisher: Springer International Publishing
Book: Advances in Computer Graphics
Print ISBN: 978-3-030-22513-1

Electronic ISBN: 978-3-030-22514-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-22514-8_22

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"