結合最短路徑改進的社會力人群疏散仿真模型

李 俊

寧波工程學院 電子與信息工程學院，浙江 寧波315211

當人群密集場所（如商場、交通樞紐、學校、醫(yī)院等）發(fā)生火災、地震、恐怖襲擊等緊急事件時，人群需要及時疏散到安全區(qū)域。如果建筑布局復雜，安全通道和逃生出口設計得不合理，或在突發(fā)事件時沒有對人群進行合理有效的疏散指導，極易使人錯過最佳疏散時機，導致出現(xiàn)嚴重的人員傷亡后果。因此，設計布局合理的建筑物，在公共場所發(fā)生突發(fā)事件前能進行預防，以及在突發(fā)事件發(fā)生時能對人群進行合理科學的疏導進行指導，是目前公共安全領域亟待解決的問題。

突發(fā)事件中人群疏散行為研究方法主要分為兩種：一是在規(guī)定的時間和地點中，組織人員進行模擬疏散演習，獲取疏散數(shù)據進行分析。另外是利用計算機進行場景建模，結合社會學、心理學和力學等學科，進行人群疏散仿真，研究在不同情景下的人群疏散特征規(guī)律。前者方法消耗較多的人力物力，存在安全隱患，難于開展大規(guī)模研究。后者方法在成本和安全性上有較大優(yōu)勢，可以在不同場景中重復仿真，通過仿真數(shù)據可以判斷建筑物的疏散通道設計得是否合理，是否滿足人群疏散的要求，也可以為制定科學合理的疏散方案提供決策支持。因此利用計算機進行人群仿真是研究人群疏散行為的重要途徑。

許多研究人員和機構對人群疏散仿真進行了廣泛的研究和探索，主要人群仿真模型有社會力模型（SFM）[1-2]、元胞自動機模型（CA）[3-4]和勢能場模型（PF）[5-6]，其中社會力模型應用廣泛，許多學者對其進行了優(yōu)化和改進。文獻[7]設計了帶有動態(tài)導航場的擴展SFM，以研究雙向行人運動。文獻[8]設計了一種改進的兩層SFM用于仿真人群聚會過程。文獻[9]利用SFM開發(fā)了用于交叉路口的行人行為分析的微觀仿真模型。文獻[10]在SFM 中增加了領導者參數(shù)進行人群仿真。文獻[11]基于改進的SFM 開發(fā)了自動扶梯中擁堵風險的仿真模型。文獻[12]利用密度場對SFM進行了改進。文獻[13]提出緊張系數(shù)、出口可靠性等參數(shù)改進SFM 來仿真車站的負重人群疏散。文獻[14]改進SFM的二維特性，在三維樓梯空間驗證SFM 可行性。文獻[15]基于SFM 建立了考慮行人隨機行為的仿真模型。

在人群疏散仿真過程中，疏散路徑的選擇對行人疏散時間和效率有重要影響。文獻[16]建立了一個動態(tài)規(guī)劃模型，通過找到最優(yōu)解來確定路徑。文獻[17]基于改進的動態(tài)參數(shù)模型，提出了一種具有不對稱出口布局的房間行人疏散的仿真模型。文獻[18]采用一種多行人導航圖與SFM相結合來執(zhí)行路線規(guī)劃。文獻[19]提出了一種性能評估框架用于城市疏散建模的行人導航模型。

本文結合最短路徑提出一種適用于多障礙物和多出口場景下的社會力人群疏散仿真模型。該模型能夠根據行人的位置、場景中障礙物的分布及每個出口的位置規(guī)劃出一條合理有效的疏散路徑。該模型能夠有效解決社會力模型出現(xiàn)行人運動停滯不前，行人陷入非凸邊形障礙物中和行人仿真的疏散路線與行人實際選擇的路線不相符等問題。通過相關實驗表明該人群疏散模型在人群仿真上更加真實。

1 社會力模型存在的問題

1.1 社會力模型原理

Helbing等人[1-2]觀察到行人在逃生過程中會與障礙物和其他人保持一定安全距離后，于1998 年提出了社會力模型，該模型基于牛頓的力學公式和行人的逃生行為，將每個行人簡化抽象為用一個粒子來描述，該粒子受到目的地的吸引產生一個自身的驅動力，同時該粒子受到與障礙物和其他粒子的斥力和摩擦力，在這些力的合力作用下，該粒子在二維的空間中產生加速度，驅動該粒子連續(xù)運動，其使用動力學公式如下：

其中,mi(v0i(t)e0i(t)-vi(t))/τi為行人指向目的地的驅動力，fij為行人間的作用力，fiw為行人與障礙物間的作用力。mi是行人質量，v0i、vi(t)為行人的期望速度和實際速度，e0i(t)為期望的運動方向，τi為適應時間。

行人間的作用力fij由排斥力和摩擦力組成，其計算公式如下：

其中，Ai、Bi、k、κ為常數(shù)量，Ai為行人間排斥力的強度，Bi為產生排斥力的最小距離，k和κ為較大的常量。rij=ri+rj，表示行人的半徑之和。dij表示行人間質心的距離，dij=‖ri-rj‖。nij表示由行人間的標準化向量，nij=(n1ij,n2ij)=(ri-rj)/dij。g(x) 表示一個函數(shù)，當行人不能互相接觸時(rij＜dij)取值為0，否則為x。 Δvtji表示行人間的切線方向的相對速率，Δvtji=(vj-vi)·tij，tij表示行人間的切線方向，tij=(-n2ij,n1ij)。

行人和障礙物間的作用力fiw由排斥力和摩擦力組成，其計算公式如下：

其中，diw表示行人和障礙物邊緣的距離，niw表示由障礙物邊緣到行人的標準化向量，vi表示行人的實際速率，tiw表示行人與障礙物邊緣的切線方向。社會力模型中參數(shù)詳見表1。

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

1.2 社會力模型在人群仿真中存在的問題

基于社會力模型進行人群疏散仿真過程中，行人在社會力的驅動下可以避免行人之間相互碰撞，向目的地方向運動，被廣泛應用于突發(fā)事件人群疏散仿真，但在多障礙物場景中，障礙物的形狀、位置分布會影響行人的疏散行為，導致基于社會力模型的人群疏散仿真有可能出現(xiàn)下列問題。

（1）行人運動軌跡震蕩、停滯不前

根據社會力模型的原理，如果行人和目的地之間沒有障礙物，行人在自驅動力和行人間的作用力下會疏散到目的地，但當行人和目的地之間有障礙物時，如果行人運動方向和障礙物垂直，則會出現(xiàn)行人運動軌跡震蕩，停滯不前現(xiàn)象。例如圖1 場景中，S點為行人出發(fā)點，T點為目的點，W為障礙物。根據公式（3），當行人距離W較遠時，自驅力大于障礙物的斥力，行人向W運動；當行人逐漸靠近W時，受W的斥力逐漸增加，當斥力大于自驅動力時，行人開始減速運動；當速度減到0時，行人開始反向運動，當行人遠離W過程中受到W的斥力越來越小，使運動方向再次反轉，行人又接近障礙物。該過程會重復進行多次，導致出現(xiàn)行人運動軌跡振蕩現(xiàn)象，當行人受到的合力為0時，行人將停滯在G1點，無法抵達T點。

圖1 行人運動軌跡震蕩、停滯不前

（2）行人無法繞過非凸邊形障礙物

當場景中有非凸邊形障礙物時，社會力模型會使處在非凸邊形區(qū)域內的行人無法繞出障礙物。例如圖2為一個具有非凸邊形障礙物的場景，當S點的行人在社會力模型驅動下運動到G1 點后，行人與W接觸，產生排斥力和摩擦力，由于行人此時受到自驅動力、與W的排斥力和摩擦力的作用下會沿著W向下運動，當行人運動到G2 點后，行人受到的自驅動力與W垂直，行人最終會停止在G2 點，無法繞過障礙物疏散到目的地點。

圖2 行人無法繞過非凸邊形障礙物

（3）行人疏散仿真路徑不合理

社會力模型中行人的運動路徑依賴于合力的驅動，在某些場景中，該模型不能產生合理的行人運動軌跡。例如圖3 場景，S點行人往往會選擇最短路徑進行疏散，即選擇S→G1 →T疏散路徑。然而在社會力模型中，S點行人在社會力的作用下首先運動到G2 點，然后碰撞到W后沿著W向上運動到G3 點，繞過W后，在目的地方向的自驅力的作用下運動到T點，整個疏散軌跡為S→G2 →G3 →T，與行人實際疏散路徑不相符。

圖3 行人仿真的疏散路徑過長

2 基于最短路徑改進的社會力模型

針對社會力模型存在的上述問題，提出一種基于最短路徑改進的社會力模型，解決在復雜空間場景中的行人疏散仿真問題。首先，在障礙物的每個頂點附近選擇一個合理的位置作為行人路徑節(jié)點。然后，根據行人初始節(jié)點、路徑節(jié)點、目的節(jié)點之間的連通性，以及節(jié)點的安全系數(shù)和擁擠系數(shù)對節(jié)點通行性的影響構造一個無向圖，并在無線圖中生成從行人初始節(jié)點到目的節(jié)點的最短路徑。最后基于社會力模型將行人按照最短路徑疏散到目的地。

2.1 生成路徑節(jié)點

用多邊形表示場景中的障礙物。為了使行人在疏散過程中能繞過障礙物，并且不與障礙物發(fā)生碰撞，在障礙物的每個頂點附近生成一個節(jié)點作為行人繞過障礙物的路徑節(jié)點。生成的節(jié)點需滿足兩個條件：一是所生成的節(jié)點不能與障礙物相交，因為如果相交，會使行人與障礙物發(fā)生碰撞，出現(xiàn)行人運動軌跡振蕩、停滯不前現(xiàn)象。例如圖4中，如果D1 點或D本身點作為頂點D附近的節(jié)點，當行人抵達該節(jié)點時將會與障礙物發(fā)生碰撞，導致行人產生振動、停滯不前。另一個是如果場景中相鄰的兩個頂點是連通的，那么由這兩個頂點生成的路徑節(jié)點在場景中也必須是連通的，因為如果不保持連通性將會導致疏散行人與障礙物發(fā)生碰撞，例如圖4中選擇A1 和B1 為頂點A和B的路徑節(jié)點，頂點A和B在場景中是連通的，但是生成的路徑節(jié)點A1 和B1不是連通的，行人會與障礙物發(fā)生碰撞。圖4 中A1 和B2 為正確的路徑節(jié)點的樣例，因為它們既不與障礙物相交，它們的連線又保持了連通性。

圖4 選擇路徑節(jié)點

為了使選擇的路徑節(jié)點滿足上述兩個條件，選擇在障礙物頂角的角平分線的反向延長線上，找到距離頂點的距離為行人N倍半徑長度的點作為該頂點生成的路徑節(jié)點。以圖5中頂點B生成路徑節(jié)點為例，描述路徑節(jié)點生成算法。

圖5 障礙物頂點對應的路徑節(jié)點

輸入：頂點A、B、C的坐標(Ax,Ay),(Bx,By),(Cx,Cy)。

輸出：角B的角平分線BF的反向延長線上距離B點長度為N×r的B'的坐標。

步驟：

（1）根據頂點A、B的坐標，求出AB的直線方程為：

（2）根據頂點B、C的坐標，求出BC的直線方程為：

（3）設直線AB和BC的角平分線為BF，設點(Fx,Fy)為直線BF上的任意一點。根據角平分線定理，點(Fx,Fy)到直線AB和BC距離相等，得到方程：

（4）根據公式（6），當Fx取值為0時可得到Fy的兩個值，設為Fy0、Fy1。通過(0,Fy0)、(Bx,By)和(0,Fy1)、(Bx,By)可以得到直線AB和BC的兩條對應的角平分線BF和BF'，如圖6所示。

圖6 生成路徑節(jié)點過程

