基于改进蚁群算法的多自主式水下机器人任务分配

刘瑞轩，张永林

江苏科技大学 电子信息学院，江苏 镇江 212003

0 引 言

自主式水下机器人（AUV），即在与母船之间没有物理连接且无人驾驶的情况下，依靠自身携带的动力自主完成复杂任务的机器人。AUV的应用范围非常广，如海底考察、海底管线铺设和水下设备维修等民用领域［1-2］，以及海底排雷、侦察和救生等军用领域。对单个AUV而言，其功能和容量均非常有限，难以满足大规模的任务需求。因此，多个AUV系统的概念应运而生，即通过多个AUV相互协调共同完成复杂的水下作业任务。这不仅可以弥补单个AUV的不足，也可以提高综合作业效率。

目前，多机器人的任务分配方法主要包括基于行为的分配方法［3］、市场拍卖算法［4-5］和群体智能算法［6］。其中，基于行为的分配方法的实时性和稳定性较好，但只能求取局部最优解；市场拍卖算法的实时性差且系统配置要求较高，但可以求取全局最优解；群体智能算法分为粒子群算法、鱼群算法和蚁群算法，该算法的鲁棒性好且计算效率较高。近年来，机器人自主任务分配方面的研究取得了较大进展，但鲜有多自主式水下机器人（MAUV）方面的研究［7］。

蚁群算法是一种模拟蚂蚁群体智能行为的仿生优化算法，该算法利用生物信息作为蚂蚁后续行为选择的依据，并通过蚂蚁协同作业来完成寻优过程［8］。蚁群算法多用于路径规划［9-10］及组合优化［11］等研究领域，而将蚁群算法用于MAUV任务分配方面的研究则较少，因为基本蚁群算法存在搜索时间较长和容易陷入局部最优解的缺点［12］。本文将以MAUV执行海底地形勘察任务为应用背景，针对基本蚁群算法的缺点，通过对剩余任务执行能力蚂蚁的选择方法、启发函数和全局信息素进行改进，由此实现MAUV全局任务的最优分配。

1 任务分配问题模型

假设MAUV的集合U包含NU个AUV，则每个AUV即为Uk∈U（k=1，2，…，NU），其属性采用四元素组表示(AUVID，POSk，Sk，Qk)，分别表示每个AUV的编号、位置、能源消耗和最大任务执行能力。任务集合T包含NT个目标任务，则每一个任务即为Tj∈T（j=1，2，…，NT），其属性采用三元素组表示(TASKID，POSj，Sj)，分别表示目标编号、目标位置和目标能耗。

任务分配后，Uk将分配到一个任务执行次序集合ψk，则Uk执行任务的目标位置依次为

MAUV的任务分配需要优先考虑以下情况：

1）MAUV的利益最大化，即对完成任务贡献最大的AUV将优先分配到任务目标。

2）尽量减少执行任务期间的能源消耗和航行距离。

3）考虑目标任务之间的均衡性。

1.1 MAUV协同作业的约束条件

1）每个任务均被分配至各个AUV，并按照要求执行，即

2）同一个任务不能分配给多个AUV，即

3）由于AUV自身的能源和续航能力有限，则Uk执行任务时的总能源消耗Sk应小于所有AUV的最大能源消耗Smax，同时Uk的续航距离Lk应小于所有AUV的最大续航总距离Lmax，即

1.2 数学模型

AUV与任务目标的距离越近，其航行距离代价越小，故应为AUV分配近距离的任务目标。对Uk而言，其航行距离代价模型为

式中，dij为第i（i=1，2，…，NT）个目标与第j个目标之间的距离，其中i≠j。

AUV的巡航过程分为直线匀速航行和转弯匀速航行，如图1所示。AUV在转弯时需要减速，故其转弯速度低于直线航行速度。假设不同的转弯角度对应不同的转弯速度，即

式中：υg为转弯速度，其中g（g=1，2，…，n）为航路节点；ag为转弯角度，其中0°＜ag≤180°。

AUV航路上的任意连续3个节点即可构成一个三角形，ag即为以中间节点为三角形顶点的内角，如图1所示。

AUV巡航时的水阻力F为

式中：C为水动力系数，其值与介质特性、AUV形状及迎流面积等有关，根据经验，一般取值为0.7；ρ为水介质的密度；υh为航行速度；s为横截面积。

