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

doi:10.7527/S1000-6893.2021.25990

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

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

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

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

收稿日期:2021-06-18 修回日期:2021-08-04 发布日期:2021-10-09
通讯作者: 张自超,E-mail:jchen@cau.edu.cn E-mail:jchen@cau.edu.cn
基金资助:
国家自然科学基金（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^1,2, LIU Xuzan¹, MIAO Xiansheng¹, HU Gui¹

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:2021-06-18 Revised:2021-08-04 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

摘要/Abstract

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

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

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

中图分类号:

V279

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

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.

参考文献

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

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

[1]	符小卫, 王辉, 徐哲. 基于DE-MADDPG的多无人机协同追捕策略[J]. 航空学报, 2022, 43(5): 325311-325311.
[2]	任少睿, 陆忠梅, 石远明, 李立欣, 陈巍. 一种基于信息素图的无人机高效通信覆盖方法[J]. 航空学报, 2022, 43(2): 324939-324939.
[3]	张瑞鹏, 冯彦翔, 杨宜康. 多无人机协同任务分配混合粒子群算法[J]. 航空学报, 2022, 43(12): 326011-326011.
[4]	陈璞, 严飞, 刘钊, 成果达. 通信约束下异构多无人机任务分配方法[J]. 航空学报, 2021, 42(8): 525844-525844.
[5]	田栢苓, 李品品, 鲁瀚辰, 宗群. 复杂环境下多无人机轨迹姿态协同控制[J]. 航空学报, 2020, 41(S2): 724245-724245.
[6]	王通, 黄攀峰, 董刚奇. 启发式多无人机协同路网持续监视轨迹规划[J]. 航空学报, 2020, 41(S1): 723753-723753.
[7]	刘宇轩, 刘虎, 田永亮, 孙聪. 面向林火持续侦察的多无人机分布式控制方法[J]. 航空学报, 2020, 41(2): 323381-323381.
[8]	陈灿, 莫雳, 郑多, 程子恒, 林德福. 非对称机动能力多无人机智能协同攻防对抗[J]. 航空学报, 2020, 41(12): 324152-324152.
[9]	黄洋, 汤俊, 老松杨. 基于复杂网络的无人机飞行冲突解脱算法[J]. 航空学报, 2018, 39(12): 322222-322222.
[10]	赵长春, 梁浩全, 祝明, 武哲, 娄文杰. 基于改进RPG方法的MUAVs协同目标跟踪[J]. 航空学报, 2016, 37(5): 1644-1656.
[11]	陈海, 何开锋, 钱炜祺. 多无人机协同覆盖路径规划[J]. 航空学报, 2016, 37(3): 928-935.
[12]	符小卫, 李建, 高晓光. 带通信约束的多无人机协同搜索中的目标分配[J]. 航空学报, 2014, 35(5): 1347-1356.
[13]	樊琼剑;杨忠;方挺;沈春林. 多无人机协同编队飞行控制的研究现状[J]. 航空学报, 2009, 30(4): 683-691.