Multi-UAV coverage path planning based on optimization of convex division of complex plots

XUE Zhentao; CHEN Jian; ZHANG Zichao; LIU Xuzan; MIAO Xiansheng; HU Gui

doi:10.7527/S1000-6893.2021.25990

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

2022 , Vol. 43 >Issue 12: 325990 - 325990

DOI: https://doi.org/10.7527/S1000-6893.2021.25990

Electronics and Electrical Engineering and Control

Multi-UAV coverage path planning based on optimization of convex division of complex plots

XUE Zhentao ,
CHEN Jian ,
ZHANG Zichao ,
LIU Xuzan ,
MIAO Xiansheng ,
HU Gui

Expand

1. College of Engineering, China Agricultural University, Beijing 100083, China;
2. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China

Received date: 2021-06-18

Revised date: 2021-08-04

Online published: 2021-10-09

Supported by

National Natural Science Foundation of China (51979275); Open Fund of Key Laboratory of Spatial-temporal Big Data Analysis and Application of Natural Resources in Megacities, MNR (KFKT-2022-05); National Key R&D Program of China (2018YFD0700603); Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Natural Resources (KF-2021-06-115); Open Project Program of State Key Laboratory of Virtual Reality Technology and Systems, Beihang University (VRLAB2022C10); Jiangsu Province and Education Ministry Co-sponsored Synergistic Innovation Center of Modern Agricultural Equipment (XTCX2002); Jilin Province Key R&D Plan Project (20180201036SF); Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (19R06); 2115 Talent Development Program of China Agricultural University

Fold

Abstract

Full coverage path planning is one of the important contents of unmanned system path planning. With the continuous development of Unmanned Aerial Vehicle(UAV) technology, UAV full coverage path planning has been importantly used in many fields. However, in this process, no-fly zones and obstacles often appear, and path planning needs to be carried out to ensure flight safety and flight efficiency. Based on convex partition optimization, this paper proposes a full coverage path planning method for complex plots with complex obstacles, which reduces the length of the coverage path and the total time of the coverage path. Complex plots often contain smooth curves or rugged inner-concave boundary contours. This article first uses an improved Douglas-Peucker algorithm to compress complex plot boundaries into complex polygonal boundaries, and then uses convex-concave points to test the vertices. Then, the shortest main line direction is identified by rotating the main line, and then Probabilistic Roadmaps(PRM) is used to find the shortest auxiliary line. Four convex division strategies are employed to optimize the convex division of the complex land, so that the UAV can be in the full coverage process, with shorter middle path and higher work efficiency. Finally, computer simulations on the test plots are performed to achieve the overall path ratio of 67.6% and 54.9%. The proposed method is compared with other convex partition optimization algorithms for the same map, showing that our method outperforms other methods in terms of path length and planning time.

Key words： complete coverage path planning; multi-UAVs; complex plot; complex obstacle; convex partition optimization; improved Douglas-Peucker algorithm; probabilistic roadmaps method

Cite this article

