Please wait a minute...
浙江大学学报(工学版)  2024, Vol. 58 Issue (10): 2031-2039    DOI: 10.3785/j.issn.1008-973X.2024.10.006
计算机与控制工程     
基于改进遗传算法的倾转旋翼无人机区域覆盖路径规划
吴越安(),杜昌平*(),杨睿,俞佳浩,方天睿,郑耀
浙江大学 航空航天学院,浙江 杭州 310027
Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm
Yue’an WU(),Changping DU*(),Rui YANG,Jiahao YU,Tianrui FANG,Yao ZHENG
School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China
 全文: PDF(2211 KB)   HTML
摘要:

基于改进遗传算法研究倾转旋翼无人机(TRUAV)在多障碍物约束下的区域覆盖路径规划问题. 运用最小跨度算法和往返路径生成算法进行任务区域内的覆盖路径初规划,将区域覆盖问题转化为旅行商问题以优化覆盖路径顺序. 为了避开区域内的障碍物,提出鱼尾形避障策略. 引入最近邻算法,生成比传统遗传算法质量更高的初始种群,设计三点式交叉算子和动态区间变异算子进行遗传操作以提高所提算法的全局搜索能力,避免算法陷入局部最优. 在含多个障碍物的多边形区域算例内仿真验证所提算法的性能. 结果表明,相比于逐行路径覆盖算法和传统遗传算法,所提算法的覆盖路径长度减少了7.80%,TRUAV的任务区域覆盖效率显著提升.

关键词: 倾转旋翼无人机区域覆盖遗传算法局部避障杜宾斯曲线    
Abstract:

An enhanced genetic algorithm was proposed to address the challenge of area coverage path planning for a tilt-rotor unmanned aerial vehicle (TRUAV) amidst multiple obstacles. A preliminary coverage path plan for the designated task area was devised, utilizing the minimum spanning and back-and-forth path generation algorithms. The area coverage dilemma was transformed into a traveling salesman problem to optimize the sequence of the coverage path. A fishtail-shaped obstacle avoidance strategy was proposed to circumvent obstacles within the region. The nearest neighbor algorithm was introduced to generate a superior initial population than a genetic algorithm. A three-point crossover operator and a dynamic interval mutation operator were adopted in the genetic processes to improve the proposed algorithm's global search capacity and prevent the algorithm from falling into local optima. The efficacy of the proposed algorithm was rigorously tested through simulations in polygonal areas with multiple obstacles. Results showed that, compared to the sequential path coverage algorithm and the genetic algorithm, the proposed algorithm reduced the length of the coverage path by 7.80%, significantly enhancing the coverage efficiency of TRUAV in the given task areas.

Key words: tilt-rotor unmanned aerial vehicle    area coverage    genetic algorithm    local obstacle avoidance    Dubins curve
收稿日期: 2023-09-14 出版日期: 2024-09-27
CLC:  TP 249  
通讯作者: 杜昌平     E-mail: yawu@zju.edu.cn;duchangping@zju.edu.cn
作者简介: 吴越安(1999—),男,硕士生,从事无人机轨迹规划研究. orcid.org/0009-0007-3503-420X. E-mail:yawu@zju.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
吴越安
杜昌平
杨睿
俞佳浩
方天睿
郑耀

引用本文:

吴越安,杜昌平,杨睿,俞佳浩,方天睿,郑耀. 基于改进遗传算法的倾转旋翼无人机区域覆盖路径规划[J]. 浙江大学学报(工学版), 2024, 58(10): 2031-2039.

Yue’an WU,Changping DU,Rui YANG,Jiahao YU,Tianrui FANG,Yao ZHENG. Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm. Journal of ZheJiang University (Engineering Science), 2024, 58(10): 2031-2039.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.10.006        https://www.zjujournals.com/eng/CN/Y2024/V58/I10/2031

