考慮液氧泄漏的改進(jìn)A*算法及其應(yīng)用*

張學(xué)鋒， 賈夢成， 湯亞玲， 儲岳中

(安徽工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 馬鞍山 243000)

0 引 言

當(dāng)前國內(nèi)工廠意外事故時有發(fā)生，其中不乏由于職工應(yīng)急處置錯誤而造成的重大后果。由于在現(xiàn)實中演練成本太高，所以為更好地應(yīng)對工廠突發(fā)事件，國內(nèi)外公司企業(yè)不斷地研發(fā)應(yīng)急演練平臺，通過讓職工操作PC端演練平臺以達(dá)到對其培訓(xùn)的目的。例如為應(yīng)對電力系統(tǒng)由于設(shè)備的危險性和操作的高要求無法經(jīng)常實地開展，王歡等[1]設(shè)計出一套模擬危險設(shè)備操作的應(yīng)急演練系統(tǒng)。但該系統(tǒng)的任務(wù)是由指揮小組手動發(fā)布而非一套標(biāo)準(zhǔn)化任務(wù)流程，同時企業(yè)會因工作需要時常改變環(huán)境布局，因此該系統(tǒng)無法滿足調(diào)整場景需求。國內(nèi)許多大學(xué)在人員疏散仿真模擬方面一直有深入研究。在文獻(xiàn)[2]中，張潤蓮等提出了基于距離與坡度的改進(jìn)A*尋路算法模型，該模型的提出優(yōu)化了搜索路徑，降低了搜索時間；張學(xué)鋒等[3]提出了基于多智能體技術(shù)的人員感知疏散模型。以上的算法改進(jìn)雖提高了算法效率但未考慮路徑的安全性。在危險發(fā)生時保證路徑的安全性是首當(dāng)其沖的,在獲取尋路路徑時應(yīng)結(jié)合尋路算法與風(fēng)險評估兩種模型考慮[4]，同時將演練平臺和人員疏散系統(tǒng)結(jié)合可以更好地應(yīng)用于實際中。

針對上述問題，提出了集演練平臺和人員疏散于一體的應(yīng)急演練系統(tǒng)，在此基礎(chǔ)之上研發(fā)了一套場景配置平臺，該平臺使得用戶可根據(jù)自身需要對場景進(jìn)行修改。傳統(tǒng)A*算法并未考慮場景的復(fù)雜性和安全性，在應(yīng)急演練系統(tǒng)中運用尋路算法時應(yīng)考慮線路中每個路點與災(zāi)難點是否保持安全距離，同時應(yīng)考慮距離與方向?qū)l(fā)函數(shù)的影響。為使得尋路算法更好地應(yīng)用于液氧泄漏實際問題中,提出了將液氧泄漏風(fēng)險模型與修改啟發(fā)函數(shù)的改進(jìn)A*算法相結(jié)合的方法。

1 系統(tǒng)架構(gòu)及設(shè)計流程

該應(yīng)急演練系統(tǒng)以Unity作為開發(fā)平臺，以3DsMax作為建模軟件對工廠進(jìn)行建模。通過多人協(xié)同完成配置好的任務(wù)流程以達(dá)到模擬現(xiàn)實災(zāi)難發(fā)生后做出正確處理以使損失降到最低的目的，同時系統(tǒng)將改進(jìn)后的A*算法應(yīng)用其中，以實現(xiàn)規(guī)劃模擬逃生路徑，達(dá)到讓用戶掌握災(zāi)難應(yīng)急處理和了解更安全逃生路線的目的。

