多條件約束三維動態(tài)行人疏散路徑優(yōu)化方法

萬 遠，胡 同*，賀 彪，楊 彪

(1. 自然資源部城市國土資源監(jiān)測與仿真重點實驗室，深圳，518034； 2. 湖北師范大學城市與環(huán)境學院，黃石，435002;3. 深圳大學智慧城市研究院，深圳，518061)

0 引言

應急疏散通常包括應急疏散響應、應急資源調(diào)度、撤離人員的疏散[1], 其問題核心是使人們擺脫危險到達安全區(qū)域所需要的時間最小化。有效的疏散路徑規(guī)劃策略不僅可以減少疏散時間的消耗，還能引導人流，緩解局部擁堵，對提高行人疏散效率具有重要意義[2]。因此有效的行人疏散路徑方法成為研究的重要課題。

國內(nèi)外關于人群疏散的研究主要集中在應急疏散模型和路徑優(yōu)化算法等方面，疏散路徑規(guī)劃的研究可分為靜態(tài)規(guī)劃和動態(tài)規(guī)劃[3]。靜態(tài)路徑規(guī)劃問題的研究為疏散分析、逃逸模擬提供了一定的理論指導，大多算法都基于Dijkstra算法[4，5]、Floyd算法[6]、A*算法[7]、RTT*路徑規(guī)劃算法[8]。應用到行人疏散時，用靜態(tài)路徑規(guī)劃來描述行人流自組織現(xiàn)象、微觀行人流和連續(xù)行人路徑選擇序列的決策過程有所欠缺。同時現(xiàn)有的應急疏散多以幾何最短路徑作為行人疏散的路徑選擇依據(jù)，忽略了整體疏散路網(wǎng)的全局效率[9-12]。特別是復雜建筑的室內(nèi)環(huán)境下，發(fā)生事故時盡管有路標的提示，但有效的疏散路徑卻很少，采用傳統(tǒng)疏散模型或路徑規(guī)劃算法進行疏散時易出現(xiàn)“出口拱形”、“快即是慢”等現(xiàn)象，出口利用率不均衡等問題突出，影響整體疏散效率。

關于行人疏散動態(tài)路徑規(guī)劃問題，主要是解決行人路徑動態(tài)選擇的問題，已成為當前研究熱點。Guo等[13]提出一種勢場算法，通過勢場來反映行人對周邊環(huán)境的動態(tài)變化情況，并研究了疏散過程中行人路徑選擇行為；Zong等[14]綜合考慮擁擠、逆行和阻塞時間對疏散速度和行人路徑選擇的影響，提出了一種分層定向人工魚群算法來提高疏散效率；Tang等[15]通過改進網(wǎng)絡疏散模型提出了一種更適合于網(wǎng)絡節(jié)點分配的新算法；文獻[16]利用深度強化學習(DRL)算法模擬行人多出口路徑選擇，提高了出口利用效率；文獻[17]提出了一種可行的視覺區(qū)域劃分算法，研究了局部視野條件下行人的路徑選擇行為；在文獻[18-21]中，研究人員設計了模擬進化算法，充分利用蟻群算法反饋信息機制的快速收斂性來優(yōu)化行人路徑選擇決策機制。

以上研究通過對算法和模型的改進，提高了行人疏散路徑的搜索時間，主要著眼于幾何路徑最短或者運行時間最短，然而實際情況下，一方面，受視域范圍內(nèi)行人數(shù)、行人空間分布格局、視野遮擋程度、行人密度、行人移動方向、目的地方向等環(huán)境約束，所得路徑難以符合行人的微觀行為規(guī)律；另一方面，行人運動具有多維隨機性，而目前對于三維環(huán)境下行人動態(tài)疏散路徑問題和路徑選擇機制的研究很少涉及。因此本文在構建三維行人疏散網(wǎng)絡的基礎上，基于社會力模型，提出了一種路徑尋優(yōu)方法，綜合考慮行人距目的地距離、路徑方向、視域范圍內(nèi)行人數(shù)、行人密度、視域空曠度等多條件約束，使用多目標蟻群算法[22，23]改進的社會力模型得到適合行人疏散的最優(yōu)路徑。同時通過構建路徑選擇機制仿真模擬行人在疏散過程中能夠根據(jù)周邊環(huán)境進行路徑選擇的動態(tài)調(diào)整。該算法平衡了各出口利用效率，提高了整體疏散效率。通過該算法模擬實驗，本文所提出的路徑尋優(yōu)方法能更好應用于三維行人疏散環(huán)境。

1 三維行人疏散網(wǎng)格模型

