面向任务的云、边、端分布式异构资源优选技术

李大伟，李 丹，刘博文，刘赛赛，王 栋

(中国电子科学研究院，北京 100041)

0 引 言

自然界中发现的大多数系统都是复杂的分布式系统，需要沟通和合作以实现共同目标。现代社会随着科技的不断发展，由异构节点构成的物联网、运输网等复杂体系也呈现出“网络极大化”的发展趋势，如何让复杂体系中的各节点各司其职就成了一个亟需解决的问题。

文献[1]将复杂体系中群体的组织模式分为网络、层次和联盟3类，每类模式具有其自身特性，往往根据任务场景需要采取相适应的群体结构组织模式。网络结构模式的群体内各节点之间可任意建立关系，具有极大的不确定性和自组织特性；层次结构模式中，群体可自顶向下按等级划分，高层级的节点具有较高的指挥控制权限，体现了任务由宏观到微观的逐级传递；联盟结构模式中，根据节点的特定属性可被划分为不同领域，任务可按领域进行拆分执行。

在军事应用中，层次结构是一种较为普遍和适用的多节点组织运用模式。文献[2]提出了多态认知智能体架构(polymorphic cognitive agent architecture，PCAA)，建立宏观(Macro)、微观(Micro)、原子(Proto)这3层认知架构，是一种多分辨率的层次结构。美国国防部高级研究计划局(DARPA)开展的进攻性蜂群使能战术(offensive swarm-enabled tactics，OFFSET)项目[3]，提出基于任务的集群系统架构，将无人蜂群作战行动自上而下分解为任务层、战术层、原语层、算法层，如图1所示。集群任务层主要表征粗粒度的整体使命需求，集群战术层对使命需求中的战术活动任务树进行建模，原子层对具体战术任务活动中的蜂群行为进行建模，算法层为具体蜂群行为提供基础功能模型。OFFSET也是典型的层次化体系架构，旨在推动蜂群自主性和人与蜂群协同工作方面的革命性发展，尤其关注蜂群自主战术行动的可行性，相关研究成果将直接应用到“马赛克战”体系中，推动低成本无人蜂群作战能力的快速构建形成。

图1 OFFSET集群系统架构

美国联合全域指挥控制条令规定使用集中式指挥和分布式控制执行的原则进行联合空中作战，推动这一空中力量组织运用原则的原因是，集中式指挥使高级梯队指挥官能够有效地控制、集结和领导部队；执行权力下放使部队能够掌握主动权，应对不确定和不断变化的环境，并提升末端的自组织灵活性[4]。

对于复杂群体结构的多智能体节点，处理分布式任务时，由于复杂性、高动态等因素具有较大挑战性。此外，多个智能体的存在提高了执行任务的性能和可信度，因为更多的智能体可以合作更快地完成相同的任务，并且系统对智能体的丢失或故障更加具有鲁棒性。此外，全局智能体分布式合作完成任务可能会降低油、电等资源消耗成本。然而，当使用多智能体系统来完成多项任务时，就会出现分工问题。

当前流行的多智能体强化学习方法则主要专注于构建完全分布式系统用于多智能体合作。在分布式系统中，每个智能体单独运行，它们自己观察环境并可通过点对点通信交换信息，实现多智能体合作。这样的分布式系统可以灵活构建大规模多智能体系统，并且具有极低的通信成本。但是在大多数情况下，分布式策略不稳定且难以学习，因为它们通常会互相影响，导致环境动态过程不稳定。虽然这个问题通过最近流行的“集中式训练和分布式执行”AC(Actor-Critic)方法得到缓解[5]，但如何有效地训练集中式的“Critic”至今仍是一个挑战。

任务分配问题的求解方法可分为集中式、分布式、混合式。集中式算法是过去研究较多的一类算法，中央协调或类似模块与所有其它智能体均有通信渠道，并决定必须分配给其它智能体的任务[6，7]。集中式任务分配方法主要包括蚁群算法[8]、粒子群算法[9]、遗传算法[10]等，这些方法的优点是它们使用较少的系统资源并且可能具有较低的实现成本，但是通信、计算成本高并且不适用于动态环境，因此它们主要用于少量智能体或静态任务的分配。此外所有智能体都与中央处理单元进行通信这一前提条件限制了它们的可扩展性[11，12]。

