Coverage Path Planning Algorithm Based on Centroidal Power Diagram

doi:10.16182/j.issn1004731x.joss.201705025

Abstract

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

CLC Number:

TP391.9

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.

References

[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.