P

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

Path selection is one of the critical aspects in emergency evacuation. In a fire scene, how to choose an optimal evacuation path for firefighters is a challenging aspect. In this paper, firstly, a dynamic triangular network model formed by robots is presented. On the basis of this model, directed graph is established in order to calculate direct paths. Then multi-parameter information fusion which includes smoke density, temperature and oxygen density is discussed in detail for environment safety evaluation. Based on the discussions, a new way has been proposed for optimal path selection, taking into consideration the safety-factor of the path. The objectives of the method are to minimize the path lengths, at the same time, to protect firefighters from the dangerous regions. In the end, numerical simulation results prove the feasibility and superiority of this method.

Tags

Transcript

(IJARAI) International Journal of Advanced Research in Artificial Intelligence,Vol. 1, No. 7, 2012
1 |Page www.ijacsa.thesai.org
Evacuation Path Selection for Firefighters Based onDynamic Triangular Network Model
Qianyi Zhang
College of Information Science andTechnology, Donghua UniversityShanghai, china
Demin Li
College of Information Science andTechnology, Donghua UniversityShanghai, china
Yajuan An
College of Information Science andTechnology, Donghua UniversityShanghai, china
Abstract
—
Path selection is one of the critical aspects inemergency evacuation. In a fire scene, how to choose an optimalevacuation path for firefighters is a challenging aspect. In thispaper, firstly, a dynamic triangular network model formed byrobots is presented. On the basis of this model, directed graph isestablished in order to calculate direct paths. Then multi-parameter information fusion which includes smoke density,temperature and oxygen density is discussed in detail forenvironment safety evaluation. Based on the discussions, a newway has been proposed for optimal path selection, taking intoconsideration the safety-factor of the path. The objectives of themethod are to minimize the path lengths, at the same time, toprotect firefighters from the dangerous regions. In the end,numerical simulation results prove the feasibility and superiorityof this method.
Keywords- Evacuation Path Selection; Information Fusion; Dynamic Triangular Network Model.
I.
I
NTRODUCTION
In recent years, frequent fire disasters have brought greatcasualties and huge property loss. Firefighter becomes a high-risk profession. When firefighters finish the search and rescuemissions, the situation of the fire scene usually gets worse,meanwhile, the oxygen reserves the firefighters carried maybecome exhausted. Therefore the firefighters must evacuate tosafety areas as soon as possible. Due to the complex, variableand uncertain situation, it is difficult for firefighters toorientate themselves and find a suitable path to the exit. Howto choose an optimal evacuation path for firefighters is animportant and challenging problem.There are various researches regarding the problem of pathselection in emergency situations. Marina Yusoff provides agood review on the mathematical algorithm and model of evacuation problems [1]. The ant colony optimizationalgorithm is applied to find the shortest path for emergenceevacuation [2-4]. Tianyu Wang established a fire evacuationsystem and combined it with the Dijkstra Algorithm [5]. Amulti-objective optimization model based genetic algorithm isadopted to solve the proposed evacuation routing problem [6].A multi-objective approach is presented to identify evacuationpaths and the location of shelters for urban evacuationplanning [7].By now, most researches only take the shortest path as theobjective. However, the optimal path does not necessarilymean the shortest path. It should also take the path safety intoconsideration. Ulf Witkowski[8] put forward a dynamictriangular ad-hoc network formed by multi-robot systems toprovide robust communication links for human and robots in afire scene. Base on the dynamic triangular network model,Demin Li, etc. [9] proposed a method for establishing smokedensity gradient based directed graph and selecting theshortest directed path for firefighters, but did not take themultiple parameter information fusion into account.In this paper, we establish a new source-destination baseddirected graph in the dynamic triangular network model.Besides, Smoke density, temperature and oxygen density areconsidered in the information fusion for environment safetyevaluation. Our objective is to minimize the path length,meanwhile, to make assure the firefighters keep away from thedangerous regions.The paper is organized as follows: In section II, a dynamictriangular network model formed by multi-robots isestablished in a fire scene. In section III, the source-destination directed graph in the dynamic triangular network model is presented and described in detail. In section IV,firstly, multiple parameters consisting of temperature, smokedensity and oxygen density are considered in informationfusion process. The results of fusion are used to classify theenvironment into three safety levels. Secondly, based on thediscussion all above, a new path selection method with safety-factor considered is proposed and verified. The last sectionmakes the conclusion.II.
D
YNAMIC
T
RIANGULAR
N
ETWORK
M
ODEL
The modern buildings tend to be large-scale and complex atpresent. When a fire happens, all communication patterns thatrely on infrastructures might be useless and cannot supplyenough surrounding information for firefighters. Firefightersusually equip with multiple sensors and could get real-timeinformation.However, some regions are too dangerous for human toapproach, the information collection is difficult. Paper [8]proposes a dynamic triangular method for robots distribution ina fire scene. All the robots are equipped with sensors to collectsurrounding information and position data. The main purposeof the method is to deploy robots in a way with the largestcoverage for facilitate communication and environmentexploration.
(IJARAI) International Journal of Advanced Research in Artificial Intelligence,Vol. 1, No. 7, 2012
2 |Page www.ijacsa.thesai.org
Figure.1. Dynamic triangular network model graph [9]
First of all, an ad-hoc network of robots needs to be builtup. Ulf Witkowski provides a dynamic triangular network schema [8], based on this scheme, Demin Li, etc. proposed thedynamic triangular network model [9], it is shown in Figure 1.The Figure 1 shows an environment covered by the ad-hocnetwork of robots using dynamic triangular network model.Robots act as the nodes of the network. Robots are representedas circles, marked by English letters. The communication linksof the robots are indicated by solid line segments. The thickersolid lines in the figure represent the obstacles. The dynamictriangulation method provides positioning of beacons used asreference points at the vertices of equilateral or nearlyequilateral triangles.Some robots can be placed as beacons at the importantposition such as entrances, doors, corners and so on. Otherrobots might be distributed as uniformly as possible in order togather reliable information about the environment. The robotswill form a partition of the environment, separating it inregions, which will represent a triangulation in the absence of obstacles.As shown in Figure 1, a fire fighter is going to evacuate tothe exit. There are obstacles in the building, so it is not safe forhim to run directly to the exit. Besides, the smoke and flamesare also great threat to him. Since obstacles are surrounded byrobots, and every robot could get the information of neighboring environment, it is wise to evacuate along theconnection line between the robots. In this way, firefighterscould avoid obstacles and high-risk region.III.
E
STABLISHING
D
IRECTED
G
RAPH
B
ASED
O
N
D
YNAMIC
T
RIANGULAR
N
ETWORK
M
ODEL
To make the optimal path selection, firstly, directed graphin the dynamic triangular network model must be set up, sothat all the feasible direct paths could be found out. The subgraph Figure 2 of Figure 1 shows 7 nodes in the network including the exit.Node Ri is defined as a two dimension coordinate (Xi, Yi).Xi and Yi are horizontal coordinate and vertical coordinate of the node, respectively. Suppose Rj is the neighbor node of Ri,Rs is the source node and Ro is the destination node (exit). Wedefine that:(1) If |arctan[(Yj-Yi)/(Xj-Xi)]-arctan[(Yo-Ys)/(Xo-Xs)]|<90°,we could set the direction from Ri to Rj;(2) If |arctan[(Yj-Yi)/(Xj-Xi)]-arctan[(Yo-Ys)/(Xo-Xs)]|>90°,we set the direction from Rj to Ri
；
(3) If |arctan[(Yj-Yi)/(Xj-Xi)]-arctan[(Yo-Ys)/(Xo-Xs)]|=90°,the direction can be set from the further node(the distancebetween the node and the exit ) to the nearer node.In this way we make sure that every movement of thefirefighter is getting closer to the exit. According to theprinciple, we establish all the possible paths from node b tonode p. As shown in the figure, Vector Vef is perpendicular toVbw, but Re is closer to Rw , so the direction should be setfrom Rf to Re.
bef dgc ak lpmlr qinotsux vwh jFire FighterexitObstacle1Obstacle2
(IJARAI) International Journal of Advanced Research in Artificial Intelligence,Vol. 1, No. 7, 2012
3 |Page www.ijacsa.thesai.org
.
wDestinationNodeSourceNodebef k lp
Figure 2. Directed graph from node b to w
The directed graph can be converted into a path matrix Cv. If the directed arc is between the ith vertex and the jth vertex,the element of the ith row and jth column C (i, j) v isEij=exp(dij) (dij is the length of arc between Ri and Rj );Otherwise it is 0. The path matrix of Fig.2 can be defined as:
be f V k l p
,
0 0 0 0 0 00 0 0 00 0 0 0 00 0 0 0 00 0 0 00 0 0 0
be febf V ek el flkp lp
E E E C E E E E E
2
0 0 0 0 0 00 0 0 0 00 0 0 0 0 00 0 0 00 0 0 00 0 0 0
bf feV be ek fe ek be ei bf fi fe elek kp el lp fl lp
E E C E E E E E E E E E E E E E E E E
3
0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0
V bf fe ek bf fe elbe ek kp be el lp bf fl lp fe ek kp fe el lp
C E E E E E E E E E E E E E E E E E E E E E
4
0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0
V bf fe ek kp bf fe el lp
C E E E E E E E E
5 6
0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0
V V
C C
If
r V
C
（
6,1
）
=0, we conclude that there is no path fromRb to Rp taking num=r hops; while if
r V
C
（
6,1
）
>0, thereis at least one path exist between Rb and Rp with num=r hops.So all the possible paths of Fig.2 can be obtained by theformula as follows:
61
(6,1) (6,1)
nV V be ek kp be el lp bf fl lpnbf fe ek kp bf fe el lp
C C E E E E E E E E E E E E E E E E E
(1)
The value of the first factor of equation(1),
exp( )
be ek kp be ek kp
E E E d d d
, fully indicates the lengthof the path : Rb
→
Re
→
Rk
→
Rp.So the smallest factor of the formula corresponds to theshortest path. However, the optimal path does not mean theshortest path. It should also take the safety of the path intoconsideration.
(IJARAI) International Journal of Advanced Research in Artificial Intelligence,Vol. 1, No. 7, 2012
4 |Page www.ijacsa.thesai.orgIV.
T
HE
O
PTIMAL
E
VACUATION
P
ATH
S
ELECTION
In fire scenes, there are many factors that may threaten thesafety of firefighters, such as high temperature, smoke,poisonous gas and so on. Therefore, environmental situationaround the selected path is essential.Firstly, in section 3, we proposed a method to establishsource-destination based directed graph, so that all feasiblepaths can be found out; Secondly, information fusion is usedto evaluate the safety of nodes in each path, the nodes safetylevel reflects surrounding environment situation; Finally,safety-factor considered optimal path selection method ispresented.
A.
Evaluation of the environment safety based on D-S evidence theory
The environment situation of the fire scene is a complexsituation with the characteristics of dynamic, nonlinear anduncontrolled. At the same time, due to the inaccuracy of sensor and environmental noise, the information gathered bysingle sensor may be not reliable and complete. So the multi-sensor information fusion is very necessary, which is used toincrease the data using rate and to advance the informationreliability and error tolerance.Currently, there are several methods of multi-sensorinformation fusion, such as Bayesian test, Kalman filter,expert system, neural networks, fuzzy sets, D-S evidencetheory and so on.However, there are many shortages which are difficult toovercome in the process of fusion by these methods, the largeamount of data calculation limits the application of Bayesiantest and Kalman filter, the shortcoming of fuzzy sets is beingmore sensitive to the object of noise in the fusion process.Compared to this algorithm, D-S evidence theory [10-14] isbetter than the traditional methods to grasp the unknown anduncertainty of the problems, meanwhile, it does not require thepriori probability, resulting in having been widely used inmulti-sensor information fusion.There are many factors that may threaten the safety of firefighters in fire scenes; we choose three most representativeparameters to evaluate the environment situation: smokedensity, temperature and oxygen density. According to theresults of the fusion, environment safety levels are divided intothree levels (I, II, III), representing safe, and medium, riskyrespectively.The table 1 below shows the each probability of environment situation, it obtained by the expert system [11].
TABLE.I.
E
ACH
P
ROBABILITY
O
F
E
NVIRONMENT
S
ITUATION
[11]
Parameter Range Safe(I)Medium(II)Risky(III)Temperature>=800 0.2 0.1 0.7200<T<800 0.3 0.4 0.3<=200 0.7 0.1 0.2SmokeDensity>=1000 0.2 0.1 0.7600<S<1000 0.3 0.3 0.4<=600 0.7 0.1 0.2OxygenDensity<=14% 0.2 0.1 0.714%<O2<21% 0.3 0.4 0.3>=21% 0.7 0.1 0.2If the information sensor gathered at the certain time is:T=400°c, S=1200ppm, O
2
=10%, Mi means different kinds of sensors, M(i) means different levels of environment situation.The probability distribution is as follow:
TABLE.II.
P
ROBABILITY
D
ISTRIBUTION
A
T
A
C
ERTAIN
T
IME
Probability M(I) M(II) M(III)M1 0.3 0.4 0.3M2 0.2 0.1 0.7M3 0.2 0.1 0.7We obtain the results of information fusion with thealgorithm of D-S evidence theory.
(1) (1) (2)
H M M
,
(2) (1) (2) (3)
H M M M
. Papers [13-14] provide adetailed definition and fusion steps of D-S evidence theory.Learning from that, we can obtain the fusion results shown intable III.
TABLE.III. R
ESULTS
O
F
I
NFORMATION
F
USION
Probability M(I) M(II) M(III)H1 0.2564 0.0256 0.718M3 0.2 0.1 0.7H2 0.0662 0.0009 0.9329According to all the tables above, the probabilities of levelI, II, III are 0.0662
、
0.0009
、
0.9329,max{M(I),M(II),M(III)} is M
（
III
）
, obviously, thesurrounding situation of the path is very dangerous, it warnsthe firefighters to avoid the high-risk node in the evacuationprocess. We can obtain environment safety level of each nodeby information fusion in order to provide for optimal pathselection.
B.
Safety-factor considered optimal path selection
Based on the results in section A, environment safety levelof each node can be classified into a certain safety levelthrough information fusion.We assume that green, yellow and red circles representsafe, medium and risky nodes respectively. The directed graphwith safety-factor weight is shown in Figure 3 as follows.

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks