徐梓桉

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

人群疏散對(duì)建筑設(shè)計(jì)和城市規(guī)劃有重要的意義。一個(gè)設(shè)計(jì)良好的疏散方案包括一個(gè)在短時(shí)間內(nèi)幫助人群到達(dá)出口的疏散指導(dǎo)。由于人群分布可以根據(jù)某些事件進(jìn)行估計(jì)，例如音樂(lè)會(huì)和新年慶祝，因此疏散方向標(biāo)志可以在人群聚集在一個(gè)地方前設(shè)置好逃生方向標(biāo)志。此外,隨著監(jiān)測(cè)照相機(jī)和傳感器網(wǎng)絡(luò)變得越來(lái)越多最近，對(duì)人群的動(dòng)態(tài)估計(jì)分布允許我們的系統(tǒng)動(dòng)態(tài)反應(yīng),提高其有效性。

人群模擬比較典型的做法是通過(guò)全局尋路確定到目標(biāo)點(diǎn)宏觀的路徑，然后通過(guò)局部的導(dǎo)航點(diǎn)和碰撞避免來(lái)獲取實(shí)際的速度[1]。我們?cè)诒疚闹刑岢隽艘粋€(gè)全新的策略來(lái)規(guī)劃全局路徑。我們的方法產(chǎn)生的結(jié)果比基于智能體的單純的目標(biāo)導(dǎo)向的導(dǎo)航模型更有可信度。該模型有一個(gè)額外的過(guò)程階段，實(shí)驗(yàn)表明，該系統(tǒng)具有較好的仿真效果，甚至在擁擠的場(chǎng)景中也能提高效率提前避免擁擠。

1 系統(tǒng)概述

在我們的研究中，我們使用了互利速度障礙（RVO）模型[2]和由全局信息決定的修改后的A*算法[3]，作為我們的基礎(chǔ)控制算法。我們使用改進(jìn)后的A*算法來(lái)計(jì)算一個(gè)個(gè)體在均勻網(wǎng)格上從當(dāng)前位置到目標(biāo)位置的長(zhǎng)期路徑。然后計(jì)算路徑的首要步驟就是使用RVO來(lái)計(jì)算最佳速度來(lái)避免附近的碰撞。我們提出的這個(gè)系統(tǒng)的關(guān)鍵方面在于我們修改了了A*算法的代價(jià)方程，將個(gè)體的現(xiàn)在和將來(lái)可能出現(xiàn)的位置納入路徑計(jì)算的代價(jià)考慮。為了實(shí)現(xiàn)這個(gè)，在每個(gè)個(gè)體的路徑計(jì)算完成之后，我們將保存路徑的信息用來(lái)幫助其他個(gè)體規(guī)劃他們的路徑。值得注意的是，我們不直接使用這些信息，這些信息是用在改進(jìn)的A*算法上的。因此，我們的算法不會(huì)受到局部最小值問(wèn)題的影響。

2 RVO算法

我們使用尋路算法規(guī)劃得到的路徑能夠使得人群能夠在全局范圍內(nèi)通過(guò)階段性的導(dǎo)航位置來(lái)找到合適的路徑和傾向速度。但是，路徑規(guī)劃是以人群個(gè)體為計(jì)算單位的，路徑規(guī)劃過(guò)程中并沒(méi)有將其他的運(yùn)動(dòng)個(gè)體作為障礙物來(lái)考慮，因此路徑規(guī)劃的結(jié)果并不能保證人群之間的路徑不會(huì)有交叉而導(dǎo)致運(yùn)動(dòng)過(guò)程中的碰撞和穿透重疊。因此，需要碰撞避免算法在運(yùn)動(dòng)過(guò)程中對(duì)路徑規(guī)劃的結(jié)果進(jìn)行修正。碰撞避免算法是通過(guò)將速度修正的邏輯使得所有在△t時(shí)間內(nèi)的人群個(gè)體的速度運(yùn)動(dòng)位置不會(huì)發(fā)生碰撞和穿透重疊的現(xiàn)象[3]。

在所有碰撞避免的實(shí)現(xiàn)方法中，F(xiàn)iorini等人提出遇障速度空間算法Velocity Obstacles[4]來(lái)解決該問(wèn)題。人群個(gè)體A以速因此當(dāng)個(gè)體A繼續(xù)以速度運(yùn)動(dòng)將會(huì)與人群個(gè)體B發(fā)生碰撞。在遇障速度算法作用下，人群個(gè)體A在人群個(gè)體B的遇障速度空間作用下得到修正速度，即；同理人群個(gè)體B也在人群個(gè)體A的遇障速度空間的作用下得到修正速度，即。

不同于遇障速度算法（VO）從其他個(gè)體的遇障速度空間獲得最優(yōu)速度，互利速度障礙算法（RVO）結(jié)合當(dāng)前速度和其他個(gè)體的遇障速度空間，取求解結(jié)果的平均值作為最優(yōu)速度，數(shù)學(xué)表達(dá)式如下所示。

人群個(gè)體B相對(duì)于人群個(gè)體A的互利速度障礙空間是所有人群個(gè)體A當(dāng)前速度和處于速度障礙空間的速度均值的集合。

3 A＊算法

