浙江大学学报(工学版), 2024, 58(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

WU Yue’an,, DU Changping,, YANG Rui, YU Jiahao, FANG Tianrui, ZHENG Yao

School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China

通讯作者: 杜昌平,男,副教授. orcid.org/0000-0003-0552-2492. E-mail:duchangping@zju.edu.cn

收稿日期: 2023-09-14  

Received: 2023-09-14  

作者简介 About authors

吴越安(1999—),男,硕士生,从事无人机轨迹规划研究.orcid.org/0009-0007-3503-420X.E-mail:yawu@zju.edu.cn , E-mail:yawu@zju.edu.cn

摘要

基于改进遗传算法研究倾转旋翼无人机(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.

Keywords: tilt-rotor unmanned aerial vehicle ; area coverage ; genetic algorithm ; local obstacle avoidance ; Dubins curve

PDF (2211KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

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

WU Yue’an, DU Changping, YANG Rui, YU Jiahao, FANG Tianrui, ZHENG Yao. Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm. Journal of Zhejiang University(Engineering Science)[J], 2024, 58(10): 2031-2039 doi:10.3785/j.issn.1008-973X.2024.10.006

路径规划是无人机(unmanned aerial vehicle, UAV)作业的核心问题[1]. 覆盖路径规划(coverage path planning, CPP)的主要任务是高效率地遍历任务区域并避开区域内的障碍物,该项应用在智能农业、遥感测绘、河流巡检和自主清洁等行业具有重要意义[2-5]. CPP算法可分为2种形式:经典式和启发式. 经典算法包括传统的路径规划算法,如随机漫步、动态规划. Pang等[6]设计的基于均方位移和截断随机游走的改进算法提升了搜索效率,Xie等[7]基于动态规划找到了覆盖区域的最优顺序. 经典算法在处理如旅行商问题(traveling salesman problem, TSP)的NP难[8]问题时,在适应复杂环境和提升覆盖效率方面显示出局限性[9]. 因此研究者越来越倾向于采用启发式算法,如蚁群算法(ant colony optimization, ACO)[10]、遗传算法(genetic algorithm, GA)[11]和基于强化学习的深度Q网络(deep Q network, DQN)、近端策略优化(proximal policy optimization, PPO)算法[12-13],以提高CPP任务的效率和适应性. 此外,杜楠楠等[14]提出基于无向图搜索方法的多无人机覆盖路径优化模型,通过有限遍历覆盖飞行的方向角,选择能流效率相对最优的飞行方向;Tnunay等[15]针对多无人机编队覆盖问题,基于虚拟引导者的最小网络拓扑生成具有动态约束的最小抖动时间参数轨迹和覆盖轨迹. 以上研究主要集中于旋翼UAV,而旋翼UAV的有效载荷小、续航时间短,难以完成大范围和远距离的CPP任务.

本研究聚焦倾转旋翼UAV (tilt-rotor UAV, TRUAV),这种新型无人机结合了旋翼UAV的垂直起降能力和固定翼UAV的高速长航时优点,能够适应多样化的复杂环境. TRUAV的非完整约束为CPP任务带来了新的挑战[16]. 已有研究基于改进的GA设计针对TRUAV的CPP算法,考虑了飞行动力学约束[17],但是没有考虑区域内可能存在的障碍物. 在现实任务环境中,阻碍正常飞行路线的不可穿越的障碍物常见,限制了该算法的现实应用. 本研究针对多障碍物约束下的凸多边形区域内的CPP任务,提出基于杜宾斯曲线的改进遗传算法(Dubins-based enhanced GA, DEGA). DEGA视CPP为TSP的变体,通过改进传统的GA,优化覆盖路径访问顺序,提高覆盖效率;结合杜宾斯路径生成符合TRUAV飞行动力学约束的平滑转弯路径. 为了保证飞行器避开区域内存在的障碍物,本研究提出适用于TRUAV特性的鱼尾形避障策略.

1. 问题描述和建模

实际应用场景中的任务区域可能存在地形变化,为了简化问题,进行如下合理假设[18]. 1) 忽略TRUAV的大小和形状,在飞行过程中高度和俯仰角保持稳定,飞行速度稳定;2) 任务区域简化为凸多边形,忽略地形起伏;3) TRUAV在转弯和直线飞行中的误差在可接受范围,不考虑如阵风、侧滑的复杂因素. 在考虑TRUAV的构型特性和非完整约束时,须特别关注TRUAV在旋翼状态和固定翼状态间频繁切换带来的额外能耗以及倾转状态下复杂的气动特性对飞控系统的挑战. 为了减少能量消耗并提高飞行稳定性,TRUAV在起降过程中采用旋翼模式,在巡航和转弯过程中采用固定翼模式.

