基于改进烟花-蚁群算法的海流环境下水下无人潜航器的避障路径规划

马 焱，肖玉杰，陈 轶，闫泓衫

（1.西北工业大学航海学院，西安710072；2.海军研究院，北京100161）

0 引言

水下无人潜航器（UnmannedUnderwater Vehicle，UUV）是水下无人系统的重要组成部分，在军用领域、民用领域均有巨大的应用价值，是响应国家军民融合发展的重点工程之一。在智能化变革的今天，UUV智能化水平的高低决定了其核心竞争力，而UUV的路径规划技术正是衡量其智能化水平的最基本、最核心的技术之一。

目前，路径规划问题在陆地和空中空间域中的研究已比较成熟，各种陆地移动机器人、空中无人机已能很好地完成路径规划任务。然而，由于UUV通常在复杂多变的海流中工作，水中的阻力远远大于空中和陆地的阻力，与其相关的路径规划则不仅仅只需考虑避障问题，还需要考虑海流对UUV航行的作用。作为一种能量的流动，海流对UUV航行带来了很大的影响。在路径规划时，应尽量使UUV顺着海流的流向航行，充分利用海流场的能量，减少因抵抗海流而逆流航行带来的能量消耗［1］。因此，需要规划出一条能量消耗尽可能少、航行距离尽可能短的路径。

针对UUV路径规划问题，很多算法应运而生，如快速探索随机树（RRT）算法［2］、萤火虫算法［3］、人工蜂群算法［4］、人工势场法［5］、基于图搜索算法［1，6］、种群进化算法［7］等，但各种算法均有其优缺点。比如，人工势场法存在当目标点附近有障碍物时无法到达目标点，以及在相隔很近的障碍物之间不能发现路径等缺点；基于图搜索算法存在计算代价会随着搜索空间维数的增大而出现指数增加的缺点；部分种群进化算法存在易于早熟和陷入局部最优解的缺点。文献［8］提出了基于量子行为的粒子群优化的路径规划方法，考虑了海流和障碍物的影响，但是其优化目标是航行时间代价，没有考虑重要的能量消耗代价。文献［6］利用稀疏A∗算法对AUV进行了全局路径规划，并建立了相应的约束条件，但其优化目标是航行总距离，同样没有考虑能量消耗代价。文献［1］考虑到了能量消耗代价，并用CD∗算法进行了路径规划，但是完全没有考虑航行时间和航行距离的代价。文献［9］利用GA⁃PSO混合算法对考虑海流环境的AUV进行了路径规划，但其仅仅考虑了能量消耗，并且其建立的海流环境没有考虑涡流等更复杂的情况。

为了在考虑海流环境的情况下，快速寻找到UUV路径规划问题的全局最优解，本文借鉴文献［10］提出的改进烟花⁃蚁群混合算法解决了此问题。首先，建立二维海流环境，得到含有障碍物的等效栅格模型。然后，建立UUV避障路径规划数学模型。最后，为验证提出的方法在处理该问题时的优势，将其与ACO方法作出仿真实验对比。实验结果表明，本文提出的方法能以更快的速度找到更优的全局最优解。

1 搜索环境模型

1.1 二维海流环境模型

由于地球的快速自转，海流水平面内的运动规模远大于垂直面，因此可以将海流考虑为多层二维水平面内的运动。这里，采用文献［11］中的多个粘性Lamb涡流叠加对海流场模型进行数值方程表示。其数学描述为

图1 海流环境模型Fig.1 Model of ocean current environment

1.2 含障碍物的等效栅格模型

在该二维海流环境中，随机布撒10个半径为R（R∈（0，2］）的圆形障碍物，含障碍物的海流模型如图2所示。为便于定义路径编码，利用文献［10］中的二维栅格模型处理障碍物。对障碍物进行适当膨胀，最终可将UUV简化为质点处理。将圆形障碍物处理为方形等效栅格时，需遵循圆形径向跨度 “四舍五入”的原则。如图3（a）所示，取4×4方格为例，红色虚线为 “四舍五入”分界线，绿色实线为圆形障碍物轮廓。分界线以内的圆形障碍物等效栅格为分界线内的最大方形区域栅格，分界线以外的圆形障碍物等效栅格为分界线以外的最小方形区域栅格，图3（b）、图3（c）为两个等效栅格实例。按照此等效原则，本文中含障碍物的海流环境等效栅格如图4所示。

