复杂环境下无人机全覆盖路径规划混合算法研究

黄迎港 陈锴 罗文广

摘  要：为解决无人机在被检物体外形复杂、多障碍物等环境下的路径规划问题，提出了一种基于混合策略的全覆盖路径规划算法，该算法由综合运动函数、死区逃离策略、运动优先级策略组成。综合运动函数对基于栅格地图的位置函数及考虑无人机能量消耗的轉向置信函数进行加权，并作为下一航点的选择依据;死区逃离策略由环形搜索、A-star算法构成;运动优先级策略设计为：左优先、下优先、直优先，以降低无人机遇到障碍物时规划路径缠绕、陷入死区和节点重复问题的发生概率，使之高效飞行。通过仿真及实机验证，结果表明：所提算法适用于复杂环境下的无人机路径规划，且可有效减少陷入死区的次数，降低路径重复率，减少路径规划时间。

关键词：无人机;路径规划;复杂环境;全覆盖;混合算法

中图分类号：V279.2;TN926          DOI：10.16375/j.cnki.cn45-1395/t.2022.01.013

0    引言

近年来，路径规划问题成为无人机控制领域的研究热点。全覆盖路径规划是指无人机从起点到终点，自主规划出一条无碰撞的飞行路径。常见的方法有：A-star算法、遗传算法、粒子群算法等。然而上述方法只在特定场景下有效且易陷入局部极小值，导致所得路径全局性差，无法满足无人机日益复杂的飞行环境要求[1]。周毅等[2]引入插入算子和删除算子对遗传算法（GA）进行改进，有效减少了航点重叠率，提高了无人机在巡线工作中的安全性。伍鹏飞等[3]采用混沌蜂群算法（ABC）提升无人机在复杂环境下的死区逃离能力。此外，通过引入辅助避障力的方法，解决人工势场法易陷入局部极小值的问题，但当环境变化时需要重新对参数进行整定，未从根本上解决其存在的缺点[4]。以上方法主要采用单一算法并进行特定的改进，虽能克服传统算法的一些缺点，但普适性较差。为此，复杂环境下的无人机路径规划研究逐渐向混合算法方向发展。周克帅等[5]采用全局+局部相结合的方式，实现动态环境下无碰撞路径规划。付兴武等[6]利用天牛须算法（BAS）中天牛个体的自寻优能力，结合粒子群算法（PSO）设计出BAS-PSO路径规划算法，可有效提高粒子的搜索效率，但PSO在解决路径规划问题时易出现早熟现象，算法的整体寻优能力提升不够显著。王翼虎等[7]将细菌觅食算法（BFO）引入粒子群优化中，避免粒子趋同现象发生，提高三维环境下路径规划的覆盖率。白杰等[8]在分散搜索算法中引入模拟退火算法，提高了分散搜索的全局寻优能力，但局部规划仍存在局限。栅格地图在路径规划环境建模方面应用广泛。郝宗波等[9]采用内螺旋覆盖算法（ISC）实现对室内环境下的全覆盖路径规划，有效降低遍历的重复性，但其并未对复杂环境进行验证。韩忠华等[10]通过降维方式提高规划效率，降低模型的复杂度，并采用局部动态搜索策略改善规划过程中的随机性。陶德臣等[11]利用图论学理论对牛耕往复式全覆盖算法进行改进，在不规则农田环境下实现全局航线规划，但其实现复杂，难以在线进行。潘楠等[12]提出基于差分进化算法（DE）优化的生命周期群搜索（LSO）算法，在模拟仓库环境飞行中延长了飞行路线，提高了无人机的工作效率。孙静等[13]提出分层规划方法，将PSO与稀疏A-star算法结合，解决了复杂环境下规划航线的无碰撞要求。唐俊[14]采用分层拓展的思想对三维环境进行建模，应用多层拓展A-star算法实现快速航迹规划，提高了三维路径规划的速度并可有效避开障碍物。唐博文等[15]采用事件触发方式，简化强化学习避障算法的复杂度，但其并未验证复杂环境下的避障有效性。

