通信拒止环境下的导弹集群多目标分配与决策方法*

丘腾海 胡佳斌 蒲志强 易建强

1. 中国科学院自动化研究所，北京 100190 2. 重庆大学-辛辛那提大学联合学院，重庆 400044

0 引言

随着战场信息化和体系化能力的提升，作战模式由单一攻防作战扩展到多对多的集群协同对抗与博弈。美军率先提出多导弹协同作战的概念，通过导弹集群协同能够有效提高攻防能力[1]。其中，多目标分配和决策直接决定了作战体系的攻防性能，是协同对抗与博弈的关键技术之一[2]。

在实际战场环境中，导弹、无人机等无人集群系统面临通信拒止等复杂环境。由于缺乏基础通信设施及存在干扰，无人集群系统在任务执行过程中可能会失去与指控中心或集群间的通信，难以获得指控中心的实时控制信息[3]。因此，具备自主、智能、协同完成任务的能力是集群协同作战的关键。

目前，针对不同的作战场景国内外研究人员提出了不同的目标分配方法，按照架构主要分为集中式和分布式[4]。集中式架构比较典型方法是将目标分配问题转换为数学规划问题，进而利用枚举法、分支定界法或整数规划来求解[5-7]。然而，这类方法随着个体数量的增加，寻优空间会急剧上升，计算耗时呈指数级增长。另外，智能优化方法由于其具有的灵活性和自适应性等特点，在复杂目标分配和决策中具有较大优势，如粒子群算法(PSO)通过单个粒子运动和整体最优位置记忆和学习[8]，在搜索空间中朝最优方向运动，与遗传算法相比[9]，具有更高的计算效率，但容易陷入局部最优，全局搜索能力较弱[10]。此外，具有自学习能力的强化学习方法通过构建仿真环境训练得到最优分配解，但训练难度较大，耗时较长，很难用于高动态复杂环境战场场景下的目标分配[11-12]。复杂的拒止作战环境对决策的实时性和最优性提出较高的需求，集中式分配方法普遍存在计算效率、自主性和多次决策性等不足。相比于集中式架构，分布式架构结构灵活，可扩展性和鲁棒性强，能够用于多节点动态变化的环境[13]。分布式方法主要有组合拍卖、合同网协议等市场算法和完全分布式的智能算法。合同网协议将参与方分为发布者和竞标者，通过招标、投标、中标和确认等步骤完成整个目标竞拍分配。经典的拍卖算法包括一致性包算法(Consensus Based Bundle Algorithm，CBBA)，遵循价高者得的原则，将目标分配给出价最高的竞拍者[14]。但市场算法更多针对一个导弹对一个目标的分配优化，无法处理多个导弹同时打击一个目标的分配问题[15]。然而，在实际作战环境中，受复杂环境、作战意图和目标防御能力等影响，导弹打击目标时存在突防成功率的问题，为保证打击任务成功率，需要考虑多个导弹打击一个目标的优化分配方案。而且，通信拒止环境中的通信拓扑网络结构存在动态复杂不确定性，现有方法无法有效解决实时在线的多个导弹打击一个目标的分配和决策问题。

因此，本文针对通信拒止环境中多导弹多目标的集群对抗目标分配与决策问题开展研究，通过构建导弹集群与目标的攻防性能指标，提出扩展的一致性拍卖 (Advanced Consensus Based Auction Algorithm, ACBAA)目标分配模型，引入考虑通信拒止环境中的先验知识，设计集群行为规则模型，计算多个导弹打击多个目标的分配方案和导弹集群的运动方案，通过仿真实验验证了所设计算法和模型的有效性。本文贡献主要有两点： 1)针对通信拒止环境下的集群对抗多目标分配问题，提出了ACBAA多导弹对一个目标的分配算法； 2)建立了通信拒止环境下的集群运动决策模型。

1 基于ACBAA算法的目标分配方法