疏散路徑的優(yōu)化問題是行人疏散問題的關鍵。本文受Guo等[24]和Zhu等[25]元胞自動機模型的啟發(fā)構建了三維行人疏散網(wǎng)格模型，如圖1和圖2。利用空間離散網(wǎng)格來提高行人對疏散環(huán)境的判斷和感知，以提高整體疏散效率為目標，通過蟻群算法來激發(fā)路徑選擇機制，確保行人在每個仿真步長中有最優(yōu)的社會環(huán)境力，以及最優(yōu)的疏散速度和運動方向。

為研究三維疏散網(wǎng)絡，本文先討論二維元胞自動機模型，以此拓展到三維空間。首先將行人疏散環(huán)境離散化為二維網(wǎng)格模型如圖1，其中每個網(wǎng)格的狀態(tài)定義為“行人占據(jù)點”、“靜態(tài)障礙點”、“危險點”、“未被占據(jù)點”。疏散過程中人群的移動軌跡與網(wǎng)格相對應，若行人i位于某網(wǎng)格中時，周圍的8個區(qū)域都可以作為下一時刻的可選疏散位置。

對于二維網(wǎng)格模型，在垂直方向上增加一維獲取三維行人疏散網(wǎng)格模型如圖2，定義：三維空間是均勻劃分為n×n×n(n為大于3的正整數(shù))個等長的單位網(wǎng)格，并從上到下、從左到右進行唯一編碼；網(wǎng)格單元作為路徑規(guī)劃中最小移動單位；網(wǎng)格單元的坐標由中心點位置確定。如圖2行人位于3×3×3的三維空間網(wǎng)格中央格子，此時空間分為三層：平面層、上層空間和下層空間。在三維空間內(nèi)行人總共有10個自由運動方向，包括二維平面上的8個方向和向上向下2個空間移動方向。其中疏散方向與二維模型一致，取決于兩個網(wǎng)格之間的信息素濃度和啟發(fā)函數(shù)值。

圖1 二維網(wǎng)格模型Fig. 1 Two-dimensional grid model

圖2 三維網(wǎng)絡模型Fig. 2 Three-dimensional grid model

三維行人疏散解空間如式(1)所示：

(1)

P為三維網(wǎng)格模型中的網(wǎng)格號；x、y、z為網(wǎng)格P對應的三維坐標；n為空間網(wǎng)格單元，f為建筑物底層，c為建筑物頂層。同時假設三維空間構成的網(wǎng)格集合為G, 行人在疏散過程中的運動軌跡與網(wǎng)格一一對應，通過三維解空間可以解算出行人在t時刻下的坐標位置Pi(t)。

2 行人疏散模型

在疏散網(wǎng)格的基礎上，對疏散過程中行人在周邊多條件環(huán)境約束下做出的反饋進行微觀分析。

2.1 社會力模型分析

1995年，Helbing和Molnar[26]觀察到行人在逃生過程中會與障礙物、其他人保持一定的距離，基于牛頓力學公式和行人逃生運動狀態(tài)提出了社會力模型，它作為一種連續(xù)型微觀仿真模型，在研究行人運動中具有重要地位。該模型將行人個體視為粒子，在逃生活動中，個體之間及個體與環(huán)境之間的非線性相互作用共同制約個體的行為活動。在疏散環(huán)境中，行人主要受到自身驅動力fi、行人與行人之間的作用力fij、行人與障礙物之間的作用力fiw的共同影響，三者共同驅動行人連續(xù)運動。社會力模型數(shù)學表達式為：

(2)

(3)

+κg(ri-diw)(vi·tiw)tiw

(4)

(5)

Helbing社會力模型在描述一些大型群體疏散中能很好地展現(xiàn)行人疏散過程中的“瓶頸現(xiàn)象”、“快即是慢”、“碰撞擠壓”等行人疏散特征，但是也存在一些問題。例如模型中所有行人對行人i的作用力變化是相同的，但在實際情況中行人i視域范圍內(nèi)的行人相對于視域范圍外的行人影響更大，比如行人會與視野前面的人保持距離而忽略背后的人；同時社會力模型將行人期望速度視為常量，實際上行人在疏散過程期望速度是不斷變化的，比如行人自身恐慌程度、視域范圍內(nèi)行人數(shù)、行人空間分布格局、距目標地遠近等都會造成行人期望速度的變化，進而影響行人進行路徑和方向的選擇。

3 路徑選擇與優(yōu)化機制

在社會力模型中，行人的運動軌跡受目的地位置、期望速度、移動方向的影響。由于后方行人被前方行人擋住視野，如果此時依然以恒定的期望速度向目標地移動勢必會出現(xiàn)“鎖死”和激烈的碰撞事故。鑒于社會力模型出現(xiàn)的以上問題，以及為了更好地應用于三維疏散場景，本文創(chuàng)建了路徑選擇與優(yōu)化機制。

3.1 臨時目標地節(jié)點

圖3 臨時目標地與空間分層Fig. 3 Temporary destination and spatial stratification