分布式算法克服了集中式算法的一些缺点[13，14]，引起了研究人员的广泛关注。分布式任务分配算法主要采用基于博弈论和基于市场的机制。在这种类型的算法中，没有中央协调模块，智能体对环境有局部感知，并且可能会彼此之间进行任务协商而不是被统一分配任务。每个智能体都有自己的收益函数。分布式算法将部分智能体的故障对整体的性能影响降到较小，同时具有较好的节点扩展性，但是由于局部的沟通结果可能会导致全局的任务冲突[11]。这种完全自主和分布式覆盖任务分配算法的主要特点和优势是，能够让感知和通信能力有限的无人机在未知环境下进行协同与控制。文献[15]针对异构多无人机执行侦察、攻击等多任务时的分配问题，提出带有时间窗的基于共识的捆绑算法(windows consensus-based bundle algorithm，WCBBA)。

混合式算法将上述两种方法进行结合，文献[16]将集中式优化和分布式拍卖的方法相结合，文献[17]将进化算法与贪心算法相结合，文献[18]将博弈论的方法与学习算法相结合。

本文主要聚焦解决实际作战场景中战役集中式指挥与战术分布式指挥控制相结合的任务分配模式，重点提出战术末端分布式任务分配方法，通过构建包含任务要素、多智能体要素的任务空间，分析智能体任务包构建、冲突消解等关键技术，将全局任务在收益最大化的要求下指派给合适的作战单元，研究特定时间窗口下的分布式无人作战资源优选技术，并在典型空海场景中进行仿真验证，具有较好的分布式任务分配效果。

1 任务空间

1.1 任务空间要素

任务空间要素主要包括任务、服务和作战单元，三者之间的关系如图2所示，作战单元提供服务，服务支撑上层任务的执行，三者之间存在内在联动的映射关系。

图2 任务、服务、作战单元三元关系

服务集合S={S1，S2，…，SK}。 寻求满足资源本体和任务执行等约束条件下的最优任务分配方案，从而发挥体系最大效能。

作战单元集合A={A1，A2，…，AN}， 其中N为作战单元的总数。作战单元通过服务的形式供任务组织编排和调用。

1.2 智能体属性

聚焦分布式任务分配，对作战单元进行基于多智能体的建模，首先给出作战单元关键属性要素如下：

(1)任务包

智能体i被分配的任务有序集合表示为bi={bi1，bi2，…，bi|bi|}，bi中的任务元素按加入包的先后顺序排列，|bi| 表示该智能体被分配的任务总数。

(2)任务路径

智能体i为完成所分配任务所需运行的矢量路径列表表示为pi={pi1，pi2，…，pi|pi|}， 其中 |pi| 表示列表长度。

(3)任务状态

智能体i的任务状态表示为τi={τi1，τi2，…，τi|τi|}， 列表中的每一个变量包含了执行任务的开始时间、持续时间和结束时间，在智能体投标和任务分配时需要考虑当前任务与智能体的任务状态是否冲突。

(4)智能体成功竞标矩阵

(5)任务中标矩阵

每个智能体对任务的中标者具有局部任务，即任务中标列表vi={vi1，vi2，…，viM}， 其中vij表示任务j的中标值，vij=0即意味着该任务尚没有中标的智能体。

(6)智能体信息时间戳

这里将智能体i的信息时间戳定义为si={si1，si2，…，si|si|}， 列表中的元素sik表示智能体i最后一次获知智能体k信息的时间，可以是直接信息交互或通过其它智能体进行间接信息交互。

1.3 任务分配问题建模

异构无人系统的任务分配问题可以定义为将一组复杂任务分配给一组智能体的问题，其中智能体和任务都可能随着时间的推移进入和离开系统。任务分配问题可转换为典型的混合整数线性规划问题，即：对给定的任务集合T={T1，T2，…，TM} 和作战单元集合A={A1，A2，…，AN}， 在规定的条件约束下寻求任务最大完成度的最优分配方案。上述问题可建模为

(1)

式中：Na为作战单元的数量，Nt为任务的数量，pi为作战单元i执行所分配任务的顺序，xij为作战单元Ai被分配了任务Tj，xi={xi1，xi2，…，xiN}， 求解目标为寻求全局收益最大化的任务分配模式。任务分配过程中服从以下约束条件

(2)

式中：Lt为作战单元最多可以被分配的任务数量。

智能体i对任务j的投标函数cij(xi，pi) 可以是任务分配结果xi或者路径pi的函数，与路径总长、任务完成时间等相关。

考虑任务执行的先后顺序以及任务的时间窗口，各作战单元需要在规定的时间内抵达指定的位置，任务分配需要将完成整体任务的消耗时间、路径代价最小化。

2 分布式任务分配算法

2.1 “云-边-端”跨层任务分配模式

