基于節(jié)點(diǎn)安全預(yù)測(cè)的火場(chǎng)撤離路徑規(guī)劃

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

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

基于節(jié)點(diǎn)安全預(yù)測(cè)的火場(chǎng)撤離路徑規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

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

1.2 節(jié)點(diǎn)安全度的評(píng)價(jià)和數(shù)據(jù)融合

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

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

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

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

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

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

根據(jù)表3最終融合結(jié)果H2顯示，環(huán)境安全，不確定，高風(fēng)險(xiǎ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)勢(shì)等級(jí)為III，為高風(fēng)險(xiǎn)節(jié)點(diǎn)，可確定該節(jié)點(diǎn)是危險(xiǎn)節(jié)點(diǎn)，消防員必須避開此節(jié)點(diǎn)。通過信息融合，確定各目的節(jié)點(diǎn)的安全等級(jí)，從而為路徑選擇做好準(zhǔn)備。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

國家自然科學(xué)基金(71171045)

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