安亞娟，李德敏，許曉天，張謙益

（東華大學 信息科學與技術(shù)學院，上海 201620）

基于節(jié)點安全預(yù)測的火場撤離路徑規(guī)劃

安亞娟，李德敏，許曉天，張謙益

（東華大學 信息科學與技術(shù)學院，上海 201620）

火場煙霧彌漫、能見度低，消防隊員很難準確定位并找尋到合適的撤離路徑。文中使用人機協(xié)作在火場中建立動態(tài)三角網(wǎng)基礎(chǔ)上，以網(wǎng)絡(luò)節(jié)點為參考點為消防員規(guī)劃撤離路線。該方案使用基于相似函數(shù)的證據(jù)理論對火場中各節(jié)點采集的煙霧濃度、溫度、氧氣濃度進行數(shù)據(jù)融合，并確定節(jié)點位置的安全等級；引入預(yù)測機制，可以預(yù)測短時間內(nèi)前進路徑中節(jié)點位置的安全等級的變化。根據(jù)安全等級變化，剔除網(wǎng)絡(luò)中危險節(jié)點，使用基于路程換算的A?算法計算實時最短的安全路徑。通過數(shù)據(jù)分析表明，該方案能更好的適應(yīng)火場環(huán)境多變的特點。

動態(tài)三角網(wǎng)；撤離路徑規(guī)劃；信息預(yù)測；規(guī)避危險節(jié)點

隨著建筑物的規(guī)模越來越大，內(nèi)部結(jié)構(gòu)越來越復(fù)雜，消防員面臨的救援形勢也越來越危險。當消防員深入火災(zāi)現(xiàn)場完成搜救搶險任務(wù)后，火勢通常會惡化，由于火場煙霧彌漫，能見度低，消防隊員很難準確定位并找尋到合適的撤離路徑。為了解決這一問題，我們提出了一種基于機器人節(jié)點安全預(yù)測算法，動態(tài)選擇安全路徑，最后進行計算分析性能，可以看出該算法在動態(tài)路徑的優(yōu)越性。

為了給消防員選擇最安全的撤離路徑，Marina Yusoff[1]對近年來有關(guān)緊急撤離的數(shù)學算法和模型進行了評價總結(jié)。其中最經(jīng)典的是使用Dijkstra進行最短路徑撤離，但是在未知環(huán)境里面此法有一定的缺陷。文獻[2]將蟻群優(yōu)化算法應(yīng)用到緊急撤離的最短路徑選擇中。文獻[3]結(jié)合Dijkstra算法進行路徑選擇建立了消防疏散系統(tǒng)。有學者提出了一種改進的遺傳算法[4]，用來解決路徑規(guī)劃問題。文獻[5-6]提出基于多目標優(yōu)化模型的城市疏散計劃然而， 上述方法多數(shù)只采取路徑長度最短作為衡量最優(yōu)路徑的單一指標。Zhang[7]考慮了節(jié)點的安全性，但是未考慮火場動態(tài)性，未對節(jié)點安全進行動態(tài)預(yù)測，在撤離時高危節(jié)點可能會被規(guī)劃在所選路線中，消防員就會進入危險節(jié)點，不僅會威脅消防員的安全，還會增加了救援時間。

本文的創(chuàng)新之處主要在于根據(jù)火場實時信息對對未來短時內(nèi)路徑的安全性進行預(yù)測，并運用采集的實時數(shù)據(jù)和路徑，預(yù)測消防員的撤離路徑。這樣保證了預(yù)測的實時性和有效性。路徑安全性預(yù)測可提前排除不安全的撤離路徑，使得消防員撤離更有效率。對采集的火場信息進行融合和預(yù)測路徑安全，可保證每個周期內(nèi)計算所得安全路徑的正確性。從而選擇出安全有效的最短路徑。

1 基于節(jié)點安全預(yù)測路徑規(guī)劃

1.1 動態(tài)三角網(wǎng)

大型倉庫、超市在火災(zāi)發(fā)生時，部分通信設(shè)備可能會失效，消防員不能及時的了解現(xiàn)場信息，尤其是獲取危險區(qū)域的信息，Ulf Witkowski構(gòu)建了由機器人組建的動態(tài)三角網(wǎng)絡(luò)模型，該方法的主要目的是最大的覆蓋方式部署機器人從而為火場中的救援機器人及消防員提供了穩(wěn)固的通信。假設(shè)某時刻機器人組建的部分救援網(wǎng)絡(luò)在平面建筑中的分布如圖1所示。

圖1 救援網(wǎng)絡(luò)模型Fig. 1 Rescue network model

Zhang規(guī)定消防員在撤離過程中必須是往出口方向移動的，忽略了包圍式火勢情況下消防員無法前進的情況。本文使用基于路程換算的A*算法對有效節(jié)點進行最短路徑選擇，避免了單純使用最短路徑情況下消防員進入危險節(jié)點。

1.2 節(jié)點安全度的評價和數(shù)據(jù)融合

選取溫度，煙霧濃度和氧氣濃度3個較能體現(xiàn)火場狀態(tài)的參量作為火場安全度的評價因素。依據(jù)專家系統(tǒng)得到的各參量在不同范圍內(nèi)的環(huán)境安全狀況。運用基于相似函數(shù)的證據(jù)理論的方式融合溫度、煙霧濃度、氧氣濃度3類不同的傳感器信息。依據(jù)融合結(jié)果和在3種參數(shù)的各種濃度下人類所能承受的極限，把節(jié)點的安全等級劃分為I、II、III 3個等級，分別代表環(huán)境安全、中度危險、高風險3個狀態(tài)。

表1 參數(shù)概率賦值表Tab.1 Asignment table of parameter probability

假設(shè)在某一特定時間，傳感器收集到的信息是：煙霧濃度1 200 ppm，溫度400 ℃，氧氣濃度10%。Si代表不同類型的傳感器，E(i)代表不同級別的環(huán)境狀況，各概率分布如下表1所示,我們運用基于相似函數(shù)的證據(jù)理論的方式融合3類不同的傳感器信息。

我們對E(1), E(2) , E(3)3個分配函數(shù)進行融合計算:

結(jié)果如表2所示：

表2 特定時間的概率分布Tab.2 Probability distribution of specif i c time

根據(jù)表3最終融合結(jié)果H2顯示，環(huán)境安全，不確定，高風險的概率分別為0.146 2、0.020 9、0.832 9。

表3 信息融合結(jié)果Tab.3 Result of the information fusion

基于相似函數(shù)的證據(jù)理論的最大可信度原則，取max{E(1)，E(2)，E(3)} ，可判定環(huán)境態(tài)勢等級為III，為高風險節(jié)點，可確定該節(jié)點是危險節(jié)點，消防員必須避開此節(jié)點。通過信息融合，確定各目的節(jié)點的安全等級，從而為路徑選擇做好準備。

2 撤離路徑節(jié)點位置安全預(yù)測算法

在火場環(huán)境中，高溫、濃煙、缺氧等因素均會威脅到消防員的安全。在危險環(huán)境下消防員的前進速度會有很大限制，Pender等人據(jù)經(jīng)驗豐富的消防員粗略測算出爬行速度為每分鐘12 m[8]。因此，必須考慮火場信息的實時性獲取，并對所獲信息進行分析，從而預(yù)測出消防員到達相應(yīng)節(jié)點時此節(jié)點的安全情況。

首先以溫度為例，計算出消防員到達某一節(jié)點i時溫度。首先對已選路徑的每個節(jié)點的過去5分鐘溫度進行分析（采樣周期Δt=5 s），文獻[9]中溫度的變化具有連續(xù)性，而傳感器所得數(shù)據(jù)是離散的，故預(yù)測消防員沿某一路徑起點， 到達時刻的節(jié)點溫度的具體計算方法如下：

對煙霧濃度和氧氣濃度的預(yù)測也是采用此方法。

3 撤離路徑預(yù)測算法的結(jié)果比較

對于圖1中,若火源在障礙物1與障礙物2附近，則附近節(jié)點便是危險區(qū)域，若使用最短路徑規(guī)劃，則選擇c→g→j→o→s 。節(jié)點Ri可以用(Xi, Yi)坐標定義，對圖1中網(wǎng)絡(luò)節(jié)點傳感器數(shù)據(jù)進行數(shù)據(jù)融合，計算得到節(jié)點d,e,f,i,j,m,n處于危險區(qū)域，依據(jù)安全等級，消防員必須避開這些節(jié)點，上述最短路徑c→g→j→o→s失效。

本文撤離路徑的選擇算法流程圖如圖2所示。

圖2 撤離路徑規(guī)劃策略流程圖Fig. 2 Flow chart of evacuation path planning strategy

A*算法在搜索過程中與Dijkstra算法相比，增加了啟發(fā)函數(shù)H(x)部分，大大縮短了尋找時間。此處使用基于路程換算的A*算法快速的計算出最短路徑，啟發(fā)函數(shù)F(x)=G(x)+H(x)，其中G(x)表示已經(jīng)經(jīng)過的路徑長度，H(x)為評估值即下一可選結(jié)點到終點的笛卡爾距離。

G0表示當前經(jīng)過的路徑長度, G'表示下一路段的長度， v'為消防員標準理想速度0.5 m/s，v為消防員在節(jié)點間實際速度，相當于同比放大了G'，在算法計算時認為通行速度越慢等于距離越長。使用Java計算仿真，其中節(jié)點的顏色越深節(jié)點危險系數(shù)越大，此時求得路徑?如圖3。

圖3 初始選擇路徑Fig. 3 Initial selection path

此時預(yù)測在消防員到達節(jié)點g時將處于危險區(qū)域，必須重新選擇路徑，講節(jié)點g從有效網(wǎng)絡(luò)節(jié)點中刪除，再次運行A*算法，得到路徑?：c→1→2→k→p →t →w→z。

