基于ORCA碰撞避免的人群疏散模擬

稅斌

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

基于ORCA碰撞避免的人群疏散模擬

稅斌

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

0　引言

隨著我國城市化進程的推進，例如超市、廣場、學校等人群密集的公共場所也越來越多。如何制定正確的人群疏散計劃，在突發事件時實現人群快速、安全疏散，將生命財產損失降到最低成為了一個亟待解決的難題。同時，由于公共場所場景的復雜性以及人群運動過程的不可預測性等特點，人群疏散模擬仍然是一個具有挑戰性的難題。一般的模擬方法是對人群進行持續的導航，循環的檢測周圍環境的變化。每次循環中每個個體都根據周圍的環境做出相應的調整。在這種方法中全局尋路和局部碰撞避免經常是分開實現的。比較典型的是，通過全局尋路確定到目標位置整體的方向，而通過本地導航實現與場景中其他人以及靜態障礙物的碰撞避免[1]。通過全局尋路以及局部導航實現真實人群模擬。1群仿真領域，人群被定義為可以感知周圍環境，同時通過選擇適當的速度，實現與其他人以及靜態障礙物的碰撞避免，并最終到達目的地的智能體。因此在人群導航模擬中，需要實現多智能體的全局尋路與多智能體的局部碰撞避免。

1　問題描述

為了描述簡單，我們假設模擬的場景為2D平面，平面底部被劃分為若干均勻的正方形網格。每個小的正方形網格S都有自己的位置坐標CS（正方形的中點）。智能體全局尋路計算時，需要使用CS作為路徑的中間節點[2]。

2　A*全局尋路

A*是全局尋路算法中最流行的一種.A*能精確地找出最短路徑，同時，作為一種啟發式的算法，它的速度也和貪心的最佳有限搜索算法相差無幾。

在正方形網格平面模型中，g（S）表示從起點到任意網格S的實際代價，h（S）表示從網格S到目標點的啟發式評估代價（heuristic Estimated Cost）。在每次循環中都選擇具有最小代價f（S）=g（S）+h（S）的網格點。在平面中有障礙物的情況下尋路結構如圖1（b）所示。

圖1　

3　ORCA速度計算

其中，P、R分別為表示智能體的圓的圓形和半徑。有：

如圖2（b）的灰色部分[1，4，5]。當A相對于B的相對速度VA-VB∈VOTA|B時，會在T的時間內發生碰撞。由此我們定義可以保證碰撞避免（Collision-avoiding）的速度區域：

VA-VB+u→（VA+u）-VB表示B的速度保持不變，使A的速度移動u實現碰撞避免。

VB-VA-u→（VB-u）-VA表示A的速度保持不變，使B的速度移動-u實現碰撞避免。

那么在一輪計算中A與B分別需要移動u與-u的向量。那對VA-VB最后移動的過程可以寫作（VA+u）-（VB-u）→（VA+2u）-VB，相當于VA移動了2u的距離，為了使A與B的移動距離最小，讓當A與B分別移動u/ 2與-u/2的向量。

最后當智能體A有很多鄰居的時候，對每個鄰居分別求出ORCA區域，并選擇位于各個ORCA交集區域內的速度時，就能保證和所有的鄰居滿足碰撞避免。

圖2　

4　實驗結果

實驗環境為VS2008，同時使用Ogre完成程序的渲實驗環境為VS2008，同時使用Ogre完成程序的渲染功能。在場景中模擬不同人數的人群運動過程。圖3 (a)和(b)展示了場景中有50個人時不同時刻的狀態，圖(c)和(d)展示了有100個人的情況下的運行狀態。實驗結果表明，系統滿足碰撞避免的要求，成功模擬的人群運動的過程。

圖3　

[1]Berg,J.,Lin,M.,Manocha,D.:Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation[C].In:Proceedings of the International Conference on Robotics and Automation,ICRA,2008

[2]Ozcan,C.Y.,Haciomeroglu,M.:A Path-based Multi-Agent Navigation Model[J].The Visual Computer，2015，31(6):863-872.

[3]李猛,梁加紅,李石磊.一中改進的多智能體碰撞避免行為[J].國防科技大學學報,2013,35(3):92-98

[4]黃鵬,劉箴.一中RVO碰撞避免的人群仿真研究[J].計算機仿真,2012,29(11):34-37.

[5]P.Fiorini,Z.Shiller:Motion Planning in Dynamic Environments Using the Relative Velocity Paradigm[C].IEEE Int.Conference on Robotics and Automation,1993:560-565.

Crowd Simulation;Collision Avoid;ORCA;A*

Crowd Evacuate Simulation Based on ORCA Collision Avoidance

SHUI Bin
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2016）02-0073-03

10.3969/j.issn.1007-1423.2016.02.017

稅斌（1990-），男，四川遂寧人，碩士研究生，研究方向為計算機圖形學、虛擬現實

2015-11-24

2015-12-30

通過真實的模擬人群疏散過程，可以為人群密集的公共場所制定人群疏散計劃提供重要的依據。由于場景的復雜性以及人群行為不可預測性等特點，使得人群在選擇疏散路徑時存在多樣性的特點。為了真實的模擬人群疏散的過程，每個個體都基于場景采用統一的尋路方式，并使用ORCA方法在人群模擬中實現碰撞避免，保證模擬過程的真實性。通過實驗模擬效果。

人群模擬；碰撞避免；ORCA；A*尋路

Through the actual simulation of crowd evacuation process,it can provide an important basis for the crowd evacuation plan.Because of the complexity of the scene and the unpredictable nature of the crowd’s behavior,the characteristics are diversity of the population in choosing the evacuation route.In order to simulate the crowd evacuation process,each individual is based on the scene using a unified approach,and the use of ORCA method in the simulation of the collision avoidance,to ensure the authenticity of the simulation process. And experiment shows the simulation results.