任务场景:装备机载相机的TRUAV从出发点${p_{\mathrm{s}}}$开始对给定的任务区域执行CPP,任务区域内存在相对较小且分散的障碍物,完成后到达结束点${p_{\text{e}}}$. 任务目标:在规避障碍的情况下,TRUAV机载相机的探测区域能全面覆盖任务区域,TRUAV的覆盖路径总长度尽可能短. 如图1所示,任务区域为标准形式的$n$个顶点的凸多边形. 凸多边形顶点按笛卡尔坐标系逆时针顺序确定,即$V = ({v_{\text{1}}},{v_{\text{2}}},\cdots,{v_{n}})$,且没有3个连续的顶点共线,${v_i} = ({v_{{{xi}}}},{v_{{{yi}}}})$为任务区域的第${{i}}$个顶点的坐标;定义${e_{{i}}}$为顶点${v_{{i}}}、{v_{{{i+}}1}}$间的边长;${O_i} = ({O_{{{xi}}}},{O_{{{yi}}}},{R_{{{oi}}}})$为任务区域内的障碍物,$ ({O_{{{xi}}}},{O_{{{yi}}}}) $$ {R_{{{oi}}}} $分别为第i个障碍物的圆心坐标和半径. 如图2所示,TRUAV机载相机的视场(field of view, FOV)为梯形区域ABCD. 图中,$h$为TRUAV的飞行高度,$l$为探测区域的长度,${w_1}$为探测区域的短边宽度,${w_2}$为探测区域的长边宽度. 为了避免可能存在的图像边缘模糊的问题,将TRUAV的扫描宽度定义为FOV的短边宽度,即$ w = {w_1} $. 根据假设,TRUAV的飞行速度保持稳定,

图 1

图 1   覆盖路径规划的任务区域

Fig.1   Task area of coverage path planning


图 2

图 2   倾转旋翼无人机的相机视场

Fig.2   Camera field of view for tilt-rotor unmanned aerial vehicle


$ \left. \begin{gathered} F\cos {\phi _{\max }} = mg, \\ F\sin {\phi _{\max }} = m{v^2}/{R_{\min }}. \\ \end{gathered} \right\} $

式中:$F$是TRUAV受到的升力,${\phi _{\max }}$为最大滚转角,$ {R_{\min }} $为最小转弯半径,$v$为飞行速度. 化简式(1),得到Rmin的计算式[19]

$ {R_{\min }} = {{{v^2}}}/({{g\tan {\phi _{\max }}}}). $

2. 障碍物约束下的区域覆盖路径规划

利用最小跨度算法确定TRUAV在区域内的最优飞行方向;根据最优飞行方向生成往返路径(back-and-forth path, BFP),从而得到任务区域的初规划覆盖路径;提出鱼尾形避障策略以应对区域内不可穿越的障碍物,从而生成区域内无碰撞的覆盖路径;DEGA用于优化覆盖路径的先后访问顺序,提高区域覆盖的任务效率,减少不必要的飞行距离.

2.1. 最小跨度算法

在固定的区域内执行覆盖任务时,TRUAV的飞行距离和能耗随转弯次数的增加而增加. TRUAV的航程有限,且转弯过程的耗能大于平飞过程,因此须找到区域内转弯总次数最少的飞行方向. 根据文献[20],基于减少转弯次数以优化覆盖任务距离的原则,当区域内的最优飞行方向平行于区域最小跨度${L_{\min }}$的支撑平行线时,TRUAV完成该区域CPP任务的总转弯次数最少. 如图3所示,凸多边形区域的跨度L为刚好夹住该区域的、方向角为$\theta $的一对平行线间距. 该平行线称为支撑平行线. 凸多边形最小跨度方向和飞行方向的关系如图4所示. 如算法1所示,通过计算从任务区域的每条边到对应顶点的最远距离,得到任务区域内最小跨度${L_{\min }}$及对应方向角${\theta _{{L_{\min }}}}$,TRUAV的最优覆盖飞行方向垂直于${L_{\min }}$. 函数Calculate_dis用于求解顶点间距;函数find_vertex用于查找${L_{\min }}$出现时对应边的2个顶点.