图2 含障碍物的海流环境Fig.2 Ocean current environment with obstacles

图3 障碍物等效栅格方法示意图Fig.3 Schematic diagram of obstacle equivalent grid method

图4 含障碍物的海流环境等效栅格Fig.4 Equivalent grid of ocean current environment with obstacles

2 UUV避障路径规划的数学模型

UUV避障路径规划是一个典型的多目标多约束的非线性优化问题，本文借鉴了文献［13］中处理复杂优化问题的方法。首先，分别设计了决策变量、目标函数和约束条件的数学模型，然后使用外罚函数法将该模型转化为无约束的单目标非线性规划问题。

2.1 决策变量设计

应用文献［10］中的栅格编码方式，规划的路径最终以序列号编码m表示，其对应于海流环境中的坐标为 (xm，ym)。因此，可以设计坐标(xm，ym)为决策变量，将其变换成序列号编码，即可得到最优路径。

2.2 目标函数设计

分别定义UUV路径规划时的能量消耗代价f1、航行距离代价f2、航行时间代价f3，建立优化目标函数。

（1）能量消耗代价f1

UUV的航行路径由从起点至当前点的一系列离散点依次表示，它是1个动态变化的集合，Path={p1，p2，…，pi，…，pn}。 其中，pi=(xi，yi)为第i步经过的坐标点，n为途径点总个数。设相邻2个路径点构成1个路径段li，i+1，每个路径段li，i+1的

图5 路径段速度合成示意图Fig.5 Schema of velocity composition in path section

由图5可知

由三角函数关系可得

式中，θri、θsi、θci分别为第i段路径的合速度、静水速度、海流速度与水平方向的夹角，取逆时针方向为正。

式中，ρ为由UUV尺寸和水流特性决定的常数。对于一条给定的路径Path，其能量消耗代价f1为

（2）航行距离代价f2

航行距离代价的定义类似于文献［10］中的适应度函数，航行距离为历史途径距离与未来预测距离之和。Path路径对应的航行距离代价f2为

式中，f2为给定的路径Path对应的航行距离代价值，dH为历史途径距离，dF为未来预测距离，（xHi，yHi）为Path路径中历史途径栅格集中于第i个栅格所对应的坐标，（xP，yP）、（xN，xN）、（xE，yE）分别为途径点j的当前栅格、将访栅格、终点栅格所对应的坐标。

（3）航行时间代价f3

由此建立的目标函数为

式中，w1、w2、w3分别为3个子目标所占的权重。

2.3 约束条件设计

（1）最大转弯角约束

由于UUV视角范围和机动性能的限制，UUV在某一时刻的转弯角存在一定的范围。因此，要求在每一途径点i处的转弯角φi不超过最大转弯角φmax，即有

（2）最小转弯半径约束

由于UUV尺寸和最大转弯角的限制，UUV在某一时刻的最小转弯半径存在一定的范围。因此，要求在每一途径点i处的转弯半径ri不小于最小转弯半径Rmin，即有

图6 转弯角定义示意图Fig.6 Sketch of turn angle definition

2.4 约束问题无约束化等效

利用文献［10］中的外罚函数法将该问题转化为无约束单目标非线性规划问题，取一个充分大的数M（M＞0），构造增广目标函数

因此，可将该复杂的数学模型转化为无约束的极值问题，即有

3 改进烟花-蚁群算法的UUV避障路径规划

在求解UUV避障路径规划数学模型时，针对该转化后的无约束非线性极值问题，本文使用了文献［10］提出的改进烟花⁃蚁群算法进行求解。

