Simulating Crowds and Autonomous Vehicles | SpringerLink
Skip to main content
Springer Nature Link
Log in

Simulating Crowds and Autonomous Vehicles

  • Chapter
  • First Online:
Transactions on Computational Science XXXVII

Part of the book series: Lecture Notes in Computer Science ((TCOMPUTATSCIE,volume 12230))

Abstract

Understanding how people view and interact with autonomous vehicles is important to guide future directions of research. One such way of aiding understanding is through simulations of virtual environments involving people and autonomous vehicles. We present a simulation model that incorporates people and autonomous vehicles in a shared urban space. The model is able to simulate many thousands of people and vehicles in real-time. This is achieved by use of GPU hardware, and through a novel linear program solver optimized for large numbers of problems on the GPU. The model is up to 30 times faster than the equivalent multi-core CPU model.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  3. Charlton, J., Gonzalez, L.R.M., Maddock, S., Richmond, P.: Fast simulation of crowd collision avoidance. In: Gavrilova, M., Chang, J., Thalmann, N.M., Hitzer, E., Ishikawa, H. (eds.) CGI 2019. LNCS, vol. 11542, pp. 266–277. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22514-8_22

    Chapter  Google Scholar 

  4. Charlton, J., Maddock, S., Richmond, P.: Two-dimensional batch linear programming on the GPU. J. Parallel Distrib. Comput. 126, 152–160 (2019)

    Article  Google Scholar 

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

    Google Scholar 

  6. Pettré, J., Kallmann, M., Lin, M.C.: Motion planning and autonomy for virtual humans. In: ACM SIGGRAPH 2008 Classes, SIGGRAPH 2008, New York, NY, USA, pp. 42:1–42:31. ACM (2008)

    Google Scholar 

  7. Pettré, J., Pelechano, N.: Introduction to Crowd Simulation. In: Bousseau, A., Gutierrez, D. (eds.) EG 2017 - Tutorials. The Eurographics Association (2017)

    Google Scholar 

  8. Thalmann, D.: Populating virtual environments with crowds. In: Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications, VRCIA 2006, New York, NY, USA, p. 11. ACM (2006). Event-place: Hong Kong, China

    Google Scholar 

  9. Narain, R., Golas, A., Curtis, S., Lin, M.C.: Aggregate dynamics for dense crowd simulation. In: ACM SIGGRAPH Asia 2009 Papers, SIGGRAPH Asia 2009, New York, NY, USA, pp. 122:1–122:8. ACM (2009)

    Google Scholar 

  10. Fickett, M., Zarko, L.: GPU continuum crowds. CIS Final Project Final report, University of Pennsylvania (2007)

    Google Scholar 

  11. Helbing, D., Molnár, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51, 4282–4286 (1995)

    Article  Google Scholar 

  12. Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Int. J. Robot. Res. 17, 760–772 (1998)

    Article  Google Scholar 

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

    Article  Google Scholar 

  14. Blue, V., Adler, J.: Cellular automata microsimulation of bidirectional pedestrian flows. Transp. Res. Rec.: J. Transp. Res. Board 1678, 135–141 (1999)

    Article  Google Scholar 

  15. Schönfisch, B., de Roos, A.: Synchronous and asynchronous updating in cellular automata. Biosystems 51, 123–143 (1999)

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  19. 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 Reserch and Applications. Springer Tracts in Advanced Robotics, pp. 71–79. Springer, Heidelberg (2006). https://doi.org/10.1007/10991459_8

    Chapter  Google Scholar 

  20. 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, Rome, Italy, pp. 1610–1616, IEEE, April 2007

    Google Scholar 

  21. Berg, J.V.D., Lin, M., Manocha, D.: Reciprocal Velocity Obstacles for real-time multi-agent navigation. In: IEEE International Conference on Robotics and Automation, ICRA 2008, pp. 1928–1935, May 2008

    Google Scholar 

  22. 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, New York, NY, USA, pp. 177–187. ACM (2009)

    Google Scholar 

  23. He, L., Pan, J., Narang, S., Wang, W., Manocha, D.: Dynamic group behaviors for interactive crowd simulation. arXiv:1602.03623 [cs], February 2016

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

    Google Scholar 

  25. Best, A., Narang, S., Manocha, D.: Real-time reciprocal collision avoidance with elliptical agents. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 298–305, IEEE (2016)

    Google Scholar 

  26. Hughes, R., Ondřej, J., Dingliana, J.: Holonomic collision avoidance for virtual crowds. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA 2014, Aire-la-Ville, Switzerland, Switzerland, pp. 103–111, Eurographics Association (2014)

    Google Scholar 

  27. Wang, L., Li, Z., Wen, C., He, R., Guo, F.: Reciprocal collision avoidance for nonholonomic mobile robots. In: 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), pp. 371–376. IEEE (2018)

    Google Scholar 

  28. Huang, X., Zhou, L., Guan, Z., Li, Z., Wen, C., He, R.: Generalized reciprocal collision avoidance for non-holonomic robots. In: 2019 14th IEEE conference on industrial electronics and applications (ICIEA), pp. 1623–1628. IEEE (2019)

    Google Scholar 

  29. Snape, J.: Optimal Reciprocal Collision Avoidance (C++), March 2019. github.com/snape/RVO2. Original-date: 2013–06-25T03:11:32Z

  30. Douthwaite, J.A., Zhao, S., Mihaylova, L.S.: Velocity obstacle approaches for multi-agent collision avoidance. Unmanned Syst. 7(01), 55–64 (2019)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  32. Gogoll, J., Müller, J.F.: Autonomous cars: in favor of a mandatory ethics setting. Sci. Eng. Ethics 23(3), 681–700 (2017)

    Article  Google Scholar 

  33. Lin, P.: Why ethics matters for autonomous cars. In: Maurer, M., Gerdes, J., Lenz, B., Winner, H. (eds.) Autonomous Driving, pp. 69–85. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-45854-9_4

    Chapter  Google Scholar 

  34. McBride, N.: The ethics of driverless cars. SIGCAS Comput. Soc. 45, 179–184 (2016)

    Article  Google Scholar 

  35. Althoff, M., Mergel, A.: Comparison of Markov chain abstraction and Monte Carlo simulation for the safety assessment of autonomous cars. IEEE Trans. Intell. Transp. Syst. 12(4), 1237–1247 (2011)

    Article  Google Scholar 

  36. Guo, J., Kurup, U., Shah, M.: Is it safe to drive? An overview of factors, metrics, and datasets for driveability assessment in autonomous driving. IEEE Trans. Intell. Transp. Syst. (2019)

    Google Scholar 

  37. Rasouli, A., Tsotsos, J.K.: Autonomous vehicles that interact with pedestrians: a survey of theory and practice. IEEE Trans. Intell. Transp. Syst. 21, 900–918 (2019)

    Article  Google Scholar 

  38. Schwarting, W., Pierson, A., Alonso-Mora, J., Karaman, S., Rus, D.: Social behavior for autonomous vehicles. Proc. Natl. Acad. Sci. 116(50), 24972–24978 (2019)

    Article  MathSciNet  Google Scholar 

  39. Bonnefon, J.-F., Shariff, A., Rahwan, I.: The social dilemma of autonomous vehicles. Science 352(6293), 1573–1576 (2016)

    Article  Google Scholar 

  40. Pettersson, I., Karlsson, I.C.M.: Setting the stage for autonomous cars: a pilot study of future autonomous driving experiences. IET Intell. Transp. Syst. 9, 694–701 (2015)

    Article  Google Scholar 

  41. Boesch, P.M., Ciari, F.: Agent-based simulation of autonomous cars. In: 2015 American Control Conference (ACC), pp. 2588–2592. IEEE (2015)

    Google Scholar 

  42. Hörl, S.: Agent-based simulation of autonomous taxi services with dynamic demand responses. Proc. Comput. Sci. 109, 899–904 (2017)

    Article  Google Scholar 

  43. Zhang, W., Guhathakurta, S., Fang, J., Zhang, G.: Exploring the impact of shared autonomous vehicles on urban parking demand: An agent-based simulation approach. Sustain. Cities Soc. 19, 34–45 (2015)

    Article  Google Scholar 

  44. Berg, J.V.D., Snape, J., Guy, S.J., Manocha, D.: Reciprocal collision avoidance with acceleration-velocity obstacles. In: 2011 IEEE International Conference on Robotics and Automation, pp. 3475–3482, May 2011

    Google Scholar 

  45. Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., Owens, J.D.: Gunrock: a high-performance graph processing library on the GPU. arXiv:1501.05387 [cs], pp. 1–12 (2016)

  46. Catapult, T.S.: Driverless Pods

    Google Scholar 

  47. Nvidia: Tuning CUDA Applications for Maxwell (2018)

    Google Scholar 

  48. Alonso-Mora, J., Breitenmoser, A., Beardsley, P., Siegwart, R.: Reciprocal collision avoidance for multiple car-like robots. In: 2012 IEEE International Conference on Robotics and Automation, pp. 360–366, May 2012

    Google Scholar 

