Velocity-based modeling of physical interactions in dense crowds

Abstract

We present an interactive algorithm to model physics-based interactions in dense crowds. Our approach is capable of modeling both physical forces and interactions between agents and obstacles, while also allowing the agents to anticipate and avoid upcoming collisions during local navigation. We combine velocity-based collision-avoidance algorithms with external physical forces. The overall formulation produces various effects of forces acting on agents and crowds, including balance recovery motion and force propagation through the crowd. We further extend our method to model more complex behaviors involving social and cultural rules. We use finite-state machines to specify a series of behaviors and demonstrate our approach on many complex scenarios. Our algorithm can simulate a few thousand agents at interactive rates and can generate many emergent behaviors.

1 Introduction

Multi-agent simulations are frequently used to model a wide variety of natural and simulated behaviors, including human crowds, traffic, groups of birds, bees, fish, ants, etc. In many of these applications, it is important for the agents to interact in a physical manner with each other and the environment. Agents often collide, push, and impart forces on other agents and on the obstacles in the environment, changing their trajectory or behavior. The challenge is to model these interactions in large multi-agent systems at interactive rates. Many multi-agent simulation techniques focus mainly on local navigation based on anticipatory collision avoidance and does not explicitly take into account physical interactions between agents or between agents and obstacles in the environment. Moreover, collision-avoidance behavior towards the obstacles is limited to the static obstacles.

Methods which focus only on collision avoidance can work well in scenarios with low to medium density (e.g. $<$2 agents/m$^2$), where there is enough space for the agents to navigate freely without collisions. However, there are many situations such as political rallies, religious gatherings, or public subway stations, where agents can get very close to each other, and physical interactions between the agents frequently occur. An agent may be pushed, or bumps into other agents in dense scenarios. For these kinds of dense crowds, it is important to model the direct physical interaction between the agents. In addition, the indirect effect of the physical impact transferred to neighboring individuals in the crowd, such as the domino effect of people leaning against each other, may impact the trajectory of a high number of agents in a crowd. In extremely dense crowds, the forces from crowds sometimes become very large and can completely change the trajectory of an agent or make them fall. In these cases, crowd disasters can occur [37]. For all these reasons, understanding and simulating physical interaction between agents is necessary to simulate and analyze dense crowd scenarios. As the density of the crowd increases, it is more likely that even small motions can cause physical interactions with neighboring agents.

Similarly, the forces from many individual agents combine to produce a large effect on the environment. For example, crowds may push stacked boxes while moving through a narrow corridor and somebody may be hit by a falling boxes. Dense, aggressive crowds bend fences or break walls. To simulate such scenarios, we need to develop appropriate two-way coupling techniques between autonomous agents and the obstacles in the environment.

Main results In this paper, we present a new method to model physical interactions between agents and objects in an interactive velocity-based multi-agent framework. Our approach incorporates both an agent’s ability to anticipate and avoid upcoming collisions, while also modeling physical responses to external forces in a single unified framework.

We compute the velocity of each agent as a linear programming problem in the velocity space. The resulting approach is efficient and can be used to simulate dense scenarios with thousands of agents at interactive rates. We further extend our method to model more complex behaviors involving social and cultural rules. We use finite state machines to define a series of behaviors as well as parameters for our physical interaction model. These parameters are used to distinguish between responsive collision-avoidance behaviors and force-based physical interactions. For example, we use our approach to simulate various behaviors during the Tawaf ritual (Fig. 1). We show that our velocity-based formulation can reliably simulate tens of thousands of agents in very dense scenarios (maximum density 8 agents/m), and model the physical interactions. Furthermore, we show that our approach is quite robust and we can use large time steps. We have also integrated our approach with the Bullet Physics Engine [1], and highlight the performance in many scenarios (Fig. 2).

Fig. 1

Simulation of Tawaf. We simulate pilgrims performing the Tawaf ritual. In our scene, about 35,000 agents circle around the Kaaba, performing a short prayer at the starting line while some of the agents try to get towards the Black Stone at the eastern corner of Kaaba. We model the interactions between the agents in a dense crowd, such as when the agents are pushed by crowd forces (see video)

Fig. 2

Wall breaking. We demonstrate the physical forces applied by cylindrical agents to breakable wall obstacles. Our algorithm can model such interactions between the agents and the obstacles in dense scenarios at interactive rates

The rest of the paper is organized as follows. Section 2 gives a brief review of related work, Sect. 3 describes velocity-based physical interaction model combining anticipatory collision avoidance and physical forces, and Sect. 4 discusses high-level behavior modeling using a finite-state machine. We highlight the performance on different scenarios focusing on physical interactions in Sect. 7.

2 Related work

2.1 Multi-agent motion models

Many approaches have been proposed to simulate the motion of large number of agents and crowds. Often these models are based on rules, which are used to guide the movement of each agent. An early example of such an approach is the seminal work of Reynolds [29], which uses simple rules to model flocking behavior.

Force-based methods, such as the social force model [11], use various forces to model attraction and repulsion between agents. These forces are not physically based; rather, they provide a mechanism to model the psychological factors that govern how agents approach each other. Other approaches model collision-avoidance behavior with velocity-based techniques [13, 28, 41] or vision-based steering approaches [26].

Other techniques have been proposed to model complex social interaction. HiDAC [27] uses various rules and social forces to model interactions between agents and obstacles; collision avoidance and physical interactions between agents and objects are handled using repulsive forces. The composite agent formulation [43] uses geometric proxies to model social priority, authority, guidance, and aggression. Many other multi-agent simulation algorithms exist, using techniques inspired by different fields such as sociology [24], biomechanics [8], and psychology [7, 9, 16, 30] to model different aspects of agent behaviors and decision models. These approaches are able to generate realistically heterogeneous behaviors for agents. Our approach to model physical interactions can also be combined with many of these approaches.

