Menge: A Modular Framework for Simulating Crowd Movement

Sean Curtis; Andrew Best; Dinesh Manocha

doi:10.17815/CD.2016.1

Authors

Sean Curtis University of North Carolina at Chapel Hill, United States
Andrew Best University of North Carolina at Chapel Hill, United States
Dinesh Manocha University of North Carolina at Chapel Hill, United States

DOI:

https://doi.org/10.17815/CD.2016.1

Keywords:

crowd simulation, pedestrians, open source, framework, software system

Abstract

We present Menge, a cross-platform, extensible, modular framework for simulating pedestrian movement in a crowd. Menge's architecture is inspired by an implicit decomposition of the problem of simulating crowds into component subproblems. These subproblems can typically be solved in many ways; different combinations of subproblem solutions yield crowd simulators with likewise varying properties. Menge creates abstractions for those subproblems and provides a plug-in architecture so that a novel simulator can be dynamically configured by connecting built-in and bespoke implementations of solutions to the various subproblems. Use of this type of framework could facilitate crowd simulation research, evaluation, and applications by reducing the cost of entering the domain, facilitating collaboration, and making comparisons between algorithms simpler. We show how the Menge framework is compatible with many prior models and algorithms used in crowd simulation and illustrate its flexibility via a varied set of scenarios and applications.

Author Biography

Sean Curtis, University of North Carolina at Chapel Hill, United States

References

Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5, 90-98 (1986). doi:10.1109/ROBOT.1985.1087247

Latombe, J.C.: Robot Motion Planning. Springer, Heidelberg (1991). doi:10.1007/978-1-4615-4022-9

Snook, G.: Simplified 3D movement and pathfinding using navigation meshes. In: Game Programming Gems, chap. 3, pp. 288-304. Charles River, Hingham, Mass. (2000)

Geraerts, R., Kamphuis, A., Karamouzas, I., Overmars, M.: Using the corridor map method for path planning for a large number of characters. In: Motion in Games, pp. 11-22. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89220-5_2

Funge, J., Tu, X., Terzopoulos, D.: Cognitive modeling: knowledge, reasoning and planning for intelligent characters. In: Proc. of SIGGRAPH, pp. 29-38 (1999). doi:10.1145/311535.311538

Ulicny, B., Thalmann, D.: Towards interactive real-time crowd behavior simulation. Computer Graphics Forum 21(4), 767-775 (2002). doi:10.1111/1467-8659.00634

Shao, W., Terzopoulos, D.: Autonomous pedestrians. In: Symposium on Computer Animation, pp. 19-28 (2005). doi:10.1145/1073368.1073371

Bandini, S., Federici, M., Manzoni, S., Vizzari, G.: Towards a methodology for situated cellular agent based crowd simulations. Engineering societies in the agents world VI pp. 203-220 (2006). doi:10.1007/11759683_13

Paris, S., Donikian, S.: Activity-driven populace: A cognitive approach to crowd simulation. Computer Graphics and Applications, IEEE 29(4), 34-43 (2009). doi:10.1109/MCG.2009.58

Oliva, R., Pelechano, N.: Automatic generation of suboptimal navmeshes. In: J.M. Allbeck, P. Faloutsos (eds.) MIG, Lecture Notes in Computer Science, vol. 7060, pp. 328-339. Springer (2011). doi:10.1007/978-3-642-25090-3

Lamarche, F., Donikian, S.: Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. Computer Graphics Forum 23(3), 509-518 (2004). doi:10.1111/j.1467-8659.2004.00782.x

Jaillet, L., Simeon, T.: A PRM-based motion planning for dynamically changing environments. In: Proc. IEEE RSJ Int. Conf. Intell. Robot. Syst., vol. 2, pp. 1606-1611 (2004). doi:10.1109/IROS.2004.1389625

Kallman, M., Mataric, M.: Motion planning using dynamic roadmaps. In: Proc. IEEE Int. Conf. Robot. Autom., vol. 5, pp. 4399-4404 (2004). doi:10.1109/ROBOT.2004.1302410

Yang, Y., Brock, O.: Elastic roadmaps: globally task-consistent motion for autonomous mobile manipulation. In: Proc. Robot. Sci. Syst., pp. 279-286 (2007). doi:10.1007/s10514-009-9151-x

Kretz, T.: Pedestrian traffic: on the quickest path. Journal of Statistical Mechanics: Theory and Experiment 2009(03), P03012 (2009). doi:10.1088/1742-5468/2009/03/P03012

Schadschneider, A.: Cellular automaton approach to pedestrian dynamics - theory. Pedestrian and Evacuation Dynamics pp. 75-86 (2002)

Helbing, D., Molnár, P.: Social force model for pedestrian dynamics. Physical Review E 51(5), 4282-4286 (1995). doi:10.1103/PhysRevE.51.4282

