SCIENCE CHINA Information Sciences, Volume 59 , Issue 11 : 112102(2016) https://doi.org/10.1007/s11432-016-0074-9

Towards social behavior in virtual-agent navigation

More info
  • ReceivedJan 26, 2016
  • AcceptedMay 3, 2016
  • PublishedOct 14, 2016


We present Social Groups and Navigation (SGN), a method to simulate the walking behavior of small pedestrian groups in virtual environments. SGN is the first method to simulate group behavior on both global and local levels of an underlying planning hierarchy. We define quantitative metrics to measure the coherence and the sociality of a group based on existing empirical data of real crowds. SGN does not explicitly model coherent and social formations, but it lets such formations emerge from simple geometric rules. In addition to a previous version, SGN also handles group-splitting to smaller groups throughout navigation as well as social sub-group behavior whenever a group has to temporarily split up to re-establish its coherence. For groups of four, SGN generates between 13\% and 53\% more socially-friendly behavior than previous methods, measured over the lifetime of a group in the simulation. For groups of three, the gain is between 15\% and 31\%, and for groups of two, the gain is between 1\% and 4\%. SGN is designed in a flexible way, and it can be integrated into any crowd-simulation framework that handles global path planning and any path following as separate steps. Experiments show that SGN enables the simulation of thousands of agents in real time.



This research was partially funded by the COMMIT/ project: \url{http://www.commit-nl.nl}.


[1] James J. {The distribution of free-forming small group size}. Amer Sociol Rev, 1953, 18: 569-570 CrossRef Google Scholar

[2] Coleman J S, James J. The equilibrium size distribution of freely-forming groups. Sociometry, 1961, 24: 36-45 CrossRef Google Scholar

[3] Moussaïd M, Perozo N, Garnier S, et al. The walking behaviour of pedestrian social groups and its impact on crowd dynamics. PLoS ONE, 2010, 5: e10047-45 CrossRef Google Scholar

[4] Kimmel A, Dobson A, Bekris K. Maintaining team coherence under the velocity obstacle framework. In: {Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012)}, Richland, 2012. 1: 247--256. Google Scholar

[5] Karamouzas I, Overmars M. Simulating and evaluating the local behavior of small pedestrian groups. IEEE Trans Vis Comput Graph, 2012, 18: 394-406 CrossRef Google Scholar

[6] Wu Q Q, Ji Q G, Du J H, et al. Simulating the local behavior of small pedestrian groups using synthetic-vision based steering approach. In: {Proceedings of the 12th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry (VRCAI 2013)}. New York: ACM, 2013. 41--50. Google Scholar

[7] Jaklin N, {Kremyzas} A, Geraerts R. Adding sociality to virtual pedestrian groups. In: {Proceedings of the 21st ACM Symposium on Virtual Reality Software and Technology (VRST 2015)}. New York: ACM, 2015. 163--172. Google Scholar

[8] Moussaïd M, Helbing D, Theraulaz G. How simple rules determine pedestrian behavior and crowd disasters. Proc Nat Acad Sci USA, 2011, 108: 6884-6888 CrossRef Google Scholar

[9] Geraerts R. Planning short paths with clearance using explicit corridors. In: {Proceedings of the 2010 IEEE International Conference on Robotics and Automation}, Anchorage, 2010. 1997--2004. Google Scholar

[10] Kallmann M. Shortest paths with arbitrary clearance from navigation meshes. In: {Proceedings of the 9th Eurographics/SIGGRAPH Symposium on Computer Animation (SCA 2010)}. Switzerland: Eurographics Association Aire-la-Ville, 2010. 159--168. Google Scholar

[11] Oliva R, Pelechano N. Clearance for diversity of agents' sizes in navigation meshes. Comput Graph, 2015, 47: 48-58 CrossRef Google Scholar

[12] Curtis S, Best A, Manocha D. Menge: a modular framework for simulating crowd movement. Technical Report. University of North Carolina at Chapel Hill, 2014. Google Scholar

[13] van Toll W, Jaklin N, Geraerts R. Towards believable crowds: a generic multi-level framework for agent navigation. In: {Proceedings of the 20th Annual Conference of the Advanced School for Computing and Imaging}, Amersfoort, 2015. Google Scholar

