|
|
|
|
Crowd and Multi-agent Simulation
|
Interactive Simulation of Dynamic Crowd Behaviors Using General Adaptation Syndrome TheorySujeong Kim, Stephen Guy, Dinesh Manocha, and Ming C. Lin We propose a new technique to simulate dynamic patterns of crowd behaviors using the General Adaptation Syndrome model. Our model accounts for permanent, stable disposition and the dynamic nature of human behaviors that change in response to the situation. The resulting approach accounts for changes in behavior as a response to external stressors, based on well-known theories in psychology. We combine this model with recent techniques on personality modeling for multi-agent simulations to capture a wide variety of behavioral changes and stressors. The overall formulation allows different stressors, expressed as functions of space and time, including time pressure, positional stressors, area stressors and inter-personal stressors. This model can be used to simulate dynamic crowd behaviors at interactive rates, including walking with variable speeds, breaking lane-formation over time and cutting through a normal flow. We also perform qualitative and quantitative comparisons between our simulation results and real-world observations. |
|
Simulating Heterogeneous Crowd Behaviors Using Personality Trait TheoryStephen J. Guy, Sujeong Kim, Ming C. Lin, and Dinesh Manocha We present a new technique to generate heterogeneous crowd behaviors using personality trait theory. Our formulation is based on adopting results of a user study to derive a mapping from crowd simulation parameters to the perceived behaviors of agents in computer-generated crowd simulations. We also derive a linear mapping between simulation parameters and personality descriptors corresponding to the well-established Eysenck three-factor personality model. Furthermore, we propose a novel two-dimensional factorization of perceived personality in crowds based on a statistical analysis of the user study results. Finally, we demonstrate that our mappings and factorizations can be used to generate heterogeneous crowd behaviors in different settings. |
|
A Least-effort Approach to Crowd SimulationStephen J. Guy, Sean Curtis, Ming C. Lin, and Dinesh Manocha We present an algorithm for simulating large-scale crowds at interactive rates based on the principle of least effort (PLE). Our approach uses an optimization method to compute a biomechanically energy-efficient, collision-free trajectory that minimizes the amount of effort for each heterogeneous agent in a large crowd. Moreover, the algorithm can automatically generate many emergent phenomena such as lane formation, crowd compression, edge and wake effects ant others. We compare the results from our simulations to data collected from prior studies in pedestrian and crowd dynamics, and provide visual comparisons with real-world video. In practice, our approach can interactively simulate large crowds with thousands of agents on a desktop PC and naturally generates a diverse set of emergent behaviors. |
|
Synthesizing Human Motion in Constrained EnvironmentsJia Pan, Liangjun Zhang, Ming C. Lin, and Dinesh Manocha We present an algorithm to synthesize plausible motions for high-degree-of-freedom human-like articulated figures in constrained environments with multiple obstacles. Our approach is general and makes no assumptions about the articulated model or the environment. Furthermore, we use path perturbation and replanning techniques to satisfy the kinematic and dynamic constraints on the motion. In order to generate realistic human-like motion, we introduce a motion blending algorithm that refines the path computed by the planner with motion capture data to compute a smooth and plausible trajectory. |
|
Modeling Collision Avoidance Behavior for Virtual HumansStephen J. Guy, Ming C. Lin, and Dinesh Manocha We present RCAP, a new trajectory planning algorithm for virtual humans. Our approach focuses on implicit cooperation between multiple virtual agents in order to share the work of avoiding collisions with each other. Specifically, we extend recent work on multi-robot planning to better model how humans avoid collisions by introducing new parameters that model human traits, such as reaction time and biomechanical limitations. We validate this new model based on data of real humans walking captured by the Locanthrope project. We also show how our model extends to complex scenarios with multiple agents interacting with each other and avoiding nearby obstacles. |
|
Aggregate Dynamics for Dense Crowd SimulationRahul Narain, Abhinav Golas, Sean Curtis, and Ming C. Lin We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the continuous setting, we introduce a novel variational constraint called unilateral incompressibility, to model the large-scale behavior of the crowd, and accelerate inter-agent collision avoidance in dense scenarios. |
|
Optimal Reciprocal Collision AvoidanceJur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha We present a formal approach to reciprocal collision avoidance, where multiple independent mobile robots or agents need to avoid collisions with each other without communication among agents while moving in a common workspace. Our formulation, optimal reciprocal collision avoidance (ORCA), provides sufficient conditions for collision-free motion by letting each agent take half of the responsibility of avoiding pairwise collisions. Selecting the optimal action for each agent is reduced to solving a low-dimensional linear program, and we prove that the resulting motions are smooth. We test our ORCA approach on a team of iRobot Create differential-drive mobile robots, as well as on several dense and complex simulation scenarios in both 2D and 3D workspaces involving thousands of agents, and compute collision-free actions for all of them in only a few milliseconds. |
|
Highly Parallel Collision Avoidance for Multi-agent SimulationStephen J. Guy, Ming C. Lin, and Dinesh Manocha We present the ClearPath collision avoidance algorithm between multiple agents for real-time simulations. ClearPath extends the velocity obstacle (VO) from robotics and formulates the conditions for collision-free navigation as a quadratic optimization problem. We use a discrete optimization method to efficiently compute the motion of each agent and parallelize the algorithm by exploiting data and thread-level parallelism. ClearPath can robustly handle dense scenarios with hundreds of thousands of heterogeneous agents in a few milliseconds. |
|
Directing Crowd Simulations Using Navigation FieldsSachin Patil, Jur van den Berg, Sean Curtis, Ming C. Lin, and Dinesh Manocha We present an approach based on navigation fields to direct and control virtual crowds. Our method directs agents towards their desired goals based on guidance trajectories. The system allows the user to sketch the paths directly in the scene or import motion fields extracted from video footage. The input guidance fields are blended together to form a goal-directed navigation field to direct virtual crowds. |
|
Composite AgentsHengchin (Yero) Yeh, Sean Curtis, Sachin Patil, Jur van den Berg, Dinesh Manocha, and Ming C. Lin We introduce composite agents to effectively model complex agent interactions for agent-based crowd simulation. Each composite agent consists of a basic agent that is associated with one or more proxy agents. The composite agent formulation allows an agent to exercise influence over other agents greater than that implied by its physical properties. Composite agents can be added to most agent-based simulation systems and used to model emergent behaviors amongst individuals. |
|
Interactive Navigation of Individual Agents in Crowded EnvironmentsJur van den Berg, Sachin Patil, Jason Sewall, Dinesh Manocha, and Ming C. Lin We present an approach for interactive navigation and planning of multiple agents in crowded scenes with moving obstacles. Our formulation uses a pre-computed roadmap that provides macroscopic, global connectivity for way-finding and combines it with fast and localized navigation for each agent. At runtime, each agent senses the environment independently and computes a collision-free path based on an extended velocity obstacle (VO) and smoothness constraints. Furthermore, our algorithm ensures that each agent exhibits no oscillatory behaviors or gets trapped at a local minimum in crowded environments. |
|
Navigating Virtual Agents in Online Virtual WorldsRussell Gayle and Dinesh Manocha We present an approach for navigating autonomous virtual agents in online virtual worlds that are based on a centralized server network topology. The motion of each virtual agent is controlled through local and global navigation. Our local navigation model is based on artificial social forces that has been extended to account for inaccurate sensing from network latency. Global navigation for each virtual agent is based on cell decomposition and computes high level paths. The overall computation is balanced by performing local navigation on client machines and global navigation on the server. |
|
Real-time Navigation of Independent Agents Using Adaptive RoadmapsAvneesh Sud, Russell Gayle, Erik Andersen, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha We present an algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and inter-agent interaction forces to continuously update the roadmap by using a physically-based agent dynamics simulator. We also introduce link bands for resolving collisions among multiple agents. |
|
Real-time Path Planning for Virtual Agents in Dynamic EnvironmentsAvneesh Sud, Erik Andersen, Sean Curtis, Ming C. Lin, and Dinesh Manocha We present an approach for real-time path planning of multiple virtual agents in complex dynamic scenes. We introduce the multi-agent navigation graph (MaNG), which is constructed from the first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. |
|
Fundamental Diagram Adherent Interactive Crowd Simulation using Density-Dependent FiltersSahil Narang, Andrew Best, Sean Curtis, Benjamin Crétien, and Dinesh Manocha We present a novel algorithm to model density-dependent behaviors in crowd simulation. Our approach aims to generate pedestrian trajectories that correspond to the speed/density relationships that are typically expressed using the Fundamental Diagram. The algorithm's formulation can be easily combined with well-known multi-agent simulation techniques that use social forces or reciprocal velocity obstacles for local navigation. Our approach results in better utilization of free space by the pedestrians and has a small computational overhead. We are able to generate human-like dense crowd behaviors in large indoor and outdoor environments; we validate our results by comparing them with captured crowd trajectories. |
|
Principal InvestigatorsResearch Sponsors |
Current Members
Past Members
|
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