为了解决多旋翼无人机[16]在复杂环境下的全覆盖路径规划问题，本文提出一种基于混合策略的全覆盖路径规划算法。在定义位置函数和建立转向置信函数的基础上，设计用于确定无人机飞行方向的综合运动函数;应用环形搜索算法和A-star算法制定死区逃离策略，解决无人机高效逃离死区问题;设置“左优先，下优先，直优先”的运动优先级策略，解决无人机飞行遇到障碍物时规划路径缠绕、陷入死区和节点重复飞行问题。将其应用到环境复杂的桥梁病害检测路径规划中，验证该算法的有   效性。

1    基于混合策略的全覆盖路径规划算法

为了解决在复杂环境下的无人机路径规划问题，在文献[17]的基础上，研究一种基于混合策略的全覆盖路径规划算法。该算法在设计出二维算法的基础上，再扩展至三维。二维算法主要由综合运动函数、死区逃离策略、运动优先级策略等构成。

1.1   二维算法设计

1.1.1    综合运动函数

综合运动函数包括2个部分：位置函数及转向信度函数。位置函数用于区分未覆盖的栅格、已覆盖的栅格以及障碍物;而转向信度函数用于引导无人机向未覆盖区域飞行，同时控制转向角度，使路径趋于平直。

构建地图是进行无人机路径规划的前提条件，常见的方法有栅格法、单元分解法和拓扑法等。栅格地图以其简单有效、表达能力强的特点得到广泛应用。栅格法就是将无人机工作环境划分为若干个栅格，通过位置函数对栅格进行赋值，进行区域的划分。栅格大小的选择是决定路径规划成功与否的关键，过大则地图分辨率降低，对真实环境的表达能力不强;过小将增加计算负担，抗干扰性差。根据桥梁检测任务和无人机桥检相机的像素，选用  1 m×1 m的栅格对地图进行建模。

1）位置函数

对栅格进行赋值可以达到区分不同栅格的目的。设位置函数为[X]，如式（1）：

[Xi， j=1;该栅格未覆盖0.5;该栅格已覆盖−1;该栅格是障碍物]，                 （1）

式中：[i]、[j]表示栅格地图中第[i]行、第[j]列的栅格。

式（1）对栅格进行了分类。飞行路径即航线由一系列航点构成，路径规划就是确定每一个航点的位置。对应到栅格地图中，需要确定每飞行一步所处的栅格坐标。例如，图1所示的每一个运行窗口中会有8个与当前节点（图中[pp]点）相连接的栅格进入待选区域;[pb]表示当前节点[pp]的父节点（前一个已覆盖节点），这2个栅格都已经完成了覆盖（灰色表示），其赋值为0.5;图中障碍物栅格设为黑色，赋值为-1;[pn1—pn5]表示未完成覆盖的栅格（白色表示），赋值为1。图2显示了图1中各个栅格的赋值情况。

2）转向置信函数

为控制无人机的航向，使其趋向未覆盖区域，设置转向信度函数[C]，如式（2）：

[C=1−△ϕπ] ，                             （2）

式中：[△ϕ∈[0， π]]，为航向变化角。

图3为航向变化角示意图。

由图3得航向变化角[△ϕ]：

[△ϕ=arctanypn-yppxpn-xpp-arctanypp-ypbxpp-xpb]，       （3）

式中：[pp（xpp， ypp）]、[pb（xpb， ypb）]及[pn（xpn， ypn）]分别表示当前节点、当前节点的父节点及未覆盖节点。

[△ϕ=0°]，[C]=1为最大，无人机沿着直线航行，无需转向，消耗能量最少，信度最高;[△ϕ=180°]，无人机往相反方向航行，转向角度最大，消耗能量最多，应该尽量避免。

3）综合运动函数

综合考虑位置函数及转向信度函数，重新定义一个综合运动函数，作为下一飞行节点的选择依据，其定义为：

[Yk=Xk+aCk]，[k=1， 2， …， i]，            （4）

式中：[a∈（0， 1]]，为加权系数，此处将其设为0.5，即在规划过程中总是朝着未覆盖节点方向行走;    [i]的取值取决于与当前节点相连接的未覆盖点的     数量。选取[Yk]值最大的节点作为下一步移动方向。

1.1.2     死区逃离策略

