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

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

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

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）所示。

式中：aij为本次任务的收益矩阵，无人船i距离目标点j的距离越短，则收益越大；xij为任务分配的结果，当xij=1时，目标点j分配给无人船i。任务分配完成后，无人船将与目标点形成一一对应的关系，如式（2）所示。

式中，A为分配中所有可能配对的集合。

假设目标点j的竞标价格为pj，那么无人船i竞拍得到目标点的净值为aij-pj。每艘无人船都希望竞拍到能获得最大净值的目标点ji，即

对于一个给定的指派S，假若存在二元对(i，j)∈S，则说明无人船i或者目标点j被分配，反之，则称无人船i或目标点j未被分配。假若这个指派S包括n组二元对，而且每艘无人船和目标点都已一一对应分配，那么这个指派可以称为可行指派或完全指派，否则，该指派被称为部分指派。对于所有二元对(i，j)∈S，如果目标点j都是无人船i在ε范围内的最优指派，即，则称分配S和价格向量p满足互补松弛（ε—CS）条件。

2 基于拍卖法的无人船任务分配

2.1 拍卖过程描述

通过用拍卖算法的迭代循环执行竞买过程，直至最后的分配为最优指派。在每次迭代开始前，需要一个符合ε—CS条件的价格向量p。将满足ε—CS度的指派和对应的价格pj作为初始选择的输入，来筛选出对无人船有吸引力的目标点，通过拍卖竞价，以使二者可以始终满足ε—CS条件。整个拍卖过程由投标阶段和分派阶段2个阶段组成。

1）投标阶段。

假设分配S中未被分配的无人船构成的集合为I。对任意无人船i∈I：

（1）寻找最大收益目标点ji，使得

并计算其对应的最大收益值νi，即

然后，寻找ji之外的其他目标点提供的最佳值ωi，即

如果ji是唯一目标点，也就是说A(i)中只有一个点，那么定义ωi=-∞，为便于计算，取一个远小于νi的值赋值给ωi。

（2）计算无人船i对目标点ji投标pji与目标点ji收到无人船i的标价pij：

2）分派阶段。

对于每个目标点j都能够收到若干无人船在投标阶段的投标，记这些无人船的集合为P(j)。若P(j)非空，记下最高标价pj，即

如果目标点j被分配给无人船i，则从指派S去掉所有与无人船i和目标点j相关的二元对，并将新的二元对(ij，j)加入指派S中，其中ij是P(j)中出价最高的无人船。

在拍卖过程中，目标点只有在被竞拍时价格才会抬高，每次竞拍价格至少增加ε。而未被竞拍的目标点的价格则一直保持在初始值。例如，若无人船i要竞拍目标点j，则竞标费用piji为

拍卖结束后，会出现一个新分配。在这个新分配里，将之前分配过的目标点与无人船编号去除，因此，被指派过的无人船和目标点不再参与后续拍卖过程。

3）无可行解的拍卖终止机制。

上述拍卖算法将会在产生一个可行分配时终止，若该分配问题没有可行解，拍卖过程将无限循环。为了打破这种循环，必须为上述拍卖算法补充一个拍卖终止机制。假设存在可行解，那么拍卖的迭代次数是有限的，如式（10）所示，即存在一个最大迭代次数上限D。若不存在可行解，即由于最后不能一一分配满足互补松弛条件的目标点，拍卖将会一直进行且迭代次数会超过最大迭代次数。当拍卖次数达到最大迭代次数时，为了兼顾拍卖的运行时间，停止对此目标点进行拍卖，并将此目标点分配给下标较小的无人船。

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

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

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

本文所提算法在任务执行船中运行，在拍卖过程中竞价信息都将发送并储存在任务管理船中，每艘任务执行船都能接受到目标点的当前竞价信息。设置构成预设队形的目标任务点χf，任务管理船将目标点的信息发送给任务执行船，各个执行船根据目标点的信息在本地计算出自己对每个目标点的距离，从而生成收益aij，将竞标价格初始化为0，然后开始拍卖过程，算法流程图如图3所示，分以下5个步骤进行：

1）更新目前未分配的无人船的数量N，每艘无人船本地算出对所有目标点的净收益bi(j)，自主寻找最大净收益值vi并记录其对应的目标点ji，找出无人船净收益第2大值wi。此时引入一个增量ε以保证竞价始终在增加，根据式（7）进行出价并将竞价信息发送给任务管理船。

