Keywords

1 Introduction

Today, as we face more and more emergencies, effective evacuation has become much important. Although people try to move faster than normal, the radical competition will slow down the evacuation process in most case. In normal environment, pedestrians have plenty time to figure out the best chooses with least consumption. They will behave some intelligent attributes, such as, they can help each other or maximize the use of resources. However, the intelligence may disappear as the security of pedestrians is threatened by the emergency situations. Due to short time and intense pressure, escape in the limited space will cause fierce competition between evacuees. How to make a good evacuation planning through the study of crowd behavior is still an open question.

Emergency simulation is a good choice, which can be used to design and evaluate evacuation plans, and train relevant personnel to gain valuable experience. It overcomes the shortness of exposing pedestrians in danger in evacuation practice which may not be treated seriously as the real emergency. By using virtual agents to simulate the behavior of pedestrians, many computational model [6, 13, 24] are built to model the autonomous agent that move and interact with each other and the environment. A key novelty of these models is the ability to represent the dynamic decision-making functions, which enable individuals to make realistic behavioral decisions.

Many factors should be considered in emergency evacuation planning, such as signs and information sharing. Safety signs will give effective exit instruction to evacuees. Effective sharing exports information, on the one hand, can help people find the way to export, on the other hand, help ease the pressure of competition and promote the cooperation between each other. For the case of panic, people will follow the general trend, that is, to do what other people do or follow the instruction of signs, which is easy to get stuck at a bottleneck during evacuation especially at the door. Therefore, to study the effect of safety signs and information sharing becomes very important for evacuation planning.

The rest of this article is organized as follows. Section 2 reviews the related work. Section 3 provides an overview of our model. In Sect. 4, the local and global technology is discussed in detail. Section 5 is the dynamic decision-making process include both local behavior motivation and global behavior controlling, where the global controlling is realized through a behavior tree. Experimental Results and Discussions is presented in Sect. 6 and finally, concludes in Sect. 7.

2 Related Work

An extensive studies arise recently dealing with different emergencies [12–14, 21]. [22] presents an agent-based travel demand model system for hurricane evacuation simulation, which is capable of generating comprehensive household activity-travel plans. [18] presents the method of crowd evacuation simulation for bioterrorism in micro-spatial environments using the basic theory of Virtual Geographic Environments (VGE), combined with pathogen diffusion and crowd simulation modeling techniques.

A good simulation model should deal with both the collision avoidance problem and global path planning and navigation. The velocity-based model [2] derived from robotics tries to find a collision-free velocities by solving a geometric optimization problem. A planning framework that satisfied multiple spatial constraints imposed on the path is presented in [11]. [20] presents a prototype of a computer simulation system that uses agent-based model to simulate an emergency environment with crowd evacuation and provides for testing of multiple disaster scenarios at virtually no cost.

The study about evacuation planning [1, 7, 23] and disaster response [5] exists. The instruction study as well as the cooperative work in evacuation is necessary. A tool for guiding a group of people out of a public building when they are faced with dangerous situations that need immediate evacuation is designed in [8]. A study about human responses to the direction information like signs, moving crowd and memorized information when choosing exit routes is proposed [3]. To establish new building design guidelines, [15] aims to enhance safety through improved design of the built environment by investigating issues associated with emergencies and evacuations. Reference [9] use the Asymmetry Information Environment (AIE) to study cooperative works. Incorporating with asymmetric information, agents can make realistic behavioral decisions which help to simulate the dynamic of evacuation inequality.

The control strategy applied to the designed models is important in crowd simulation. Evacuees are modeled as an agent complying with a series of behavior rules and decision-making methods [1]. An adaptive affective social decision-making model is proposed in [16]. Different decision-making methods directly influence the intelligence and reality of simulation results. BDI is a model to represent both the human decision-making and decision-planning functions in a unified framework [10, 17].

3 Overview

In the process of simulation, local collision avoidance as well as global path planning and navigation are two indispensable technologies. Collision avoidance consider the interaction between agents and obstacles and the classical method is the Optimal Reciprocal Collision Avoidance (ORCA) method [19]. Path planning and navigation are used to provide goal-seeking capability and to model individual intention. Global path planning is used to reach the destination with the preferred velocity which is managed by collision avoidance to keep the reality of simulation.

Dynamic decision-making includes two parts, which are corresponding to the technologies discussed above. A pedestrian’s moving motivation is decided through the local interaction, which is not only for the sake of avoiding collision but also important to its local navigation. Its local behavior motivation will generate the behavior driven, which decides a pedestrian’s current preferred velocity. The influence of safety signs and information sharing are important in this process. The decision tree will determine the agents’ decision in current situation, which will generate their willingness of moving towards the destination. It will decide the global path it chooses to move.

4 Local and Global Technology

In local navigation, collision avoidance technique is used to deal with interactions between agents and obstacles, which can effectively avoid upcoming collision. In this paper, the collision avoidance problem is solved by applying the Optimal Reciprocal Collision Avoidance (ORCA) method presented in [19]. As shown in (1).

$$\begin{aligned} ORCA^{\tau }_{A|B}=\{\mathbf {v}|(\mathbf {v}-(\mathbf {v}^{opt}_A+\frac{1}{2}\mathbf {u})) \cdot \mathbf {n}\ge 0\} \end{aligned}$$
(1)

Global path planning mainly solves the problem about how to reach the destinations with the preferred velocity. Based on the reality of collision avoidance between the moving agents, \(\mathbf {v}^{CA}\) which means the velocity meets the requirement of collision avoidance is generated by filtering \(\mathbf {v}^{pre}\) with the process of ORCA in (2). The detail of solving \(\mathbf {v}^{pre}\) is in Sect. 5.1

$$\begin{aligned} { \mathbf {P}}_{tar} = { \mathbf {P}}_{cur} + \mathbf {v}^{CA}*{\varDelta }T \end{aligned}$$
(2)

\({\mathbf {P}}_{tar}\) denotes the target position and \({\mathbf {P}}_{cur}\) denotes the current position.

5 Dynamic Decision-Making

Dynamic decision-making includes two parts, which are corresponding to the technologies discussed above. A pedestrian’s moving motivation is decided through the local interaction, which is not only for the sake of avoiding collision but also important to its local navigation. The agent’s willingness of moving towards the destination is generated through a decision tree which decides the global path it chooses.

5.1 Local Behavior Motivation

A pedestrian’s moving motivation is its preferred velocity, which control its current moving direction and speed [4]. As shown in (3).

$$\begin{aligned} \mathbf {v}^p_i=v^p_i\cdot \mathbf {e}^p_i \end{aligned}$$
(3)

The Speed of Preferred Velocity: The magnitude of the preferred velocity \(v^p_i\) is calculated in two kinds of pedestrians. The acquainted pedestrians who know the way to exit will move at maximum speed \(v_{max}\), while the novice pedestrians who always follow others will move at average speed of its neighbors. Although this strategy can simplify calculation to a certain extent, it is not very reasonable, because of the ignorance of many factors.

Adjust the Speed: For the member in the acquainted group, they have different level of willingness to help others. If they help the others, they couldn’t move at the maximum speed \(v_{max}\). As a result, their preferred speed will be reduced correspondingly. In emergency, people move or try to move considerably faster than normal. The moving speed not only depends on its physical condition but also on psychological effect aroused by the hazards. However, members in the novice group will be more panic than those in the acquainted group.

Inspired by these situations, we unify the speed of the acquainted group and the novice group as follows (4):

$$\begin{aligned} v^p_i =\beta _i \cdot v_{max}+ (1-\beta _i)\cdot v_{mean} \end{aligned}$$
(4)

where \(\beta _i\), shown in (5) is used to control the weight of \(v_{max}\) and \(v_{mean}\).