“云-边-端”体现层次结构，“云”侧强调人在回路，重点对任务进行分解，并按照领域、方向将分解后的任务分配给“边”，“边”侧人机协作，为联盟结构，围绕特定领域开展任务分配；“端”侧为网络结构，强调末端作战单元的自主组织。“云-边-端”分布式任务分配模式的工作流程如图3所示。

图3 “云-边-端”跨层跨域任务分配和资源优选模式

“云”侧在任务分解时，依据混合知识空间的通用任务清单，通过OV-5a作战活动分解树模型[19]，呈现作战构想中的战略/战役/战术作战任务层次结构清单，通过将任务关联到作战活动分解树模型中的具体任务项，检索任务项下的子任务，实现将高层级任务进行分解，并将子任务按领域分配给“边”，由“边”进行具体的任务到资源的分配，是一个面向任务的资源优选过程。

“边”侧依据混合知识空间的“任务-服务-资源”内在联动知识模型，按需抽取任务所关联的作战单元资源池，其关联关系如上文图2中任务空间要素的三元关系所示。在具体任务分配时，各智能体作为“端”节点，采用分布式任务分配模式，根据自身功能属性、能力指标、任务状态等情况，对任务进行竞标，通过分布式节点局部信息交互共享，对存在冲突的竞标结果进行消解，不断迭代以达成全局收益最大化。

2.2 算法原理

本文提出一种基于分布式拍卖机制的“云-边-端”跨层 多任务分配算法，算法包含两个阶段，即智能体任务包构建和基于全局共识的冲突消解。在智能体任务包构建阶段，每个智能体根据自身能力、位置、状态、收益等情况投标合适的任务，生成自己的任务包，任务包中的任务按时间次序执行，并能够按照一定的路径串联起来；在基于全局共识的冲突消解阶段，相邻智能体之间进行信息交互，根据投标值高低更新自己的任务包信息，并采用冲突消解规则达成共识，通过不断迭代促进分布式智能体完成全局信息交换并达成全局共识，算法思路如图4所示。

图4 算法思路

2.3 智能体任务包构建

每个智能体仅创建其自身任务包，该任务包会随着分配过程的进行而更新。在智能体具备的能力约束条件范围内，每个智能体按照最大化自身任务收益为原则进行任务投标，任务包具有两个任务相关向量：bi和pi，其中bi是按照任务的添加顺序，pi是按照任务的执行顺序。

设智能体i初始任务包为bi，则其在后续的任务投标过程中会选择将边际收益最大的任务Tj∈T加入到bi中，直到无法添加。

任务包的更新如下

bi←(bi⊕endj)

(3)

pi←(pi⊕njj)

(4)

式中：⊕nj表示增加在位置n的任务j。

在所有任务完成分配后，当出现某服务失效或失去连接时，该服务需求会再次发布。任务包中的任务根据添加顺序进行排序，而路径中的任务根据其预测的执行时间进行排序。

(5)

算法1：任务包构建

输入:Wi(t-1),Vi(t-1),bi(t-1)和pi(t-1)

输出:Wi(t),Vi(t),bi(t),pi(t)

While |bi(t-1)|

cij=maxSi(pi⊕{j})

for ∀j∈J

hij=1

hij=1

else

hij=0

end

else

end

end

end

Ji=agmaxjcijhij

ni,Ji=agmaxnSi(pi⊕{j})

bi(t)=bi(t-1)⊕end{j})

pi(t)=pi(t-1)⊕ni,Ji{j})

end while

2.4 基于全局共识的冲突消解

在构建完成自身的任务包后，各智能体之间是不知道相互之间的任务分配状态情况的，由于智能体之间可能存在冲突任务，例如不同智能体分配到同一任务，因此需要智能体之间进行信息交互和共享，重置或更新自身的任务包，从而确保每个智能体的任务包都是正确的，在全局智能体之间达成任务分配的共识。在基于全局共识的任务冲突消解阶段，所有智能体需要与相邻智能体之间进行信息交换，包括获胜智能体列表、获胜投标列表和时间戳列表，并按照一定的规则更新自身信息以达成面向任务的全局共识。

从具体规则来看，智能体Ai会通过比较其它智能体对相同任务的投标值来确定自己是否会中标。如果自身投标值更高，则它将通过竞标分配到任务。如果获知任务Tj有更高的投标值，则Aj会释放Tj， 并将任务包中后续的任务进行删除和再分配。智能体选择全局最高收益任务如下所示

(6)

其中，hij=I(cij(pij)>vij)， 表示智能体i之外高于vij的有效投标值。

在全局最高收益下，智能体i的任务包更新情况可表示为

