Emergent Crowd Grouping via Heuristic Self-Organization

Abstract.

Modeling crowds has many important applications in games and computer animation. Inspired by the emergent following effect in real-life crowd scenarios, in this work, we develop a method for implicitly grouping moving agents. We achieve this by analyzing local information around each agent and rotating its preferred velocity accordingly. Each agent could automatically form an implicit group with its neighboring agents that have similar directions. In contrast to an explicit group, there are no strict boundaries for an implicit group. If an agent’s direction deviates from its group as a result of positional changes, it will autonomously exit the group or join another implicitly formed neighboring group. This implicit grouping is autonomously emergent among agents rather than deliberately controlled by the algorithm. The proposed method is compared with many crowd simulation models, and the experimental results indicate that our approach achieves the lowest congestion levels in some classic scenarios. In addition, we demonstrate that adjusting the preferred velocity of agents can actually reduce the dissimilarity between their actual velocity and the original preferred velocity. Our work is available online.

Figure 1. A classic scenario where 100 agents are distributed evenly on a circle, and their destination is to navigate to the antipodal position on the circle. In contrast to the severe trajectory oscillations produced by the Dutra method (dutra2017gradient, ) at agent meeting area and the congestion with slow movement generated by the implicit crowd (karamouzas2017implicit, ) in the same locations, our method achieved organized motion, realizing congestion-free scenarios. Due to the symmetry in the motion of all agents, they self-organize into the same group, moving in the “same direction” (clockwise rotation).

1. Introduction

Large multi-agent systems, such as the real-time simulation of human crowds, are important tasks in games (colas2022interaction, ; wolinski2014parameter, ), animation (gustafson2016mure, ; zhang2023orcanet, ) and visual effects (kanyuk2015headstrong, ; van2021algorithms, ; hu2021heterogeneous, ). In the realm of crowd simulation studies, the classification typically involves two categories: flow-based, wherein the entire crowd is conceptualized as a substance with fluid-like characteristics, and agent-based, where each individual of the crowd is represented as an intelligent agent. The focus of this work is specifically on microscopic approaches, delving into the intricacies of addressing the crowd simulation problem at the individual scale. This work focuses on agent-based approaches that generate crowd dynamics from the micro perspective of individuals.

In agent-based methods, the primary focus is to model local interactions among agents which specifies how the movement of each agent is impacted by the presence of neighboring agents and obstacles. Subsequently, macroscopic collective behaviors emerge through the microscopic interactions among individuals. Amidst various modeling considerations, a significant portion (van2020generalized, ; van2011reciprocal, ; lee2018crowd, ) is dedicated to addressing collision avoidance. Typically, a local navigation algorithm needs to calculate a velocity for an agent at a given moment, enabling it to navigate its path safely around other nearby agents and obstacles without collisions. In many modern techniques for procedural animation of intelligent systems and crowd dynamics, this local navigation algorithm could be optimizing a cost or energy function (karamouzas2017implicit, ), performing low-dimensional linear programming under the constraint of velocity obstacles (fiorini1998motion, ; van2008reciprocal, ) and leaning to interact with agents(charalambous2023greil, ; talukdar2023learning, ; lee2018crowd, ; kwiatkowski2023reward, )

In addition to the necessary collision avoidance characteristics, human crowds usually display a rich variety of self-organized behaviors that support efficient motion under everyday conditions (moussaid2011simple, ). One of the best-known examples is the spontaneous formation of uni-directional lanes in bi-directional pedestrian flows (helbing1995social, ). This intricate ability of crowds to self-organize has not only practical implications for everyday scenarios but also holds promise for optimizing crowd flow in controlled environments.

Group dynamics modeling is an effective crowd organizing method that reduces internal conflicts among crowds by organizing individuals into groups (gorrini2014empirical, ; li2017grouping, ; nicolas2023social, ). Existing crowd simulation methods for modeling group behaviors often require explicit grouping or the establishment of heterogeneous leaders. Previous research on modeling group behavior has predominantly focused on cohesive motion or spatial structures within the crowd. Fundamental algorithms involve clustering agents into predefined groups, with each group maintaining a constant size (static grouping) (bruneau2015going, ; tang2023crowd, ). However, these methods fall short in capturing the evolving sizes of groups, dividing large crowds into subgroups, or merging smaller groups into larger ones (he2016dynamic, ). Therefore, how to produce group dynamics via self-organization need further exploration.