图 3

图 3   任务区域的支撑平行线

Fig.3   Supporting parallel lines of task area


图 4

图 4   倾转旋翼无人机的飞行方向

Fig.4   Flight direction of tilt-rotor unmanned aerial vehicle


算法1 最小跨度

输入:凸多边形$V$的逆时针顶点坐标序列$ \{ {v_1},{v_2},\cdots,{v_n}\} $,其中$n$为凸多边形的顶点数,$ {v_i} = ({x_i},{y_i}),i \in [1,n+1] $;

输出:最小跨度${L_{\min }}$对应的方向角${\theta _{{L_{\min }}}}$;

1. for $ i\text{ }=\text{ }1:\text{ }n $:

2.  for $ j{\text{ }} = {\text{ }}1:{\text{ }}n $:

3.   if $j \ne i,j \ne i+1$:

4.    ${{\mathrm{dis}}_{ij}} = {\mathrm{Calculate}}\_{\mathrm{dis}}({v_i},{v_j})$;

5.   end if;

6.  end for;

7.  ${\mathrm{MAX}}\_{{\mathrm{dis}}_i}^2 = \max ({{\mathrm{dis}}_{ij}}^2)$;

8. end for;

9. ${\mathrm{MIN}}\_{\mathrm{dis}} = \min ({\mathrm{MAX}}\_{{\mathrm{dis}}_i}^2)$;

10. ${v_{{\mathrm{tmp}}}},{v_{{\mathrm{tmp}}+1}} ={\mathrm{ find}}\_{\mathrm{vertex}}({{\mathrm{dis}}_{ij}}^2 = = {\mathrm{MIN\_dis}})$;

11. ${\theta _{{L_{\min }}}}{\text{ = }}({y_{{\mathrm{tmp}}+1}} - {y_{{\mathrm{tmp}}}})/({x_{{\mathrm{tmp}}+1}} - {x_{{\mathrm{tmp}}}})$.

2.2. 往返路径生成算法

对于给定的任务区域,常见的覆盖方法有螺旋形、之字形和往返形等. 在确定TRUAV的最优飞行方向后,采用BFP实现区域内的路径覆盖. BFP能够极大地简化路径计算过程,保证TRUAV在直线飞行时相机始终指向地面. 实现区域的完全覆盖须使第一条扫描路径与边界间的距离为扫描宽度$w$的一半;若最后一条扫描路径到边界的距离大于$w$,须添加一条扫描路径来保证区域内的完全覆盖. 完全覆盖任务区域的最小覆盖路径数量的计算式为

$ {n_{{\text{c}}}} = \left\lceil {{L_{\min }}/w} \right\rceil . $

式中:$\left\lceil x \right\rceil $表示向上取整. 如算法2所示,通过连接所有覆盖路径并确保相邻覆盖路径的飞行方向相反,生成区域内的全覆盖路径. 函数Find_Intersection用于生成当前扫描线与区域边界间的有效交点. 算法2输出的交点集$p$包含BFP与任务区域边界的所有交点,其中${p_i}$为第$i$条BFP与任务区域$V$的2个交点坐标. 第i条BFP的航路点集为

$ F(i) = (1 - \alpha ){p_{i1}}+\alpha {p_{i2}},\;\alpha \in \left[ {0,1} \right]. $

算法2 BFP生成算法

输入:凸多边形$V$的逆时针顶点坐标$ \{ {v_1},{v_2},\cdots,{v_n}\} $, 最小跨度的方向角${\theta _{{L_{\min }}}}$, 覆盖路径数量${n_{{\text{c}}}}$;

输出:交点集$p = \left\{ {{p_1},{p_2},\cdots,{p_m}} \right\}$,${p_i} = \left\{ {{p_{i1}},{p_{i2}}} \right\}$;

1. 将凸多边形$V$顺时针旋转${\theta _{{L_{\min }}}}$,使其与$x$轴平行;

2. 找到旋转后$V$${y_{\max }},{y_{\min }}$,令${y_{{\mathrm{tmp}}}} = {y_{\min }}+w/2$;

3. for $ {{i }} = {\text{ }}1:{\text{ }}{{{n}}_{{\mathrm{c}}}} $:

4.  $ {p_i} = {\text{Find\_Intersection }}(V,{y_{{\mathrm{tmp}}}}) $;