Pelechano, N., Allbeck, J., Badler, N.: Controlling individual agents in high-density crowd simulation. In: Symposium on Computer Animation, pp. 99-108 (2007). doi:10.2312/SCA/SCA07/099-108

Karamouzas, I., Heil, P., van Beek, P., Overmars, M.H.: A predictive collision avoidance model for pedestrian simulation. In: Motion in Games, Lecture Notes in Computer Science, vol. 5884, pp. 41-52. Springer (2009). doi:10.1007/978-3-642-10347-6_4

Ondřej, J., Pettré, J., Olivier, A.H., Donikian, S.: A synthetic-vision based steering approach for crowd simulation. In: Proc. SIGGRAPH, pp. 123:1-123:9 (2010). doi:10.1145/1778765.1778860

Narain, R., Golas, A., Curtis, S., Lin, M.C.: Aggregate dynamics for dense crowd simulation. ACM Trans. Graph. 28, 122:1-122:8 (2009). doi:10.1145/1661412.1618468

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

Pettré, J., Ondřej, J., Olivier, A.H., Cretual, A., Donikian, S.: Experiment-based modeling, simulation and validation of interactions between virtual walkers. In: Symposium on Computer Animation, pp. 189-198 (2009). doi:10.1145/1599470.1599495

Reynolds, C.: Flocks, herds and schools: A distributed behavioral model. In: Proc. of SIGGRAPH (1987). doi:10.1145/280811.281008

Zheng, X., Zhong, T., Liu, M.: Modeling crowd evacuation of a building based on seven methodological approaches. Building and Environment 44(3), 437-445 (2009). doi:10.1016/j.buildenv.2008.04.002

Duives, D.C., Daamen, W., Hoogendoorn, S.P.: State-of-the-art crowd motion simulation models. Transportation Research Part C: Emerging Technologies 37(0), 193-209 (2013). doi:10.1016/j.trc.2013.02.005

Treuille, A., Cooper, S., Popović, Z.: Continuum crowds. In: Proc. of ACM SIGGRAPH, pp. 1160-1168 (2006). doi:10.1145/1141911.1142008

Kapadia, M., Singh, S., Hewlett, W., Faloutsos, P.: Egocentric affordance fields in pedestrian steering. In: Proceedings of the Symposium on Interactive 3D Graphics and Games, pp. 215-223 (2009). doi:10.1145/1507149.1507185

Bruderlin, A., Calvert, T.W.: Goal-directed, dynamic animation of human walking. In: Proc. of SIGGRAPH '89, pp. 233-242 (1989). doi:10.1145/74333.74357

Sun, H.C., Metaxas, D.N.: Automating gait generation. In: Proc. of ACM SIGGRAPH, pp. 261-270 (2001). doi:10.1145/383259.383288

Multon, F., France, L., Cani-Gascuel, M.P., Debunne, G.: Computer animation of human walking: a survey, vol. 10, pp. 39-54 (1999)

Kovar, L., Gleicher, M., Pighin, F.: Motion graphs. ACM Trans. Graph. 21(3), 473-482 (2002). doi:10.1145/566570.566605

Heck, R., Gleicher, M.: Parametric motion graphs. In: Proceedings of Symposium on Interactive 3D Graphics and Games, pp. 129-136 (2007). doi:10.1145/1230100.1230123

Lee, K.H., Choi, M.G., Hong, Q., Lee, J.: Group behavior from video: a data-driven approach to crowd simulation. In: Symposium on Computer Animation, pp. 109-118 (2007). doi:10.2312/SCA/SCA07/109-118

van Basten, B.J.H., Stuvel, S.A., Egges, A.: A hybrid interpolation scheme for footprint-driven walking synthesis. Graphics Interface pp. 9-16 (2011)

Cohen-Or, D., Chrysanthou, Y., Silva, C., Durand, F.: A survey of visibility for walkthrough applications. IEEE Transactions on Visualization and Computer Graphics 9(3), 412-431 (2003). doi:10.1109/TVCG.2003.1207447

Samet, H.: Foundations of MultiDimensional and Metric Data Structures. Morgan Kaufmann (2006)

Newell, A.: Unified theories of cognition. Harvard University Press, Cambridge, MA, USA (1990). doi:10.1002/wcs.1180

Singh, S., Kapadia, M., Faloutsos, P., Reinman, G.: An open framework for developing, evaluating, and sharing steering algorithms. In: Proceedings of the 2nd International Workshop on Motion in Games, pp. 158-169 (2009). doi:10.1007/978-3-642-10347-6_15

Kapadia, M., Marshak, N., Shoulson, A., Badler, N.I.: ADAPT: The agent development and prototyping testbed. IEEE Transactions on Visualization and Computer Graphics 20(7), 1035-1047 (2014). doi:10.1109/TVCG.2013.251

