改進A*的高層建筑逃生路徑規劃算法研究

靳海亮，王贏樂，袁 鳴，陳夢龍

(1. 河南理工大學測繪與國土信息工程學院，河南 焦作 454000； 2. 河南省遙感測繪院，河南 鄭州 450003； 3. 河南省測繪工程院，河南 鄭州 450003 )

隨著經濟的發展及科技水平的提高，城市中高層建筑不斷涌現，在提高土地利用率、節約市政成本的同時，也帶來了一些安全隱患。如在火災發生時，由于高層建筑內部空間結構和逃生通道的限制，在沒有合理疏散引導的情況下，短時間內建筑內部人員將快速向樓梯間移動，從而導致人員疏散速度大幅下降，二次事故發生概率劇增[1]。因此，在火災發生時結合計算機技術制訂合理的逃生路徑規劃方案尤為必要。

目前，中外學者在這一領域已經開展了研究，取得了一些成果。如文獻[2]針對大型建筑或船舶發生火災時人員疏散問題，通過對火勢蔓延、二氧化碳濃度、煙塵濃度等因素的研究，基于蟻群算法提出了火災場景中的逃生路徑規劃方法。文獻[3]針對危機發生時受災人員因恐慌、焦慮等因素影響而導致的疏散效率低下的問題，基于代理人基模型對人行為的異質性和人與環境的相互作用進行了研究，在此基礎上提出了考慮行人行為和多種路徑策略的疏散方案。文獻[4]考慮環境因素在A*算法基礎上提出了一種優化的建筑火災逃生算法。文獻[5]針對應急疏散中多約束條件下進行合理路徑規劃問題，基于對Dijkstra算法的改進實現了疏散總時間最短的路徑規劃優化算法的設計。文獻[6]在研究靜態路徑規劃算法的基礎上將A*算法引入室內靜態路徑規劃，并實現了基于智能手機平臺的APP軟件。文獻[7]針對傳統的基于節點的拓撲模型無法較好解決室內空間“路網”的模糊性問題，提出將基于Delaunay三角剖分導航網格的A*算法應用于室內導航路徑規劃中。文獻[8]針對大型樓宇內部逃生路徑規劃問題，綜合對比了經典路徑規劃算法的優劣并闡述了其在樓宇內部逃生疏散場景應用的算法思想和主要特征。文獻[9]在對傳統路徑規劃算法研究的基礎上，對A*算法結構進行了優化，提高了算法的效率。

雖然學者們結合環境因素和人行為因素完善了高層建筑逃生路徑規劃算法的約束條件，或通過改進算法結構提高了算法效率，但在疏散過程中疏散效率隨人員密度增加而降低的問題并沒有得到有效解決[10]，擁堵問題仍會出現。因此，本文針對該問題在對A*算法進行改進的基礎上提出一種逃生路徑規劃算法，旨在提高逃生疏散過程中的疏散效率，保證逃生路徑的通暢性。

1 A*算法

1.1 基本原理

A*算法是一種在靜態路網中求解最短路徑的有效的直接搜索方法，它通過估價函數包含的啟發信息快速鎖定目標方向[11-13]。估價函數的計算方式如下

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

(1)

式中，f(n)代表從起點經過節點n到終點的估計代價；g(n)代表從起點到節點n的真實代價；h(n)為啟發函數，代表從節點n到終點的啟發式預計代價[8,11]。求解最短路徑時，以距離為代價進行估價函數的計算。A*算法在執行過程中，將路徑搜索場景以規則格網(本文以正方形格網為例)的形式進行分割，每1個格網代表1個節點。如圖1所示，算法開始時首先引入兩個集合，即開啟列表(用于存儲滿足估價函數限定條件待遍歷的節點，OpenList)和關閉列表(存儲已經過遍歷并不再進行遍歷的點，CloseList)。在路徑搜索過程中，以當前節點周圍8個方向的鄰接節點為擴展對象加入開啟列表中，從中選擇f(n)最小的格網移出開啟列表并加入關閉列表中。以此類推，不斷對節點進行擴展，當找到目標節點時完成路徑規劃。

1.2 算法分析

與Dijkstra算法和Flyod算法的暴力搜索方式不同，A*算法在執行過程中不需要對所有節點進行遍歷，因此算法運行效率可有效提高。同時算法增加了約束條件，可針對不同應用環境制定路徑規劃策略，提高了算法的可擴展性。

