基于多蚁群协同搜索算法的多AUV 路径规划

岳 伟，席 云，关显赫

(大连海事大学 船舶电气工程学院，辽宁 大连，116026)

0 引言

随着人们对海洋认识和开发力度的不断深入，勘探、绘制地形图、清理化学物质泄漏、排雷和探测水下目标等水下作业常常借助自主水下航行器(autonomous undersea vehicle，AUV)完成。但是，由于AUV 自身携带动力能源有限，已不能满足人们的需求[1]。为了使AUV 能够在复杂、多变、难以预测的水下环境中，在有限的时间内高效地完成任务，多AUV 技术成为AUV 研究和发展的必然趋势[2-3]。

国内外学者对AUV 路径规划问题已开展了广泛的研究，主要有自组织神经网络算法[4]、粒子群优化算法[5]和蚁群算法[6]等。Wang 等[6]提出了一种简单的蚁群优化元启发式算法来解决AUV 的路径规划问题，寻找一条从起点到终点避开障碍物的最短路径。朱大奇等[7]基于自组织神经网络，引入栅格信度函数概念，提出一种改进的栅格信度自组织(belief function self-organizing map，BFSOM)算法，在已知目标确切位置的情况下对栅格信度函数赋值，每次路径点选择过程中需要将目标位置和AUV 位置比较，根据距离最近的原则实现对目标位置的访问。文献[6]和[7]需要在已知目标位置的前提下规划安全可行的路径，与传统的从起点到终点生成避障路径的规划任务不同，搜索路径规划因不确定目标位置而变得复杂。Wen 等[8]将蚁群算法与自组织神经网络相结合，提出了一种全覆盖路径规划方法，但仅适用于单个AUV。为了提高目标发现概率，张跟鹏等[9]将2 个AUV 以固定的队形，对搜索区域进行搜索直至完成对任务区域的全覆盖，理论上只要时间足够长，该算法一定可以发现任务区域内存在的目标，但耗时较长，同时2 个AUV 的检测区域存在部分重叠，虽然增加了重叠区域检测的可信度，但也浪费了有限的传感器资源，搜索效能较低。为了减少AUV 的平均搜索时间，提高目标发现概率，Yoon 等[10]提出了一种基于初始目标信息的多AUV 分布式协同搜索策略。上述研究需要在不同水深条件下，并假设AUV 搭载合成孔径声呐，在同一平面实现对不同深度目标的探测。AUV 执行搜索任务时需要考虑目标发现概率和声呐探测距离的关系，以及AUV 之间的避碰约束，上述方法并未对此进行综合考虑，因此规划的结果并不能很好的反映AUV 协同搜索的需求。

针对上述搜索算法效率低，优化目标单一的问题，文中假设采用合成孔径声呐对不同水深的目标探测，并提出基于先验信息的多蚁群协同搜索算法。主要研究内容如下：

1) 假设搭载合成孔径声呐可以在某一水平面对不同深度水下目标探测，首先建立二维正态分布的目标概率图，进一步地根据目标概率图初始化种群信息素浓度；

2) 算法综合考虑目标发现概率以及AUV 转向等因素，设计路径选择策略和信息素更新规则，以减少对航路点的重复选择，从而提高目标发现概率；

3) 在信息素更新时，根据搜索路径的收益值调整信息素浓度，增加收益值高的路径信息素浓度，加快算法收敛速度。同时限制信息素浓度范围，避免算法过快收敛。最后，通过仿真验证该算法的有效性。

1 问题描述

在完全未知的水下环境中，使用多个相同类型的AUV 对若干个目标执行搜索任务，AUV 上载有探测设备(合成孔径声呐)，声呐最大探测宽度为R，AUV 以自主协同的方式对任务区域展开搜索，期望以最小的代价在任务区内快速发现目标，图1给出了多AUV 协同搜索目标的场景。

图1 多AUV 协同搜索场景Fig.1 Scenario of cooperative search using AUVs

1.1 环境建模

文中采用栅格法对未知位置的水下目标进行建模。将长为Lx，宽为Ly，深为hz的海域划分为三维栅格，设每个栅格位置对应目标存在概率值为pijk。为减少在执行搜索任务过程中AUV 频繁的上浮或下潜，这里设三维空间中每个栅格的目标存在概率pijki，将该概率向xoy平面做投影，如图2 所示，可得横纵坐标相同的所有栅格中目标存在的概率为pij，其中i为栅格的横坐标，j为栅格的纵坐标。pij=pijk1+pijk2+…+pijkn(kn为z轴方向栅格数)。

图2 目标分布示意图Fig.2 Diagram of target distribution

1.2 目标概率图模型

根据建立的搜索环境模型，先验信息只要知道目标位置的横纵坐标，就可建立目标初始概率分布。目标位置的不确定性决定了文中研究的搜索本质上是一个随机问题，对不确定环境下的目标进行搜索，通常采用正态分布函数来描述目标的存在状态，即每个目标具有相同的概率分布。根据先验信息已知目标m的初始位置为()，则目标m初始位置的联合概率密度函数可表示为

