Emotion Contagion Model for Dynamical Crowd Path Planning

2.1. Crowd Simulation

Article

Emotion Contagion Model for Dynamical Crowd Path Planning

Yunpeng Wu ¹, Xiangming Huang ¹, Zhen Tian ¹, Xiaoqiang Yan ^1,*, and Hui Yu ^2,*

¹ School of Computer and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China

² cSCAN, University of Glasgow, G12 8QB, United Kingdom

* Correspondence: iexqyan@zzu.edu.cn; hui.yu@glasgow.ac.uk

Received: 17 December 2023

Accepted: 23 April 2024

Published: 24 September 2024

Abstract: Crowd path planning aims to find the optimal path between the source and destination for multiple agents in crowd scenes. The advent of parallel theory and digital twin technologies provides a novel platform for simulating crowd path planning, which has become increasingly popular in various applications, such as pedestrian evacuation, intelligent transportation, and civil planning. The widely used strategy for crowd path planning emphasizes the objective factors, such as user-specific guidance, shortest path and crowd density. However, this strategy ignores the subjective emotion of agents, which can have significant impact on the diverse path choices of each agent. To tackle this challenge, we present a novel Emotion Contagion Model (ECM) to dynamically conduct path planning in crowded environments by incorporating the emotion of each agent. The proposed method provides a solution to the long-standing high-level affective issue for virtual agents during path search. Firstly, to bridge the gap between emotion states and path choices, the emotion preference is defined based on personality traits of multiple agents. Secondly, an emotion contagion algorithm is proposed to recognize the collective patterns of these agents, which can reveal the dynamical variation of emotion preference under crowded complex environments. Finally, to solve the emotion-to-path mapping, we propose a leastexpected-time objective function to find the optimal path choice for each agent according to the navigation graph in the given scenario. Experimental results on various scenarios, including the subway station, railway station square, fire evacuation and indoor environment, verify the effectiveness of the ECM compared with the state-of-the-art methods.

1. Introduction

Given multiple agents and their corresponding environments, crowd path planning is a task to generate an optimal or suboptimal path for these agents, such as pedestrian, robots and vehicles, from their initial source to the destination. Crowd path planning requires to simultaneously characterize the global behavior of multiple agents and the local behavior of individual agent, which is a key issue in various crowd scenarios, such as pedestrian evacuation [1], self-driving [2] and drone formation control [3]. Specifically, for pedestrian evacuation, reasonably planning an evacuation path can reduce the evacuation time as well as the property and life loss once an disaster occurs in densely populated areas; For self-driving, path planning is a core technology to improve the safety and avoid crowd congestion in dynamic and complex road networks; For drone formation control, it is important to make sure that some unmanned aerial vehicles move to certain targets so that their positions resemble the specific formations or patterns. Recently, crowd path planning has received considerable attention and achieved some promising results in the domains of artificial intelligence [4−7] and pedestrian dynamics with the development of the parallel theory and digital twin technologies [8−11].

Some studies on crowd path planning resorted local collision avoidance to navigate agents to their destination. The seminal work by Reynolds [12] employed efficient rules that could create visually plausible flocking behavior. Follow that work, numerous extensions were proposed to model the crowd motion with local collision avoidance, such as the social force model (SFM) [13, 14], reciprocal velocity obstacles (RVO) [15], optimal reciprocal collision avoidance (ORCA) [16], holonomic aspect [17], hybrid long-range view [18] and dynamic group behavior [19]. Although these methods have achieved promising results, they are restricted to the pre-defined target settings, which leads to the lack of adaptivity. In addition, the aforementioned models only rely on local collision avoidance to search and optimize candidate paths, which always results in unnatural behavior or "getting stuck" in crowded scenes with complex structure.

Some other methods dedicated to the global path planning under crowded environments [20, 21]. For instance, Tobias et al. [22] proposed an approach with the strategy of the quickest path planning. Wouter et al. [23] described how crowd density can be used to guide the characters through a crowded environment. However, these works addressed the global navigation only based on the objective factors such as user-specific guidance, shortest path and crowd density, while ignoring the impact of the emotion states of human-like agents [24]. In fact, agents with different emotion states will lead to diverse choices of path planning. For instance, an individual with aggressive emotion will anticipate overcrowded regions and navigate hurriedly around them, while the one with patient emotion will stick to the current path choice and follow the behavior of nearby agents. The above two situations exactly correspond to the realistic phenomenon that “faster-is-slower” and “path-following”, respectively. Therefore, the emotion states are important issues to accurately model the crowd behavior to generate realistic and plausible motion. Based on this view, some works [14], [25, 26] had directly incorporated personality trait models into crowd path planning. However, these works have the following two disadvantages: 1) only present the mapping between emotion states and parameters of local-level motion; 2) ignore the emotion contagion which exists widely in realistic phenomena.

In summary, a well-defined model for crowd path planning should: 1) achieve the dynamical path planning under complex environments in realistic and plausible manner; 2) emerge the diverse path preference for massive agents with different emotion states; 3) consider the emotion contagion which exists widely in real-world scenarios; and 4) able to be easily applied and generalized to the existing local collision avoidance algorithms.

To meet these criteria, a novel Emotion Contagion Model (ECM) is proposed in this paper, which can achieve the dynamical path planning by incorporating the different emotion states of multiple agents in crowded scenes. The pipeline is shown in Figure 1. Firstly, the emotion preference is defined to describe the path choices under different emotion states based on the OCEAN (openness, conscientiousness, extroversion, agreeableness, neuroticism) personality trait model [27, 28]. Then, an emotion contagion algorithm is proposed under the view that agents in a group will have more interactions, which can fully characterize the impact of contagious information, selective perception and dampening factors. Finally, a least-expected-time objective function is proposed to search an optimal path from the directed navigation graph. Experiments show that the proposed model can achieve the realistic simulation on diverse scenarios with a large-scale crowd. Compared to the previous works on simulation results and quantitative analysis, our method is more effective and efficient. The robustness is further validated by combining different local collision avoidance algorithms. The main contributions can be concluded as follows:

Figure 1. The pipeline of the dynamical crowd path planning with emotion contagion model.

• A novel ECM is proposed to find out the optimal path choice dynamically for multiple agents in crowded environments efficiently and effectively.
• The emotion preference is defined to bridge the gap between personality traits and path choices.
• An emotion contagion algorithm is proposed on the basis of the pattern recognition of group behaviors.
• Based on the emotion preference, a least-expected-time objective function is proposed to decide the path choice of each agent dynamically under complex environments.

2. Related Work

Crowd simulation has been extensively applied in various fields including robots, traffic engineering and social sciences. Most crowd simulators handle this problem in two steps: local collision avoidance and global path planning.

Local Collision Avoidance Since the seminal work [12] provided rule-based methods to keep individuals away from each other when getting too close, local collision avoidance has been proposed in different aspects such as force-based [13, 14], [29], cellular automata [30, 31], and velocity-based [15, 16]. Recently, many extensions and optimizations have been proposed [32]. For instance, Guy et al. [33, 34] presented new local collision avoidance algorithms for real-time crowd simulations. Karamouzas et al. [35] presented a novel approach to simulating the walking behavior with the pattern of small groups. Lemercier et al. [36] aimed at providing the perception rules for the interaction of individuals and environments. However, these works have not taken full consideration of the global path planning, which results in unnatural behavior or “getting stuck” in crowded scenes with complex structure.

Global Path Planning The evolutionary algorithms provide the insights for multi-agent path planning optimization problems. These algorithms usually aim at finding the optimal path according to the shortest distance or least time [37−39]. However, for an effective crowd simulation system, it’s crucial to navigate the agents in a human-like manner and emerge the real phenomenon such as “fast is slower” and “path following”. It’s difficult to reveal these phenomena with the shortest distance or least time path planning. Some literature about global path planning has been proposed in crowed environments [20], [40]. These frameworks adopted the heuristically search algorithm as the solution of global path planning, which has the similar limitations to generate realistic and plausible crowd motion. For instance, Sachin et al. [21] proposed an advanced method based on navigation fields. Geraerts et al. [41] proposed a path planing algorithm with the principle of the shortest distance. Van et al. [23] integrated density information into the objective function to navigate characters to detour around congestion, which, to a large extent, improves the reality of simulations. However, the impact of the personality traits on the diversity of path planning was ignored by those works.

2.2. Personality Traits Integrated Crowd Modeling

The modeling of affective computing attempts to develop and validate computational models of human emotion mechanisms, which has attracted extensive attention from interdisciplinary subjects, such as psychology and computer science [42]. As one of the most popular emotion models, the OCEAN personality traits [27, 28] can be regarded as orthogonal dimensions of the personality space. In OCEAN, each factor is composed of several traits, which can have positive and negative factors. In this study, we follow the personality descriptor presented in [28], where an agent's personality \( \pi \) is a five-dimensional vector and its dimension is represented by a personality factor \( \psi_i \). The Gaussian distribution function \( {N} \) is employed to present the distribution of the personality factors in a group of individuals:

\[ \begin{array}{l} \pi =\left \langle \psi_O,\psi_C,\psi_E,\psi_A,\psi_N \right \rangle,\\ \psi_i={N}\left (\mu_i,\sigma_i^2 \right ),\forall i\in \left \{ O,C,E,A,N \right \} \\ \mu\in\left[ 0,1 \right], \sigma\in \left[ -0.1,0.1 \right] \end{array} \] (1)

Several studies integrated the emotion or personality models into modeling the crowd behaviors [26], [42], [43], [44]. For instance, Helbing et al. [13, 14], [45] simulated panic crowd evacuation by using panic parameters to adjust movement direction. Guy et al. [25] employed PEN (psychoticism, extroversion, neuroticism) to simulate the diversity of the crowd. Durupinar et al. [28] mapped personality traits to the set of crowd behaviors. Further studies incorporated psychological models into the local interactions among agents [46, 47]. Lv et al. [48] proposed an emotional contagion-aware deep reinforcement learning model for antagonistic crowd simulations. Xu et al. [49] proposed an emotion-based crowd simulation model for integrating physical strength consumption. However, these works mainly focus on mining the relationships between psychological models and agents' local interactions in specific scenarios, and this is not adaptive to the crowd simulations under complex scenarios. Mao et al. [50] proposed a unified framework to simulate the emergency evacuations in virtual environments. Liu et al. [51] proposed a recurrent emotional contagion (REC) method for crowd evacuation of the cyber-physical society. Xu et al. [52] simulated pedestrian movement in a region with a periodic boundary condition to study the dynamics of emotional contagion in dense crowds. Note that these methods put more emphasis on how the emotion contagion affects the motion features of agents, and the global navigation module finds the optimal path planning only with the objective factors.

3. Emotion Contagion Model

The emotion preference is first proposed based on the OCEAN personality traits. According to patterns of group behaviors recognized by the collective clustering, the emotion contagion algorithm is then presented to update the emotion preference dynamically.

3.1. Personality Traits-based Emotion Preference

The task of modeling the global path planning for agents within a crowd involves several complex decisions. As a result, different agents will approach the same destination in different manners. While both biological and developmental variations have significant effects on agents’ overall behaviors, we put more emphasis on catching the portion of such variations considering the differences in personality traits. The OCEAN personality trait is suitable to model different patterns of human mental traits. However, it is difficult to make clear about the relationship between the diverse trait factors and the different path choices of agents. To address this problem, we creatively propose the emotion preference to generate plausible variations of the path choices based on the OCEAN personality traits.

Agents within a crowd always emerge the dynamic path planning in complex environments. For example, agents with aggressive emotion will anticipate overcrowded regions and navigate hurriedly around them, while the ones with patient emotion will stick to the current choice of path and follow the behavior of neighbors. From the above observations, we can conclude that agents are always making the path decisions in the dynamical balance between faster velocity and shorter distance. Therefore, the proposed emotion preference includes the distance preference \( P_d \) and velocity preference \( P_v \), which indicate the degree of preferring to the faster path or shorter path. To solve the emotion preferences, the OCEAN personality trait is introduced as the emotion descriptor following the previous work [28]. We further conclude the relationship between trait-descriptive adjectives of OCEAN personality traits and emotion preferences. As a result, the emotion preferences are defined as follows.

The distance preference \( P_d \) represents that agents prefer to walk along the shortest path to their destination. The agents having simple, aggressive and vigorless trait-descriptive adjectives prefer to the path with shorter distance. Corresponding to personality traits, the distance preference is proportional to agreeableness, and is inversely proportional to the openness and extroversion. Thus, \( P_d \) is formulated as

\[ \begin{array}{*{20}{l}} &P_d=f(\psi_O)+f(\psi_E)+f(\psi_A)\\ &f(\psi_O)=\left\{\begin{matrix} 1-\psi_O &0\leqslant \psi_O<0.5 \\ 0 & otherwise \end{matrix}\right.\\ &f(\psi_E)=\left\{\begin{matrix} 1-\psi_E &0\leqslant \psi_E<0.5 \\ 0 & otherwise \end{matrix}\right.\\ &f(\psi_A)=\left\{\begin{matrix} 2\psi_A-1 &\psi_A\geqslant 0.5 \\ 0 & otherwise \end{matrix}\right.\\ &where \; P_d\propto A,P_d\propto^{-1}O, E \end{array} \] (2)

The velocity preference \( P_v \) represents that agents prefer to walking along the fastest path to their destination. The agents having changeable and fearful traits-descriptive adjectives prefer to the path with faster velocity. Corresponding to personality traits, the velocity preference is proportional to extroversion and is inversely proportional to conscientiousness. Therefore, the formulation of \( P_v \) is also given as

\[ \begin{array}{*{20}{l}} &P_v=f(\psi_C)+f(\psi_E)+f(\psi_N)\\ &f(\psi_C)=\left\{\begin{matrix} 1-\psi_C &0\leqslant \psi_C<0.5 \\ 0 & otherwise \end{matrix}\right.\\ &f(\psi_E)=\left\{\begin{matrix} \psi_E &\psi_E\geqslant 0.5 \\ 0 & otherwise \end{matrix}\right.\\ &f(\psi_N)=\left\{\begin{matrix} 2\psi_N-1 &\psi_N\geqslant 0.5 \\ 0 & otherwise \end{matrix}\right.\\ &where \; P_v\propto E, N, P_v\propto^{-1}C \end{array} \] (3)

The distance preference \( P_d \) and the velocity preference \( P_v \) are derived from the complex dimensions of the personality trait space, and reveal the relation between the personality traits and preference of path choices. Different values of \( P_d \) and \( P_v \) represent different weights between the path under the balance of distance and velocity. As shown in Table 1, agents have larger distance preferences if their personality factors is simple, aggressive, and fragile (corresponding to OCEAN factors: O\( - \), E\( - \), A\( + \)), and agents have larger velocity preferences if their personality factors are variable, energetic, and functional (corresponding to OCEAN factors: C\( - \), E\( + \), N\( + \)). If an agent has a large distance preference, its velocity preference is usually smaller, and vice versa. The final distance preference and velocity preference will dynamically determine the later procedure of path planning.

Table 1 Traits-descriptive adjectives of emotion preferences

Emotion preference	Personality factor	OCEAN factor
distance	Simple, aggressive, vigorless.	O\( - \),E\( - \),A\( + \)
velocity	Changeable, energetic, fearful.	C\( - \),E\( + \),N\( + \)

As a conclusion, the proposed emotion preferences can describe the complex personality traits using two parameters directly related to the crowd path planning. Additionally, we use different colors to represent diverse emotion preferences to get better visual and simulated effects as shown in Figure 2. The normalization is introduced for visualizing the emotion preferences in Eq. (4). Note that the normalization processing is just utilized for the visualization of diverse emotion preferences.

\[ \begin{array}{l} P^{vis}_d = P_d / (P_d + P_v) \\ P^{vis}_v = 1 - P^{vis}_d \end{array} \] (4)

Figure 2. The visualization of the diverse emotion preferences. Different colors indicate diverse emotion preferences mapping from the corresponding personality traits.

3.2. Emotion Contagion Based on Group Behaviors

Emotion contagion plays an important role in the crowd simulation under complex environments. Prior research and observations in sociology and behavioral psychology have suggested that real-world crowds are composed of groups [53, 54]. The group is a meso-level concept and is composed of two or more agents that share similar goals, over a short or long period of time, and exhibit collective movements or behaviors. Actually, an agent will largely refer to the ones sharing the similar motion in the same group. Therefore, recognizing such groups and considering the collective decisions are significant for modeling the interactions among agents, i.e., emotion contagion.

3.2.1. Recognizing Group Behaviors with Collective Clustering

There are two key challenges for the task of discovering group behaviors: (1) the density distributions of the crowded agents are always non-uniform and the shapes of the groups are arbitrary; and (2) the efficiency of collective groups detection is crucial for the real-time crowd simulation. To address these problems, we propose a collective clustering algorithm based on the density of crowded agents to discover the arbitrarily shaped clusters, \( i.e. \), collective groups [55, 56]. Firstly, we present the definition of the collective density as follows.

Given a crowd \( C \) including \( N \) agents, where \( C = \{C_{i}|i=1..N\} \), we treat the spatial position \( {\boldsymbol{p}}_i=(p^x_i, p^y_i) \) and velocity \( {\boldsymbol{vel}}_i=(vel^x_i, vel^y_i) \) as the motion features of one agent \( C_i \). The similarity of two agents \( C_i \) and \( C_j \) is calculated as follows:

\[ \begin{array}{c} d_{xy}(i,j) = \left\|{\boldsymbol{p}}_i - {\boldsymbol{p}}_j\right\|\\ d_{ori}(i,j) = \left|\arccos{({\boldsymbol{vel}}_i)}- \arccos{({\boldsymbol{vel}}_j)}\right| \end{array} \] (5)

where \( d_{xy}(i,j) \) and \( d_{ori}(i,j) \) are the similarity of the two agents \( C_i \) and \( C_j \) in terms of spatial position and orientation, respectively. Then, the collective relationship between agents can be defined as follows.

Definition 1 (Collective relationship). For a crowd \( C \), its collective relationship matrix \( W \) is defined as

\[ W(i,j)=\left\{ \begin{aligned} 1&,\; d_{xy}(i,j) \leq cut_{xy} * \theta(i,j)\; or\; \lambda(i,j)=1\\ 0&,\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; otherwise \end{aligned} \right. \] (6)

where

\[ \theta(i,j)=\left\{ \begin{aligned} e^{-(d_{ori}(i,j)/cut_{ori})^2}\; \; \; ,&\; d_{ori}(i,j) \geq cut_{ori}\\ 1 + e^{-(d_{ori}(i,j)/cut_{ori})^2},&\; d_{ori}(i,j) < cut_{ori} \end{aligned} \right. \] (7)

\[ \lambda(i,j)=\left\{ \begin{aligned} 1,& \; agents\; C_i\; and\; C_j\; share\; the\; same\; goal\\ 0,& \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; otherwise \end{aligned} \right. \] (8)

In Eq.(6), \( W(i,j)=1 \) indicates that agents \( C_i,C_j \) are collective neighbors, which considers two aspects: 1) agents have the similar motion; and 2) agents share the same goal. \( \theta(\cdot) \) is an amplification function to dynamically modify the distance cut-off \( cut_{xy} \) according to the orientation cut-off \( cut_{ori} \). \( \lambda(\cdot) \) denotes whether agents share the same goal. The parameters are given empirically, \( cut_{xy} = 50, cut_{ori} = \pi/3 \). Based on the collective relationship, we further define the collective density.

Definition 2 (Collective density). The collective density for the agent \( C_i \) is

\[ \rho_i = \sum\limits_j W(i,j) \] (9)

A key issue of clustering is to determine the cluster centers for groups. Intuitively, the cluster centers of groups are characterized by the following two factors: 1) the collective density of the center is always higher than their neighbor ones; and 2) there is always a large distance and orientation variation between a center and the agents with higher density than this center. Based on this, we intend to propose a collective clustering algorithm that can determine the cluster centers for groups.

To discover the cluster centers, we define the nearest collective neighbor with higher density as follows:

\[ neigh_i = \left\{ \begin{aligned} j &, \; \; \; \; \; \; \; \exists argmin_{j}(d_{xy}(i,j)), \\ &\; \; \; \; s.t.\; \rho_j > \rho_i, W(i,j)=1\\ -1&, \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; otherwise \end{aligned} \right. \] (10)

Algorithm 1 Collective Clustering Algorithm
Input: The number of agents \( N \), the similarity \( d_{xy}(i,j) \), \( d_{ori}(i,j) \), and the collective releationship \( W(i,j) \).
Output: The cluster result \( cluster \).
01: \( \forall i \), calculate the density \( \rho_i \)
02: Intialize the cluster center with \( cluster_{argmax_j(\rho(j))}=j \), and \( cluster_i = -1 \) otherwise
03: For i = 1 TO \( N \)
04:　\( \; \; \; \; \; \)Solve \( cluster_i \) according to Eq.11
Return: the cluster assignment vector \( cluster \)

Next, we present the process of cluster assignment according to Eq.(10). Firstly, the agent with the highest collective density is treated as the initial cluster center, i.e., \( \max_i(\rho_i) \), and \( cluster_i = i \). Then, the remaining agents are sorted in descending order of \( \rho \). For agent \( C_i \) and its \( neigh_i\neq -1 \), it will be allocated to a group with cluster center \( C_{neigh_i} \). Otherwise, the agent \( C_i \) will be treated as a new cluster center. According to this cluster assignment strategy, the centers of a crowd can be determined automatically. The assignment vector \( cluster \) is denoted as

\[ cluster_i = \left\{ \begin{aligned} cluster_{neigh_i},&\; \; \; \; \; \; \; neigh_i \neq -1\\ i,\; \; \; \; \; \; \; \; &\; \; \; \; \; \; \; \; \; \; otherwise \end{aligned} \right. \] (11)

The collective clustering algorithm can efficiently generate the behavior of groups within agents having local consistency or sharing the same goal. Figure 3 shows the colored groups during the simulation of an indoor scene.

Figure 3. The colored groups during the simulation of an indoor scene. Note that only the colors here is utilized to identify the different groups and the others represent the visualization of emotion preferences.

3.2.2. Emotion Contagion Algorithm

The contagion of emotion preference should consider the following aspects: 1) the agent-to-agent contagious information of emotion preference is susceptible to the nearer agents in the same group; 2) the agents have the selective perception for the contagious information; and 3) the update of emotion preference is related to the dampening factor because agents always keep the inherent personality traits. To address these problems, the emotion contagion algorithm is proposed, as shown in Figure 4.

Figure 4. The overview of the emotion contagion algorithm.

Algorithm 2 Emotion Contagion Algorithm
Input: Collective groups \( cluster \), initial emotion preference \( P_d^0, P_v^0 \).
Output: The values of \( P_d^k, P_v^k \) at the \( kth \) update.
01: For agents \( C_i,C_j \) within the same group and the contagious sources \( Src \)
02:　\( \; \; \; \; \; \)Solve contagious information according to Eq.12
03:　\( \; \; \; \; \; \)Solve selective perception according to Eq.13
04:　\( \; \; \; \; \; \)Solve dampening factor according to Eq.14
05:　\( \; \; \; \; \; \)Update emotion preference according to Eq.15
06: Normalize \( P_d^k, P_v^k \) according to Eq.16
Return: the updated \( P_d^k, P_v^k \)

The emotion contagion has three important components, including the contagious information, selective perception and dampening factor. The definitions of components are given as follows.

Definition 3. Contagious Information Agents are susceptible to the other agents in the same group. The contagious information between agents is affected by the distance between agents and the difference between emotion preferences. Additionally, agents may be affected by the extra contagious sources, \( e.g. \) the fire disaster. Thus, the contagious information consists of the information from agents to agents and the information from contagious sources to agents. For agents \( C_i \)\( C_j \) in the same group and the contagious source \( Src_m \), \( \triangle P_d^k(i) \) and \( \triangle P_v^k(i) \) denote the contagious information from both agents and sources at the \( kth \) update,

\[ \begin{array}{l} \triangle P_d^k(i) = \displaystyle\sum\limits_j{e^{((P_d^{k-1}(j) - P_d^{k-1}(i))/d_{xy}(i,j))}}\\ \quad\quad\quad\quad + \displaystyle\sum\limits_m{e^{(P_d^{k-1}(i)/d_{xy}(i,Src_m))}}\\ \triangle P_v^k(i) = \displaystyle\sum\limits_j{e^{((P_v^{k-1}(j) - P_v^{k-1}(i))/d_{xy}(i,j))}} \\ \quad \quad \quad\quad + \displaystyle\sum\limits_m{e^{(P_v^{k-1}(i)/d_{xy}(i,Src_m))}} \end{array} \] (12)

where \( d_{xy}(i,j) \) is the distance between agents \( C_i \) and \( C_j \). \( d_{xy}(i,Src_m)) \) is the distance between \( C_i \) and source \( Src_m \).

Definition 4. Selective Perception. Agents always exhibit the selective perception for lots of contagious information coming from the other agents and contagious sources. However, agents under different environments will perform diverse degrees of perception for the distance preference \( P_d \) and velocity preference \( P_v \). Thus, we define the weight of selective perception \( \omega_d \) and \( \omega_v \) for \( P_d \) and \( P_v \) as follows:

\[ \begin{array}{l} \omega_d(i) = e^{-0.05*dist_{goal}(i)} \\ \omega_v(i) = e^{-2.0*vel(i)} \end{array} \] (13)

Figure 5 illustrates the two curves of \( \omega_d \) and \( \omega_v \). The value of \( \omega_d \) will increase rapidly when the distance from destination \( dist_{goal} \) is lower (less than 100). It indicates that the agent prefers to focus on the distance preference when an agent is close to the destination. The value of \( \omega_v \) will increase rapidly when the velocity \( vel \) is lower (less than 2). It indicates that the agent has a rather low velocity and is more desired to approach the desired maximum velocity.

Figure 5. The curves of the weights of selective perception \( \omega_d \) and \( \omega_v \), respectively.

Definition 5. Dampening Factor. The dampening factor is introduced to control the undesirable change of emotion preferences. As a result, agents will preserve the inherent personality traits during the emotion contagion, which is in line with the objective fact that agents will not easily change their nature. For example, an aggression agent will keep a certain degree of impatience even the one is among calm agents. The initial emotion preferences \( P_d^0 \) and \( P_v^0 \) are adopted as the inherent personality traits. Let \( \zeta_d \) and \( \zeta_d \) denote the dampening factors for two emotion preferences

\[ \begin{array}{l} \zeta_d = P_d^0(i) * 0.1\\ \zeta_v = P_v^0(i) * 0.1\\ \end{array} \] (14)

Finally, the emotion preferences at the \( kth \) update are formulated as

\[ \begin{array}{l} P_d^k(i) = P_d^{k-1}(i) + \overline{\triangle P_d^k(i)}*\omega_d(i) + \zeta_d \\ P_v^k(i) = P_v^{k-1}(i) + \overline{\triangle P_v^k(i)}*\omega_v(i) + \zeta_v \\ \end{array} \] (15)

As same as Eq. 4, the normalization is also introduced for the visualization:

\[ \begin{array}{l} P^{vis}_d(i) = P_d^k(i) / (P_d^k(i) + P_v^k(i)) \\ P^{vis}_v(i) = 1 - P^{vis}_d(i) \end{array} \] (16)

4. Dynamical Crowd Path Planning

4.1. Environment Initialization

Given a scenario, the simulated environment is initialized with the directed navigation graph to extract the available paths for all local areas. A bitmap file is adopted as the input, in which different RGB values indicate the walkable regions or obstacles. In the bitmap, the local area surrounded by exits or walls is regarded as the vertex \( V \), and the exit is denoted by the edge \( E \). Then, we can get a connected graph \( G=(V,E) \) for the whole environment. The BFS (Breadth-First Search) is utilized only once to get the shortest path from current vertex \( v_i \) to the destination \( v_0 \). For each vertex \( v_k \), the shortest path is denoted as \( Path(v_k) = \{v_k,\cdots,v_l,\cdots,v_0\} \), and the gradient \( grad(v_k) \) of \( v_k \) is defined as the length of \( Path(v_k) \). Based on the gradients for all vertices, we construct the directed navigation graph \( G_D=(V,E_D) \), where the directed edge \( e_{k-l}=\langle v_k,v_l \rangle\; s.t.\; grad(v_k)\geqslant grad(v_l) \). As a result, the directed edges can provide the available paths for agents in any local area, as shown in Figure 6.

Figure 6. The modeling process from the simulated environment to the directed navigation graph.

4.2. Emotion-to-Path Mapping

An agent in a local area \( v \) can choose the reasonable destination dynamically according to three aspects: 1) the available paths in its located area; 2) its current emotion preferences including the velocity preference and distance preference; and 3) the objective factors such as the density for each path and the distance from the destination. For an agent \( C_i \) located in area \( v_k \), \( e_{k-l} \) denotes one of the available paths. Meanwhile, denote \( den(e_{k-l}) \) and \( dist_{exit}(e_{k-l}) \) as the density of the exit on \( e_{k-l} \) and the distance from the agent's position to the exit. An objective function is proposed with the least-expected-time strategy.

\[ e^{opt}_i = argmin_{e_{k-l}}\left(\frac{dist_{exit}(e_{k-l})}{vel_0^i*e^{(-(den(e_{k-l})*(P_v + 1)/(P_d + 1))^2)}}\right) \] (17)

where \( e^{opt}_i \) is the optimal path for agent \( C_i \), and \( vel_0^i \) denotes the desired velocity for agents. In Eq.(17), the object function represents the expected time for the agent to arrive at the destination, where the item \( e^{(*)} \) is the adjustment factor for the desired velocity \( vel_0^i \). The larger \( den(e_{k-l}) \) will lead the \( vel_0^i \) to get smaller, \( i.e. \), the crowded path will require more time to arrive at the destination. Additionally, the preferences \( P_v \) and \( P_d \) here are utilized to adjust the impact of the density on the desired velocity. A larger \( P_d \) or lower \( P_v \) will make the item \( e^{(*)} \) more access to \( 1 \), then the impact of the density on the desired velocity is smaller. As a result, the agents with larger \( P_d \), \( i.e. \) the patient ones, will stick to the path which is even crowded. On the contrary, the agents with smaller \( P_d \), \( i.e. \) the aggressive ones, will be more sensitive to the crowded path, and prefer to navigate hurriedly around them.

The proposed least-expected-time strategy based objective function can dynamically choose the optimal path from multiple feasible paths based on their subjective emotional preferences and objective environmental factors. As shown in Eq.(17), objective environmental factors are highly correlated with the distance between individuals and exits, as well as the density of people near the target exit. In particular, the distance between individuals and exits, and the density of people near the target exit are dynamically changing. In addition, individuals' emotional preferences are also dynamically changing during their journey. To fully take the dynamic changes mentioned above into account, we design Eq.(17) to capture the dynamic changes of multiple factors.

5. Simulation Results on Diverse Scenarios

We highlight the performance of our algorithm on different scenarios. The simulation results are recorded and visualized in real-time using the Horde3D graphics engine [57] on a personal computer with a 4GHz Intel Core I7 processor, NVIDIA GeForce 980Ti graphics card, and 32 GB of RAM.

The Indoor Scenario. As shown in Figure 7, this scenario comprises of 600 agents in a room with two exits. Figure 7(a)-(c) are the three stages of the simulation, and Figure 7(d)-(h) are the close-up views corresponding to of the five black rectangles in the above figures. There are three salient features in the simulation: 1) the relaxed agents (with colors close to blue) prefer to a short path, and the aggressive agents (with colors close to red) prefer to a faster path. In Figure 7(d), among the agents in the top left corner, the blue ones prefer the above exit with congestion, however, the red ones prefer the below exit even far away. Moreover, Figure 7(f) is another proof of this effect; 2) under the congestion environment, more and more agents will be aggressive. Figure 7(e) and Figure 7(g) are two screenshots with the same place in the same perspective. At the beginning, lots of agents are in relaxed or patient states, however, agents become aggressive in the congested region; and 3) agents approaching to the desired velocity will become patient. As shown in Figure 7(d) and Figure 7(h), some agents in Figure 7(d) are with aggressive emotion, where the ones in Figure 7(H) are with alleviated emotion. From the above three aspects, it can be concluded that the proposed ECM based crowd path planning can reveal diverse choices of the agents’ behavior.

Figure 7. The demonstration of crowd path planning in an indoor scenario. (a)-(c) are the overhead views of simulation in three stages. (d)-(h) are the close-up views from (a)-(c).

Boarding the Subway. Figure 8 shows the simulation that people are boarding the subway. At first, lots of the passengers gather around the head of the train. The congestion makes agents' emotion becomes more and more aggressive during the boarding, even for the ones with relaxed or patient emotion initially. Then, some agents move towards the other entrances of the train to get on the train quickly.

Figure 8. The demonstration that the crowds are boarding a train in the subway station.

Evacuation outside the Railway Station. Figure 9 shows an outdoor scenario of crowd evacuation outside the railway station. During the evacuation, a few agents still keep relaxed emotion, and more and more agents are becoming aggressive. At first, the exits at the left and right sides have a relatively close distance. As a result, lots of agents choose either the left or the right exit as the destination. Since the congestion happens at the left and right exits, some aggressive agents begin to choose the middle exit with relatively far distance as the new destination. This experiment employs 1500 agents which demonstrates that the proposed ECM is available for the large-scale crowd path planning.

The Evacuation under Fire Disaster. As shown in Figure 10, a special scenario of the evacuation under fire disaster is shown, which can verify that the ECM can be applied widely to emergent behaviour simulations. When the fire occurs, agents near the fire origin turn to have aggressive or panic emotion rapidly. The panic spreads along the crowd within a group, and more and more agents are contagious with the panic state. Furthermore, this scenario demonstrates that ECM can simulate the crowd path planning in a quite complex environment.

Figure 9. The large-scale crowd evacuation outside the railway station.

Figure 10. The large-scale crowd evacuation under fire disaster.

6. Analysis and Comparison

6.1. The Initialization of Emotion Preference

The emotion preference is a key component of the proposed ECM, which can generate the path preferences based on OCEAN personality traits. As shown in Figure 11, the emotion preferences are initialized with different distributions in OCEAN personality traits, including extremely aggressive, aggressive, normal situation, patient, and extremely patient. We can see that: 1) \( \psi_E \) is the major factor to decide the overall distribution. The expectation of the normal distribution \( \psi_E \) is less than \( 0.5 \) in Figure 11(a)(b), and is bigger than \( 0.5 \) in Figure 11(d)(e). In the normal situation, the expectation of \( \psi_E \) equals \( 0.5 \); 2) the others are the auxiliary factors which can make a small adjustment. \( \psi_O \) and \( \psi_A \) have great relation to the distance preference, and \( \psi_C \) and \( \psi_N \) correspond to the velocity preference; and (3) the concentration of different emotion preferences is adjusted by the variance of each normal distribution. It can be concluded that the emotion preferences can be initialized in a flexible manner for different simulation tasks.

Figure 11. The visualization that emotion preferences are initialized with diverse distributions of OCEAN personality traits \( \psi_i, i\in\{O,C,E,A,N\} \) (600 agents). (a) Extremely aggressive. (b) Aggressive. (c) Normal situation. (d) Patient. (e) Extremely patient.

6.2. Crowd Path Planning Under Different Emotion Preferences

The experiments of crowd path planning with different emotion preferences are given to verify the effectiveness of the proposed ECM. Figure 12(a)-(c) are the extreme situations and Figure 12(d) is a normal scenario. In Fig-ure 12(a), all agents are initialized with the distance preference \( P^{vis}_d = 1.0 \) and velocity preference \( P^{vis}_v = 0.0 \). During the simulation, most agents choose the exit with shortest distance as the destination. In Figure 12(b), when the agents are initialized with \( P^{vis}_d = 0.5 \) and \( P^{vis}_v = 0.5 \), more agents begin to avoid the congestion and choose the exit far away. In Figure 12(c), lots of agents are impatient to the congestion and they begin walking towards the furthest exit. In the last scenario with a normal emotion distribution, lots of aggressive agents prefer to avoid the congestion and most of patient agents still prefer the exit with the shortest distance. We can conclude that the ECM based crowd path planning can reveal the diverse choices of agents in a plausible manner: 1) lots of impatient agents prefer the path with a fast velocity, but not all of them just choose the fast path arbitrarily; 2) most patient agents prefer the path with the shortest distance, but a few of them still can avoid the congestion smartly; and 3) for the relaxed agents, they are neutral to choose the path according to the dynamic environments.

Figure 12. The demonstration of crowd path planning with different emotion preferences.

6.3. Combination with local collision avoidance

In crowd simulation, local collision avoidance and global path planning are two modules for achieving crowd motion control in complex scenes. Specifically, local collision avoidance is a module responsible for local-level motion, which can achieve crowd movement control from the starting point to the target point without collision between agents, obstacles, and other agents in simple scenes. However, the local collision avoidance can’t handle the situations that the path from the starting point and target point is relatively complex. Therefore, crowd path planning is necessary for the crowd simulation in a complex environment. That is to say, local collision avoidance provides agent's motion control within a local range, while global path planning provides overall guidance for a crowd. Therefore, if we want to achieve crowd simulations in complex scenes, we need to consider both local collision avoidance and global path planning.

Our model can be easily integrated into other multi-agent simulation systems by combining diverse local collision avoidance algorithms, such as Social Force Model (SFM) [13], Reciprocal Velocity Obstacles (RVO) [15], and Optimal Reciprocal Collision Avoidance (ORCA) [16]. We outline the above methods as follows:

Social Force Model The SFM for pedestrian dynamics [13] is commonly used for collision avoidance in multi-agent systems. In this scheme, collision avoidance is achieved by means of forces acting on each agent. There is a repulse force that prevents the agent from colliding with other agents and obstacles. In addition, there is also an attractive force that guides the agent to the goal. In our experiment, the key parameters are configured as follows: the desired speed is \( v^0 = 2.0 \), the collision avoidance radius is \( r = 2.0 \) and the mass of agent is \( m = 80 \). In addition, the parameters for the computation of interaction forces are employed with default values.

Reciprocal Velocity Obstacles & Optimal Reciprocal Collision Avoidance. The RVO [15] is a geometric framework for local collision avoidance. It takes as input the preferred velocity of the agent and returns an optimal collision-free velocity that minimizes the chosen penalty metric. The ORCA [16] is the latest version of the RVO. Here, the key parameters are given as \( maxNeighors = 10 \), \( maxSpeed = 3.0 \), \( neighborDist = 15 \), and \( radius = 2.0 \).

Figure 13 shows the results that the ECM is integrated into the SFM, RVO and ORCA under complex environments. The agents have the similar navigation path with the ECM, and the difference of local interaction is caused by different collision avoidance methods. Moreover, Figure 14 illustrates the performance of ECM with SFM and ORCA under different scales of crowds, and the indicator Frame Per Second (FPS) is employed. We can see that the proposed ECM can simulate the crowd with 500 agents in real-time (about 30fps). Since no extra strategy of rendering acceleration is employed, the FPS will drop down to 3 when the number of agents is larger than 1500.

Figure 13. The demonstration of crowd evacuation simulation by combining Emotion Contagion Model with current local collision-avoidance methods, such as SFM, RVO, ORCA. (a) SFM; (b) RVO; (c) ORCA.

Figure 14. The curves between crowd scale and frame rate(FPS) by combining the Emotion Contagion Model with SFM and ORCA, respectively.

6.4. Comparison with existing works

Figure 15 shows the comparison among the shortest distance based path planning (SD) [20, 22], density awareness based path planning (DA)[23] and emotion contagion model based path planning (ECM). Figure 15(a)-(c) are the simulation results of the above approaches. The simulation results show that: (1) the SD method navigates all agents to move straight to the nearest doors rigidly, which is not consistent with the reality; (2) the DA method can simulate that agents can pick another way when congestion happens, however, the only consideration of density makes the agents change the path frequently; and (3) the proposed ECM can simulate the dynamical and diverse choices of different agents. Some agents choose the shortest path even under congestion, and some choose the path with less congestion, though a further distance. The last column of Figure 15 illustrates the trace to further demonstrate the change of path choices. The trace of ECM is more consistent with the reality.

Figure 15. The comparison on simulation result and trajectory.

Quantitative comparison is also introduced in Table 2. The FPS and Total Evacuation Time (TET) are adopted as the quantitative indicators. The FPS of the proposed ECM is a little higher than that of SD and DA because of the introduction of emotion contagion. From the aspect of TET, our ECM achieves the best performance. The reasons are (1) SD always chooses the shortest path where the congestion leads to more time to finish the evacuation; (2) and DA can avoid the congestion areas by awareness of the density. However, the different density may lead the agents change the path frequently.

