无人船集群队形重构的目标任务分配

吕光颢，彭周华，王丹，窦伟滔

116026大连海事大学 船舶电气工程学院，辽宁 大连 摘 要：［目的］针对无人船编队队形重构中的目标分配问题，提出一种队形重构目标分配方法。［方法］首先，在目标点固定的情况下，通过各无人船的当前位置，生成基于距离的收益函数。其次，以拍卖理论为基础，根据无人船队形重构中目标分配的快速性要求，针对传统拍卖算法在重构分配中可能存在的无可行解问题，提出基于最大迭代次数的拍卖终止机制，分散部分计算量，从而缩短分配时间。［结果］仿真结果表明，与匈牙利法相比，所提方法针对大规模无人船集群队形重构能够快速给出目标任务分配方案。［结论］所提方法能为无人船集群队形重构中目标分配问题以及无人船自主决策研究提供一定的参考。关键词：无人船；队形重构；任务分配；拍卖算法

Target assignment in formation reconfiguration for swarms of unmanned ships

LV Guanghao，PENG Zhouhua，WANG Dan，DOU Weitao School of Marine Electrical Engineering，Dalian Maritime University，Dalian 116026，China Abstract：［Objectives］ To study the target assignment in the formation reconfiguration of unmanned ships，a target assignment method is proposed. ［Methods］ Firstly，a distance-based cost function is generated by the current positions of the unmanned ships and the fixed target points. Secondly，based on the auction theory and according to the rapidity requirement of the target assignment in the formation reconfiguration of the unmanned ship， an auction termination mechanism is proposed based on the maximum number of iterations for possible non-feasible solution in the assignment of the traditional auction algorithm， which disperses part of the simulations， thus shortening the assignment time. ［Results］Finally，the simulation results show that this proposed method can quickly give an optimized target assignment scheme for the formation reconfiguration of swarms of the unmanned ships when compared with the classical Hungarian method.［Conclusions］The proposed method herein can provide an effective reference for the target assignment in the formation reconfiguration of swarms of the unmanned ships and for the study on the autonomous decision-making of the unmanned ships. Key words：unmanned ships；formation reconfiguration；task allocation；auction algorithm

0引言

伴随着“工业4.0”概念的提出，人工智能、无人驾驶技术得到快速发展，无人船成为船舶智能

化发展的趋势。无人船因其具备自主性高、装配简单、使用灵活、成本低等优势［1］，在军事与民用领域都得到了广泛应用，例如利用无人船来执行

军事侦察、搜寻救助、水文勘察、海洋环境监测等任务。为了扩大任务执行范围，提高任务执行效率，无人船集群通常以编队的形式协同完成某项任务。在无人船集群以编队形式协同执行任务时，由于所处水域的复杂程度和任务的临时变换，无人船集群的队形重构不可避免，队形重构中，需要将构成预设队形的目标任务点分配给集群中的无人船。目标任务点的分配效率对无人船集群队

形重构以及协同任务执行效率有着重要影响。关于目标任务分配问题，Mcgrew等［2］用近似动态规划技术求解指定速度一对一作战机动问题；Sujit等［3］通过博弈论的方法，解决了双智能体的未知区域协同搜索问题；Manathara等［4］采用启发式算法，针对多异构无人机的资源分配问题设计了分配策略；Kim等［5］基于响应阈值模型，提出了区域搜索任务分配方法；Wei等［6］基于粒子群算法设计出双级任务分配方法，使得任务完成精度与可靠性得到了提高；谢宗仁、朱晓军等［7-8］分别利用突变级数法与遗传算法对舰船编队的部署作战能力进行分析，以达到资源的优化分配；Chopra等［9］针对经典匈牙利法无法处理大规模集群任务分配的问题，将匈牙利法改进成了一种并行运行

的分配方法。除以上所提任务分配方法外，近年来，一种基于拍卖机制［10-11］的资源分配方法因其计算量小且运行方式灵活，得到了各国学者的广

泛关注。虽然目前针对多无人机系统的目标任务分配问题已有相关研究，但有关无人船集群自主决策任务分配以及无人船队形重构方面的研究应用还较少。本文将主要研究无人船集群队形重构中目标任务点的分配问题，基于拍卖理论设计出一种无人船集群队形重构的目标分配方法，集群中各无人船自主决策选择兴趣目标点进行竞拍。同时，针对传统拍卖算法在队形重构的目标分配中可能存在的无可行解问题，提出基于最大迭代次数的拍卖终止机制。然后对其进行仿真，并与匈牙利法相比较。

1 无人船队形重构任务分配问题描述

1如图 所示，本节将研究由无人船集群中的n艘无人船（黄圈）到队形中的n个目标点（蓝圈）的分配问题，并使分配后的收益 z 最大，行程最短，如式（1）所示。{ ´ xij} （1） z = max1 aij  j  n式中：aij 为本次任务的收益矩阵，无人船i 距离目

标点 j 的距离越短，则收益越大；x 为任务分配ij的结果，当 xij = 1 时，目标点 j 分配给无人船 i 。任务分配完成后，无人船将与目标点形成一一对应的关系，如式（2）所示。å{ xij = 1 "i = 1 2 n j| ( i j )Î A} å{ （2） xij = 1 "j = 1 2 n i| ( i j )Î A} xij = 0 1 "(i j)ÎA式中，A为分配中所有可能配对的集合。

