Chinese Journal of Ship Research
基于改进蚁群算法的多自主式水下机器人任务分配
刘瑞轩，张永林
212003江苏科技大学 电子信息学院，江苏 镇江 ：［目的］以多自主式水下机器人（MAUV）执行海底地形勘察任务为背景，提出一种基于改进蚁群算法摘 要MAUV的 最优任务分配算法。［方法］首先，建立任务分配问题模型；然后，针对基本蚁群算法进行改进。改进的蚁群由多个子群组成，通过对任务执行能力蚂蚁的选择方法、启发函数和全局信息素更新方式进行改进，以2-opt此提高算法的自适应能力和全局搜索能力，并在局部搜索中通过 算法进一步加快最优解的收敛速度。［结果］Matlab MAUV仿真结果表明，改进的蚁群算法可以有效提高 的任务分配效率，从而快速地平衡航行距离和MAUV能耗代价。［结论］研究成果可为 海底地形勘察任务分配提供参考。关键词：蚁群算法；任务分配；多自主式水下机器人
Task allocation of multiple autonomous underwater vehicles based on improved ant colony algorithm
LIU Ruixuan，ZHANG Yonglin School of Electrical and Information，Jiangsu University of Science and Technology，Zhenjiang 212003，China
Abstract：［Objectives］With the submarine topographic survey mission of the Multiple Autonomous Underwater Vehicles （MAUV） as the background， the optimal task allocation method of MAUV is proposed on the basis of an improved ant colony algorithm.［Methods］The task allocation model is first established and the basic ant colony algorithm subsequently improved. The improved ant colony consists of multiple groups. In order to enhance the adaptive and global search ability of the algorithm，the ant selection method of the remaining task execution capability，new heuristic function and updated global pheromone method are improved. In local searches，the convergence rate of the optimal solution is further accelerated by the 2-opt algorithm.［Results］The Matlab simulation results show that the improved ant colony algorithm can effectively improve the task allocation efficiency of MAUV while also providing a good balance between the distance of the voyage and the cost of the consumption.［Conclusions］This article can provide references for submarine topographic survey mission assignment in real environments. Key words：ant colony optimization；task allocation；Multiple Autonomous Underwater Vehicles（MAUV）
0引言
人（AUV），即自主式水下机器 在与母船之间 没有物理连接且无人驾驶的情况下，依靠自身携AUV带的动力自主完成复杂任务的机器人。 的应用范围非常广，如海底考察、海底管线铺设和水
下设备维修等民用领域［1-2］，以及海底排雷、侦察AUV和救生等军用领域。对单个 而言，其功能和容量均非常有限，难以满足大规模的任务需求。AUV因此，多个 系统的概念应运而生，即通过多AUV个 相互协调共同完成复杂的水下作业任AUV务。这不仅可以弥补单个 的不足，也可以提高综合作业效率。
目前，多机器人的任务分配方法主要包括基于行为的分配方法［3］、市场拍卖算法［4-5］和群体智能算法［6］。其中，基于行为的分配方法的实时性和稳定性较好，但只能求取局部最优解；市场拍卖
算法的实时性差且系统配置要求较高，但可以求取全局最优解；群体智能算法分为粒子群算法、鱼群算法和蚁群算法，该算法的鲁棒性好且计算效率较高。近年来，机器人自主任务分配方面的研
究取得了较大进展，但鲜有多自主式水下机器人（MAUV）方面的研究［7］。蚁群算法是一种模拟蚂蚁群体智能行为的仿
生优化算法，该算法利用生物信息作为蚂蚁后续
行为选择的依据，并通过蚂蚁协同作业来完成寻优过程［8］。蚁群算法多用于路径规划［9-10］及组合MAUV优化［11］等研究领域，而将蚁群算法用于 任务分配方面的研究则较少，因为基本蚁群算法存在搜索时间较长和容易陷入局部最优解的缺点［12］。MAUV本文将以 执行海底地形勘察任务为应用背景，针对基本蚁群算法的缺点，通过对剩余任务
执行能力蚂蚁的选择方法、启发函数和全局信MAUV息素进行改进，由此实现 全局任务的最优分配。
1 任务分配问题模型
MAUV AUV，则每假设 的集合U 包含 NU 个AUV ∈ U（k=1，2，…，NU个 即为Uk ），其属性采用四元素组表示 (AUVID POSk Sk Qk ) ，分别表AUV示每个 的编号、位置、能源消耗和最大任务执行能力。任务集合T包含 NT 个目标任务，则每∈T（j=1，2，…，一个任务即为Tj NT ），其属性采用三元素组表示 (TASKID POSj Sj ) ，分别表示目标编号、目标位置和目标能耗。
任务分配后，Uk 将分配到一个任务执行次序集合 ψk ，则 Uk 执行任务的目标位置依次为={( ) ( ( ) ( )} ψk xU yk0 U xT yk1) T xT ykj T xU yk0 U k0 k1 kj k0 （1） 式中：(xU yk0) U为Uk 的起始位置；(xT ykj ) 为Uk 的T k0 kj某个目标位置。MAUV的任务分配需要优先考虑以下情况： 1）MAUV的利益最大化，即对完成任务贡献AUV最大的 将优先分配到任务目标。2 ）尽量减少执行任务期间的能源消耗和航行距离。3）考虑目标任务之间的均衡性。
1.1 MAUV协同作业的约束条件
1）每个任务均被分配至各个AUV，并按照要求执行，即
NU U 1ψk =T （2） k = 2）同一个任务不能分配给多个AUV，即=Ø （3） ψk ψk + 1 3）由于AUV自身的能源和续航能力有限，则AUV Uk 执行任务时的总能源消耗 Sk 应小于所有的最大能源消耗 S ，同时 Uk 的续航距离 Lk 应max AUV小于所有 的最大续航总距离 L ，即max
1.2 数学模型
AUV与任务目标的距离越近，其航行距离代AUV价越小，故应为 分配近距离的任务目标。对Uk 而言，其航行距离代价模型为NT å 6 Lk = dij （ ） i j =1 i=1，2，…，式中，dij 为第（i NT ）个目标与第j个目标之间的距离，其中i ¹ j 。AUV的巡航过程分为直线匀速航行和转弯1所示。AUV匀速航行，如图 在转弯时需要减速，故其转弯速度低于直线航行速度。假设不同的转弯角度对应不同的转弯速度，即7 υg = 0.01ag + 0.7 （ ） g（g=1，2，…，n）为航式中：υg 为转弯速度，其中路节点；ag 为转弯角度，其中0 °< ag 180°。AUV 3航路上的任意连续 个节点即可构成一个三角形，ag 即为以中间节点为三角形顶点的内1角，如图 所示。AUV巡航时的水阻力 F 为（8） F = Cρυ h2 s/2为水动力系数，其值与介质特性、AUV式中：C 形状及迎流面积等有关，根据经验，一般取值为
0.7；ρ 为水介质的密度；υ 为航行速度；s为横截h面积。忽略推进器之外的元器件发热和能耗，AUV在巡航过程中的能量损耗主要来自克服水阻力做
功，即
2 2 Cρυ sLk Cρυ s 360 - ag 9 Wg = Fυ t= + ( )2πr（ ） z g h 2 2 360 AUV式中：Wg 为 的巡航能耗；t为巡航时间；υ 为z AUV直线航行速度；r为 转弯半径。AUV的总能耗 Sk 包括到达目标点过程中克服水阻力的能耗W和到达目标点j后的作业能耗2 Sj 这 个部分，即n
10 Sk = W + Sj = åWg + Sj （ ） g =1
1.3 性能评价指标
MAUV的任务分配方案可以通过多个指标进行评估，由于各个性能指标之间可能存在冲突，故
任务分配方案不存在唯一的全局最优解，需进行归一化处理。本文建立的数学模型将考虑完成任
务所需的航行距离代价 Lk 和能源消耗代价 Sk ， MAUV从而得到 协同任务分配的性能指标函数 H NU å 11 min H = ωSk + (1 - ω)L （ ） k k =1 ∈（0，1），为式中，ω 性能指标中 Lk 和 Sk 的所占比重加权数，ω > 0.5表示任务分配时以能源消耗代价为主，ω < 0.5表示任务分配时以航行距离代
价为主。
2 改进的蚁群算法 2.1 基本蚁群算法
蚁群算法是一种元启发式算法，具有问题求解快速性和全局最优特性等优点。蚁群算法的核心是状态转移概率和信息素更新规则，状态转移概率的表达式为
[τij (t)]α (ηij )β g Î Allowed NT 12 pij (t)= å [τij (t)] α (ηij) β （ ） i j =1 0 Otherwise式中：pij (t)为 t时刻从目标i转移到目标j的状态转移概率； τij (t)为 t时刻在目标i和目标j之间的路径上残留的信息素值；α为信息启发式因子，反
映转移过程中所积累的信息对任务转移的影响； β 为期望启发因子，反映选择任务转移路径时启
发信息的受重视程度；ηij 为启发函数，即蚂蚁从当前目标i到目标j的代价， 1 （13） ηij = dij·Sj所有任务完成一次求解即完成一次循环，并t+1同时更新信息素值（从t时刻更新为 时刻），即（14） τij (t + 1) = (1 - δ)τij (t) +D τij (t) X 15 Dτij (t)= （ ） dij ∈（0，1 1-式中： δ ），为信息素挥发系数； δ 为信息素残留因子；Dτij (t)为本次循环的信息素增量； X为信息素强度。鉴于蚁群算法存在易出现停滞现象和陷入局
部最优解的缺点，本文将针对剩余任务执行能力蚂蚁的选择方法、启发函数、全局信息素更新方式和局部搜索方式这几点进行改进。
2.2 蚁群协调机制
MAUV对于 的集合U ，其任务分配计划 AC =1，将由蚂蚁子群 AC 和蚂蚁组群 AG （ v k v 2，…，m）分别构造的 NU 个任务行和m个任务列∈ ∈组成，其中 AC AC 且 AG AC 。k v ={Antk v}（16） AC 1 Antk 2 Antk 3 ... Antk k式中，Antk 为第k个蚂蚁子群中的第v 只蚂蚁。v AG 为来自不同蚂蚁子群 AC 的 NU 只蚂蚁v k构造的任务列，即={Ant1 v}T ΑG v Ant2 v Ant3 AntNU （17） v v蚁群算法的任务分配有多种状态转移方式，
例如，从组群中随机选择一只蚂蚁或依次轮流进
行状态转移。本文将根据组群内剩余蚂蚁的执行任务能力、剩余航程长度来选择蚂蚁，第m个组群内第k只蚂蚁的状态转移概率 pm tran 为k E （18） p tran = k m k NU å Ek k =1
（19） Ek = Lk ´ Qk res res （20） res max now Lk = Lk - Lk （21） res max now Qk = Qk - Qk MAUV res上述式中：Ek为 剩余任务的综合指标；L k为第k只蚂蚁的剩余航程；Qk 为第k只蚂蚁的剩res now余任务执行能力；Lk 为第k只蚂蚁当前已经分max配目标所需的航行距离；Lk 为第k只蚂蚁的最max大航程；Qk 为第k只蚂蚁的最大任务执行能力； now Qk为第k只蚂蚁已经消耗的任务执行能力。由上式可知，剩余任务执行能力多、剩余航程长的蚂蚁可以优先选择新的任务目标，这种选择MAUV机制可以使 的任务分配相对均衡。被选中的蚂蚁将根据信息素浓度和启发信息进行状态转移，并选择下一个任务目标。
2.3 全局信息动态更新
式（14）和式（15）每一次迭代结束后，将根据对当前最优路径进行信息素全局更新，即L1 - Lg （22） Dτij = Lg式中：L1为到目前为止的最优路径长度；Lg 为本次循环的最优路径长度。每次迭代后，如果 L1 > Lg ，即说明本次迭代的路径更优，则式（22）应增加本次迭代所得的最优路径信息强度，保存本次迭代的最优路径；如果L1 < Lg ，即说明本次迭代得到的路径没有到目前为止的最优路径好，则式（22）应削弱本次迭代所得的最优路径信息素强度。为避免路径的信息素过度集中，应采用信息素最大/最小策略，以避免算法陷入停滞状态。假设式（14）计算所得的信息[ max] min素范围为 τ τ ，其中 τ 和 τ 为设定的信min max息素最小值和最大值。若 τij (t) < τ ，则修改 τij (t) min值，令 τij (t) = τ ；若 τij (t) > τ ，则修改 τij (t) 值，令min max τij (t) =τ。max
2.4 局部搜索策略
2-opt为提高最优解的质量，本文将采用 算法对多组蚁群算法每次迭代所得的路径进行优化。具体实现方法是：在所有蚂蚁组群实现一次循环2-opt搜索之后，对所有路径均采用 算法进行局部搜索，如果局部搜索所得的新路径优于原有路径，则代替原有路径。改进算法的具体实现步骤如下： Step 1：算法初始化，建立蚂蚁子群 AC 和蚂k蚁组群 AGv 。 Step 2：开始一组蚂蚁搜索。1） Antk Î ，根据状态转移规则寻找下v v一节点，直至所有节点已被访问。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 - ε 且 lim p*(o) = 1。o ®¥证明过程如下：本文的多组蚁群算法采用了信息素限制策略，即任意路径上的信息素均被限制在 τ 和 τ min max之间，则可行解的状态转移概率 p > 0 ，且min ββ α τ η 23 p pmin = > 0（ ） min min min α α β (NT - 1)τ η + τ η max max min min式中： η 为最大启发信息； η 为最小启发信max min息；p 为可行解状态转移的最小概率。min对于任意解，均满足NT （24） p p >0 min N式中： p 为任意解的状态转移概率；p为栅格min节点 NT ′ 下的转移概率，其中 NT ′为满足约束的最长可行路径的栅格节点。只要有一只蚂蚁找到最优解，即可认为算法收敛，则 p*(o) 的最小限值为（25） p*(o) = 1 - (1 - p)o由式（25）可知，对于任意小的数 ε ，只要o足够 大 ，即 满 足 p*(o) 1 - ε 。当 o ®¥ 时， lim p* (o) = 1 ，即多组蚁群算法实现收敛。o ®¥
3 Matlab仿真实验
MAUV 14在 海底勘察的任务区域中设置 个需要勘察的任务目标点，每个目标点的位置及到1 4 AUV达目标点的能源消耗数据如表 所示。 个的起点位置相同，即坐标为（194 328）的 2 ， T （图 ）， 1
AUV最终均将回到起点位置。每个 的正常航行3kn 5kn AUV速度为 ，最高航速为 。 在正常航行24h。4 AUV状态下的最大续航时间为 个 的初始100% AUV状态均为 满能，要求每个 的总能耗不90%。得超过自身储备能源的 =1，β =5，改进蚁群算法的相关参数值设为：α =0.5，o =50，m=20。ω MAUV采用改进蚁群算法的任务分配方案如2 2所示，4 AUV图 和表 个 均从起点 T1 出发，T ～ 2 AUV T15为任务目标点，每个 完成任务后均将返回2可知，4 AUV至 起点位置 T1。由表 个 完成各自任务需消耗的能源均未超过限定值。该任务分配AUV方案可以较好地平衡每个 的能源消耗代价和航程距离代价。 为进一步验证本文多组蚁群算法的可行性，针对能源消耗代价和航行距离代价平衡时的性能 指标值，将本文算法与文献［7］的自适应蚁群算法2 50进行对比。 种算法分别进行 次任务分配实验，取每次运行结果的平均值，性能指标均值曲线3 3如图 所示，仿真结果如表 所示。 3 3 14由图 和表 可知，改进蚁群算法在第 次21.13，而自适应蚁群算法在迭代时的最优解为38 21.63。可见，改进的第 次迭代时的最优解为多组蚁群算法比自适应蚁群算法的收敛速度更快，最优解更优，迭代次数也更少。
4结语
MAUV以 执行海底地形勘察任务为应用背景，通过对基本蚁群算法的状态转移方式、启发函数、信息素更新和局部搜索方式进行改进，提出了MAUV一种基于改进蚁群算法的 最优任务分配算法，该算法具备迭代次数少、收敛速度快等优点。在一定的约束条件下，改进的多组蚁群算法可以MAUV很好地实现 的最优任务分配，并在分配任务的能源消耗与航行距离之间保持良好的均衡。
参考文献：
124-132. ZHANG W K，WANG G X， XU G H ，et al. Develop⁃ ment of control system in abdominal operating ROV ［J］. Chinese Journal of Ship Research，2017，12（2）： 124-132（in Chinese）. ［ 3］ 柳林，季秀才，郑志强. 基于市场法及能力分类的多机器人任务分配方法［J］. 机器人，2006，28（3）： 337-343. LIU L， JI X C ，ZHENG Z Q. Multi-robot task alloca⁃ tion based on market and capability classification［J］. Robot，2006，28（3）：337-343（in Chinese）. 4］ . ［ 张嵛，刘淑华 多机器人任务分配的研究与进展［J］. 智能系统学报，2008，3（2）：115-120. ZHANG Y，LIU S H. Survey of multi-robot task alloca⁃ tion［J］. CAAI Transactions on Intelligent Systems， 2008，3（2）：115-120（in Chinese）. 5］ 齐心跃，田彦涛，杨茂，等. ［ 基于市场机制的多机器人救火任务分配策略［J］. 吉林大学学报（信息科学版），2009，27（5）：506-513. QI X Y ，TIAN Y T，YANG M，et al. Market-based multi-robot task allocation for fire-disaster response ［J］. Journal of Jilin University （Information Science Edition），2009，27（5）：506-513（in Chinese）. ［6］ WHITLEY D，HAINS D，HOWE A. A hybrid genetic algorithm for the traveling salesman problem using gen⁃ eralized partition crossover ［C］//Proceedings of the 11th International Conference on Parallel Problem Solv⁃ ing from Nature：Part I. Berlin Heidelberg：Spring⁃ er-Verlag，2011：566-575. ［7］ LIH ，YANG S X，SETO M L. Neural-network-based path planning for a multi-robot system with moving ob⁃ stacles［J］. IEEE Transactions on Systems，Man，and Cybernetics：Part C，2009，39（4）：410-419. ［8］ 梁德赛. 基于自适应蚁群算法的JSP问题仿真研究［J］. 计算机仿真，2012，29（6）：228-232，239. LIANG D S. Study on job shop scheduling problems based on new adaptive ant colony algorithm［J］. Com⁃ puter Simulation，2012，29（6）：228-232，239 （in Chinese）. ［ 9］ 张汝波，李建军，杨玉. 基于改进蚁群算法的AUV航路避障任务规划［J］.华中科技大学学报（自然科学版），2015，43（增刊1）：428-430. ZHANG R B， LI J J ，YANG Y. AUV route planning study for obstacle avoidance task based on improved ant colony algorithm［J］. Journal of Huazhong Univer⁃ sity of Science and Technology（Natural Science Edi⁃ tion），2015，43（Supp 1）：428-430（in Chinese）. 10］ 谢秉磊，李颖，刘敏. ［ 带临时补充点的融雪剂撒布J］. 2014，34车辆路径问题［ 系统工程理论实践， （6）：1593-1598. XIE B L LIY ，LIU M. Vehicle routing problem with
， temporary supplementary points for spreading deicing salt［J］. Systems Engineering-Theory and Practice， 2014，34（6）：1593-1598（in Chinese）. 11］ 冀俊忠，黄振，刘椿年. ［ 一种快速求解旅行商问题J］. 2009，46的蚁群算法［ 计算机研究与发展， （6）：968-978. JIJZ ，HUANG Z，LIU C N. A fast ant colony optimi⁃ zation algorithm for traveling salesman problems［J］. Journal of Computer Research and Development， 2009，46（6）：968-978（in Chinese）. 12］ . D］. ［ 祝永华 改进的蚁群算法及其应用研究［ 杭州：浙江工业大学，2013. ZHU Y H. Research of improved ant colony algorithm and its application［D］. Hangzhou：Zhejiang Universi⁃ ty of Technology，2013（in Chinese）.