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

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

作　　者：薛镇涛 陈建[1] 张自超 刘旭赞 苗宪盛 胡贵 XUE Zhentao;CHEN Jian;ZHANG Zichao;LIU Xuzan;MIAO Xiansheng;HU Gui(College of Engineering,China Agricultural University,Beijing 100083,China;State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China)

机构地区：[1]中国农业大学工学院,北京100083 [2]武汉大学测绘遥感信息工程国家重点实验室,武汉430079

出　　处：《航空学报》2022年第12期397-411,共15页Acta Aeronautica et Astronautica Sinica

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

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

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

分 类 号：V279[航空宇航科学与技术—飞行器设计]