In response to this limitation, this work proposes a method to facilitate the spontaneous emergence of group dynamics in crowds. The primary objective of this paper is to facilitate the emergence of self-organizing phenomena by adjusting the preferred velocity of agents, thereby improving the efficiency of crowd movement. In terms of collision avoidance, Optimal Reciprocal Collision Avoidance (ORCA) (van2011reciprocal, ) is employed as the underlying model, where the preferred velocity is a crucial variable compared to other collision avoidance models. Our approach enables agents with similar forward directions to implicitly organize into groups. As agents move, changes in their positions result in individuals diverging automatically from the group when their target directions deviate. The formation, merging, splitting, and redistribution of these implicit groups are spontaneously driven by interactions among agents. This paper achieves the emergence of automatic implicit grouping behavior in crowds through a bottom-up approach, potentially offering a novel perspective in the realm of crowd simulation. The main contributions of this paper are as follows:

1. Focusing on promoting the emergence of group dynamics, this paper proposes a method that allows agents to make slight adjustments to their preferred velocity in the direction based on the surrounding information. This enables the crowd to autonomously generate implicit groups, which can reduce internal conflicts among intelligent agents experiencing significant disparities in movement directions.

2. The proposed method is compared with many agent-based crowd models, including the state-of-the-art method, implicit crowd (karamouzas2017implicit, ), a crowd simulation model that utilizes implicit integration to produce highly smooth trajectories while maintaining strong robustness. Experimental results indicate that the proposed method performs better than compared algorithms in terms of crowd congestion level and the alignment between preferred velocity and actual velocity.

3. We encapsulated our method into a Python package, accessible via the Pip package management tool. This facilitates easy integration and usage for researchers seeking to apply the developed approach in their work.

2. Background

2.1. Related Work

Social Force model (helbing1995social, ) is one of the earliest proposed models for simulating crowd dynamics. Each agent in this model is influenced by surrounding agents and obstacles. This influence is defined as virtual physical forces, and, therefore, the movement of agents can be calculated based on principles of mechanics. The concept of Velocity Obstacle (VO) space, denoting the velocities of an agent that would result in a collision between the agent and an obstacle or another agent at some future time, was introduced in (fiorini1998motion, ). Therefore, collision avoidance can be transformed into a linear programming problem, considering velocity obstacles with respect to other agents or obstacles. Numerous subsequent studies, building upon the concept of VO, have been proposed. Rather than opting for a new velocity outside the velocity obstacle of the other agent in VO method, Reciprocal Velocity Obstacle (RVO) (van2008reciprocal, ) selects a different velocity by averaging its current velocity with a velocity positioned outside the velocity obstacle of the other agent. Compared to the original VO method, RVO can generate safer and smoother trajectories. The formulation of RVO can only guarantee collision-free in certain specific conditions and Optimal Reciprocal Collision Avoidance (ORCA) was proposed to provide a sufficient condition for multiple agents to avoid collision (van2011reciprocal, ). Some studies (karamouzas2009predictive, ; karamouzas2014universal, ) also use the notion of time to collision to achieve collision avoidance and describe human interactions. Vision information was also useful in agent-based crowd simulation and was explored in many studies (ondvrej2010synthetic, ; hughes2015davis, ; dutra2017gradient, ). In these methods, each agent movement can be calculated by evaluating the future collisions based on the time to collision, time to closet approach or distance of closest approach of each pixel. Karamouzas et al. (karamouzas2017implicit, ) presented an optimization integrator named "Implicit Crowds," tailored to harmonize with nonlinear, anticipatory forces, and physics-based animation in multi-agent systems. Through the incorporation of dissipation functions, this approach demonstrates insensitivity to parameters and achieves the generation of remarkably smooth and collision-free trajectories for crowd movement. In recent years, with the continuous increase in computational power, some researchers tried to use machine learning (alahi2016social, ; zhong2022data, ; hu2021heterogeneous, ; kwiatkowski2023reward, ) to discover crowd behavior patterns and employ reinforcement learning (lee2018crowd, ; talukdar2023learning, ; charalambous2023greil, ) to explore interaction strategies within crowds. The above algorithms effectively model crowds and are sufficient to reproduce many known crowd phenomena. However, limited attention has been given to how the emergence of self-organizing phenomena in crowds can be facilitated through the local interactions of agents.

