[1]李晓娜,孙立博,秦文虎.虚拟人群仿真的路径规划新算法[J].东南大学学报(自然科学版),2011,41(2):420-424.[doi:10.3969/j.issn.1001-0505.2011.02.039]
 Li Xiaona,Sun Libo,Qin Wenhu.New path planning algorithm for crowd simulation[J].Journal of Southeast University (Natural Science Edition),2011,41(2):420-424.[doi:10.3969/j.issn.1001-0505.2011.02.039]
点击复制

虚拟人群仿真的路径规划新算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
41
期数:
2011年第2期
页码:
420-424
栏目:
计算机科学与工程
出版日期:
2011-03-20

文章信息/Info

Title:
New path planning algorithm for crowd simulation
作者:
李晓娜1孙立博2秦文虎1
(1东南大学仪器科学与工程学院,南京 210096)
(2天津大学计算机科学与技术学院,天津 300072)
Author(s):
Li Xiaona1Sun Libo2Qin Wenhu1
(1School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)
(2School of Computer Science and Technology, Tianjin University, Tianjin 300072, China)
关键词:
路径规划相对速度障碍物Delaunay三角形单元入口图
Keywords:
path planning reciprocal velocity obstacle Delaunay triangulation cell and portal graphs
分类号:
TP391.9
DOI:
10.3969/j.issn.1001-0505.2011.02.039
摘要:
提出了一种用于虚拟人群仿真的路径规划新算法.该算法由全局路径规划模块和局部避碰模块组成.全局路径规划模块利用具有最短距离约束的Delaunay三角形方法分割虚拟环境,并由具有距离信息的单元入口图进行表示; 局部避碰模块利用相互速度障碍物方法,并加入了停止规则.实验结果表明:通过对具有距离信息的单元入口图的遍历可获得并存储具有最短距离值的路径,个体通过查询该图即可获得有效全局疏散路径从而实现全局导航; 相互速度障碍物方法实现了虚拟人之间,虚拟人与静态障碍物之间的避碰,而停止规则的运用彻底消除了抖动现象.该路径规划新算法实时模拟了人群疏散的运动过程,较真实地再现了疏散特性.
Abstract:
A new path planning algorithm for crowd simulation is proposed in this paper. The algorithm is composed of global path planning module and local obstacle avoidance module. The former is achieved by Delaunay triangulation method with shortest distance constraints for the subdivision of virtual environment, which can be depicted in distance weighted cell and portal graph; while the latter is realized by using reciprocal velocity obstacle approach with stop rule. Results show that shortest paths are gained and stored after traversing the entire graph, which are queried by individuals to get optimal path for global navigation. Obstacle avoidance among virtual characters or between virtual character and static obstacle is realized by reciprocal velocity obstacle approach. In addition stop rule is integrated to eliminate vibration. The new path planning algorithm can be used for the simulation of crowd evacuation process in real time, which shows the good performance for crowd evacuation.

参考文献/References:

[1] Masehian E,Sedighizadeh D.Classic and heuristic approaches in robot motion planning-a chronological review [C]//Proceedings of World Academy of Science,Engineering and Technology.Berlin,Germany,2007:101-106.
[2] Salomon B,Garber M,Lin M C,et al.Interactive navigation in complex environments using path planning [C]//Proceedings of ACM Symposium on Interactive 3D Graphics.Monterey,CA,USA,2003:41-50.
[3] Oskam T,Sumner R W,Thuerey N,et al.Visibility transition planning for dynamic camera control [C]//Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation.New Orleans,LA,USA,2009:55-65.
[4] Niederberger C,Radovic D,Gross M.Generic path planning for real-time applications [C]//Proceedings of Computer Graphics International. Crete,Greece,2004:299-306.
[5] Lamarche F,Donikian S.Crowd of virtual humans:a new approach for real time navigation in complex and structured environments [J].Computer Graphics Forum,2004,23(3):509-518.
[6] Gloor C,Stucki P,Nagel K.Hybrid techniques for pedestrian simulations [M].New York:Springer-Verlag,2004.
[7] Helbing D,Buzna L,Johasson A,et al.Self-organized pedestrian crowd dynamics:experiments,simulation,and design solution[J].Transportation Science,2005,39(1):1-24.
[8] Shewchuk J R.Triangle:engineering a 2D quality mesh generator and Delaunay triangulator [M]//Lin M C,Manocha D.First Workshop on Applied Computational Geometry.Philadelphia,PA,USA,1996:203-222.
[9] van den Berg J,Lin M,Manocha D.Reciprocal velocity obstacles for real-time multi-agent navigation [C]//Proceedings of IEEE Conference on Robotics and Automation.Pasadena,CA,USA,2008:1928-1935.
[10] Fiorini P,Shiller Z.Motion planning in dynamic environments using velocity obstacles[J].The International Journal of Robotics Research,1998,17(7):760-772.

相似文献/References:

[1]谈士力,万德钧,龚振邦.真空气吸附壁面行走机器人动态路径规划[J].东南大学学报(自然科学版),1996,26(5):88.[doi:10.3969/j.issn.1001-0505.1996.05.017]
 Tan Shili,Wan Dejun,Gong Zhenbang,et al.Dynamic Path Planning of Mobile Robot Capable of Moving on the Vertical Wall Surface by Vacuum Adhering[J].Journal of Southeast University (Natural Science Edition),1996,26(2):88.[doi:10.3969/j.issn.1001-0505.1996.05.017]

备注/Memo

备注/Memo:
作者简介:李晓娜(1983—),女,博士生;秦文虎(联系人),男,博士,教授,博士生导师,qinwenhu@seu.edu.cn .
基金项目:上海市科委基金资助项目(08515810202)、江苏省社会发展基金资助项目(BE2009662).
引文格式: 李晓娜,孙立博,秦文虎.虚拟人群仿真的路径规划新算法[J].东南大学学报:自然科学版,2011,41(2):420-424.[doi:10.3969/j.issn.1001-0505.2011.02.039]
更新日期/Last Update: 2011-03-20