5.  ${y_{{\mathrm{tmp}}}} = {y_{\min }}+w$;

6. end for;

7. 将交点集$p$各坐标逆时针旋转${\theta _{{L_{\min }}}}$;

8. return $p$.

2.3. 鱼尾形避障策略

虽然算法2能够有效处理区域覆盖问题,但在多障碍物约束的区域内,基于BFP的覆盖路径可能受障碍物的影响,导致TRUAV无法依照原定的直线路线飞行. 比较障碍物的半径${R_o}$与TRUAV的$ {R_{\min }} $的大小. 当${R_o}$$ {R_{\min }} $时,TRUAV沿障碍物的边缘绕行即可成功避开障碍;当${R_o}$$ {R_{\min }} $时,由于TRUAV存在最小转弯半径约束,无法采用前述避障方法. 为了避开半径小于TRUAV最小转弯半径的圆形障碍物,且在避障过程中平滑转弯,提出如图5所示的避障策略,因其外部轮廓线类似于鱼尾形,称之为鱼尾形避障策略. 图中,区域ABCD为TRUAV机载相机的探测范围;点划线为鱼尾形避障策略的有效探测范围,圆弧形点划线与直线点划线相较于探测区域边界;实线为TRUAV的前进方向与转向圆,半径为$ {R_{\min }} $,2个转向圆与前进方向相切并与外部的点划线圆弧同心;$ {R_{{\mathrm{s}}}} $为避免TRUAV碰撞而设定的安全半径阈值;PT为转向点,距离TRUAV为${D_{{\mathrm{TP}}}}$${O_1},{O_2}$为转向圆圆心,半径为$ {R_{\min }} $.

图 5

图 5   鱼尾形避障策略的探测范围

Fig.5   Detection range of fishtail-shaped obstacle avoidance strategy


在区域内执行覆盖任务时,TRUAV进行当前规划路径障碍物探测,若探测到障碍物,则启动鱼尾形避障策略. 如图6(a)所示,设TRUAV在当前规划路径左侧检测到障碍物,TRUAV继续向前飞行,保持方向不变. 如图6(b)所示,当鱼尾形策略探测范围的边界圆弧形点划线与障碍物相切时,识别并添加2个半径为$ {R_{\min }} $的辅助圆${C_1},{C_2}$(辅助圆${C_1}$与转向圆${O_2}$相切,切点为${T_1}$,圆心与障碍物圆心的连线垂直于规划路径的方向;辅助圆${C_2}$${C_1}$和当前规划路径同时相切,切点分别为${T_2}$${T_3}$),${C_1}$的圆心到${O_2}$的圆心距离和到${C_2}$的圆心距离均为$2{R_{\min }}$.图6(c)所示,TRUAV在转向点转弯,沿转向圆转弯飞行至点${T_1}$,随后平滑转弯至${C_1}$并沿${C_1}$飞行至点${T_2}$,最后平滑转弯至${C_2}$并沿${C_2}$转弯飞行至点${T_3}$,重新回到当前规划路径并完成避障,转而探测当前规划路径前方可能存在的下一个障碍物.

图 6

图 6   鱼尾形避障策略的工作流程

Fig.6   Workflow of fishtail-shaped obstacle avoidance strategy


2.4. 基于杜宾斯曲线的改进遗传算法

对于给定的区域,覆盖路径长度为${l_{{\mathrm{t}}}} = {l_{{\mathrm{i}}}}+{l_{{\mathrm{o}}}}$,其中${l_{{\mathrm{i}}}}$为区域内BFP的总长度,${l_{{\mathrm{o}}}}$为区域外的转弯距离. 为了获得高分辨率的图像,须保证扫描宽度$w$不变,飞行方向确定后${l_{{\mathrm{i}}}}$便不会改变,${l_{{\mathrm{i}}}} = \displaystyle\sum\nolimits_{k = 1}^{{n_{{\text{c}}}}} {{l_{{\mathrm{i}},k}}} $,其中${l_{{\mathrm{i}},k}}$为第k条BFP的长度. 因此,CPP任务的覆盖路径长度取决于${l_{{\mathrm{o}}}}$

$ {l_{{\mathrm{o}}}} = \sum\limits_{i = 1}^{i \lt {n_{{\text{c}}}}} {\Delta {{\mathrm{dis}}_{i,i+1}}} . $