根據(jù)上述策略描述，火勢是實時變化的，路徑規(guī)劃必須動態(tài)規(guī)劃才能保證消防員快速安全的撤離。因此消防員在前進3個節(jié)點后重新選擇路徑得到最終的路徑如圖4。

圖4 本文算法最終選擇路徑Fig. 4 Final selection path of proposed algorithm

圖5 矩陣迭代算法選擇路徑Fig. 5 Selection path of matrix iteration algorithm

此時針對同一火場情況，消防員從相同起點就Zhang[7]所提出基于安全的矩陣迭代法與本文方法進行比較如表4，圖5表示基于矩陣迭代法選擇路徑，圖4表示基于本文方法選擇路徑。

表4 不同撤離方法對比Tab.4 Different evacuation method comparison

從以上結(jié)果可以看出，矩陣迭代法同樣可以選擇安全路徑，但是缺乏預(yù)測功能導(dǎo)致消防員進入危險節(jié)點，不但會威脅到消防員人身安全，且需要不斷的從危險節(jié)點轉(zhuǎn)移到安全節(jié)點，從而增加了撤離時間降低了效率。而本文算法則在選擇最短路徑的同時考慮火場變換動態(tài)預(yù)測安全路徑，使消防員以最短時間撤離。

4 結(jié)束語

文中提出了一種基于動態(tài)三角網(wǎng)的消防員撤離路徑規(guī)劃的優(yōu)化方法。此處機器人攜帶有傳感器，具有從消防員難以達到的未知區(qū)域獲取實時信息的優(yōu)勢。假設(shè)在構(gòu)架動態(tài)三角網(wǎng)的火場中只有一個出口，需要進一步研究的有多出口的火場撤離路徑規(guī)劃，同時此模型中的機器人是假設(shè)固定的，現(xiàn)實情況中機器人有可能跟隨消防員移動從而獲得實時數(shù)據(jù)，因此下一步研究方向為基于移動的機器人的消防員火場撤離路徑規(guī)劃。

[1] Yusoff M, Optimization Approaches for Ma-croscopic Emergency Evacuation Planning[J]. A Survey, Information Technology,2010(3):1-7.

[2] YAO Kun, CHEN Qing-quan. Applying the Ant Colony Algorithm to the Optimization of Emerbency Response Search Paths[C].CICTP,2012.

[3] ZONG Xin-lu ,Multi-objective Ant Colony Optimization Model for Emergency Evacuation[C]//International Conference on Natural Computation, 2010.

[4] WANG Tian-YU, I. The Application of the Shortest Path Algorithm in the Evacuation System[C]//International Conference of Information Technology, Computer Engineering and Management Sciences,2011.

[5] LI Qiu-ping.Multi-objective Ev-acuation Route Assignment Model Based on Genetic Algorithm[C]//Geoinformatics,18th International Conference, 2010.

[6] Joao Coutinho-Rodrigues,Lino Tralhao,Luís Alaada- Almeida,Solving a location-routing problem with a multi-objective approach:the design of urban evacuation plans[J]. Journal of Transport Geography,2012(22): 206-218.

[7] ZHANG Qian-yi.AN.Evacuat-ion Path Selection for Firefighters Based on Dynamic Triangular Network Model [J].International Journal of Advanced Research in Artificial Intelligence, 2012,1(7):1-6.

[8] PENDERS. A Robot swarm assisting a human fire-fighter[J]. Advanced Robotics,2011, 25(1-2):93-117.

[9] Joshi V.Analyzing electrical effects of RTA-driven local anneal temperature variation[C]//Proceedings of the 2010 Asia and South Pacific Design Automation Conference,2010.

An evacuation path planning based on dynamic triangular network model

AN Ya-juan, LI De-min, XU Xiao-tian, ZHANG Qian-yi
（College of Information Science and Technology, Donghua University, Shanghai 201620, China）

It’s difficult for the firefighters to position accurately when find the right evacuation path cause the smoke,low visibility. Dynamic triangulation network is generated by Robot and firefighter and used to help compute evacuation routed. Evidence theory based on similarity function is used to determine the node security levels after fusing the firedata such as smoke concentration, temperature, oxygen concentration. Prediction mechanism is introduced in order to predict the changes of the security level of node position in the forward path in a short period of time, then risk nodes in network are processed dynamically A* algorithm based on distance conversion is used periodically to calculation the shortest and safest path in real time. By computing and data analyzing, It can adapt to the characteristics of the fire environment changes more flexible.

dynamic triangulation network; evacuated route planning; Information prediction; avoiding dangerous node

TN913

A

1674-6236(2014)03-0059-03

2013–06–20 稿件編號：201306126

國家自然科學基金(71171045)

安亞娟(1988—)，女，河南濮陽人，碩士研究生。研究方向：無線自組網(wǎng)及其應(yīng)用。