基于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.