[14] Thalmann D, Musse S R. Crowd Simulation. 2nd ed. Berlin: Springer, 2013. Google Scholar

[15] Pelechano N, Allbeck J, Badler N. {Virtual Crowds: Methods, Simulation, and Control (Synthesis Lectures on Computer Graphics and Animation)}. San Rafael: Morgan and Claypool Publishers, 2008. Google Scholar

[16] Musse S, Thalmann D. A model of human crowd behavior: group inter-relationship and collision detection analysis. In: Thalmann D, van der Panne M, eds. Proceedings of the Eurographics Workshop in Budapest, Hungary, 1997. 39--51. Google Scholar

[17] Qiu F S, Hu X L. Modeling group structures in pedestrian crowd simulation. Simul Model Pract Theory, 2010, 18: 190-205 CrossRef Google Scholar

[18] Kamphuis A, Overmars M. Finding paths for coherent groups using clearance. In: {Proceedings of the 3rd ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 2004)}. Switzerland: Eurographics Association Aire-la-Ville, 2004. 19--28. Google Scholar

[19] Fiorini P, Shiller Z. Motion planning in dynamic environments using velocity obstacles. Int J Robot Res, 1998, 17: 760-772 CrossRef Google Scholar

[20] van den Berg J, Guy S, Lin M, et al. Reciprocal $n$-body collision avoidance. In: Pradalier C, Siegwart R, Hirzinger G, eds. {Robotics Research}. Berlin/Heidelberg: Springer, 2011. 3--19. Google Scholar

[21] Park S I, Quek F, Cao Y. Modeling social groups in crowds using common ground theory. In: {Proceedings of the Winter Simulation Conference (WSC 2012)}, Berlin, 2012. 113. Google Scholar

[22] Huang T Y, Kapadia M, Badler N I, et al. Path planning for coherent and persistent groups. In: {Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA 2014)}, Hong Kong, 2014. 1652--1659. Google Scholar

[23] Ond\v{r}ej J, Pettr{é} J, Olivier A-H, et al. A synthetic-vision based steering approach for crowd simulation. ACM Trans Graph, 2010, 29: 123-772 Google Scholar

[24] Fruin J J. {Pedestrian Planning and Design}. New York: Metropolitan Association of Urban Designers and Environmental Planners, 1971. Google Scholar

[25] Karamouzas I, Geraerts R, Overmars M. Indicative routes for path planning and crowd simulation. In: {Proceedings of the 4th International Conference on Foundations of Digital Games}. New York: ACM, 2009. 113--120. Google Scholar

[26] Jaklin N, Cook IV A, Geraerts R. Real-time path planning in heterogeneous environments. Comput Animat Virtual Worlds, 2013, 24: 285-295 CrossRef Google Scholar

[27] Zipf G K. {Human Behavior and the Principle of Least Effort.} Boston: Addison-Wesley Press, 1949. Google Scholar

[28] Costa M. Interpersonal distances in group walking. J Nonverbal Behav, 2010, 34: 15-26 CrossRef Google Scholar

[29] Fridman N, Kaminka G A, Zilka A. The impact of culture on crowd dynamics: an empirical approach. In: {Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems (AAMAS 2013)}, Richland, 2013. 143--150. Google Scholar

[30] Weidmann U. Transporttechnik der fussgänger. {IVT, Institut für Verkehrsplanung, Transporttechnik, Strassen-und Eisenbahnbau}, 90, 1992. Google Scholar

[31] K{ö}ster G, Treml F, Seitz M, et al. Validation of crowd models including social groups. In: Weidmann U, Kirsch U, Schreckenberg M, eds. {Pedestrian and Evacuation Dynamics 2012}. Switzerland: Springer International Publishing, 2014. 1051--1063. Google Scholar

[32] {Liddle} J, {Seyfried} A, {Steffen} B, et al. {Microscopic insights into pedestrian motion through a bottleneck, resolving spatial and temporal variations}. {arXiv:1105.1532v1}. Google Scholar

[33] Xu S, Duh H B-L. A simulation of bonding effects and their impacts on pedestrian dynamics. IEEE Trans Intell Transp Syst, 2010, 11: 153-161 CrossRef Google Scholar