0 引　言

无人艇集群作战任务分配是在满足各种约束条件下，根据当前态势为各无人艇分配有效任务序列，使得无人艇集群协作效能达到最优或次优，直接影响协同作业性能的优劣^[1]。研究新型无人艇集群任务分配方法，对提升无人艇集群协同区域探测、敌方舰队入侵拦截打击等作战任务实时性、准确性、高效性，具有深远意义。

海上博弈对抗过程中，集群任务分配受通信影响较大。艇群之间的通信由于高海况因素，缺乏稳定性，面临局部失联带来的执行任务失败风险。另外，对于无人艇集群而言，如何在分布式系统中实现对复合任务（即一个任务需要多智能体协同完成）^[2]的有效分配，涉及到复合任务分解以及各子任务之间约束关系的构建2个过程。

利用分布式任务分配方法能够解决传统任务分配依赖于稳定的网络通信、一致的态势感知，以及单点故障等问题，适用于通信不稳定，无人艇状态波动较大的任务场景。国内外学者在研究通信受限条件下的任务分配问题时，往往采用信息一致性理论消除任务冲突。Rabbath等^[3]提出分布式一致性求解方法，解决通信异步间断时的协同任务分配问题。利用状态估计的方法也能弥补通信受限带来的影响^[4-6]。Choi等^[7]提出基于共识的捆绑算法(CBBA)通过共识阶段和拍卖阶段相互迭代，解决了态势感知不一致和通信受限问题。但这些方法主要是针对全局已知任务，如何实现对复合任务的最优分配还有待深入研究。

本文旨在通过创新研发基于局部子网络的任务分配方法（BLSA）对复合任务进行分解，研究无人艇类型、任务类型之间的约束条件，生成并优化局部子网络，将异构复合任务（局部任务）分配给具有不同能力的无人艇，进一步降低通信受限对动态任务分配的影响，降低网络通信的数据量，达到优化全局任务分配的目的。

1 基于局部子网络的复合任务分配算法（BLSA） 1.1 问题描述与建模

本文主要针对异构无人艇集群在不稳定的动态海洋环境下的探测打击任务分配问题。任务过程包括对目标海域进行实时探测，一旦探测到入侵艇，立刻进行拦截打击（见图1）。

异构无人艇类型主要分为2种，探测类型无人艇USV_Patrol和目标打击类型无人艇USV_Strike。任务主要分为区域探测任务Task_Patrol、拦截打击复合任务Task_Strike。其中Task_Patrol属于单艇完成任务（USV_Patrol或USV_Strike）；Task_Strike属于复合任务，需至少2艘无人艇协同完成对目标的拦截打击，且2艘无人艇中有1艘为USV_Strike。

在此背景下，开发BLSA任务分配方法，流程图如图2所示。BLSA任务分配过程主要包含2个步骤：1）复合任务分解，算法在目标区域随机生成的探测任务进行任务分配；当无人艇集群探测过程中发现敌方艇后生成拦截打击任务并分解为打击子任务和拦截子任务。2）通过算法的共识阶段和拍卖阶段构建局部子网络，并进行任务分配。复合任务分配是一个典型的NP-hard^[8-9]问题，本文以共识算法和拍卖算法为基础，该NP-hard问题可以用下面的模型表示：

$ \max\sum _{i=1}^{I}\left(\sum _{j=1}^{J}{c}_{ij}\left({P}_{i}\right){x}_{ij}\right)。$

(1)

其中： $ J $ 为任务的集合； $ I $ 为无人艇的集合， $ {x}_{ij} $ 为1表示任务j被分配给无人艇i则为1（未分配为0）； $ {c}_{ij}\left({P}_{i}\right) $ 为无人艇i获得任务j的评分函数，该评分取决于无人艇i现有的路径列表 $ {P}_{i}({P}_{i} $ 为无人艇i中执行任务的顺序)。最优任务分配为式（1）中评分值最大时对应的方案。

1.2 复合任务分解

在作战过程中，需要将复合打击任务分解成打击和拦截子任务，故式（1）中的模型变换为：

$ \max\left(\sum _{j\in {J}_{s}}\sum _{i\in I}{c}_{ij}\left({P}_{i}\right){x}_{ij}^{s}+\sum _{j\in {J}_{c}}\sum _{i\in {I}_{s}}\sum _{k\in I}{g}_{ikj}({P}_{i},{P}_{k}){x}_{ikj}^{c}\right)。$

(2)

分配约束条件如表1所示。