系統(tǒng)通過構(gòu)建多個模塊與子系統(tǒng)來完成預(yù)案流程，達(dá)到處理災(zāi)難點的目的(圖1)。該系統(tǒng)分為系統(tǒng)服務(wù)端、客戶端。服務(wù)分為云數(shù)據(jù)服務(wù)和數(shù)據(jù)服務(wù)。數(shù)據(jù)服務(wù)的主要功能是解析角色登錄信息，從數(shù)據(jù)庫中獲取預(yù)案信息、裝備信息、題目信息等發(fā)送給客戶端以回應(yīng)客戶端的請求，以及同步各角色的位置，記錄每次演練的效果及成績等。該演練系統(tǒng)的客戶端通過多個模塊的設(shè)計讓系統(tǒng)中的角色完成已設(shè)定好的任務(wù)，從而模擬發(fā)生液氧泄漏時應(yīng)做出的緊急處理，達(dá)到演練的效果。此外該應(yīng)急演練系統(tǒng)還具備場景配置功能，用戶可根據(jù)自身需求在場景配置端進(jìn)行修改，修改后的場景信息以xml文件保存在服務(wù)器中，重新打開演練平臺時系統(tǒng)自動讀取該信息并覆蓋原演練場景。圖2為系統(tǒng)界面。

圖1 系統(tǒng)框架

圖2 系統(tǒng)界面

2 標(biāo)準(zhǔn)A*算法

20世紀(jì)60年代末，Hart和Nilsson將最為經(jīng)典的A*算法提出，雖然半個世紀(jì)的時間已經(jīng)過去，各項技術(shù)和科學(xué)已有了質(zhì)的飛躍，但A*算法依然是最有效果的靜態(tài)路網(wǎng)尋求最短路徑的直接搜索算法，同時也是許多現(xiàn)實生活的科技產(chǎn)品中較為常用的啟發(fā)式算法之一。

A*算法的原理可以用一個估價函數(shù)如式(1)所示：

f(n)=g(n)+h(n)

(1)

g(n)代表著當(dāng)前所在位置與起始點之間的距離，h(n)代表的是當(dāng)前所在位置與終點之間的距離，f(n)代表了對當(dāng)前節(jié)點n的估價。以當(dāng)前點n為中心分別計算該節(jié)點附近8個點的代價并從中選出最小代價的點，以該選中點為中心繼續(xù)以上操作直至到達(dá)終點。由此操作規(guī)劃出的路徑即為起點與終點間的最優(yōu)路徑。其中距離通常采用曼哈頓距離如式(2)所示，歐式距離如式(3)所示或切比雪夫距離[5-6]如式(4)所示：

DM=|x1-xgoal|+|y1-ygoal|

(2)

(3)

DC=max{ |x1-xgoal|,|y1-ygoal| }

(4)

步驟：首先建立表并將地形信息以坐標(biāo)的形式存入表中,建立close表和open表，分別存儲當(dāng)前節(jié)點周圍已遍歷的8個子節(jié)點及其估計值和已走過的節(jié)點；先將起始點存于open表中，對open表中最新加入元素的周圍8個子節(jié)點遍歷，并計算出每個子節(jié)點的估價值，對比close表，若該表中無加入的子節(jié)點，則將其存于close表中，如果有該點，則更新該子節(jié)點的信息；再對close表中所有元素排序，取出估價值最小的節(jié)點存于open表中。重復(fù)以上操作直至到達(dá)終點，即獲得了最優(yōu)路徑。

3 A*算法的改進(jìn)

傳統(tǒng)的A*尋路算法僅考慮了最小網(wǎng)格映射中路徑長度來生成最小路徑，并未考慮場景的復(fù)雜性和安全性，難以應(yīng)用于實際問題中，為更好地解決實際問題，需要對標(biāo)準(zhǔn)A*算法進(jìn)行改進(jìn)。

3.1 改進(jìn)原理

在傳統(tǒng)A*算法啟發(fā)函數(shù)中，g(n)為從起始點開始沿著已計算出的最佳路徑移動到點n的實際代價。對于每個點而言，沿著已計算出的路徑移動，該代價函數(shù)的值是固定不變的，唯一影響候選點值的是h(n)，該函數(shù)表示的是候選點n到目標(biāo)點的估計代價，當(dāng)該函數(shù)越接近實際代價,路徑越接近最佳路徑。針對液氧泄漏的問題,不僅要考慮路徑的長短而且需要考慮路徑的安全性，所以對A*算法改進(jìn)的思路主要有3點：第一點是該算法必須在遠(yuǎn)離泄漏點的安全區(qū)域內(nèi)進(jìn)行搜索；第二點是針對工廠復(fù)雜的地形，對A*算法的啟發(fā)函數(shù)進(jìn)行修改；第三點是為了使得啟發(fā)函數(shù)中h(n)估計代價更接近于實際代價，應(yīng)對啟發(fā)函數(shù)進(jìn)行修改。

3.2 風(fēng)險模型

由于液氧的沸點為-183 ℃，所以液氧泄漏最直接的危害是人體碰觸會發(fā)生凍傷；其次當(dāng)液氧接觸到靜電火花時易發(fā)生爆炸；當(dāng)空氣中氧氣濃度高于23.5%時，為富氧狀態(tài)，此時易產(chǎn)生火災(zāi)，當(dāng)氧氣濃度高于40%時，人體吸入后引發(fā)氧中毒的可能性較大[7]。所以在災(zāi)難發(fā)生時，通過尋路算法找尋最佳逃生路徑時應(yīng)避開這些區(qū)域。爆破能力E計算公式如式(5)所示：

Ew=[(H1-H2)-(S1-S2)T1]W

(5)

它可計算泄漏發(fā)生爆炸時產(chǎn)生的能量。其中Ew表示以kJ為單位的飽和水的爆破能量；H1和H2分別表示爆炸前液化液體的焓以及大氣壓下飽和液體的焓，其單位都是kJ/kg；液氧的H1與H2分別為 -79.84 kJ/kg和-133.69 kJ/kg；S1與S2表示的是爆炸前液化液體的熵以及大氣壓下飽和液體的熵,單位是kJ/(kg·K)；液氧的S1和S2分別為3.44 kJ/(kg·K)與2.94 kJ/(kg·K)[8];T1表示的是介質(zhì)在大氣壓下的沸點，單位為K；W是飽和液體質(zhì)量，單位為kg。得出Ew的值后，即可得出TNT當(dāng)量q(kg)，如式(6)所示：

q=E/qTNT

(6)

液氧槽產(chǎn)生爆炸時的效果與TNT當(dāng)量q的關(guān)系如式(7)所示：

R=r/q1/3

(7)

其中，R表示沖擊波大小(ΔP),表1列出了沖擊波大小對人體的傷害程度。據(jù)此，計算該廠區(qū)密度為1.14×103kg/m2的液氧儲槽發(fā)生泄漏產(chǎn)生爆炸時的安全距離。通過查閱相關(guān)資料可知，對于液氧儲槽發(fā)生泄漏后氧氣濃度高于40%的區(qū)域為30 m內(nèi)的地方[10]。

表1 沖擊波對人體傷害程度

3.3 改進(jìn)算法啟發(fā)函數(shù)

災(zāi)難發(fā)生時,絕對安全區(qū)域是一個范圍而非一個定點，所以最終人物移動到設(shè)定的目標(biāo)點附近即可，因此對于不同路段與時間段人物移動的目的性有細(xì)微差別。在人物遠(yuǎn)離絕對安全區(qū)域前尋路的最主要目的是準(zhǔn)確朝著目標(biāo)點的方向移動，而在離目標(biāo)點較近時尋路的主要目的是迅速移動到絕對安全點附近。由此對傳統(tǒng)的A*尋路算法進(jìn)行修改，在其中加入權(quán)重因子W，從而公式變?yōu)?/p>

f(n)=g(n)+W*h(n)

加入矢量因子的目的在于可以根據(jù)離絕對安全區(qū)域的距離來自行增加或減少向目標(biāo)節(jié)點收斂的速度[11-12]。W=0時，該方法變?yōu)镈ijkstra算法，Dijkstra算法為寬度優(yōu)先的盲目搜索算法，并不適用于場景較大的系統(tǒng)；W<1時，估計值h(n)與實際值相差太遠(yuǎn)，所以采用的W≥1，增大當(dāng)前所在位置與終點之間的距離對f(n)的影響。