2 搜索效能指标

在多AUV 执行搜索任务过程中存在以下问题：

1) 由于AUV 间的通信能力随着机间距离增加而严重衰减，因此需要AUV 间保持在通信范围内，但同时增加了AUV 碰撞的可能性；

2) AUV 能量有限，频繁转向也会增加能量消耗，因此需要减少转向带来的能量消耗，文中引入转向代价函数。

式中：θmnθ为AUVm第nθ次转向时转向角度的绝对值；Cθ为系数；Nθ为总的转向次数。

在AUV 协同搜索问题路径优化过程中，不可避免地会出现各AUV 间路径重合的情况。在相同的一段时间内，各AUV 间路径重合易造成AUV 间的碰撞，重合的航路点数目越多，则该航路的威胁代价越大，因此在AUV 航路优化过程中，避免选择威胁代价高的航路，定义为AUVm，v的碰撞威胁代价如下

式中，lapped为不满足安全距离约束的航路点的数目；Cc为系数。

AUVm的威胁代价表示为

AUV 协同目标搜索问题中，优化的搜索路径应该以最小的代价尽可能以最大的概率发现目标。由此可以得出协同搜索属于一类组合优化问题，文中建立如下搜索效能指标函数：

式中：K为系数；N为搜索路径栅格数目；zi为目标距离水平面距离；h为AUV 距水平面距离；为AUVm的航行代价。

3 多蚁群搜索算法

由于多AUV 搜索目标与蚁群觅食行为极为相似(见表1)，文中利用多蚁群算法进行多AUV协同路径优化设计。将蚂蚁分为Nv个种群，每个子群分别对应1 个AUV，将各子群间通过信息素的传递完成觅食搜索的能力应用于具有通信能力的多 AUV 协同搜索目标的任务中。定义蚁群AC=｛AC j，j=1，2，…，Nv｝为AUV 对应的蚂蚁种群数目，各子群定义为ACj=｛Ant l，l=1，2，…，M｝，其中M为各子群中的蚂蚁个数。多蚁群算法的结构如图3 所示。各子群中每只蚂蚁都具有1 个独立的运算单元，依据设计的搜索规则及与其他蚂蚁交互信息来进行局部优化，下文将分别从信息素初始化、路径转移以及信息素更新分析蚁群如何为多AUV 进行协同路径优化。

表1 多AUV 协同搜索与蚁群觅食行为关系Table 1 Relationship between multi-AUVs cooperative search and ant colony foraging behavior

图3 基于多蚁群算法AUV 协同搜索结构图Fig.3 Structure of cooperative search for multi-AUVs based on multi-ant colony algorithm

3.1 信息素初始化

为充分利用已有的先验信息，使各蚁群中的蚂蚁尽可能提高目标发现概率，提出如下信息素初始化函数

式中：τi0表示栅格i的信息素浓度；pi为每个栅格中的目标概率值；τ0为常数。该初始函数可有效地将信息素初值与搜索区域目标信息进行关联。

3.2 路径选择策略

每只蚂蚁按照状态转移规则从起点选择下一个栅格，在t时刻第l只蚂蚁从栅格i转移到栅格j的状态转移规则设计如下

式中：UK为当前可作为下一跳的栅格集合，UK=N-Tabuk，且Tabuk 表示已访问过的栅格集合；ηij为路径的启发信息，且，k1和k2为常数；φjk(t)表示其余蚂蚁子群信息素在栅格j处的值；α为在栅格选择中信息素的重要程度；β为启发信息在蚂蚁选路决策中的重要程度；γ为其他种群的信息素对航路点选择的影响，γ越大抑制作用越强，可以避免不同AUV 之间对航路点的重复选择。

3.3 信息素更新规则

信息素更新分为局部信息素更新和全局信息素更新2 个阶段[11-12]。在局部信息素更新过程中基于排序蚂蚁算法进行设计，选出每一次迭代中部分优秀的个体信息素进行增强，在引导后代蚂蚁搜索的同时，保证了部分搜索较差蚂蚁的生存能力，有利于搜索的多样性，同时考虑各代蚂蚁搜索路径的优劣，采取不等量信息素增强方式，信息素的增强量和每一只蚂蚁搜索效能密切相关。

3.3.1 局部信息素更新

针对传统的信息素更新容易出现停滞的情况，提出一种改进信息素更新方式： 根据搜索路径解的优劣情况，动态地修改信息素更新方式。一方面保证了搜索空间足够大，以尽可能寻找最优解，另一方面有效地将当前解的信息重点放在适应值较优的个体，从而加快收敛到全局最优解[12-13]。

在每一次迭代过程中，对蚂蚁经过的栅格进行信息素更新，栅格j处的信息素按下式进行更新

式中：τjk(t+1)和τjk(t)分别是更新前后网格j内第k个种群信息素的值；ρ为信息素挥发系数；Δτjk(t+1)是信息素更新值，信息素按下式更新

3.3.2 全局信息素更新