Download references

Acknowledgements

This research was supported by EPSRC grant “Accelerating Scientific Discovery with Accelerated Computing” (grant number EP/N018869/1), and by the Transport Systems Catapult, and the National Council of Science and Technology in Mexico (Consejo Nacional de Ciencia y Tecnología, CONACYT).

Author information

Authors and Affiliations

  1. University of Sheffield, Sheffield, S10 2TN, UK

    John Charlton, Luis Rene Montana Gonzalez, Steve Maddock & Paul Richmond

Authors
  1. John Charlton
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luis Rene Montana Gonzalez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Steve Maddock
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Paul Richmond
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to John Charlton .

Editor information

Editors and Affiliations

  1. University of Calgary, Calgary, AB, Canada

    Marina L. Gavrilova

  2. Sardina Systems OÜ, Tallinn, Estonia

    C. J. Kenneth Tan

  3. Bournemouth University, Poole, UK

    Jian Chang

  4. MiraLab, University of Geneva, Geneva, Switzerland

    Nadia Magnenat Thalmann

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer-Verlag GmbH Germany, part of Springer Nature

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Charlton, J., Gonzalez, L.R.M., Maddock, S., Richmond, P. (2020). Simulating Crowds and Autonomous Vehicles. In: Gavrilova, M., Tan, C., Chang, J., Thalmann, N. (eds) Transactions on Computational Science XXXVII. Lecture Notes in Computer Science(), vol 12230. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-61983-4_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-61983-4_8

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-61982-7

  • Online ISBN: 978-3-662-61983-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation