基于節點安全預測的火場撤離路徑規劃

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

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

基于節點安全預測的火場撤離路徑規劃

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

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

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

動態三角網；撤離路徑規劃；信息預測；規避危險節點

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

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

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

1 基于節點安全預測路徑規劃

1.1 動態三角網

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

圖1 救援網絡模型Fig. 1 Rescue network model

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

1.2 節點安全度的評價和數據融合

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

表1 參數概率賦值表Tab.1 Asignment table of parameter probability

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

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

結果如表2所示：

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

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

表3 信息融合結果Tab.3 Result of the information fusion

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

2 撤離路徑節點位置安全預測算法

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

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

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

3 撤離路徑預測算法的結果比較

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

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

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

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

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

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

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

根據上述策略描述，火勢是實時變化的，路徑規劃必須動態規劃才能保證消防員快速安全的撤離。因此消防員在前進3個節點后重新選擇路徑得到最終的路徑如圖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

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

4 結束語

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

[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—)，女，河南濮陽人，碩士研究生。研究方向：無線自組網及其應用。