bi←(bi⊕endj*)

(7)

pi←(pi⊕nj*j*)

(8)

任务路径pi在该任务后的所有任务也会随之删除，在下一次的迭代中进行重新分配。

全局共识是为了避免由于广域分布的智能体之间信息不共享导致同一任务被加入到不同智能体的任务包中。在相邻智能体之间进行信息交互共享时，当发现别的智能体投标值更高的情况，则进行任务更新；当路径出现变动时，则后续任务进行重置；当自身投标值高时，进行任务保持，冲突消解规则公式如下：

(1)任务更新：wij=wkj，vij=vkj；

(2)任务重置：wij=∅，vij=0；

(3)任务保持：wij=wij，vij=vij。

3 算法仿真

在本节中，我们对提出的方法进行仿真验证。仿真环境配置为Intel(R)Core(TM)i7-8700K @3.70 GHz CPU处理器，Window 10操作系统。设定在某空海场景中，任务空间范围设定为30 km×30 km×10 km，作战单元包含有无人诱饵平台、无人侦察平台、无人打击平台、察打一体无人平台、远距离无人通信平台5类6种异构无人系统，可以执行诱骗、侦察、打击、通信4类任务，任务遵循OODA环的顺序，在场景中可根据需求随机生成所需任务清单列表，并且可根据需要随时加入或删除任务和资源，每个任务具有任务类型、坐标位置、最晚完成时间、任务需持续时间等信息。无人平台、服务的关联关系见表1。

表1 某空海场景下无人平台类型

3.1 跨域分布式任务分配

假定该空海场景中共有6型异构无人系统共10个，需执行诱骗、侦察、打击、通信4类任务共计22项，各无人系统及任务的位置由MatLab中的rand函数生成。设定该空海场景下优化目标为所有任务执行完成用时最小化，各无人平台的任务分配结果如图5所示，圆圈代表各类异构无人系统，线段表示异构无人系统的运行路径，两个相邻的三角形之间的连线代表在执行相关的任务，无人平台在任务分配中可能执行多个任务，结果清晰地展现了各无人系统的任务分配结果及执行任务的路线图。算法确保无人平台在任务执行过程中路径及消耗相对较少，全局收益趋向极大值，且智能体所执行的任务之间不会出现任务和路线冲突。

图5 时间窗口下的任务分配结果(A=10，T=22)

3.2 面向扰动的适变调整

面向复杂、高动态的环境，在任务完成初始分配后，主要存在2种变数，一是“端”节点发生变化，比如由于某些作战单元被打击失效或失去连接无法使用；二是任务发生变化，比如出现新增任务或任务出现判断分支。面对这些变化时就需要对任务分配进行动态调整，适变任务分配流程如图6所示。“边”侧实时更新可用的作战单元，同时发布新的“任务-服务”需求，“端”侧各作战单元根据自身功能属性、能力匹配、任务状态、预期收益判断是否投标以及具体投标值，通过全局共识确认是否中标，从而执行新的任务。

图6 任务适变调整流程

为简化问题，任务取诱骗、侦查、打击3种，任务数量及类型见表2，作战单元共有3种，每种数量有3个，每种作战单元可以执行任一任务。

表2 任务类型及数量

在t时刻，假定智能体9失效，其原先被分配的后续任务将无法执行，此时需要对所有尚未执行完的任务进行适变分配调整，根据当前智能体的位置、能力、状态等情况，将尚未完成的任务重新分配给剩下的智能体1-8，分配后的智能体任务计划如图7所示，各智能体执行任务的空间路径如图8所示。

图7 不同无人平台的任务分配计划

图8 时间窗口下的任务分配结果(A=8，T=20)

3.3 不同服务集成度的效能分析

不同作战单元会具有不同集成度的服务，平台越大功能越多，其集成度也越高。美军的“马赛克战”新型作战概念提出采用分布式小平台的马赛克单元构建分布式杀伤网，基于多智能体建模方法对可快速分散、组合且异构作战力量进行建模仿真，并得出结论：分布式小平台的作战适变性和造价性价比要高于大平台[20]。

图9 不同服务集成度的任务完成效果

4 结束语

针对异构无人系统的分布式任务分配和优选问题，基于全局动态合约共识，提出知识驱动的“云-边-端”跨层分布式任务分配模式，重点设计针对端侧的分布式任务分配算法，实现战场上任务与资源的匹配和优选，并结合典型场景进行仿真验证，结果表明该算法能够实现跨域分布式任务分配，并能够面向扰动进行动态适变，具备面向未来复杂动态环境的适应能力。