在通信拒止环境下，导弹与地面指挥站基本无法通信，导弹之间无法实时传输大量感知、控制等数据，仅能以较低频率广播少量观测信息。然而，广播通信不可靠，通常以能正常通信的导弹个数反映环境的通信拒止程度。70%以上的导弹之间无法正常通信称为强拒止，40%～70%的导弹之间无法正常通信称为中拒止，40%以下的导弹之间无法正常通信称为低拒止。在不同程度拒止环境下，每一时刻能够正常通信的导弹个数不同，且一旦建立通信连接，通信拓扑图可保持Δt时刻，之后将重新建立新的通信拓扑。CBAA算法主要考虑一对一的目标分配， 在多导弹共同选择同一目标的场景时具有局限性。本文提出了ACBAA算法，旨在解决通信拒止环境下的导弹多目标分配问题。

1.1 攻防性能指标

本文以拒止环境下多个导弹协同打击目标为背景，基于文献[12]构建的性能指标，对导弹攻击性能进行评估，包括由弹目相对角度指标、相对距离指标和相对速度指标组成的攻击性能指标，以及考虑突防概率的毁伤性能指标等。导弹发射前，在竞拍阶段考虑目标收益值和自身消耗的关系，当分配的目标收益值小于自身价值损耗，则可以终止目标选择。而在导弹发射过程中，由于其不可取消的特点，其自身消耗已成为固定成本。本文将攻击性能指标和毁伤性能指标相结合，作为综合效费性能指标，对目标分配方案进行评估。综合效费性能指标如下：

(1)

1.2 关键算法要素

在ACBAA算法中，首先明确定义导弹i目标分配信息的关键要素：

1)时间戳列表si

时间戳列表si≜{si1,…,sij,…,siNM}，是目标分配冲突消解阶段的重要指标，用于记录导弹i获得其他邻居导弹分配信息的更新时刻，表征导弹从其他导弹获得信息的新旧程度。式中sij表示导弹i获取到导弹j最新信息的时刻，通过有限范围的通信传输共享。对每个导弹来说，导弹自身最新消息的更新时间大于等于其他导弹得知该导弹最新消息的时间，即：

sii≥sji,j∈∀

(2)

2)获胜导弹列表Zi

获胜导弹列表Zi≜{Zi1,Zi2,…,ZiNM}，用于记录邻居导弹投标的目标编号，式中Zij=k表示导弹i获取到的导弹j在第sij时刻投标的目标编号是k。当导弹i获知到导弹j没有投标目标时，Zij=100。

3)获胜投标列表Yi

获胜投标列表Yi≜{Yi1,Yi2,…,YiNT}，用于记录导弹i视角下各目标的投标对象导弹编号，列表中的值与列表Zi中的值一一对应，即Yik=j表示在导弹i视角下目标k的投标对象导弹编号为j，且与时间戳列表si一致。当导弹i获知到目标k没有投标目标时，Yik=100。

4)分配列表xi

分配列表xi≜{xi1,xi2,…,xiNT}，用于记录导弹i到目标的投标策略，当xik=1时表示导弹i对目标k进行投标，当xik=0时表示导弹i不对目标k进行投标。

5)优势度列表Si

优势度列表Si≜{Si1,Si2,…,SiNT}是基于攻击性能指标构建的，用于记录导弹i对各目标的优势，Sik为导弹i对目标k的量化攻击优势度。

6)总收益列表Ci

总收益列表Ci≜{Ci1,…,Cik,…,CiNT}用于记录导弹i对目标的综合收益，包括攻击性能和毁伤性能，其中Cik表示导弹i对目标k的收益，其值为攻击性能与毁伤性能加权求和，即

(3)

1.3 算法模型求解

ACBAA算法主要分为2个阶段: 一致性阶段和拍卖阶段，拍卖阶段依赖于一致性阶段提供的其他导弹的最新消息进行投标。在一致性阶段，导弹通过通信拓扑网络传递竞标信息，并根据一致性法则，消除目标分配冲突。在拍卖阶段，导弹判断自身是否已分配目标，若未分配，则按照一定规则进行竞标，为自身分配目标。

下面以某一轮竞拍中，第i枚导弹的第t次迭代为例，详细介绍ACBAA算法中的一致性阶段和拍卖阶段。

1)一致性阶段

导弹i通过时间戳列表si来确定接收到的其他导弹的最新信息。每当导弹i与导弹l建立通信连接，除获取导弹l自身的信息外，还可通过导弹l更新导弹k的最新信息, 对导弹i的时间戳列表和其他信息进行替换。若导弹l关于导弹k的时间戳大于导弹i关于导弹k的时间戳，说明导弹l获取的导弹k的信息新鲜度更高，则进行如下更新：