（5）在直線BF和BF'上分別求出距離B點距離為NR的點，可以得到四個點，分別是B1、B2、B3、B4，這四個點中只有一個點可以作為路徑節(jié)點。為了確定該點，首先找出這四個點中位于障礙物內的點，該點所在的直線上的另一個點即是所選擇的路徑節(jié)點。如圖6中找到位于障礙物內的點是B1 點，該點所在的直線是BF，該直線上另一個點是B3，則B3 的坐標是頂點B對應路徑節(jié)點B'的坐標。

2.2 判斷路徑節(jié)點的可選擇性

疏散路徑節(jié)點的通行狀況會隨著環(huán)境的變化而改變，例如發(fā)生火災時，著火點周圍的空間存在危險性，越靠近著火點的路徑節(jié)點的危險性越高，越難作為逃生路線中的節(jié)點，因此對路徑節(jié)點定義一個危險系數(shù)屬性，用NR表示，其取值范圍為[0，1]，NR值越大，代表危險性越高，0 表示路徑節(jié)點無危險，1 表示危險性最高。NR計算方法如下：

其中，DR是路徑節(jié)點與危險源中心點的距離，危險源可以為著火點、物體倒塌位置或移動的恐怖分子等，DMinR是路徑節(jié)點與危險源的最小安全距離。

當某個疏散路徑周圍的人數(shù)較為擁擠時，會降低該節(jié)點的可通行性，因此疏散路徑節(jié)點的擁擠程度也會影響路徑節(jié)點的通行效率。定義路徑節(jié)點的擁擠性系數(shù)NC，取值范圍為[0，1]，NC值越大，代表擁擠性越高，0表示路徑節(jié)點無擁擠，1表示擁擠性最高。設路徑節(jié)點周圍5 m 范圍內的行人會對擁擠系數(shù)產生影響，NC計算方法如公式（8）：

其中PR為行人與路徑節(jié)點的距離。

行人在疏散過程中會考慮危險系數(shù)和擁擠系數(shù)選擇合理的疏散路徑。由于行人存在個體性差異，對于危險性和擁擠性的認知不同，定義行人對于危險性的認知系數(shù)（用PR表示）和對擁擠性的認知系數(shù)（用PC表示），根據不同的行人類型，其取值范圍為[0，1]，取值越高表明行人對于路徑節(jié)點的危險和擁擠程度的承受能力越強。行人選擇路徑節(jié)點的條件為PR≥NR&PC≥NC，行人只能在符合條件的路徑節(jié)點中選擇最短疏散路徑。

2.3 基于路徑節(jié)點構造行人疏散路徑

為求得行人的疏散路徑，采用一個無向圖對場景進行重構。把場景中行人開始節(jié)點、所有可選路徑節(jié)點（若路徑節(jié)點的危險系數(shù)PR或擁擠系數(shù)PC高于行人的危險認知系數(shù)NR和擁擠認知系數(shù)NC，則該節(jié)點為不可選路徑節(jié)點）和所有出口節(jié)點作為無向圖的頂點集合，判斷該集合中任意兩個頂點的連線與障礙物是否相交，如果不相交，表明頂點連通，創(chuàng)建一條邊，如此構造出場景的連通無向圖。該無向圖中從行人開始節(jié)點到目的節(jié)點的每條通路都是行人可能選擇的疏散路徑，一般情況下，行人會在眾多疏散路徑中選擇最短路徑，因此在構造的無向圖中采用Dijkstra算法求出從行人開始節(jié)點到每個出口節(jié)點的最短路徑，選擇其中最短的一條路徑作為行人選擇的疏散路徑。

