基于模糊規(guī)則和BFS算法的行人疏散模型研究*

翟龍真，馮紹紅，文 哲，王 迪

(1.南京航空航天大學(xué) 經(jīng)濟與管理學(xué)院，江蘇 南京 211100；2.東南大學(xué) 儀器科學(xué)與工程學(xué)院，江蘇 南京 210096)

0 引言

隨著國家現(xiàn)代化、城市化水平的顯著提高，各類大型活動中心以及交通樞紐等場所的高密度聚集活動愈加頻繁。而突發(fā)事件導(dǎo)致的嚴(yán)重危害使人群安全問題日益突出。因此，研究疏散機理，構(gòu)建符合真實情況的行人疏散模型，準(zhǔn)確再現(xiàn)并預(yù)測行人的疏散行為，并采取干預(yù)措施，對維護社會公共安全具有重要意義。

人群疏散模型主要從宏觀和微觀2個方面展開。微觀模型從時間與空間維度上劃分，包括連續(xù)型模型和離散型模型。1995年，Helbing等提出社會力模型(Social-Force,SF)，后來的連續(xù)性模型均在此基礎(chǔ)上改進[1]；離散型模型最具代表性的是元胞自動機(Cellular Automaton，CA)模型，由于其成熟的理論體系、簡單的演化規(guī)則，元胞自動機模型被廣泛應(yīng)用于行人疏散領(lǐng)域[2-4]。考慮到行人感知信息的模糊性，文獻[5-6]利用模糊推理方法建立多出口房間環(huán)境下行人出口選擇行為模型，建立模糊元胞自動機模型(fuzzy cellular automata,FCA)，優(yōu)化行人出口選擇機制，以更加真實地描述疏散過程。雖然FCA在疏散決策方面已有大量研究，但較少對行人移動速度進行研究。以往行人移動速度多是利用函數(shù)方程的方法精確計算，事實上行人移動速度的確定需要根據(jù)行人對周圍環(huán)境的感知進行調(diào)整，信息的模糊性與動態(tài)性導(dǎo)致移動速度具有同樣的特征。同時，從以往的速度公式中可以看出，速度僅由環(huán)境中的人群密度決定，未考慮其他因素的影響，其真實性有待商榷。在疏散方向及疏散路線方面，Schadschneider等[7]修正基于元胞自動機的領(lǐng)域模型，通過靜態(tài)領(lǐng)域和動態(tài)領(lǐng)域建立行人的移動選擇偏好矩陣，實時調(diào)整行人的移動概率，實現(xiàn)行人移動過程中的相互作用；楊立中等[8]、Zhu等[9]從人員行為的角度出發(fā)，提出基于元胞自動機的人員行為微觀離散模型。以上研究重點分析行人與出口的距離、元胞被占領(lǐng)狀態(tài)和出口附近的行人密度等因素對移動方向的影響，未考慮真實情況下行人移動速度的變化以及對出口選擇行為的影響。因此本文在以上研究的基礎(chǔ)上，將模糊推理理論引入元胞自動機模型，結(jié)合人群密度和行人相對距離對移動速度的影響，建立動態(tài)模糊速度模型；融合危險度和動態(tài)參數(shù)模型的思想，建立基于雙端隊列的廣度優(yōu)先搜索(Breadth First Search，BFS)算法，使元胞向危險度更低的方向移動，使模型更加符合真實情況。同時提出基于排隊理論的出口疏散機制。利用所建模型對行人疏散過程中的疏散時間、疏散速度等現(xiàn)象進行討論，為應(yīng)急預(yù)案與應(yīng)急管理提供依據(jù)，從而提升應(yīng)急管理的能力與水平，保障社會公共安全。

1 模型建立

1.1 模型假設(shè)

1)元胞自動機擴展的Moore型結(jié)構(gòu)

在離散二維空間內(nèi)建立元胞自動機模型，每個元胞只能容納1個行人，每個行人只能占據(jù)1個元胞，且位于元胞中心。行人與被占據(jù)的元胞是一一對應(yīng)的關(guān)系。每個元胞的邊長為0.4 m。

本文采用擴展的Moore型鄰居。行人可以向周圍8個方向(編號1～8)移動，或停在原始位置，如圖1所示。把行人在1個時間步長內(nèi)可以移動的位置定義為行人的移動領(lǐng)域。