在整个蚁群完成一次迭代后，选出每个种群中本次迭代解最优的蚂蚁，信息素按下式更新

式中：k*为权值；f（Jklbest）为种群k中最优搜索收益函数。

在局部信息素更新时采用不等量信息素增强方式，可加快算法的收敛速度，但同时会导致陷入局部最优，为避免这种情况的发生，将栅格内每个种群k的信息素浓度限制在［τmin，τmax］，保证算法快速收敛速度的同时增加搜索空间，综合局部和全局的信息素更新规则

4 仿真结果与分析

为了验证文中算法的有效性，在 Matlab 2015b 环境下建立了多AUV 协同搜索仿真环境，采用3 个AUV 对区域为20 km ×20 km海域进行搜索，声呐的探测半径R=1000 m，将搜索海域分成20 × 20的栅格(声呐每次完全覆盖一个栅格)，区域内存在10 个深度不同的目标，每个栅格同一时刻最多只存在一个目标，目标概率分布如图4 所示。为验证算法的有效性，将从多个角度进行仿真，并和传统的搜索方法进行对比。

图4 目标分布概率图Fig.4 Diagram of target distribution probability

情景1： 给出步长为30，40，50 条件下的搜索路径图。3 个AUV 的初始位置分别为(1，1)，(1，16)，(20，19)，如图5 所示。

图5 多蚁群算法搜索路径Fig.5 Search path of multi-ant colony algorithm

图5 中，3 种步长情况下AUV 分别发现5 个，6 个和7 个目标，增加步长可以提高目标的发现概率，但需要浪费更多的算力，以及更长的搜索时间。

情景2： 并行搜索、贪婪搜索和未改进蚁群算法的搜索路径如图6 所示。从图中可以看出，步长40 条件下，文中搜索方法明显优于并行(发现3 个目标)和贪婪算法(发现5 个目标)，未改进的蚁群算法虽然也发现了6 个目标，但是AUV 之间存在较高碰撞概率，且存在大量重复搜索路径和频繁的转向，搜索效能较低。

图6 其他算法搜索路径对比Fig.6 Comparison of search paths of other algorithms

情景3： 相同数目的AUV 在不同搜索方式下的目标发现概率(若对同一栅格重复搜索，目标发现概率只算一次)。在计算目标发现概率时考虑声呐探测距离与目标的相对距离。以步长60 为例，在20 km ×20 km的搜索区域内3 个AUV 发现概率随搜索时间的变化。从图7 可知，前50 步并行算法效率最低，随着搜索时间的增加，并行算法超过了贪婪算法，发现贪婪算法和文中方法目标发现概率几乎相同，并行搜索发现概率较低；当搜索步长大约40 时，贪婪算法目标发现概率增加缓慢，主要原因是随着搜索步长的增加，贪婪搜索路径重叠严重；在搜索步长到50 时，并行搜索发现概率超过贪婪搜索；步长为60 时，文中算法目标发现概率约为75%，因种群间缺乏交流机制，未改进的蚁群算法目标发现概率约为69%，且始终低于改进多蚁群算法。

图7 不同算法目标发现概率比较Fig.7 Comparison of search probabilities of different algorithms

情景4： 50 次仿真不同算法搜索到的目标数目。表2 是3 个AUV 在20 km×20 km 区域，搜索随机分布的10 个目标，50 次仿真所得4 种方法不同步长搜索到的目标平均数目。

表2 不同方法下搜索目标数目比较Table 2 Numbers of search targets by different methods

文中方法在步长为20 时，平均发现目标3.3个；步长为60 时，平均发现目标8.3 个。可以看出，文中方法搜索目标数目远高于其余3 种算法。

情景5： 在搜索步长为40 时，经过200 次迭代搜索效能的变化。传统蚁群算法和改进后的蚁群算法搜索效能和迭代次数比较如图8 所示。图中：a是在传统蚁群算法信息素的更新方式下，按照蚂蚁经过次数等量的增加每条路径的信息素浓度，经过约110 次迭代，最佳搜索效能为17.3；c是在传统蚁群算法基础上加快收敛速度的结果，约经过40 次迭代，搜索效能为16；b是对收敛速度和避免过快收敛折衷处理后的结果，经过60 次迭代，最佳搜索效能约为17。可见，改进的信息素方式在加快收敛速度的同时，还能保证解的质量。

图8 搜索效能对比曲线Fig.8 Comparison curves of search effectiveness

5 结束语

文中基于搜索目标随机分布的概率图特点，建立多个指标(包括搜索率、转弯次数、避碰和重复路径等)，提出一种改进的多蚁群优化算法，充分考虑目标存在概率和转向的影响，各种群之间通过信息素的排斥，减少对其他种群选择过的航路点的重复选择。仿真结果表明，该算法实现AUV 协同目标搜索，有效减少航路重合，以较大概率发现目标。下一步研究中将进一步考虑AUV协同搜索时存在通信受限、涌浪干扰、可见度低等问题，以期得到更符合实际的搜索方法。