图 1  覆盖路径规划的任务区域
图 2  倾转旋翼无人机的相机视场
图 3  任务区域的支撑平行线
图 4  倾转旋翼无人机的飞行方向
图 5  鱼尾形避障策略的探测范围
图 6  鱼尾形避障策略的工作流程
图 7  基于杜宾斯曲线的改进遗传算法流程
图 8  覆盖路径顺序编号
图 9  三点式交叉算子
图 10  动态区间变异算子
图 11  倾转旋翼无人机样机
图 12  基于杜宾斯曲线的改进遗传算法的转弯策略
图 13  不同算法的四边形区域覆盖路径规划
图 14  不同算法的五边形区域覆盖路径规划
算法lt/kmte/s
n=10n=20n=50n=10n=20n=50
DEGA3.91356.368014.55618.49118.92480.665
GA4.32267.453417.92348.35618.70877.156
SPC5.279310.405325.79811.2392.0334.562
表 1  区域覆盖路径算法的性能对比(四边形区域)
算法lt/kmte/s
n=10n=20n=50n=10n=20n=50
DEGA4.59407.948119.63949.11719.91280.386
GA4.98298.972722.58918.94819.58878.633
SPC5.037810.320225.80041.4181.9984.567
表 2  区域覆盖路径算法的性能对比(五边形区域)
1 TANG G, TANG C, ZHOU H, et al R-DFS: a coverage path planning approach based on region optimal decomposition[J]. Remote Sensing, 2021, 13 (8): 1525
doi: 10.3390/rs13081525
2 LOTTES P, KHANNA R, PFEIFER J, et al. UAV-based crop and weed classification for smart farming [C]// 2017 IEEE International Conference on Robotics and Automation . Singapore: IEEE, 2017: 3024–3031.
3 VAN PHAM H, LAM T N A new method using knowledge reasoning techniques for improving robot performance in coverage path planning[J]. International. Journal of Computer Applications in Technology, 2019, 60 (1): 57- 64
doi: 10.1504/IJCAT.2019.099503
4 YAO P, XIE, Z, REN P Optimal UAV route planning for coverage search of stationary target in river[J]. IEEE Transactions on Control System Technology, 2019, 27 (2): 822- 829
doi: 10.1109/TCST.2017.2781655
5 BASIRI A, MARIANI V, SILANO G, et al A survey on the application of path-planning algorithms for multi-rotor UAVs in precision agriculture[J]. The Journal of Navigation, 2022, 75 (2): 364- 383
doi: 10.1017/S0373463321000825
6 PANG B, SONG Y, ZHANG C, et al Effect of random walk methods on searching efficiency in swarm robots for area exploration[J]. Applied Intelligence, 2021, 51: 5189- 5199
doi: 10.1007/s10489-020-02060-0
7 XIE J, CARRILLO L R G, JIN L An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems[J]. IEEE Control Systems Letters, 2019, 3 (1): 67- 72
doi: 10.1109/LCSYS.2018.2851661
8 TAN C S, MOHD-MOKHTAR R, ARSHAD M R A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms[J]. IEEE Access, 2021, 9: 119310- 119342
doi: 10.1109/ACCESS.2021.3108177
9 KAN X, TENG H, KARYDIS K. Multi-robot field exploration in hex-decomposed environments for Dubins vehicles [C]// 2019 IEEE International Conference on Robotics and Biomimetics . Dali: IEEE, 2019: 449-455.
10 CHEN J, LING F, ZHANG Y, et al Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system[J]. Swarm and Evolutionary Computation, 2022, 69: 101005
doi: 10.1016/j.swevo.2021.101005
11 TUNG W, LIU J Solution of an integrated traveling salesman and coverage path planning problem by using a genetic algorithm with modified operators[J]. IADIS International Journal on Computer Science and Information Systems, 2019, 14 (2): 95- 114
doi: 10.33965/ijcsis_2019140206
12 LE A V, PARWEEN R, KYAW P T, et al Reinforcement learning-based energy-aware area coverage for reconfigurable hRombo tiling robot[J]. IEEE Access, 2020, 8: 209750- 209761
doi: 10.1109/ACCESS.2020.3038905
13 CHEN X, TUCKER T M, KURFESS T R, et al. Adaptive deep path: efficient coverage of a known environment under various configurations [C]// 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems . Macau: IEEE, 2019: 3549–3556.
14 杜楠楠, 陈建, 马奔, 等 多太阳能无人机覆盖路径优化方法[J]. 航空学报, 2021, 42 (6): 324476
DU Nannan, CHEN Jian, MA Ben, et al Optimization method for coverage path planning of multi-solar powered UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42 (6): 324476
15 TNUNAY H, MOUSSA K, HABLY A, et al. Virtual leader based trajectory generation of UAV formation for visual area coverage [C]// IECON 2021 - 47th Annual Conference of the IEEE Industrial Electronics Society . Toronto: IEEE, 2021: 1–6.
16 KUČEROVÁ K, VÁŇA P, FAIGL J. Variable-speed traveling salesman problem for vehicles with curvature constrained trajectories [C]// 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems . Prague: IEEE, 2021: 4714–4719.
17 YUAN J, LIU Z, LIAN Y, et al. Global optimization of UAV area coverage path planning based on good point set and genetic algorithm[J]. Aerospace, 2022, 9 (2): 86
doi: 10.3390/aerospace9020086
18 XIE J, L CARRILLO L R G, JIN L. Path planning for UAV to cover multiple separated convex polygonal regions[J]. IEEE Access, 2020, 8: 51770- 51785
doi: 10.1109/ACCESS.2020.2980203
19 李文广, 胡永江, 孙世宇, 等 基于最小转弯半径的无人机转弯航迹规划算法[J]. 计算机工程与设计, 2019, 40 (10): 2849- 2854
LI W, HU Y, SUN S, et al UAV turning path planning algorithm based on minimum turning radius[J]. Computer Engineering and Design, 2019, 40 (10): 2849- 2854
[1] 朱云辰,程明骏,郑昕文,岑沛立,郗祥硕,黄杉,华晨,黄海. 基于优化第三代非支配排序遗传算法的城市应急设施模糊选址[J]. 浙江大学学报(工学版), 2024, 58(9): 1832-1843.
[2] 薛雅丽,李寒雁,欧阳权,崔闪,洪君. 战场环境下遗传黏菌算法的多机协同任务分配[J]. 浙江大学学报(工学版), 2024, 58(8): 1748-1756.
[3] 赵杰,刘锋,夏灵,范一峰. 基于遗传算法-序列二次规划的磁共振被动匀场优化方法[J]. 浙江大学学报(工学版), 2024, 58(6): 1305-1314.
[4] 李立峰,侯坤,邹德强,彭浩,李凌霄. 中等跨径钢板组合梁截面布置优化[J]. 浙江大学学报(工学版), 2024, 58(3): 510-517.
[5] 刘鹏,路庆昌,秦汉,崔欣. 道路网络多阶段抗灾能力优化模型构建与应用[J]. 浙江大学学报(工学版), 2024, 58(1): 96-108.
[6] 李煌,葛红娟,马莹,王永帅. 基于超平面NSGA-II的双输入双降压逆变器系统参数优化设计[J]. 浙江大学学报(工学版), 2023, 57(3): 606-615.
[7] 许丽丽,詹燕,鲁建厦,郎一丁. 四向穿梭车仓储系统复合作业调度优化[J]. 浙江大学学报(工学版), 2023, 57(11): 2188-2199.
[8] 查浩,费少华,傅云,吕震,朱伟东. 基于EtherCAT总线的六维力传感器在线解耦技术[J]. 浙江大学学报(工学版), 2023, 57(10): 2042-2050.
[9] 赵永胜,李瑞祥,牛娜娜,赵志勇. 数字孪生驱动的机身形状控制方法[J]. 浙江大学学报(工学版), 2022, 56(7): 1457-1463.
[10] 孙宝凤,张新康,李根道,刘娇娇. 第II类机器人混流装配线的平衡与排序联合决策[J]. 浙江大学学报(工学版), 2022, 56(6): 1097-1106.
[11] 张昕莹,陈璐,杨雯惠. 考虑系统时变效应与预防性维护的平行机调度[J]. 浙江大学学报(工学版), 2022, 56(2): 408-418.
[12] 胡鸿昊,李秀娟,于俊锋,张清周,柳景青. 基于耦合模拟的污水管网入流入渗定量识别[J]. 浙江大学学报(工学版), 2022, 56(11): 2313-2320.
[13] 邹贻权,黄浩洲,夏绪勇,王鑫. 成本导向下基于遗传算法的曲面幕墙设计优化[J]. 浙江大学学报(工学版), 2022, 56(10): 2049-2056.
[14] 向胜涛,王达. 基于改进量子遗传算法的模型交互修正方法[J]. 浙江大学学报(工学版), 2022, 56(1): 100-110.
[15] 鞠飞,庄伟超,王良模,刘经兴,王群. 混合动力汽车经济型巡航的车速规划策略[J]. 浙江大学学报(工学版), 2021, 55(8): 1538-1547.