擴展A*算法的火災逃生路徑規劃研究*

程鵬舉，吳 楠，孟凡坤，李 爽

（1.中國人民解放軍戰略支援部隊信息工程大學，河南 鄭州 450000；2.鄭州大學，河南 鄭州 450000）

0 引言

隨著現代城市規模的不斷擴大，大型場館和高層建筑越來越多，且樓層高，結構復雜，人員密集?，F有的消防疏散逃生設備不能根據火災實際情況進行相應的改變，可能會導致逃生人員跑向火情點。因此，當發生火災時，如何智能規劃出有效的逃生路徑對人員進行安全指引，降低火災中人員的傷亡代價是十分有價值的研究[1]。而如何有效引導人員進行疏散逃生涉及到路徑規劃問題，故本文重點研究路徑規劃算法。

目前，有大量的專家學者在路徑規劃領域做了較多研究，包括人工勢場法、A*算法、蟻群算法及粒子群算法等[2]。其中，A*算法具有計算量小、規劃路徑快等特點，但算法的啟發函數考慮維度較簡單，規劃出的路徑容易冗余。文獻[3]在傳統的八角度搜索鄰域基礎上，設計了多角度A*算法，可獲得更短的可行路徑。文獻[4]通過目標性擴展、目標可見性判斷、改變啟發函數以及改變擴展節點選取方略等4 個方面改進A*算法，使算法運行得更快。文獻[5]將A*算法擴展到24 鄰域，使路徑方向具有更多選擇，并融合曼哈頓距離和歐幾里得距離，提高算法的路徑規劃能力。文獻[6]針對多U 型障礙環境，引入鄰域矩陣進行障礙搜索以提升路徑安全性，結合角度信息和分區自適應距離信息改進啟發函數以提高計算效率。以上研究對A*算法的改進提高了算法效率，但都沒有討論算法在某位置存在多個最小代價因固定選取第一個最小代價值而造成路徑曲折的情況。針對此問題，本文提出擴展A*算法。當傳統A*算法在某點處出現多個最小代價值時，假設每個最小值點為下一點，依次對其進行擴展計算，直到找到最小綜合代價值，并選擇此分支為最優路徑。

1 環境建模與算法原理

1.1 環境建模

本文簡化建筑物模型，假設各樓層之間的消防樓梯安全且僅通過此處相互連接，并采用柵格法對各個樓層的環境進行建模[7]。將各樓層二維平面劃分為N×N的地圖，Ni={1,2,3,…,N2}。按照從左至右、從下至上依次編排，分為自由柵格、障礙柵格和火情柵格3 種柵格，人員只能在自由柵格中跑動，模型如圖1所示。柵格圖中，可通行區域設為自由柵格，障礙區域設為障礙柵格，發生火災的區域設為火情柵格，障礙物和火情不足1 格的區域按照1 個柵格計算。

每個柵格中心坐標可表示為：

式中，mod 為求余運算，ceil 表示向后取整數。

圖1 環境柵格示意

本文忽略人流密度、人員情緒以及煙霧濃度等影響，并假設人員的平均逃生速度為單位速度，其在逃生時的運動模型如圖2 所示，即人員每次只能向相鄰的8 個柵格內移動1 格。

圖2 運動鄰域模型

1.2 A＊算法原理

A*算法通過對相鄰8 個節點計算代價值，在進行啟發式搜索提高效率的同時，可以找到一條優化路徑[8]。算法從起點T開始，依次對8 鄰域可通行節點計算啟發代價值，直到找到終點S或進入死胡同或遍歷完所有自由節點[9]。

算法的啟發函數為：

式中：g(n)是從起始點T到節點n的實際代價；h(n)是從節點n到終止點S的估計代價；f(n)為節點n的代價函數[10]。

式中：Li是起始點T到當前點i的實際代價且初始值為0；xn、yn、xi、yi、xS、yS分別為節點n、當前點i和終點S的橫縱坐標值[11]。設立集合close用于存儲已經走過的節點，使其不被再次搜索。算法流程如圖3 所示。

