靳海亮，王贏樂，袁 鳴，陳夢(mèng)龍

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

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

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

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

1 A*算法

1.1 基本原理

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

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

(1)

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

1.2 算法分析

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

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

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

2.1 算法改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Struct NodeNet

{

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

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

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

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

private int dangerousLevel;∥節(jié)點(diǎn)對(duì)應(yīng)危險(xiǎn)等級(jí)，危險(xiǎn)為2，威脅為1，暫時(shí)安全為0

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

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

private int Y;

private int Z;

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

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

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

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

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

}

2.3 算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

4 試驗(yàn)驗(yàn)證

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

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

5 結(jié) 語

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