通過一個復雜多障礙場景實例驗證行人疏散路徑選擇的合理性。在圖7（a）中，S點為行人初始點，T1、T2 點為出口點，中間為多邊形障礙物，A～O為障礙物生成的路徑節(jié)點，其中假設K點為著火區(qū)域，危險系數(shù)很高，M點為擁擠系數(shù)很高。根據算法行人不會選擇K點和M點，故場景中去除M點和K點，根據場景中任意兩個節(jié)點的連線與障礙物是否相交構造無向圖。具體構造場景的無向圖如圖7 所示。依次判斷S點和A點之間是否有障礙物，通過圖7（a）可見，S和A點之間有障礙物，所以S和A點之間沒有邊。判斷S和B點之間沒有障礙物，則S和B點之間創(chuàng)建一條連線，如圖7（a）所示。再同理依次判斷S和圖中其他節(jié)點之間是否有障礙物畫出連線，結果如圖7（b）所示。重復進行此操作，至到把無向圖中所有連通的兩個頂點創(chuàng)建一條連線，構造出場景最終連通無向圖，如圖7（c）藍色虛線所示。最后求出從行人開始節(jié)點到所有目的地點的最短路徑，選擇其中最短的一條路徑作為疏散路徑，見圖7（d）紅色路徑S→C→D→E→F→T2 為行人選擇的疏散路徑。

圖7 生成最短路徑

2.4 基于社會力模型疏散行人

確定行人疏散路徑后，采用社會力模型對行人進行疏散。先將行人位置作為行人的初始節(jié)點，以行人疏散路徑中的第二個節(jié)點作為行人的臨時目的地，利用社會力模型驅動行人運動到該臨時目的地，再將疏散路徑中的下一個節(jié)點作為行人的臨時目的地，如此往復直到行人抵達目的地。

3 相關實驗

為驗證算法的有效性采用Visual Studio 2019開發(fā)仿真系統(tǒng)，通過設置不同的障礙物場景，記錄行人的運動軌跡，驗證行人是否能夠合理、有效地繞行障礙物，選擇合理的疏散路徑逃到出口。

3.1 簡單障礙物的路徑規(guī)劃實驗

仿真實驗場景中的障礙物分別采用三角形（見圖8（a））和多邊形（見圖8（b））表示，實驗單個行人疏散路徑規(guī)劃。圖8中A點為行人出發(fā)節(jié)點，B點為目的節(jié)點，藍色節(jié)點為障礙物生成的路徑節(jié)點，綠色的路徑為算法規(guī)劃出的行人疏散路徑。從圖中可見該算法在單障礙物場景中可以有效規(guī)劃出行人疏散路徑。

圖8 簡單障礙物場景

3.2 多障礙物的路徑規(guī)劃實驗

圖9（a）、（c）是兩個包含多種障礙物（包括非凸邊形）組合而成的場景，根據路徑節(jié)點和目的節(jié)點生成連通圖。圖9（b）、（d）為算法在這兩個圖中對多個不同位置的行人規(guī)劃的疏散軌跡線，從圖中可見該算法在多障礙物、多行人場景中都可以有效規(guī)劃出疏散路徑。

圖9 多障礙物多行人場景

3.3 復雜場景路徑規(guī)劃實驗

設計一個超市場景，場景中有橫向和縱向的貨架且存在非凸形的貨架。圖10（a）為只在超市場景中的下面設計一個安全出口，圖10（b）為在超市場景中的左側、右側和下側各設計一個安全出口。超市場景中隨機布置50個行人。圖10為本文算法對該場景生成的疏散軌跡線，可見不同位置行人可以選擇與其最近的出口完成疏散，表明該算法可以根據場景中障礙物和出口的布局規(guī)劃出合理的疏散路徑。

圖10 復雜障礙物多行人場景

3.4 路徑危險性實驗

為了驗證路徑節(jié)點存在危險性時算法的有效性，設計如下實驗。

（1）多障礙物場景

設計由4 個矩形構成的場景，下方為行人的出發(fā)點，上方的矩形為目的區(qū)域，當所有的路徑節(jié)點有效時，行人疏散軌跡如圖11（a）所示。用一個矩形障礙物阻擋通道，如圖11（b）所示，使相關路徑節(jié)點失效，此時行人疏散軌跡發(fā)生了變化，避開了不可通行區(qū)域，選擇了可同行的路徑疏散到目的地。用圓形表示場景中發(fā)生火災的區(qū)域（見圖11（c）、（d）），這時火災相鄰區(qū)域的路徑節(jié)點危險系數(shù)較高，此時行人都選擇危險系數(shù)較低的路徑通行。通過這些實驗結果可知該算法能使行人選擇更加合理的疏散路徑，說明了算法的有效性。