There is also some research on group dynamics. Bruneau et al.(bruneau2015going, ) studied collision avoidance among predefined and fixed pedestrian groups. Tang et al. (tang2023crowd, ) group individuals via machine learning methods. Dynamic grouping (he2016dynamic, ) was also explored to introduce a process for maintaining and updating groupings within the crowd after agents update their positions and velocities. Despite these efforts, many real-world scenarios involve crowds exhibiting spontaneous cooperative behaviors, such as the emergence of channeling effects, without explicit grouping and criteria for grouping. Further investigation is required into the emergence of crowd grouping.

2.2. Agent-based Crowd Simulation

In the setting of agent-based crowd simulation, the task involves navigating $N$ agents to their individual destinations while avoiding collisions with other agents or obstacles. These agents traverse a two dimensional plane and are commonly depicted as discs with radii $r$. The simulation includes a loop with frames of a fixed duration $\Delta t$. At the simulation time step $t$, the state of agents can be characterized by three $1\times N$ matrixes:

(1) $$\mathbf{X}^{t}=\left[\mathbf{x}_{1}^{t},\mathbf{x}_{2}^{t},\cdots,\mathbf{x}_{i}^{t},\cdots,\mathbf{x}_{N}^{t}\right]$$

(2) $$\mathbf{V}^{t}=\left[\mathbf{v}_{1}^{t},\mathbf{v}_{2}^{t},\cdots,\mathbf{v}_{i}^{t},\cdots,\mathbf{v}_{N}^{t}\right]$$

(3) $$\mathbf{P}^{t}=\left[\mathbf{p}_{1}^{t},\mathbf{p}_{2}^{t},\cdots,\mathbf{p}_{i}^{t},\cdots,\mathbf{p}_{N}^{t}\right]$$

where each $\mathbf{x}_{i}^{t}$,$\mathbf{v}_{i}^{t}$,$\mathbf{p}_{i}^{t}$ represent the position, velocity, and preferred velocity of agent $A_{i}$ at time step $t$, respectively.

The preferred velocity signifies the direction in which the agent intends to move forward. In its most basic form, the preferred velocity for each agent is represented as a vector starting from the agent’s current position and pointing towards a local destination. Its magnitude is equal to a user-specified preferred speed $S_{pref}$.

Typically, a global path planner is assumed to operate outside local navigation, calculating a global path for each agent in the scenario. This path can be decomposed into multiple local destinations. Then, at each simulation time step $t$, the preferred velocities $\mathbf{V}^{t}$ for all agents can be determined based on their current positions and local destinations.

To ascertain the state of agents in the subsequent time step $t+1$, local navigation is required to calculate $\mathbf{X}^{t+1}$ and $\mathbf{V}^{t+1}$ for the agents first. Then, $\mathbf{P}^{t+1}$ can be determined based on current positions $\mathbf{X}^{t}$ and the local destinations of agents. Usually, $\mathbf{X}^{t+1}$ can be calculated from $\mathbf{V}^{t+1}$, and $\mathbf{V}^{t+1}$ also can be inferred from $\mathbf{X}^{t+1}$. Thus, local navigation only needs to compute either of these two. For example, in (karamouzas2017implicit, ), the calculation is for $\mathbf{X}^{t+1}$, while in (van2011reciprocal, ; dutra2017gradient, ; van2008reciprocal, ), the calculation is for $\mathbf{V}^{t+1}$.

When the surrounding environment is crowded, the actual velocity $\mathbf{V}^{t+1}$ of agents often deviates from their preferred velocity $\mathbf{V}^{t}$. Agents aspire to advance towards their local goals but are required to adhere to certain local navigation constraints, such as avoiding collisions with other agents, maintaining proximity to a specific agent or group, and other relevant considerations. According to some crowd simulation models, such as (van2008reciprocal, ; karamouzas2014universal, ; karamouzas2017implicit, ), the agent repeatedly makes a local adjustment to step in a certain direction. In this work, for convenience, we use a function to represent this local adjustment/navigation:

(4) $$\mathbf{V}^{t+1}=\mathcal{F}\left(\mathbf{X}^{t},\mathbf{V}^{t},\mathbf{P}^{t}\right).$$

where $\mathcal{F}(\cdot)$ serves as an abstraction for the process of local navigation algorithms (collision avoidance in particular). It take the state of agents as input and output the velocities of all agents of the next time step.

3. Method

3.1. Preferred Velocity Correction

So far, the calculation of preferred velocity is still based on a greedy rule, where each agent wishes to move in the direction that brings it closest to its destination in the shortest distance. This holds true for an individual pedestrian, but in a crowd, individual preferences are often influenced by the collective (le2002crowd, ). In real-life scenarios such as subway stations, airports, etc., the movement preferences of crowds often exhibit a tendency to follow the pedestrians in front, and even create channeling effects (helbing1995social, ) in some scenes. These autonomously emerging crowd phenomena can often enhance the efficiency of crowd movement. The basic idea in this work is to adjust the preferred velocity of each agent based on the surrounding crowd state, trying to create some beneficial crowd dynamics to enhance the efficiency of crowd movement. Therefore, we modify the calculation of $\mathbf{V}^{t}$ as follows:

(5) $$\mathbf{V}^{t+1}=\mathcal{F}\left(\mathbf{X}^{t},\mathbf{V}^{t},\mathbf{G}^{t}\right).$$

where $\mathbf{G}^{t}$ is considered as the new preferred velocities of agents after being influenced by the surrounding crowd. Each $\mathbf{g}^{t}_{i}$ in $\mathbf{G}^{t}$ for each agent $A_{i}$ should be a more promising direction for the agent when the surroundings are crowded, compared with its original preferred velocity $\mathbf{p}_{i}^{t}$. At the same time, $\mathbf{g}^{t}_{i}$ must also possess the functionality of $\mathbf{p}_{i}^{t}$, guiding the agent towards its (local) destination.

How to find a reasonable $\mathbf{G}^{t}$ is the focus of our work. The proposed method in this paper is to make a slight rotation, by an angle $\theta_{i}$, to the original preferred velocity of each agent $A_{i}$ based on its current neighboring agents. Therefore, the relationship between $\mathbf{G}^{t}$ and $\mathbf{P}^{t}$ is as follows.

(6) $$\mathbf{G}^{t}=\mathbf{R}^{t}\circ\mathbf{P}^{t},$$

(7) $$\mathbf{R}^{t}=R\left(\Theta^{t}\right)=\left[R\left(\theta_{1}^{t}\right),R\left(\theta_{2}^{t}\right),\cdots,R\left(\theta_{i}^{t}\right),\cdots,R\left(\theta_{N}^{t}\right)\right],$$

in which $R(\theta_{i})$ donates the rotation matrix corresponding to the angle $\theta_{i}$, $\circ$ represents the Hadamard product (horn2012matrix, ). In this case, the goal of this work is to calculate for $N$ offset angles $\Theta^{t}=[\theta_{1}^{t},\theta_{2}^{t},\cdots,\theta_{N}^{t}]$ at each time step $t$, which can be characterized by (8).

(8) $$\Theta^{t}=\mathcal{G}\left(\mathbf{X}^{t},\mathbf{V}^{t},\mathbf{P}^{t}\right)$$

In the next subsection, a simple and efficient method for producing $\Theta^{t}$ is presented.

3.2. Factors Influencing the Rotation Angle

Most existing crowd simulation models calculate $\mathbf{v}_{i}^{t+1}$ for each agent $A_{i}$ based on several kinds of information, including the current velocity $\mathbf{v}_{i}^{t}$ and position $\mathbf{x}_{i}^{t}$ of $A_{i}$, the agent’s preferred velocity $\mathbf{p}_{i}^{t}$, and the positions and velocities of other agents around $A_{j}$. While these pieces of information primarily serve the purpose of collision avoidance, they also have the potential to offer guidance for optimizing crowd movement efficiency—a facet that has not received adequate attention in prior research. In this section, we examine the potentially viable offset direction for each agent, considering the information mentioned above. By simulating common behavioral patterns observed in real-life crowds, we hope to construct a following effect among individuals, thereby achieving crowd implicit grouping.

3.2.1. View field

In real-world scenarios, the preferences of pedestrians are often influenced only by the states of the crowd in front of them (within their field of view). Therefore, we introduce a term to model this phenomenon. We define a vector $\Phi^{t}$ as the directions of the agents at the current time step $t$:

(9) $$\Phi^{t}=\left[\phi^{t}_{1},\phi^{t}_{2},\cdots,\phi^{t}_{i},\cdots,\phi^{t}_{N}\right].$$

In this work, we do not consider the actual velocity of an agent at time step t as its direction because the actual velocity may result in a very strange direction when avoiding collisions. Instead, we take a compromise between the actual velocity and the preferred velocity as the direction of an agent:

(10) $$\Phi^{t}=\mathbf{V}^{t}+\mathbf{P}^{t}.$$