表中： $ {J}_{s} $ 为Task_Patrol的集合； $ {J}_{c} $ 为Task_Strike的集合； $ {I}_{s} $ 为USV_Strike的集合； $ {I}_{p} $ 为USV_Patrol的集合； $ {x}_{ij}^{s} $ 为对于单艇任务j，如果被分配给了无人艇i则为1，否则为0； $ {x}_{ikj}^{c} $ 为对于复合任务j，如果被分配给了USV_Strikei和任意类型无人艇k则为1，否则为0； $ {g}_{ikj}({P}_{i},{P}_{k}) $ 为无人艇i，k分别获得Task_Strike j的2个子任务的评分函数。

求解式（1）的评分最大值，受制于约束1～约束5。其中 $ {L}_{t} $ 为无人艇所能执行的最大任务数量。需要注意，假设有2艘无人艇 $ i\in {I}_{s} $ 和 $ j\in I $ ， $ {g}_{ikj}({P}_{i},{P}_{k}) $ ，存在等价的方案，即

$ {g}_{ikj}\left({P}_{i},{P}_{k}\right)={c}_{ij}\left({P}_{i}\right)+{c}_{kj}\left({P}_{k}\right) 。$

(3)

式中： $ {c}_{ij}\left({P}_{i}\right) $ 和 $ {c}_{kj}\left({P}_{k}\right) $ 分别为无人艇i和无人艇k完成对应打击子任务获得的分数。为了将该分解适用于式（1）中， $ {x}_{ikj}^{c}=\{0，1\} $ 被重新定义为：

$ {x}_{ikj}^{c}={x}_{ij}^{f}{x}_{ik}^{d},\forall i\in {I}_{s},k\in I\text{，}j\in {J}_{c} 。$

(4)

式中： $ {x}_{ij}^{f} $ 为Task_Strike j的第一个子任务被分配给无人艇i； $ {x}_{ij}^{d} $ 为第二个子任务被分配给无人艇k，故式（2）更新为：

$ \begin{split}\max & \sum _{j\in {J}_{s}}\sum _{i\in I}{c}_{ij}\left({P}_{i}\right){x}_{ij}^{s}+\sum _{j\in {J}_{c}}\sum _{i\in {I}_{s}}\sum _{k\in I}({c}_{ij}{\left({P}_{i}\right)x}_{ij}^{f}+\\ & {c}_{kj}{\left({P}_{k}\right)x}_{kj}^{d})\left[{x}_{ij}^{f}{x}_{kj}^{d}\right]。\end{split}$

(5)

1.3 局部子网络

在过去研究中发现，当无人艇集群对某海域进行探测打击时，一个任务往往会分配给与其距离较近的无人艇^[10]，忽略了通信连通受限的约束，造成任务分配得不到最优解。为解决这个问题，本文提出局部子网络概念，将某一任务的分配限制在艇周围的一个局部子网络中，通过实时网络通信情况和网络传递步数，确定局部子网络的范围。

为优化局部子网络结构，在BLSA算法中设置距离阈值Distahce_threshold和网络传递步数用来限制子网络范围，当且仅当网络传递步数小于Distahce_threshold时才传递任务信息。在存储本地任务信息时，假设有n个本地任务，并为每个无人艇设计本地任务列表 $ {taskLocal}_{i} $ ，初始值为无效，即 $ {taskLocal}_{i}\left[j\right] =  0 $ ； $ {taskLocal}_{i}\left[j\right] =j $ ，则表示无人艇i中任务j为有效本地任务，且任务编号为j。当无人艇i探测的过程中发现目标艇，随即会在其本地任务中按序将2个无效本地任务分别设置为打击子任务和拦截子任务，并在每艘无人艇上设置网络传递步数列表 $ {DT}_{i} $ ， $ {DT}_{i}\left[j\right] $ 表示无人艇i对每个本地任务j的局部子网络范围约束。进而在该局部子网络中对任务j进行共识和拍卖，从而优化局部子网络并完成任务分配。

在局部自网络构建完成后，BLSA算法对该局部子网络中的任务j进行共识和拍卖阶段，从而优化局部子网络并完成任务分配，求解过程如图3所示。BLSA算法在共识阶段实现艇间数据一致化，并根据通信约束，缩小局部子网络范围。在拍卖阶段无人艇仅依据自身数据对任务出价，通过有效出价适当扩大局部子网络的范围，并更新自身数据。艇间的数据存在差异，需要共识阶段和拍卖阶段之间反复迭代直至获得稳定的一致性艇间数据。

算法1 - 共识阶段，无人艇i接收到无人艇k上的任务信息。

输入：网络通信 $\cal G $ ，无人艇信息 $\cal A $ ，任务信息 $\cal J $ ，算法参数 $\cal P $ ；

输出：无人艇信息 $\cal A $ ，任务信息 $\cal J $ 。