式中:$ \Delta {{\mathrm{dis}}_{i,i+1}} $为从第$i$条扫描路径转到下一条扫描路径的转弯距离. ${l_{{\mathrm{o}}}}$与BFP间的访问顺序密切相关[20],为此以DEGA优化BFP的访问顺序,缩短${l_{{\mathrm{o}}}}$.

传统CPP的算法依顺序覆盖任务区域,优点是算法逻辑简单、实现容易;缺点是方法存在很大的局限性,不足以应对复杂的环境,可能导致规划效率低下,尤其是当$ {R_{\min }}\geqslant w$时,由于TRUAV不得不在区域外进行宽幅转弯,导致额外的飞行距离大量增加. DEGA将CPP问题转化为TSP的变体. 当$ {R_{\min }} \geqslant w$时,DEGA通过改进的GA对覆盖路径顺序进行启发式搜索,以减少宽幅转弯带来的额外飞行距离;在$ {R_{\min }} $$w$的情况下,采用基于坐标顺序的逐行路径覆盖(sequential path coverage,SPC)算法,优化BFP的访问顺序. DEGA的流程如图7所示,杜宾斯曲线用于依序连接所有的BFP.

图 7

图 7   基于杜宾斯曲线的改进遗传算法流程

Fig.7   Workflow of Dubins-based enhanced genetic algorithm


2.4.1. 旅行商问题转化

将BFP的访问顺序优化问题转化为TSP. CPP的任务特性决定了任务区域内的每条覆盖路径都必须被访问,且仅被访问一次. 因此,将区域内每条覆盖路径的中点视为TSP中必经的“城市”,并对这些“城市”按照顺序进行编号,编号方法如图8所示. BFP优化问题的TSP数学模型为

图 8

图 8   覆盖路径顺序编号

Fig.8   Sequence number of coverage path


$ \min f(R),\;f(R) = \sum\limits_{i = 1}^{{n_{{\text{c}}}} - 1} {d_{\mathrm{dis}}({C_i},{C_{i+1}})} . $

式中:${C_i}$为第$i$个待访问的“城市”,$d_{\mathrm{dis}}$ $ ({C_i},{C_{i+1}}) $${C_i}$${C_{i{\text{+}}1}}$间的杜宾斯曲线距离. 求满足式(6)的最优覆盖路径访问顺序$R = ({C_1},{C_2},\cdots,{C_{{n_{{\text{c}}}}}})$. 本研究讨论对称TSP,有$ d_{\mathrm{dis}}({C_i},{C_{i+1}}) = ({C_{i+1}},{C_i}) $.

2.4.2. 改进的遗传算法

GA是基于生物遗传机制的启发式随机搜索算法,通过模拟自然选择、交叉、变异的过程,展现出强大的并行搜索和全局优化能力. 在GA种群中,染色体与潜在的覆盖路径访问顺序$({C_1},{C_2},\cdots,{C_{{n_{{\text{c}}}}}})$一一对应,基因代表待访问的“城市”${C_i}$. 通过TSP的转化,DEGA利用改进的GA搜索覆盖路径的访问顺序的最优解,找到最有效的覆盖策略. 为了提高算法解的质量,更有效地执行CPP任务,本研究对传统GA的改进主要有1) 初始种群的生成,2) 适应度函数的设计,3) 交叉算子的改进,4) 变异算子的改进.

1)初始种群的生成. 传统GA中的初始种群随机生成,可能生成大量低效或者非可行的解,无法捕捉到问题域中的先验知识和启发性信息,导致算法可能陷入局部最优解. 采用最近邻算法优化初始种群. 最近邻算法是有效的启发式搜索策略,常用于解决如TSP的组合优化问题. 如算法3所示,最近邻算法的核心思想是从某个随机的起始基因开始,逐步构建路径. 为了生成更均匀的初始种群,算法从距离当前基因最近的3个基因中择一添加到当前染色体中作为目标路径的一部分. 该过程重复进行,直到所有基因被访问一次,从而完成单个染色体的路径构建. 在此过程中,算法维护访问状态数组以确保每个基因只被访问一次,在选择下个“城市”时,已访问的“城市”不再被选中. 采用基于距离信息的启发式方法构建路径,优先选择相邻的基因,优化传统的随机生成种群策略,显著提高了初始种群的质量. 通过选择不同的起始基因,使解空间具有多样性,减少了早熟收敛的风险,能够避免算法陷入局部最优解.