在进行上述的路径规划时，可能会产生这样的情形：与当前节点毗邻的节点不存在未覆盖节点，都是已覆盖节点或障碍物，或者是边界，这时称无人机陷入死区，如图4所示。无人机进入死区后不能按图3所示的航向变化角方向进行下一步飞行，只有逃离死区后才能继續完成覆盖任务。为此，设计死区逃离策略：当无人机陷入死区后，使用环形搜索算法搜索死区外环的节点，寻找未覆盖的节点;然后计算各未覆盖节点与当前节点的代价值，用A-star算法确定下一节点。

1）环形搜索

当无人机陷入死区时，进行环形搜索。如图5所示，灰色为已覆盖节点或障碍物，蓝色为正在搜索区域，红色为搜索结束区域。以当前节点与未覆盖节点之间的最短欧氏距离为半径进行环形搜索，寻找未覆盖节点。

2）A-star算法选择路径

A-star算法是一种典型的启发式算法，具有原理简单、易于代码实现、适应性好等优势，在路径规划领域得到广泛应用。其在搜索过程中，通过比较每一个待选节点的代价值，选择代价值最小的节点作为下一个节点。

对于能量源有限的无人机，在复杂环境中进行路径规划时，需要重点考虑其高效飞行问题。因此，将A-star算法的代价值选择为“能量消耗”，在这里体现出来的就是“最短飞行距离”，在栅格地图中则为飞行的“栅格数”。实际上通过A-star算法就是要选择“从当前节点到达该未覆盖节点的路径长度是所有未覆盖节点中最短”的节点，定义为“最近”未覆盖节点，如图6所示。因为“死区”可能包括障碍物，无人机需要避开障碍物，环形搜索到的未覆盖节点未必是飞行距离最短的节点。图中，按最短欧氏距离（3个栅格）搜索到的未覆盖节点为[pn1]，而从当前节点[pp]出发，到达[pn1]需要经过栅格1、2、3、[pn2]、4、5、6、7、8、9，共飞行11个栅格，“飞行距离”大于“欧氏距离”。按下一个最短欧氏距离（4个栅格）搜索到的未覆盖节点[pn2]等（仅以[pn2]说明），从当前节点[pp]出发，到达[pn2]只需要经过栅格1、2、3，共飞行4个栅格，“飞行距离”等于“欧氏距离”。经过2次环形搜索后，A-star算法找到最佳逃离“死区”的节点为[pn2]。通过上述分析，设计的死区逃离策略具体步骤如下：

Step 1    按“最短欧氏距离”原则搜索未覆盖节点。

Step 2    计算当前节点到未覆盖节点的“飞行距离”，获得其中“最小飞行距离”。

Step 3  “最小飞行距离”是否等于或小于“最短欧氏距离”？如果是，则选择相应节点为“最近”未覆盖节点，无人机飞向该节点，逃离“死区”;反之，则执行下一步。

Step 4  “最短欧氏距离”增加一个栅格，转到Step 1，进行新一轮搜索。

在上述步骤中，“最小飞行距离”是指所有环形搜索中的最小值;“最短欧氏距离”是指每次环形搜索中的值，根据搜索的具体情况会不断加大。

1.1.3     运动优先级策略

由上述分析可知，综合运动代价函数能够对航线进行全覆盖规划，但当无人机遇到障碍物时，更容易陷入死区。为了逃离死区而产生节点重复飞行，导致规划路径存在冗余航点、路径重复率高的缺点。为此，引入运动优先级策略，规范无人机路径，降低陷入死区和节点重复飞行（重复率）的概率，使之高效规划路径。运动优先级策略设计为：左优先，下优先，直优先。在图7（a）中，当无人机触及障碍物边缘后，若左侧存在未覆盖区域，则优先覆盖左侧区域。在图7（b）中，当无人机触及障碍物边缘时，若下方存在未覆盖区域，则优先覆盖下方区域。在图7（c）中，下一节点存在2种选择，即左侧直行或向左上角运动。根据综合运动代价函数，将选择2号栅格作为下一个节点，但这很可能会造成1号栅格的未覆盖。根据运动优先级策略，优先覆盖1号栅格节点，减少规划路径缠绕的      发生。

1.2    二维全覆盖路径规划流程

二维全覆盖路径规划流程如图8所示。

