May 2010 Simulation Technologies for Evacuation Planning and Disaster Response Project Leads Ming C. Lin, PhD University of North Carolina at Chapel Hill Dinesh Manocha, PhD University of North Carolina at Chapel Hill Statement of Problem First responders need a new generation of technology and resources to prepare for and respond to terrorist attacks, natural disasters, and large-scale emergencies. Next-generation simulation and experiential technologies for first responders can help better prepare them for evacuation planning and disaster response, better facilitate training experiences, and enable leaders and law-enforcement personnel to optimize their tactics using \"what-if\" simulations that are based on actual situations in which they might work. To accomplish these goals, new sets of technologies for evacuation planning and disaster response in urban environments are necessary. These include real-time technologies for simulating large groups of heterogeneous crowds consisting of non-uniformly distributed groups of people and \"agents\" (real, virtual, or constructive) with independent behaviors and goals, and urban traffic over a complex road network. Crowds, ubiquitous in the real world from groups of humans to schools of fish, are vital elements to model in a virtual environment. Realistic simulation of virtual crowds has diverse applications in architecture design, emergency evacuation, urban planning, personnel training, education, and entertainment. Existing work in this area can be broadly classified into agent 1 based methods (Reynolds, 1987), which focus more on individual behavior, and crowd simulations, which aim to exhibit emergent phenomena of the groups (Bellomo & Dogbe, 2008; Braun, Bodmann, & Musse, 2005). Pedestrian dynamics of heterogeneous crowds exhibit a rich variety of collective effects, including lane formation, oscillation, chemotaxis, and panic effects. Given the existing models and methods available, the research questions are as follows: Are existing methods sufficient to model large groups of heterogeneous crowds for real-time training? What are the most effective approaches for training and improving the first responders' readiness for unexpected events? How can we evaluate and validate the results of crowd simulations for these given applications? Background An extensive body of literature exists on crowd simulation and dynamics in computer graphics as well as architecture, psychology, social sciences, and civil and traffic engineering (Helbing, Buzna, & Werne, 2003; Helbing, Buzna, Johansson, & Werner, 2005; Wilkerson, Avstreih, Gruppen, Beier, & Woolliscroft, 2008; Zhang, Liu, Liu, & Zhao, 2007). Various approaches have been proposed for modeling movement and simulation of multiple human agents (Zarboutis & Marmaras, 2007), crowds, or individual pedestrians (Thalmann et al., 2006; Zheng, Zhong, & Liu, 2009). They can be classified based on specificity, such as problem decomposition (discrete versus continuous, local versus global, etc.). Discrete Methods Discrete methods rely on discretization or sampling of the environment or of the agents. Some common approaches (Thalmann, O'Sullivan, Ciechomski, & Dobbyn, 2006) include the following: Agent-based Methods: These are based on the seminal work of Reynolds (1987) and can generate fast, simple local rules that can create visually plausible flocking behavior. Numerous extensions that have been proposed account for social forces (Cordeiro, Braun, Silveria, Musse, & Cavalheiro, 2005), psychological models (Pelechano, O'Brien, Silverman, & Badler, 2005), directional preferences (Sung, Gleicher, & Chenney, 2004), sociological factors (Musse & Thalmann, 1997), and other factors. Interesting techniques for collision avoidance have also been developed based on grid-based rules (Loscos, Marchal, & Meyer, 2003) and behavior models (Tu & Terzopoulos, 1994). Cellular-Automata Methods: These methods model the motion of multiple agents by solving a cellular automaton. The evolution of cellular automata at the next time step is governed by static and dynamic fields (Hoogendoorn, Luding, Bovy, Schrecklenberg, & Wolf, 2000; Aube & Shield, 2004). The static fields are used to capture the environment, and dynamic fields are used to capture the movement of the agents. Although these algorithms can 2 capture emergent phenomena, they are not physically based. Different techniques for collision avoidance have been developed from grid-based rules (Loscos et al., 2003) and behavior models (Tu & Terzopoulos, 1994). Particle Dynamics: Computing physical forces on each agent is similar to an N-body particle system (Schreckkenberg & Sharma, 2001; Helbing et al., 2003). Sugiyama and colleagues (2001) presented a 2D optimal velocity (OV) model that generalizes the 1D OV model used for traffic flow. Under this model each agent attempts to move at its optimal velocity under constraints from other particles. Group formation under the OV model has been stochastically studied (Nakayama, Hasebe, & Sugiyama, 2005); however, this approach does not accurately capture real pedestrian movement. The generalized force model (Helbing et al., 2003) captures various interactions among agents as social forces and has been demonstrated to be capable of capturing several crowd phenomena. However this model does not scale well to large crowds. A major \"bottleneck\" in these systems is the cost of nearest neighbor queries for large crowds. Another problem is that this model has previously been applied to simple scenarios and can result in agents getting stuck in local minima for more complex environments. Continuous Methods The flow of crowds or multiple agents can be formulated as fluid flows. At low densities crowd flow is like that of a gas, at moderate densities it resembles fluid flow, and at high densities it has been compared to granular flow (Helbing et al., 2005). More recently, Treuille, Cooper, and Popovic (2006) proposed a novel approach for crowd simulation based on continuum dynamics. They compute a dynamic potential field that simultaneously integrates global navigation with local obstacle avoidance. The resulting system runs at interactive rates and demonstrates smooth traffic flows for three to four groups of large crowds that are moving with common goals. This work, however, is not designed for heterogeneous crowds whose individual behavior characteristics and goals are unique. Local Versus Global Most agent-based techniques use local collision avoidance techniques that consider only a small neighborhood of \"nearest neighbors.\" They cannot give any guarantees on the correctness of global behaviors or provide any high-level way-finding capability. Global path planning and navigation techniques are needed to provide goal-seeking capability and to model individual intentions. In practice, global planning algorithms typically use graph search techniques for each agent (Bayazit, Lien, & Amato, 2002; Funge, Tu, & Terzopoulos, 1999; Lamarche & Donikian, 2004; Sung, Kovar, & Gleicher, 2005). Pettre, Laumond, and Thalmann (2005) proposed a graph structure that decomposes the space into multi-layered terrains to support fast graph search for multiple characters. Sud, Andersen, Curtis, Lin, and Manocha (2008) introduced a new data structure, Multi-agent Navigation Graph (MaNG), to perform 3 route planning and proximity computations for each agent in real time by using graphics hardware and efficient culling techniques. However, none of these methods can simulate thousands of virtual humans in real time. Synthesis Agent-based techniques focus on modeling individual behavior and intent. They offer many attractive benefits, as they often result in more realistic and detailed simulations. However, individuals constantly adjust their behavior according to dynamic factors in the environment (e.g., another approaching individual). Therefore, one of the key challenges in a large-scale agent-based simulation is global collision-free path planning for each virtual agent and behavior modeling. These problems can become very challenging for real-time applications with a large group of moving agents, as each is a dynamic obstacle for others. Moreover, there may be other dynamic obstacles in the scene, and the underlying applications cannot make any assumptions about their motion. Many prior techniques are either restricted to static environments, only perform local collision avoidance computations, or may not scale to complex environments with hundreds of agents. The use of solely local methods can result in unnatural behavior or \"getting stuck\" in local minima. These problems tend to be more challenging in a dynamically changing scene with multiple moving virtual agents (i.e., a moblike scene). Therefore, although models and methods exist for modeling heterogeneous crowds, their performance and generality are insufficient for real-time training. Given the state of the art in modeling crowds, it is important to combine both local and global methods, as well as continuous and discrete models, to generate robust solutions for simulating diverse groups of heterogeneous agents and capture the richness of their distinct behaviors. Future Directions Highly dense crowds exhibit a low interpersonal distance and a corresponding loss of individual freedom of motion. In dense crowds, the finite spatial extent occupied by humans becomes a significant factor. This effect introduces new challenges, as the flow varies from freely compressible when the density is low to incompressible when the agents are close together. This characteristic is shared by many other dynamic systems consisting of numerous objects of finite size, including dense traffic. Techniques must be developed to model highly dense crowds, as the existing methods do not work well in these scenarios. Furthermore, it is possible today to extract the motion flows of a video, which can in turn be used to drive a crowd simulation, thus providing a platform for policy makers and intelligent analysts to evaluate \"what-if\" scenarios. In doing so, one must have an interactive mechanism to \"edit\" and \"re-direct\" the agents in the crowd simulations. Therefore, there is also a need to 4 develop new methodologies for directing the flow of virtual agents in a simulation and interactively control a simulation at runtime to evaluate various test case scenarios. Finally, due to their limited use (e.g., they are not applicable to large-scale dynamic scenes or dense crowds), the existing methods cannot always provide a reliable predicted measure on response times using a simulation-based system under varying conditions (e.g., variations in exits, pathways, the number of agents, crowd density, and traffic). Furthermore, few experiments have been conducted to evaluate the correctness of the existing models. One future challenge in proposing better modeling and faster simulation techniques would be formal and experimental validation of these emerging models in a meaningful way. Contact Information Ming C. Lin University of North Carolina at Chapel Hill Chapel Hill, NC 27599-3175 (919) 962-19974 lin@cs.unc.edu Dinesh Manocha University of North Carolina at Chapel Hill Chapel Hill, NC 27599-3175 (919) 962-1749 dm@cs.unc.edu Ming C. Lin is currently the Beverly W. Long Distinguished Professor of Computer Science at the University of North Carolina at Chapel Hill (UNC). Her research interests include physically based modeling, real-time 3D modeling for virtual environments, haptics, sound rendering, robotics, geometric computing, and distributed interactive simulation. She has authored or co-authored more than 190 refereed scientific publications and coedited/authored three books. She has served as a program committee member for over 90 leading conferences on virtual reality, computer graphics, robotics, haptics, and computational geometry. She also has co-chaired over 20 international conferences and workshops. She is the associate editor-in-chief of IEEE Transactions on Visualization and Computer Graphics (TVCG), and has served as an associate editor and guest editor of dozens of journals and magazines. She also has served on the steering/executive committees of the Association for Computing Machinery's Special Interest Group on Graphics and Interactive Techniques (ACM SIGGRAPH)/Eurographics Symposium on Computer Animation and of IEEE 5 Virtual Reality Conference; paper advisory board of Eurographics 2009; IEEE Computer Society Technical Committee on Visualization and Graphics; advisory board of IEEE Robotics and Automation Society and Computer Society Technical Committee on Haptics; conference board of IEEE Haptic Symposium; the Software Technical Advisory Board of AGEIA Technologies, Inc.; the National Science Foundation's Information Technology Research (ITR) Committee of Visitors; and several technical advisory committees constituted by the Army and the Department of Defense. Dinesh Manocha is currently the Phi Delta Theta/Matthew Mason Distinguished Professor of Computer Science at the University of North Carolina at Chapel Hill. He received his BTech degree in computer science and engineering from the Indian Institute of Technology, Delhi, in 1987, and he received his MS and PhD in computer science at the University of California at Berkeley in 1990 and 1992, respectively. He received an Alfred and Chella D. Moore fellowship and an IBM graduate fellowship in 1988 and 1991, respectively, and a Junior Faculty Award in 1992. He was selected as an Alfred P. Sloan Research Fellow, received an NSF Career Award in 1995 and the Office of Naval Research Young Investigator Award in 1996, Honda Research Initiation Award in 1997, and Hettleman Prize for scholarly achievement at UNC in 1998. He has also received more than 13 best paper and panel awards at the ACM SuperComputing, ACM Multimedia, ACM Solid Modeling, Pacific Graphics, IEEE VR, IEEE Visualization, ACM SIGMOD, ACM VRST, CAD, I/ITSEC, and Eurographics conferences. Manocha's research interests include geometric computing, interactive computer graphics, physics-based simulation, and robotics. He has published more than 270 papers in these areas. His research has been sponsored by AMD/ATI, the Army Research Office (ARO), the Defense Advanced Research Projects Agency (DARPA), Disney, the Department of Energy, Honda, Intel, Microsoft, the National Science Foundation, NVIDIA, Office of Naval Research, the U.S Army Research Development and Engineering Command (RDECOM), and the Alfred P. Sloan Foundation. Some of the software systems developed by his group on collision and geometric computations, interactive rendering, and GPU-based algorithms have been widely downloaded and used by leading commercial vendors. Mr. Dinesh has served as a program committee member or program chair for more than 75 leading conferences and has also served as a guest editor or member of editorial board for 10 leading journals. He has supervised 40 MS and PhD students. References Aube, F., & Shield, R. (2004). Modeling the effect of leadership on crowd flow dynamics. In P. M. A. Sloot, B. Chopard, & A. G. Hoekstra (Eds.), Cellular Automata, Proceedings: Vol. 3305 (pp. 601-611). Springer-Verlag Berlin Heidelberg. 6 Bayazit, O. B., Lien, J. M., & Amato, N. M. (2002). Better group behaviors in complex environments with global roadmaps. Proceedings of the Eighth International Conference on Artificial Life (pp. 362-370). Bellomo, N., & Dogbe, C. (2008). On the modelling crowd dynamics from scaling to hyperbolic macroscopic models. Mathematical Models & Methods in Applied Sciences, 18, 1317-1345. Braun, A., Bodmann, B. E. J., & Musse, S. R. (2005). Simulating virtual crowds in emergency situations. Proceedings of the ACM Symposium on Virtual Reality Software and Technology (pp. 244-252). Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., & Cavalheiro, G. G. (2005). Concurrency on social forces simulation model. First International Workshop on Crowd Simulation. Funge, J., Tu, X., & Terzopoulos, D. (1999). Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proceedings of the Association for Computing Machinery's Special Interest Group on Graphics and Interactive Technique (pp. 29-38). Helbing, D., Buzna, L., Johansson, A., & Werner, T. (2005). Self-organized pedestrian crowd dynamics: Experiments, simulations and design solutions. Transportation Science, 39(1), 1-24. Helbing, D., Buzna, L., & Werner, T. (2003). Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum, 12, 1-39. Hoogendoorn, S. P., Luding, S., Bovy, P., Schrecklenberg, M., & Wolf, D. (Eds.) (2000). Traffic and granular flow. Springer, 2000. Lamarche, F., & Donikian, S. (2004). Crowd of virtual humans: A new approach for realtime navigation in complex and structured environments. Computer Graphics Forum, 23(3), 509-518. Loscos, C., Marchal, D., & Meyer, A. (2003). Intuitive crowd behaviour in dense urban environments using local laws. Proceedings of the Theory and Practice of Computer Graphics (TPCG'03) (pp. 122-129). Musse, S. R., & Thalmann, D. (1997). A model of human crowd behavior: Group interrelationship and collision detection analysis. In Workshop Computer Animation and Simulation of Eurographics (pp. 39-52). Nakayama, A., Hasebe, K., & Sugiyama, Y. (2005). Instability of pedestrian flow and phase structure in a two-dimensional optimal velocity model. Physical review E, Statistical, Nonlinear, and Soft Matter Physics, 71(3), 36121. Pelechano, N., O'Brien, K., Silverman, B., & Badler, N. (2005). Crowd simulation incorporating agent psychological models, roles and communication. First International Workshop on Crowd Simulation. 7 Pettre, J., Laumond, J.-P., & Thalmann, D. (2005). A navigation graph for real-time crowd animation on multilayered and uneven terrain. First International Workshop on Crowd Simulation. Reynolds, C. W. (1987). Flocks, herds, and schools: A distributed behavioral model. Proceedings of the Association for Computing Machinery's Special Interest Group on Graphics and Interactive Techniques (ACM SIGGRAPH): Volume 21 (pp. 25-34). Schreckkenberg, M., & Sharma, S. D. (2001). Pedestrian and evacuation dynamics. Springer, 2001. Sud, A., Andersen, E., Curtis, S., Lin, M., & Manocha, D. (2008). Real-time path planning in dynamic virtual environments using multi-agent navigation graphs. IEEE Transactions on Visualization and Computer Graphics, 14(3), 526-538. Sung, M., Gleicher, M., & Chenney, S. (2004, September). Scalable behaviors for crowd simulation. Computer Graphics Forum, 23(3), 519-528, 2004. Sung, M., Kovar, L., & Gleicher, M. (2005). Fast and accurate goal-directed motion synthesis for crowds. Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (pp. 291-300). Thalmann, D., O'Sullivan, C., Ciechomski, P., & Dobbyn, S. (2006). Populating virtual environments with crowds. Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications (p. 11). Treuille, A., Cooper, S., & Popovic Z. (2006). Continuum crowds. Proceedings of the Association for Computing Machinery's Special Interest Group on Graphics and Interactive Techniques (ACM SIGGRAPH) (pp. 1160-1168). Tu, X., & Terzopoulos, D. (1994). Artificial fishes: Physics, locomotion, perception, behavior. Proceedings of the Association for Computing Machinery's Special Interest Group on Graphics and Interactive Techniques (ACM SIGGRAPH) (pp. 43-50). Wilkerson, W., Avstreih, D., Gruppen, L., Beier, K. P., & Woolliscroft, J. (2008). Using immersive simulation for training first responders for mass casualty incidents. Academic Emergency Medicine, 15(11), 1152-1159. Zarboutis, N., & Marmaras, N. (2007). Design of formative evacuation plans using agentbased simulation. Safety Science, 45(9) 920-940. Zhang O., Liu, M., Liu, J., & Zhao, G. (2007). Modification of evacuation time computational model for stadium crowd risk analysis. Process Safety and Environmental Protection, 85(B6), 541-548. Zheng, X. P., Zhong, T. K., & Liu M. (2009). Modeling crowd evacuation of a building based on seven methodological approaches. Building and Environment, 44(3) 437-445. 8