算法3 最近邻算法

输入:所有覆盖路径间距离矩阵$ {\boldsymbol{d}}_{\mathrm{dis}} $,基因数${n_{{\text{c}}}}$,种群染色体数$s$;

输出:初始种群${\mathrm{pop}}\;(s)$;

1. for $ i = 1:s $:

2.  随机选取起始基因:${\text{start\_gene = rand}}\;(1,n_{\mathrm{c}})$;

3.  初始化已访问列表:${\mathrm{visited = false}}\;(n_{\mathrm{c}})$;

4.  标记起始点为已访问:$ {\bf{visited}}\;{\mathrm{[StartGene] = true}} $;

5.  for $j = 2:n_{\mathrm{c}} - 1$:

6.  获取上一个基因到所有基因的距离:$ {\boldsymbol{d}}_{\mathrm{prev}} = {\boldsymbol{d}}_{\mathrm{dis}} ({\mathrm{LastCity}},{\text{ }}:) $

7.  访问过的基因距离设为无穷:$ {\boldsymbol{d}}_{\mathrm{prev}}({\bf{visited}})= {\bf{ inf}} $;

8.  在距离最近的3个基因中随机选择作为下一个访问的基因:$ {\mathrm{NextGene}} = {\mathrm{rand}}\;(\arg \min \;({\boldsymbol{d}}_{\mathrm{prev}},3)) $;

9.  $ {\mathrm{pop}}\;(i).{\text{ }}{\mathrm{append}}\;({\mathrm{NextGene}}) $;

10. 标记该基因为已访问${\bf{visited}}\;{\mathrm{[NextGene] = true}}$;

11. end for;

12. end for;

13. return pop.

2) 适应度函数的设计. 适应度函数在优化过程中扮演着至关重要的角色,通过量化种群中个体性能的差异来指导优化的方向. 合理设计的适应值函数不仅可以加速算法的收敛过程,还能助力在全局搜索空间中发现更优解决方案. 在CPP任务中,核心的优化目标是最小化TRUAV的覆盖路径长度,为此适应度函数采用杜宾斯曲线距离作为衡量基因间距离的指标. 杜宾斯曲线距离的计算方法简洁且物理意义清晰,能够准确地反映CPP任务中的转弯距离. 适应度函数的表达式为

$ {\mathrm{fit}}(s) = {1}\Bigg/{{\displaystyle\sum\limits_{i = 1}^{{n_{{\text{c}}}}} {(d_{\mathrm{dis}}({C_{s,i}},{C_{s,i+1}}))} }}. $

式中:$ d_{\mathrm{dis}}({C_{s,i}},{C_{s,i+1}}) $为该染色体内连续2个基因间的杜宾斯曲线距离. 染色体的杜宾斯曲线距离越大,适应度越低,与CPP任务的优化目标越不相符.

3) 交叉算子的改进. GA的交叉算子能够在解空间中进行全局搜索. 为了增强染色体间的信息交换,本研究提出三点交叉算子. 该算子不仅能够提高子代染色体的适应度,还继承了父代优秀的特性,具体的交叉操作如图9所示. 根据染色体的长度${n_{{\text{c}}}}$,随机确定染色体上的3个交叉点cp1、cp2、cp3,确定2个交叉区间:${\mathrm{sub1}} = \left[ {{\mathrm{cp1}},{\mathrm{cp2}} - 1} \right]$${\mathrm{sub2}} = \left[ {{\mathrm{cp3}},{n_{{\text{c}}}}} \right]$. 通过在交叉区间的基因交换,创建新的子代. 若交换后出现基因位置重复,则在非交换区间内进行必要的基因调换,以消除重复. 三点式交叉方法通过混合父代的基因特征,大幅提升了种群的多样性,扩展了搜索过程中解空间的范围.

图 9

图 9   三点式交叉算子

Fig.9   Three-point crossover operator


4) 变异算子的改进. 变异算子在当前解空间的局部邻域内引入随机扰动,旨在避免算法过早陷入局部最优并促进种群多样性的维持. 为了精细控制其对搜索过程的影响,变异概率应设定为较小值. 本研究提出的动态区间变异算子根据算法迭代的进程动态调整变异的强度,具体的变异算子操作如图10所示. 该算子根据$ {n_{{\text{c}}}} $随机选择变异点mp1、mp2并确定变异区间${\mathrm{sub}} = \left[ {{\mathrm{mp1}},{\mathrm{mp2}}} \right]$;在此区间内,变异强度动态调整,依赖于当前迭代次数I与预设的最大迭代次数$ I_{\mathrm{max}} $的比值. 区间内基因交换的长度计算式为

