Global path planning based reciprocal velocity obstacles method for crowd evacuation
HUANG Yangyu1,HU Wei1,YUAN Guodong2
1. College of Information Sciences and Technology, Beijing University of Chemical Technology, Beijing 100029, China
2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
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.
SNAPE J, van den BERG J, GUY S J, et al. Smooth and collision-free navigation for multiple robots under differential-drive constraints［C］// IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2010: 4584-4589.
[2]
van den BERG J, GUY S J, LIN M, et al. Reciprocal n-body collision avoidance［C］// Proceedings of the 14th International Symposium on International Symposium of Robotics Research. Berlin: Springer, 2011:3-19.
[3]
van den BERG J, ABBEEL P, GOLDBERG K. LQG-MP: optimized path planning for robots with motion uncertainty and imperfect state information［J］. The International Journal of Robotics Research, 2011,30(7):895-913.
[4]
HELBING D, VICSEK T. Optimal self-organization［J］. New Journal of Physics, 1999,1(3):1-13.
[5]
HELBING D, FARKAS I, VICSEK T, et al. Simulating dynamical features of escape panic［J］. Nature, 2000,407(6803):487-490.
[6]
HELBING D, BUZNA L, JOHANSSON A, et al. Self-organized pedestrian crowd dynamics: experiments, simulations, and design solutions［J］. Transportation Science, 2005,39(1):1-24.
HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths in graphs［J］. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
WALD I, HAVRAN V. On building fast kd-trees for ray tracing, and on doing that in O(N log N)［C］// Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. Piscataway: IEEE, 2006:61-69.
[11]
ZHOU K, HOU Q,WANG R, et al. Real-time kd-tree construction on graphics hardware［J］. ACM Transactions on Graphics,2008,27(5):1-11.
[12]
HUNT W, MARK W R, STOLL G, et al. Fast KD-tree construction with an adaptive error-bounded heuristic［C］// Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. Piscataway: IEEE, 2006:81-88.
2013, Vol. 33 