对于全覆盖路径规划问题，关键在于根据相关策略确定无人机的下一个航点位置（节点）。图8中，大多数节点属于正常节点，由综合运动函数确定;无人机陷入死区时，则由死区逃离策略确定;若无人机触及障碍物边缘，则采用运动优先级策略确定。当所有栅格的赋值都不为1时，即不存在未覆盖节点，可认为完成了对工作区域的全覆盖路径规划。

1.3    三维全覆盖路径规划流程

无人机进行飞行时处于三维环境中，因此，需要将二维算法推广至三维。三维路径规划流程如 图9所示。

借助等高线的概念，将工作区域根据高度值分为若干层（z层），在每一层进行二维路径规划。当这一层完成全覆盖后，寻找正上（下）方的节点作为下一层的起点，若该节点为障碍物节点，则寻找“最近”节点，作为下一层的初始任务航点。循环以上步骤，直至三维工作空间完成全覆盖。

2    试驗及分析

2.1   仿真试验及分析

分别建立二维仿真地图及三维桥梁抽象地图，以验证本文提出的全覆盖规划算法的有效性。在全覆盖路径规划任务中，可以利用以下指标来评价全覆盖路径规划策略的性能。

1）区域覆盖率

区域覆盖率（[Cc]）表示为：

[Cc=NcN×100%]，                        （5）

式中：[Nc]表示无人机完成覆盖的栅格个数，[N]表示所有需要覆盖的栅格个数。

以使用无人机对桥梁进行病害检测为例，检测范围是桥梁的全部外表面，重点检测桥墩外表面、桥板下底面以及桥墩与桥板的连接处。为了避免漏检现象的发生，无人机需要遍历以上提到的所有区域，因此，要求算法所规划路径的区域覆盖率要达到100%。

2）路径重复率

路径重复率[RR]可以表示为：

[RR=NL-NN]，                          （6）

式中：[NL]代表无人机飞行路径的长度，在栅格地图中即为其所经过的栅格总数。

在任务背景下，区域覆盖率[Cc=100%]，使得[NL≥N]。由于无人机续航能力有限，这就要求[RR]尽可能小，提高工作效率。

2.1.1    二维环境仿真试验

在二维环境中，模拟工作区域为[25×25]的栅格地图，其中每一个栅格都赋值为1，用白色表示未覆盖节点;或赋值为-1，用黑色表示障碍物节点，障碍物为随机生成。地图的边界视为障碍物，标记为黑色。初始起点设置在地图左下角，显示为黑色实心圆。在地图中总计625个网格，其中待覆盖节点（白色）504个，障碍物节点（黑色）121个，仿真地图如图10所示。

在二维地图中，仅使用综合运动函数进行全覆盖路径规划，其结果如图11所示。从图中可以看出，仅使用综合运动代价函数可以完成对地图的全覆盖，覆盖率可以达到100%，但其所规划的路径多次陷入死区（图空心小方块代表陷入死区的节点），这就导致了较高的路径重复率。为了改善算法性能，将运动优先级策略加入其中，重新进行路径规划，其规划结果如图12所示，2种方法的对比试验结果如表1所示。

2种方法都可达到区域全覆盖率，但加入运动优先级策略后的路径重复率从26.8%降低至10.1%;路径总长度从639降低至555;陷入死区次数从42次降低至26次。由上可知，在加入了运动优先级策略后，算法所规划的路径较之前有了较大改善，将原本内螺旋型的线路更改为现有的往复式线路，大大减小了路线发生缠绕及陷入死区的可能性，同时逃离死区后的路径小于之前的路径重复率。结果表明，运动优先级策略可以有效降低路径重复率，缩短路径长度，有效提升无人机工作     效率。

目前全覆盖路径规划任务中使用比较多的方法有单元分解法以及生物激励神经网络算法等。使用以上2种算法对本文中的二维模拟地图进行全覆盖路径规划，使用覆盖率、路径长度、路径重复率、路径规划时间以及陷入死区次数作为算法的性能指标，结果如表2所示。通过表中数据可以看出，虽然3种方法的区域覆盖率都达到了100%，但从其他性能指标来看，本文提出的算法更具优势。