但是，將A*算法直接運用在高層建筑逃生路徑規劃中時，仍然會出現以下問題：①逃生路徑規劃時直接設置逃生終點不利于人員的分流疏散，因此應結合逃生起點與火災發生位置的距離合理規劃逃生終點；②逃生路徑規劃過程中僅僅注重距離最短是不可取的，短時間內的人員快速聚集會導致疏散效率降低，因此還應綜合更多因素為節點擴展提供評估條件，以提高逃生路徑的通暢性；③節點擴展過程中如果直接對樓層平面進行格網劃分，會造成冗余，降低算法效率，因此應結合樓層平面布局有針對性地進行分割。

2 高層建筑逃生路徑規劃算法設計與實現

2.1 算法改進

2.1.1 逃生終點優化分配

為了充分利用逃生通道，實現逃生過程中的分流疏散并降低擁堵現象發生概率，本文在進行路徑搜索前，首先根據火災發生的位置信息，按照與火災位置的樓層距離對高層建筑樓層進行危險等級劃分。主要劃分成危險、威脅、暫時安全3個等級。針對不同危險等級，確定不同的逃生目標點，實現逃生人員的分流。

本文對樓層危險等級劃分做出以下規定：①火災發生樓層的危險等級設置為危險；②火災發生樓層上下兩層距離內的樓層危險等級設置為威脅；③在危險、威脅區域以外的樓層危險等級設置為暫時安全。算法執行時，首先根據起火位置對樓層進行危險等級劃分，然后判斷逃生起點的危險等級信息，針對不同危險等級設置對應的逃生終點，實現分流疏散。

2.1.2 節點擴展優化

為了提高逃生路徑規劃算法運行效率，本文對節點擴展過程進行了優化。根據高層建筑樓層平面布局，借鑒拓撲結構思想對房間、走廊、樓梯間等進行抽象，忽略形狀大小的影響，用節點表示房間、樓梯間、走廊等關鍵點，用線段表示逃生路徑，構造高層建筑內部路網拓撲結構。在保證高層建筑內部路網基本特征的前提下減少對非必要節點的遍歷，降低節點擴展時鄰接點的數量，提高算法運算效率。改進后的節點擴展如圖2所示。

算法通過該方式進行節點擴展時，首先排除已經存在于CloseList和OpenList中的節點及障礙節點，然后對鄰接節點進行遍歷并尋求滿足權值的節點加入OpenList中。算法執行過程中不再從8個方向獲取鄰接節點信息，只對具備拓撲鄰接關系的節點進行遍歷，有效提高了節點擴展效率，同時節點擴展也實現了在三維空間中的延伸(如圖2(a)、(b)所示)。

2.1.3 權值優化

影響高層建筑逃生的因素主要分為以下3個方面：①火災發生的狀態，包括火災發生位置、火災蔓延速度、煙氣濃度等；②高層建筑內人員狀態，包括人員數量、人員分布、人員移動速度、人員密度等；③高層建筑內部特征，包括走廊寬度、疏散關鍵點分布等[13]。本文主要依據影響疏散效率的相關因素選用以下5個方面內容作為路徑規劃的權重并記錄在屬性表中。

(1) 火災位置。火災位置是影響逃生路徑規劃的主要因素之一，它直接影響逃生策略的制定。火災位置在算法中以路網節點屬性進行存儲，包括空間坐標及樓層信息。本文主要通過火災位置實現高層建筑內樓層危險等級的劃分。

(2) 人員數量與分布。作為逃生的主體，人員數量與分布直接影響逃生路徑的走向，同時也是權值計算的主要內容。人員數量是指火災發生時樓內各個路網節點對應人員數量；人員分布主要記錄各個樓層人數及位置分布。在算法中人員數量及其分布主要通過路網節點對應人數屬性進行存儲，通過路網節點對應空間坐標實現人員分布控制。

(3) 走廊面積。走廊面積由走廊長度和寬度決定，一般情況下，走廊面積與逃生過程中疏散效率成正比，走廊面積越大，逃生過程中疏散效率就會越高；反之，疏散效率越低。本文主要通過記錄走廊長度和寬度實現走廊面積計算，在算法中計算走廊面積對應的長寬均由固定值表示。

(4) 人員密度。人員密度是逃生路徑規劃的關鍵影響因素，本文采用單位面積內人員的數量表示人員密度。算法中人員密度由路網節點對應人員密度屬性存儲，通過人員數量與走廊面積之比進行表示，用于節點擴展過程中估價函數h(n)的計算。

(5) 路網節點分布信息。路網節點分布信息用于描述各樓層房間分布信息及樓層與樓層之間逃生出口信息，它為火災發生時人員的疏散引導提供指南。本文以空間坐標和節點類型的方式記錄各路網節點的相關信息。