烟花算法［10］是一种新颖的优化算法，其具有局部搜索能力和全局搜索能力的自调节机制，同时其种群具有多样性，针对大规模的复杂优化问题，具备良好的搜索效率。但是，对于基本烟花算法，烟花产生机制没有利用火花群中其他优秀火花的位置信息和整个群体信息，火花之间交流较少。另外，当将烟花算法应用到终点栅格不位于搜索区域中心或区域中心附近位置时，搜索过程中会出现大量 “迷失”的火花，产生很多非完整路径。为解决基本烟花算法中存在的种群信息交流不足和映射规则不尽合理的缺陷，提出了“先锋火花”的概念。先锋火花增强了群体间的信息交互，增加了火花粒子的多样性，提高了算法的搜索精度和收敛速度。

3.1 先锋火花生成规则

先锋火花生成规则与基本烟花生成火花的区别在于烟花爆炸算子和映射规则的不同。

（1）先锋火花爆炸算子

①爆炸强度

由先锋烟花产生的先锋火花个数为

其中，Sp为产生的先锋火花的个数；coefp为先锋火花数系数，用来限制生成的先锋火花的个数；Dmax、Dmin分别为当前种群中火花所在栅格到终点栅格距离的最大值和最小值；Dp为先锋烟花所在栅格到终点栅格的距离。

②爆炸幅度

先锋烟花爆炸幅度的范围公式为

其中，Ap为先锋烟花爆炸的幅度范围，Maxp、Minp分别为先锋烟花爆炸幅度的最大值和最小值。

（2）先锋火花镜面映射规则

先锋火花使用 “镜面映射”规则对超出搜索区域边界的先锋火花做映射操作，镜面映射规则的计算公式为

3.2 改进烟花-蚁群算法

改进烟花算法能以很快的速度实现收敛，但得到的最优路径并不是有效路径。该路径存在跨越障碍物的现象，这是因为爆炸火花的搜索方式为不连续的跳跃式搜索，故而所寻路径不可避免地越过了障碍物，形成无效路径。

鉴于改进的烟花算法能以很少的迭代次数和初始烟花数快速寻找到一条从起点栅格到终点栅格的最优路径，因而可以将此路径作为参考路径，再与其他群的智能优化算法结合，快速找到最短的全局有效路径。

可以结合改进烟花算法和蚁群算法的优点，克服各自缺陷，找到一条有效的全局最优路径。改进烟花⁃蚁群混合算法首先利用改进烟花算法产生1条初始参考路径，然后将其转化为蚁群算法的初始信息素分布。该混合算法在时间效率和精度上均分别优于改进烟花算法和蚁群算法，是求解优化问题的一种新方法。

（1）改进烟花算法与蚁群算法的衔接

（2）混合算法的路径点选择

其中，allowedk={C-tabuk}为蚂蚁k下一步允许选择的栅格，C为所有栅格的集合，α为信息启发式因子，β为期望启发式因子，ηmn（l）为启发函数，ηmn（l）=1/dmn，dmn为相邻两栅格m、n的中心点距离。

（3）混合算法的信息素更新

该混合算法的信息素更新公式为

其中，ρ（0≤ρ＜1）为信息素残留因子，1-ρ为信息素的挥发系数；Lc为蚂蚁周游最优路径长度；Lw为改进烟花算法寻找到的最优参考路径长度；ak、bk为整型变量，分别代表周游蚂蚁寻找到的路径和改进烟花算法寻找到的路径更新信息素的权重，其和为常数K；Q0为信息素强度，为一常数。

初始时刻的Δτmn（0）将信息素强度Q0均分到改进烟花算法寻找到的全局最优参考路径Lw上，其计算公式为

4 仿真实验验证

4.1 实验参数设置

为验证改进烟花⁃蚁群混合算法在UUV避障路径规划中的优越性，对提出的算法进行了仿真实验，并将其与基本蚁群算法的路径规划效果做出了对比。

基本蚁群算法的参数设置为：蚂蚁数目Na=30，最大迭代次数Ma=50，信息启发式因子α=1，期望启发式因子β=7，信息素残留因子ρ=0.3，信息素强度Q0=200。