$$\begin{aligned} \beta _i ={\exp {-\dfrac{A+\rho ^{will}_i}{B-\rho ^{priori}_i}}} \end{aligned}$$
(5)

We use parameters \(\rho ^{priori}_i\) and \(\rho ^{will}_i\) to denote its priori knowledge, and its willingness to help others respectively. Constants A and B are used to adjust the contributions of \(\rho ^{will}_i\) and \(\rho ^{priori}_i\).

The Direction of Preferred Velocity: The moving direction \(\mathbf {e}^p_i\) is influenced by different degree of extrinsic and intrinsic factors [4]. Illustrated in (6).

$$\begin{aligned} \mathbf {e}^p_i=\alpha _i \cdot \mathbf {e}^E_i+ (1-\alpha _i) \cdot \mathbf {e}^I_i \end{aligned}$$
(6)

where \(\alpha _i \in [0,1]\) is the combination weight.

The extrinsic factor \(\mathbf {e}^E_i\) is solved through a well constructed neighborhood \({\varPsi }_i\). As shown in (7). It satisfies three conditions: (1) The neighbor being chosen should be within its maximum visual range \(p_{ij} < R\); (2) The neighbor should not be blocked by the barrier, when condition one is met; (3) To handle the condition when the number of neighbors \(N'\) is larger or smaller than N. If \(N'\) is larger than N, then the N nearest neighbors are chosen. If \(N'\) is smaller than N, then the \(N'\) neighbors’ information plus \(N-N'\) pairs of (0,0) are used to construct \({\varPsi }_{i}\).

$$\begin{aligned} \quad \quad \quad \quad {\varPsi }_{i}=\{(\mathbf {p}_{i1},\mathbf {v}_{i1}),...,(\mathbf {p}_{ik},\mathbf {v}_{ik}),...,(\mathbf {p}_{iN},\mathbf {v}_{iN})\} \end{aligned}$$
(7)

where \(\mathbf {p}_{ik}\) denotes the position of \(k_{th}\) neighbor of pedestrian i, and \(\mathbf {v}_{ik}\) denotes the neighbor’s velocity.

The intrinsic factor \(\mathbf {e}^I_i\) is obtained through the exit choosing process, which follow the principle of the closer the exit the higher chance to be selected. The probability \(P_k\) of choosing exit k can be computed by (8).

$$\begin{aligned} P_k = \frac{L_k^{-1}}{\sum _{i=1}^{M}L_i^{-1}} \end{aligned}$$
(8)

Adjust the Direction: The method discussed above considers only one group of crowd, when signs exit or not to calculate the extrinsic factor \(\mathbf {e}^E_i\). When two groups of pedestrians moving in opposite directions, pedestrian at the boundary of the two groups will only be influenced by one side, as shown in Fig. 1.

Fig. 1.
figure 1

(a) Two groups of pedestrians; (b) The pedestrian in red between the two groups chooses only one group to follow (Color figure online).

Full size image

The neighbors are found simply according to the topology structure, that is not very reasonable. In addition, if it is influenced by two sides, neither groups will it follow. Then a strange phenomenon will appear, pedestrians at the boundary move in the direction perpendicular to the two directions of the two groups.

To avoid this situation, we first classify the pedestrians according to the target destination. In our common sense, a pedestrian will not change it destination easily, unless it find a better one or the previous one is impossible. If a pedestrian is at the boundary of N groups, only one direction of the groups will it choose to follow. \(D_{c_k}\) denotes the destination of most pedestrians in the \(k_{th}\) crowd within the maximum visual range of pedestrian i, \(D_i\) is the current destination of pedestrian i. The moving direction of a crowd is represent by \(\mathbf {e}^{c_k} \), and \(\mathbf {e}^s\) is the safety signs instructive direction inside the maximum visual range.

  1. 1.

    When there is no sign instruction, \(D_i\) is equal to \(D_{c_k}\), pedestrian i will choose its neighborhood in the \(k_{th}\) crowd and calculate \(\mathbf {e}^E_i\).

  2. 2.

    If \(D_i\) is equal to \(D_{c_k}\) and condition \(\mathbf {e}^{c_k} \cdot \mathbf {e}^s>0\) is met, which means the crowd is moving in the direction consistent with signs. In this situation, the pedestrian will follow the crowd naturally.

  3. 3.

    If safety signs exit and no crowd meeting the condition \(\mathbf {e}^{c_k} \cdot \mathbf {e}^s>0\), it will do the same operation like the no sign exits.

  4. 4.

    If the crowd destination which is different with it however consistent with signs, it will have a trend to change its direction or insist on the original direction. Details will be discussed in Sect. 5.2. If it changed its direction, then its neighborhood will be reconstructed.

5.2 Decision Tree

Decision tree plays an important role in choosing between several paths to destination. It generates the agent’s current global goal, based on the private intention of the agent itself as well as the current situation. The agent executing the conditional judgment throughout the decision tree according to the information set collected from the environment. Meanwhile, a behavior set is introduced to tell the reaction of agents when an incident is triggered.

Behaviors illustrate in behavior tree between two kinds of agents, the novice agents and the acquainted agents. Novice agents who are unfamiliar with the scenario or environment make the decision mainly depend on the neighborhood. Acquainted agents obtain the knowledge of how to escape from the emergency and decide mainly by the prior knowledge but rarely focus on what the neighbor agents would behave.

Agents with the same condition may behave differently, which is showed in Figs. 2(b) and 3(b). The notes in Figs. 2 and 3 are illustrated as follows:

  • EXIT1: The exit in right bottom corner of the maze.

  • EXIT2: The exit in left top corner of the maze.

  • IMPASSE: The regions where cannot be got through.

  • START: The current location of the crowd, represented by red dot.

  • UNKNOWN REGION: The area where the agent is unfamiliar with.

In Figs. 2(a) and 3(a), the blue dots are T-junctions and the green ones are right-angle intersections. The black dots in right corner indicate the crowd. There are three probable paths to reach EXIT1 and EXIT2, \( Path_{1} = \{START\rightarrow i\rightarrow j\rightarrow k\rightarrow h\rightarrow EXIT1\}\), \(Path_{2}=\{START\rightarrow a\rightarrow b\rightarrow c\rightarrow d\rightarrow e\rightarrow f\rightarrow g\rightarrow h\rightarrow EXIT1\}\), \( Path_{3}=\{START\rightarrow i\rightarrow j\rightarrow k\rightarrow l\rightarrow m\rightarrow n\rightarrow o\rightarrow p\rightarrow EXIT2\}\).

In Figs. 2(b) and 3(b) the blue dots are the branch node whose child nodes are the conditions represented by several green dots and actions represented by several orange dots. The information set consists of different conditions and the behavior set is composed of a sequence of actions.

Fig. 2.
figure 2

(a) The maze scenario when the emergency happens and path from k to h is crowded; (b) Decision tree for novice agents (Color figure online).

Full size image

Take novice agent \(A_n\) as an example, the information set {Emergency, Discover Crowd, Discover Sign}, the behavior set {Escape, Follow the Crowd, Follow the Sign}. The decision tree of the novice agent in Fig. 2(b) illustrates that when \(A_n\) arrived at k in Fig. 2(a) two behaviors will be carried out according to the conditions. If the condition of “Discover Crowd” is satisfied, \(A_n\) will take action of “Follow the Crowd” which means that the agent follows the crowd at the corner near EXIT1 under the impact of crowds’ moving trend. However, if the condition of “Discover Sign” is satisfied, \(A_n\) will take action of “Follow the Sign”, this branch stands for the fact that the novice agent move along the direction as the yellow arrows tell and the neighborhood has far less effect on the agent’s destination. With the satisfaction of these two decision branches, the novice agent chooses one of the two decisions with a comprehensive comparison.

Fig. 3.
figure 3

(a) The maze scenario when the emergency happens and path from h to EXIT1 is crowded; (b) Decision tree for acquainted agents (Color figure online).

Full size image

For acquainted agent \(A_a\), the behavior tree is shown in Fig. 3(b) with the information set {Emergency, Close to EXIT1, Close to EXIT2, EXIT1 Blocked, Crowded, Endure Time Unreached} and the behavior set {Escape, Run in EXIT1 Direction, Run in EXIT2 Direction, Give up EXIT1, Insist on EXIT1}. When \(A_a\) realizes the “Emergency” condition, \(A_a\) tries to escape from the maze. Because \(A_a\) notices the fact that it is closer to EXIT1, it will take the action of “Run in EXIT1 Direction” and move forward. When it arrives at position k in Fig. 3(a) it realised that the condition of “EXIT1 Blocked” and “Crowded” are satisfied. It faces the choices of “Give up EXIT1”, “Run in EXIT2 Direction”, or “Insist on EXIT1” by getting through the crowd until “Endure Time Unreached” is satisfied. The acquainted agent with strong confidence makes the decisions not on the neighborhood but on its own desires. It chooses one branch of the decision tree and makes the decision according to the probability about each branch.

6 Experimental Results and Discussions

In this section, we conducted several experiments with our dynamic-decision model. Agents will be influenced by so many factors, like safety signs, the crowds motion trend and the safety exit information.

Fig. 4.
figure 4

The influence of crowd size to the escape time.

Full size image

First, we test the escape time of our model with different crowd size in a confined space, when the escape ratio reaches 80 %. Escape ratio is defined as the ratio between the number of pedestrians get out the maze and the crowd size. The result is shown in Fig. 4. The escape time will increase with the increase of crowd size. At the beginning of evacuation, time increases in linear with the crowd size. When the escape ratio is higher, the relation ship of crowd size and escape time is no longer in linear relationship. This is because the influence of congestions, which hinders the escape process.

The second experiment is conducted to test the influence of signs on the evacuation process. We conduct several experiments with 400–500 agents to test the influence of signs to the escape time, when escape ratio reaches 80 %.

Fig. 5.
figure 5

The influence of safety signs to the escape time.

Full size image

As shown in Fig. 5, following the instruction of signs can significantly reduce the escape time. This result is consistent with the common sense that when emergency happens, it is better to actively seek the way to export than randomly wander in the scenario with panic. Effective emergency evacuation signs play an important role in this respect.

The third experiment is conducted to test the influence of crowds motion trend on the agent moving direction. As shown in Fig. 6, a small group of agents in the right side find the crowd in front moving in the left direction. As a result, the condition of “Discover Crowd” is satisfied, they take action of “Follow the Crowd” and the agents follows the crowd under the impact of crowds’ moving trend.

The last experiment is conducted to test the influence of agents’ willingness to share information and help each other. We run the simulation with 400 pedestrians. A group of acquainted agents whose prior knowledge \(\rho ^{priori}\) is high. We change the degree of the willingness of those agents to share information and help those novices.

Fig. 6.
figure 6

(a) Two groups of agents; (b) The small group find the crowds moving trend; (c) Follow the crowd (Color figure online).

Full size image
Fig. 7.
figure 7

The influence of increase willingness of share exit information to the escape time.

Full size image

As shown in Fig. 7, with the increase of the willingness of acquainted agents to share information the mean of the escape time will decrease with fairly small mean square time. We can conclude that when emergency happens, to share the information about the exit will help all the agents to get out and ease the pressure of competition.

7 Conclusions and Future Works

This paper proposes a model of dynamic decision-making for crowd simulation. This model shows the influence of safety sign and crowd on the agents’ behavior. It also shows that easing the pressure of competition of people and helping people share information and help each other will have better evacuation effect.