Other techniques use cognitive and decision-making models to generate human-like behaviors [32, 40, 44], or use data-driven approaches to the problem [19, 21].

2.2 Dense crowd simulation

Density and crowd behaviors are closely related. The fundamental diagram is an empirically measured relationship between the pedestrian density and speed [31]. Some crowd simulation algorithms tend to adhere to the fundamental diagram. Curtis et al. [5] propose a method to simulate density-dependent behaviors for velocity-based collision-avoidance technique. Lemercier et al. [20] focus on generating realistic following behaviors based on varying densities.

Other approaches for modeling crowds are based on continuum or macroscopic models [12, 25, 39]. In particular, Narain et al. [25] present a hybrid technique using continuum and discrete method for aggregate behaviors in large and dense crowds. These continuum methods are mainly used to simulate the macroscopic flow and may not model the detailed interactions between the individuals and the obstacles. In contrast, our approach simulates agent–agent and agent–obstacles physical interaction.

Some force-based techniques are used to simulate the interactions between agents in a dense crowd. Helbing et al. [10] model panic behavior with two additional physical forces (body force and sliding friction) in addition to the social forces. Yu and Johansson [45] propose a force-based technique to model the turbulence-like motion of a dense crowd by increasing the repulsive force.

2.3 Force-based techniques for character animation

There has been extensive work on using physics-based models to improve character animation. Sok et al. [36] use a force-based approach to ensure that the resulting motions are physically plausible. Other approaches consider geometric and kinematic constraints [35] or use interactive methods for character editing [14]. These techniques, which are primarily based on enhancing motion-captured data, can be used to simulate behaviors of and interactions between the characters and obstacles in their environment.

Many hybrid techniques have been proposed that bridge the gap between physics-based simulation of character motion and pre-recorded animation of characters to model responsive behavior of character [33, 46]. Muico et al. [23] propose a composite method to improve the responsiveness of physically simulated characters to external disturbances by blending or transitioning multiple locomotion skills.

Our approach is quite different from these methods. Unlike character animation techniques that mainly focus on generating the full-body motion of a relatively small number of characters, we focus on generating physically plausible interactions between a large number of agents in dense scenarios.

2.4 Crowd simulation in game engines

Some commercial game engines or middleware products can simulate character motion or crowd behavior. This includes Natural Motion’s Euphoria, which simulates realistic character behavior based on biomechanics and physics simulation. There are also commercial AI middlewares for game engines that combine crowd and physics simulation: Kynapse, Havok AI, and Unreal Engine are examples of these. These systems primarily focus on the local and global navigation of each agent using navigation meshes and local rules. Other crowd simulation software such as Miarmy, Massive, and Golaem are integrated with modeling and rendering tools, and used to create character animation. Our approach to generating physical interactions can be combined with these systems to improve local interactions between the agents and the obstacles in the scene.

3 Velocity-based modeling of physical interactions

Our approach extends the approach described in [15] to model the physical interactions between a large number of agents and obstacles. In this section, we give an overview and a summary of techniques used to compute the forces.

3.1 Overview

Local navigation and anticipatory collision avoidance of agents can be efficiently modeled using reciprocal velocity obstacles, which impose linear constraints on an agent’s velocity to help it navigate its environment. We extend this framework by representing the effect of physical forces on agents also as linearized velocity constraints. This allows us to use linear programming to compute a new velocity for each agent—one which takes into account both the navigation and force constraints imposed upon that agent. Figure 3 gives an overview of the full simulation system.

Fig. 3

System overview. The motions for objects and agents are computed by a rigid body dynamics solver and a constrained optimizer, respectively. Physical interactions between agents and obstacles determine forces. For obstacles, the forces serve as inputs to the rigid body system; for agents, they become force constraints. These force constraints are combined with the original ORCA planning constraints and serve as inputs to optimization algorithm

Agents are assumed to have a preferred velocity. This is the velocity at which the agent would travel if there were no collisions to avoid or physical forces acting on the agent. At each time step, an agent computes a new velocity that satisfies the velocity constraints, then updates its position based on the preferred velocity. There are two types of constraints which we impose on an agent’s velocity:

• ORCA constraints guide the collision avoidance by specifying the space of velocities which are guaranteed to remain collision-free for a given period of time [41].

• Force constraints account for forces which arise through physical interactions with other agents and objects.

Given an agent A with neighbors B, the permitted velocities for A, $\hbox {PV}_\mathrm{A}$ is the union of ORCA constraints and force constraints. We can state our agent update algorithm as an optimization problem. Formally:

$$\begin{aligned}&\hbox {PV}_\mathrm{A} = \hbox {FC}_\mathrm{A} \cap \bigcap _{\mathrm{B} \ne \mathrm{A}}\hbox {ORCA}_{\mathrm{A}|\mathrm{B}}, \end{aligned}$$

(1)

$$\begin{aligned}&{\mathbf {v}}^\mathrm{new} = \mathop {\hbox {argmin}}\limits _{{\mathbf v} \in \hbox {PV}_\mathrm{A}} \Vert {\mathbf v} - {\mathbf v}^\mathrm{pref}\Vert , \end{aligned}$$

(2)

where ${\mathbf {v}}^\mathrm{new}$, ${\mathbf {v}}^\mathrm{pref}$ and $\hbox {FC}_\mathrm{A}$ are the new velocity, preferred velocity, and force constraints of A, respectively. $\hbox {ORCA}_{\mathrm{A}|\mathrm{B}}$ is ORCA constraints of A given its neighbors B.

3.2 Anticipatory collision avoidance

There are some significant differences between an agent’s interaction with a neighboring agent and a dynamic obstacle, in terms of the motion computation. The motion of obstacles (e.g. rigid bodies) is governed by Newtonian physics, since these objects have no will and are unable to initiate movement on their own. As a result, the agents cannot assume that the obstacles will anticipate collisions and change trajectory to avoid them. We take account such difference into agent’s collision-avoidance behavior.

