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

doi:10.7527/S1000-6893.2022.27856

Abstract

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

CLC Number:

V328.1

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 1

Fig.7

Table 2

Fig.8

References 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.

算例	规则程度	田块数	田块顶点总数	补给点位置/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]	Chunhui ZHAO, Anmeng LIU, Yang LYU, Quan PAN. A survey of resilient self-localization for UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(8): 28839-028839.
[2]	Wei ZHANG, Ruojun HE. Autonomous trajectory design for IoT data collection by UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(8): 329054-329054-1.
[3]	Chao AN, Guixi HUO, Yang MENG, Changchuan XIE, Chao YANG. Aerodynamic modeling methods and influence of layout parameters for wingtip⁃hinged multi⁃body combined UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 629587-629587.
[4]	Hongyu YIN, Yu WU, Tianjiao LIANG. Cooperative path planning for patrol coverage of fixed wing UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 328944-328944.
[5]	Xudong LUO, Yiquan WU, Jinlin CHEN. Research progress on deep learning methods for object detection and semantic segmentation in UAV aerial images [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 28822-028822.
[6]	Gaojie ZHENG, Xiaoming HE, Dongpo LI, Huijun TAN, Kun WANG, Zhenlong WU, Depeng WANG. Double 90° deflection inlet/volute coupling flow characteristics of tail-powered unmanned aerial vehicle [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(4): 128782-128782.
[7]	Zhu WANG, Mengtong ZHANG, Zhenpeng ZHANG, Guangtong XU. Multi-UAV cooperative path planning based on multi-index dynamic priority [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(4): 328816-328816.
[8]	Qingrui ZHANG, Yunyun LIU, Huijie SUN, Bo ZHU. Robust cooperative tracking control for close formation of fixed⁃wing unmanned aerial vehicles [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(1): 629233-629233.
[9]	Hongzhen GUO, Mou CHEN, Yongdong DAI, Maofei WANG. Distributed adaptive event⁃triggered formation control for QUAVs [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729917-729917.
[10]	Kunda LIU, Xueming LIU, Bo ZHU, Qingrui ZHANG. Robust safe control for multi⁃UAV formation flight through narrow corridors [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729768-729768.
[11]	Xuejian WANG, Yongming WEN, Xiaorong SHI, Ningning ZHANG, Jiexi LIU. Design of hybrid intelligent decision framework for multi⁃agent and multi⁃coupling tasks [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729770-729770.
[12]	Lianbo YU, Pinzhao CAO, Liang SHI, Jie LIAN, Dong WANG. An improved conflict⁃based search algorithm for multi⁃agent path planning [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S1): 727648-727648.
[13]	An ZHANG, Mi YANG, Wenhao BI, Baichuan ZHANG, Yunong WANG. Task allocation of heterogeneous multi-UAVs in uncertain environment based on multi-strategy integrated GWO [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(8): 327115-327115.
[14]	Guotao MAO, Tianmin DENG, Nanjing YU. Object detection in UAV images based on multi-scale split attention [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(5): 326738-326738.
[15]	Yong XU, Hongtao YAN, Tao JIA, Yue MA, Zehua DENG, Duoneng LIU. Aerial simulation docking technology of fixed-wing clustering UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(5): 326539-326539.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 30

Related Articles 15

Recommended Articles

Metrics

Comments