忽略推进器之外的元器件发热和能耗，AUV在巡航过程中的能量损耗主要来自克服水阻力做功，即

式中：Wg为AUV的巡航能耗；t为巡航时间；υz为直线航行速度；r为AUV转弯半径。

AUV的总能耗Sk包括到达目标点过程中克服水阻力的能耗W和到达目标点j后的作业能耗Sj这2个部分，即

1.3 性能评价指标

MAUV的任务分配方案可以通过多个指标进行评估，由于各个性能指标之间可能存在冲突，故任务分配方案不存在唯一的全局最优解，需进行归一化处理。本文建立的数学模型将考虑完成任务所需的航行距离代价Lk和能源消耗代价Sk，从而得到MAUV协同任务分配的性能指标函数H

式中，ω∈（0，1），为性能指标中Lk和Sk的所占比重加权数，ω＞0.5表示任务分配时以能源消耗代价为主，ω＜0.5表示任务分配时以航行距离代价为主。

2 改进的蚁群算法

2.1 基本蚁群算法

蚁群算法是一种元启发式算法，具有问题求解快速性和全局最优特性等优点。蚁群算法的核心是状态转移概率和信息素更新规则，状态转移概率的表达式为

式中：pij(t)为t时刻从目标i转移到目标j的状态转移概率；τij(t)为t时刻在目标i和目标j之间的路径上残留的信息素值；α为信息启发式因子，反映转移过程中所积累的信息对任务转移的影响；β为期望启发因子，反映选择任务转移路径时启发信息的受重视程度；ηij为启发函数，即蚂蚁从当前目标i到目标j的代价，

所有任务完成一次求解即完成一次循环，并同时更新信息素值（从t时刻更新为t+1时刻），即

式中：δ∈（0，1），为信息素挥发系数；1-δ为信息素残留因子；Δτij(t)为本次循环的信息素增量；X为信息素强度。

鉴于蚁群算法存在易出现停滞现象和陷入局部最优解的缺点，本文将针对剩余任务执行能力蚂蚁的选择方法、启发函数、全局信息素更新方式和局部搜索方式这几点进行改进。

2.2 蚁群协调机制

对于MAUV的集合U，其任务分配计划AC将由蚂蚁子群ACk和蚂蚁组群AGv（v=1，2，…，m）分别构造的NU个任务行和m个任务列组成，其中ACk∈AC且AGv∈AC。

式中，Antk，v为第k个蚂蚁子群中的第v只蚂蚁。

AGv为来自不同蚂蚁子群ACk的NU只蚂蚁构造的任务列，即

蚁群算法的任务分配有多种状态转移方式，例如，从组群中随机选择一只蚂蚁或依次轮流进行状态转移。本文将根据组群内剩余蚂蚁的执行任务能力、剩余航程长度来选择蚂蚁，第m个组群内第k只蚂蚁的状态转移概率为

上述式中：Ek为MAUV剩余任务的综合指标；为第k只蚂蚁的剩余航程为第k只蚂蚁的剩余任务执行能力；为第k只蚂蚁当前已经分配目标所需的航行距离；为第k只蚂蚁的最大航程；为第k只蚂蚁的最大任务执行能力；为第k只蚂蚁已经消耗的任务执行能力。

由上式可知，剩余任务执行能力多、剩余航程长的蚂蚁可以优先选择新的任务目标，这种选择机制可以使MAUV的任务分配相对均衡。被选中的蚂蚁将根据信息素浓度和启发信息进行状态转移，并选择下一个任务目标。

2.3 全局信息动态更新

每一次迭代结束后，将根据式（14）和式（15）对当前最优路径进行信息素全局更新，即

式中：L1为到目前为止的最优路径长度；Lg为本次循环的最优路径长度。

每次迭代后，如果L1＞Lg，即说明本次迭代的路径更优，则式（22）应增加本次迭代所得的最优路径信息强度，保存本次迭代的最优路径；如果L1＜Lg，即说明本次迭代得到的路径没有到目前为止的最优路径好，则式（22）应削弱本次迭代所得的最优路径信息素强度。为避免路径的信息素过度集中，应采用信息素最大/最小策略，以避免算法陷入停滞状态。假设式（14）计算所得的信息素范围为，其中τmin和τmax为设定的信息素最小值和最大值。若τij(t)＜τmin，则修改τij(t)值，令τij(t)=τmin；若τij(t)＞τmax，则修改τij(t)值，令τij(t)=τmax。

