# A Game Theory Based on Monte Carlo Analysis for Optimizing Evacuation Routing in Complex Scenes

Authors: Wenhui Li; Jinlong Zhu; Huiying Li; Qiong Wu; Liang Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With more complex structures and denser populations, congestion is a crucial factor in estimating evacuation clearance time. This paper presents a novel evacuation model that implements a game theory combining the greatest entropy optimization criterion with stochastic Monte Carlo methods to optimize the congestion problem and other features of emergency evacuation planning. We introduce the greatest entropy criterion for convergence to Nash equilibrium in then-person noncooperative game. The process of managing the conflict problem is divided into two steps. In the first step, we utilize Monte Carlo methods to evaluate the risk degree of each route. In the second step, we propose an improved method based on game theory, which obtains an optimal solution to guide the evacuation of all agents from the building.


---

## Body

## 1. Introduction

Emergency evacuation plans are developed to ensure the safest and most efficient evacuation time of all expected residents of a structure or region [1–4]. With the increasing complexity of building and frequency of disasters, the evacuation routing optimization problem has become very popular in the area of emergency planning. In particular, evacuee congestion-related evacuation modeling has drawn attention because evacuee congestion has a significant impact on emergency evacuation planning. Ha and Lykotrafitis [5] considered motivational force, psychological repulsive tendency, compression, viscous damping/personal force, and sliding friction in the simulation of specific emergency evacuations. They govern particles’ motion by the social-force model to investigate the effect of crowd evacuation. Chooramun et al. [6] developed an evacuation model utilizing hybrid space discretization, which uses a mixture of three basic techniques for space discretization, namely, coarse networks, fine networks, and continuous networks. Manley and Kim [7] took an agent-based approach to estimate formation of bottlenecks during urgent evacuation. Furthermore, many studies have been conducted to interpret the multiple-exit selection problem in a game-theoretic framework. The work of Zheng et al. [8–10] studied evacuees’ cooperative and competitive behaviors by using a close analogy to the chicken-type game. Tanimoto et al. [11] proposed a deductive approach to analyze the bottleneck problems of pedestrian evacuation by using a close analogy to the saint and temptation reciprocity game. Shi and Wang [12] proposed a microscopic framework to research the complicated interactions among the competing pedestrians based on the modified lattice gas model by using snowdrift game theory. Lo et al. [13] proposed a dynamic exit selection model by calculating a mixed-strategy Nash equilibrium of a zero-sum game. Li et al. [14] proposed a Bayesian game to research how pedestrians select exits for evacuation optimization. They proposed a QRA model only considering one factor with Monte Carlo methods. They regarded the individual as a participant and prepared a local framework to research the evacuation problem; however, this method omits global evacuation factors. During the past decade, game theory has been developed in the areas of competitive behaviors and the rationality problem of evacuees [15–18]. However, the degree of congestion of the emergency exit, the average congestion degree of the evacuation route, the congestion degree of diverted traffic, the route evacuation degree, the maximum flow rate of exit, and the fire origin location are six crucial factors that affect evacuation clearance time and the process of evacuation. In most evacuation models, modeling the dynamic wayfinding of people with respect to these congestion situations and the actions of other evacuees simultaneously is rare. Therefore, the present study is an attempt to present a new evacuation routing optimization from the perspective of these six factors.In this paper, we present a multiple-exit evacuation model (MEEM) based on a game with quantitative risk assessment (QRA) to make an optimal egress route plan, taking into account these six factors. MEEM uses information about the congestion and evacuees to evaluate the risks and compute the Nash equilibrium of the evacuees using the payment function of the game. To demonstrate our method, the crowd simulations treat all evacuees as discrete individuals using agent-based modeling (ABM) [5]. ABM considers each individual as a particle whose motion is governed by Newton’s equations, assuming that we know the agents’ distribution and locations. We measured experimental data from the first floor of the Computer Building in Jilin University.This paper addresses two issues. The first is how to estimate the degree of risk of a route. The second is how to determine the optimal evacuation routes for evacuees. This paper investigates the optimal evacuation plan using a game-theoretical model to estimate the degree of risk of a route. The evacuation clearance time and crowd density can be improved using this technique, which also takes full advantage of multiple exits to obtain the safest evacuation route.The remainder of this paper is organized as follows. Section2.1 introduces the QRA model based on Monte Carlo methods. Section 2.2 presents the route optimization based on game theory and introduces the related work about evacuation planning. Section 3 presents the optimization results. Section 4 concludes this paper and looks into the future of this research.


## 2. The Methodology

### 2.1. Risk Assessment

Quantitative risk assessment models based on the Monte Carlo algorithm were designed to estimate the risk indices for the routes, which are used in quantitative analysis and decision-making. They involve a class of computational algorithms that rely on repeated random sampling to calculate their results. Some researchers use Monte Carlo method for simulating pedestrian evacuation [2, 4, 19–21]. They are often used to model phenomena with significant uncertainties in inputs.Monte Carlo simulation furnishes the decision-maker with a range of possible outcomes and associated probabilities. They will occur for any choice of action. It shows the extreme possibilities of “going for broke” as well as the most conservative decision along with all conceivable consequences in between.This simulation method does not always require truthful data to be computed, such as risk assessment. We use deterministic and pseudorandom sequences, making it easy to test and rerun simulations. The only quality usually necessary to make satisfactory simulations is the pseudorandom sequence to appear “random enough” in a certain sense. The model follows a particular pattern:(1)
Define a domain of possible inputs for the risk assessment.
(2)
Randomly generate inputs from a probability distribution sampled over the domain.
(3)
Perform a deterministic estimate on the inputs according to distribution characteristics of the random variable.
(4)
Obtain the risk assessment value.The quantitative risk assessment principles estimate the risk indices of the escape route by combining the various risk weights of enclosures. We select sensitive factors as stochastic variables in the Monte Carlo analysis. The factors consist of five principal events: the fire origin location, the congestion degreec
e
x
i
t of the emergency exit, the average congestion degree c
r
o
u
t
e of the evacuation route, the congestion degree c
i
n
t
e
r
s
e
c
t
i
o
n of diverted traffic, and the route evacuation degree t
e
v
a
c
u
a
t
i
o
n.Here,t
e
v
a
c
u
a
t
i
o
n
=
d
e
x
i
t
/
s
r
o
o
m: d
e
x
i
t is the distance between the exit and the location and s
r
o
o
m is the average speed of the pedestrians in an enclosure. The congestion degree is the D value between the congestion evacuation time and the ideal evacuation time. The building construction regulates the minimum requirement of outflow rate per unit exit width and unit time, called the outflow coefficient r
a
t
e
e
v
a
c
u
a
t
e. The ideal evacuation time is the quotient of the number of pedestrians divided by r
a
t
e
e
v
a
c
u
a
t
e. As random variables, c
e
x
i
t, c
r
o
u
t
e, and t
e
v
a
c
u
a
t
i
o
n obey lognormal distributions in the QRA model, and c
i
n
t
e
r
s
e
c
t
i
o
n obeys a triangular distribution.The triangular distribution is defined using the most optimistic value OP, the maximum possible value MP, and the most pessimistic value PP, where0
<
O
P
<
M
P
<
P
P. The values around the maximum possible value are more likely to occur. The variables described by a triangular distribution include the congestion per unit of time. The triangular distribution data of congestion degree of diverted traffic are shown in Table 1.Table 1
Triangular distribution function and inverse function.
Order
OP
MP
PP
(A
-
Y
a)2/n
(B
-
Y
b)2/n
(C
-
Y
c)2/n
1
25
50
99
0.036
0.036
0.016
2
25
50
100
0.036
0.036
0.036
3
26
51
98
0.016
0.016
0.196
4
27
52
102
0.196
0.196
0.676
5
25
50
100
0.036
0.036
0.036
6
26
51
99
0.016
0.016
0.016
7
25
50
100
0.036
0.036
0.036
8
27
52
97
0.196
0.196
0.576
9
25
50
99
0.036
0.036
0.016
10
25
50
100
0.036
0.036
0.036
Y
25.6
50.6
99.4
0.64
0.64
1.64
σ
0.8
0.8
1.280625
cv
3.13%
1.58%
1.29%The QRA model calculates OP, MP, and PP for the duration time of the key congestion crossroads.Y
=
(
X
1
+
X
2
+
⋯
+
X
n
)
/
n, c
v (coefficient of dispersion) = σ
/
Y, and c
v
<
10
%.The lognormal distribution is defined using values that are positively skewed, not symmetric like a normal distribution. It is used to represent the values that do not go below zero but have unlimited positive potential. For a lognormal distributionX, the parameters denoted by μ and σ are, respectively, the mean and the standard deviation of the variable’s natural logarithm, X
=
e
μ
+
σ
Z, and Z is a standard normal variable. Norm = NORMSINV (LAP), NORMSINV is the inverse function of the standard normal distribution function, and σ
i
=
-
R
i
/
N
o
r
m. See Table 2 for the congestion degree of the emergency exit.Table 2
Lognormal distribution function and inverse function.
Order
Min
Max
CP
R
LAP
Norm
μ
σ
i
1
30
54
0.9
12
0.05
-
1.64
5
42
7.29548
2
31
55
0.85
12
0.075
-
1.4
40
43
8.33604
3
31
55
0.9
12
0.05
-
1.645
43
7.29548
4
32
56
0.9
12
0.05
-
1.645
44
7.29548
5
31
55
0.85
12
0.075
-
1.4
40
43
8.33604
6
30
54
0.85
12
0.075
-
1.4
40
42
8.33604
7
32
56
0.95
12
0.025
-
1.96
0
44
6.12256
8
30
54
0.9
12
0.05
-
1.645
42
7.29548
9
31
55
0.9
12
0.05
-
1.645
43
7.29548
10
30
54
0.85
12
0.075
-
1.4
40
42
8.33604
Y
42.8
7.59441
σ
0.748
0.69377
cv
1.75%
9.14%
Min: the congestion minimum value, Max: the congestion maximum value, and CP: coverage probability.According to the distribution function, we parse the inverse function of the random variable. Then, we calculate the results iteratively, each time drawing a different set of random deviates from the probability functions. Five hundred Monte Carlo simulation iterations are used. Finally, we calculate the mean value of each event as the tabular statement of assessment criteria (TSAC).In this section, we propose a risk index (RI) to quantify the magnitude of risk for emergency exits based on TSAC. As a general case, we consider an example of an enclosure that hasN exits leading to the outside of the building. Let R
I
=
p
i
/
∑
p
j, i
∈
N and j
∈
N, p
i representing that the ith exit has imposed capacity restrictions. We thus have(1)
p
i
x
=
min
⁡
f
i
x
,
c
i
.Here,x is the number of pedestrians in the enclosure and c
i is the threshold of the pedestrian in the ith exit making sure that every exit congestion time is less than the congestion time threshold (20 seconds). We calculate each exit that can accommodate a maximum number of evacuated people f
(
x
), concretely as (2)
f
x
i
=
t
safe
∗
s
room
t
safe
>
0
,
t
safe
<
t
evacuation
,
x
t
safe
>
0
,
t
safe
>
t
evacuation
,
0
t
safe
<
0
,where t
safe
=
t
harm
-
Q
r
i
s
k, and Q
r
i
s
k is defined as(3)
Q
risk
=
c
intersection
+
t
evacuation
+
c
exit
+
c
path
.Here,t
h
a
r
m is the available safe egress time:(4)
t
harm
=
t
c
∗
d
f
r
,where t
c is the duration time of the combustion source, d is the distance between the fire location and the exit, and f
r is the risk radius of the combustion source.RI is a weighting factor of payoff function in MEEM, allocating the distribution of evacuees in each route using game theory.


