基于Voronoi图的实时人群路径规划  

Voronoi-Based Real-Time Crowd Path Planning

作　　者：尹宝才[1] 徐振华[1] 孔德慧[1] 肖小芳[1] 

机构地区：[1]北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室,北京100124

出　　处：《北京工业大学学报》2009年第8期1115-1121,共7页Journal of Beijing University of Technology

基　　金：北京市自然科学基金资助项目(4061001);国家科技攻关项目资助(2005BA904B09);北京市教育委员会科技发展计划面上项目资助(KM200710005017;KM200710005023)

摘　　要：为了实现在人群路径规划中避碰操作,作者提出了一种基于GPU高效计算特性的实时离散Voronoi图计算方法,并建立了一种基于Voronoi图的人群路径规划方案.利用Voronoi图对平面按照欧式距离进行划分的特性,并通过将每个虚拟人的Voronoi区域作为其活动范围,使每个虚拟人都限制在自己的区域内活动,从而在人群路径规划中避免了为虚拟人进行碰撞检测的复杂操作.In order to perform the collision avoidance,a new algorithm is introduced to make use of the high effectiveness of GPU to compute the discrete Voronoi diagram in real-time.And a solution for crowd path navigation based Voronoi diagram is presented.By making use of the ability that the Voronoi diagram partitions the space according to the Euclidean metric,the path planning with collision avoidance is achieved by forbidding agents to move outside their Voronoi regions.

关 键 词：GPU VORONOI图 虚拟人 人群路径规划 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]