基于势场启发蚁群算法的远程水中兵器航路规划

刘海光，孙明太，王桂芹

（1.海军航空工程学院青岛分院，山东青岛 266045；2.海军潜艇学院，山东青岛 266199）

基于势场启发蚁群算法的远程水中兵器航路规划

刘海光1，2，孙明太1，王桂芹2

（1.海军航空工程学院青岛分院，山东青岛 266045；2.海军潜艇学院，山东青岛 266199）

针对航行误差较大的远程水中兵器航路规划问题，采用栅格化方法建立海洋环境模型，为使兵器在航行过程中能有效规避障碍并导向目标，提出一种人工势场力为启发因子的改进蚁群算法，利用该方法搜索远程水中兵器从起始点至目标点的最佳路径，算法解决了经典蚁群算法容易陷入局部最优及收敛速度慢的问题。仿真结果表明该规划算法虽有少量的路径损失，但可以有效避免由于误差引起的航行安全问题，是一种有效的远程水中兵器航路规划方法。

蚁群算法；远程水中兵器；航路规划；人工势场；栅格法

远程水中兵器是一种水下远距离航渡到作战海域，自主执行作战任务的水中兵器，其航渡时间长、航程远，航途障碍多、敌情复杂。因此为其规划安全航路以便顺利到达作战海域是其作战任务顺利完成的前提。相对于短程水下航行器的航路由人工控制，远程水下航行器航路一般自主控制。随着远程水下航行器不断出现，其航路规划逐渐成为研究的热点，形成了几何模型搜索、虚拟势场及导航函数、典型生物智能和数学优化四种方法［1］。几何模型法通过建立障碍物模型，采用一定优化算法进行搜索寻找最优解，方法简单，但较难考虑约束性条件影响，可用来进行无约束条件的航路规划。虚拟势场法算法简单，执行效率高，多使用于局部路径规划，文献［2］在考虑了海流影响下使用虚拟势场法进行水下航行器航路规划。生物智能法较多，典型的有遗传算法、蚁群算法、粒子群算法及各智能算法的组合等，这些算法多考虑约束条件的影响，适合于全局路径规划，文献［3⁃4］分别利用遗传算法及蚁群算法对水下航器进行了路径规划。文献［5］将各种约束转换为数学多项式，并利用数学优化方法求最优解，数学优化法较容易考虑动力学约束条件，计算速度快，但构建合适的数学模型较为困难。

远程水中兵器航渡阶段速度低，航向受水下环境及惯导控制精度影响大，需定时上浮校准位置，当由于敌情等原因无法正常上浮时，其航向累积误差较大。为提高环境适应性、隐蔽性及航行安全性，同时需将敌情敏感区域也作为障碍考虑到环境中。航路规划应综合各种因素规划一条从发射点到目的地，隐蔽性高、同时兼顾航行安全性和航程指标的全局最优路径。蚁群算法作为智能路径规划算法的一种，具有良好的通用性、鲁棒性和开放性，本文选择它为基本算法规划远程水中兵器航路。但标准蚁群算法也存在着容易陷入局部最优及收敛速度慢等缺点，因此在具体使用时应根据具体任务进行算法改进。为使远程水中兵器在发生较大航行误差的情况下能有效规避水中障碍，同时加快算法运算速度，本文提出一种人工势场为启发信息因子的改进蚁群算法进行远程水中兵器航路规划，算例表明该方法考虑了在较大航行误差下能够避开威胁，实现了远程水中兵器航路选择与优化的目的。

1 环境表达

栅格化方法是处理大型地图建模的经典方法［6⁃7］，本文采用栅格化方法将整个航渡海域海图划分为二维网格，进行编码，并利用海图给出的数据和敌情信息，判断海域水深、障碍物、封锁区域、适航区域等信息。用网格编码代表远程水中兵器在海域中的位置，将编码统一映射为网格的左下角坐标，并用相对位置来表示网格间的位置关系。用逻辑变量来表示网格的状态，1表示障碍，0表示自由海域，如图1所示，黑色表示障碍，白色表示自由区域，整个网格可以形成一个二维矩阵。图中网格中箭头表示每个自由海域网络可以移动路径的方向。根据蚁群算法搜索路径原理，蚂蚁可以从起始节点出发，沿箭头方向移动到下一网格并最终到达目标点，可选路径有很多种，经过反复选择搜索到一条路径最短且满足条件的最佳路径。路径长度计算方法为：设网格边长为a0，则任意相邻两个网格（x1，y1）、（x2，y2）间的距离J为