2）任务管理船开始记录对任务s竞拍的船数以及最高出价并作为当前所有执行船对任务s的下次竞标价格。

3）如若对任务s的出价数量唯一，则说明任务只有一艘执行船在竞标并且满足互补松弛条件。因此，分配任务s给出价的执行船。若对任务s的出价数量有重复，则counti加1。

4）若counti超出设置的最大迭代次数D，说明有若干艘无人船一直在重复竞标且对任务s具有相同的兴趣，出价一直相同。此时，把任务s分配给下标较小的执行船。同时，删除任务s以及对应的执行船来提高运算速度。

5）判断未分配任务的执行船的数量lj，若lj=0，说明任务已全部分配，此时跳出循环，分配结束。若lj=1，则说明还有一艘执行船和一个目标点未分配，此时，无需竞价直接分配即可，同时跳出循环分配结束。在该算法中，任务执行船不需要知道其初始位置信息，任务管理船将目标点的信息发送至各任务执行船，各任务执行船本地计算各自收益，自主决策选择兴趣目标点进行竞拍，从而分散计算量，最终完成分配任务。

在此过程中，会存在以下2个问题：

1）在无人船i变化时，其对应的最大净收益所对应的下标集合ji会随之变化，即在算法迭代过程中ji的维数是会改变的。因此，在实际编写程序时，要特别注意声明ji数组的大小。

2）为了贴合实际市场中的拍卖过程，减小分配时间，在本文算法中，每有一对无人船i与目标点j匹配完成，就把与无人船i和任务j相关的所有数据删除不再参与以后的竞拍过程。那么在步骤3）与步骤5）进行任务分配记录时，xi中第1个元素对应的并不是第1艘无人船，而是目前尚未分配的无人船中下标最小的无人船。同样的，χf中储存的第1个元素是未被分配的目标点中下标最小的目标点。

3 无人船任务分配仿真分析

本文假设某一水域存在由39艘无人船组成的集群需要进行队形重构，针对构成预设队形的39个目标任务点分配问题进行仿真。如图4所示，将39艘随机分布在水域中的无人船分派到构成DMU队形的39个目标任务点，形成DMU编队队形。

上述分配方案中的增量参数ε对分配收益有重要影响，因此，首先针对不同ε取值时的分配收益进行仿真分析。图5所示为增量参数ε对分配后收益的影响。总体上分配收益随增量参数ε的增加呈下降趋势。尤其是当增量参数ε的取值为0.02～0.03时，分配收益下降幅度大。在ε＞0.1时，分配收益的下降趋于平缓，此时，分配收益值达到最优分配收益值的93%左右。

其次，本文将选取的ε=1/39时的分配结果与匈牙利法的最优分配结果进行比较验证。分配结果如图6所示，DMU队形中39个目标任务点被分配，无人船所分配到的目标点基本在附近范围之内。2种分配方法所得分配结果相似，验证了本文所述分配方案的合理性。

最后，为了进一步对比本文所述算法与经典匈牙利法，针对不同规模的无人船集群进行队形任务点的分配。此时，ε的取值均为1/n，最大迭代次数D的设置如式（10）所示。由表1可以看出，本文分配方法和匈牙利法相对比，收益最大差值在2%左右；但随着集群规模的增大，拍卖分配求解时间较匈牙利法有所缩短，即用匈牙利法分配目标点的分配收益大于拍卖分配目标点的收益，但拍卖分配计算量分散，分配时间有所缩短。

表1 算法分配结果对比Table 1 Comparisons of the results of two assignment algorithms

4 结 语

本文基于“拍卖理论”提出了一种对无人船编队队形重构中目标任务点的分配算法，集群中无人船本地计算，自主决策选择兴趣目标点竞拍，完成预设队形中目标点的分配。与匈牙利法的比较结果验证了采用本文所提方法当补增量ε的取值在1/n附近时能快速得出相对优化的分配方案。本文中的分配方法还可以针对无人船集群多节点通信问题做进一步研究，这样不仅可以减少对处理器的依赖，也可解决无人船通信带宽不足的问题，从而提高大规模无人船集群动态队形重构的鲁棒性。