稅斌

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

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

稅斌

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

0　引言

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

1　問題描述

為了描述簡單，我們假設(shè)模擬的場(chǎng)景為2D平面，平面底部被劃分為若干均勻的正方形網(wǎng)格。每個(gè)小的正方形網(wǎng)格S都有自己的位置坐標(biāo)CS（正方形的中點(diǎn)）。智能體全局尋路計(jì)算時(shí)，需要使用CS作為路徑的中間節(jié)點(diǎn)[2]。

2　A*全局尋路

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

在正方形網(wǎng)格平面模型中，g（S）表示從起點(diǎn)到任意網(wǎng)格S的實(shí)際代價(jià)，h（S）表示從網(wǎng)格S到目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)（heuristic Estimated Cost）。在每次循環(huán)中都選擇具有最小代價(jià)f（S）=g（S）+h（S）的網(wǎng)格點(diǎn)。在平面中有障礙物的情況下尋路結(jié)構(gòu)如圖1（b）所示。

圖1　

3　ORCA速度計(jì)算

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

如圖2（b）的灰色部分[1，4，5]。當(dāng)A相對(duì)于B的相對(duì)速度VA-VB∈VOTA|B時(shí)，會(huì)在T的時(shí)間內(nèi)發(fā)生碰撞。由此我們定義可以保證碰撞避免（Collision-avoiding）的速度區(qū)域：

VA-VB+u→（VA+u）-VB表示B的速度保持不變，使A的速度移動(dòng)u實(shí)現(xiàn)碰撞避免。

VB-VA-u→（VB-u）-VA表示A的速度保持不變，使B的速度移動(dòng)-u實(shí)現(xiàn)碰撞避免。

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

最后當(dāng)智能體A有很多鄰居的時(shí)候，對(duì)每個(gè)鄰居分別求出ORCA區(qū)域，并選擇位于各個(gè)ORCA交集區(qū)域內(nèi)的速度時(shí)，就能保證和所有的鄰居滿足碰撞避免。

圖2　

4　實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境為VS2008，同時(shí)使用Ogre完成程序的渲實(shí)驗(yàn)環(huán)境為VS2008，同時(shí)使用Ogre完成程序的渲染功能。在場(chǎng)景中模擬不同人數(shù)的人群運(yùn)動(dòng)過程。圖3 (a)和(b)展示了場(chǎng)景中有50個(gè)人時(shí)不同時(shí)刻的狀態(tài)，圖(c)和(d)展示了有100個(gè)人的情況下的運(yùn)行狀態(tài)。實(shí)驗(yàn)結(jié)果表明，系統(tǒng)滿足碰撞避免的要求，成功模擬的人群運(yùn)動(dòng)的過程。

圖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ìn)的多智能體碰撞避免行為[J].國防科技大學(xué)學(xué)報(bào),2013,35(3):92-98

[4]黃鵬,劉箴.一中RVO碰撞避免的人群仿真研究[J].計(jì)算機(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-），男，四川遂寧人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)

2015-11-24

2015-12-30

通過真實(shí)的模擬人群疏散過程，可以為人群密集的公共場(chǎng)所制定人群疏散計(jì)劃提供重要的依據(jù)。由于場(chǎng)景的復(fù)雜性以及人群行為不可預(yù)測(cè)性等特點(diǎn)，使得人群在選擇疏散路徑時(shí)存在多樣性的特點(diǎn)。為了真實(shí)的模擬人群疏散的過程，每個(gè)個(gè)體都基于場(chǎng)景采用統(tǒng)一的尋路方式，并使用ORCA方法在人群模擬中實(shí)現(xiàn)碰撞避免，保證模擬過程的真實(shí)性。通過實(shí)驗(yàn)?zāi)M效果。

人群模擬；碰撞避免；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.