质心Power图下覆盖路径规划算法

doi:10.16182/j.issn1004731x.joss.201705025

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (5): 1120-1124.doi: 10.16182/j.issn1004731x.joss.201705025

质心Power图下覆盖路径规划算法

郑利平, 程亚军, 路畅, 廖婷

合肥工业大学计算机与信息学院,安徽合肥 230009

收稿日期:2015-04-30 修回日期:2015-08-06 出版日期:2017-05-08 发布日期:2020-06-03
作者简介:郑利平(1978-),男,湖北,博士,教授,研究方向为可视化、群体和疏散仿真;程亚军(1990-),男,安徽,硕士生,研究方向为群体仿真。
基金资助:
国家自然科学基金(61300118),安徽省科技强警项目(1401b042009)

Coverage Path Planning Algorithm Based on Centroidal Power Diagram

Zheng Liping, Cheng Yajun, Lu Chang, Liao Ting

Schoolof Computer and Information, Hefei University of Technology, Hefei 230009, China

Received:2015-04-30 Revised:2015-08-06 Online:2017-05-08 Published:2020-06-03

摘要/Abstract

摘要： 覆盖路径规划算法广泛应用于移动传感网络、群机器人系统等领域。研究基于质心容量限制Power图下的覆盖算法,对经典Lloyd方法进行扩展,在生成质心Power图的Lloyd算法基础上,改进后得到可用于路径规划的PD-Lloyd算法,考虑实际场景中个体移动的物理特性,给出两种优化策略,以增强算法效果和可信性。实验证明：该算法稳定性好,具有内在避碰特性,能产生较优的运动路径。

关键词: Power图, 覆盖路径规划, Lloyd方法, 人群仿真

Abstract: Coverage path-planning algorithm is widely used in mobile sensor networks, multi-robot system, and other fields. The coverage path planning algorithm based on CCCPD(Centroidal Capacity Constrained Power Diagram) was studied. The classical Lloyd based generating method for Centroidal Power Diagram was extended to PD-Lloyd algorithm, which could be used for path-planning. Two optimizing strategies were proposed to enhance the credibility of the PD-Lloyd algorithm by considering the physical moving characteristics of individuals in the real scene. Experiments prove that the proposed algorithm has advantages of well stability and inherent collision-free characteristic, and can generate more optimal motion path.

Key words: Power diagram, coverage path planning, Lloyd method, crowd simulation

中图分类号:

TP391.9

郑利平, 程亚军, 路畅, 廖婷. 质心Power图下覆盖路径规划算法[J]. 系统仿真学报, 2017, 29(5): 1120-1124.

Zheng Liping, Cheng Yajun, Lu Chang, Liao Ting. Coverage Path Planning Algorithm Based on Centroidal Power Diagram[J]. Journal of System Simulation, 2017, 29(5): 1120-1124.

参考文献

[1] Huang T, Kapadia M, Badler N I, et al.Path planning for coherentand persistent groups[C]// Robotics and Automation (ICRA), 2014 IEEE International Conference on. USA: IEEE, 2014: 1652-1659.
[2] 任治国, 盖文静, 金嘉磊, 等. 面向动态场景视频的虚拟行人路径规划[J]. 计算机辅助设计与图形学学报, 2013, 25(4): 433-441.
(Ren Z G, Gai W J, Jin J L, et al.Dynamic Path Planning of Virtual Pedestrian in a Real Scene Video[J]. Journal of Computer-Aided Design and Computer Graphics, 2013, 25(4): 433-441.)
[3] Niederberger C, Radovic D, Gross M.Generic path planning for real-time applications[C]// Computer Graphics International, Proceedings. USA: IEEE, 2004: 299-306.
[4] Sud A, Gayle R, Andersen E, et al.Real-time navigation of independent agents using adaptive roadmaps[C]// Virtual Reality Software and Technology, ACM Symposium on, USA: ACM, 2007: 99-106.
[5] Kavraki L E, Svestka P, Latombe J C, et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. Robotics and Automation, IEEE Transactions on (S1042-296X), 1996, 12(4): 566-580.
[6] Balch T, Hybinette M.Social potentials for scalable multi-robot formations[C]// Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on. USA: IEEE, 2000, 1: 73-80.
[7] Reif J H, Wang H.Social potential fields: A distributed behavioral control for autonomous robots[J]. Robotics and Autonomous Systems (S0921-8890), 1999, 27(3): 171-194.
[8] Cortes J, Martinez S, Karatas T, et al.Coverage control for mobile sensing networks[C]// Robotics and Automation, 2002. Proceedings. ICRA'02. IEEE International Conference on. USA: IEEE, 2002, 2: 1327-1332.
[9] Du Q, Faber V, Gunzburger M.CentroidalVoronoi tessellations: applications and algorithms[J]. SIAM Review, 1999, 41(4): 637-676.
[10] Lloyd S.Least squares quantization in PCM[J]. Information Theory, IEEE Transactions on (S0018-9448), 1982, 28(2): 129-137.
[11] 吴壮志, 杨钦. Power 图的性质及构造算法研究[J]. 计算机辅助设计与图形学学报, 2001, 13(12): 1057-1062.
(Wu Z Z, Yang Q.Research on Properties of Power Diagram andIts Construction Algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 2001, 13(12): 1057-1062.)
[12] Balzer M.Capacity-constrained Voronoi diagrams in continuous spaces[C]// Voronoi Diagrams, 2009. ISVD'09. Sixth International Symposium on. USA: IEEE, 2009: 79-88.

质心Power图下覆盖路径规划算法

Coverage Path Planning Algorithm Based on Centroidal Power Diagram

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	李弋豪, 黄天羽, 李鹏, 丁刚毅. 基于密集人群的表演行为建模与仿真方法研究[J]. 系统仿真学报, 2021, 33(7): 1617-1625.
[2]	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.
[3]	费月, 桂志强, 姚裕友, 徐本柱, 郑利平. 面状LED发光体灯珠分布和组合连接优化算法[J]. 系统仿真学报, 2020, 32(12): 2317-2323.
[4]	郑利平, 路畅, 蔡瑞文, 桂志强. 质心容量限制Power图一体化生成算法[J]. 系统仿真学报, 2018, 30(7): 2489-2496.
[5]	甘文洋, 朱大奇. 基于行为策略的AUV全覆盖信度函数路径规划算法[J]. 系统仿真学报, 2018, 30(5): 1857-1868.
[6]	刘婷婷, 刘箴, 柴艳杰, 刘翠娟, 陈佳鑫. 一种基于心理学模型的人群踩踏情景仿真方法[J]. 系统仿真学报, 2016, 28(10): 2448-2454.
[7]	方昊, 刘箴, 陆涛, 刘良平, 刘婷婷, 刘翠娟. 突发事件中人群跟随现象的一种仿真模型[J]. 系统仿真学报, 2015, 27(10): 2432-2438.