基于改进ACO的带续航约束无人机全覆盖作业路径规划

doi:10.7527/S1000-6893.2022.27856

电子电气工程与控制

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

前一篇 | 后一篇

基于改进ACO的带续航约束无人机全覆盖作业路径规划

于全友¹, 徐止政¹(), 段纳¹, 徐觅蜜¹, 程义²

^1.江苏师范大学电气工程及自动化学院，徐州 221000
^2.江苏蒲公英无人机有限公司，徐州 221000

收稿日期:2022-07-26 修回日期:2022-09-13 接受日期:2023-01-28 出版日期:2023-06-25 发布日期:2023-02-06
通讯作者: 徐止政 E-mail:xuzz@jsnu.edu.cn
基金资助:
国家自然科学基金(62173166);江苏省高等学校自然科学研究面上项目(20KJB510047);徐州市基础研究计划(KC22053);江苏省研究生科研与实践创新计划(SJCX21_1130)

Coverage operation path planning of UAV with endurance constraints based on improved ACO

Quanyou YU¹, Zhizheng XU¹(), Na DUAN¹, Mimi XU¹, Yi CHENG²

^1.College of Electrical Engineering and Automation，Jiangsu Normal University，Xuzhou 221000，China
^2.Jiangsu Dandelion UAV Company，Xuzhou 221000，China

Received:2022-07-26 Revised:2022-09-13 Accepted:2023-01-28 Online:2023-06-25 Published:2023-02-06
Contact: Zhizheng XU E-mail:xuzz@jsnu.edu.cn
Supported by:
National Natural Science Foundation of China(62173166);Universities Natural Science Research Project of Jiangsu Province(20KJB510047);Fundamental Research Program of Xuzhou City(KC22053);Postgraduate Research and Practice Innovation Program of Jiangsu Province(SJCX21_1130)

摘要/Abstract

摘要：

本文研究带续航约束的电动多旋翼无人机全覆盖作业路径规划问题。首先，基于扫描线路径生成方法建立了带续航约束的无人机全覆盖作业路径规划的数学模型，然后，针对该路径规划模型中路径节点拓扑结构动态变化的特点，提出了改进的蚁群算法（ACO）。该蚁群算法给出了无人机返航时机判断机制和返航点计算方法，设计了动态局部距离矩阵，提出了滚动权值加权和的信息素更新机制，在寻优过程中兼顾全局启发性信息和局部启发性信息。最后，采用规则地形和复杂地形多田块作业算例对提出算法的有效性和优越性进行仿真验证，实验结果表明与其他4种对比算法相比，提出算法获得的规则作业田块的最优转移路径长度至少缩短了1.8%，获得的复杂作业田块的最优转移路径长度至少缩短了11.4%。

关键词: 无人机, 全覆盖作业, 路径规划, 续航约束, 蚁群算法

Abstract:

This paper studies the path planning problem of full coverage operation of electric multi-rotor UAVs with endurance constraint. Firstly， a mathematical model of path planning for UAV full coverage operation with endurance constraints is established based on the sweep method. Then， an improved Ant Colony Optimization （ACO） is proposed for handling the dynamic change of path node topology in the path planning model. In the improved ACO， the assessment mechanism of UAV’s return time and calculation method of the return point is provided. A dynamic local distance matrix， together with a pheromone updating mechanism based on the rolling weight weighted sum， is designed， considering both global and local heuristic information in the optimization process. Finally， two examples of multi-field operation tasks with regular and complex terrains are used to verify the effectiveness and advantage of the proposed algorithm. The results show that， compared with the other four algorithms， the proposed algorithm can reduce the length of the shifting path by at least 1.8% and 11.4% on the regular terrain and complex terrain， respectively.

Key words: unmanned aerial vehicle, full coverage operation, path planning, endurance constraint, ant colony optimization

中图分类号:

V328.1

于全友, 徐止政, 段纳, 徐觅蜜, 程义. 基于改进ACO的带续航约束无人机全覆盖作业路径规划[J]. 航空学报, 2023, 44(12): 327856-327856.