### 2.2. Route Optimization Based on Game Theory

A game consists of a set of participants, a set of strategies available to those participants, and a specification of payoffs for each combination of strategies [22].In this paper, we present MEEM by using a close analogy to then-person noncooperative game. MEEM provides a macroscopic perspective to understand the conflicts during emergency evacuation as well as the rationality of evacuees. We employ a density-detection method to judge a congestion problem. The density-detection method employed assesses the crowd density during emergency evacuations in cases where the rectangular enclosures are discrete homogeneous building enclosures. If the crowd density of rectangular enclosures is above the density threshold, we regard all escape exits as the participants of the game. We define any combination of distributed evacuations of each participant as game strategies. The maximum flow rate of each exit is the number of agents walking through an exit per unit time. The maximum flow rate (MFR) can influence the evacuation time. For example, when a number of evacuees who decide to egress through an exit come to the MFR, the evacuees must queue at the exit. The corridor has a maximum flow rate, like the exit. In order to introduce the MFR, we set the ratio σ of the MFR of the exit to the MFR of the corridor as a weighting factor in the payoff function.The enclosure calculates evacuation planning using game theory with Monte Carlo risk assessment mechanisms. The evacuation planning redistributes agents to other exits in the queue, which reduces queue sizes and the escape time.The conflict problem uses MEEM that has two significantly different processes in two different phase states. The first is a preoptimization state, in which the Dijkstra algorithm obtains the shortest route of each enclosure (e.g., a room) to an exit at the beginning of the evacuation. The second is a conflict optimizing state, in which crowd densities over the density thresholdd
threshold trigger reselection of other exits to reduce evacuation clearance time.The process of an agent’s evacuation is mainly influenced by other agents and the environment. Each agent will always choose the maximum utility (minimum cost) route with respect to the states of the exits so as to minimize the escape time. In the preoptimization state, each exit estimates the crowd density according to the expected travel time of all enclosures and the outflow coefficient. If the crowd density of an exit will exceed the density threshold, we treat an enclosure as a whole entity and assign all the evacuees of the enclosure to the exit.In the conflict optimizing state, we treat all the evacuees of crowding as a whole entity and reselect any exit, when the crowding is formed at the vicinity of an exit in the evacuation process. The distance to the reselected exit is less than the scope threshold between the reselected exit and the enclosure.As a general case, we consider the MEEM in thatP pedestrians are anxious to evacuate from an enclosure. The enclosure has N exits leading to the outside of the building. The initial positions of the evacuees are distributed randomly at the start of evacuation. The game is defined as G
=
{
R
,
S
,
A
,
U
}, where(1)
participator is theith escape exit defined as R
i, i
∈
N, N
=
{
1,2
,
…
,
n
};
(2)
strategy space is a strategy ofR
i which is S
i, S
i
∈
[
0
,
G
i
], i
∈
N and we assume that the largest number of evacuees is G
i from R
i and G
i is equal to p
i
(
x
) in QRA method;
(3)
action isB
i which is the set of actions for enclosure i; let B
=
{
select, select none
}, i
∈
N;
(4)
preference is the priority level of the game such that more dangerous routes obtain higher priority;
(5)
U
(
x
1
,
…
,
x
n
) is the payoff function of the game, where p
i
-
q
i
∗
x
i represents the payoff value of R
i; more formally, let(5)
U
x
1
,
…
,
x
n
=
p
1
-
q
1
x
1
,
…
,
p
n
-
q
n
x
n
,
0
≤
x
1
≤
G
1
,
…
,
0
≤
x
n
≤
G
n
,
0
≤
x
1
+
⋯
+
x
n
≤
P
,
0
,
…
,
0
,
other
,where p
i
=
δ
i
∗
R
I
i
∗
P, p
i
=
δ
i, and p
i
-
q
i
x
i is satisfied by(6)
σ
∗
RI
∗
P
-
x
.The product of RI timesP represents the maximal number of evacuees in the ith exit. Based on the QRA method, we can estimate the number of occupants evacuated at the ith exit by the product of RI and P. x represents the number of evacuees who set the ith exit as the destination. When x increases, R
I
∗
P
-
x decreases and so does the revenue. In addition, we consider the parameter σ as the outflow coefficient to affect the evacuation planning. When σ
<
1, it illustrates that occupants who walk through the corridor to the exit are more numerous than those who escape through the exit. With the decrease of σ, the capacity of evacuation becomes smaller, and it is more than 0. When σ is equal to 1, it indicates that the corridor and the exit have an outflow coefficient of the same width. Therefore, we take (p
i
-
q
i
∗
x
i) to influence the capacity of evacuation at each exit in terms of the evacuation rate.In game theory, a Nash equilibrium is the optimal combination of strategies. It will force the strategies proposed by some participants to be the best reaction to strategies put forward by other participants. We introduce the Greatest Entropy Criterion (GEC) for solving the Nash equilibrium involved in the game theory.The GEC shows that every player must understand what strategies other players select in order to obtain large amounts of information. Nash equilibria are expected equilibria inn-person noncooperative condition games under GEC. The Nash equilibrium is the maximum point of G. We set (
a
1
∗
,
…
,
a
n
∗
) as the expected equilibrium; a
j
∗ is the maximum point of the function G
j
(
a
j
) with the following formulation:(7)
G
j
a
j
=
∑
i
∈
M
/
L
j
u
i
j
a
j
μ
F
i
j
a
j
,
j
=
1,2
,
…
,
n
,where L
j
=
{
i
∈
M
∣
μ
i
j
(
a
j
)
=
0
,
∀
a
j
∈
D
i
j
}. M is the number of measurable sets on the measurable space, M
∈
{
1,2
,
…
,
m
}, and D
i
j
=
{
a
j
∈
A
j
∣
F
i
j
(
a
j
)
≠
⌀
}.   When each player chooses an action, A
j is a payoff function U
(
x
1
,
…
,
x
n
) for player j. In this study, we solve the maximum point with its derivative as follows: (8)
d
u
1
j
x
j
μ
F
1
j
x
j
d
x
j
=
u
1
j
x
j
d
μ
F
1
j
x
j
d
x
j
+
μ
F
1
j
x
j
d
u
1
j
x
j
d
x
j
.The detailed mathematical description of the derivative of functionG
j
(
a
j
) is given by(9)
μ
F
1
j
x
j
=
μ
x
1
∈
0
,
G
1
,
…
,
x
n
∈
0
,
G
n
∣
∑
k
=
1
,
k
≠
j
n
x
k
≤
P
-
x
j
=
1
n
-
1
!
P
-
x
j
n
-
1
.We see that the variableG
j
(
a
j
) becomes(10)
u
1
j
x
j
=
p
j
-
q
j
x
j
,
d
μ
F
1
j
x
j
d
x
j
=
-
1
n
-
2
!
P
-
x
j
n
-
2
,
u
2
j
x
j
=
0
.The derivative of the function G
P
(
a
P
) is(11)
d
u
1
j
x
j
μ
F
1
j
x
j
d
x
j
=
1
n
-
1
!
P
-
x
j
n
-
2
n
q
j
x
j
+
p
j
-
n
p
j
-
P
q
j
.We can solve forx
j. Let pro
j
=
x
j
/
Σ
x
n and obtain the pedestrian distribution pro
j
∗
P assigning the crowd to R
j. Figure 1 shows the game theory rules to deal with the conflict. The computation process will be iterated at each time step.Figure 1
Game theory to solve the congestion process.