图1 网格划分及其相互关系图

2 航路规划算法设计

2.1 改进蚁群算法

蚁群算法利用蚂蚁在所经路径上留下的信息激素作为后续蚂蚁选择路径的依据，并通过蚁群协同来完成路径选择。总数为N的蚂蚁在路径的网格间可选择的网格范围内，根据路径选择的规则选择下一个网格，在第t次搜索中，从网格i选择网格j的概率pi，j（t）定义为

式中，τi，j（t）为第t次循环搜索时网格i到网格j路径上的信息素浓度，ηi，j为该路径上的启发信息，α为信息素浓度的权值，β为启发信息的权值，allowedk表示约束条件下节点i的可移动节点集合。蚂蚁从初始节点出发，根据节点转移概率不停地在节点间进行选择，最后到达目的地，完成一次路径搜索。到达目的节点后，需要对路径上的信息素进行更新，为加快算法的收敛速度，设置更新规则如下：算法的目的是为了寻找满足条件的最短路径，因此可以根据路径长度来确定解的优劣，在完成一次搜索后，必然产生最优解Jmin和最差解Jmax。为加快算法运算速度，只对接近最优解的路径信息素进行更新。更新条件为，待更新信息素的路径长度Jx满足：

更新规则为

式中，ρ为信息消散指数。Δτi，j为新增加的信息素浓度。其与该次搜索途径路径长度成反比，路径较短的被附加更多的信息素。

式中，C为常数，为蚂蚁释放的信息素总量。

2.2 人工势场法

人工势场法是一种利用虚拟势场力来进行路径规划的方法，它假定工作区域内的目标点产生吸引力场，同时障碍点产生排斥力场，利用引力场和排斥力场的综合作用进行航路规划［8］。目标位置为G，在水中兵器位置P处引力场可表示为

式中，ζ为引力系数，d（P，G）为兵器与目标的距离。可以看到兵器与目标的距离越大吸引力越大，引力梯度函数为

式中，nG为兵器指向目标点的单位矢量。在位置Po处有障碍物，其对兵器产生斥力，斥力场函数为：

式中，d0为一常数，λ为斥力场常数，表示斥力场的作用范围。兵器所受到的斥力可以表示为：

式中，nO为兵器指向障碍物的单位矢量，由此兵器在海域中所受的引力与斥力的合力为：

2.3 启发信息

由标准蚁群算法可知，当不同路径上的启发信息差别比较大时，蚁群算法的搜索能力就会变弱，容易陷入局部最优。可选网格到目标网格的距离，一定程度上反应了路径的优越程度，应该让较优的路径有相对较大的概率被选择；本文定义待选网格到目标网络距离的倒数为启发式信息的因子Δηij（t）。待选网格到目标网格的距离差别不大，这样可以适当增加较差路径被选择的概率，既保证了路径选择的随机性又能避免算法过早地出现局部最优。

当出现较大航向误差时，引入人工势场法可实现远程水中兵器快速规避障碍。因此当兵力与障碍距离较远，启发式信息应主要由式（12）决定，而当兵器与障碍间的距离较小，蚂蚁在选择路径时应受到信息素和势场力的双重作用。兵器所处位置的Ft大小一定程度上能够表征该节点与障碍或目标的距离，如果Ft较大，说明该网格靠近障碍或目标，应在势场力的启发下尽快远离或接近该区域，则有助于保证兵器航行安全。为发挥蚁群算法与人工势场算法的优势，将两部分的因素综合考虑，共同决定蚂蚁状态转移的启发信息ηij（t）。

式中，θ表示可选择路径方向与合力Ft方向的夹角。这种情况下，当Ft较大或可选路径方向与Ft角度接近时，被选中的概率会较大，主要由势场力来决定兵器移动的方向，便于兵器远离障碍及导向目标。

3 算法实现步骤

结合改进的蚁群算法和人工势场法进行远程水中兵器的航路规划，具体实现步骤及详细流程如图3所示。

图2 算法流程图

4 算例分析

为验证算法有效性，将兵器航渡区域离散化成40× 40的网格。蚂蚁起始点坐标为（0，0），目标点G坐标为（40，40）。蚁群算法参数初始化为：信息素权值α为1，启发信息权值β为3，信息素总量参数C为3，信息消散系数ρ为0.7，蚂蚁总数量M为20只，最大迭代次数为100。引力场参数设置为：引力系数ζ为2，斥力系数η为2，斥力作用距离d0＝3个单位长度。利用Matlab进行计算，最终输出的最优路径如图3所示，路径长度为72.385个单位长度，最优解的迭代过程如图4所示。