A*算法是一種啟發(fā)式的路徑搜索算法，使用啟發(fā)函數(shù)來(lái)指導(dǎo)最短路徑的計(jì)算。和Dijkstra算法一樣都能用于最短路徑的計(jì)算。但Dijkstra算法以起始節(jié)點(diǎn)為中心，無(wú)差別的擴(kuò)展鄰居節(jié)點(diǎn)，而A*算法則使用啟發(fā)函數(shù)h(n)來(lái)篩選鄰居，指導(dǎo)最短路徑的搜索過(guò)程，具有比Dijkstra算法更高的搜索效率。

A*算法的最短路徑的估值函數(shù)如下所示。

f（n）表示從出發(fā)點(diǎn)s出發(fā)經(jīng)過(guò)節(jié)點(diǎn)n，到達(dá)目標(biāo)點(diǎn)d的路徑長(zhǎng)度的預(yù)估值。g（n）表示的是從出發(fā)點(diǎn)s到節(jié)點(diǎn)n的路徑長(zhǎng)度，h（n）表示從節(jié)點(diǎn)n到目標(biāo)點(diǎn)d的估計(jì)路徑長(zhǎng)度，h（n）的值通常為節(jié)點(diǎn)n與目標(biāo)點(diǎn)d之間的曼頓距離。在A*算法中g(shù)（n）的計(jì)算通常如下所示。

A*算法的優(yōu)點(diǎn)是當(dāng)從起始點(diǎn)出發(fā)存在到目標(biāo)點(diǎn)的路徑時(shí)，A*算法一定能找到一條最優(yōu)的路徑。相比于Dijkstra算法對(duì)鄰居節(jié)點(diǎn)無(wú)差別的擴(kuò)展方式，可以很大程度上減少冗余節(jié)點(diǎn)，在效率上有很大提升。更適合于起始節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)都明確的計(jì)算場(chǎng)景。但是g（n）的計(jì)算方式只考慮了靜態(tài)的距離的因素影響，而沒(méi)有考慮其他人群個(gè)體的位置分布和運(yùn)動(dòng)方向?qū)β窂揭?guī)劃的影響，因此我們對(duì)A*算法的做了修改。

4 改進(jìn)的A＊算法

為了讓我們的系統(tǒng)能夠?qū)⑷巳哼\(yùn)動(dòng)方向和人群未來(lái)的位置分布納入考慮，我們將A*算法的代價(jià)方程由公式（3）改成公式（4）。

在公式（1）和公式（2）中，Cs是 A*算法正在處理的當(dāng)前所在的網(wǎng)格，Cd是網(wǎng)格Cs的鄰居網(wǎng)格，dist函數(shù)表示的是這兩個(gè)網(wǎng)格之間的歐氏距離。fuhao（Cd）代表了在網(wǎng)格Cd處的額外的潛在代價(jià)值。k是一個(gè)常數(shù)，用于調(diào)節(jié)額外代價(jià)的影響系數(shù)。

我們假設(shè)人群個(gè)體可以從水平，垂直4個(gè)方向進(jìn)入和離開(kāi)網(wǎng)格。每個(gè)網(wǎng)格保存4個(gè)方向的權(quán)重值，對(duì)于相鄰的網(wǎng)格表示人群個(gè)體從Cs到Cd的單位向量。那么網(wǎng)格Cd在方向上的權(quán)值記為的公式如下所示。

因此，當(dāng)考慮人群的移動(dòng)方向時(shí)，網(wǎng)格Cs移動(dòng)到網(wǎng)格Cd的代價(jià)函數(shù)更新為：

我們?cè)诳紤]將來(lái)的人群分布對(duì)全局路徑規(guī)劃的影響時(shí)，考慮到當(dāng)前規(guī)劃的路徑對(duì)其他人的路徑規(guī)劃的影響越小。因此，假設(shè)人群個(gè)體i規(guī)劃的全局路徑為，對(duì)于Pathi上的任意網(wǎng)格，都表明人群個(gè)體i會(huì)在將來(lái)的某個(gè)時(shí)刻到達(dá)該網(wǎng)格。因此，我們將影響從網(wǎng)格Ci0到網(wǎng)格Cin路徑上網(wǎng)格的權(quán)值依次遞減，其遞減值為：

其中BPrice為基準(zhǔn)值，Pathi對(duì)路徑上網(wǎng)格Ci權(quán)值的影響為：

因此，我們的網(wǎng)格Cs到Cd的代價(jià)函數(shù)為：

5 實(shí)驗(yàn)結(jié)果分析

本文在相同的硬件環(huán)境下使用了普通的A*算法（圖1）和經(jīng)本文改進(jìn)后的A*算法（圖2），對(duì)相同的初始場(chǎng)景和數(shù)量同為2000人的實(shí)驗(yàn)條件進(jìn)行疏散模擬。

圖1

圖2

[1]黃鵬，劉箴.一種RVO碰撞避免的人群仿真研究[J].計(jì)算機(jī)仿真，2012，29（11）:34-37.

[2]Jur Van den Berg,Ming Lin,Dinesh Manocha.Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation.In Robotics and Automation,2008.ICRA 2008.IEEE International Conference on,pages 1928-1935.IEEE,2008.

[3]Hart P E,Nilsson N J,Raphael B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].Systems Science and Cybernetics,IEEE Transactions on,1968,4（2）:100-107.

[4]Paolo Fiorini and Zvi Shiller.Motion Planning in Dynamic Environmentsusing Velocity Obstacles.The International Journal of Robotics Research,17（7）:760-772,1998.