关键词: 人群疏散, 路径优化, KD树, 三维模拟, 速度障碍物

Abstract: 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.

Key words: crowd evacuation, path optimization, KD tree, 3D simulation, Velocity Obstacle (VO)