XUE Zhentao , CHEN Jian , ZHANG Zichao , LIU Xuzan , MIAO Xiansheng , HU Gui . Multi-UAV coverage path planning based on optimization of convex division of complex plots[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022 , 43(12) : 325990 -325990 . DOI: 10.7527/S1000-6893.2021.25990

References

[1] 徐博, 徐旻, 陈立平, 等. 智能机械全覆盖路径规划算法综述[J]. 计算机测量与控制, 2016, 24(10):1-5, 53. XU B, XU M, CHEN L P, et al. Review on coverage path planning algorithm for intelligent machinery[J]. Computer Measurement & Control, 2016, 24(10):1-5, 53(in Chinese).
[2] MAC T T, COPOT C, TRAN D T, et al. Heuristic approaches in robot path planning:A survey[J]. Robotics and Autonomous Systems, 2016, 86:13-28.
[3] 陶德臣, 祖家奎, 高尚文. 基于全覆盖路径的植保无人直升机航线规划方法与实现技术[J]. 电子测量技术, 2020, 43(7):50-55, 166. TAO D C, ZU J K, GAO S W. Planning method and implementation technology of plant protection unmanned helicopter route based on full coverage path[J]. Electronic Measurement Technology, 2020, 43(7):50-55, 166(in Chinese).
[4] WU Y, WU S B, HU X T. Multi-constrained cooperative path planning of multiple drones for persistent surveillance in urban environments[J]. Complex & Intelligent Systems, 2021, 7(3):1633-1647.
[5] ZHANG H M, HONG W, CHEN M J. A path planning strategy for intelligent sweeping robots[C]//2019 IEEE International Conference on Mechatronics and Automation. Piscataway:IEEE Press,2019:11-15.
[6] 王术波, 韩宇, 陈建, 等. 基于ADRC迭代学习控制的四旋翼无人机姿态控制[J]. 航空学报, 2020, 41(12):324112. WANG S B, HAN Y, CHEN J, et al. Active disturbance rejection control of UAV attitude based on iterative learning control[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(12):324112(in Chinese).
[7] 杨俊成, 李淑霞, 蔡增玉. 路径规划算法的研究与发展[J]. 控制工程, 2017, 24(7):1473-1480. YANG J C, LI S X, CAI Z Y. Research and development of path planning algorithm[J]. Control Engineering of China, 2017, 24(7):1473-1480(in Chinese).
[8] ZHAO Y J, ZHENG Z, LIU Y. Survey on computational-intelligence-based UAV path planning[J]. Knowledge-Based Systems, 2018, 158:54-64.
[9] 刘洋成, 耿端阳, 兰玉彬, 等. 基于自动导航的农业装备全覆盖路径规划研究进展[J]. 中国农机化学报, 2020, 41(11):185-192. LIU Y C, GENG D Y, LAN Y B, et al. Research progress of agricultural equipment full coverage path planning based on automatic navigation[J]. Journal of Chinese Agricultural Mechanization, 2020, 41(11):185-192(in Chinese).
[10] 于靖, 陈刚, 张笑, 等. 面向自然岸线抽稀的改进道格拉斯-普克算法[J]. 测绘科学, 2015, 40(4):23-27, 33. YU J, CHEN G, ZHANG X, et al. An improved Douglas-Peucker algorithm oriented to natural shoreline simplification[J]. Science of Surveying and Mapping, 2015, 40(4):23-27, 33(in Chinese).
[11] 李星烨. 多无人机协同区域搜索关键技术研究[D]. 成都:电子科技大学, 2020. LI X Y. Research on technologies of multi-UAV cooperative area search[D]. Chengdu:University of Electronic Science and Technology of China, 2020(in Chinese).
[12] 吴青坡, 周绍磊, 闫实. 复杂区域多UAV覆盖侦察方法研究[J]. 战术导弹技术, 2016(1):50-55, 63. WU Q P, ZHOU S L, YAN S. Multi-UAVs cooperative coverage reconnaissance in complex area[J]. Tactical Missile Technology, 2016(1):50-55, 63(in Chinese).
[13] 陈海, 何开锋, 钱炜祺. 多无人机协同覆盖路径规划[J]. 航空学报, 2016, 37(3):928-935. CHEN H, HE K F, QIAN W Q. Cooperative coverage path planning for multiple UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3):928-935(in Chinese).
[14] 戴健, 许菲, 陈琪锋. 多无人机协同搜索区域划分与路径规划[J]. 航空学报, 2020, 41(S1):723770. DAI J, XU F, CHEN Q F. Multi-UAV cooperative search on region division and path planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1):723770(in Chinese).
[15] VINH K, GEBREYOHANNES S, KARIMODDINI A. An area-decomposition based approach for cooperative tasking and coordination of UAVs in a search and coverage mission[C]//2019 IEEE Aerospace Conference. Piscataway:IEEE Press,2019:1-8.
[16] NIELSEN L D, SUNG I, NIELSEN P. Convex decomposition for a coverage path planning for autonomous vehicles:interior extension of edges[J]. Sensors, 2019, 19(19):4165.
[17] RANTANEN M T, JUHOLA M. How to construct small probabilistic roadmaps with a good coverage?[J]. Advanced Robotics, 2014, 28(22):1519-1531.
[18] LE A V, NHAN N H K, MOHAN R E. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots[J]. Sensors (Basel, Switzerland), 2020, 20(2):445.
[19] 阚平, 姜兆亮, 刘玉浩, 等. 多植保无人机协同路径规划[J]. 航空学报, 2020, 41(4):323610. KAN P, JIANG Z L, LIU Y H, et al. Cooperative path planning for multi-sprayer-UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(4):323610(in Chinese).
[20] 周林娜, 汪芸, 张鑫, 等. 矿区废弃地移动机器人全覆盖路径规划[J]. 工程科学学报, 2020, 42(9):1220-1228. ZHOU L N, WANG Y, ZHANG X, et al. Complete coverage path planning of mobile robot on abandoned mine land[J]. Chinese Journal of Engineering, 2020, 42(9):1220-1228(in Chinese).
[21] 李楷, 陈永府, 金志勇, 等. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学, 2019, 41(7):1227-1235. LI K, CHEN Y F, JIN Z Y, et al. A full coverage path planning algorithm based on backtracking method[J]. Computer Engineering & Science, 2019, 41(7):1227-1235(in Chinese).
[22] HASSAN M, LIU D K. PPCPP:A predator-prey-based approach to adaptive coverage path planning[J]. IEEE Transactions on Robotics, 2020, 36(1):284-301.
[23] GUO T, JIANG N, LI B Y, et al. UAV navigation in high dynamic environments:A deep reinforcement learning approach[J]. Chinese Journal of Aeronautics, 2021, 34(2):479-489.
[24] LIU Y, ZHANG X J, ZHANG Y, et al. Collision free 4D path planning for multiple UAVs based on spatial refined voting mechanism and PSO approach[J]. Chinese Journal of Aeronautics, 2019, 32(6):1504-1519.
[25] QU C Z, GAI W D, ZHANG J, et al. A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle (UAV) path planning[J]. Knowledge-Based Systems, 2020, 194:105530.
[26] LIU W, ZHENG Z, CAI K Y. Bi-level programming based real-time path planning for unmanned aerial vehicles[J]. Knowledge-Based Systems, 2013, 44:34-47.
[27] 杜楠楠, 陈建, 马奔, 等. 多太阳能无人机覆盖路径优化方法[J]. 航空学报, 2021, 42(6):324476. DU N N, CHEN J, MA B, et al. Optimization method for coverage path planning of multi-solar powered UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(6):324476(in Chinese).

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References