(4)

(5)

导弹i对可通信范围内的所有导弹完成信息交互，对自身时间戳列表si、获胜导弹列表Zi、自身获胜投标值列表Yi进行更新。

假设导弹i当前的自身竞选目标为m，即Zii=m。如果自身竞选目标的竞标对象导弹没有发生改变，即Yim(t-1)=Yim(t)，则导弹i的竞选目标不发生改变。反之，若Yim(t-1)≠Yim(t)，则导弹i退出当前竞选目标，即：

xim(t)=0,sii(t)=当前时刻,Zii(t)=100

2)拍卖阶段

(6)

(7)

式中，Pik为不考虑其他导弹对目标k的打击时，导弹i对目标k的命中概率，PYik[j]表示导弹i获取的目标k的竞选导弹j的命中概率。为避免竞选冲突，该过程仅选用综合收益大于导弹i的导弹，即采用所有满足Cjk>Cik,j∈Yik的导弹j对于目标k的命中概率。

于是，导弹i从中选择竞争收益最大的目标k*：

(8)

(9)

xik*(t)=1,sii(t)=当前时刻,Zii(t)=k*

(10)

上述一致性和拍卖过程不断迭代，直到所有导弹的获胜导弹列表均不再发生变化，视为本轮竞拍结束，得到本轮目标分配方案及相应的总收益。ACBAA算法的流程如图1所示。

图1 ACBAA算法流程图

此外，针对不同通信拒止等级条件下导弹集群的动态通信拓扑交互特征，为增强基于ACBAA的分配能力，设计通信拒止环境下的导弹集群协同交互规则：

1)在导弹感知范围和通信范围内，导弹可更新其他导弹对于目标的收益；

2)若导弹j在导弹i的感知范围，但不在通信连通范围内，则假定导弹j的分配结果与上一轮相同，对于各目标的收益则采用最新的数据；

3)若导弹j不在导弹i的感知范围和通信连通范围内，则导弹j在本轮目标分配过程中，导弹j对于各目标的收益和分配的目标与上一轮相同。

2 基于SACO的集群运动决策方法

根据目标分配方案，导弹朝各自所分配的目标运动，本文借鉴自然界鸟群、鱼群等群居性生物的集群协同机动方法，在有限感知和机动能力条件下，基于经典生物集群行为规则“避撞-结队-聚集”(Separation Alignment Cohesion，SAC)[16]，引入导弹的攻击行为(Offense)，建立导弹运动行为规则SACO，以及通信拒止环境下的导弹集群协同交互规则，使导弹集群涌现出宏观的作战行为。

1)避撞(Separation)

(11)

2)结队(Alignment)

(12)

3)聚集(Cohesion)

(13)

式中，ga(dij)为引力函数。

4)攻击(Offense)

(14)

式中，κo>0为攻击导航力控制增益，xb为所分配目标的位置。

根据所设计的SACO行为规则，计算单个导弹运动决策控制量如下：

(15)

3 仿真校验

为验证本文所提方法的有效性，分别设计了针对基于ACBAA目标分配和SACO集群运动决策的实验，在配置酷睿i7-8750H@2.20GHz CPU和 Python3.8的计算机上进行仿真验证。

3.1 基于ACBAA算法的目标分配仿真

假定导弹数对目标数以15对10为例，验证ACBAA算法的有效性。仿真实验中导弹和目标的初始态势如表1和表2所示。其中，X、Y、Z分别为地面坐标下的三维坐标，单位为km，V为导弹飞行速度，单位m/s；γ为导弹速度倾斜角，为导弹速度方向与水平面的夹角(向上为正，向下为负)，γ∈[-π/2,π/2]，单位rad；ψ为导弹速度方位角，为飞机速度矢量在水平投影与正北的夹角，ψ∈[-π,π]，单位是rad。考虑到导弹实际性能的限制，V的范围为Ma6～10，过载的范围为[-10, 10]。

表1 导弹初始态势表

表2 目标初始态势表

在综合攻击优势度评估中，距离优势模型中的R0=30km，过载优势模型中的n0=8，各项的加权系数分别为：kθ=0.2,kσ=0.2,kr=0.2,kn=0.4。