圖3 A*算法流程

2 擴展A＊算法

傳統的A*算法在一定情況下會陷入多個最小代價值的困境，在選取下一點時往往選擇位置靠前的最小代價，不能對多個最小代價值的路徑進行評估后選擇最佳路徑。其中，算法在特定情況出現兩個最小代價點的示意圖如圖4 所示。圖中T、S為起止點，在點i處，其可選下一點為圖中點{1,2,3,4}的位置，其中最小代價點有{3,4}兩點，算法默認選擇靠前的最小代價即點3，規劃出的路徑為A 路徑。相比之下，另一最小代價點即點4，其規劃出的B 路徑轉折少，路徑更短。由此看出，當環境規模較大時，一旦陷入此困境，將使規劃出的路徑曲折往復，大大增加了路徑長度。在火災逃生路徑規劃中，曲折的路徑和較長的路線將大幅增加人員逃生耗時，降低逃生效率。

圖4 兩最小代價點情況

本文針對此困境提出擴展A*算法，在其出現多個最小代價值時依次擴展每個最小值。假設每個最小值點為其下一點，并計算該點鄰域的啟發代價，將得到的最小代價值累加到上一層的代價中，對比其綜合代價，選擇綜合代價最小的路徑。當擴展層最小代價值也相等時，再以此為基礎擴展其下一層，計算其最小代價值，累計到上一層。依次類推，直到最后選擇綜合代價最小的分支。改進后的算法流程如圖5 所示。

3 仿真驗證

為驗證改進后算法的有效性，本文的實驗平臺如下：計算機CPU 為Inter Core i7-8750H（2.2 GHz），內存為8 GB，顯卡為NVIDIA GeForce GTX1050Ti，仿真軟件為MATLAB R2018b。A*算法的啟發距離為歐幾里得距離。

在30×30 的環境地圖中，對傳統A*算法和擴展A*算法進行10 次仿真實驗，結果如表1 所示。表1 中，l1、l2分別表示傳統A*算法和改進后的擴展A*算法規劃出的路徑長度。雖然擴展A*算法在多個最小代價點需要對每個最小值進行擴展計算，增加了計算量，但可以選擇最佳路徑，使路線變短，減少需要計算的路徑點。兩者相互抵消后，從表1的計算時間均值可以看出，兩種算法的計算量相差不大。

圖5 擴展A*算法流程

表1 傳統A＊算法和擴展A＊算法結果比較

從圖6 和圖7 可以看出，算法在圓圈標記的位置出現兩個最小代價點。傳統的A*算法選擇靠前的最小代價，導致規劃出的路徑長且曲折。改進后的擴展A*算法在擴展一層后，其最小代價值依然相等；當經過兩層擴展后，最小代價值不同，最后選擇出綜合代價最小的路徑，規劃出的路徑平滑且大幅縮短了長度。綜合以上結果分析可知，在此環境下，兩種算法的計算時間相差不大，但改進后的擴展A*算法規劃出的路徑縮短了50.7279，降幅約52%，且路線遠離火災區域，更便于人員逃生。實驗表明，改進后的A*算法在多最小代價值位置可以選擇最優分支，可高效地進行路徑規劃。

圖6 傳統A*算法結果

圖7 擴展A*算法結果

4 結語

發生火災時，結合路徑規劃算法的智能逃生指引可大大降低火災中人員傷亡程度。傳統的A*算法計算速度快，但在多最小代價點處固定選取第一個最小代價值容易規劃出較長路徑，不利于人員逃生。針對此問題，本文提出擴展A*算法，在多最小代價點處對每一個最小代價進行擴展計算，并將擴展后的最小代價累加到上一層，以此類推，直到選擇出綜合代價最小的分支，從而使改進算法規劃出的路徑更短。在MATLAB 軟件中對其進行仿真驗證，結果表明，改進后的擴展A*算法規劃出的路徑更短，算法尋優效率更高，應用在火災逃生中可大大提高逃生效率，降低人員傷亡。