2.4 局部搜索策略

为提高最优解的质量，本文将采用2-opt算法对多组蚁群算法每次迭代所得的路径进行优化。具体实现方法是：在所有蚂蚁组群实现一次循环搜索之后，对所有路径均采用2-opt算法进行局部搜索，如果局部搜索所得的新路径优于原有路径，则代替原有路径。

改进算法的具体实现步骤如下：

Step 1：算法初始化，建立蚂蚁子群ACk和蚂蚁组群AGv。

Step 2：开始一组蚂蚁搜索。

1）Antk，v∈AGv，根据状态转移规则寻找下一节点，直至所有节点已被访问。

2）采用2-opt算法对所有的蚂蚁路径进行局部搜索优化。

3）计算每条蚂蚁路径的代价。

Step 3：重复Step 2，直至完成m组蚂蚁的搜索，完成一次循环。

Step 4：记录该次循环的最优路径，进行全局信息素更新。

Step 5：判断是否达到最大循环次数或连续若干次循环的最优解无变化，则停止计算；否则重复Step 2，进行新一轮的循环搜索。

2.5 收敛性证明

设p*(o)为多组蚁群算法第o次循环搜索时首次出现最优解的概率，对于任意小的数ε（ε＞0），只要迭代次数o足够大，即成立p*(o)≥1-ε且

证明过程如下：

本文的多组蚁群算法采用了信息素限制策略，即任意路径上的信息素均被限制在τmin和τmax之间，则可行解的状态转移概率pmin＞0，且

式中：ηmax为最大启发信息；ηmin为最小启发信息；为可行解状态转移的最小概率。对于任意解，均满足

式中：为任意解的状态转移概率；为栅格节点下的转移概率，其中为满足约束的最长可行路径的栅格节点。

只要有一只蚂蚁找到最优解，即可认为算法收敛，则p*(o)的最小限值为

由式（25）可知，对于任意小的数ε，只要o足够大，即满足p*(o)≥1-ε。当o→∞时，，即多组蚁群算法实现收敛。

3 Matlab仿真实验

在MAUV海底勘察的任务区域中设置14个需要勘察的任务目标点，每个目标点的位置及到达目标点的能源消耗数据如表1所示。4个AUV的起点位置相同，即坐标为（194，328）的T1（图2），最终均将回到起点位置。每个AUV的正常航行速度为3 kn，最高航速为5 kn。AUV在正常航行状态下的最大续航时间为24 h。4个AUV的初始状态均为100%满能，要求每个AUV的总能耗不得超过自身储备能源的90%。

改进蚁群算法的相关参数值设为：α=1，β=5，ω=0.5，o=50，m=20。

表1 任务目标的位置及能源消耗Table 1 Task location and energy consumption

MAUV采用改进蚁群算法的任务分配方案如图2和表2所示，4个AUV均从起点T1出发，T2～T15为任务目标点，每个AUV完成任务后均将返回至起点位置T1。由表2可知，4个AUV完成各自任务需消耗的能源均未超过限定值。该任务分配方案可以较好地平衡每个AUV的能源消耗代价和航程距离代价。

表2 任务分配方案Table 2 Task assignment scheme

为进一步验证本文多组蚁群算法的可行性，针对能源消耗代价和航行距离代价平衡时的性能指标值，将本文算法与文献［7］的自适应蚁群算法进行对比。2种算法分别进行50次任务分配实验，取每次运行结果的平均值，性能指标均值曲线如图3所示，仿真结果如表3所示。

表3 不同蚁群算法仿真结果Table 3 Simulation results of different ant colony algorithms

由图3和表3可知，改进蚁群算法在第14次迭代时的最优解为21.13，而自适应蚁群算法在第38次迭代时的最优解为21.63。可见，改进的多组蚁群算法比自适应蚁群算法的收敛速度更快，最优解更优，迭代次数也更少。

4 结 语

以MAUV执行海底地形勘察任务为应用背景，通过对基本蚁群算法的状态转移方式、启发函数、信息素更新和局部搜索方式进行改进，提出了一种基于改进蚁群算法的MAUV最优任务分配算法，该算法具备迭代次数少、收敛速度快等优点。在一定的约束条件下，改进的多组蚁群算法可以很好地实现MAUV的最优任务分配，并在分配任务的能源消耗与航行距离之间保持良好的均衡。