基于RVO的人群運動路徑規劃

徐梓桉

（四川大學計算機學院，成都 610065）

0 引言

人群疏散對建筑設計和城市規劃有重要的意義。一個設計良好的疏散方案包括一個在短時間內幫助人群到達出口的疏散指導。由于人群分布可以根據某些事件進行估計，例如音樂會和新年慶祝，因此疏散方向標志可以在人群聚集在一個地方前設置好逃生方向標志。此外,隨著監測照相機和傳感器網絡變得越來越多最近，對人群的動態估計分布允許我們的系統動態反應,提高其有效性。

人群模擬比較典型的做法是通過全局尋路確定到目標點宏觀的路徑，然后通過局部的導航點和碰撞避免來獲取實際的速度[1]。我們在本文中提出了一個全新的策略來規劃全局路徑。我們的方法產生的結果比基于智能體的單純的目標導向的導航模型更有可信度。該模型有一個額外的過程階段，實驗表明，該系統具有較好的仿真效果，甚至在擁擠的場景中也能提高效率提前避免擁擠。

1 系統概述

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

2 RVO算法

我們使用尋路算法規劃得到的路徑能夠使得人群能夠在全局范圍內通過階段性的導航位置來找到合適的路徑和傾向速度。但是，路徑規劃是以人群個體為計算單位的，路徑規劃過程中并沒有將其他的運動個體作為障礙物來考慮，因此路徑規劃的結果并不能保證人群之間的路徑不會有交叉而導致運動過程中的碰撞和穿透重疊。因此，需要碰撞避免算法在運動過程中對路徑規劃的結果進行修正。碰撞避免算法是通過將速度修正的邏輯使得所有在△t時間內的人群個體的速度運動位置不會發生碰撞和穿透重疊的現象[3]。

在所有碰撞避免的實現方法中，Fiorini等人提出遇障速度空間算法Velocity Obstacles[4]來解決該問題。人群個體A以速因此當個體A繼續以速度運動將會與人群個體B發生碰撞。在遇障速度算法作用下，人群個體A在人群個體B的遇障速度空間作用下得到修正速度，即；同理人群個體B也在人群個體A的遇障速度空間的作用下得到修正速度，即。

不同于遇障速度算法（VO）從其他個體的遇障速度空間獲得最優速度，互利速度障礙算法（RVO）結合當前速度和其他個體的遇障速度空間，取求解結果的平均值作為最優速度，數學表達式如下所示。

人群個體B相對于人群個體A的互利速度障礙空間是所有人群個體A當前速度和處于速度障礙空間的速度均值的集合。

3 A＊算法

A*算法是一種啟發式的路徑搜索算法，使用啟發函數來指導最短路徑的計算。和Dijkstra算法一樣都能用于最短路徑的計算。但Dijkstra算法以起始節點為中心，無差別的擴展鄰居節點，而A*算法則使用啟發函數h(n)來篩選鄰居，指導最短路徑的搜索過程，具有比Dijkstra算法更高的搜索效率。

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

f（n）表示從出發點s出發經過節點n，到達目標點d的路徑長度的預估值。g（n）表示的是從出發點s到節點n的路徑長度，h（n）表示從節點n到目標點d的估計路徑長度，h（n）的值通常為節點n與目標點d之間的曼頓距離。在A*算法中g（n）的計算通常如下所示。

A*算法的優點是當從起始點出發存在到目標點的路徑時，A*算法一定能找到一條最優的路徑。相比于Dijkstra算法對鄰居節點無差別的擴展方式，可以很大程度上減少冗余節點，在效率上有很大提升。更適合于起始節點、目標節點都明確的計算場景。但是g（n）的計算方式只考慮了靜態的距離的因素影響，而沒有考慮其他人群個體的位置分布和運動方向對路徑規劃的影響，因此我們對A*算法的做了修改。

4 改進的A＊算法

為了讓我們的系統能夠將人群運動方向和人群未來的位置分布納入考慮，我們將A*算法的代價方程由公式（3）改成公式（4）。

在公式（1）和公式（2）中，Cs是 A*算法正在處理的當前所在的網格，Cd是網格Cs的鄰居網格，dist函數表示的是這兩個網格之間的歐氏距離。fuhao（Cd）代表了在網格Cd處的額外的潛在代價值。k是一個常數，用于調節額外代價的影響系數。

我們假設人群個體可以從水平，垂直4個方向進入和離開網格。每個網格保存4個方向的權重值，對于相鄰的網格表示人群個體從Cs到Cd的單位向量。那么網格Cd在方向上的權值記為的公式如下所示。

因此，當考慮人群的移動方向時，網格Cs移動到網格Cd的代價函數更新為：

我們在考慮將來的人群分布對全局路徑規劃的影響時，考慮到當前規劃的路徑對其他人的路徑規劃的影響越小。因此，假設人群個體i規劃的全局路徑為，對于Pathi上的任意網格，都表明人群個體i會在將來的某個時刻到達該網格。因此，我們將影響從網格Ci0到網格Cin路徑上網格的權值依次遞減，其遞減值為：

其中BPrice為基準值，Pathi對路徑上網格Ci權值的影響為：

因此，我們的網格Cs到Cd的代價函數為：

5 實驗結果分析

本文在相同的硬件環境下使用了普通的A*算法（圖1）和經本文改進后的A*算法（圖2），對相同的初始場景和數量同為2000人的實驗條件進行疏散模擬。

圖1

圖2

[1]黃鵬，劉箴.一種RVO碰撞避免的人群仿真研究[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.