单元分解法在面对复杂地图、障碍物较多且分散的情况下，分解产生的子单元数量会非常大，导致路径极易陷入死区。相较于本文算法，其陷入死区的次数增加了11次，增加了42.3%，这就导致其路径重复率高达19.6%，比本文算法高出9.5%。生物激励神经网络算法的性能高于单元分解法，但该算法设计比较复杂且使用微分计算来更新节点的活性值，与本文直接对栅格进行操作相比，计算量大，其路径规划时间相较于本文算法高出了56.5%。

2.1.2    三维环境仿真试验

利用无人机进行桥梁病害检测时，实际工作环境是一个空中的三维空间。为了使仿真试验更加贴近实际工作环境，首先建立一个简单桥梁模型，包括桥墩及桥板两部分，桥梁简易模型如图13所示。无人机的工作任务是拍摄桥梁所有外表面，主要是桥墩外表面以及桥板下表面，因此，无人机的航线需要遍历以上地点。使用本文中提出的三维全覆盖路径规划算法对图13中的三维桥梁模型进行航线规划，其结果如图14所示。

在图14中无人机的初始起点为（3，12，1）。在  z =1层上，从初始起点开始，无人机沿桥墩外边沿飞行一圈后，完成了对该高度的全覆盖;在到达该层最后一个可达节点（4，13，1）后（右侧桥墩暂时无法到达），开始寻找z =2层的起点，由于（4，13，2）不是障碍物节点，故将其作为z =2层的起点。重复以上过程，直到完成所有高度层的二维全覆盖路径规划。完成对z =6层的覆盖后，右侧仍存在未覆盖区域，因此，寻找距离z =6层终点（12，36，6）最近的下行点（11，35，6），以完成对右侧桥墩的覆盖，即完成了桥梁模型的三维全覆盖路径规划。可以看出，本文提出的算法不仅能在二维环境中规避障碍物并实现全覆盖路径规划，而且在三维复杂环境下仍具有高效全覆盖路径规划能力。

2.2   运行测试及分析

经仿真验证后，将本文提出的全覆盖规划算法嵌入自行开发的天星GXUST地面站平台，对位于某大学东环校区内的宗元桥进行实际路径规划试验。在实机航线规划中将无人机视为一个质点，不考虑无人机的大小及外形，同时由于多旋翼无人机卓越的机动性能，可以合理假设在飞行中无人机可以全方位运动，不受转向角及俯仰角的限制。测试过程中由地面站软件控制无人机沿规划路径进行自主飞行，其地面站界面及路径规划效果如图15所示。其中，主界面分为：飞行数据显示区域、飞行命令及控制区域和航线规划及地图显示区域。右侧为本次桥检任务自动规划的航线，可以看出地面站系统将算法规划的任务航点转化为地理坐标（经、纬度和高度）形式并进行可视化显示。

该桥属于单拱桥，桥高4 m，上设路灯等设备，故无人机需对桥面及双侧桥墩进行航线覆盖，并确保机体在不与桥体及障碍物碰撞的前提下完成桥梁检测任务。图16为航线细节图。使用直径   70 cm的四旋翼无人机进行实际测试，设定距飞机中心80 cm为安全飞行范围，初始航点1从桥左侧3 m处出发，按z =1 m依次升高，先对两侧桥墩进行检测，随后对桥面进行往复式覆盖，最终降落在桥面（航点177）。实机飞行路径表明，该路径对桥体的覆盖率达到100%、无路径重复率且成功避免其陷入死区。在对该桥梁进行实测过程中，路径规划算法能够根据待检桥梁的三维重建模型规划出一条满足实际环境约束及待检桥梁类型要求的三维航线，并实现避障功能。

3     结束语

本文所提出的全覆盖路径规划混合算法可适用于复杂环境下的无人机路径规划。通过与单元分解法和生物神经算法进行比较后可知，该混合算法能高效完成对被检区域的路径规划任务，同时有效缩短航线总里程以提高检测效率;死区逃离策略可有效减少陷入死区的次数;运动优先级的设置降低了路径重复率，减少了路径规划时间，提高了规划算法的效率，并通过实机测试验证了该算法在实际复杂环境下（桥梁检测）路径规划的有效性。

参考文献

[1]     杨俊成，李淑霞， 蔡增玉.路径规划算法的研究与发展[J]. 控制工程，2017，24（7）：1473-1480.

