基于复杂地块凸划分优化的多无人机覆盖路径规划

薛镇涛; 陈建; 张自超; 刘旭赞; 苗宪盛; 胡贵

doi:10.7527/S1000-6893.2021.25990

航空学报 >

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

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

电子电气工程与控制

基于复杂地块凸划分优化的多无人机覆盖路径规划

薛镇涛 ,
陈建 ,
张自超 ,
刘旭赞 ,
苗宪盛 ,
胡贵

展开

1. 中国农业大学工学院, 北京 100083;
2. 武汉大学测绘遥感信息工程国家重点实验室, 武汉 430079

收稿日期: 2021-06-18

修回日期: 2021-08-04

网络出版日期: 2021-10-09

基金资助

国家自然科学基金（51979275）；自然资源部超大城市自然资源时空大数据分析应用重点实验室开放基金（KFKT-2022-05）；国家重点研发计划（2018YFD0700603）；自然资源部城市国土资源监测与仿真重点实验室开放基金资助课题（KF-2021-06-115）；虚拟现实技术与系统国家重点实验室（北京航空航天大学）开放课题基金（VRLAB2022C10）；省部共建现代农业装备与技术协同创新中心资助课题（XTCX2002）；吉林省重点研发计划（20180201036SF）；测绘遥感信息工程国家重点实验室资助课题（19R06）；中国农业大学2115人才工程

收起

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

摘要

全覆盖路径规划是无人系统路径规划的重要内容之一。伴随无人机（UAV）技术的不断发展，无人机全覆盖路径规划在较多领域中已有重要运用，但在此过程中，往往会出现禁飞区和障碍物，需要进行路径规划保证飞行安全及效率。为此，基于凸划分优化，提出了一种针对含有复杂障碍物的复杂地块的全覆盖路径规划方法，减少了覆盖路径长度，降低了覆盖路径总时间。复杂地块往往含有光滑曲线或崎岖的内凹边界轮廓，首先采用改进Douglas-Peucker算法，将复杂的地块边界压缩为复杂多边形边界，再用凹凸点检验标记顶点凹凸性。之后通过旋转主线找出最短主线方向，再使用随机路标法（PRM）寻找最短的辅线，并采用四种凸划分策略对于复杂地块进行凸划分优化，使得无人机在全覆盖过程中路径更短，工作效率更高。最后，对测试地块进行计算机仿真，达到整体路径比67.6%和54.9%的性能指标，并与其他凸划分优化算法在相同地块上进行比较，验证了本文算法在路径长度以及规划时间上相对更优。

关键词： 全覆盖路径规划; 多无人机; 复杂地块; 复杂障碍物; 凸划分优化; 改进Douglas-Peucker算法; 随机路标法

本文引用格式

薛镇涛 , 陈建 , 张自超 , 刘旭赞 , 苗宪盛 , 胡贵 . 基于复杂地块凸划分优化的多无人机覆盖路径规划[J]. 航空学报, 2022 , 43(12) : 325990 -325990 . DOI: 10.7527/S1000-6893.2021.25990

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

参考文献

[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

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献