Whether other agents are in front of agent $A_{i}$ can be inferred using the following formula:

(11) $$T_{0}=H\left(\left(\Phi^{t}\right)^{\top}\otimes\mathbf{1}_{1\times N}\odot\Delta\mathbf{X}^{t}\right),$$

where $H(\cdot)$ is the Heaviside step function (zhang2020feature, ), $\Delta\mathbf{X}^{t}$ is the matrix of relative positions of all agents:

(12) $$\Delta\mathbf{X}^{t}=\mathbf{X}^{t}\otimes\mathbf{1}_{N\times 1}-\left(\mathbf{X}^{t}\right)^{\top}\otimes\mathbf{1}_{1\times N},$$

in which $\otimes$ donates the Kronecker product (henderson1983history, ), $\odot$ donates element-wise dot product, $\mathbf{1}_{n\times m}$ means an all-ones matrix with size of $n\times m$. $T_{0}$ is a matrix of dimensions n-by-m, comprised of ones and zeros. The element in the $i$-th row and $j$-th column signifies whether $A_{j}$ is positioned in front of $A_{i}$, with one indicating yes and zero indicating no. When calculating $\theta^{t}_{i}$, $T_{0}$ can be used as a mask to control which agents’ information needs to be included in the calculation.

3.2.2. The similarity and dissimilarity in directions

The movement of a pedestrian is often influenced by the velocities of the surrounding crowd. The velocities of other pedestrians commonly serve as a foundation for achieving collision avoidance. Simultaneously, the preferred velocity of a pedestrian is also influenced by these velocities. In real-world situations, when a pedestrian encounters a group of individuals walking towards them, there is a tendency to avoid them. Conversely, the pedestrian is inclined to follow a group of people moving in a similar direction as them. Inspired by this phenomenon, this work uses this observation as partial basis to calculate $\Theta^{i}$.

The degree of difference in the direction between an agent $A_{i}$ and another agent $A_{j}$ can be calculated by their inner product $\mathbf{\phi}^{t}_{i}\cdot\mathbf{\phi}^{t}_{j}$. In this work, we assume that agents can only know the actual velocities of other agents at time step t, without knowing their preferred velocities. Therefore, for agent $A_{i}$, we use $\mathbf{\phi}^{t}_{i}\cdot\mathbf{v}^{t}_{j}$ as an indicator of the difference in velocity between $A_{i}$ and $A_{j}$. When $\mathbf{\phi}^{t}_{i}\cdot\mathbf{v}^{t}_{j}$ is positive, the larger the value, the closer the directions of $A_{i}$ and $A_{j}$. When $\mathbf{\phi}^{t}_{i}\cdot\mathbf{v}^{t}_{j}$ is negative, the larger the absolute value, the more conflicting the directions of $A_{i}$ and $A_{j}$. These indicators form a $N\times N$ matrix, which can be calculated by (13).

(13) $$T_{1}=\left(\mathbf{\Phi}^{t}\right)^{\top}\mathbf{V}^{t}.$$

The value of $\mathbf{\phi}^{t}_{i}\cdot\mathbf{v}^{t}_{j}$ can be positive or negative. If it is negative, $A_{i}$ needs to avoid $A_{j}$; if it is positive, $A_{i}$ could follow $A_{j}$. The magnitude of $\theta^{t}_{i}$, which represents the degree of correction to the preferred velocity of $A_{i}$, can partially depend on the absolute value of $\mathbf{\phi}^{t}_{i}\cdot\mathbf{v}^{t}_{j}$.

3.2.3. Detour

The magnitude of the angle between the direction of an agent $A_{i}$ and the relative position of another agent $A_{j}$ with respect to $A_{i}$ can serve as an indicator of the potential obstruction that $A_{j}$ might pose to the movement of $A_{i}$ in future time steps. When there are numerous other agents in the front of an agent, it suggests the possibility of potential congestion ahead (liao2023towards, ). $A_{i}$ can make some detour-like adjustments, i.e., offsetting the preferred velocity. In this work, this indicator is utilized as a component in calculating $\Theta^{t}$.

(14) $$T_{2}=\left(\Phi^{t}\right)^{\top}\otimes\mathbf{1}_{1\times N}\odot\Delta\mathbf{X}^{t}\oslash\sqrt{\Delta\mathbf{X}^{t}\odot\Delta\mathbf{X}^{t}},$$