图 10

图 10   动态区间变异算子

Fig.10   Dynamic interval mutation operator


$ {\mathrm{len}} = \left\lceil {\frac{{{\mathrm{mp2}} - {\mathrm{mp1}}}}{2} \times \left(1 - \frac{{I}}{{I_{\mathrm{max}}}}\right)} \right\rceil . $

在迭代初期,变异算子施加较大强度的基因变异,区间内的所有基因进行前后互换以促进种群多样性的增加;在迭代的后期,随着算法接近收敛,区间内变异强度减弱,互换的基因长度按比例动态地减少,确保动态区间变异算子在接近全局最优解时的精细搜索. 动态区间变异算子通过当前迭代次数和预设的最大迭代次数之比来决定变异强度,实现探索与开发的动态平衡. 此策略的引入增加了搜索策略的灵活性,有效避免了算法过早收敛的问题,增强了算法在解空间中保持多样性的能力.

3. 实验验证

以Matlab为仿真实验工具,运行环境为Windows10, Intel(R) Core(TM) i5-7500 CPU @3.4 GHz. 实验主要包括1) 基于DEGA设计多个包含障碍物的任务区域作为测试案例;2) 以覆盖路径长度lt和执行时间te为评估指标,比较DEGA与现有CPP算法在覆盖效率和计算效率方面的性能. DEGA的主要参数如下:种群规模$N = 300$Imax=150,交叉概率${P_{\text{c}}} = 0.8$,变异概率${P_{\text{m}}} = 0.1$,选择替换个数为20. TRUAV实机如图11所示,正常巡航速度为15 m/s,最大滚转角${\phi _{\max }}$=$20^\circ $. 在最大滚转角的情况下,$ {R_{\min }} $≈63 m,考虑到飞行安全和控制难度,实际操作中TRUAV在转弯时的滚转角不会达到${\phi _{\max }}$. 考虑安全性和可控性,设定$ {R_{\min }} $=70 m.

图 11

图 11   倾转旋翼无人机样机

Fig.11   Prototype of tilt-rotor unmanned aerial vehicle


3.1. 覆盖路径规划结果

DEGA根据TRUAV的扫描宽度$w$$ {R_{\min }} $的大小关系,采取的不同转弯策略,如图12所示. 当$ w \leqslant {R_{\min }} $时,使用改进的GA优化覆盖路径的访问顺序;当$w > {R_{\min }}$时,使用逐行访问的策略. 在包含多个半径大小不等的圆形障碍物的任务区域内对CPP规划结果进行不同算法的对比. 当$w > {R_{\min }}$时,四边形和五边形任务区域内的规划结果分别如图13图14所示. 可以看出,在任务区域内,鱼尾形避障策略能够有效利用障碍周围的可用空间,成功地规避了区域内的所有障碍,且障碍附近的转弯路径连续、平滑. 还可以看出,相比于DEGA规划的结果,GA的规划结果显得复杂和凌乱,未能有效规划各覆盖路径的访问顺序;SPC算法在区域外进行多次灯泡形的宽幅转弯,造成大量额外的飞行距离,覆盖效率严重降低. DEGA对覆盖路径的访问顺序进行了有效调整,结果显示DEGA规划的覆盖路径更有序,低效的宽幅转弯次数显著减少,额外飞行距离有效地缩短,路径覆盖的效率得到提升.

图 12

图 12   基于杜宾斯曲线的改进遗传算法的转弯策略

Fig.12   Turning strategy of Dubins-based enhanced genetic algorithm


图 13

图 13   不同算法的四边形区域覆盖路径规划

Fig.13   Paths planned by different algorithms covering quadrilateral region


图 14

图 14   不同算法的五边形区域覆盖路径规划

Fig.14   Paths planned by different algorithms covering pentagon region


3.2. 算法性能对比