共识阶段（见算法1）， $ {G}_{ik}=1 $ 表示当前时刻无人艇i和无人艇k的网络是连通的。当无人艇i接收到无人艇k传来的任务信息，遍历所有已知任务j。在任务j是本地任务的条件下，如果任务j的网络传递步数小于Distahce_threshold，则扩展局部子网络的范围并更新 $ tasksLocal $ 和 $ {DT}_{i} $ 值。否则只需更新 $ {DT}_{i} $ 值。当局部子网络的相关数据更新完成后进入共识阶段，对获胜投标列表 $ {y}_{i} $ 、获胜智能体列表 $ {z}_{i} $ 达成共识。

算法2 - 拍卖阶段，无人艇i建立捆绑包B_i。

输入：无人艇信息 $\cal A $ ，获胜代表 ${\cal Z}_i $ ，获胜列表 ${\cal Y}_i $ ，捆绑包 ${\cal B}_i $ ；

输出：无人艇信息 $\cal A $ ，获胜代表 ${\cal Z}_i $ ，获胜列表 ${\cal Y}_i $ ，捆绑包 ${\cal B}_i $ 。

完成对数据的共识后进入拍卖阶段（见算法2）。首先移除共识阶段完成后出价过高的任务；其次无人艇i对所有任务j出价，获得最高出价任务j和对应的出价 $ {\rm{Max}}Value $ ；再判断出价是否有效，若 $ j > y\left[j\right] $ ，则表明有效；若 $ j $ 为本地任务，为了不遗漏最优解，进一步减小任务j的步数值，并扩展局部子网络范围；更新对应的获胜代理列表、获胜列表、捆绑包列表。需要注意，由于复合任务存在无效分配（2个子任务只有一个成功分配）的情况，需要周期检测是否存在无效分配，如存在则释放该任务重复分配。通过新方法构建出的最优局部子网络如图4所示。

2 仿真试验结果 2.1 环境参数

通过仿真和实艇测试新的任务分配方法BLSA的可行性和有效性，仿真环境设置和参数见表2。

2.2 可行性测试

假设距离阈值为2，有限通信下的网络拓扑结构如图5所示。

在上述环境参数和网络拓扑条件下，任务分配结果的时间安排如图6所示。任务规划结果如图7所示，x，y轴表示无人艇和任务的位置。同时利用BLSA方法对100组不同的网络拓扑结构做了测试，均能够得到有效任务分配结果。

BLSA方法在实际水域环境中也做了测试，由4艘实艇组成的集群成功自主完成了对探测-打击复合任务的分配，图8和图9分别展示探测和打击任务执行的过程。

2.3 通信消耗测试

在仿真环境下，对BLSA算法在有限通信条件下通信消耗情况进行测试。分别在有限通信和完全通信情况下，比较通信次数、网络传输的数据量、达到共识所需时间3个参数。对1-5不同距离阈值测试了100次并取平均值，每次测试无人艇位置、任务位置都不同，仿真结果如图10所示。从图10a和图10b可以发现，有限通信条件下通信次数和网络传输数据量明显低于完全通信，随着距离阈值的增大，局部子网络的范围随之增大，通信次数和网络传输数据量的差距逐渐减小；图10c显示当距离阈值小于3时，在有限通信下算法达到稳定共识所需时间明显小于完全通信；在有限通信下全局任务花费时间高于完全通信，故图中有限通信下时间值才会反超完全通信，说明BLSA算法可以减少对通信的消耗。

2.4 方法对比测试

由于传统CBBA算法并没有本地任务的概念，为了比较新方法和CBBA，将本地任务在CBBA算法中设为全局已知任务，计算出所有任务评分函数的总和（ $ {SUM}_{CBBA} $ ），用该值与本文所提出BLSA评分总和（ $ {SUM}_{BLSA} $ ）进行比较。每个数据取100次测试结果的平均值，结果如表3所示。评分函数总和变化的百分比很小，在2%以内。说明BLSA方法在限制了网络通信的情况下，仍然可以产生与完全通信近似等同的解决方案，同时还能提高收敛的速度，减少整个网络的通信需求。

3 结　语

本文提出一种基于局部子网络的复合任务分配(BLSA)方法。该方法对复合任务进行分解，并使用共识和拍卖的组合优化异构无人艇集群多任务分配问题，以实现满足约束的可行、无冲突解决方案。此外，BLSA方法可添加本地任务并限制数据传输，形成动态局部通信子网络，减少了不必要的通信消耗。通过仿真和实艇试验，证明了新的任务分配方法在实际环境中的可行性。未来研究需要考虑更多实际情况的约束，如在海上对抗博弈过程中己方无人艇损毁的情况、无人艇剩余油量、弹药库存数量等对任务分配的影响。