2.2 算法數據結構設計

根據前述路徑規劃權值的內容，算法的數據結構設計如下：

Struct NodeNet

{

private string nodeName; ∥記錄節點名稱

private string nodeType; ∥記錄節點類型，主要分為房間節點、走廊節點、樓梯節點、電梯節點

private Point fatherNode;∥記錄節點的父節點

private Point neibor;∥記錄節點鄰接節點

private int dangerousLevel;∥節點對應危險等級，危險為2，威脅為1，暫時安全為0

private int floor;∥記錄節點對應樓層信息

private int X;∥記錄節點位置信息

private int Y;

private int Z;

private int count;∥記錄節點對應人數信息

private double G;∥從上一節點到當前節點的真實代價

private double H;∥啟發函數計算值

private double F;∥估價函數計算值

private double density;∥記錄節點對應人員密度

}

2.3 算法步驟

改進后的算法步驟如下：

(1) 輸入路網數據G、起火點位置信息F、樓內總人數集合C及逃生起點S。

(2) 根據起火點F劃分各樓層危險等級，判斷起點S所在樓層的危險等級，如果為危險，轉至步驟(3)；如果為威脅，轉至步驟(4)；如果為暫時安全，轉至步驟(5)。

(3) 設置起點S對應路徑搜索目標點E1為最近安全樓層消防電梯節點。

(4) 設置起點S對應路徑搜索目標點E2為危險樓層人員疏散完畢后消防電梯節點。

(5) 設置起點S對應路徑搜索目標點E3為大樓出口節點。

(6) 將起點S加入開啟列表中，設置S為當前節點，根據拓撲關系獲得當前節點對應鄰接節點，并加入開啟列表中，設置父節點為當前節點。

(7) 將當前節點從開啟列表中移出，加入關閉列表中。

(8) 遍歷開啟列表，進行如下判斷：判斷該點是否為障礙點，若該點是障礙點，則跳過該點；若該點不是障礙點，選擇f(n)值最小的點S1，h(n)值最小的點S2。對S1和S2作如下判斷：若S1對應h(n)值小于S2對應的h(n)值，則將S1加入開啟列表中，并設置S1為當前節點；若S1對應h(n)值大于S2對應的h(n)值，則將S2加入開啟列表中，并設置S2為當前節點。

(9) 重復步驟(6)—(8)，當路徑搜索目標點存在于開啟列表時，根據節點對應父節點返回路徑信息，輸出路徑節點并繪制在計算機屏幕上。

高層建筑逃生路徑規劃算法流程如圖3所示。

3 算法復雜度分析

假設路網中有n個節點，每個節點有k個鄰接節點。完成路徑求解需要以下幾個過程：首先對n個節點的危險等級進行劃分，對應時間復雜度為O(n)；其次確定當前節點危險等級，對應時間復雜度為O(1)；然后對鄰接節點進行遍歷向逃生終點靠近，考慮最壞的情況，需要遍歷的鄰接節點個數是4個(A*算法則需要遍歷8個鄰接節點)，對應時間復雜度為O(k2)(k≤4)；最后返回路徑規劃結果，對應時間復雜度為O(n)。因此改進后算法的時間復雜度為O(n+k2)，雖然與A*算法的時間復雜度一致，但降低了鄰接點遍歷次數，因此算法運行效率明顯提高。

4 試驗驗證

本文選取某高層建筑為試驗對象，對該建筑進行路網數據收集，其路網數據如圖4所示。基于Visual Studio 2010開發環境使用C#編程語言結合EV-Globe SDK二次開發包實現了高層建筑逃生路徑規劃算法，并與A*算法進行了對比。算法效果如圖5所示，其中圖5(a)為算法改進前的路徑規劃效果，圖5(b)為算法改進后的逃生路徑規劃效果。

通過算法的實現效果可以看出，改進后的算法根據不同區域的危險等級進行了有針對性的路徑規劃，同時考慮了人員密度、人員數量等因素，在逃生路徑規劃過程中不再一味追求距離最短，而更多地考慮了路徑的通暢性。

5 結 語

本文針對高層建筑內部結構復雜、沒有疏散引導的情況，以及逃生過程中疏散效率降低的問題，對A*算法進行改進，提出了適用于高層建筑的逃生路徑規劃算法。該算法通過對終點的優化分配、節點擴展的優化及權值優化3個方面的改進，實現了高層建筑內部的分流疏散，保證了逃生路徑的通暢性。