对四边形区域和五边形区域进行仿真实验,引入3种扫描宽度,共6个测试场景. 设定的出发点${p_{\mathrm{s}}} $坐标为(400,−100),结束点${p_{\mathrm{e}}} $坐标为(0,750),给定的四边形区域坐标为[(1500,75), (1500,650), (500,650), (750,75)],给定的五边形区域坐标为[(925,0), (1625,350), (1500,650), (500,650), (400,250)];由式(3)设计区域内包含10、20和50条覆盖路径的3组不同测试场景. DEGA、GA和SPC算法均执行10次独立测试,评估指标均使用测试平均值. 由于使用最小跨度算法预先确定了TRUAV的飞行方向,各算法在同一测试区域内的BFP长度固定,在实验中lt仅反映任务区域外的转弯飞行距离,对比结果分别如表1表2所示,其中四边形区域的面积为0.503 km2,五边形区域面积为0.833 km2. GA在四边形任务区域的lt相较于SPC已减少了至少18%(当n=10时);与GA相比,DEGA将lt分别减少了9.46%、14.56%和18.79%. 在五边形任务区域覆盖的实验中,DEGA同样表现出色,相比于GA,lt分别减少了7.80%、11.42%和13.06%. 结果证明DEGA在给定任务区域下的优异覆盖路径规划性能. 虽然SPC在执行时间上表现较好,但是在覆盖路径长度优化上的表现不理想,覆盖效率较低,难以在实际中应用. 在包含50条覆盖路径的四边形任务区域的实验中,DEGA的执行时间相较于GA增加了4.35%;在包含50条覆盖路径的五边形任务区域的实验中,DEGA的执行时间较GA增加了2.18%. 考虑到DEGA是基于GA的改进算法,计算效率略低于GA的实验结果符合预期. 鉴于DEGA在覆盖效率上的显著提升,接受部分计算效率的损失为合理的权衡. 在现实的应用中,尤其在对覆盖效率要求高于执行速度的场合中,这样的权衡是可以接受的. 综上所述,相比GA和SPC算法,DEGA在优化覆盖路径规划方面具有明显优势,在现实复杂任务环境中具有一定的实用性.

表 1   区域覆盖路径算法的性能对比(四边形区域)

Tab.1  Performance comparison of region-covering path algorithms (quadrilateral region)

算法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

新窗口打开| 下载CSV


表 2   区域覆盖路径算法的性能对比(五边形区域)

Tab.2  Performance comparison of region-covering path algorithms (pentagon region)

算法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

新窗口打开| 下载CSV


4. 结 语

研究倾转旋翼无人机在多障碍物约束下的规则区域覆盖路径规划问题,考虑倾转旋翼无人机的运动学特点,提出鱼尾形避障策略,并提出新型覆盖路径规划算法DEGA. 通过结合鱼尾形避障策略和杜宾斯曲线,所提算法显著提高了倾转旋翼无人机的区域覆盖效率. 在四边形和五边形任务区域内引入3种扫描宽度并开展不同路径规划算法的性能对比实验. 结果表明,在优化覆盖路径长度方面,DEGA相较于传统遗传算法和逐行路径覆盖算法表现更佳,在不明显增加计算成本的情况下,所规划的覆盖路径总长度远小于对比算法,充分证明DEGA在提升覆盖效率方面的显著效果. 后续研究将把DEGA应用于真实的倾转旋翼无人机飞行实验中,进一步验证该算法在实际应用中的效果和可行性.

参考文献

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      [本文引用: 1]

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.

[本文引用: 1]

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     

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     

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      [本文引用: 1]

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      [本文引用: 1]

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      [本文引用: 1]

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      [本文引用: 1]

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.

[本文引用: 1]

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      [本文引用: 1]

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      [本文引用: 1]

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      [本文引用: 1]

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.

[本文引用: 1]

杜楠楠, 陈建, 马奔, 等

多太阳能无人机覆盖路径优化方法

[J]. 航空学报, 2021, 42 (6): 324476

[本文引用: 1]

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

[本文引用: 1]

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.

[本文引用: 1]

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.

[本文引用: 1]

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      [本文引用: 1]

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      [本文引用: 1]

李文广, 胡永江, 孙世宇, 等

基于最小转弯半径的无人机转弯航迹规划算法

[J]. 计算机工程与设计, 2019, 40 (10): 2849- 2854

[本文引用: 1]

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]

LI Y, CHEN H, ER M J, et al

Coverage path planning for UAVs based on enhanced exact cellular decomposition method

[J]. Mechatronics, 2011, 21 (5): 876- 885

DOI:10.1016/j.mechatronics.2010.10.009      [本文引用: 2]

/