圖11 多障礙物多行人場景

（2）復雜障礙物場景

為了驗證算法的有效性，模擬在商場場景中突發(fā)事件時人群疏散情況。設計商場場景中分布著3 行、4 列柜臺，右側有一個出口，場景中人數(shù)為70人。圖12（a）為場景中的通道通暢時算法模擬出的行人軌跡線。圖12（b）是單個通道中發(fā)生火災時本文算法模擬出的行人軌跡線，圖12（b）中的圓形表示火災的范圍，火災附近的路徑節(jié)點會失效，從圖中可以看出行人會避開火災區(qū)域，選擇合理的繞行路徑疏散到安全出口。

（3）復雜障礙物場景三維效果實驗

為了提升仿真效果，采用unity3D 進行三維場景仿真，在場景中利用六面體表示柜臺，加入火焰效果，導入3D人物模型，三維仿真效果如圖13所示，其中圖13（a）為正常場景，圖13（b）為單個火災場景。從圖中可以看出行人會避開火災區(qū)域，選擇合理的繞行路徑疏散到安全出口。

圖12 復雜障礙物行人疏散軌跡

圖13 復雜障礙物行人疏散三維場景

3.5 與AnyLogicg軌跡對比實驗

常用的行人疏散仿真軟件有AnyLogic、MassMotion、Simwalk、Steps等。其中Anylogic實現(xiàn)了基于SFM和最短路徑優(yōu)化的行人庫模型，可用于復雜空間中的行人模擬，因此本文采用Anylogic進行實驗對比。

采用相同的場景，相同的行人數(shù)量及初始位置與Anylogic進行實驗對比。對比仿真的軌跡如圖14所示，其中圖14（a）、（c）為AnyLogic的行人疏散軌跡線，圖14（b）、（d）為本文算法的行人疏散軌跡線。從圖中可以看出，本文改進的社會力模型和Anylogic模型中行人選擇避開障礙物的疏散路徑基本一致，并且場景中的所有行人都可以成功撤離到出口，表明本文算法的有效性。但是在圖14（c）中，AnyLogic算法在出口附近部分行人疏散軌跡線顯示為弧形，這與實際的行人疏散行為不符，主要原因是Anylogic 模型在疏散行人的過程中考慮了行人的慣性作用所致。在本文算法中，當行人疏散到出口時，他們將疏散到離自己最近的位置，疏散軌跡更加逼真。

圖14 與AnyLogic對比實驗

通過上述實驗表明該改進的社會力模型能有效解決原有社會力模型中出現(xiàn)行人停滯不前、無法通過非凸邊形障礙物和疏散路徑過長問題。在復雜多障礙物、多出口、凹多邊形障礙物場景中，該模型都可以合理地規(guī)劃出行人疏散路徑。當場景中存在危險源和行人擁擠時，該模型也可以規(guī)劃出合理的疏散路徑。并且與AnyLogic 的疏散路徑相比較，該算法模擬出的疏散路徑更真實。表明該模型能夠更加真實地模擬突發(fā)事件時行人疏散行為。

4 結束語

本文通過研究社會力模型在人群仿真中存在的局限性，提出了一種改進的社會力人群疏散模型，該模型根據障礙物的頂點生成路徑節(jié)點，然后根據行人可選路徑節(jié)點構造出場景無向圖，最后根據構造出的無向圖獲得行人最佳疏散路徑，并使用社會力模型對行人進行疏散。實驗結果表明本文算法在多障礙場景中能夠有效地規(guī)劃出疏散路徑，使得人群疏散仿真更加真實。人群仿真是一個具有挑戰(zhàn)性的工作，人群在疏散過程中，還有多種因素影響疏散軌跡的選擇，行人個體導航的認知能力、場景中導向標記、場景中刺激源的分布、人群的整體運動方向等，這些是下一步研究路徑規(guī)劃過程中擬進一步考慮的因素。