## 2.1. Risk Assessment

Quantitative risk assessment models based on the Monte Carlo algorithm were designed to estimate the risk indices for the routes, which are used in quantitative analysis and decision-making. They involve a class of computational algorithms that rely on repeated random sampling to calculate their results. Some researchers use Monte Carlo method for simulating pedestrian evacuation [2, 4, 19–21]. They are often used to model phenomena with significant uncertainties in inputs.Monte Carlo simulation furnishes the decision-maker with a range of possible outcomes and associated probabilities. They will occur for any choice of action. It shows the extreme possibilities of “going for broke” as well as the most conservative decision along with all conceivable consequences in between.This simulation method does not always require truthful data to be computed, such as risk assessment. We use deterministic and pseudorandom sequences, making it easy to test and rerun simulations. The only quality usually necessary to make satisfactory simulations is the pseudorandom sequence to appear “random enough” in a certain sense. The model follows a particular pattern:(1)
Define a domain of possible inputs for the risk assessment.
(2)
Randomly generate inputs from a probability distribution sampled over the domain.
(3)
Perform a deterministic estimate on the inputs according to distribution characteristics of the random variable.
(4)
Obtain the risk assessment value.The quantitative risk assessment principles estimate the risk indices of the escape route by combining the various risk weights of enclosures. We select sensitive factors as stochastic variables in the Monte Carlo analysis. The factors consist of five principal events: the fire origin location, the congestion degreec
e
x
i
t of the emergency exit, the average congestion degree c
r
o
u
t
e of the evacuation route, the congestion degree c
i
n
t
e
r
s
e
c
t
i
o
n of diverted traffic, and the route evacuation degree t
e
v
a
c
u
a
t
i
o
n.Here,t
e
v
a
c
u
a
t
i
o
n
=
d
e
x
i
t
/
s
r
o
o
m: d
e
x
i
t is the distance between the exit and the location and s
r
o
o
m is the average speed of the pedestrians in an enclosure. The congestion degree is the D value between the congestion evacuation time and the ideal evacuation time. The building construction regulates the minimum requirement of outflow rate per unit exit width and unit time, called the outflow coefficient r
a
t
e
e
v
a
c
u
a
t
e. The ideal evacuation time is the quotient of the number of pedestrians divided by r
a
t
e
e
v
a
c
u
a
t
e. As random variables, c
e
x
i
t, c
r
o
u
t
e, and t
e
v
a
c
u
a
t
i
o
n obey lognormal distributions in the QRA model, and c
i
n
t
e
r
s
e
c
t
i
o
n obeys a triangular distribution.The triangular distribution is defined using the most optimistic value OP, the maximum possible value MP, and the most pessimistic value PP, where0
<
O
P
<
M
P
<
P
P. The values around the maximum possible value are more likely to occur. The variables described by a triangular distribution include the congestion per unit of time. The triangular distribution data of congestion degree of diverted traffic are shown in Table 1.Table 1
Triangular distribution function and inverse function.
Order
OP
MP
PP
(A
-
Y
a)2/n
(B
-
Y
b)2/n
(C
-
Y
c)2/n
1
25
50
99
0.036
0.036
0.016
2
25
50
100
0.036
0.036
0.036
3
26
51
98
0.016
0.016
0.196
4
27
52
102
0.196
0.196
0.676
5
25
50
100
0.036
0.036
0.036
6
26
51
99
0.016
0.016
0.016
7
25
50
100
0.036
0.036
0.036
8
27
52
97
0.196
0.196
0.576
9
25
50
99
0.036
0.036
0.016
10
25
50
100
0.036
0.036
0.036
Y
25.6
50.6
99.4
0.64
0.64
1.64
σ
0.8
0.8
1.280625
cv
3.13%
1.58%
1.29%The QRA model calculates OP, MP, and PP for the duration time of the key congestion crossroads.Y
=
(
X
1
+
X
2
+
⋯
+
X
n
)
/
n, c
v (coefficient of dispersion) = σ
/
Y, and c
v
<
10
%.The lognormal distribution is defined using values that are positively skewed, not symmetric like a normal distribution. It is used to represent the values that do not go below zero but have unlimited positive potential. For a lognormal distributionX, the parameters denoted by μ and σ are, respectively, the mean and the standard deviation of the variable’s natural logarithm, X
=
e
μ
+
σ
Z, and Z is a standard normal variable. Norm = NORMSINV (LAP), NORMSINV is the inverse function of the standard normal distribution function, and σ
i
=
-
R
i
/
N
o
r
m. See Table 2 for the congestion degree of the emergency exit.Table 2
Lognormal distribution function and inverse function.
Order
Min
Max
CP
R
LAP
Norm
μ
σ
i
1
30
54
0.9
12
0.05
-
1.64
5
42
7.29548
2
31
55
0.85
12
0.075
-
1.4
40
43
8.33604
3
31
55
0.9
12
0.05
-
1.645
43
7.29548
4
32
56
0.9
12
0.05
-
1.645
44
7.29548
5
31
55
0.85
12
0.075
-
1.4
40
43
8.33604
6
30
54
0.85
12
0.075
-
1.4
40
42
8.33604
7
32
56
0.95
12
0.025
-
1.96
0
44
6.12256
8
30
54
0.9
12
0.05
-
1.645
42
7.29548
9
31
55
0.9
12
0.05
-
1.645
43
7.29548
10
30
54
0.85
12
0.075
-
1.4
40
42
8.33604
Y
42.8
7.59441
σ
0.748
0.69377
cv
1.75%
9.14%
Min: the congestion minimum value, Max: the congestion maximum value, and CP: coverage probability.According to the distribution function, we parse the inverse function of the random variable. Then, we calculate the results iteratively, each time drawing a different set of random deviates from the probability functions. Five hundred Monte Carlo simulation iterations are used. Finally, we calculate the mean value of each event as the tabular statement of assessment criteria (TSAC).In this section, we propose a risk index (RI) to quantify the magnitude of risk for emergency exits based on TSAC. As a general case, we consider an example of an enclosure that hasN exits leading to the outside of the building. Let R
I
=
p
i
/
∑
p
j, i
∈
N and j
∈
N, p
i representing that the ith exit has imposed capacity restrictions. We thus have(1)
p
i
x
=
min
⁡
f
i
x
,
c
i
.Here,x is the number of pedestrians in the enclosure and c
i is the threshold of the pedestrian in the ith exit making sure that every exit congestion time is less than the congestion time threshold (20 seconds). We calculate each exit that can accommodate a maximum number of evacuated people f
(
x
), concretely as (2)
f
x
i
=
t
safe
∗
s
room
t
safe
>
0
,
t
safe
<
t
evacuation
,
x
t
safe
>
0
,
t
safe
>
t
evacuation
,
0
t
safe
<
0
,where t
safe
=
t
harm
-
Q
r
i
s
k, and Q
r
i
s
k is defined as(3)
Q
risk
=
c
intersection
+
t
evacuation
+
c
exit
+
c
path
.Here,t
h
a
r
m is the available safe egress time:(4)
t
harm
=
t
c
∗
d
f
r
,where t
c is the duration time of the combustion source, d is the distance between the fire location and the exit, and f
r is the risk radius of the combustion source.RI is a weighting factor of payoff function in MEEM, allocating the distribution of evacuees in each route using game theory.


