nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Fast Simulation of Crowd Collision Avoidance

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

Erschienen in: Advances in Computer Graphics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Transferring Object Layouts from Virtual to Physical Rooms: Towards Adapting a Virtual Scene to a Physical Scene for VR

Nächstes Kapitel 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

Titel: Fast Simulation of Crowd Collision Avoidance
verfasst von: John Charlton
Luis Rene Montana Gonzalez
Steve Maddock
Paul Richmond
Verlag: Springer International Publishing
Buch: Advances in Computer Graphics
Print ISBN: 978-3-030-22513-1

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

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

Premium Partner

Bildnachweise

Rittal/© Rittal, NTT Data/© NTT Data, Wildix/© Wildix, Ceyoniq Technology GmbH/© Ceyoniq Technology GmbH, arvato Systems GmbH/© arvato Systems GmbH, Ninox Software GmbH/© Ninox Software GmbH, Everyday Software S.L./© Everyday Software S.L., Redgate/© Redgate, CELONIS Labs GmbH, DC-Datacenter-Group GmbH/© DC-Datacenter-Group GmbH, all for one/© all for one, G Data CyberDefense/© G Data CyberDefense, FAST LTA/© FAST LTA, Vendosoft/© Vendosoft, Kumavision/© Kumavision, Noriis Network AG/© Noriis Network AG, WSW Software GmbH/© WSW Software GmbH, tts GmbH/© tts GmbH

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"