随着现代信息与通信技术和人工智能技术的发展，具有自主能力的无人机智能体在现代战场上得到越来越广泛的应用^[1]。然而面对日趋复杂的现代战场环境，由于单个无人机所发挥的功能有限，许多作战任务需要多个无人机智能体协同完成，每个无人机智能体分别执行一系列任务^[2]。实际作战环境不断动态变化，新任务及无人机智能体受损等不确定事件的出现会使原有任务分配方案不能满足任务需求^[3]。多无人机智能体联盟动态任务分配研究逐渐成为当前热点^[4]。

针对多无人机智能体联盟动态任务分配问题，文献[5]提出了一种基于分布式拍卖机制的多无人机协同作战动态目标分配方法。文献[6]提出了一种引入指挥员人为干预的动态任务分配机制，指挥员手动操作实现任务分配结果动态调整。但这一方法耗时较长，且确保指挥员与无人机间通信稳定可靠。文献[7]基于分阶段贪心规划算法(phased greedy planning algorithm, PGPA)对异构多无人机智能体分发资源问题进行了研究，算法实时性较强。文献[8]提出了基于监督顺序拍卖机制的任务重分配方法，对战场环境中突发新任务由拍卖者随机产生拍卖顺序，各无人机顺序投标选择任务，直至所有突发均被选择为止。文献[9]以异构多无人机协同执行防空压制任务为背景，采用了分布式遗传算法解决多无人机智能体协同任务分配问题，模型中考虑了飞行器载荷类型及末端进入目标角度等约束条件。

随着地面防空武器的不断发展，多无人机智能体协同执行作战任务时间更为紧凑，“时间窗口作战”特性不断增强^[10]。同时，对于复杂作战任务，通常需要先对目标附近区域进行预先侦察，完成目标特征确认后完成对地攻击，因而任务之间存在时序约束关系且分别需要一定的执行时间^[11]。但目前上述相关研究中对任务时序约束及执行时间窗口考虑不充分，缺少对时序耦合关系及时间窗口约束下多无人机智能体联盟动态任务分配问题的研究。

一致性包算法(CBBA)具有快速收敛至无冲突分配方案的优点^[12]。本文针对任务载荷资源约束、任务耦合关系约束及执行窗口约束等条件下的异构多智能体动态联盟任务分配问题，首先基于CBBA算法，提出了一致性联盟算法；在此基础上，针对突发新任务出现的动态场景，给出了3种动态任务分配策略。最后，以多架无人侦察飞机(unmanned search aerial vehicle, USAV)和UCAV(unmanned combat aerial vehicle, UCAV)协同执行对地侦察攻击任务为任务背景，通过仿真实验验证了该算法及3种动态分配策略的可行性和算法性能。

1 多无人机智能体联盟任务分配问题描述 1.1 任务空间

本文研究任务表述如下：在预先已知战场态势感知信息的情况下，携带有不同种类载荷资源的异构无人机智能体，协同完成任务区域内具有时间窗口、耦合时序及载荷资源种类等多种约束各项作战任务。本文中载荷资源均为不可消耗类。

首先给出任务空间相关参数描述。

1) 无人机智能体集

I{1, …, N_a}代表执行作战任务的无人机智能体集合(为简洁表达, 下文中所有智能体均指无人机智能体), 其中i∈I为智能体唯一身份标识, N_a为智能体数量。智能体异构性主要表现在携带载荷资源种类及运动学性能有所不同。无人机i∈I采用四元组〈P_i, R_i, V_i, L_i〉表示, 其中P_i为智能体位置坐标, R_i为智能体i∈I携带载荷资源列表, V_i为智能体速度, L_i为智能体i执行任务数量上限。

2) 任务集

J{1, …, N_T}为战场环境中的任务集, N_T为任务数量。任务j∈J采用元素组〈P_j, , n_j^t, t_j, n_j^S, D_j, T_j〉描述, 其中P_j为任务位置坐标; 为执行该任务所需载荷资源种类列表, =ø则表示任务j对智能体携带资源无要求, 所有智能体都可投标; n_j^t为任务j所需智能体数量, n_j^t>1时表示任务j需要多架无人机智能体组成联盟协同完成; t_j={τ_j^start, τ_j^end, τ_j^last, λ_j}为执行该任务时间约束集合, 其中τ_j^start和τ_j^end分别为任务j执行最早和最晚时间节点, τ_j^last为任务持续时间, 0≤λ_j < 1为任务时间折扣因子, 用于在后续计算任务时效收益值; n_j^S为任务j包含的子任务类数, 子任务类别通过所需载荷资源种类划分

(1)

为子任务时序耦合关系矩阵, 其中d_wq表示子任务w和子任务q之间的耦合关系约束, d_wq=1表示子任务w和子任务q之间存在时序关系约束, d_wq=0表示2个子任务之间无时序约束关系; 当子任务之间存在时序关系约束时, w和q起始时间存在最小时间间隔Δt_min, 即有

(2)

式中，T_j为子任务时序间隔矩阵。

1.2 多无人机智能体联盟任务分配模型

异构多智能体联盟任务分配问题为典型混合整数线性规划问题, 即:给定任务集J{1, …, N_T}和智能体集合I{1, …, N_a}, 寻求满足智能体本体和任务执行等约束条件的最优任务分配方案, 从而使得系统效用最大。

采用文献[14]的分布式整数规划模型, 上述问题可描述为

(3)

式中：p_i为智能体i执行所分配任务的顺序；S_ij为智能体i执行任务j的收益; x_ij ∈{1, 0}为任务分配决策变量；x_ij=1表明智能体i执行任务j, 否则x_ij=0。公式(3)需满足以下假设：

1) 智能体i执行任务j的收益为智能体到达任务时间的函数;

2) 智能体i到达任务j处时间由任务执行顺序p_i唯一确定;

3) p_i由智能体i任务分配决策变量x_i唯一确定。

2 一致性联盟算法

CBBA算法在异构多智能体协同执行某项任务的场景中具有一定局限性^[13]。本节在CBBA算法基础上提出了一致性联盟算法(consensus based coalition algorithm, CBCA)。

2.1 算法关键要素

首先给出CBCA算法中有关智能体i任务分配信息的关键要素:

1) 任务路径列表p_i

任务路径列表p_i{p_i1, …, p_i|pi|}表示分配给智能体i的待执行任务列表, 列表中元素按照i计划执行顺序排列, |p_i|表示列表长度。p_i=ø表示智能体i路径列表为空。

2) 任务包b_i

任务包b_i{b_i1, …, b_i|bi|}表示分配给智能体i的任务集合, 集合中元素按任务加入包的先后顺序排列, |b_i|代表b_i列表长度, 且有|b_i|≤|p_i|。b_i=ø表示智能体i任务包为空。

3) 获胜智能体矩阵Zⁱ

Zⁱ为N_a×N_T维矩阵, 其中z_kjⁱ=1表示智能体i认为智能体k是任务j的投标获胜者; 否则z_kjⁱ=0。Zⁱ中第j列非零元素数量之和N_j^sum=z_kjⁱ代表了智能体i认为执行任务j的智能体总数。

4) 获胜投标值矩阵Yⁱ

Yⁱ存储智能体i视角下各项任务联盟成员的投标值, 矩阵中各元素与Zⁱ一一对应。当智能体i认为任务j没有获胜者时, y_ij=-∞。

5) 时间戳列表s_i

时间戳列表s_i{s_i1, …, s_iNa}记录智能体i从相邻其他智能体中获得更新信息的时刻, 其中s_ik表示智能体i从智能体k获得最新信息的时刻。s_i是冲突消除的重要指标, 表征了智能体i从相邻智能体获得信息的新旧程度。

2.2 任务包构建

CBBA算法的基础是顺序贪婪算法(sequential greedy algorithm, SGA), 即每个智能体每次以最大化自身任务收益增量为原则选择任务。设智能体i初始任务包为b_i, i选择收益边际增益最大的任务j^*∈J加入到b_i中。任务选择过程持续到任务包已满或无可选任务。智能体只对满足时间窗约束和载荷资源约束的有效任务进行投标。

智能体i沿任务路径p_i的收益为

(4)

式中:r_ij(p_i)为任务执行收益, 考虑任务动态时效性, 采用时间折扣收益来计算, 即

(5)

式中：r_j为任务j的静态收益；τ_ij(p_i)为智能体i沿路径p_i执行任务j的估计时间。

ξ_ij为智能体行程损耗代价, 即

(6)

式中：d_ij为智能体i与任务j之间的直线距离；γ为行程代价系数。

依据新任务j′加入b_i前后的收益, 可获得j′的边际增益为

(7)

式中：n表示j′在p_i中所有可能位置；|p_i|为路径列表长度；p_i⊕_n{j′}表示将j′插入到路径列表p_i中第n位, 原路径列表中第n位及其以后的元素保持原顺序不变, 依次后移。

当n_j=1时, 任务j为单智能体执行型, 投标过程与CBBA算法相同, 详细步骤见文献[13]。当n_j>1时, 任务j需要多智能体组成联盟协同完成, 此时任务j可分为两种情况:①竞标执行任务j的智能体数量已满足联盟智能体数量需求, 即N_j^sum=n_j, 此时分配执行任务j的智能体数量已满荷; ②分配执行任务j的智能体数量未满足数量需求, 即N_j^sum < n_j。

任务j分配已满荷时, 智能体将自身边际增益与当前任务最小获胜投标值作比较, 当

(8)

时, 智能体i可以投标(h_ij=1), 并将最小获胜投标值替换为自身投标值; 否则, 智能体i放弃任务j(h_ij=0)。当智能体i投标值与最小获胜投标值相同时, 选择身份标识小的智能体。

智能体不断构造自身任务包直至任务包已满或没有满足约束条件的有效任务。具体CBCA任务包构造流程如算法1所示。

Algorithm 1: Bundle construction of CBCA

Input:Winning agents matrix Zⁱ(t-1), winning bids matrix Yⁱ(t-1), task bundle b_i(t-1) and path list p_i(t-1)

Output: Zⁱ(t), Yⁱ(t), b_i(t) and p_i(t)

1:While |b_i(t-1)| < L_i do

2:    c_ij=(p_i⊕_n{j})-S_i(p_i), ∀j∈J

3:    for ∀j∈J

4:        if n_j^t>1 then

5:            if n_j^t>z_kjⁱ then

6:                h_ij=1

7:            else if c_ij>min(y_kjⁱ), ∀k∈I then

8:                h_ij=1

9:            else

10:                h_ij=0

11:              end

12:          else

13:              h_ij=I(c_ij>y_kjⁱ)

14:          end

15:      end

16:          J_i=argmax_jc_ijh_ij

17:          n_{i, Ji}=argmax_nS_i(p_i⊕_n{j})

18:          b_i(t)=b_i(t-1)⊕_end{J_i}

19:          p_i(t)=p_i(t-1)⊕_{nj, Ji}{J_i}

20:          yⁱ_{i, Ji} (t)=c_{i, Ji}

21:          zⁱ_{i, Ji} (t)=1

22:          end while

2.3 基于一致性的冲突消解

任务包构建结束后, 智能体需要与相邻智能体交换获胜智能体列表、获胜投标列表和时间戳列表等信息, 并按照一定的行动规则更新信息以获得无冲突任务分配。

具体冲突消解过程如算法2所示。

Algorithm 2: Conflict resolution of CBCA

Input: Winning agents matrix Z^k(t-1), winning bids matrix Yⁱ(t-1) and time stamp s_k(t-1) from agent k

Output: Zⁱ(t), Yⁱ(t) and s_i(t)

1:send Zⁱ(t-1), Yⁱ(t) and s_i(t-1) to its neighbor agent k

2:receive Z^k(t-1), Y^k(t-1) and s_k(t-1) from agent k

3:for ∀j∈J

4:          if n_j^t=then

5:              run consensus resolution of CBBA

6:          else

7:              for ∀m∈I where z_mjⁱ=1

8:                    if k=m and s_km>s_im then

9:                      z_mjⁱ=z_mj^k

10:                        y_mjⁱ=y_mj^k

11:                    end

12:                  end

13:                  for ∀m∈I where z_mj^k=1

14:              if m≠i and z_mjⁱ=0 and s_km>s_im then

15:                  if z_mjⁱ < n_j^t then

16:                      z_mjⁱ=z_mj^k

17:                      y_mjⁱ=y_mj^k

18:              else

19:                  if min(y_njⁱ ∀n) < y_mj^k and R_m∩R_n≠ø then

20:                      z_njⁱ=0, z_mjⁱ=z_mj^k

21:                      y_njⁱ=-∞, y_mjⁱ=y_mj^k

22:                      end

23:                  end

24:              end

25:          end

26:      end

27:          s_ik=t

28:end

3 动态联盟任务分配策略

CBCA算法适用任务信息预先已知的静态场景。当任务空间出现更有打击价值的新任务T^*时, 需设计动态重分配机制, 以快速获得重分配方案保证作战任务顺利进行。本节针对新任务出现的分布式联盟动态任务分配问题, 提出了动态任务分配策略。

3.1 无重规划动态分配策略(NR-CBCA)

无重规划分配策略(consensus based coalition algorithm with no resetting, NR-CBCA)中, 当新任务T^*出现时, 多智能体系统在原有任务分配基础上考虑将新任务插入自身任务包, 即在任务包构造中, p_i(t)=p_i(t-1), b_i(t)=b_i(t-1)。此时, 满足载荷资源需求的智能体i投标值为

(11)

式中，p_i⊕_n{T^*}表示将T^*插入到路径列表p_i中第n位。进一步, 当T^*位于p_i中第n^*位时有

(12)

进一步考虑到

(13)

则有

(14)

yiT*i可以分解为两部分, 第一部分((14)式中第一行)代表智能体i沿新任务路径p′i执行T*的收益值, 第二部分((14)式中2~3行)代表智能体执行同样的任务沿任务路径p′i与pi的收益差值。注意到执行顺序在T*之前的任务收益保持不变, 因此第二部分可简化为

(15)

由(15)式可知, 执行任务T^*的边际增益包含两部分内容, 一部分是任务T^*时效收益, 另一部分为由于插入任务T^*导致后续任务延迟执行的收益差值。尽早执行任务T^*, 可提高任务T^*时效收益; 但同时会导致列表中更多任务因为延迟执行而导致收益值降低。因此任务T^*在p′_i中的位置需综合权衡两方面因素。

NR-CBCA策略具有快速响应、算法收敛性不受新任务影响的优点。但智能体i只有在已分配任务数量少于L_i时, 才可以对新任务竞标。当突发新任务价值较高或对载荷资源要求较严时, NR-CBCA策略求解质量较差。因此释放原有任务列表, 进行重规划可保证任务T^*的分配不受之前任务分配结果的影响。

3.2 完全重规划动态分配策略(FR-CBCA)

在完全重规划策略(consensus based coalition algorithm with full resetting, FR-CBCA)中, 当发现新任务时, 符合任务资源需求的智能体清空原有任务分配结果, 重新构造任务包和路径列表, 即p_i(t)=ø, b_i(t)=ø。通过将任务包和任务路径列表重置为空, FR-CBCA策略可以有效消除原有任务分配结果对新任务分配的局限, 通过灵活重构任务包和任务路径列表, 降低T^*可能导致的边际增益损耗。

虽然FR-CBCA策略具有灵活性强、提高多智能体协作能力的优点, 但它需要一定的时间完成完整重分配。同时由于将原有任务包和任务路径列表重置为空集, 重规划可能导致多智能体系统扰动, 即系统始终处于重规划状态中, 无法获得一致无冲突的任务分配结果, 原有任务分配问题解的收敛性难以保证。

3.3 部分重规划动态分配策略(PR-CBCA)

为了更好地权衡动态任务分配时算法收敛速度与算法总收益, 提出了一种部分重规划的动态联盟任务分配策略(consensus based coalition algorithm with partial resetting, PR-CBCA)。在PR-CBCA策略中, 每个智能体在任务包构建时从自身任务包释放收益值最低的n_resetⁱ个任务, 保留其余任务不变。n_resetⁱ数值大小可以通过综合考虑新任务数量及响应速度需求来确定。当新任务频繁出现、多智能体系统需要在下一批新任务出现前实现无冲突任务分配时, 可以设定n_resetⁱ数值较小; 当新任务价值很高时, 则可以通过释放更多任务来提高智能体协作能力。

Algorithm 3: CBCA with partial resetting (PR-CBCA)

Input: A subset of agents I_reset participating in the replanning, a desired response time t_response, a communication period t_comm

Output: Zⁱ(t), Yⁱ(t), b_i(t) and p_i(t)

1: d=Diameter(I_reset)

2: n_resetⁱ=

3: y_sortⁱ=Sort(y_iⁱ)

4: J_resetⁱ={j∈J|y_ijⁱ∈y_sortⁱ [1:n_resetⁱ]}

5: for i∈I_reset do

6: for j∈J_resetⁱ do

7:                  p_i(t)=p_i(t-1)! j

8:                  b_i(t)=b_i(t-1)! j

9:                  y_ijⁱ=-∞

10:                  z_ijⁱ=0

11:    end for

12:end for

在PR-CBCA策略中, 当新任务出现时, 符合新任务载荷资源需求的智能体将收益值最低的n_resetⁱ个任务从自身任务包和路径列表中释放, 并重置相应的获胜投标值与获胜智能体矩阵元素数值。通过选择符合载荷资源、参与重规划智能体子集I_reset大小, 可以实现更为灵活的动态分配, 当多智能体系统规模较大时, 可选择较多智能体释放较少任务进行重规划; 或者选择较少数量智能体进行完全重规划。通过改变n_resetⁱ数值可以看出, NR-CBCA策略和FR-CBCA策略为PR-CBCA策略在n_resetⁱ=0和n_resetⁱ=L_i时的2个特例。

4 仿真结果及分析

以动态环境下多架USAV和UCAV执行侦察与攻击任务为例, 对CBCA算法及动态任务分配策略进行仿真验证。战场任务主要划分为3类:仅需USAV进行侦察搜索的侦察类任务、仅需UCAV进行对地攻击的攻击类任务及需由USAV先执行侦察确认随后UCAV进行攻击的察打类任务。

4.1 CBCA算法仿真结果分析

算例1中共有5架无人机对9个地面固定目标进行侦察攻击, 任务空间范围设定为5 km×5 km×2 km, 无人机和目标初始状态信息如表 1和表 2所示。侦察类任务需要2架USAV执行, 攻击类任务需要2架UCAV协同完成, 察打类任务需2架USAV和1架UCAV。察打类任务可分为侦察子任务和攻击子任务, 其对应子任务耦合关系矩阵为

相应时序间隔矩阵为

矩阵D_sa和T_sa行(/列)元素按顺序分别代表侦察子任务和攻击子任务, 其中d₁₂(d₂₁)=1表明侦察子任务与攻击子任务之间存在时序约束关系, Δt_min=10 min为UCAV执行攻击子任务前USAV完成侦察子任务所需的最短时间。需要2架无人作战/侦察飞机协同完成的攻击/侦察任务只包含一类子任务, 此时子任务关系矩阵为D_s/a=ø, 对应时序间隔矩阵为T_s/a=ø。

算例1中CBCA算法分配结果和各UAV的任务路径列表分别如表 3和图 1所示。对察打类任务Task1和Task5, 首先UAV1和UAV3进行侦察确认, 侦察子任务结束后UAV5执行攻击任务, 满足子任务耦合时序关系。算法总收益值为1 805.01。仿真结果表明CBCA算法可解决复杂约束条件下异构多智能体联盟任务分配问题。

4.2 算法最优性评估

将CBCA算法与量子蚁群算法^[15]进行比较, 分别记录算法平均总收益值, 以实现对CBCA算法最优性评估。算例2中5架无人机对9个目标进行攻击, 随机产生无人机和目标的初始位置, 任务空间范围设定为5 km×5 km×2 km, 任务静态收益均为100, 时间折扣因子为0, Δt_min=10 min。设定仿真次数为50次, 量子蚁群算法中以多无人机收益最大为目标函数, 蚂蚁数为50, 迭代次数为100次, 其余试验参数设置同文献[15]。对比结果如图 2所示。

仿真结果表明集中式量子蚁群算法任务分配收益值优于分布式CBCA算法, CBCA算法平均收益值为量子蚁群算法最优收益值均值的83.3%。造成这一结果的主要原因在于集中式量子蚁群算法从全局角度实现异构多无人机最优化任务分配, 而基于贪婪策略的分布式CBCA算法则以个体边际效益最大为投标原则。

4.3 动态场景验证

算例3中无人机群完成初始联盟任务分配后, 出现侦察类新任务, 任务时间窗口(min)为[30, 100], 初始位置km为(2.86, 0.91, 0), 任务静态收益为100, 其余参数设置同算例1, I_reset={UAV1, UAV3, UAV4}, n_reset=2。分别记录动态任务分配策略下任务路径列表(如图 3至5所示), 总收益值及算法运行时间对比结果如表 4所示。

仿真结果表明NR-CBCA策略耗时最短, 但是总收益值最低; FR-CBCA策略和PR-CBCA策略总收益值较高, 但是由于释放原有任务列表, 算法总运行时间更长。FR-CBCA策略收益值略低于PR-CBCA策略的主要原因是, FR-CBCA策略中侦察类无人机UAV1、UAV3及UAV4清空自身原有任务列表, 并重构自身任务包。以UAV3为例, FR-CBCA策略中新路径列表p′₃总收益值为417.746 6;PR-CBCA策略中p′₃总收益值为424.913 8。对比可以看出FR-CBCA策略中p′₃加入新任务后, 由于任务时效因子影响, 导致列表中后续任务收益值降低。

4.4 动态任务分配性能比较

算例4中将基于CBCA算法的3种动态任务分配策略与基于改进合同网协议(ICNP)方法^[16]进行比较。由于动态任务分配结果受任务时间窗口约束影响表现出随机性, 因此, 记录各不同无人机、任务数量组合下, 30次不同初始条件下算法平均收益值和平均运行时间。分别选取任务数量为6, 9, 12, 无人机数量为6~20, 侦察型和攻击型无人机配比为1:1, 不同情况下侦察类和攻击类任务配比如表 5所示。记录结果如图 6和图 7所示。

相比于ICNP算法，基于CBCA算法动态任务分配策略性能更优。3种动态任务分配策略均能解决复杂约束条件下异构多智能体动态联盟任务分配问题，但性能有所差异，NR-CBCA策略具有更好的实时性，但算法收益较低；FR-CBCA策略收益最高，但算法平均运行时间较长；PR-CBCA策略在保证任务分配结果质量的基础上，实现对动态场景的实时响应。

5 结论

1) 针对复杂约束条件下的异构多无人机智能体联盟任务分配问题，提出了一致性联盟(CBCA)分布式任务分配算法。仿真结果表明该算法可以实现复杂约束条件下完全分布式异构多无人机智能体系统任务分配；

2) 针对任务空间出现新任务的动态性，基于CBCA算法提出了动态任务分配策略，仿真结果表明3种动态分配策略均可获得高效合理的动态分配结果，FR-CBCA策略结果最优但耗时最长，NR-CBCA策略实时性较好但动态分配收益值最低，通过灵活设定参与重规划的智能体及释放任务数量，PR-CBCA策略在保证规划结果质量基础上，实现了对突发新任务及时响应。