圖1 元胞自動機擴展的Moore型鄰居Fig.1 Extended Moore type neighbor in CA

2)期望移動速度

行人初始行走速度為0.9～1.5 m/s，正常狀態(tài)下的速度為1.25 m/s，應(yīng)急疏散情況下期望速度為2.5 m/s[10]。

3)信息感知

行人從環(huán)境中感知到的信息包括行人與最近障礙物的距離和感知區(qū)域內(nèi)人群的密度。本文感知區(qū)域為鄰居半徑r=5的鄰居空間，在各移動方向上為5×5的矩陣(如圖1所示)。障礙物定義為感知范圍內(nèi)任何妨礙行人移動速度的對象，如其他行人、墻壁等。人群密度是單位面積上的人員數(shù)量，人/m2。

1.2 基于模糊規(guī)則與BFS算法的行人疏散模型

1)動態(tài)模糊速度模型的建立

影響人員疏散速度的主要因素包括移動方向上人員與障礙物的距離和人群密度[11-13]。而人員從環(huán)境中獲取的距離信息和密度信息均是主觀感知信息，具有不確定性和不精確性，因此運用模糊推理理論建立動態(tài)模糊速度模型。模糊推理系統(tǒng)主要包括模糊化、模糊規(guī)則庫、模糊推理方法和去模糊化4部分。本文建立以行人與最近障礙物的距離D和感知范圍內(nèi)的障礙物密度E為輸入，以速度V為輸出的mamdani型動態(tài)模糊速度模型。

模糊變量的定義域以及覆蓋定義域的模糊集合數(shù)量根據(jù)專家經(jīng)驗知識和實驗數(shù)據(jù)決定。輸入變量行人與最近障礙物的距離D，其定義域取值范圍為0～2.83 m，由3個模糊集{Very-Near(VN),Near(N),Far(F)}表示，分別代表“非常近”“近”和“遠”，采用歐式距離方法計算[12]。利用F統(tǒng)計方法確定模糊集合“VN”“N”和“F”的隸屬度，并采用回歸方法選擇擬合度最高的梯形隸屬函數(shù)為模糊變量的隸屬函數(shù)，距離隸屬函數(shù)如圖2所示。輸入變量障礙物密度E的定義域取值范圍為0～5人/m2，由3個模糊集{Low(L),Medium(M),High(H)}表示，分別表示“低”“中”和“高”。移動領(lǐng)域內(nèi)目標(biāo)方向上的人群密度采用梯形隸屬函數(shù)，障礙物密度隸屬函數(shù)如圖3所示[10]。輸出變量行人移動速度V的定義域為0～5 m/s，移動速度由3個模糊集{Slow(S),Medium(M),Fast(F)}表示，速度隸屬函數(shù)為梯形[12]，如圖4所示。

圖2 距離隸屬函數(shù)Fig.2 Membership function of distance

圖3 障礙物密度隸屬函數(shù)Fig.3 Membership function of obstacle density

圖4 速度隸屬函數(shù)Fig.4 Membership function of speed

行人在向目標(biāo)方向移動的過程中，根據(jù)感知到的環(huán)境信息，將與最近障礙物的距離和障礙物密度加權(quán)融合，確定運動速度。行人與最近障礙物的距離越大，移動速度越大；障礙物密度越小，移動速度越大。但是當(dāng)行人與最近障礙物的距離非常近(<0.4 m)時，即使目標(biāo)方向上的障礙物密度很低，行人的移動速度依然為0。因此，為避免決策沖突，設(shè)定行人間最短距離與人群密度的權(quán)重之比為0.7∶0.3。模糊推理系統(tǒng)可以描述為式(1)：

[V]=R(D,E)

(1)

式中：V表示行人移動速度，m/s；R()為模糊推理系統(tǒng)函數(shù)；D表示行人與最近障礙物的距離，m；E表示感知范圍內(nèi)的障礙物密度，人/m2。推理規(guī)則見表1，共包含9條規(guī)則。

表1 模糊推理規(guī)則Table 1 Fuzzy inference rules

2)基于BFS算法的危險度模型的建立

行人向安全出口的移動通過元胞的危險度確定。危險度越低，行人向該格點移動的概率越大。危險度主要由格點與出口間的距離(“靜態(tài)危險度”)以及出口附近的人群密度(“動態(tài)危險度”)2個因素決定。

