Computer Graphics - Fall 2016
by Dr. Mubbasir Kapadia
Computer Science department,
Rutgers - The state University of New Jersey

Agents – are imparted with artificial intelligence, that guides them based on one or more functions, such as sight, hearing, basic emotion, energy level, aggressiveness level, etc. These agents are given goals to achieve while there are obstacles in a simulated environment. They interact with each other and the environment to achieve their goal just like how a human crowd would. In Computer Graphics, Crowd Simulation is the process of simulating such Intelligent agents. Their intelligence is derived from studying human behavior and interaction in crowd and imparting the learned knowledge to simulate collective behavior. Complex Agent representation deals with the various ways by which agents are simulated to mimic realistic crowd behavior. Agent based models is one such class of Computational models that deals with simulating the actions and interaction of autonomous agents with a view to assessing their effects on the environment as a whole. Crowd Simulation is the process of simulating large numbers of people, each interacting in one environment. These agents are expected to move to their goals, interact with their environment, and respond to each other. Observed human behavior and interactions are taken into account to replicate collective behavior. Crowd simulations have many uses, including improving architectural planning, enhancing training environments and virtual realties, and driving artificially-intelligent (AI) characters in games and movies. 

Agent based crowd simulators have access to several motion engines and animatino stes which define behavioral output types. These types can range from basic behaviors like changing direction, to complex behaviors like spreading shoulders to clear its path. The feature set of the crowd simulator and the underlying agent model define the complexity of agent behavior.

Computer-generated crowds of virtual humans gain a lot of attention these years. Applications are multiple. Accurate crowd simulation is required for risks and evacuation planning. The entertainment industry is demanding of realistic looking crowd of virtual characters in order to create amazing scenes in movies, commercials or video games. Believable virtual crowds are the key of success for virtual therapies treating agoraphobia. Real-time 3D crowds could populate virtual cities and virtual worlds can be found on the Internet.

Human beings are the most complex creature in the world, thus the most difficult to simulate. Crowd simulation nowadays is based on foundations of the early representation of small creatures.

1987 Flocks of birds (Reynolds) ^[1]..

1994 Schools of fish (Tu and Terzopoulos).

1989 FLocks of animated birds shown in the movie Eurhythmy.

1996 Bouvier and Guilloteau presented a crowd simulation in immersive space management and a new approach of particle systems as a generic model for simulations of dynamic systems.

1997 Brogan and Hodgins simulated group behaviors for systems with significant dynamics.

2001 Thalmann presented a hierarchical model for real-time simulation of virtual human crowds

2002 O’Sullivan et al. described a simulation of crowds and groups with level of details for geometry, motion, and behavior.

One of the most influential agent-based models that utilized complex agent representation to address panic situations is the Helbing's Social-Forces model ^[2]. Social-Forces correspond to the physical, social and psychological interactions that happen between multiple humans in a crowd. These forces were derived using existing physical forces and granular interactions etc. to model human crowd panic behavior. In general, any agent i has multiple forces acting on him/her while in an environment of obstacles and other agents. There is an interaction and/or repulsive force between the agent and other agents especially during an escape situation. There is also a repulsive force from obstacles such as walls. These forces were mathematically modeled and simulation were run to study how individuals in a crowd of humans behavior. These are mainly used in crowd simulation, computer graphics, virtual reality, and urban planning etc.

Social Forces model was proposed in 2000 by Helbing and others to study panic behavior in human crowd. After studying multiple crowd stampede investigations, socio-psychological literature, reports and engineering handbooks, following observations on the characteristic features of escape panics were made:

1. People move or try to move considerably faster than normal ^[3].
2. Individuals start pushing, and interactions among people become physical in nature.
3. Moving and, in particular, passing of a bottleneck becomes uncoordinated ^[4].
4. At exits, arching and clogging are observed, building up jams ^{[5] [6]}.
5. The physical interactions in the jammed crowd add up and cause dangerous pressures up to 4,450 N m-1 (refs 2, 5) which can bend steel barriers or push down brick walls ^[7].
6. Escape is further slowed by fallen or injured people acting as `obstacles'.
7. People show a tendency towards mass behaviour, that is, to do what other people do ^[8].
8. Alternative exits are often overlooked or not efficiently used in escape situations ^[9].

These observations were leveraged to model collective phenomenon of escape panic in the framework of self-driven many particle systems. 'social forces' model was framed using socio-psychological and physical forces.

Consider there are ${\displaystyle N}$ agents ${\displaystyle i}$ with mass ${\displaystyle m_{i}}$ moving with a desired speed ${\displaystyle v_{i}^{0}}$ in a certain direction ${\displaystyle e_{i}^{0}}$ and therefore tends to correspondingly adapt to actual velocity ${\displaystyle v_{i}}$ with a certain time ${\displaystyle \tau _{i}}$. Simultaneously, the agent also tries to keep a velocity-dependent distance from other agents ${\displaystyle j}$ and walls or static non living obstacles ${\displaystyle W}$. In order to model the force acting on such an agent, the change of velocity in time ${\displaystyle t}$ is given by the acceleration equation as

${\displaystyle m_{i}{\frac {dv_{i}}{dt}}=m_{i}{\frac {v_{i}^{0}(t)e_{i}^{0}(t)-v_{i}(t)}{\tau _{i}}}+\sum _{j(\neq i)}f_{ij}+\sum _{W}f_{iW}}$

where the change of position ${\displaystyle r_{i}(t)}$ is given by the velocity ${\displaystyle v_{i}(t)=dr_{i}/dt}$. Inspired by granular interactions ^{[10] [11]} and the agents' tendency to stay away from each other, the force acting on an agent as a result of other agent ${\displaystyle j}$ can be described as

${\displaystyle f_{ij}=\{A_{i}\exp[(r_{ij}-d_{ij})/B_{i}]+kg(r_{ij}-d_{ij})\}n_{ij}+\kappa g(r_{ij}-d_{ij})\Delta v_{ij}^{t}t_{ij}}$

where the first term represents the repulsive interaction force between two agents, ${\displaystyle A_{i}}$ and ${\displaystyle B_{i}}$ are constants, ${\displaystyle d_{ij}=||r_{i}-r_{j}||}$ denotes the distance between agents' center of mass and ${\displaystyle n_{ij}=(r_{i}-r_{j})/d_{ij}}$ is the normalized vector pointing from agent j to i. Also 'body force' ${\displaystyle k(r_{ij}-d_{ij})n_{ij}}$ counteracts body compression and 'sliding friction force' ${\displaystyle \kappa (r_{ij}-d_{ij})\Delta v_{ij}^{t}t_{ij}}$ impedes relative tangential motion, if agent ${\displaystyle i}$ and ${\displaystyle j}$ are very close to each other. Similarly considering an environment with physical obstacles, interaction with such obstacles are considered analogously. If ${\displaystyle W}$ is a wall at a distance ${\displaystyle d_{iW}}$ from the agent ${\displaystyle i}$, ${\displaystyle n_{iW}}$ the direction perpendicular to the wall, and ${\displaystyle t_{iW}}$ the direction tangential to it, then the interaction force between the agent and the wall can be determined using,

${\displaystyle f_{iW}=\{A_{i}\exp[(r_{i}-d_{iW})/B_{i}]+kg(r_{i}-d_{iW})\}n_{iW}+\kappa g(r_{i}-d_{iW})(v_{i}t_{iW})t_{iW}}$

These force equations can be utilized to simulate intelligent agents in various environments under varying conditions and constraints to test panic behavior. These models help realistically simulate an individual human's tendency in the presence of a crowd of humans.

These equations more precisely model human panic behavior. Different simulations using these equations have resulted in the following conclusions.

1. As long as the desired velocity ${\displaystyle v_{i}^{0}}$ is lesser than 1.5 m/s, there is normal behavior. Once the velocity goes beyond that, panic strikes and clogging and arch-like formation happens near narrow exits in the environment. Escaping would become improper and uncoordinated.
2. 'Fast is slower effect' is observed when agents increase their velocity and try to escape. This reduces the average velocity of the entire group thereby resulting in more people getting stuck without escaping.
3. When a situation arises where some people inside a smoke filled room have to find exits and consequently leave the room, it is best to have the following direction

${\displaystyle e_{i}^{0}(t)=Norm[(1-p_{i})e_{i}+p_{i}<e_{j}^{0}(t)>_{i}]}$

where ${\displaystyle p_{i}}$ decides the degree of panic of an individual agent. If ${\displaystyle p_{i}}$ is low, then it results in individualistic behavior where one decides to follow his/her own direction ${\displaystyle e_{i}}$ in finding an exit. If ${\displaystyle p_{i}}$ is high, then the individual follows the average direction of the neighbors around ${\displaystyle <e_{j}^{0}(t)>_{i}}$ resulting in herding behaviors. It was found that, it is best to mix and match both behaviors to achieve optimal results.

These results are useful in modelling an environment before construction ^[12]. Strategically placing exits and entrances and other pathways, hallways etc. while planning an urban environment, makes a great impact during escape panic situations. These models would help simulate such behavior in any environment and the results can be used to fine tune spaces to avoid catastrophe ^[13]. This knowledge can also be used to generate realistically behaving human agents in games and 3D visuals or virtual reality ^[14].

Collision avoidance is another challenging problem to be addressed. The collision avoidance techniques should be efficient enough to prevent a large number of agents from bumping into each other in real time. The greatest difficulty of collision avoidance is from the  absence of other agents’ current velocities. A common solution to this problem is to assume that the other agents are dynamic obstacles whose future motions are predicted as linear extrapolations of their current velocities. The agent then selects a velocity that avoids collisions with the extrapolated trajectories of other agents. This is the idea of velocity obstacle. Considering the case in which each agent navigates independently without explicit communication with other agents, van den Berg et al. (2008) propose a new concept, the “reciprocal velocity obstacle,” which takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision avoidance reasoning. This concept can be applied to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles for real-time simulation.  

A simple method for describing the crowd behavior is through group interrelationships.  The group parameters are specified by defining the goals (specific positions which each  group must reach), number of autonomous virtual humans in the group, and the level of dominance from each group. This is followed by the creation of virtual humans based on the groups’ behavior information. The sociological effects modeled in the presented rules are: • Grouping of individuals depending on their interrelationships and the domination effect • Polarization and the sharing effects as the influence of the emotional status and domination parameters • Relationship between autonomous virtual humans and groups  

• Emergency and Evacuation Simulations

A major use of Real Time Search is for helping make buildings better designed for emergency evacuation simulations. The usage of crowd simulators with real time search lets you examine crowd behavior in emergency situations which is nearly impossible to do safely with real people ^[15]. Humans have a predictable reaction to emergency situations. This allows the agents in a crowd simulation to be programmed with a realistic real time search to examine what design has the best evacuation capabilities. The use of real time search allows the crowd simulations to support Multi-Agent systems that are more realistic compared to others ways of crowd simulation. Social forces are then used to differentiate the agents to make the agents unique rather than them having exactly the same characteristics ^[16].

• Architecture Planning

• Human Motion Simulation

• 3D computer graphics
• Artificial intelligence
• Complex agent representations for crowd simulations
• Crowd analysis
• Crowd tracking
• Emergent behavior
• Multi-agent system
• Particle system