Hutton, A.: London bridge station, the role of ped modelling: Pedestrian modelling and design development. In: 6th International Conference on Pedestrian and Evacuation Dynamics. Zurich, Switzerland (2012)

Curtis, S., Snape, J., Manocha, D.: Way portals: Efficient multi-agent navigation with line-segment goals. Proc. of Symposium on Interactive 3D Graphics and Games pp. 15-22 (2012). doi:10.1145/2159616.2159619

Golas, A., Narain, R., Lin, M.: Hybrid long-range collision avoidance for crowd simulation. Proc. of Symposium on Interactive 3D Graphics and Games (I3D) pp. 29-36 (2013). doi:10.1145/2448196.2448200

He, L., van den Berg, J.: Meso-scale planning for multi-agent navigation. In: Proc. IEEE Int. Conf. on Robotics and Automation - ICRA (2013). doi:10.1109/ICRA.2013.6630970

Helbing, D., Farkas, I., Vicsek, T.: Simulating dynamical features of escape panic. Nature 407, 487-490 (2000). doi:10.1038/35035023

Singh, S., Kapadia, M., Faloutsos, P., Reinman, G.: Steerbench: a benchmark suite for evaluating steering behaviors. Computer Animation and Virtual Worlds 20(5-6), 533-548 (2009). doi:10.1002/cav.277

Burghardt, S., Klingsch, W., Seyfried, A.: Fundamental diagram of stairs: Critical review and topographical measurements. In: Pedestrian and Evacuation Dynamics (2012). doi:10.1007/978-3-319-02447-9_27

Kim, S., Guy, S.J., Manocha, D., Lin, M.C.: Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory. ACM Symposium on Interactive 3D Graphics and Games pp. 55-62 (2012). doi:10.1145/2159616.2159626

Guy, S.J., Kim, S., Lin, M.C., Manocha, D.: Simulating heterogeneous crowd behaviors using personality trait theory. In: ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), pp. 43-52 (2011). doi:10.1145/2019406.2019413

Gu, Q., Deng, Z.: Generating freestyle group formations in agent-based crowd simulations. IEEE Computer Graphics and Applications 33(1), 20-31 (2013). doi:10.1109/MCG.2011.87

Ju, E., Choi, M.G., Park, M., Lee, J., Lee, K.H., Takahashi, S.: Morphable crowds. ACM Trans. Graph 29(6), 140 (2010). doi:10.1145/1882261.1866162

Zhang, P., Liu, H., Ding, Y.h.: Crowd simulation based on constrained and controlled group formation. The Visual Computer pp. 1-14 (2013). doi:10.1007/s00371-013-0900-7

Best, A., Curtis, S., Kasik, D., Senesac, C., Sikora, T., Manocha, D.: Ped-air: a simulator for loading, unloading, and evacuating aircraft. In: 7th International Conference on Pedestrian and Evacuation Dynamics. Delft, Netherlands (2014). doi:10.1016/j.trpro.2014.09.052

Weidmann, U.: Transporttechnik der Fussgänger. Tech. Rep. 90 (1993)

Best, A., Narang, S., Curtis, S., Manocha, D.: Densesense: Interactive crowd simulation using density-dependent filters. In: Symposium on Computer Animation (2014). doi:10.2312/sca.20141127

Gloor, C.: Pedsim: A microscopic pedestrian crowd simulation system. http://pedsim.silmaril.org/ (2003)

Reynolds, C.W.: Steering behaviors for autonomous characters. Game Developers Conference (1999). doi:10.1145/2522628.2522899

Mononen, M.: Recast: navigation-mesh construction toolset for games. http://code.google.com/p/recastnavigation/ (2009)

Forschungszentrum Jülich: JuPedSim. http://www.jupedsim.org/ (2016)

Forschungszentrum Jülich: Open Ped Sim. http://sourceforge.net/projects/openpedsim/ (2014)

Chraibi, M., Seyfried, A., Schadschneider, A.: Generalized centrifugal-force model for pedestrian dynamics. Phys. Rev. E 82(4), 046111 (2010). doi:10.1103/PhysRevE.82.046111

Rabin, S.: AI Game Programming Wisdom 4, 1 edn. Charles River Media (2008)

Shum, H.P.H., Komura, T., Shiraishi, M., Yamazaki, S.: Interaction patches for multi-character animation. ACM Trans. Graph 27(5), 114 (2008). doi:10.1145/1457515.1409067

Hyun, K., Kim, M., Hwang, Y., Lee, J.: Tiling motion patches. IEEE Trans. Vis. Comput. Graph 19(11), 1923-1934 (2013). doi:10.1109/TVCG.2013.80