目标函数权重w1、w2、w3分别为0.5、0.2、0.2，与UUV尺寸和水流特性相关的常数ρ=10。

4.2 实验结果及分析

为了比较改进烟花⁃蚁群混合算法和基本蚁群算法在UUV避障路径规划中的优劣，主要比较了2种算法寻找到的避障最优路径的平均适应度值收敛速度、最优路径适应度值和计算时间。这里得到了在40km×40km的平面海域内，在含有10个随机障碍物、8个随机涡流的海流环境下，2种算法的避障最优路径的仿真实验结果，如图7～图11所示。

图7是改进烟花算法寻找到的最优路径。由图7可知，改进烟花算法可以有效利用海流能量，较好地顺着海流流向，避开逆流海流，同时兼顾航行距离最短的目标。但是，由于烟花算法跳跃式搜索的特点，寻找到的路径会跨越部分障碍物，致使寻找到的路径为无效路径。获得该路径计算用时为4.23s，且收敛速度较快。

以图7得到的路径为参考路径，利用改进烟花⁃蚁群混合算法寻找到的避障最优路径的平均适应度值收敛曲线和最优路径分别如图8、图9所示。由图8可知，该混合算法能够快速得到全局最优解，大约迭代15次后便趋于收敛。由图9可知，改进烟花⁃蚁群混合算法所得路径不仅能尽量靠拢参考路径，还可以有效避障，充分发挥了烟花算法和蚁群算法各自的优势。

图8 改进烟花-蚁群混合算法避障最优路径平均适应度值收敛曲线Fig.8 Convergence curve of average fitness value of optimal path avoiding obstacles for improved fireworksant colony hybrid algorithm

图9 改进烟花-蚁群混合算法寻找到的最优路径Fig.9 Optimal path found by improved fireworks-ant colony hybrid algorithm

图10、图11分别为两种算法得到的避障最优路径的平均适应度值收敛曲线和最优路径对比结果。由两种算法在海流环境下的平均适应度值收敛曲线可知，改进烟花⁃蚁群算法能在5～15次迭代左右快速寻找到全局有效最优路径，而基本蚁群算法在迭代50次时才勉强寻找到次优路径。由两种算法在海流环境下的最优路径对比可知，改进烟花⁃蚁群算法能够充分利用参考路径信息，兼顾路径距离代价和避障，而基本蚁群算法会出现逆海流航行路径，寻找到的路径距离也不是全局最优的。环境越复杂，基本蚁群算法的劣势表现得越明显，而改进烟花⁃蚁群算法仍能快速、高精度地在参考路径附近寻找到全局有效最优路径。

图10 基于改进烟花-蚁群混合算法、蚁群算法的平均路径长度收敛曲线对比Fig.10 Comparison of convergence curves of average path length based on improved fireworks-ant colony hybrid algorithms and ant colony algorithm

图11 基于改进烟花-蚁群混合算法、蚁群算法寻找到的最优路径对比Fig.11 Optimal path comparison based on improved fireworksant colony hybrid algorithm and ant colony algorithm

由表1可知，改进烟花算法能在非常短的时间内寻找到参考路径。在同样的环境和参数下，改进烟花⁃蚁群混合算法的计算时间约为基本蚁群算法的一半。就寻找到的最优路径的精度而言，改进烟花⁃蚁群混合算法基本找到了客观上的最优路径，而基本蚁群算法的最优路径精度则较低。实际上，该混合算法在很少的迭代次数下就寻找到了全局有效最优路径，因而该算法实际寻找到的最优路径的时间比表1中还要短很多。

表1 算法结果比较Table 1 Comparison of algorithm results

5 结论

本文针对考虑海流和障碍物影响的二维海流环境下UUV避障路径的规划问题，建立了含有随机分布障碍物的二维海流环境模型和综合考虑能量消耗代价、航行时间代价、航行距离代价的路径规划数学模型，应用改进烟花⁃蚁群混合算法对该非线性优化问题进行了求解。实验结果表明，该算法能够快速寻找到全局最优解，为水下无人潜航器避障路径的规划提供了一个新途径。