杨鑫，王维，王燮（通信作者）

1.成都信息工程大学软件工程学院，四川成都，610225；2.成都飞机设计研究所，四川成都，610095

0 引言

对于无人机来说，路径规划是无人机能完成任务并顺利返回的重要保障。在已知起始点与目的地的复杂环境中，无人机需要在其运动空间中找到一条切实可行的最优路径或接近最优的路径[1]。为了解决无人机的路径规划问题涌现了许多算法，例如A*算法[2]、D*算法[3]、PRM算法[4]、人工势场算法[5]、遗传算法[6]、粒子群算法[7]、蚁群算法[8]等。随着仿生学习算法的发展，路径规划领域又出现了许多新的算法，包括狼群算法[9]、鲸鱼算法[10]、蝙蝠算法[11]。然而这些算法都有其局限性，因此许多研究人员致力于改进路径规划算法来得到更好的规划效果。文献[12]中采用局部信息和全局信息结合动态地改进信息素更新方式，并根据三维空间中路径的平坦程度和光滑度二阶微分分别增加了一阶微分和二阶微分来修改信息素更新规则，使得改进后的蚁群算法克服了收敛速度慢、容易陷入局部最优的缺点。文献[13]借鉴正弦余弦算法局部搜索的优势，在DE算法基础上融入种群重心概念，基于正弦余弦算法搜索机制对变异策略进行改进，并设计新的自适应缩放因子，以增强种群多样性、提高搜索能力；引入扰动策略到交叉策略，利用优秀个体信息引导搜索方向，提高收敛速度。文献[14]中提出了一种变步长的A*算法，减少了A*算法的路径搜索时间。根据文献对于路径规划算法做出的改进，路径规划算法的优化在于提高收敛速度、避免局部收敛等方向。

本文针对基本蚁群算法在三维路径规划方面存在的容易陷入局部收敛的问题，在基本蚁群算法中引入了鲸鱼算法的包围行为、随机搜索、泡泡网攻击操作来提高算法的寻优能力与稳定性。为调节收敛速度的平衡，借鉴A*算法的估价函数，引入对目的地距离的计算，降低路径搜索难度，提高算法的收敛速度。通过在仿真环境下与基本蚁群算法做对比验证，改进后的算法与基本蚁群算法收敛时间一样，不易陷入局部收敛，且得出的三维路径代价更小。

1 环境建模

环境建模是无人机进行路径规划的基础，目前用于环境建模的主要方法有栅格法、可视图法、切线法等。利用栅格法的基本思想将无人机的运动空间离散为n*m个小栅格。然后将运动空间的高度信息存储在n*m的矩阵中。然后利用MATLAB中的函数将仿真地图显示出来，仿真地图如图1所示。

图1 仿真地图

二维空间中，蚁群算法中的蚂蚁以目前所在的栅格为中心可以访问周边8个栅格。但在三维空间中栅格周围围绕的栅格数太多，为降低路径的搜索时间，将x、y两个维度中起始点与目的地相差最大的维度作为主轴。用主轴上维度的变化将三维空间进一步离散为n个二维平面，也将无人机的三维路径规划问题转变为了二维平面可行路径点的搜索问题。

考虑无人机自身的视野与转向角度的限制，因此在路径搜索过程中设定无人机在下一平面搜索路径点时允许移动的最大横向偏移和最大纵向偏移。此举措还可提高搜索效率，降低搜索难度。如图2所示，当位于平面∏i上的路径点α在平面∏i+1上搜索下一个路径点α+1就存在一个可视区域，只需搜索由最大横向偏移和最大纵向偏移组成的可视区域中的栅格节点。红色区域为可搜索的可视区域。

图2 可视区域栅格选择

2 算法改进

2.1 基本蚁群算法原理

（1）蚂蚁的状态转移

蚁群算法中蚂蚁选择下一个栅格的公式为：

式中，Pkij代表蚂蚁k到下一平面可视区域内各点的概率，allowedk代表蚂蚁k在下一平面可以到达的路径点集合。τij为路径点i到j上的信息素浓度，α为信息素影响因子，反映信息素浓度对蚂蚁路径点选择的影响程度。ηij为路径点i到j上的启发信息量，k为启发影响因子，反映启发信息量对蚂蚁路径点选择的影响程度。ηij一般的计算为路径点i到j上的距离的倒数1/dij，距离的计算一般为欧氏距离。将Pkij求出后，蚁群算法一般用轮盘赌法来选择下一路径点。

（2）信息素的更新

蚁群算法中信息素的更新一般分为两个部分：一是每只蚂蚁在每运动一步就在相应栅格留下信息素的局部信息素添加，二是每次迭代完成后对所有栅格的信息素进行挥发处理，并对该迭代中最优路径添加信息素的全局信息素更新。

蚂蚁的局部信息素添加公式为：

式中，ρ是信息素挥发因子，代表信息素挥发的速度。τ0为算法开始时设置好的信息素初始量。

蚁群的全局信息素更新公式为：

其中△τ0为信息素增量，计算公式为：

式中，bestfit为该迭代的最佳路径的代价大小。蚁群算法就是这样靠着信息素在迭代间聚集，依靠信息素的改变实现对问题解的筛选更新。但基本蚁群算法的启发函数是走一步算一步，缺乏对目的地方向的评估，容易贪图目前的最短路径陷入局部收敛，因此，本文在改进中加入A*算法启发函数对目的地方向的计算，提高算法收敛效率，避免陷入局部收敛。

2.2 鲸鱼算法原理