Table 2 The quantitative comparison of three algorithms

	FPS(frame/s)				TET(s)
number	200	400	600		200	400	600
SD	87.3	60.3	27.2		13.9	50.7	109.1
DA	81.2	56.9	25.6		13.4	48.8	106.7
ECM	77.2	54.8	24.4		12.9	45.8	94.5

6.5. Comparison with the Real-World Scene

In Figure 16, we simulate crowd behaviour according to the real-world videos recorded inside the railway station. In these videos, passengers receive safety check before boarding the train. Figure 16(a) and Figure 16(b) show the two procedures in both overhead view and close-up view, respectively. The first column is the real-world clip, and the other two columns are the different stage of the simulation. Additionally, a detailed example is given in Fig-ure 16(c), some of which stick to the crowded entrance and several ones decide to avoid congested regions. Such an example exists in both the real-world scenarios and simulation results. It can be concluded that the simulation is consistent with the real crowds from the aspect of dynamical path planning.

Figure 16. The simulation from the real scene: security channels in the train station. (a) The overhead view; (b) The close-up view; (c) The detailed demonstration of dynamic path planning existing in both the simulation and real-world scenario.

We design two evaluation metrics, the rate of path changes (\( RPC \)) and average number of path changes (\( ANPC \)), to validate the effectiveness of the proposed model. Firstly, we provide the definitions of \( RPC \) and \( ANPC \) as follows:

RPC refers to the proportion of agents with the path choice changing to the total number of agents in the crowd, which is defined as

\[ RPC = N' / N \] (18)

where N′ is the number of agents that change its path choice in the simulation or real-world videos, and N is the total number of agents in the crowd. From this definition, \( RPC \) can measure the stability of crowd path planning. The closer this indicator is to the real \( RPC \), the better the simulation effect.

ANPC indicates the average number of path changes of each agent in the crowd, which is defined as

\[ ANPC = \sum{Cnt_i} / N \] (19)

where \( Cnt_i \) indicates the path change times of agent \( C_{i} \) in the virtual or real scenarios. In this study, we adopt real videos from a railway station as the benchmark, which are captured from the security gate in railway station.

Specifically, we divide the video into 20 clips (5 minutes for each clip). Table 3 show the average RPC and ANPC on the 20 clips compared with SD and DA baselines. In this experiment, the SD represents the methods employed the shortest-distance as the strategy for path planning, and DA indicates the methods using the density-aware path planning. For the SD, all the average \( RPC \) and \( ANPC \) equal to 0 since the path choice for each agent is fixed to destination with the shortest distance so that the path choice doesn’t change at any time. The DA adopts the dynamical strategy that the path choices will change according to the densities of destinations. However, the single consideration of the density will lead to that the frequent change of path choices, which is not accordance with the real scenarios. The proposed method achieves the dynamical path planning with the balance between the objective factors (density, distance) and subject personality factors, which can achieve better simulation results.

Table 3 The quantitative comparison on the real-world videos

Baselines	Average RPC	Average ANPC
SD	0%	0
DA	47.67%	9.75
Ours	17.84%	1.37
Real-world Videos	13.62%	0.89

6.6. Ablation Study

To further verify the effectiveness of each module in the proposed model, we conduct the experiments for following 3 scenarios: (A) retain the objective function without the emotion preference; (B) retain the proposed emotion preference and objection function without the emotion contagion; and (C) retain all the proposed modules.

From Table 4, we can obtain the following observations. According to (A) and (B), we can observe that the objective function with the factors such as density and distance will lead to higher average values of \( RPC \) and \( ANPC \), which indicates that the optimal path decision based on the density and distance will make the agents change their destination frequently.

Table 4 The ablation study

		Methods
		The Emotion Preference	The Emotion Contagion	The Objective Function	Average RPC	Average ANPC
Simulation Scenarios	(A)			\( \checkmark \)	34.17%	7.56
	(B)	\( \checkmark \)		\( \checkmark \)	21.39%	3.94
	(C)	\( \checkmark \)	\( \checkmark \)	\( \checkmark \)	17.84%	1.37
Real-world Videos		-	-	-	13.62%	0.89

According to (B) and (C), we can observe that the lack of emotion contagion degrades the simulation performance. This is mainly because that some agents with aggressive emotion preferences will change their destination frequently even if they are among the patient agents.

From (A) and (C), we observe that the simulation effect of our method is closer to the real situation by introducing the emotional preference and contagion. This further validates the effectiveness of our proposed objective function with emotional factors.

7. Conclusions

We present a novel ECM in this paper, which can simulate the crowd path planning in dynamical environments. Based on the OCEAN personality traits, the emotion preference is defined to discover the relationship between emotion states and path choices. Furthermore, we propose an emotion contagion algorithm based on recognizing group behaviors to reveal the emotional variations of agents under complex environments. A least-expected-time objective function is introduced to solve the optimal emotion-to-path mapping. We illustrate the performance on several simulation scenarios, such as the indoor environment, subway station, railway station square, and fire evacuation. Our method can be easily combined with most current local collision-avoidance methods. Compared to the previous works using simulations, the results and quantitative analysis show that our method is more effective and efficient.

Author Contributions: Yunpeng Wu: conceptualization, methodology, software, writing. Xiangming Huang: software, investigation, validation. Zhen Tian: investigation, supervision. Xiaoqiang Yan: conceptualization, supervision. Hui Yu: writing and editing, supervision.

Funding: This work is supported by the National Natural Science Foundation of China (Grant No. 62002330, 62301423), China Postdoctoral Science Foundation under grant No. 2020M682357 and in part by the Henan Science and Technology Research under grant No. 32102211027, 222102210012.

Data Availability Statement: The data are available from the corresponding author on reasonable request.

Conflicts of Interest: The authors declare no conflicts of interest.