3.2 行人視域分析

在實際疏散場景中，水平方向上行人的視域范圍是有限的。行人更加關注視域范圍內(nèi)其他行人的運動狀態(tài)、行人數(shù)量、位置分布等情況，進而影響行人對移動方向、移動速度等路徑選擇的判斷。

3.2.1 視域范圍與視域空曠度

(6)

其中向量集合X可以通過行人位置函數(shù)計算，在集合Xe中,行人期望移動方向為Ln與Ln+1最大夾角的角平分線指向臨時目標地的方向。通過向量角平分線原理計算可得，此處不再贅述。

圖4 視域范圍示意圖1Fig. 4 Field of view 1

圖5 視域范圍示意圖2Fig. 5 Field of view 2

圖6 視域空曠度Fig. 6 Visual field visibility

在行人路徑選擇中，行人通過判斷視域范圍內(nèi)格子的權重來做出下一步的路徑選擇，視域空曠度越大，行人選擇該格子移動的概率越大。

3.3 行人離臨時目標地距離與行人密度

(7)

(8)

其中ρ為視域行人密度。

3.4 視域范圍內(nèi)行人數(shù)

(9)

其中，

(10)

綜上，行人i候選網(wǎng)格m的權重記為：

(11)

4 改進社會力模型三維行人疏散策略

三維疏散環(huán)境中，行人選擇臨時目標地或出口時，受多條件約束，行人可能會放棄距離較近的臨時目標地或出口而選擇相對空閑、行人密度低、人數(shù)少的出口。在三維行人疏散網(wǎng)格模型的基礎上，考慮每個網(wǎng)格對于行人i的選擇權重，不同路徑的疏散機制也不同，本文主要考慮：視域空曠度、行人到臨時目標地的距離、行人密度、視域范圍內(nèi)行人數(shù)等因素，通過多目標蟻群算法改進社會力模型，提出一種新的路徑優(yōu)化算法，改進行人路徑選擇機制從而得到最優(yōu)疏散路徑。一般來講，行人在疏散場景中傾向于向視域空曠度高、距離目的地近、行人密度低、視域范圍內(nèi)行人數(shù)少的方向移動。

4.1 基于蟻群算法優(yōu)化路徑

蟻群算法具有強大的全局搜索能力，在各種優(yōu)化問題上取得不錯的效果[30，31]。

(12)

其中ξi(t)表示節(jié)點在t時刻信息素數(shù)量，ηi(t)表示啟發(fā)函數(shù)，一般為兩節(jié)點之間距離的倒數(shù),ηi(t)=1/dij；a為信息素濃度因子；b為啟發(fā)因子；GK為當前節(jié)點i在下一步可到達節(jié)點的集合。

下一步先處理啟發(fā)函數(shù)。本文使用行人期望移動方向與臨時目標地的方向的夾角作為啟發(fā)函數(shù)，例如圖6向量L0與期望移動方向的夾角為h,h越小表示臨時目標地期望越大。因此定義啟發(fā)函數(shù)為：

ηi(t)=eμcos(h)

(13)

其中μ為控制系數(shù)。

(14)

其中，ψ1,ψ2,ψ3為3種優(yōu)化目標的權重，ψ1+ψ2+ψ3=1。由于量綱不同，進行單位化處理后可轉化為：

(15)

則使用單位化后的解A′更新信息素公式為：

(16)

(17)

式中，c為信息素揮發(fā)程度，Q是信息素總量。

4.2 算法步驟

根據(jù)上述條件求解模型，(1)根據(jù)三維行人疏散網(wǎng)格模型計算各網(wǎng)格點坐標。(2)蟻群算法初始化，設置相關參數(shù)，見表1、表2和表3。(3)記錄找到終點的螞蟻并更新每只成功螞蟻路徑上的信息素。(4)重復步驟，直到遍歷所有節(jié)點。(5)輸出每次迭代中螞蟻V值和路徑直到路徑不發(fā)生明顯變化。

表1 社會力模型參數(shù)設置參考

表2 蟻群算法參數(shù)設置參考

表3 實驗區(qū)參數(shù)設置

5 實驗與結果分析

本文以黃石市民之家為實驗區(qū)域，通過 CAD數(shù)據(jù)構建三維行人疏散網(wǎng)格，如圖7，每個網(wǎng)格大小為0.5 m×0.5 m，范圍為20 m×10 m，建筑層高3 m，在樓梯(疏散過程中暫不考慮電梯情況)等關鍵位置設置臨時目標地節(jié)點。如圖10和圖11：在二、三樓樓梯處設置臨時目標地節(jié)點，編號為5～20，在一樓處有四個出口，設置為終點目的地，編號為1～4，如圖8，其中1號出口為主出口。實驗選取2 200人，隨機離散分布于三層樓三維空間中，其分布特性服從泊松概率分布。分別利用原始蟻群算法和本文的路徑優(yōu)化算法得到相應的路徑，并通過行人數(shù)量與時間關系圖對比分析疏散效率，圖9為總體疏散人數(shù)與時間的關系；優(yōu)化前后各出口處人數(shù)與疏散時間關系如圖12～圖15；同時記錄出口處行人密度情況如圖16～圖17，行人疏散過程場景展示如圖18。