[2]     周毅，李东武，孟浩，等.遗传算法路径规划在无人机电力巡线中的应用[J].自动化技术与应用，2021，40（2）：29-33.

[3]     伍鹏飞，李涛，曹广旭，等.基于改进混沌蜂群算法的无人战斗机路径规划[J].中国科技论文，2021，16（3）：301-306.

[4]     韩尧，李少华.基于改进人工势场法的无人机航迹规划[J/OL].系统工程与电子技术，2021：1-9[2021-06-30].http：//kns.cnki.net/kcms/detail/11.2422.TN.20210531.1117.014.html.

[5]     周克帅，范平清.改进A*算法与人工势场算法移动机器人路径规划[J].电子器件，2021，44（2）：368-374.

[6]     付兴武，胡洋.基于改进粒子群算法的三维路径规划[J].电光与控制，2021，28（3）：86-89.

[7]     王翼虎，王思明.基于改进粒子群算法的无人机路径规划[J].计算机工程与科学，2020，42（9）：1690-1696.

[8]     白杰，杨根科，潘常春，等.基于改进分散搜索算法的无人机路径规划[J].上海交通大学学报，2011，45（2）：173-178.

[9]     郝宗波，洪炳镕，黃庆成.基于栅格地图的机器人覆盖路径规划研究[J].计算机应用研究，2007（10）：56-58.

[10]   韩忠华，毕开元，杨丽英，等.室内复杂环境下多旋翼无人机动态路径规划[J].中国惯性技术学报，2019，27（3）：366-372，377.

[11]   陶德臣，祖家奎，高尚文.基于全覆盖路径的植保无人直升机航线规划方法与实现技术[J].电子测量技术，2020，43（7）：50-55，166.

[12]   潘楠，陈启用，刘海石，等.复杂工业品仓储环境无人机库盘任务规划[J/OL].计算机集成制造系统，2021：1-17[2021-06-30].http：//kns.cnki.net/kcms/detail/11.5946.TP.20210318.0934.006.html.

[13]   孙静，吴碧，许玉堂，等.复杂环境下无人机三维航迹规划方法研究[J].弹箭与制导学报，2014，34（3）：170-174.

[14]   唐俊.顾及复杂环境约束的无人机三维航迹快速规划[J].测绘通报，2019（11）：26-30.

[15]   唐博文，王智文，胡振寰.基于事件驱动的无人机强化学习避障研究[J].广西科技大学学报，2019，30（1）：96-102，117.

[16]   徐亚妮，罗文广，张亮.基于FPGA的四轴飞行器飞行控制系统设计[J].广西科技大学学报，2018，29（3）：50-56.

[17]   甘文洋，朱大奇.基于行为策略的AUV全覆盖信度函数路径规划算法[J].系统仿真学报，2018，30（5）：1857-1863.

Hybrid algorithm of UAV full coverage path planning in

complex environment

HUANG Yinggang1，2， CHEN Kai1， LUO Wenguang*1，2

（1.School of Electrical， Electronic and Computer Science， Guangxi University of Science and Technology，

Liuzhou 545616， China; 2. Guangxi Key Laboratory of Automobile Components and Vehicle Technology （Guangxi University of Science and Technology）， Liuzhou 545006， China）

Abstract： A hybrid strategy-based full coverage path planning algorithm is proposed to solve the    problem of UAV path planning in environments with complex shapes and multiple obstacles. The        algorithm is composed of comprehensive motion function， dead zone escape strategy， and motion      priority strategy. The comprehensive motion function weights the position function based on the grid map and the steering confidence function considering the energy consumption of the UAV as the basis for selecting the next waypoint; the dead zone escape strategy is composed of ring search and A-star   algorithm; the motion priority strategy design is of left-priority， down-priority and straight-priority to   reduce the planned path winding， dead zone and node duplication when the UAV encounters obstacles， enabling it to fly efficiently. The simulation and real machine verification results show that the          proposed algorithm is suitable for UAV path planning in complex environments and can effectively     reduce the number of dead zones， path repetition rate and path planning time.

Key words： unmanned aerial vehicle; path planning; complex environment; full coverage; hybrid        algorithm

（責任编辑：黎  娅）