where $T_{2}$ is a $N\times N$ matrix, $\oslash$ donates Hadamard division (cyganek2013object, ). The element in the $i$-th row and $j$-th column of $T_{2}$ signifies the degree of proximity between the movement direction of $A_{i}$ and the direction of $A_{j}$ relative to $A_{i}$.

3.2.4. Distance

A basic intuition is that distant agents have a reduced impact on oneself. This work uses the reciprocal of the relative distance to describe this influence:

(15) $$T_{3}=\left(\sqrt{\Delta\mathbf{X}^{t}\odot\Delta\mathbf{X}^{t}}\right)^{\circ-1}.$$

The impact on agent $A_{i}$ from other agents positioned at a greater distance should be diminished. This idea has also been widely adopted in many previous studies, such as neighbor region (van2008reciprocal, ). When adjusting the preferred velocity, it is also not necessary to consider all other agents. A new mask $T_{4}$ can be used to achieve this:

(16) $$T_{4}=1-H\left(\sqrt{\Delta\mathbf{X}^{t}\odot\Delta\mathbf{X}^{t}}-L_{m}\right),$$

where $L_{m}$ is the radius of the neighbor region. When the distance between $A_{j}$ and $A_{i}$ is greater than $L_{m}$, $A_{j}$ is not considered to have an impact on the preferred velocity of $A_{i}$.

3.2.5. Rotation direction of preferred velocity

The indicators introduced above can provide a basis for the magnitude of the preferred velocity offset angle, but we need to introduce a new component to control the direction of the preferred velocity offset. This work proposes a method to control the rotation direction of the preferred velocity via cross product. Because the cross product of $\mathbf{x}^{t}_{j}-\mathbf{x}^{t}_{i}$ and $\phi^{t}_{i}$, and the sine of the angle between them have a linear relationship, we can use their cross product to determine whether $A_{j}$ positioned in the left or right half area of $A_{i}$. Therefore, we use $T_{5}$ to control the rotation direction of each preferred velocity:

(17) $$T_{5}=2H\left(\left(\Phi^{t}\right)^{\top}\otimes\mathbf{1}_{1\times N}\star\Delta\mathbf{X}^{t}\right)-1,$$

where $\star$ donates element-wise cross product. $T_{5}$ is a matrix consisting of $1$s and $-1$s. If the value in the $i$-th row and $j$-th column is $1$, it means that $A_{j}$ is on the left side of $A_{i}$; otherwise, on the right side.

3.3. Overall Framework

Based on the analysis in the previous subsection, we have obtained some useful information (i.e., $T_{0}$ to $T_{5}$) for calculating $\Theta^{t}$. This subsection employs a straightforward multiplication approach to organize the potential information outlined earlier. As $T_{5}$ is obtained via the cross-product operation that is associated with the sine function. Its values are distributed around $0$ when the state of crowd is completely random. Therefore, this work establishes the following relationship:

(18) $$\sin\left(\Theta^{t}\right)\underset{\sim}{\varpropto}\mathbf{1}_{1\times N}\overset{5}{\underset{i=0}{\bigcirc}}\left(T_{i}\right)^{\top}.$$

We can finally obtain the calculation formula for $\Theta^{t}$ by normalization and the addition of the coefficient $K$:

(19) $$\Theta^{t}=\sin^{-1}\left(\frac{1}{2}\tanh\left(K\mathbf{1}_{1\times N}\overset{5}{\underset{i=0}{\bigcirc}}\left(T_{i}\right)^{\top}\right)\right),$$

where the term $\frac{1}{2}$ is used to control the deviation of the preferred velocity, ensuring it does not exceed $\frac{\pi}{2}$.

The overall framework of the algorithm is illustrated in Algorithm 1. The simulation initiates with the assignment of initial positions $\mathbf{X}^{0}$ and velocities $\mathbf{V}^{0}$ for the agents. In typical situations, $\mathbf{V}^{0}$ is composed of $N$ zero vectors, indicating that agents are initially stationary. The simulation proceeds through discrete time steps until reaching a predefined maximum time limit $T_{max}$. At each time step, the preferred positions $\mathbf{P}^{t}$ for agents are calculated based on their global paths. Then, the rotation angles $\Theta^{t}$ of $\mathbf{P}^{t}$ are calculated via the proposed method. Accordingly, $\mathbf{P}^{t}$ is rotated and the new preferred velocities $\mathbf{G}^{t}$ of agents can be obtained. The velocities of agents are updated by collision avoidance model $\mathcal{F}(\cdot)$ that considers the current positions $\mathbf{X}^{t}$, velocities $\mathbf{V}^{t}$, and rotated preferred velocities $\mathbf{G}^{t}$. In this work, ORCA (van2011reciprocal, ) is adopted as the foundational collision avoidance model. Given its emphasis on preferred velocity as the objective, it aligns seamlessly with our approach. The positions are updated accordingly, and the current state of the simulation is visualized. This iterative process continues until the maximum time limit is reached.