從疏散開始到結(jié)束，行人a在單位時間Δt內(nèi)從m(m>1)個出口中選擇出口i的概率Pi如式(2)所示：

(2)

其中Q的計算如式(3)所示：

(3)

靜態(tài)危險度采用廣度優(yōu)先遍歷(Breadth-First Search，BFS)算法計算。BFS是1種解決圖論中最短路徑問題的遍歷算法[14]，其基本思想是采用逐層掃描的方法，從起始頂點開始依次訪問其每1個鄰接點，然后以鄰接點為頂點繼續(xù)掃描下1層鄰接點，直到到達路徑的終點或設(shè)定的終止條件為止。BFS在逐層遍歷圖時用隊列存儲鄰接頂點，利用隊列的“先進先出”實現(xiàn)遍歷要求[15]。

靜態(tài)危險度由格點與出口的距離決定，以出口為中心，向周圍遞增，離出口越近，危險度越低，離出口越遠，危險度越高。靜態(tài)危險度BFS算法流程如下：

①將所有方格的危險度記為DI。

④如果擴張元胞與當(dāng)前格點同屬于當(dāng)前出口內(nèi)的格點，那么該擴張元胞的預(yù)期危險度為0，否則，擴張元胞的預(yù)期危險度為當(dāng)前格點的危險度與Dxy之和，Dxy的計算如式(4)所示：

(4)

式中：Dxy為元胞為擴張元胞(x,y)與當(dāng)前格點的距離，m；Me為無限大的正數(shù)，說明障礙物格點的危險度為無窮大，行人不會選擇被障礙物占據(jù)的格點移動。

⑤如果擴張元胞的危險度為所有方塊的危險度DI，或者大于預(yù)期危險度，將其危險度設(shè)為預(yù)期危險度，并加入隊列；如果預(yù)期危險度為0，將其加入隊列頭，否則加入隊列尾。

⑥如果隊列不為空，則返回步驟③，直到隊列為空。

⑦如果還有未訪問過的出口，則返回步驟②，直到所有的出口均已訪問，且隊列為空，算法結(jié)束，即可得到每個格點的危險度。

3)基于排隊理論的出口疏散機制

疏散過程中擁堵主要集中于疏散出口處，行人在封閉區(qū)域中的疏散時間可視為自由流時間，到達疏散出口擁堵處開始排隊疏散[16]?；诮煌肪W(wǎng)中的常見的Vickrey點排隊模型，將疏散區(qū)域的擁擠延誤轉(zhuǎn)化為端點的排隊時間?；谠詣訖C的傳統(tǒng)BFS方法在出口處的疏散圖如圖5所示。假設(shè)當(dāng)行人①準(zhǔn)備離開出口時的速度為V1。當(dāng)行人①離開出口后，周圍的行人②～⑥均有可能移動到出口附近。此時按照本文提出的模糊速度模型，則周圍的行人②～⑥會考慮周圍的影響，因此最終某個行人會以速度V2移動到出口附近。根據(jù)文獻[1]以及行人流的理論可知當(dāng)出口處行人密度增加時，會導(dǎo)致行人移動速度降低，因此必然存在如式(5)所示的關(guān)系：

圖5 傳統(tǒng)模型出口疏散Fig.5 Exit evacuation diagram of traditional model

V2?V1

(5)

這種情況下嚴(yán)重影響出口行人疏散效率。

為進一步提高疏散效率，為設(shè)施設(shè)備的優(yōu)化布局提供實驗依據(jù)，本文在模糊速度規(guī)則的基礎(chǔ)上引入出口行人疏散排隊理論。基于該模型，路徑上同行能力不受限制，將疏散行人擁擠延誤轉(zhuǎn)化為端點的排隊時間，排隊理論模型過程如圖6所示。

圖6 排隊理論模型Fig.6 Model diagram of queuing theory

根據(jù)圖6的排隊理論模型對圖5的人員疏散進一步分析?；谂抨犂碚撃Ｐ偷某隹谑枭D如圖7所示。按照圖7的疏散流程，當(dāng)行人①以速度V1離開出口時，此時周圍雖然有行人②～⑥，但是根據(jù)排隊理論只有行人④可以順利移動到出口位置。假設(shè)行人④移動到出口位置的速度為V3，則滿足的關(guān)系如式(6)所示：

