改進(jìn)A*的高層建筑逃生路徑規(guī)劃算法研究

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

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

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

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

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

1 A*算法

1.1 基本原理

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

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

(1)

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

1.2 算法分析

與Dijkstra算法和Flyod算法的暴力搜索方式不同，A*算法在執(zhí)行過程中不需要對所有節(jié)點進(jìn)行遍歷，因此算法運行效率可有效提高。同時算法增加了約束條件，可針對不同應(yīng)用環(huán)境制定路徑規(guī)劃策略，提高了算法的可擴(kuò)展性。

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

2 高層建筑逃生路徑規(guī)劃算法設(shè)計與實現(xiàn)

2.1 算法改進(jìn)

2.1.1 逃生終點優(yōu)化分配

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

本文對樓層危險等級劃分做出以下規(guī)定：①火災(zāi)發(fā)生樓層的危險等級設(shè)置為危險；②火災(zāi)發(fā)生樓層上下兩層距離內(nèi)的樓層危險等級設(shè)置為威脅；③在危險、威脅區(qū)域以外的樓層危險等級設(shè)置為暫時安全。算法執(zhí)行時，首先根據(jù)起火位置對樓層進(jìn)行危險等級劃分，然后判斷逃生起點的危險等級信息，針對不同危險等級設(shè)置對應(yīng)的逃生終點，實現(xiàn)分流疏散。

2.1.2 節(jié)點擴(kuò)展優(yōu)化

為了提高逃生路徑規(guī)劃算法運行效率，本文對節(jié)點擴(kuò)展過程進(jìn)行了優(yōu)化。根據(jù)高層建筑樓層平面布局，借鑒拓?fù)浣Y(jié)構(gòu)思想對房間、走廊、樓梯間等進(jìn)行抽象，忽略形狀大小的影響，用節(jié)點表示房間、樓梯間、走廊等關(guān)鍵點，用線段表示逃生路徑，構(gòu)造高層建筑內(nèi)部路網(wǎng)拓?fù)浣Y(jié)構(gòu)。在保證高層建筑內(nèi)部路網(wǎng)基本特征的前提下減少對非必要節(jié)點的遍歷，降低節(jié)點擴(kuò)展時鄰接點的數(shù)量，提高算法運算效率。改進(jìn)后的節(jié)點擴(kuò)展如圖2所示。

算法通過該方式進(jìn)行節(jié)點擴(kuò)展時，首先排除已經(jīng)存在于CloseList和OpenList中的節(jié)點及障礙節(jié)點，然后對鄰接節(jié)點進(jìn)行遍歷并尋求滿足權(quán)值的節(jié)點加入OpenList中。算法執(zhí)行過程中不再從8個方向獲取鄰接節(jié)點信息，只對具備拓?fù)溧徑雨P(guān)系的節(jié)點進(jìn)行遍歷，有效提高了節(jié)點擴(kuò)展效率，同時節(jié)點擴(kuò)展也實現(xiàn)了在三維空間中的延伸(如圖2(a)、(b)所示)。

2.1.3 權(quán)值優(yōu)化

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

(1) 火災(zāi)位置?；馂?zāi)位置是影響逃生路徑規(guī)劃的主要因素之一，它直接影響逃生策略的制定?；馂?zāi)位置在算法中以路網(wǎng)節(jié)點屬性進(jìn)行存儲，包括空間坐標(biāo)及樓層信息。本文主要通過火災(zāi)位置實現(xiàn)高層建筑內(nèi)樓層危險等級的劃分。

(2) 人員數(shù)量與分布。作為逃生的主體，人員數(shù)量與分布直接影響逃生路徑的走向，同時也是權(quán)值計算的主要內(nèi)容。人員數(shù)量是指火災(zāi)發(fā)生時樓內(nèi)各個路網(wǎng)節(jié)點對應(yīng)人員數(shù)量；人員分布主要記錄各個樓層人數(shù)及位置分布。在算法中人員數(shù)量及其分布主要通過路網(wǎng)節(jié)點對應(yīng)人數(shù)屬性進(jìn)行存儲，通過路網(wǎng)節(jié)點對應(yīng)空間坐標(biāo)實現(xiàn)人員分布控制。

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

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

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

2.2 算法數(shù)據(jù)結(jié)構(gòu)設(shè)計

根據(jù)前述路徑規(guī)劃權(quán)值的內(nèi)容，算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計如下：

Struct NodeNet

{

private string nodeName; ∥記錄節(jié)點名稱

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

private Point fatherNode;∥記錄節(jié)點的父節(jié)點

private Point neibor;∥記錄節(jié)點鄰接節(jié)點

private int dangerousLevel;∥節(jié)點對應(yīng)危險等級，危險為2，威脅為1，暫時安全為0

private int floor;∥記錄節(jié)點對應(yīng)樓層信息

private int X;∥記錄節(jié)點位置信息

private int Y;

private int Z;

private int count;∥記錄節(jié)點對應(yīng)人數(shù)信息

private double G;∥從上一節(jié)點到當(dāng)前節(jié)點的真實代價

private double H;∥啟發(fā)函數(shù)計算值

private double F;∥估價函數(shù)計算值

private double density;∥記錄節(jié)點對應(yīng)人員密度

}

2.3 算法步驟

改進(jìn)后的算法步驟如下：

(1) 輸入路網(wǎng)數(shù)據(jù)G、起火點位置信息F、樓內(nèi)總?cè)藬?shù)集合C及逃生起點S。

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

(3) 設(shè)置起點S對應(yīng)路徑搜索目標(biāo)點E1為最近安全樓層消防電梯節(jié)點。

(4) 設(shè)置起點S對應(yīng)路徑搜索目標(biāo)點E2為危險樓層人員疏散完畢后消防電梯節(jié)點。

(5) 設(shè)置起點S對應(yīng)路徑搜索目標(biāo)點E3為大樓出口節(jié)點。

(6) 將起點S加入開啟列表中，設(shè)置S為當(dāng)前節(jié)點，根據(jù)拓?fù)潢P(guān)系獲得當(dāng)前節(jié)點對應(yīng)鄰接節(jié)點，并加入開啟列表中，設(shè)置父節(jié)點為當(dāng)前節(jié)點。

(7) 將當(dāng)前節(jié)點從開啟列表中移出，加入關(guān)閉列表中。

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

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

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

3 算法復(fù)雜度分析

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

4 試驗驗證

本文選取某高層建筑為試驗對象，對該建筑進(jìn)行路網(wǎng)數(shù)據(jù)收集，其路網(wǎng)數(shù)據(jù)如圖4所示?；赩isual Studio 2010開發(fā)環(huán)境使用C#編程語言結(jié)合EV-Globe SDK二次開發(fā)包實現(xiàn)了高層建筑逃生路徑規(guī)劃算法，并與A*算法進(jìn)行了對比。算法效果如圖5所示，其中圖5(a)為算法改進(jìn)前的路徑規(guī)劃效果，圖5(b)為算法改進(jìn)后的逃生路徑規(guī)劃效果。

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

5 結(jié) 語

本文針對高層建筑內(nèi)部結(jié)構(gòu)復(fù)雜、沒有疏散引導(dǎo)的情況，以及逃生過程中疏散效率降低的問題，對A*算法進(jìn)行改進(jìn)，提出了適用于高層建筑的逃生路徑規(guī)劃算法。該算法通過對終點的優(yōu)化分配、節(jié)點擴(kuò)展的優(yōu)化及權(quán)值優(yōu)化3個方面的改進(jìn)，實現(xiàn)了高層建筑內(nèi)部的分流疏散，保證了逃生路徑的通暢性。