1 Initial $\mathbf{X}^{0}$ and $\mathbf{V}^{0}$;

2

3$t\leftarrow 0$;

4 while $t<T_{max}$ do

5       Calculate $\mathbf{P}^{t}$ based on the global paths of agents;

6       $\Theta^{t}\leftarrow\sin^{-1}\left(\frac{1}{2}\tanh\left(K\mathbf{1}_{1\times N}\overset{5}{\underset{i=0}{\bigcirc}}\left(T_{i}\right)^{\top}\right)\right)$ ;

7       $\mathbf{G}^{t}\leftarrow R\left(\Theta^{t}\right)\circ\mathbf{P}^{t}$ ;

8       $\mathbf{V}^{t+1}\leftarrow\mathcal{F}\left(\mathbf{X}^{t},\mathbf{V}^{t},\mathbf{G}^{t}\right)$, $\mathbf{X}^{t+1}\leftarrow\mathbf{X}^{t}+\mathbf{V}^{t+1}\Delta t$ ;

9       Visualize$(\mathbf{X}^{t})$,  $t\leftarrow t+1$ ;

10      

11 end while

Algorithm 1 The Proposed Method

4. Implementation

4.1. Setting

This work primarily focuses on the efficiency of crowd movement. Therefore, the evaluation metrics in this paper include the dissimilarity between preferred velocity and actual velocity $M_{1}=\frac{1}{2N}\Delta t\sum_{i}^{N}|\mathbf{v}^{t}_{i}-\mathbf{p}^{t}_{i}|^{2}$ and crowd congestion (liao2023crowd, ) level

(20) $$M_{2}=\frac{1}{N^{2}}\sum_{i\neq j}^{N}\frac{1-\cos(\angle{\mathbf{v}^{t}_{i},\mathbf{v}^{t}_{j}})}{2}e^{-|x^{t}_{i}-x^{t}_{j}|}.$$

We test our method in several classic scenarios, including: Circle (see Figure 1, a classic scenario involves the even distribution of 100 agents on a circle, with their goal being to navigate to the antipodal position on the same circle), AsyCircle (similar to the configuration of Circle scenario, but with a slight perturbation added to the destination of agents, causing their movement to be not entirely symmetrical), 2-Group (see Figure 2(a), two groups, each comprising 20 agents, are positioned on the east and west sides of the scenario in a grid formation, with each agent’s destination mirroring horizontally w.r.t. the scenario center), and 4-Group (see Figure 2(b), four groups, each comprising 25 agents, are arranged in a grid formation in four directions of the scenario, and each agent’s destination is a position symmetric w.r.t. the scenario center).

(a) initial state of 2-Group

(b) initial state of 4-Group

Figure 2. The initial distribution of agents of two scenarios

Our model is compared with following models: SocialForces (helbing1995social, ), RVO (van2008reciprocal, ), PLEdestrians (guy2010pledestrians, ), PowerLaw (karamouzas2014universal, ), Karamouzas (karamouzas2010velocity, ), Moussaid (moussaid2011simple, ), ORCA (van2011reciprocal, ), Dutra (dutra2017gradient, ) and Implicit (karamouzas2017implicit, ). We implemented our method in C++ for the simulation of agents and Python for user interface. The parameters in our work are configured with $\Delta t=0.1,r=0.3,K=0.6,L_{m}=10$.

4.2. Results and Analysis

Figure 3. Curves of $M_{1}$ (the dissimilarity between preferred velocity and actual velocity of agents) over time steps of different crowd simulation models in four scenarios. In each scenario, although our approach exhibits a brief period of significant dissimilarity at the initial stage, it maintains relative stability throughout the subsequent simulation process.

Figure 4. Curves of $M_{2}$ (the crowd congestion level) over time steps of different crowd simulation models in four scenarios. Our method consistently maintains a low level of congestion when agents encounter others (time steps around the middle of the x-axis)