圖7 黃石市民之家三維行人疏散網(wǎng)格Fig. 7 3D Pedestrian evacuation grid of Huangshi citizen’s home

圖8 黃石市民之家一樓Fig. 8 First floor of Huangshi citizen’s home

圖9 總體疏散人數(shù)與時間Fig.9 Total evacuation pedestrians and time

圖10 黃石市民之家二樓Fig. 10 Second floor of Huangshi citizen’s home

圖11 黃石市民之家三樓Fig. 11 Third floor of Huangshi citizen’s home

圖12 優(yōu)化前后1號出口Fig. 12 Exit 1 before and after optimization

圖13 優(yōu)化前后2號出口Fig. 13 Exit 2 before and after optimization

圖14 優(yōu)化前后3號出口Fig. 14 Exit 3 before and after optimization

圖15 優(yōu)化前后4號出口Fig. 15 Exit 4 before and after optimization

圖16 未優(yōu)化路徑各出口密度Fig. 16 The density of each exit of the unoptimized path

圖17 優(yōu)化路徑后各出口密度Fig. 17 The density of each exit of the optimized path

5.1 行人疏散時間

圖9為未優(yōu)化蟻群算法所得的疏散時間，由于行人均采取最短的路徑策略進行疏散，在100 s～150 s處曲線趨于平緩，從圖16中可看出1號出口行人密度在此處激增，造成行人通行效率很低，出現(xiàn)“快即是慢”和主出口“瓶頸現(xiàn)象”嚴重。這導致疏散時間較長，耗時496 s才能將所有人員疏散到安全位置。采用本文尋優(yōu)方法獲得的路徑，由于引入路徑選擇與優(yōu)化機制，更新了啟發(fā)函數(shù)信息素，考慮了社會環(huán)境力和行人微觀特性對行人路徑選擇的影響，當出口人數(shù)達到一定程度時行人不會按既定路徑疏散而是在總體上朝著出口方向進行運動的同時會根據(jù)周邊環(huán)境實時動態(tài)調(diào)整。利用所得最優(yōu)路徑進行疏散時，提升了疏散效率，疏散耗時408 s。結果表明，經(jīng)過仿真模擬對比，采用本文算法總體疏散效率提高了17.74%。

5.2 出口處人數(shù)

從圖12～圖15中可以看出，出口1在262 s后擁堵人數(shù)總量整體下降，主要是優(yōu)化后的路徑使行人在出口選擇上趨于動態(tài)平衡，避免了主出口載荷過大超過節(jié)點容量出現(xiàn)擁擠和碰撞。雖然其他出口集聚人數(shù)有所增加，但主出口“瓶頸現(xiàn)象”緩解，提高了行人整體疏散效率。

5.3 出口處密度

從圖16中可以看出采用未優(yōu)化路徑進行疏散時，在出口1處擁堵情況明顯，在300 s～420 s時尤為顯著，出口1處行人密度一直保持較大狀態(tài)，此時段密度平均高達2.21人/m2，嚴重影響疏散效率和出口利用率。而采用優(yōu)化路徑后進行疏散時，雖然1-3出口密度有所上升，但是出口1行人密度變化很大，比未優(yōu)化時平均下降19.8%。

圖18 行人疏散過程Fig. 18 The process of pedestrian evacuation

6 結論

(1)本文提出的多條件約束三維動態(tài)行人疏散路徑優(yōu)化方法能夠平衡考慮路徑距離、行人視域、行人運動方向、行人密度等社會環(huán)境力和行人自身因素的影響，更多考慮了微觀行人運動規(guī)律，滿足實際路徑優(yōu)化需求。

(2)本文在構建三維行人疏散網(wǎng)絡的基礎上，通過多目標蟻群算法改進社會力模型，改進行人路徑選擇機制，使行人能根據(jù)社會環(huán)境力進行路徑動態(tài)選擇，與原始蟻群算法相比，本文的模型算法平衡了各出口利用率，提高了整體疏散效率，更適用于行人疏散路徑優(yōu)化問題。

(3)本文算法對于解決室內(nèi)多出口行人疏散的路徑優(yōu)化問題、出口處瓶頸問題以及研究行人流微觀規(guī)律和行人行為決策機理具有一定的參考意義，為建立突發(fā)事件下的三維行人疏散提供新的思路和方案。