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

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

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

0 引言

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

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

1 模型建立

1.1 模型假設

1)元胞自動機擴展的Moore型結構

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

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

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

2)期望移動速度

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

3)信息感知

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

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

1)動態模糊速度模型的建立

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

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

圖2 距離隸屬函數Fig.2 Membership function of distance

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

圖4 速度隸屬函數Fig.4 Membership function of speed

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

[V]=R(D,E)

(1)

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

表1 模糊推理規則Table 1 Fuzzy inference rules

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

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

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

(2)

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

(3)

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

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

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

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

(4)

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

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

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

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

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

疏散過程中擁堵主要集中于疏散出口處，行人在封閉區域中的疏散時間可視為自由流時間，到達疏散出口擁堵處開始排隊疏散[16]。基于交通路網中的常見的Vickrey點排隊模型，將疏散區域的擁擠延誤轉化為端點的排隊時間。基于元胞自動機的傳統BFS方法在出口處的疏散圖如圖5所示。假設當行人①準備離開出口時的速度為V1。當行人①離開出口后，周圍的行人②～⑥均有可能移動到出口附近。此時按照本文提出的模糊速度模型，則周圍的行人②～⑥會考慮周圍的影響，因此最終某個行人會以速度V2移動到出口附近。根據文獻[1]以及行人流的理論可知當出口處行人密度增加時，會導致行人移動速度降低，因此必然存在如式(5)所示的關系：

圖5 傳統模型出口疏散Fig.5 Exit evacuation diagram of traditional model

V2?V1

(5)

這種情況下嚴重影響出口行人疏散效率。

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

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

根據圖6的排隊理論模型對圖5的人員疏散進一步分析。基于排隊理論模型的出口疏散圖如圖7所示。按照圖7的疏散流程，當行人①以速度V1離開出口時，此時周圍雖然有行人②～⑥，但是根據排隊理論只有行人④可以順利移動到出口位置。假設行人④移動到出口位置的速度為V3，則滿足的關系如式(6)所示：

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

V1=V3?V2

(6)

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

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

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

步驟1:行人疏散移動進入排隊調整區域。

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

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

2 仿真與分析

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

圖9 疏散環境平面Fig.9 Plan view of evacuation environment

2.1 改進模型仿真分析

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

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

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

(7)

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

2.2 與傳統元胞自動機疏散模型對比

1)與傳統疏散模型的對比

①移動速度

②出口方向選擇

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

③出口疏散機制

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

2)疏散時間與效率對比

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

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

3)出口利用率對比

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

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

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

3 結論

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

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

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