## 2.2. Route Optimization Based on Game Theory

A game consists of a set of participants, a set of strategies available to those participants, and a specification of payoffs for each combination of strategies [22].In this paper, we present MEEM by using a close analogy to then-person noncooperative game. MEEM provides a macroscopic perspective to understand the conflicts during emergency evacuation as well as the rationality of evacuees. We employ a density-detection method to judge a congestion problem. The density-detection method employed assesses the crowd density during emergency evacuations in cases where the rectangular enclosures are discrete homogeneous building enclosures. If the crowd density of rectangular enclosures is above the density threshold, we regard all escape exits as the participants of the game. We define any combination of distributed evacuations of each participant as game strategies. The maximum flow rate of each exit is the number of agents walking through an exit per unit time. The maximum flow rate (MFR) can influence the evacuation time. For example, when a number of evacuees who decide to egress through an exit come to the MFR, the evacuees must queue at the exit. The corridor has a maximum flow rate, like the exit. In order to introduce the MFR, we set the ratio σ of the MFR of the exit to the MFR of the corridor as a weighting factor in the payoff function.The enclosure calculates evacuation planning using game theory with Monte Carlo risk assessment mechanisms. The evacuation planning redistributes agents to other exits in the queue, which reduces queue sizes and the escape time.The conflict problem uses MEEM that has two significantly different processes in two different phase states. The first is a preoptimization state, in which the Dijkstra algorithm obtains the shortest route of each enclosure (e.g., a room) to an exit at the beginning of the evacuation. The second is a conflict optimizing state, in which crowd densities over the density thresholdd
threshold trigger reselection of other exits to reduce evacuation clearance time.The process of an agent’s evacuation is mainly influenced by other agents and the environment. Each agent will always choose the maximum utility (minimum cost) route with respect to the states of the exits so as to minimize the escape time. In the preoptimization state, each exit estimates the crowd density according to the expected travel time of all enclosures and the outflow coefficient. If the crowd density of an exit will exceed the density threshold, we treat an enclosure as a whole entity and assign all the evacuees of the enclosure to the exit.In the conflict optimizing state, we treat all the evacuees of crowding as a whole entity and reselect any exit, when the crowding is formed at the vicinity of an exit in the evacuation process. The distance to the reselected exit is less than the scope threshold between the reselected exit and the enclosure.As a general case, we consider the MEEM in thatP pedestrians are anxious to evacuate from an enclosure. The enclosure has N exits leading to the outside of the building. The initial positions of the evacuees are distributed randomly at the start of evacuation. The game is defined as G
=
{
R
,
S
,
A
,
U
}, where(1)
participator is theith escape exit defined as R
i, i
∈
N, N
=
{
1,2
,
…
,
n
};
(2)
strategy space is a strategy ofR
i which is S
i, S
i
∈
[
0
,
G
i
], i
∈
N and we assume that the largest number of evacuees is G
i from R
i and G
i is equal to p
i
(
x
) in QRA method;
(3)
action isB
i which is the set of actions for enclosure i; let B
=
{
select, select none
}, i
∈
N;
(4)
preference is the priority level of the game such that more dangerous routes obtain higher priority;
(5)
U
(
x
1
,
…
,
x
n
) is the payoff function of the game, where p
i
-
q
i
∗
x
i represents the payoff value of R
i; more formally, let(5)
U
x
1
,
…
,
x
n
=
p
1
-
q
1
x
1
,
…
,
p
n
-
q
n
x
n
,
0
≤
x
1
≤
G
1
,
…
,
0
≤
x
n
≤
G
n
,
0
≤
x
1
+
⋯
+
x
n
≤
P
,
0
,
…
,
0
,
other
,where p
i
=
δ
i
∗
R
I
i
∗
P, p
i
=
δ
i, and p
i
-
q
i
x
i is satisfied by(6)
σ
∗
RI
∗
P
-
x
.The product of RI timesP represents the maximal number of evacuees in the ith exit. Based on the QRA method, we can estimate the number of occupants evacuated at the ith exit by the product of RI and P. x represents the number of evacuees who set the ith exit as the destination. When x increases, R
I
∗
P
-
x decreases and so does the revenue. In addition, we consider the parameter σ as the outflow coefficient to affect the evacuation planning. When σ
<
1, it illustrates that occupants who walk through the corridor to the exit are more numerous than those who escape through the exit. With the decrease of σ, the capacity of evacuation becomes smaller, and it is more than 0. When σ is equal to 1, it indicates that the corridor and the exit have an outflow coefficient of the same width. Therefore, we take (p
i
-
q
i
∗
x
i) to influence the capacity of evacuation at each exit in terms of the evacuation rate.In game theory, a Nash equilibrium is the optimal combination of strategies. It will force the strategies proposed by some participants to be the best reaction to strategies put forward by other participants. We introduce the Greatest Entropy Criterion (GEC) for solving the Nash equilibrium involved in the game theory.The GEC shows that every player must understand what strategies other players select in order to obtain large amounts of information. Nash equilibria are expected equilibria inn-person noncooperative condition games under GEC. The Nash equilibrium is the maximum point of G. We set (
a
1
∗
,
…
,
a
n
∗
) as the expected equilibrium; a
j
∗ is the maximum point of the function G
j
(
a
j
) with the following formulation:(7)
G
j
a
j
=
∑
i
∈
M
/
L
j
u
i
j
a
j
μ
F
i
j
a
j
,
j
=
1,2
,
…
,
n
,where L
j
=
{
i
∈
M
∣
μ
i
j
(
a
j
)
=
0
,
∀
a
j
∈
D
i
j
}. M is the number of measurable sets on the measurable space, M
∈
{
1,2
,
…
,
m
}, and D
i
j
=
{
a
j
∈
A
j
∣
F
i
j
(
a
j
)
≠
⌀
}.   When each player chooses an action, A
j is a payoff function U
(
x
1
,
…
,
x
n
) for player j. In this study, we solve the maximum point with its derivative as follows: (8)
d
u
1
j
x
j
μ
F
1
j
x
j
d
x
j
=
u
1
j
x
j
d
μ
F
1
j
x
j
d
x
j
+
μ
F
1
j
x
j
d
u
1
j
x
j
d
x
j
.The detailed mathematical description of the derivative of functionG
j
(
a
j
) is given by(9)
μ
F
1
j
x
j
=
μ
x
1
∈
0
,
G
1
,
…
,
x
n
∈
0
,
G
n
∣
∑
k
=
1
,
k
≠
j
n
x
k
≤
P
-
x
j
=
1
n
-
1
!
P
-
x
j
n
-
1
.We see that the variableG
j
(
a
j
) becomes(10)
u
1
j
x
j
=
p
j
-
q
j
x
j
,
d
μ
F
1
j
x
j
d
x
j
=
-
1
n
-
2
!
P
-
x
j
n
-
2
,
u
2
j
x
j
=
0
.The derivative of the function G
P
(
a
P
) is(11)
d
u
1
j
x
j
μ
F
1
j
x
j
d
x
j
=
1
n
-
1
!
P
-
x
j
n
-
2
n
q
j
x
j
+
p
j
-
n
p
j
-
P
q
j
.We can solve forx
j. Let pro
j
=
x
j
/
Σ
x
n and obtain the pedestrian distribution pro
j
∗
P assigning the crowd to R
j. Figure 1 shows the game theory rules to deal with the conflict. The computation process will be iterated at each time step.Figure 1
Game theory to solve the congestion process.