为验证本文算法的先进性，使用相同的参数设置方式，利用标准蚁群算法对相同的环境进行航路规划，输出结果如图5所示，最优路径长度为68.798个单位长度。迭代过程如图6所示。通过比较可以看到，相对于标准蚁群算法，势场启发的蚁群算法具有相对较快的收敛速度，为消除航行误差对航行安全的影响，在临近障碍时采取了一定的“平滑”过渡，兵器航行路径与障碍间距离加大，更容易规避航路中的障碍，航行安全性更高。其最优路径长度比标准蚁群算法约有5%的航程损失，但为保证航行安全，少量的航程损失也是有必要的。

图3 势场启发蚁群算法路径规划

图4 势场启发的蚁群算法迭代过程

图5 标准蚁群算法路径规划

图6 标准蚁群算法迭代过程

5 结束语

蚁群算法开放性较好，方便与其它算法结合使用，以充分利用各种算法的优势。本文针对远程水中兵器航渡阶段速度低，航行误差较大等问题，在改进蚁群算法的基础上，通过将人工势场力作为改进蚁群算法的启发因子，实现了远程水中兵器的航路规划。仿真结果表明改造后的算法比标准蚁群算法收敛速度快，在面对水中障碍时能够以相对平滑的方式规避，在牺牲小部分航程为代价的基础上，可有效避免航行误差对航行安全性的影响。表明该方法为一种可行的远程水中兵器航路规划方法。

［1］ 王奎民.水下潜器的航路规划技术综述［J］.智能系统学报，2014，9（6）：563⁃658.

［2］ 吴正平，等.基于改进人工势场法的AUV路径规划［J］.化工自动化及仪表，2014，41（12）：1421⁃1423.

［3］ 张京娟.基于遗传算法的水下潜器自主导航规划技术研究［D］.哈尔滨：哈尔滨工程大学，2003：29⁃35.

［4］ 刘利强.蚁群优化方法研究及其在潜艇导航规划中的应用［D］.哈尔滨：哈尔滨工程大学，2007：35.

［5］ Singhr.Path planning using Shi and Karl level sets［S］. Proceedings of the 1st International Conference on Robot Communication and Coordination.Piscataway.USA，2007：2829⁃2832.

［6］ 曲镜圆.基于声纳的AUV环境感知与地形建模方法研究［D］.哈尔滨：哈尔滨工程大学，2009：12⁃22.

［7］ Duan Hai⁃bin，Yu Ya⁃xiang，Zhang Xiang⁃yin.Three di⁃mension path planning for UCAV using hybrid meta⁃heu⁃ristic ACO⁃DE algorithm［J］.Modeling Practice and Theo⁃ry，2010，18（8）：1104⁃1115.

［8］ 罗德林，吴顺祥.基于势场蚁群算法的机器人路径规划［J］.系统工程与电子技术，2010，32（6）：1277⁃1280.

Remote Underwater Weapon Path Planning Based on Ant Colony Optimization Inspired by Field Heuristic

LIU Hai⁃guang1，2，SUN Ming⁃tai1，WANG Gui⁃qin2
（1.Qingdao Branch of Naval University of Aeronautics＆Astronautics，Qingdao 266045；2.Navy Submarine Academy，Qingdao 266199，China）

Aimming at the problems of path planning for the remote underwater weapon with large navigation error，a grid method is used to establish the model of marine environment，in order to enable the weapon to be able to move effectively a⁃way from the barrier in the navigation，an improved ant colony optimization algorithm is proposed，and the artificial potential field is a heuristic factor of it.This algorithm is used to search for the best path of the remote underwater weapon from the starting point to the target point，and solves the problems that the standard ant colony algorithm is easy to fall into local opti⁃mum and has slow convergence speed.Simulation results show that the path planning algorithm brings a small amount of path loss，but it can avoid the problem of navigation safety due to the error.This algorithm is an effective path planning method for the remote underwater weapon.

ant colony algorithm；remote underwater weapon；path planning；artificial potential field；grid method

TJ630；E917

A

10.3969／j.issn.1673⁃3819.2016.06.009

1673⁃3819（2016）06⁃0042⁃04

2016⁃07⁃21

2016⁃08⁃18

刘海光（1975⁃），男，山东济宁人，博士研究生，讲师，研究方向为水中兵器保障与应用。

孙明太（1961⁃），男，教授，博士生导师。

王桂芹（1977⁃），女，副教授。