鲸鱼鱼群捕食的行为可分解成三个部分：随机搜索、包围猎物以及泡泡网攻击。其实泡泡网也可算作包围猎物，只是表现形式不同。包围猎物的行为如粒子群算法寻优一般，直接向猎物靠近。泡泡网攻击则是一种螺旋包围的方式，来围困猎物。在鲸鱼算法中这两部分为一个步骤：围捕猎物。一般鲸鱼算法中两个行为的概率都为50%。

其更新公式为：

其中，X*t表示到目前为止得到的最优解，Xt为当前解，ρ为[0,1]之间的随机数。b是定义对数螺线形状的常数，l为[-1,1]内的随机数，e是自然常数。A与C是系统向量，计算公式为：

其中，r1与r2都为[0,1]之间的随机数，t为当前的迭代次数，T为预先设好的最大迭代次数。

而随机搜索时，鲸鱼将向猎物包围圈外围游走，根据自身位置随即更新，体现到鲸鱼算法中的操作便是，鲸鱼随机向鲸鱼群中的另一只鲸鱼靠近。

此时鲸鱼的更新公式为：

2.3 算法改进

本文在基本蚁群算法中将蚂蚁追随富集信息素的行为看作围捕猎物，再加入鲸鱼算法中随机搜索的环节来实现扩大蚁群算法搜索范围的功能。具体公式为：

其中rand为[0,1]之间的随机数，t为当前迭代数，T为最大迭代次数。qzij为系统向量，计算公式为：

τij为路径点i到j上的信息素浓度，α为信息素影响因子，反映信息素浓度对蚂蚁路径点选择的影响程度。ηij为路径点i到j上的启发信息量，k为启发影响因子，反映启发信息量对蚂蚁路径点选择的影响程度。ηij在改进后的算法中的计算公式为：

dij为当前栅格与下一栅格的实际距离，djt为下一栅格与目的地的估计距离。该公式参考鲸鱼算法的猎物搜寻，将向随机鲸鱼靠近替换成更符合蚁群算法的将栅格的适应度大小调换选择路径，更能扩大蚁群算法的搜索范围。并且将下一栅格与目的地的估计距离加入启发因子的计算中，使得蚂蚁的路径搜索具有方向性，蚁群算法的搜索效率有所提高。

且因为三维蚁群算法在路径搜索中需要主轴指引，就如同象棋中的兵无法后退，会导致一些目的地周围较多障碍时无法收敛。因此，改进算法利用文献[15]中对蚁群算法的改变主方向的改进。在蚂蚁主轴进程与目的地栅格只差一格且其他维度离目的地距离较远时，对蚂蚁将起点变更为当前位置，主轴变更为x、y两个维度中的另一个，再次进行路径规划。搜寻到目的地后将路径合并，完成该蚂蚁的路径规划。

改进后的算法流程为：

算法参数初始化；

判断维度，选定主轴；

For t=1：T

For n=1：N

将起点放入路径表中；

For x=2:PortGrid-1（选择主轴方向到目的地之间的路径）

根据改进后的启发函数（17）计算下一平面可视区域内各点的启发值；

更新系统参数A与一个随机数rand；

If （rand＜A）

蚂蚁个体根据概率转移公式（1）计算可视区域内各点的概率，并利用轮盘赌随机选择下一个节点；

Else

蚂蚁个体根据公式（14）（16）计算可视区域内各点的概率，并利用轮盘赌随机选择下一个节点；

End

将选择好的下一节点存入路径表中，依照公式（2）局部更新信息素；

End

If（路径表最后的路径点能与目的地直连）

将目的地直接存入路径表中；

Else

将该点变为起点，变更主轴，再次选择路径；

路径规划好后，两段路径合并；

End

End

计算当前迭代每只蚂蚁路径的路径长度；

筛选并记录当前迭代的最佳路径与长度；

根据公式（3）全局更新信息素；

End

3 仿真实验及结果分析

为了验证该改进算法的有效性，在MATLAB平台上进行仿真并比较基本蚁群算法的仿真结果，对实验结果进行分析。本文所选的仿真环境为网上下载的HeightData地图，利用栅格法将地图划分成21×21的小栅格。该实验设置的参数如表1所示。

表1 参数设置

在该参数设置的条件下，两种算法在Height Data地图中（起点为[1,2,5]，终点为[21,21,10]）所规划出的路径效果如图3所示，其收敛曲线对照如图4所示。其中红线为基本蚁群算法，黑线为改进算法。

图3 路径规划图

图4 收敛曲线

为避免实验中的随机性影响，对种群数为30、50、80时各提取20次实验结果进行分析，如表2所示。

表2 20 次仿真结果对比

由图3、图4与表2的结果可知，本文改进的算法比基本蚁群算法规划的路径缩短了8%左右。由图4可知，改进后的算法比基本蚁群的搜索范围大，能避免局部收敛，且收敛时间相差不大。综上分析，通过仿真环境对算法进行实验，验证了改进算法比基本蚁群算法具有更好的寻优能力，算法的搜索范围提高，规划的路径更为平滑且路径长度较短，符合无人机的移动规则。

4 结语

针对蚁群算法在三维路径规划环境时容易陷入局部收敛的问题，本文利用A*算法的目的地的启示函数与鲸鱼算法的扩大算法搜索范围的机制对蚁群算法进行改进，加强了算法的全局寻优能力，扩大了算法的搜索范围，并避免目的地周围障碍较多无法收敛的问题，加入改变蚁群主方向的机制，保障算法的收敛。经过对比实验，改进算法比蚁群算法更好地避免了容易陷入局部收敛的问题，有更好的寻优能力，能有效地完成路径规划。