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

doi:10.7527/S1000-6893.2022.27856

电子电气工程与控制

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

前一篇 |

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

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

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

收稿日期:2022-07-26 修回日期:2022-09-13 接受日期:2023-01-28 出版日期:2023-02-07 发布日期: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-02-07 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]	张安, 杨咪, 毕文豪, 张百川, 王雨农. 基于多策略GWO算法的不确定环境下异构多无人机任务分配[J]. 航空学报, 2023, 44(8): 327115-327115.
[2]	马亚杰, 王娟, 姜斌, 龚建业. 一种无人机⁃无人车编队系统容错控制方法[J]. 航空学报, 2023, 44(8): 327216-327216.
[3]	符小卫, 徐哲, 朱金冬, 王楠. 基于PER-MATD3的多无人机攻防对抗机动决策[J]. 航空学报, 2023, 44(7): 327083-327083.
[4]	肖和业, 杨建峰, 白俊强, 张旭东, 吴利荣. 面向任务需求的模块化无人机配置方法[J]. 航空学报, 2023, 44(7): 327100-327100.
[5]	奉志强, 谢志军, 包正伟, 陈科伟. 基于改进YOLOv5的无人机实时密集小目标检测算法[J]. 航空学报, 2023, 44(7): 327106-327106.
[6]	冒国韬, 邓天民, 于楠晶. 基于多尺度分割注意力的无人机航拍图像目标检测算法[J]. 航空学报, 2023, 44(5): 326738-326738.
[7]	许勇, 颜鸿涛, 贾涛, 马跃, 邓泽华, 刘多能. 固定翼集群无人机空中模拟对接技术[J]. 航空学报, 2023, 44(5): 326539-326539.
[8]	张良阳, 李占科, 韩海洋. 微型无人机栖息设计技术综述[J]. 航空学报, 2023, 44(12): 27573-027573.
[9]	文超, 董文瀚, 解武杰, 蔡鸣, 刘日. 基于回访机制的无人机集群分布式协同区域搜索方法[J]. 航空学报, 2023, 44(11): 327561-327561.
[10]	郭华, 郭小和. 改进速度障碍法的无人机局部路径规划算法[J]. 航空学报, 2023, 44(11): 327586-327586.
[11]	苏子康, 陈海通, 李春涛, 邢卓琳, 王宏伦. 非匹配包线下无人机空基回收拖曳系统协调运动规划[J]. 航空学报, 2023, 44(10): 327377-327377.
[12]	邵嘉琪, 张晓辉, 席涵宇, 刘子荣. 太阳能无人机线性自抗扰多环路能源控制[J]. 航空学报, 2023, 44(10): 327812-327812.
[13]	薛远亮, 金国栋, 谭力宁, 许剑锟. 基于多尺度融合的自适应无人机目标跟踪算法[J]. 航空学报, 2023, 44(1): 326107-326107.
[14]	郭琪磊, 桑为民, 牛俊杰, 袁烨. 复杂气象条件下考虑结冰风险的无人机飞行策略[J]. 航空学报, 2023, 44(1): 627518-627518.
[15]	梁超, 杨力, 潘成胜, 戚耀文. 卫星网络动态资源图多QoS约束路由算法[J]. 航空学报, 2023, 44(1): 326422-326422.

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 30

相关文章 15

编辑推荐

Metrics

本文评价