ACTA AERONAUTICAET ASTRONAUTICA SINICA >
Coverage operation path planning of UAV with endurance constraints based on improved ACO
Received date: 2022-07-26
Revised date: 2022-09-13
Accepted date: 2023-01-28
Online published: 2023-02-06
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)
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.
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 . DOI: 10.7527/S1000-6893.2022.27856
| 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. |
/
| 〈 |
|
〉 |
CJA