Complex agent representations for crowd simulations employ algorithms that represent each individual in a crowd simulation as an independent complex agent with its own set of behaviors, rules and goals. It emphasizes on agent-based model with complex shapes and geometry or complex behavior in crowd simulation.
For efficiency reasons, most of the agents used in crowd simulations are constructed from point-like representations,[1] so that the performance is easy to optimize. However, in order to produce more realistic virtual worlds, sometimes more complex agent shapes are needed. In order to generate more realistic simulations, recent advances in crowd simulation have introduced more complex model and behavior of agents. In the meantime, to simulate to motion of agents, real-time search (also known as real-time path planning or any-time search) techniques are used for agent navigation.
These techniques find application in such disparate fields as molecular biology and economics. They have also been used in solving problems related to crowd behavior during a panic situation.[2]
History
The idea of agent-based modeling was developed as a relatively simple concept in the late 1940s. Since it requires computation-intensive procedures, it did not become widespread until the 1990s. After that, with the development of computer hardware and software, crowd simulation gradually attracted more attention. People started to simulate virtual human crowds and crowd behavior. After solving the problems in basic geometry simulation, research progressed into complex agent representation for crowd simulation, using the collected data to serve real life.
Background
Crowds are ubiquitous in the real world and are an important component for evacuation planning and emergency response training systems. The problem of simulating a large number of virtual agents or human crowds has been studied in different fields including computer graphics, social and behavioral sciences, architecture, physics, psychology, civil and traffic engineering, and robotics. In particular, crowds are regarded as complex dynamical systems that exhibit distinct characteristics, such as emergent behaviors, self-organization, and pattern formation due to multi-scale interactions among individuals and groups.
Agent representation
Deformable polygoal agents
Pitiot et al.[1] proposed a method for real-time simulation for crowds which includes complex and deformable shapes. The main idea is to use polyhedral bounding cages to control the deformations and animations of agents. For collision avoidance and proximity queries, they use the footprints of the cages on the ground surface.
The model behavior is presented on the basis of external and internal forces. The external forces control agents to move away from each other, while the internal forces ensure certain elasticity. The positions and velocities are transformed as follows:
- for every vertex and edge, a potential field is computed and the generated forces applied to the agents in its vicinity;
- for every polygonal agent, its Shape Matching forces are computed and these internal forces applied to its vertices;
- for every vertex, those forces are numerically integrated to compute its new position and velocity.
Interaction forces
Every vertex generates a spherical force field. This force field decreases as a second order polynomial function of the distance. Every polygonal agent and every obstacle generates a force field whose intensity is maximal inside the polygon and decreases with the distance to that polygon. Special attention is given to possible interpenetrations as numerical integration on discrete time steps could produce unwanted situations where some vertices lay inside these polygons.
Shape matching
Firstly, the Shape Matching algorithm stores the initial position of the deformation cage’s vertices of the polygonal agent. Then, when those vertices move during the animation process, a translation and rotation of the initial shape is computed to fit the new shape as close as possible. This computation gives a goal to each vertex that would maintain the initial shape. Finally, the plasticity of the agent is controlled through two parameters: α and β. β controls the importance of following the goal given to each vertex while α × β controls the freedom given to the fitting algorithm.
Integration
When all force fields are estimated, a classical Euler integration method is used.
Proximity queries
The environment is modeled as a multiresolution surface mesh that allows the simulation to take place on any manifold. The agents can move on this mesh, except across faces that were explicitly marked as obstacles (such as walls, roofs or doors). Agents’ vertices are registered within the face they belong to. This information is updated each time a vertex crosses an edge. This information leads to efficient topological queries to retrieve the list of agents in the vicinity of a given face.
The vertices of polygonal agents query their environment like the other agents do. The edges of polygonal agents are registered as described hereafter. The registration of an edge consists in spanning a particle from one vertex to the other to gather the faces of the environment that have been crossed. The edge is registered as contained in all those faces. The vertices and edges are registered so that their force fields can be considered by other agents. For that purpose, every agent retrieves registered entities from their current face and its one-ring, i.e. its immediate vicinity.
Complex behavior agent
Using navigation fields to control crowds
Patil et al[3] created an algorithm that allows a user to specify guidance fields that direct the agents in a simulation. Changing what the guidance fields are allows the user to see what the best way for people to travel through an area is. An example use of this algorithm would be a festival organizer wanting to see what the best way to have people go through the festival is. The festival organizer can change the guidance fields to see which suggested path allows for the least congestion.
Hybrid Crowds
Dense crowds exhibit a low interpersonal distance and a corresponding loss of individual freedom of motion. This observation suggests that the behavior of such crowds may be modeled efficiently at a coarse level, treating its motion as the flow of a single aggregate system.[4] The "Hybrid crowds" solution is : take density of the agents into consideration. For example, Whenever the density of crowds agents is larger than 4 per square meter, this group of people will be treated as a whole. This includes modeling the crowd as a fluid and a continuum that responds to local influences by assuming that the individuals in the continuum move so as to optimize their behavior to reach non-local objectives [Hughes 2002]. Thus, we can apply same path planning algorithm or other motion function to this group, which saves a lot of computation resource. This method makes the program run very efficiently, when both the number and density of crowds are high.
Related algorithm
Multi-agent navigation graph (MaNG)
Multi-agent navigation graph (MaNG) is a new data structure which is constructed from the first and second order of Voronoi diagrams.[5] The MaNG is used to compute the real-time path planning for each agent in a complex environment. In multi-agent planning, each moving agent represents a dynamic obstacle for the remaining agents. Hence, the goal is to compute a global navigation data structure that provides the clearance information for each agent. In particular, for each agent we want to compute a graph that provides maximal clearance to the obstacles and remaining agents.[5]
Applications
Human Motion Simulation
There are many animation techniques that are capable of producing high-quality motions of human characters. Beyond that, interactive applications such as games can respond to user input and synthesize new results in real time. Mostly, a human motion simulation in virtual dynamic world employs a framework under the idea of model predictive control.
Off-line approach
Many recent approaches which track motion data have found approximately optimal control policies by using off-line pre-computation methods such as feedback error learning or simplex methods. Since the goal of an off-line approach is to produce a new motion with new content, data is used to restrict the search space of possible solutions[6] to model simplified equations of motion, and to learn parameters of motion style.[7]
References
- 1 2 Pitiot, Thomas; Cazier, David; Jund, Thomas; Habibi, Arash; Kraemer, Pierre (September 28, 2016). "Deformable polygonal agents in crowd simulation". Computer Animation And Virtual Worlds. 25(3-4): 343–352. ISSN 1546-4261.
- ↑ Baig, Mirza; Barakova, Emilia; Regazzoni, Carlo; Rauterberg, Matthias (2014). "Realistic Modeling of Agents in Crowd Simulations". IEEE, 2014 5th Intelligent Systems, Modelling and Simulation (ISMS): 507–512. doi:10.1109/ISMS.2014.93.
- ↑ Patil, Sachin; van den Berg, Jur; Curtis, Sean; Lin, Ming; Dinesh, Manocha. "Directing Crowd Simulations Using Navigation Fields" (PDF). gamma.cs.unc.edu. Retrieved 6 October 2016.
- ↑ Lin, M. C., Manocha, D., Eifert, L., & Rodriguez, A. (2011). Interactive behavior modeling for large-scale crowd simulations. In20th Annual Conference on Behavior Representation in Modeling and Simulation 2011, BRiMS 2011. (pp. 177-184)
- 1 2 Sud, A.; Andersen, E.; Curtis, S.; Lin, M. C.; Manocha, D. (2008-05-01). "Real-Time Path Planning in Dynamic Virtual Environments Using Multiagent Navigation Graphs". IEEE Transactions on Visualization and Computer Graphics. 14 (3): 526–538. doi:10.1109/TVCG.2008.27. ISSN 1077-2626.
- ↑ Liu, C. Karen; Hertzmann, Aaron; Popović, Zoran (2005-01-01). "Learning Physics-based Motion Style with Nonlinear Inverse Optimization". ACM SIGGRAPH 2005 Papers. SIGGRAPH '05. New York, NY, USA: ACM: 1071–1081. doi:10.1145/1186822.1073314.
- ↑ Sok, Kwang Won; Kim, Manmyung; Lee, Jehee (2007-01-01). "Simulating Biped Behaviors from Human Motion Data". ACM SIGGRAPH 2007 Papers. SIGGRAPH '07. New York, NY, USA: ACM. doi:10.1145/1275808.1276511.
External links
- SteerSuite, An open-source framework for developing and evaluating crowd simulation algorithms