基于全局路径规划的相互速度障碍物人群疏散方法

针对相互速度障碍物（RVO）模型缺少全局路径规划，只依靠局部碰撞避免不能很好地模拟复杂的疏散场景问题，提出了一种剩余路径代价尽量小的动态全局路径选择方法。该方法包含路径预处理和路径实时更新两部分:第一部分使用快速最短路径算法（SPFA）求取场景最短路径（SSP）;第二部分根据SSP快速动态地计算每个个体的最优疏散路径，并使用KD树优化障碍物阻挡判断过程。最后将方法扩展到多楼层、多障碍物、多通道、多出口的复杂场景实现了近千人的仿真实验。实验结果表明，该方法在多个场景中都取得了良好的路径规划效果。

Global path planning based reciprocal velocity obstacles method for crowd evacuation

Reciprocal Velocity Obstacles (RVO) can process collision avoiding between large-scale agents, and be used in many crowd simulation engines. However, due to the lack of optimized path planning, it is difficult for RVO to simulate crowd evacuation in complicated environment. In this paper, based on RVO mechanism, a new global optimal path planning method, comprising path preprocessing and dynamical computation, was proposed for crowd evacuation simulation in complicated environment. SPFA (Shortest Path Faster Algorithm) algorithm was firstly used for pre-calculating SSP (Scene Shortest Path), and then the SSP was utilized to compute optimized evacuation path for each Agent in complicated scenes in real-time. KD tree (K-Dimension tree) was also used to further improve processing performance. Some examples demonstrate that the method can do well in global path planning for large-scale crowd evacuation in complicated scenes, especially in multi-floor, multi-obstacle, multi-stair, and multi-outlet scenes.