在目标威胁建模中，设置式中的Vt0=10m/s，加权系数为kΓ=0.6,kv=0.4。导弹探测感知范围为100km，通信距离为200km。

根据所得到的优势度拒止，在无通信拒止环境下，基于CBAA算法和ACBAA算法得到目标分配方案如图2和图3所示，可以看出基于CBAA算法的目标结果会出现部分导弹未分配目标的情况，分配收益为10.51，这是由于CBAA算法本身是一对一的目标分配方式。而采用本文所设计的ACBAA算法，可以实现多目标分配的结果，分配收益为12.18，提高了最终的分配收益。

图2 CBAA算法无拒止环境下目标分配

图3 ACBAA算法无拒止环境下目标分配

导弹间的通信连通强度可利用通信拓扑图G的拉普拉斯矩阵第二小特征值λ2表示[17-18]，当该值越大，拓扑图的连通强度越大，当该值为0时表示该图不连通。根据该值可以得到在不同通信拒止情况下，导弹连通情况。图4为在不同拒止程度环境下，每个拒止等级条件下重复100次不同连通情况的平均连通值，由该图可知，当拒止程度达到85%时，出现导弹间通信完全不连通的情况。

图4 不同通信拒止程度下导弹间的连通情况

为进一步说明算法的有效性，本文基于CBAA算法和ACBAA算法在不同通信拒止程度下分配所花费时间和平均收益如图5所示。图5(a)表明，ACBAA算法进行目标分配所需时间普遍小于CBAA算法。图5(b)表明，在中低通信拒止环境下，ACBAA算法的目标分配结果平均收益多于CBAA算法的目标分配结果平均收益，这验证了ACBAA算法的有效性。在90%以上的导弹无法通信的强通信拒止环境下，导弹间的协同很难完成，CBAA和ACBAA算法在竞拍时都会倾向选择各自最大收益的目标，缺乏一致性消除冲突的阶段，因此最终目标分配的结果也会倾向一致，分配收益几乎没有差别。

图5 不同拒止程度下目标分配的平均运算时间和收益

此外，在不同通信拒止程度下进行蒙特卡罗仿真实验，在同样参数配置条件下，基于ACBAA算法连续仿真100次实验，目标分配收益分布如图6所示。由图6可以看出，无拒止环境(0%)和弱拒止环境下(≤40%)，由于各导弹间的通信连通情况较好，拒止程度对ACBAA算法的影响较小，均能获得比较高的分配收益；在强拒止环境下(≥70%)，ACBAA算法结果受到的影响较大，得到的目标分配收益比较小；在完全拒止条件下(100%)，分配收益结果为9.37，相较于无拒止环境分配结果，其收益衰减不到30%，证明ACBAA算法在拒止环境下运行的有效性。

图6 不同拒止等级环境下目标分配收益

3.2 基于SACO规则的集群运动仿真实验

集群运动模型中的系统参数设置为斥力范围lr=50，引力范围la=50，斥力Cr= 100，引力Ca= 100，速度协同力控制增益κv=0.4，攻击导航力控制增益κo=80，阻尼ξ=0.000035，最大加速度amax=10g，感知范围为100km。仿真实验时间间隔为2s，总循环次数2000。图7展示了在不同拒止环境下导弹的运行轨迹图，验证了ACBAA算法在不同拒止环境基于SACO规则的集群运动的可行性。

图7 不同拒止程度下导弹的运动轨迹

图8展示了在不同拒止环境下，导弹从起始点到目标的分配收益变化图。由图可以看出在弱拒止环境和无拒止环境下，先验知识对基于SACO规则的集群运动收益没有产生明显的影响，但在强拒止环境下，先验知识和感知范围可以对集群运动过程的收益产生显著的影响，使收益更加稳定。

图8 在不同拒止环境下的导弹的收益变化

4 结论

针对通信拒止复杂环境下的导弹集群多目标分配问题，提出一种分布式的ACBAA多目标分配和决策方法。通过一致性和拍卖阶段，优化目标分配方案，并建立通信拒止环境下的通信先验知识和集群行为规则模型，支持不同通信拒止等级环境下的导弹集群运动。仿真结果表明，本文设计的方法能够实现不同通信拒止等级条件下的目标分配决策，具有较好的优化性能，其计算效率相对于其他方法具有更明显的优势。