傳統(tǒng)A*算法主要針對的是簡單場景的尋路，在3D復(fù)雜場景中需要對啟發(fā)函數(shù)進(jìn)行修改，加入方向因素同時權(quán)衡距離與方向的影響，該改動會使得相鄰的幾個節(jié)點估計代價相同的幾率更小，對減少非必要的回溯有明顯效果，從而提高搜索的精度也加快了搜索進(jìn)程。修改后的公式如式(8)所示：

h(n)=W1*α(ni,nj)+W2*d(nj,ngoal)

(8)

α(ni,nj)表示的是當(dāng)前點與周圍候選點的連線L1與起始點和目標(biāo)點的連線L2之間的夾角值；d(nj,ngoal)表示的是候選點與目標(biāo)點的距離值；W1與W2分別為角度與距離的權(quán)重，W1取值范圍為[0.35，0.45)，W2的取值范圍是(0.55，0.65][13]。在復(fù)雜地形中引入權(quán)重系數(shù)的優(yōu)勢在于權(quán)衡距離信息與方向信息, 加快搜索進(jìn)程。

綜上，修改后的A*啟發(fā)函數(shù)如式(9)所示：

f(n)=g(n)+W(W1*α(ni,nj)+

(1-W1)*d(nj,ngoal))

(9)

改進(jìn)后的A*算法流程圖如圖3所示。

4 實驗結(jié)果對比

在該應(yīng)急演練系統(tǒng)中，利用Unity3D自身所攜帶的坐標(biāo)系統(tǒng)并設(shè)Y坐標(biāo)為0，將整個地形信息以及障礙物信息以點坐標(biāo)的形式存入數(shù)組中，再根據(jù)A*算法和A*改進(jìn)算法的啟發(fā)函數(shù)進(jìn)行實驗。其中障礙物被白色方框圍起來以方便觀察，火焰地方即為泄漏點。

根據(jù)以上所寫內(nèi)容，進(jìn)行對比實驗。實驗分別為根據(jù)實際環(huán)境標(biāo)出障礙物條件下的標(biāo)準(zhǔn)A*算法的尋路路線(圖4)；同樣具備障礙物條件下不考慮風(fēng)險模型A*改進(jìn)算法的尋路路線(圖5)和考慮風(fēng)險模型的A*改進(jìn)算法的尋路路線(圖6)。

圖3 改進(jìn)A*算法流程

圖4 標(biāo)準(zhǔn)A*算法尋路路徑

圖5 不考慮風(fēng)險模型的A*改進(jìn)算法尋路路徑

圖6 考慮風(fēng)險模型的A*改進(jìn)算法尋路路徑

由實驗結(jié)果表明：標(biāo)準(zhǔn)A*算法獲得的逃生路徑(圖4)距離災(zāi)難發(fā)生點的最近距離為18.9 m，逃生路徑節(jié)點中處于爆炸沖擊波和液氧傷害危險的傷害范圍的節(jié)點為79個(表2)。修改A*算法的啟發(fā)函數(shù)后獲得的尋路路徑相較于標(biāo)準(zhǔn)A*算法所獲得的路徑在節(jié)點數(shù)上有所減少，但路徑中仍有較多路點處于危險區(qū)內(nèi)。從實驗結(jié)果可以看出，改進(jìn)A*算法獲得的尋路路線(圖6)完美避開危險區(qū)域，逃生路徑中沒有處于危險區(qū)域內(nèi)的節(jié)點，且距離泄漏點最近的距離為32.3 m(表2)。

表2 處于液氧泄漏危險范圍內(nèi)的節(jié)點個數(shù)

當(dāng)災(zāi)難發(fā)生時為了保護(hù)場內(nèi)員工的生命安全，應(yīng)對標(biāo)準(zhǔn)尋路算法做出如上改進(jìn)，使得可以規(guī)劃出更合理更安全的路線以便員工迅速安全的到達(dá)指定地點。同時，對A*啟發(fā)函數(shù)的修改后獲得的路徑相對于僅考慮風(fēng)險模型的A*算法獲得的路徑回溯更快。