3.2.1 Agent–agent collision avoidance

ORCA constraints are defined by a set of velocities that are guaranteed to avoid upcoming collisions with other nearby agents. The constraints are represented as the boundary of a half plane containing the space of feasible, collision-free velocities. Given two agents, A and B, which we represent as 2D discs, we compute the minimum vector $\mathbf {u}$ of the change in relative velocity needed to avoid collision. ORCA enforces this constraint by requiring each agent to change their current velocity by at least 1/2 $\mathbf {u}$. The ORCA constraint on A’s velocity induced by B would be:

$$\begin{aligned} \hbox {ORCA}_{\mathrm{A}|\mathrm{B}}=\left\{ \mathbf {v}|\left( \mathbf {v}-(\mathbf {v}_\mathrm{A}+\frac{1}{2} \mathbf {u})\right) \cdot \hat{\mathbf {u}} \ge 0\right\} , \end{aligned}$$

(3)

where $\mathbf {v}_\mathrm{A}$ is A’s current velocity and $\hat{\mathbf {u}}$ is the normalized vector $\mathbf {u}$.

If A has multiple neighboring agents, each will impose its own ORCA constraint on A’s velocity. Local navigation is computed by finding the new velocity for A (${\mathbf {v}}^\mathrm{new}$) which is closest to its preferred velocity (${\mathbf {v}}^\mathrm{pref}$) while respecting all the ORCA constraints.

3.2.2 Agent–dynamic obstacle collision avoidance

The dynamic object $O$ is represented, like the agents, as an open disc that is a 2D projection of the bounding sphere of the object. We use this bounding shape for collision avoidance since the agent’s navigation is performed in 2D space, but the underlying rigid body simulation uses an 3D object shape for handling collisions with other rigid bodies in the scene.

Agents try to avoid collisions with dynamic obstacles whenever the dynamic obstacles are within agent’s visual range. However, agents do not assume objects will reciprocate in avoiding collisions. Therefore, assuming that a change in velocity of $\mathbf {u}$ (Sect. 3.2.1) is required to avoid an anticipated collision with an obstacle, the collision-avoidance constraint for agent A induced by object O is:

$$\begin{aligned} \hbox {ORCA}_{\mathrm{A}|\mathrm{O}}^{\tau }=\{\mathbf {v}|(\mathbf {v}-(\mathbf {v}_\mathrm{A}+\mathbf {u}))\cdot \hat{\mathbf {u}} \ge 0\}. \end{aligned}$$

(4)

3.3 Constraints from physical forces

We give brief description of the forces in this section. Contact forces include pushing forces and collision forces, and model collision response force or an attempted pushing. inferred forces include deceleration force and resistive force, and model the impact of forces on agent’s motion. For more detail, please refer to [15].

3.3.1 Force computation

Pushing forces Pushing is one of the ways for agents to physically interact with each other [27]. In our formulation, the pushing force $\mathbf {f}_{i|k}^\mathrm{p}$ exerted by an agent $i$ pushing another agent $k$ can be given as:

$$\begin{aligned} \mathbf {f}_{i|k}^\mathrm{p} = \rho _k {f}_\mathrm{p}\frac{\mathbf {p}_{k}-\mathbf {p}_{i}^{+}}{\Vert \mathbf {p}_{k}-\mathbf {p}_{i}^{+} \Vert }, \end{aligned}$$

(5)

where $\mathbf {p}_{i}$ and $\mathbf {p}_{k}$ indicate the positions of agent $i$ and $k$, respectively, and $\mathbf {p}_{i}^{+}= \mathbf {p}_{i}+\mathbf {v}_{i}\Delta {t}$ is the pushing agent’s future position at the next time step. $f_\mathrm{p}$ is a magnitude of total pushing force of agent $i$ towards all interacting agents. It can be defined by the designer, but in our examples, we compute this value to be proportional to agent $i$’s current speed. $\rho _{k}$ is used to define the weight of pushing force towards each interacting agent $k$. For our examples, we formulate it as an inverse of number of agents that are pushed.

Collisions In case of collisions between agents, a collision resolution force is applied. This force is computed based on the physically based simulation approach proposed by Baraff [2]. We consider only linear momentum and simulate agents as radially symmetric discs. For an agent $i$ colliding with agent $k$, the collision force $\mathbf {f}^\mathrm{c}$ is computed as follows:

$$\begin{aligned}&\mathbf {f}^\mathrm{c} = \left( \dfrac{-(1+\epsilon )\mathbf {v}^\mathrm{rel}}{1/m_{i}+1/m_{k}}\cdot \mathbf {n}\right) /\Delta t, \end{aligned}$$

(6)

where $\mathbf {n}$ is the collision normal, pointing towards agent $i$ from agent $j$; $v^\mathrm{rel}$ is relative velocity; and $m_{i}$ and $m_{k}$ are the mass of agent $i$ and agent $k$, respectively. $\epsilon$ is the coefficient of restitution. In our examples, we assign a uniform mass to each agent, but any reasonable mass value can be used for the simulation.

In case of a collision between an agent and a dynamic object, the impulse force is computed in the same way. A force with the same magnitude but with the opposite direction is applied to the object, which also results in change of angular motion generated by the torque $\mathbf {\tau }^\mathrm{c}$:

$$\begin{aligned}&\mathbf {\tau }^\mathrm{c} = \mathbf {f}^\mathrm{c} \times \mathbf {r}_\mathrm{o}, \end{aligned}$$

(7)

where $\mathbf {r}_\mathrm{o}$ is the displacement vector for the contact point of the object.

Deceleration forces When an agent reduces speed while preserving direction to within a certain threshold ($\theta _\mathrm{d}$), we introduce a force into the system based on this velocity change. The deceleration force generated by agent $i$’s deceleration is defined as:

$$\begin{aligned} \mathbf {f}_{i}^\mathrm{d} = \left\{ \begin{array}{l@{\quad }l} k_\mathrm{thresh} m_i {\Delta \mathbf {v}_i}/{\Delta t} &{} \hbox {if } (\Delta \hat{\mathbf {v}}_i \cdot \hat{\mathbf {v}}_i) < -cos(\theta _\mathrm{d}), \\ 0 &{} \hbox {otherwise}, \end{array} \right. \end{aligned}$$

(8)

where $\Delta \mathbf {v}_i = \mathbf {v}_i-\mathbf {v}_i^{-}$ is the change in velocity from the previous time step to the current time step. Agents can absorb or transform forces, which are approximated by a parameter $k_\mathrm{thresh}$. We assume that the speed reduction arises from one of two sources: self-will (e.g. sudden change of preferred velocity) or agent interaction (e.g. impending collision avoidance). When there is no interacting agent, we assume it is the former case, and the deceleration force is applied back to the agent itself. In the latter case, we distribute the deceleration force among the neighbors. A neighboring agent $k$ causes such behavior if it lies within a cone centered on $\mathbf {v}_{i}^{-}$ and is within an angular space of $2\theta _\mathrm{d}$ degrees.

Resistive forces Resistive forces occur when an agent’s computed velocity does not account for the entire change in velocity expected from the external force. This difference is propagated to neighboring agents via the resistive forces. This force is computed by the difference between the velocity $\mathbf {v}$ computed by (2) and the velocity $\mathbf {v}^{f}$ computed only from the net force applied to the agent. The resistive force of an agent $i$ experiencing the discrepancy between $\mathbf {v}^{f}$ and $\mathbf {v}$ is:

$$\begin{aligned} \mathbf {f}_{i}^\mathrm{r} = \left\{ \begin{array}{l@{\quad }l} k_\mathrm{thresh}m_i(\mathbf {v}_i-\mathbf {v}_i^\mathrm{f})/\Delta t &{} \hbox {if } \mathbf {v}_i^\mathrm{f} \ne \mathbf {0} \\ 0 &{} \hbox {otherwise}. \end{array} \right. \end{aligned}$$

(9)

As in the case of deceleration force, the resistive force is applied to the agent $i$ when there is no interacting agent. Otherwise, the resistive force is distributed equally among the interacting agents, whose position is inside a cone centered on $\mathbf {v}_i^\mathrm{f}$ and with an angular span of $2\theta _\mathrm{r}$ degrees.

The resistive force and deceleration force can be viewed as complementary to one another. The resistive force is non-zero only in the presence of external physical forces on an agent, and the deceleration force is non-zero only in the absence of such forces.

3.3.2 Force constraints

The net force $\mathbf {f}$ is the sum of all the forces applied to the agent:

$$\begin{aligned} \mathbf {f}&= \sum \mathbf {f}^\mathrm{c} + \sum \mathbf {f}^\mathrm{d} + \sum \mathbf {f}^\mathrm{r} +\sum \mathbf {f}^\mathrm{p}. \end{aligned}$$

(10)

The force constraint FC induced by the net force $\mathbf {f}$ is computed as follows:

$$\begin{aligned}&\mathbf {v}^\mathrm{f} = \mathbf {v} +\frac{\mathbf {f}}{m}\Delta t \end{aligned}$$

(11)

$$\begin{aligned}&\hbox {FC}=\{\mathbf {v}| (\mathbf {v}- \mathbf {v}^\mathrm{f})\cdot \hat{\mathbf {f}} \ge 0 \}. \end{aligned}$$

(12)

FC is a half plane whose boundary, a line through $\mathbf {v}^\mathrm{f}$, is perpendicular to the normalized force $\hat{\mathbf {f}}$. It contains a set of velocities that is equal to or greater than the minimum velocity change required by the force $\mathbf {f}$.

3.4 Benefits of force constraints

By introducing inferred forces, our method can model balance recovery motions that cannot be captured by physics-based rigid body dynamics.

Balance recovery motion When forces are applied, rigid body motion changes accordingly to the Newtonian dynamics. However, humans have the ability to absorb and resist the external forces even from unexpected events such as sudden pushes or an impact from an obstacle. In these situations, humans take effort to keep their balance creating a behavior known as balance recovery in Biomechanics [22]. Balance recovery is important to model human locomotion, and has been studied in other fields like robotics for humanoid robots [42] and in computer graphics for animated characters [34].

Typical balance recovery motions include taking additional steps or reaching and grasping an object for support. When humans fails to recover the balance, they take further adjustments to refine their initial responses. In other words, the balance recovery can affect the motion, including the trajectory, for a period of time. The balance recovery motion is a result of both physical and cognitive activity, which also depends on the environmental constraints and affordances (e.g., space to step, objects to grasp for support) [22].

We define two forces, deceleration force and resistive force that are used to simulate the behavior corresponding to balance recovery. We infer these forces from the agent’s motion at a given time, based on our assumption that the motion of an agent can be decomposed into two components: collision avoidance and Newtonian dynamics. Loosely speaking, we treat the different between the velocity implied by the physics forces and the resultant velocity produced by the simulation as a recovery force which is applied on the nearby environment and agents.

Force propagation Forces applied to an agent can propagate through a dense crowd, since one agent is likely to exert forces on others for support to recover from the external pushing force. The propagation forces can be inferred when the motion computed using constrained optimization does not match the motion expected from external physical forces. In this case, we assume that the agent’s action of balance recovery took place to resist the external physical forces. For example, when an agent decelerates at a faster rate than that implied by the external forces, we infer that the agent must be pushing against other agents or obstacles to be able to slow down so quickly. Likewise, when an agent accelerates at a rate less than that implied by external forces, we infer the agent must be pushing against other agents or obstacles, while resist the effect of the forces. These inferred propagation forces are applied to the appropriate neighboring agents during the subsequent time step.

4 Higher level behavior modeling

In many cases, the crowd or individual behaviors change over a period of time. Cultural, social norms, as well as personal goals and intentions can change a person’s behaviors over time. Likewise, individuals can exhibit role-specific behaviors, in a variety of situations which can fundamentally change how they interact with each other. A clear example of this can be seen in sporting events, where the behavior towards the players of their own team members are cooperative (and avoid collisions), whereas the behavior towards members of the opposite team often includes blocking, tackling and other forms of physical collisions. Ideally, we would like to model a full variety of such behaviors using our physically based interactions, while accounting for changes in behavior.

Incorporating such a variety of behaviors changing over time, and depending on the situation or social, cultural norms requires a way to model higher level decision-making process and behavior rules. A common approach to achieve state-dependent behaviors in general is to use finite-state machines (FSMs). In this section, we show how our simulation approach can be combined with FSMs to model such complex physical behaviors in multi-agent simulations. The resulting framework provides a natural way to define different behavior patterns and changes of those behaviors over time and in different situations.

4.1 The behavior finite-state machine

An FSM is a machine or a model which has finite number of state and transitions between the states. FSMs have been widely used as a way to model intention and decision-making process for agents in crowd simulation and games [3, 38]. For example, FSMs can describe a set of behaviors for an agent with certain social status (e.g., a leader) along with the transition of these behaviors in certain situations (e.g., safe state or dangerous state) based on the leader agent’s perceived information. Recent work has integrated such an FSM-based behavior specification with velocity-based local collision-avoidance schemes to simulate crowds displaying various behaviors [4]. We present an improved algorithm that extends this framework to produce complex simulations with physically based agent interactions.

Figure 4 shows the overall architecture of the FSM-based behavior modeling for our physical interaction model. We specify a set of actions (behaviors) for each state, along with interaction parameters that change the behavior of the individual agents and the crowd. Transitions between the FSM states are made based on the result of our physical interaction model combined with local collision-avoidance method. This corresponds to the decision-making process of an agent, which is based on the perceived information about the agent itself and its neighbors. The perceived information and the decision of current action altogether are used to compute agents’ local navigation planning. In other words, we model agents behavior using FSM by specifying the interaction parameters that define perception and local planning.

Fig. 4

Overview of FSM-based behavior modeling. FSM states are used to specify a set of available actions, along with the parameters used for physics-based interaction and local collision avoidance. Transitions between the FSM states are made based on the result of our physical interaction model combined with local collision-avoidance method

Importantly, it is the combined interplay between an agent’s perceived information and its behavioral simulation parameters that determine its actions in a simulation. For example, if we reduce an agent’s perception by only allowing it to sense very close neighbors, the agent will be less able to plan ahead to avoid collisions and more likely to run into neighbors. However, when the two agents collide, the magnitude of the interaction will be controlled by the physical interaction parameters. Therefore, a rude or hurried agent state can be created by reducing the perception range, and increasing the pushing forces, and a more polite or relaxed agent state can by made by increasing the perception range and decreasing pushing. In this way, we use the same motion model (Eqs. 1 and 2) across all the states of the FSM, but leverage the agent parameters to diversify the agent interactions.

Because of this relationship between collision-avoidance parameters and physical interaction parameters, both should be considered together when designing the FSM. Table 1 shows what both of these components should be like in terms of intentional behaviors and responsive behaviors. For intentional interactions, the agent’s primary goal is to approach the target and apply intended forces. In this case, higher anticipatory collision-avoidance behavior prevents the agent from getting closer to the target. Rather, the agent should be able to approach the target even when they perceive impending collision with the target. For example, a soccer player would even run towards the ball even when the ball is approaching the player at a high speed. To model such behavior, local collision-avoidance behavior should be minimized to allow the agent to physically interact with the target, but still be able to prevent overlap with the target object.

Table 1 Different interaction parameters for intentional behaviors and responsive behaviors

5 Results

In this section, we highlight the performance of our algorithm in different scenarios. We first show some results of our physical interaction model, and then present FSM-based behavior modeling with dodge-ball game scenario and Tawaf ritual scenario. We also analyze the approach and compare it with other techniques. We direct the readers to the video or the preliminary version paper [15] for more results on physical interaction models.

5.1 Agent–agent interaction

We demonstrate a few scenarios which highlight the effect of physical interactions between agents and how those effects propagate through crowds.

Running through scenario We demonstrate a scenario where an agent runs at a high speed and push through a dense crowd of 25 agents that are standing still. Figure 5 compares the result of our method to those achieved using multi-agent simulation without any physical interactions.

Fig. 5

Rushing through still agents. The red agent tries to rush through a group of standing agents, simulated a with only anticipatory collision avoidance and b with physical interactions. Using our method, the forces are propagated among the agents, resulting in a new distribution pattern (b)

The left side of each image shows a pushing agent (red) passing through the crowd, and the right side of each image shows the position of all other agents in the crowd after the fast-moving agent has passed. As Fig. 5 demonstrates, agents simulated without physics-based interaction use minimal motion to avoid collisions. In contrast, agents simulated using our physically based formulation resist the pushing motion (in an attempt to stand still) and propagate the effects of being pushed to other agents.

Two bottlenecks scenario In this scenario, long lines of closely spaced walking agents attempt to pass through two narrow bottlenecks, as illustrated in Fig. 6. The first bottleneck (denoted in the figure as (2)) is about the width of two agents; the second is narrower, about wide enough for one agent (denoted as (1)). A local navigation algorithm that performs collision avoidance frequently results in congestion at both the bottlenecks due to stable-arch formation of agents (highlighted with a yellow circle) in Fig. 6a. However, agents simulated by our physically based method are able to break this congestion at the bottleneck area by pushing the blocking agents. The ability to break through bottlenecks also results in a quantitatively higher rate of flow for agents using our approach. After seconds, twice as many agents make it through both the bottlenecks, using our algorithm.

Fig. 6

Two bottlenecks scenario. We simulate and compare crowd behavior at two narrow bottlenecks, which are marked with red dotted lines. Bottleneck (1) is barely wide enough for one person to pass through; bottleneck (2) is about twice that width and allows two agents to pass through it at a time. The result from collision-avoidance-only simulation results in an arch-shaped arrangement of agents in the crowd (highlighted with a yellow circle), which causes congestion at the bottleneck. Our method breaks the congestion by allowing the agents to push one other in congested conditions

5.2 Agent–object interaction

We also demonstrate the effect of forces between dynamic objects and agents. We used the Bullet Physics engine [1] to compute the motion of dynamic obstacles (3D rigid body dynamics). The results demonstrate several features of our approach:

• Dynamic obstacle avoidance: Agents try to avoid collisions with other agents and with dynamic obstacles.

• Agent–object interactions: Our method takes into account the collisions which occur between the agents and the objects. The forces generated by these collisions affect both the objects and the agents.

• User interactions: Our method is fast enough for real-time interactive simulation. Users can participate in the simulation by moving rigid bodies inside the scene; this movement dynamically changes the environment for the moving agent.

Wall breaking scenario In this scenario, long lines of agents come at a constant rate into the simulated region, which is blocked off with a movable wall made of 200 blocks glued together. This wall can be broken into separate blocks if a large external force is applied by the agents. Agents initially stop to avoid hitting the wall, but as other agents start to push from behind, the wall breaks apart and gets carried away with the agents. Figure 2 shows stills from the simulation.

Changing the various properties of the wall changes how the crowd interacts. Figure 7 shows the result of simulation with two different configurations of the wall. In the first configuration, when the blocks are tightly attached, the wall is not broken. Instead, it is moved and rotated by crowd forces, and makes a gap for the crowd to escape through. In the second configuration, when the wall consists of much heavier blocks that are glued together tightly, it does not break or move easily even after the crowd (1,200 agents) has entered the isle. In this configuration, the crowd sometimes makes a wave-like movement where the sparse density crowd movement is propagated from front to back and vice versa.

Fig. 7

Wall breaking simulations with different wall properties. a When the blocks are tightly attached, the wall is not broken. Instead, it is moved and rotated by crowd forces, and made a gap for the crowd to escape through. b When the wall consists of much heavier blocks, it does not break or move easily even after all the crowds (1,200 agents) entered the isle. In this example, sometimes crowd makes a wave-like movement where sparse density crowd movement is propagated front to back and vice versa

Cluttered office scenario In this scenario, several decomposed 3D models—a table, a chair, and a shelf, and several rigid bodies (e.g. boxes) stacked on top of each other—are placed in the way of the agents. A long stream of agents attempts to navigate past the obstacles. Users can throw boxes, which push the agents and knock over objects in the environment. Figure 8 shows a still from the simulation.

Fig. 8

Office scenario. Agents navigate to avoid office furniture. As users insert flying pink boxes into the scene, the agents get pushed, collide into each other, and avoid falling objects (see video)

5.3 Dodge-ball scenario

As an example of state-based, physical interaction, we show how our FSM-based algorithm can be used to control behavior changes in simulated game of dodge ball. Here, we created an interactive dodge-ball game, where a user can control one of the game characters, and the computer program controls the other character(s). A two-state FSM is used to specify the behaviors (see Fig. 9), with the states consisting of a defense state and an attack-state. During the attack-state, a character chases a ball and kicks it to its opponent. A character in defense-state tries to avoid the ball until the ball rolls on the ground. State transitions occur based on the location of the ball and the kicking action performed by the characters.

Fig. 9

FSM for dodge-ball scenario. We use a simple two-state FSM to specify the game rule. The states consist of defense-state and an attack-state. During the attack-state, the character chases a ball and kicks it to its opponent. A character in defense-state tries to avoid the ball until the ball fell down on the ground. State transitions occur based on the location of the ball and the kicking (applying force to the ball) action performed by the character

Figure 10 shows part of the scenario highlighting the change in interaction between the agent and the ball. The first two images, Fig. 10a, show the agent behavior in the defense-state. The user-controlled green character on the left kicks the red ball at the FSM-controlled orange character on the right. Initially the red character tries hard to avoid the ball, with the local collision-avoidance algorithm for this character considering a large perception radius, with a long time duration, when computing its motion. In cases where the agent is not able to avoid the collision (e.g., the ball is moving too fast), there is a physically simulated collision response between the ball and the agent. Due to relatively smaller mass (0.4 kg) of the ball compared to the characters (70 kg), the effect of collision and resulting forces is much larger on the ball. If the FSM agent is successful in avoiding the collision, its state will change to the attack-state (Fig. 10). Here, the agent’s collision-avoidance behavior is changed allowing it to approach the ball as fast as possible (e.g., small sight radius and large preferred velocity), then to kick the ball towards the green character. The force applied to the ball is computed based on the speed of the character, and its direction is towards the user-controlled agent.

Fig. 10

Behavior examples modeled by our method. a Green character (user-control, left) kicks the red ball to the orange character (computer control, right). Orange character is in the defense-state at that moment, and tries to avoid the ball. b When the ball falls down, the orange character’s state is changed to the attack-state. Collision-avoidance behavior is changed just to meet non-overlapping condition with the ball and the character’s preferred velocity is updated towards the ball. The orange character approaches the ball and kicks the ball to the green character

As can be seen in this example, our overall approach can model collision avoidance, collision response, applying intentional forces, and decision making for the character (e.g., goal position and transition of the state). In the supplementary video, we show an expanded version of this scenario with increased number of balls. We can observe a character chasing a ball while avoiding other dynamic obstacles, and, at times, pushing through them to attack the other character. Properly simulating these interacting behaviors requires physical interaction, local collision avoidance, and behavioral states to be combined together in the same framework as we have presented here.

5.4 Large-scale simulation: Tawaf scenario

Because our method has only a small computational cost per agent, and is stable even in dense scenarios, it can be used to produce complex, large-scale simulations with agents physically interacting across a variety of different behaviors. To illustrate this, we performed a case study in simulating the large, dense crowd performing the Islamic ritual of pilgrimage called the Tawaf.

During the Tawaf, pilgrims walk in a circle around the Kaaba, the large central structure, seven times counter-clockwise for prayers. While circulating, many pilgrims try as part of the ritual to reach the central black stone located at the eastern corner of the Kaaba; alternatively, they perform a short prayer while facing the Kaaba at the beginning of each circuit. The walkable area surrounding the Kaaba, is known as the Mataf and can support upwards of 35,000 pilgrims gather to perform the Tawaf [4].

We have extended the simulation of Curtis et al. [4], to produce a simulation of the Tawaf ritual with about 35,000 FSM-driven, physically interacting agents as described in Sect. 4.

The FSM we use, both sets the goals of the agents to follow the steps of the ritual and modifies the agent’s behavioral parameters to help achieve these goals. For example, some of the agents will probabilistically choose to move closer to the central Kaaba structure to approach a religiously significant black stone. Agent in the “Move to Black Stone” state are allowed to exert physical pushing forces on their nearby neighbors to successfully move through the dense crowd to reach the stone. Figure 11 shows all the FSM states and transition conditions, along with the descriptions about a few important variables conditions for the local navigation and physical interactions for the corresponding state. Most notably, agents exert pushing forces on the crowd if they are trying to touch to the black stone on the Kaaba or are trying to exit the Mataf after completing the ritual.

Fig. 11

Agent states and transitions. The Tawaf states are represented as blue circles and transition condition between these states are marked with arrows. We associate different properties like walking speed, pushing condition, etc., with the agent behavior

Flow Analysis We measured the average speed and density of the agents from our simulation. First, we computed the average speed in different regions of Mataf shown in [4]; there is an overall trend towards higher speed in region 6 and towards a lower speed in regions 1 and 7 when compared to the speeds of their neighboring regions (see Fig. 14). These highest speed and lowest speed regions also match with the real-world data provided by Koshak and Fouda [17]. Second, we computed the density in different regions of Mataf based on our Tawaf simulator. Empirically, the density on the Mataf floor can be as high as 8 people/m$^2$ [4]; our method gives a maximum density around 7.4 agents/m$^2$ (see Fig. 12).

Fig. 12

Density from the simulated result. Reported densities on the Mataf floor can be as high as 8 people/m$^2$ [4]; our method gives a maximum density around 7.4 agents/m$^2$

5.4.1 Effect of physical interactions

We perform two experiments to show the benefit of physical interactions in large, dense crowd settings. The first experiment shows crowd forces acting on agents. The second experiment compares the overall crowd flow simulated during the Tawaf ritual under increased pushing behaviors between agents.

Pushing in the queue to the black stone As part of the Tawaf, we simulate the movement of pilgrims waiting in lines to touch or kiss the Black Stone (the eastern cornerstone of Kaaba). Pilgrims in this region makes distinctively slow motion patterns compared to the other pilgrims circling around the Kaaba. After they touch the Black Stone, these pilgrims join the rest of circling flow and adjust to the speed of other neighbors.

In the real-world video (see the supplementary video), we can observe that some of the pilgrims in the queue are often pushed by neighboring pilgrims. We attempted to simulate such crowd force that are applied to the agents in a dense crowd. To see the effect of crowd force, we assign lower preferred speeds to the agents who have entered the beginning of the queue. Figure 13 shows the 2D comparison between the simulated queuing behavior for the Black Stone, (a) when no physical interactions added and (b) with physical interactions. Green circles represent the agents in the queue, red circles represent the agents circling around the Kaaba, blue circles represent the agents leaving the queue and start circling after given waiting time.

Fig. 13

Pushed by crowd. Green circles represent the agents in the queue waiting to touch the black stone. The green agents slow down and the result in heavy congestion at the beginning of the queue. Without physical interactions, agents are stuck in the beginning of the queue although there is a space in front of the queue to proceed. By adding physical interactions, the agents in the queue are pushed by the crowds, and move towards the black stone without breaking the queue

Due to the sudden slowdown caused by the green agents, heavy congestion is made at the beginning of the queue. Without adding physical interactions, we cannot capture the effect of crowd force applied to these agents even in such high density. Agents are stuck in the beginning of the queue although there is a space in front of the queue to proceed. By adding physical interactions, the agents in the queue are pushed by the crowds, and move towards the black stone without breaking the queue.

Pushing towards exits We also evaluate the effect of physical interactions in large crowds. First, we compare the average speed of the agents with and without physical interactions. Figure 14 shows the average speed of the agents measured in the several different regions as proposed in [17]. The overall trend of relative speeds between regions is the same with and without pushing, but the average speed increase as agents push more. In both cases, the trends match well with those reported in the Tawaf literature [17].

Fig. 14

Region speed from the simulation result. Average speed of each region of the Mataf area. It matches the overall trend corresponding to higher average speed (region 6) and lower speeds (regions 1 and 6) observed by Koshak and Fouda [17]

In addition, we run the same scenario with increased number of aggressive pushing agents. When an agent finishes the ritual, the agent is assigned a randomly selected exit (from the five exits in the Mataf area) as their goal position, and tries to push through the crowd. Since the exiting agents have to escape through a very dense crowd while also moving in the circular flow, their pushing forces affects the average speed of entire region. At any given point in the simulation, about 2 % of the total number of agents are trying to exit. By adding more pushing agents, the average speed increased about 0.2 m/s. Figure 15 summarizes the speed of the agents in each of the Tawaf regions.

Fig. 15

Comparison of average region speeds. Blue bars correspond the average speeds of the agents in each region when we introduce excessive pushing behavior to the exiting agent and queuing agents. Red bars correspond the average speeds when only the queuing agents push forwards while moving towards the black stone. Increasing number of pushing behaviors brought a 20–40 % increase in average speed

6 Analysis

Our approach is mainly designed for interactive applications that require plausible physical behavior (e.g., games or virtual worlds) as well as real-world scenarios with high crowd densities. Using a combination of force and navigation constraints that affect agents’ behavior, our approach can simulate many useful effects and emergent behaviors. For example, our formulation allows for intentionally uncooperative agents to physically push their way through a crowd by imparting physical forces to nearby agents. In addition, agents can use navigation constraints to avoid collisions with dynamic obstacles as well as other agents. By expressing all interactions as linear velocity constraints, we can naturally combine the two different simulation paradigms of forces and navigation into a unified framework and compute the new velocity for each agent using linear programming.

Performance We measured the simulation timings for the demos we presented in earlier sections (see Table 2). The timings were computed on a 3.4 GHz Intel i7 processor with 8 GB RAM. Our method efficiently simulates large numbers of agents, and also exhibits interactive performance when integrated with the Bullet Physics library.

Table 2 Performance on a single core for different scenarios

Stability analysis It is well known that many forced-based simulation models, such as social force models commonly used to simulate crowd (e.g., [11]) are prone to stability problems that can even occur at small step sizes [18]. These problems include oscillation and loss of accuracy in terms of trajectory computation. Using bigger time steps can make the problem worse. In contrast, velocity-based collision-avoidance techniques have been shown to produce stable simulations in large, dense crowds [6]. Our approach preserves this stability across time steps while still accounting for physical forces.

One way to analyze the stability of our approach is by analyzing the number of times we are unable to find a feasible velocity that satisfies all the constraints, e.g., both anticipated collision-avoidance constraints and force constraints. When this occurs, it means an agent can choose a potentially colliding velocity or is not respecting the physical constraints.

We perform a test using a scenario similar to Fig. 5. An aggressive agent pushes through 50 standing agents, and the pushed agents sequentially exert forces on adjacent neighbors by generating physical interactions. During the simulation, we measure the number of times when linear optimization fails to find the feasible velocity satisfying all the constraints. In this case, we perform higher order optimization to find a solution.

As can be seen in Fig. 16, at the peak of congestion in the simulation 95 % of the agents are able to find velocities that satisfy all their constraints. Importantly, this stability holds across a variety of time steps. As the time-step size varies from 0.01 up to 0.2, most of the agents are still able to find constraint-satisfying velocities. In general, the behavior does not change significantly across this wide range of time steps.

Fig. 16

Number of constraint optimization failures. We analyze the stability of our method by measuring the number of constraint optimization failures. At the peak of congestion in the simulation, 95 % of the agents are able to find velocities that satisfy all their constraints. Importantly, this stability holds across a variety of time steps. As the time-step size varies from 0.01 up to 0.2, most of the agents are still able to find constraint-satisfying velocities

Benefits of our method Many techniques have been proposed in the literature for simulating large numbers of agents that display a wide variety of emergent behaviors. However, the primary emphasis of these methods is on collision avoidance—avoiding any physical contact between the agents. In other words, they model how agents move around each other, but do not usually model explicit physical contacts, interactions, and external forces.

Force-based methods such as [11] use forces to model social factors (e.g., attraction and repulsion) between the agents, not physical interactions. Most closely related to our work are methods such as [10, 27, 45]. These methods model crowd turbulence or physical interactions among panicking agents by adding explicit physical force or by increasing repulsive forces. These methods are capable of reproducing some important emergent crowd phenomena, but do not account for the anticipation needed to efficiently avoid upcoming collisions with other agents and obstacles.

Force-based methods can also suffer from stability issues in dense scenarios, which require careful tuning and small time steps in order to remain stable [4, 18]. Our method provides stable anticipatory motion for agents while incorporating agent responses to forces. It can be easily combined with other velocity-based approaches.

In terms of large, dense crowd simulation, continuum-based methods such as [12, 39] or hybrid method coupling continuum-based method and velocity-based method [25] can be effective solutions. However, these methods do not model physical interactions between the agents or obstacles. Moreover, it is hard to extend these methods to model individually varying behaviors or high-level social behaviors.

Limitations We use a physically inspired approach to simulate the interactions between a high number of agents and the obstacles. However, it is only an approximation and may not be physically accurate. Secondly, we assume that agents are constrained to move along a 2D plane, and we use the projected positions of 3D dynamic objects to compute the interactions. Third, like other agent-based simulation methods, we use a rather simple approximation for each agent (a 2D disc). This means that we cannot accurately simulate physical interactions with human-like articulated models and 3D objects.

7 Conclusions and future work

We have proposed a novel method to combine physics-based interactions with anticipatory collision-avoidance techniques that use velocity-based formulation. Our method can generate many emergent behaviors, physically based collision responses, and propagation of forces to the agent’s nearby neighbors. In combination with the Bullet Physics library, we were able to simulate complex interactions between agents and dynamic obstacles in the environment. We also showed that our approach can be extended to model more complex behaviors involving a decision-making process. In addition, we simulated real-world examples of massive crowds such as in the Tawaf ritual. Our method was able to generate many emergent behaviors compared with real-world behaviors.

As future work, we would like to further explore our method by comparing the results with real-world crowd behaviors and performing more validation. Moreover, in many scenarios, the external forces could change an agent behavior. For example, applying intentional forces such as pushing, kicking can slow down an agent. Such a phenomena could be well incorporated in our approach given studies about how such forces can limit human behavior (e.g., from biomechanics). Furthermore, we need better techniques to collect data about real-world crowds in dense settings and use them to validate the simulation algorithms. We would also like to extend our model to agents moving in 3D space or multi-layer frameworks, and to consider using more complex shapes, or even articulated body models, to represent agents, as this would allow for more accurate force computation. Finally, we would like to use more accurate physically based modeling algorithms to generate appropriate behaviors.