Figure 3 presents the variation of $M_{1}$ over time steps in different scenarios. It can be observed that when agents from different directions converge (time steps around the middle of the x-axis), the actual velocities of agents in most methods deviate significantly from their preferred velocities. Our method achieved a relatively stable alignment between preferred velocity and actual velocity during the most of time of each simulation process. This results indicate that applying beneficial rotations to the agents’ original preferred velocities $\mathbf{P}^{t}$ can actually reduce the dissimilarity between $\mathbf{P}^{t}$ and $\mathbf{V}^{t+1}$. We hope that these results can provide some potential insights for future researchers in related studies.

Figure 4 depicts the variation of congestion levels over time steps for different algorithms in different scenarios. From the figure, it can be observed that our method exhibits relatively low congestion level when agents from different directions start to converge. Surprisingly, in the Circle scenario, due to the highly symmetrical movement of the crowd, all agents self-organize into a single group (refer to Figure 1), resulting in no congestion. Implicit crowd also performed well in most scenarios. However, the Dutra method performed poorly in two circle-based scenarios. Referring to the motion trajectories in Figure 1, it can be observed that this vision-based method exhibits severe oscillations when encountering a large and densely packed number of agents from different directions. SocialForces and PowerLaw are two rule-based methods that, without adding perturbations, exhibit prolonged congestion in symmetric scenarios. The area enclosed by the curve and the x-axis can be approximated as the overall congestion level of the crowd throughout the simulation process. Our method demonstrated the minimum congestion level in each scenario. This indicates that mimicking the following effect of real-life crowd behavior can significantly reduce congestion among individuals.

We also compares three crowd simulation models – ORCA, Implicit, and our method – within the AsyCircle scenario visually (its agents’ initial positions can be referenced from the first subplot in Figure 1). Figure 5 presents the simulation outcomes, highlighting distinctive characteristics of each model. Both ORCA and Implicit exhibit congestion at the convergence area where agents meet in the middle. In contrast, our proposed method showcases a unique behavior, forming loosely structured groups of agents with similar directions prior to their encounters. After agents meet, the original Implicit group disperses, and they reorganize into new formations with similar velocity directions (visible queues of agents in the figure). Notably, in our crowd simulation method, there is a conspicuous absence of significant congestion, emphasizing the efficacy of our approach in mitigating crowd congestion issues. Figure 6 shows illustrates partial trajectories of three agents from different crowd simulation models in a classic three-agent scenario. Agents in our method exhibit stronger proactive avoidance behavior compared to the Implicit and ORCA. This indicates that the pattern in our method, which considers avoiding or taking detours around pedestrians ahead, works.

Figure 5. Agent states for three crowd simulation models in the AsyCircle scenario. Both ORCA and Implicit exhibit congestion at the area where the agents converges in the middle. Our method results in loosely formed groups of agents with similar directions before they encounter each other. Upon meeting, there is no significant congestion observed.

Figure 6. Agent states for three crowd simulation models in classic three-agent scenario. Compared to the close encounters in ORCA, Implicit and our method demonstrate more realistic behaviors by incorporating necessary avoidance maneuvers and detours.

Figure 7 illustrates the computation time of the ORCA, Implicit, and our method for different numbers of agents. From the figure, it can be observed that our algorithm is highly efficient, adding almost negligible computational overhead compared to the ORCA. While Implicit is a global optimization algorithm, its runtime efficiency is comparatively lower.

Figure 7. The computation time of the ORCA, Implicit, and our method for different numbers of agents. Our algorithm is highly efficient, introducing nearly negligible computational overhead to the underlying ORCA.

5. Conclusion

In this paper, we propose an approach that allows crowd grouping to emerge via self-organization, leading to efficient crowd movement. Experimental results demonstrate that our approach significantly reduces crowd congestion and the dissimilarity between agents’ preferred and actual speeds, compared to several other crowd simulation models. This indicates that our original intention to achieve efficient crowd movement via the autonomous emergence of latent behaviors of crowd, such as implicit group formation of agents with similar directions, is feasible.

Our method achieves the emergence of implicit groups, the process of loosely formed groups being disrupted and then reassembled (after unavoidable encounters with groups in severe directional conflict) is highly inefficient. Future research could focus on addressing this issue to achieve more efficient crowd movement. While the components $T_{0}$ to $T_{5}$ of our method are built based on the rationale of real-world scenarios, the final combination of these components, however, is still at a very preliminary stage. Moreover, the combination also introduces an additional hyperparameter, which is not an ideal design. In the future, considering the use of symbolic regression methods can potentially address the mentioned issues.