## 3. Discussion and Results

The configurations for the simulation are set as follows:(1)
The room is a square space, 10 m × 15 m. The corridor is a square space, 40 m × 4 m.
(2)
There are 40 pedestrians in each room with a total of 160 pedestrians in the entire building.
(3)
The fire location is in the middle of a long corridor space. The fire and the corridor are 18 m apart.
(4)
We set the parameters of fire as follows:f
r
=
2, t
c
=
10, and d
=
20
2.Figure2 shows four rooms (black squares), a corridor (gray square), four doors (red squares), and two escape exits (purple squares). The average escape time for the agent, MEEM, and exit selection models are 89 minutes, 77 minutes, and 84 minutes, respectively.Figure 2
Study of the evacuation of the building with four rooms.Table3 shows the distribution of evacuees among two exits. We can see that MEEM makes the most of the availability of the two exits. The simulation output with the game theory model provides a more rational result than the agent method by merely considering the travel distance from the exit. Our algorithm is compared to the agent method to reduce the evacuation time and the degree of congestion.Table 3
Exiting pattern for a 4-room/1-corridor situation.
Agent model [5]
MEEM
Exit selection model [13]
P
Exit 1
160
116
130
Exit 2
0
44
30
T
89
77
84Table4 shows the simulation output of different outflow coefficient ratios for the first exit in the game. When σ is closer to 1, the evacuation capability is larger. With an increase of the outflow coefficient ratio, the evacuation time becomes smaller but is not more than 1. The experiment demonstrated that the referenced evacuation coefficient can affect the evacuation planning.Table 4
Exiting pattern for different outflow coefficient ratio situation.
σ
=
0.5
σ
=
1
P
Exit 1
116
152
Exit 2
44
8
T
77
57
P: cumulative number of persons passing through the exit. T: clearance time.Figure3 shows that the simulated output of the two methods gives the same evacuation time when P is less than 80. That is because the congestion degree is less than the density threshold, and the optimized evacuation route can be found without using game theory. With the increase of P, the time difference of the two methods becomes greater but is not more than 260. When 260 pedestrians evacuate from the entire building, the agent using game theory is able to push the optimization ability to its limits.Figure 3
Average escape time by agent and MEEM.To test our algorithm, we ran it on the first floor of the Computer Building in Jilin University as shown in Figure4. Figure 4 shows the layout plan of the first floor. The building information, labeled on the diagram, is as follows.Figure 4
Layout plan.Here,A (B) represents an enclosure A which will accommodate B pedestrians in the circle. Exit C
/
D describes exit information as a serial number divided by the outflow coefficient of the exit. All occupants will escape from the enclosure and then pass through the exit to reach the place of safety.The gray rectangles are the corridors of the building. We mark the outflow coefficient of the corridor on its inside.For example, Exit 1 is an escape hatch in the shortest route of enclosure 15. When the crowd is formed at the vicinity of Exit 1, enclosure 15 will seek an alternative exit. The optional exits include Exit 1, Exit 2, Exit 3, and Exit 4. Figure6 shows the evacuation assessment of each exit. The red curve represents the number of congestion agents at the exit, and the blue curve represents the number of agents at the exit.The QRA method calculated the RI of each route according to the threshold of the pedestrian. It generated the tabular statement of assessment criteria for escape routes as shown in Tables5 and 7.Table 5
Evaluation index table.
Number
Export congestion
Path congestion
Intersection congestion
Path time-consuming
RN
cv
RN
cv
RN
cv
RN
cv
1
0.499257
42.79
0.710921
14.45
0.285449
7.10
0.96203
99.16
2
0.405381
40.98
0.983167
19.38
0.662515
8.84
0.034211
25.92
3
0.794601
49.05
0.983125
19.38
0.294659
7.15
0.416339
98.46
4
0.763606
48.25
0.564434
13.21
0.929786
10.70
0.03238
25.91
5
0.419017
41.25
0.147974
9.41
0.260629
6.97
0.127017
26.21
6
0.747297
47.86
0.67011
14.09
0.89551
10.32
0.66539
98.69
7
0.259172
37.89
0.368653
11.64
0.89474
10.31
0.652972
98.68
8
0.025218
27.94
0.038118
7.12
0.41223
7.71
0.671424
98.70
9
0.344342
39.76
0.445005
12.26
0.30068
7.18
0.487949
98.52
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
500
0.193843
26.36
0.193843
26.36
0.193843
26.36
0.193843
26.36
Mean
0.50896
43.02019
0.468052
12.38077
0.476657
7.968394
0.50492
73.96422
RN: random number, RN∈
[0, 1], and cv: corresponding value.The simulation output provides a more rational result than merely considering the travel distance to the exit. The total number of evacuees is 806. Table6 shows the distribution of the crowd evacuation. The digits are the serial number of the enclosure in front of the brackets of the section column, and the quantitative distribution of the pedestrians is in the brackets. The Headcount column is the total number of pedestrians.Table 6
Evacuation allocation table.
Section
Headcount
Exit
Pretreatment
1(
5
), 2(
5
), 3(
5
), 4(
5
), 5(
5
), 6(
5
), 7(
5
), 8(
5
), 9(
5
), 10(
6
), 11(
7
), 12(
6
), 13(
8
), 14(
100
), 15(
100
), 31(
2
), 32(
100
), 33(
100
), 34(
35
), 35(
35
), 36(
35
), 37(
6
), 38(
5
), 39(
5
), 40(
5
), 41(
5
), 42(
5
), 43 (
5
)
615
1
Postoptimality
1(
5
), 10 (
6
), 31(
2
), 32(
100
), 33(
79
), 34 (
35
), 35 (
35
), 37(
6
), 38(
5
), 40(
5
), 41(
5
), 42(
5
), 43 (
5
)
293
Pretreatment
16(
10
), 17(
10
), 18(
10
), 19(
10
), 20(
10
), 21(
60
), 27(
10
), 28(
8
), 29(
6
), 30(
7
)
141
2
Postoptimality
2(
3
), 3(
3
), 4(
3
), 5(
3
), 6(
3
), 7(
3
), 8(
3
), 9(
3
), 11(
5
), 12(
2
), 13(
6
), 14(
60
), 15(
66
), 16(
10
), 17(
10
), 18(
10
), 19(
10
), 20(
10
), 21(
60
), 27(
10
), 28(
8
), 29(
6
), 30(
7
), 33(
21
), 36(
21
), 39(
3
)
349
Pretreatment
22(
10
), 23(
10
)
20
3
Postoptimality
2(
1
), 3(
1
), 4(
1
), 5(
1
), 6(
1
), 7(
1
), 8(
1
), 9(
1
), 11(
1
), 12(
2
), 13 (
1
), 14(
20
), 15(
17
), 22(
10
), 23(
10
), 36(
7
), 39(
1
)
77
Pretreatment
24(
10
), 25(
10
), 26(
10
)
30
4
Postoptimality
2(
1
), 3(
1
), 4(
1
), 5(
1
), 6(
1
), 7(
1
), 8(
1
), 9(
1
), 11(
1
), 12(
2
), 13(
1
), 14(
20
), 15(
17
), 24(
10
), 25(
10
), 26(
10
), 36(
7
), 39(
1
)
87Table 7
QRA degree list of each exit.
Exit
EC
PC
IC
PTC
QRA
1
43.02
12.38
7.97
73.96
100.81
2
0
0
7.83
36.21
44.04
3
0
0
7.96
55.13
63.09
4
0
0
7.86
55.98
63.84
EC: export congestion, PC: path congestion, IC: intersection congestion, and PTC: path time-consuming.We analyzed the data merely considering the travel distance from the exit and game theory to optimize the export evacuation. The upper half of Figure7 is the result of the merely agent-based optimization evacuation. The lower half is the details of the evacuation plan. Subsequently, congestion data and evacuation data are described as ways for analyzing the evacuation in Figure 5. Figure 8 is the optimized evacuation diagram. Comparing the two optimized kinds of data shows that the merely agent-based optimization evacuation cost is 161 s and the maximum congestion number is 332 pedestrians, while the optimized game evacuation cost is 121 s. Meanwhile, we can see from Figure 8 that the evacuation takes full advantage of the four exits and the congestion number is not more than 37.Figure 5
Simulation output of each exit.
(a)
Exit 1
(b)
Exit 2
(c)
Exit 3
(d)
Exit 4Figure 6
Expected evacuation numbers of each exit. (a) The pedestrian evacuation distribution at Exit 2. (b) The pedestrian evacuation distribution at Exit 3 and Exit 4.
(a)
Exit 2
(b)
Exit 3 and Exit 4Figure 7
The mere consideration of the travel distance from the exit.Figure 8
Optimizing the evacuation effect diagram.
(a)
The pedestrian evacuation plan
(b)
The pedestrian congestion diagramFinally, comparing a simulation output for the snowdrift game theory and the exit selection model, we note that those two methods improve the evacuation planning better than the agent method in Table8. We set P
I
C
=
0.5, k
=
0.1, P
C
=
0.5, and r
=
0.8 in the snowdrift game theory.Table 8
Evacuation characteristics of the contrast table.
The evacuation method
Time (s)
MEEM
121 s
Agent [5]
161
Exit selection model [13]
132
Snowdrift game theory [12]
156Since snowdrift game theory merely considers a single room, we introduce the shortest route to the global optimization of evacuation planning, in order to compare with our approach.The performance of the exit selection model obtains a better result than the snowdrift game theory. However, the exit selection model does not consider fire source positions or MFR. In addition, the agent and snowdrift game theories are microscopic optimizations for evacuation and merely obtain locally optimal solutions, so they cannot arrive at a globally optimal solution from a local optimum in a complex scene. Table8 shows that our proposed algorithm improves the efficiency of the evacuation. Our method can minimize time compared to other methods. We can conclude that the method guides evacuations to achieve larger outflow and lower probability for congestion at the exit.


## 4. Conclusion

Evacuation optimization technology has traditionally faced the problem of achieving effective evacuation planning with minimal evacuation clearance time for individuals. In this paper, we have presented a novel model (MEEM) in which game theory and Monte Carlo methods are combined for evacuation routing optimization in complex scenes. The improved game theory method finds the global minimizer for the evacuation time using maximum entropy theory. This model obtains a global optimum agent distribution with an estimation of the degree of risk of a route to manage the routing selection problem and the congestion conflict problem. Compared to other evacuation models, we employed a method based on an agent whose motion is governed by Newton’s equations to simulate the effect of complex building architectures during urgent evacuation. MEEM has been established to examine how the rational evacuation planning of the evacuees affects the evacuation process. Our model considers the exits as participants rather than agents, which can deal with more agents in the game optimization problem. Finally, we develop evacuation plans by calculating payoff functions for convergence to Nash equilibria, which are established based on maximum entropy theory. Thus, MEEM can rationalize the route of the evacuees. Further work will need to examine the effect of familiarity and environmental stimuli as well as accident prevention effects on multiple-exit selection.



---

*Source: 292093-2015-05-26.xml*