假设目标点 j的竞标价格为 pj ，那么无人船i竞拍得到目标点的净值为 aij - pj 。每艘无人船都

希望竞拍到能获得最大净值的目标点 ji ，即aij - pj = max ){ aij - p j} （3） j Î A ( i式中， A ( i )={ j|(i j)Î A} ，为无人船 i 可以竞价的

目标点集合。当所有无人船都满足这一条件时，可以认为价格向量 p = ( p1 p  pn) 是在互补松2弛度［12］以内的。对于一个给定的指派 S ，假若存在二元对(i j)Î S ，则说明无人船 i 或者目标点 j 被分配，反之，则称无人船 i 或目标点 j 未被分配。假若

这个指派 S 包括 n组二元对，而且每艘无人船和目标点都已一一对应分配，那么这个指派可以称为可行指派或完全指派，否则，该指派被称为部分指派。对于所有二元对 (i j)Î S ，如果目标点 j都是无人船 i 在 ε范围内的最 优指派 ，即{ aij - pj  max aij - pj}- ε ， "( i j )Î S ，则称分j Î A(i)

配 S 和价格向量 满足互补松弛（ ε—CS ）条件。

2 基于拍卖法的无人船任务分配 2.1 拍卖过程描述

通过用拍卖算法的迭代循环执行竞买过程，直至最后的分配为最优指派。在每次迭代开始前，需要一个符合 ε—CS 条件的价格向量 p 。将

满足 ε—CS 度的指派和对应的价格 pj 作为初始选择的输入，来筛选出对无人船有吸引力的目标点，通过拍卖竞价，以使二者可以始终满足 ε—CS条件。整个拍卖过程由投标阶段和分派阶段2个阶段组成。1）投标阶段。假设分配 S 中未被分配的无人船构成的集合为 I 。对任意无人船i Î I ： （1）寻找最大收益目标点 ji ，使得{ j} 4 ji = arg max aij - p （ ）

并计算其对应的最大收益值 νi ，即{ j} （5） νi = max aij - p j Î A(i)然后，寻找 ji 之外的其他目标点提供的最佳

值 ωi ，即

{ j} （6） ωi = max aij - p j Î A(i) j ¹ ji如果 ji 是唯一目标点，也就是说 A(i) 中只有一个点，那么定义 ωi =-¥ ，为便于计算，取一个远小于 νi 的值赋值给 ωi 。（2）计算无人船 i 对目标点 ji 投标 pji 与目标点 ji 收到无人船i 的标价 pij ： 7 pij = pji + νi - ωi +ε （ ） 2）分派阶段。对于每个目标点 j都能够收到若干无人船在

投标阶段的投标，记这些无人船的集合为 P( j) 。

若 P( j)非空，记下最高标价 pj ，即（8） pj = maxi pij Î P( j)如果目标点 j 被分配给无人船i ，则从指派S去掉所有与无人船 i 和目标点 j 相关的二元对，

并将新的二元对 (ij j) 加入指派 S 中，其中 ij 是P( j)中出价最高的无人船。

在拍卖过程中，目标点只有在被竞拍时价格才会抬高，每次竞拍价格至少增加 ε 。而未被竞拍的目标点的价格则一直保持在初始值。例如，若无人船i要竞拍目标点 j ，则竞标费用piji 为piji = aiji - ωi + ε = pji +ε （ 9 ） 拍卖结束后，会出现一个新分配。在这个新分配里，将之前分配过的目标点与无人船编号去除，因此，被指派过的无人船和目标点不再参与后续拍卖过程。3）无可行解的拍卖终止机制。上述拍卖算法将会在产生一个可行分配时终止，若该分配问题没有可行解，拍卖过程将无限循环。为了打破这种循环，必须为上述拍卖算法补充一个拍卖终止机制。假设存在可行解，那么拍卖的迭代次数是有限的，如式（10）所示，即存在一个最大迭代次数上限D。若不存在可行解，即由于最后不能一一分配满足互补松弛条件的目标点，拍卖将会一直进行且迭代次数会超过最大迭代次数。当拍卖次数达到最大迭代次数时，为了兼顾拍卖的运行时间，停止对此目标点进行拍卖，并将此目标点分配给下标较小的无人船。max naij - min naij D = ni max j = 1  j = 1  （ 10 ） = 1 n ε

2.2 基于拍卖法的任务分配机制设计

2如图 所示，由n艘无人船组成的系统动态网络有集成的网络通信能力，其中无人船所担任的2角色可以分为任务管理与任务执行 类。任务管理船的主要功能是将任务需求及分配发送至各执行船。任务执行船是一种能够执行任务的单元，通常是带各种负载的无人船，其主要功能是执行由任务管理船发送的各个任务请求。本文中，任务管理船将预设队形中目标点的信息并发送给集群中任务执行船，各个任务执行船根据目标点的信息自主决策，选择兴趣目标点进行出价竞拍，并将竞价发送给任务管理船，然后任务管理船通过竞价高低来分配目标任务点，最终目标任务点能够分配到各个任务执行船，执行船前往各自所分配到的目标点位置构成预设队形。

2.3 基于拍卖法的无人船任务分配流程

本文所提算法在任务执行船中运行，在拍卖过程中竞价信息都将发送并储存在任务管理船

1图 编队队形重构示意图Fig.1 Visualization of a swarm reconfiguration

图2 无人船通信网络Fig.2 Communications network of unmanned ships