Quanyou YU, Zhizheng XU, Na DUAN, Mimi XU, Yi CHENG. Coverage operation path planning of UAV with endurance constraints based on improved ACO[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(12): 327856-327856.

图/表 10

图1

图2

图3

图4

图5

图6

表1

图7

表2

图8

参考文献 30

1	曹光乔，李亦白，南风，等. 植保无人机飞控系统与航线规划研究进展分析［J］. 农业机械学报， 2020， 51（8）： 1-16.
	CAO G Q， LI Y B， NAN F， et al. Development and analysis of plant protection UAV flight control system and route planning research［J］. Transactions of the Chinese Society for Agricultural Machinery， 2020， 51（8）： 1-16 （in Chinese）.
2	杜楠楠，陈建，马奔，等. 多太阳能无人机覆盖路径优化方法［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）.
3	张卫东，刘笑成，韩鹏. 水上无人系统研究进展及其面临的挑战［J］. 自动化学报， 2020， 46（5）： 847-857.
	ZHANG W D， LIU X C， HAN P. Progress and challenges of overwater unmanned systems［J］. Acta Automatica Sinica， 2020， 46（5）： 847-857 （in Chinese）.
4	黄刚，李军华. 基于AC-DSDE进化算法多UAVs协同目标分配［J］. 自动化学报， 2021， 47（1）： 173-184.
	HUANG G， LI J H. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm［J］. Acta Automatica Sinica， 2021， 47（1）： 173-184 （in Chinese）.
5	XU Y， SUN Z， XUE X Y， et al. A hybrid algorithm based on MOSFLA and GA for multi-UAVs plant protection task assignment and sequencing optimization［J］. Applied Soft Computing， 2020， 96： 106623.
6	李继宇，罗慧莹，朱长威，等. 基于能量优化的无人机喷施规划组合算法研究［J］. 农业机械学报， 2019， 50（10）： 106-115.
	LI J Y， LUO H Y， ZHU C W， et al. Research and implementation of combination algorithms about UAV spraying planning based on energy optimization［J］. Transactions of the Chinese Society for Agricultural Machinery， 2019， 50（10）： 106-115 （in Chinese）.
7	RUAN W Y， DUAN H B. Multi-UAV obstacle avoidance control via multi-objective social learning pigeon-inspired optimization［J］. Frontiers of Information Technology & Electronic Engineering， 2020， 21（5）： 740-748.
8	向锦武，董希旺，丁文锐，等. 复杂环境下无人集群系统自主协同关键技术［J］. 航空学报， 2022， 43（10）： 527570.
	XIANG J W， DONG X W， DING W R， et al. Key technologies for autonomous cooperation of unmanned swarm systems in complex environments［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（10）： 527570 （in Chinese）.
9	彭雅兰，段海滨，张岱峰，等. 仿灰狼合作捕食行为的无人机集群动态任务分配［J］. 控制理论与应用， 2021， 38（11）： 1855-1862.
	PENG Y L， DUAN H B， ZHANG D F， et al. Unmanned aerial vehicle swarm dynamic mission planning inspired by cooperative predation of wolf-pack［J］. Control Theory & Applications， 2021， 38（11）： 1855-1862 （in Chinese）.
10	薛镇涛，陈建，张自超，等．基于复杂地快凸划分优化的多无人机覆盖路径规划［J］．航空学报， 2022， 43（12）： 325990.
	XUE Z T， CHEN J， ZHANG Z C， et al. Multi-UAV coverage path planning based on optimization of convex division of complex plots ［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（12）：325990 （in Chinese）.
11	徐博，陈立平，谭彧，等. 基于无人机航向的不规则区域作业航线规划算法与验证［J］. 农业工程学报， 2015， 31（23）： 173-178.
	XU B， CHEN L P， TAN Y， et al. Route planning algorithm and verification based on UAV operation path angle in irregular area［J］. Transactions of the Chinese Society of Agricultural Engineering， 2015， 31（23）： 173-178 （in Chinese）.
12	徐博，陈立平，谭彧，等. 多架次作业植保无人机最小能耗航迹规划算法研究［J］. 农业机械学报， 2015， 46（11）： 36-42.
	XU B， CHEN L P， TAN Y， et al. Path planning based on minimum energy consumption for plant protection UAVs in sorties［J］. Transactions of the Chinese Society for Agricultural Machinery， 2015， 46（11）： 36-42 （in Chinese）.
13	王宇，陈海涛，李煜，等. 基于Grid-GSA算法的植保无人机路径规划方法［J］. 农业机械学报， 2017， 48（7）： 29-37.
	WANG Y， CHEN H T， LI Y， et al. Path planning method based on Grid-GSA for plant protection UAV［J］. Transactions of the Chinese Society for Agricultural Machinery， 2017， 48（7）： 29-37 （in Chinese）.
14	王宇，陈海涛，李海川. 基于引力搜索算法的植保无人机三维路径规划方法［J］. 农业机械学报， 2018， 49（2）： 28-33， 21.
	WANG Y， CHEN H T， LI H C. 3D path planning approach based on gravitational search algorithm for sprayer UAV［J］. Transactions of the Chinese Society for Agricultural Machinery， 2018， 49（2）： 28-33， 21 （in Chinese）.
15	阚平，姜兆亮，刘玉浩，等. 多植保无人机协同路径规划［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）.
16	LI Y， CHEN H， JOO ER M， et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method［J］. Mechatronics， 2011， 21（5）： 876-885.
17	TORRES M， PELTA D A， VERDEGAY J L， et al. Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction［J］. Expert Systems with Applications， 2016， 55： 441-451.
18	张昆，崔静莹，涂友超，等. 植保无人机精准覆盖航迹规划算法设计与验证［J］. 农机化研究， 2022， 44（2）： 15-22.
	ZHANG K， CUI J Y， TU Y C， et al. Design and verification of an algorithm of precision coverage path planning for unmanned aerial vehicle［J］. Journal of Agricultural Mechanization Research， 2022， 44（2）： 15-22 （in Chinese）.
19	黄小毛，唐灿， TANG Lie，等. 含障碍物多田块下旋翼无人机作业返航补给规划研究［J］. 农业机械学报， 2020， 51（7）： 82-90， 71.
	HUANG X M， TANG C， TANG L， et al. Refill and recharge planning for rotor UAV in multiple fields with obstacles［J］. Transactions of the Chinese Society for Agricultural Machinery， 2020， 51（7）： 82-90， 71 （in Chinese）.
20	黄小毛，张垒， TANG Lie，等. 复杂边界田块旋翼无人机自主作业路径规划［J］. 农业机械学报， 2020， 51（3）： 34-42.
	HUANG X M， ZHANG L， TANG L， et al. Path planning for autonomous operation of drone in fields with complex boundaries［J］. Transactions of the Chinese Society for Agricultural Machinery， 2020， 51（3）： 34-42 （in Chinese）.
21	唐灿，宗望远，黄小毛，等. 农用无人机多机多田块作业路径规划算法［J］. 华中农业大学学报， 2021， 40（5）： 187-194.
	TANG C， ZONG W Y， HUANG X M， et al. Path planning algorithm for cooperative operation of multiple agricultural UAVs in multiple fields［J］. Journal of Huazhong Agricultural University， 2021， 40（5）： 187-194 （in Chinese）.
22	CHOWDHURY S， MARUFUZZAMAN M， TUNC H， et al. A modified ant colony optimization algorithm to solve a dynamic traveling salesman problem： A case study with drones for wildlife surveillance［J］. Journal of Computational Design and Engineering， 2019， 6（3）： 368-386.
23	MAVROVOUNIOTIS M， MULLER F M， YANG S X. Ant colony optimization with local search for dynamic traveling salesman problems［J］. IEEE Transactions on Cybernetics， 2017， 47（7）： 1743-1756.
24	XU X L， YUAN H， MATTHEW P， et al. GORTS： Genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems［J］. Soft Computing， 2020， 24（10）： 7197-7210.
25	JIANG C， WAN Z P， PENG Z H. A new efficient hybrid algorithm for large scale multiple traveling salesman problems［J］. Expert Systems with Applications， 2020， 139： 112867.
26	LU L C， YUE T W. Mission-oriented ant-team ACO for min-max MTSP［J］. Applied Soft Computing， 2019， 76： 436-444.
27	MA A X， ZHANG X H， ZHANG C S， et al. An adaptive ant colony algorithm for dynamic traveling salesman problem［J］. Journal of Information Science and Engineering， 2019， 35（06）： 1263-1277.
28	MAVROVOUNIOTIS M， YANG S X， VAN M， et al. Ant colony optimization algorithms for dynamic optimization： A case study of the dynamic travelling salesperson problem［research frontier］［J］. IEEE Computational Intelligence Magazine， 2020， 15（1）： 52–63.
29	STODOLA P， MICHENKA K， NOHEL J， et al. Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem［J］. Entropy （Basel， Switzerland）， 2020， 22（8）： 884.
30	YANG K， YOU X M， LIU S， et al. A novel ant colony optimization based on game for traveling salesman problem［J］. Applied Intelligence， 2020， 50（12）： 4529-4542.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

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

算例	规则程度	田块数	田块顶点总数	补给点位置/m
1	较规则	3	12	（-40，100）
2	不规则	3	41	（-50，140）

算例	续航里程/m	方向角	算法获得最优转移路径长度（总路径长度）/m
算例	续航里程/m	方向角	提出的算法	ACO-GBC	ACO-GNO	Greedy-GBC	Greedy-GNO
1	1 000	优化	1 379.35（6 674.35）	1 577.95（6 872.95）	1 405.27（6 700.27）	2 153.14 （7 448.14）	1 519.00 （6 814.00）
	1 000	未优化	1 451.09（6 826.09）	1 471.01（ 6846.01）	1 470.99（6 845.99）	2 072.01（7 447.01）	2 087.80 （7 462.80）
	1 500	优化	1 076.36（6 371.36）	1 325.32（6 620.32）	1 144.67（6 439.67）	1 627.24（6 922.24）	1 515.02 （6 810.02）
	1 500	未优化	1 159.70（6 534.70）	1 471.71（6 846.71）	1 506.70（6 881.70）	1 735.95 （7 107.95）	1 612.74 （6 987.74）
	2 000	优化	916.60（6 211.60）	1 417.22（6 712.22）	1 072.30（6 367.30）	1 355.56 （6 650.56）	1 343.62 （6 638.62）
	2 000	未优化	9 23.09（6 298.09）	1 283.50（6 658.50）	1 295.77（6 670.77）	1 406.84 （6 781.84）	1 483.91 （6 858.91）
2	1 000	优化	3 171.84（8 729.84）	3 834.09（9 392.09）	3 942.58（9 500.58）	4 096.98 （9 654.98）	4 010.89 （9 568.89）
	1 000	未优化	4 100.19（9 638.19）	4 081.32（9 619.32）	4 083.56（9 621.56）	4 184.13 （9 722.13）	4 265.15 （9 803.15）
	1 500	优化	1 930.43 （7 488.43）	2 714.81（8 272.81）	2 621.46（8 179.46）	2 877.81 （8 435.81）	2 641.60 （8 199.60）
	1 500	未优化	2 468.00（8 006.00）	2 571.15（8 109.15）	2 724.71（8 262.71）	2 827.57 （8365.57）	2 926.56（8 464.56）
	2 000	优化	1 585.09（7 143.09）	1 788.66（7 346.66）	1 789.45（7 347.45）	2 024.91（7 582.91）	1 816.90（7 372.90）
	2 000	未优化	1 825.65（7 363.65）	1 980.53（7 518.53）	1 933.99（7 471.99）	1 991.92（7 529.92）	2 141.50（7 679.50）

[1]	王海峰, 刘坤澎, 江泓鑫, 杜晨曦. 螺旋桨多设计点气动优化方法和变桨距角策略[J]. 航空学报, 2024, 45(9): 528831-528831.
[2]	赵春晖, 刘安萌, 吕洋, 潘泉. 无人机韧性自主定位技术综述[J]. 航空学报, 2024, 45(8): 28839-028839.
[3]	张薇, 何若俊. 面向物联网数据收集的无人机自主路径规划[J]. 航空学报, 2024, 45(8): 329054-329054-1.
[4]	赵靖, 宋丹. 无人机GNSS/IMU组合导航系统完好性监测方法[J]. 航空学报, 2024, 45(7): 328943-328943.
[5]	王传云, 苏阳, 王琳霖, 王田, 王静静, 高骞. 面向反制无人机集群的多目标连续鲁棒跟踪算法[J]. 航空学报, 2024, 45(7): 329017-329017.
[6]	尹洪玉, 吴宇, 梁天骄. 固定翼无人机巡逻覆盖协同路径规划方法[J]. 航空学报, 2024, 45(6): 328944-328944.
[7]	安朝, 霍贵玺, 孟杨, 谢长川, 杨超. 翼尖铰接组合式无人机气动建模方法及布局参数影响[J]. 航空学报, 2024, 45(6): 629587-629587.
[8]	罗旭东, 吴一全, 陈金林. 无人机航拍影像目标检测与语义分割的深度学习方法研究进展[J]. 航空学报, 2024, 45(6): 28822-028822.
[9]	李广佳, 王红波, 张凯, 仪志胜. 临近空间太阳能无人机增升减阻技术综述[J]. 航空学报, 2024, 45(5): 529644-529644.
[10]	蔡云鹏, 周大鹏, 丁江川. 具有防撞安全约束的无人机集群智能协同控制[J]. 航空学报, 2024, 45(5): 529683-529683.
[11]	郑高杰, 何小明, 李东坡, 谭慧俊, 汪昆, 吴祯龙, 王德鹏. 尾部推进无人机双90°偏折进气道/蜗壳耦合流动特性[J]. 航空学报, 2024, 45(4): 128782-128782.
[12]	王祝, 张梦通, 张振鹏, 徐广通. 基于多指标动态优先级的无人机协同路径规划[J]. 航空学报, 2024, 45(4): 328816-328816.
[13]	张清瑞, 刘赟韵, 孙慧杰, 朱波. 固定翼无人机紧密编队的鲁棒协同跟踪控制[J]. 航空学报, 2024, 45(1): 629233-629233.
[14]	郭洪振, 陈谋, 戴永东, 王茂飞. 分布式自适应事件触发四旋翼无人机编队控制[J]. 航空学报, 2023, 44(S2): 729917-729917.
[15]	刘坤达, 刘雪明, 朱波, 张清瑞. 面向狭窄通道穿越的多机编队安全鲁棒控制[J]. 航空学报, 2023, 44(S2): 729768-729768.

基于改进ACO的带续航约束无人机全覆盖作业路径规划

Coverage operation path planning of UAV with endurance constraints based on improved ACO

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 30

相关文章 15

编辑推荐

Metrics

本文评价