圖7 基于排隊理論模型出口疏散Fig.7 Exit evacuation diagram based on queuing theory model

V1=V3?V2

(6)

根據(jù)以上分析可知，采用排隊理論能夠有效提高出口處行人的疏散速度。此時，利用疏散延時時間，行人③,⑤,②,⑥會依次進入疏散隊列。基于排隊理論的行人疏散策略如圖8所示。定義圖8中①，④，⑦，③所在位置區(qū)域為排隊區(qū)域。行人按照隊列依次高速離開出口。灰線與排隊區(qū)域中間為排隊調(diào)整區(qū)域。該區(qū)域的行人會自我調(diào)整，依次進入排隊區(qū)域。疏散行人遵循先進先出( First Input First Output，F(xiàn)IFO) 原則。

圖8 基于排隊理論的行人疏散策略Fig.8 Pedestrian evacuation strategy based on queuing theory

基于排隊理論的行人疏散步驟如下。

步驟1:行人疏散移動進入排隊調(diào)整區(qū)域。

步驟3:往出口反方向平行于排隊區(qū)域移動。如果前方有行人則等待，否則移動。移動后判斷是否滿足步驟2中的距離要求，如果滿足則排隊離開出口，否則進入步驟4。

步驟4:繼續(xù)往出口反方向平行于排隊區(qū)域移動，直到滿足距離要求。

2 仿真與分析

為驗證本文所提出的元胞自動機模型的有效性，通過模擬仿真的方法進行應(yīng)用分析。模型建立在空間大小為21×29的離散二維空間內(nèi)，即把人群的移動空間分成離散的21×29個元胞。每個網(wǎng)格實際占據(jù)面積0.4 m×0.4 m，每個出口占據(jù)1個元胞，大小為0.4 m，每次只允許1人通過。疏散空間中共有198名行人，模擬行人的直徑為0.4 m，行人中心為格點的中心。如圖9所示。圖9為根據(jù)仿真條件設(shè)計的含有2個出口的疏散環(huán)境，出口A位于疏散空間的左下方，B位于上方。行人初始行走速度為0.9～1.5 m/s，正常狀態(tài)下的速度為1.25 m/s，應(yīng)急疏散情況下期望速度大小為2.5 m/s。模型采用并行更新機制。為使數(shù)據(jù)分析可靠有效，所得數(shù)據(jù)為8次模擬的平均值。

圖9 疏散環(huán)境平面Fig.9 Plan view of evacuation environment

2.1 改進模型仿真分析

根據(jù)本文所提出的模型，疏散過程如圖10所示。圖10(a)～(f)分別表示t=10，20，30，40，50，60 s時，行人的疏散情況。行人考慮與出口的距離和出口附近的人群密度，向危險度較低的出口移動。由圖10(a)可知，在疏散的初始階段，由于距離B出口的人數(shù)較多，所以根據(jù)最近距離原則，選擇B出口的人數(shù)較多。隨著疏散過程的繼續(xù)，B出口的行人越來越多，人群密度增大，移動速度降低，導(dǎo)致排隊時間增長。這時行人會綜合考慮“靜態(tài)危險度”和“動態(tài)危險度”的值，重新評估通過2個出口的總時間，選擇總時間較少的出口。因此部分行人改變目標(biāo)出口，朝A出口疏散。由圖10(f)可以看出，通過2個出口的人員幾乎同時離開疏散區(qū)域，符合實際疏散情況。行人在疏散過程中向出口聚集時，出口區(qū)域呈現(xiàn)“拱形”結(jié)構(gòu)，在疏散后期“拱形”結(jié)構(gòu)逐漸變小并最終消失。模型仿真再現(xiàn)行人疏散的自組織現(xiàn)象，證明所提出模型是有效的。

圖10 行人疏散仿真過程Fig.10 Simulation process of pedestrian evacuation

圖11 基于模糊速度規(guī)則的行人平均疏散速度曲線Fig.11 Average evacuation speed curve of pedestrian based on fuzzy speed rules

(7)

在本文提出的模型中，每個行人根據(jù)周圍環(huán)境以不同的速度方式移動，隨著疏散的進行，當(dāng)t>40 s時，疏散區(qū)域中人數(shù)變少，人群密度降低，平均疏散速度增加。當(dāng)t為56 s左右時，平均移動速度急劇下降。這是因為在疏散的后期，區(qū)域內(nèi)大部分行人出現(xiàn)在“拱形”區(qū)域內(nèi)，行人之間密度很小，導(dǎo)致平均速度下降。疏散區(qū)域內(nèi)所剩行人繼續(xù)減少，行人的移動速度隨之增加，并達到最大值；當(dāng)行人全部離開疏散區(qū)域時，行人移動平均速度降到最低。平均疏散速度的提高在一定程度上提高疏散效率。

2.2 與傳統(tǒng)元胞自動機疏散模型對比

1)與傳統(tǒng)疏散模型的對比

①移動速度

②出口方向選擇

傳統(tǒng)疏散模型和本文所提出的模型在出口方向的選擇上，均考慮行人所在位置距出口的距離和出口處人群密度2個影響因素，其中靜態(tài)危險度均采用BFS算法計算。

③出口疏散機制

本文提出基于排隊理論的出口疏散機制，而傳統(tǒng)模型中未包含此部分。

2)疏散時間與效率對比

在A，B 2個出口的疏散環(huán)境下，2種模型的疏散時間對比情況如圖12所示。可以看出，傳統(tǒng)模型的疏散時間為t=87 s,改進模型的疏散時間為t=72 s。較之傳統(tǒng)模型，改進模型的疏散時間縮短15 s,疏散效率提高17.24%。

圖12 疏散時間對比曲線Fig.12 Comparison curve of evacuation time

3)出口利用率對比

傳統(tǒng)疏散模型和本文提出的疏散模型在整個疏散過程中，各出口的疏散人數(shù)隨時間的變化情況如圖13所示。橫坐標(biāo)X表示疏散時間，s,縱坐標(biāo)Y表示疏散人員的數(shù)量，個。傳統(tǒng)模型中出口A和B的疏散人數(shù)分別是68和130，本文提出的模型在出口A和B的疏散人數(shù)分別為96和102，相比于傳統(tǒng)模型，2個出口的疏散人數(shù)更加接近，出口利用率更高。

圖13 不同出口的疏散人數(shù)對比曲線Fig.13 Comparison curve of number of evacuees at different exits

雖然2個模型在計算危險度時均考慮行人位置與出口的距離和出口附近的人群密度，并將二者進行耦合，但傳統(tǒng)模型2出口的疏散人數(shù)之差仍然較大。原因是行人的疏散時間由行人移動到出口的時間(自由流時間)和在出口排隊疏散的時間(排隊時間)2部分組成。在傳統(tǒng)模型中，對于B出口疏散區(qū)域的外圍人員來說，當(dāng)B出口人群擁擠而以A為目標(biāo)出口時，行人只能以1元胞/步的速度向A出口移動，這時移動到A出口所花費的時間與繼續(xù)選擇B出口所花費的時間相比并未減少，因此行人繼續(xù)選擇從B出口疏散。改進的模型中，行人能夠根據(jù)周圍環(huán)境調(diào)整移動速度，比如當(dāng)B出口疏散群體的外圍行人在朝向A出口的前進方向上無行人阻礙時，能夠以較大的速度向A出口移動，使從A出口疏散的總時間少于繼續(xù)從B出口疏散的時間，從而以A為目標(biāo)出口。因此本文提出的模型能夠解決多出口環(huán)境中行人的出口選擇這一重要問題，更真實地描述行人的決策過程與疏散行為，更符合真實的疏散情況。

3 結(jié)論

1)根據(jù)行人對周圍環(huán)境的模糊感知，運用模糊推理理論建立動態(tài)模糊速度模型，從微觀角度更加真實準(zhǔn)確地描述行人不同的移動速度，以及群體疏散過程，為行人疏散模型的建立提供1種思路。

2)通過設(shè)定危險度規(guī)則，使用基于雙端隊列的BFS算法快速計算每個格子的危險度，同時結(jié)合出口附近的人群密度，更加科學(xué)合理地選擇安全出口，規(guī)劃疏散路徑。

3)在出口疏散方面，引入排隊理論模型，設(shè)置排隊區(qū)域和排隊調(diào)整區(qū)域，優(yōu)化排隊模式，進一步提高疏散效率，為公共區(qū)域的設(shè)施布局提供有效建議。