周 鑫, 王维平, 朱一凡, 王 涛, 井 田

(国防科技大学系统工程学院, 湖南 长沙 410073)

0 引 言

当前战争越来越复杂,装备之间的联系愈加多样,特别是近些年无人装备[1-3]的逐渐使用,使得作战样式发生深刻变化。体系是有限数量组分系统的集成,这些组分系统能够独立运行,在一定时间段内相互联系以实现更高的目标[4-6]。无人装备体系是以无人装备为核心的体系,是由协同网络连接的无人装备系统组成,这些无人装备系统具有某些性能上互补的功能,可以完成某些任务,其核心要素是使命任务、装备系统和交互协同。从功能结构可以划分为侦察监视预警无人装备体系、指挥控制无人装备体系、火力打击无人装备体系和综合保障无人装备体系;从对象层次分可以分为无人装备编制体系、面向任务的无人装备体系等。本文主要研究面向任务的无人装备体系(本文中简称装备体系),由于装备体系是复杂的,涉及到装备建设与应用的诸多方面,因此本文通过研究装备体系架构来研究整个体系。架构[7-8]是体系的组分系统、组分系统之间关系,以及约束其演化的规则和指南。当前面向任务的装备体系架构少有从影响作战能力的核心要素出发进行考量,同时往往直接给出了架构与能力之间的映射关系。然而很多情况下,能力与架构之间难以找到映射关系,更有可能是一种概率关系。因此,本文定义了装备体系架构形式化模型框架,构建了架构方案空间搜索问题模型,并提出了一种动态规划算法以求解问题。

与指导建筑施工的架构图一样,装备体系架构也用于指导装备体系的建设与运用。面向不同使命和环境,不同装备体系表现出不同的能力,该体系是基于架构构建的,因而可以认为每个架构具有潜在的能力,称为架构能力。需要说明的是,架构能力在体系建成之前是不确定的。所谓原型化,就是将逻辑层面的架构实例化为物理层面的体系的过程,例如搭建仿真系统、演示系统、实物系统等。在设计架构一般考虑体系的核心要素,无法考虑所有可能要素。因此,架构能力的不确定性体现在两个方面:架构本身的性质,设计过程中未考虑的一些次要因素。其次,可能存在多种手段将同一种架构原型化为体系。此时,应评估这些手段的预期收益以便做出最佳选择。再者,可能需要若干备选架构以便供决策者选择。

鉴于此,本文主要工作如下:第一,提出了一种装备体系架构超网络模型,该超网络主要由任务网络、装备网络、协同网络组成,此外提出了一种新颖的架构方案空间动态规划问题框架[9]。第二,针对架构方案空间动态规划问题,论文提出了一种基于顺次分配的多Agent搜索算法,从理论上分析了该算法具有多项式时间的计算复杂度,并且可能是最优的。第三,论文通过仿真实验检验和评估了算法的性能,实验结果表明提出的算法质量很好,并优于其他基准算法。

1 相关工作

本节从装备体系架构和架构搜索问题两方面回顾有关相关工作。

1.1 装备体系架构

能力是在一定预先筹备和环境条件的前提下,完成作战使命以达到某些作战效果[10-11]。美国国防部认为生成作战能力需要提高理论、组织、训练、装备、领导和教育、人员、设施和政策[12-13]几个方面水平,即将装备和非装备要素有机地结合在一起[14-15]。本文着重从装备角度出发设计满足作战能力的体系。目前,许多学者对装备体系架构提出了自己的理解,但没有统一的概念。在军事应用中,许多体系架构框架被广泛使用。常见的架构建模框架包括:美国国防部体系结构框架[16]、英国国防部体系架构框架[17]、北约体系架构框架[18]。本质上这些架构可以由超网络模型表示,超网络是指规模庞大、连接复杂、节点异构的网络,即超网络由多个不同特征的网络组成,这些网络具有多层、多维、多属性等特征。超网络是一种通用模型,可用于反映装备体系架构中的相互作用关系。例如,Gao[19]提出了一种超网络模型,包括感知节点、指控节点和打击节点,以及这些节点之间的关联。Shi[20]提出了一种由5个异构节点组成的超级网络,包括传感器节点、信息节点、决策节点、通信节点和交战节点,节点之间存在不同类型的交互。Chen[21]提出了一种指控超网络模型,包括感知子网、指控子网和火力子网。不同于与之前提出的超网络模型,本文面向任务能力的核心要素,即任务、提炼体系架构,并给出超网络模型形式化描述。本文工作与现有工作出发点不同,之前研究出发点是作战过程中主要环节。而本文的出发点是基于能力,衡量架构优劣的指标也是能力。

基于能力的架构设计考虑了在近期和远期可能遇到的不同威胁,以及在军事上要消除这种威胁所需要的能力,更多着眼于对手当前和未来可能怎么打仗。该模式具有更为广泛的视野,更具有指导性和目标性。关于架构能力与架构超网络模型之间的关系,之前研究者大多将其建模为函数关系,如Shu[11]提出了架构超网络模型与架构能力之间的映射关系,并提出了一种基于智能演化的架构方案空间探索算法。然而能力与架构之间往往难以给出映射关系,因为还涉及到许多不确定因素,因此两者之间更有可能是符合概率关系。

1.2 方案空间搜索

在本文中,装备体系架构被建模为一个超网络方案,面向同一使命任务的多个超网络方案构成了体系架构空间。那么,此时需要提出架构空间搜索算法以便从中选择最优的若干架构方案。本文将架构方案空间搜索问题建模为一类数学优化问题,并将架构方案空间搜索问题转换为一种方案路径选择问题,这问题类似于旅行商问题[22]。旅行商问题是一个组合优化问题,是指推销员遍历所有城市并返回其家乡城市的最短行程,期间不能两次访问同一城市。旅行商问题被广泛用于实际问题中,例如车辆路线规划和仓库货物放置[23-24]。群体智能算法是解决组合优化问题的有效手段,例如遗传算法、粒子群算法、蚁群算法、萤火虫算法、蝙蝠算法、细菌菌落觅食算法、蜂群算法和蜘蛛猴算法,以及其他扩展算法[25-26]。这些群体智能算法通过大量的仿真实验找到最优值,但是很难保证理论上找到最优值。旅行商问题与本文提出的问题有所不同,本文提出问题中每种架构方案在搜索之前其能力是未知的,服从某种概率分布;确切能力值只有在原型化之后才知道,且在原型化之后架构的能力值是确定不变的。因此,群体智能算法很难直接应用于本文问题。

在面临重大决策问题时,一般采取的思路是先评估-后决策。而如何评价装备体系具有一定挑战性。一种可行的方法是边实践边评估,即基于某种架构搭建体系原型,如果该体系原型具有较高能力值则选择该体系,反之则继续根据新的架构搭建体系原型。潘多拉问题[27]主要解决经济学中的项目方案选择问题,每种项目方案在实际运用之前并不知道其获得的价值,通过边实践边评估的方式进行搜索,最终选择合适的项目。但是潘多拉问题只能选择一个项目方案,无法直接用于多个方案的选择问题。Chen[28]也做过类似研究,将潘多拉问题应用于人机协作,但也只能选择一个方案。顺次分配法正好适合求解多方案选择问题。顺次分配法是一种常用协调方法,广泛应用于资源分配、多机器人路径规划等问题。在顺序分配机制中,Agent轮流做出决策。在每个回合中,每个Agent选择策略以基于当前情况获取最大回报值。

2 装备体系空间搜索问题

本节给出装备体系架构定义,提出一种多Agent系统[29]动态规划问题。

2.1 装备体系架构的定义

能力用于衡量体系完成使命任务可能性的大小。具体来说,每种装备系统具有一定功能,通过协同结构相互连接装备系统具备完成特定使命的能力。装备体系架构(以下简称“架构”)只考虑了装备体系的核心要素,因此根据该架构所原型化的装备体系的能力具有不确定性。架构形式化由架构能力、原型化成本以及架构超网络三部分组成,记为〈W,P,GA〉,其中GA表示架构超网络。下面分别给出架构能力、原型化成本以及拓扑模型三者定义。

(1)架构能力

架构能力是指装备体系完成特定使命的能力,记为W。其中装备体系由装备体系架构原型化而成。在原型化之前,架构能力不确定性用概率分布表示,记为W。这是因为架构能力可能受一些不确定因素的影响,对于这种不确定因素一般用概率来表示。确切能力是在体系建成之后才能得到,而原型化的过程是需要花费成本的。对于体系架构能力概率分布的选择和参数赋值,可以采取定性与定量相结合的方法,如层次分析法,在本文中认为已有相关数据。

(2)原型化成本

原型化成本是指根据架构方案建设体系时所花费的成本,记为P。本文假设每个架构的原型化成本是已知的和固定的。

(3)拓扑模型

架构方案可抽象为拓扑模型，是由任务网络、装备网络和协同网络3种不同类型的子网络及其相互关系构成。

任务网络是由任务节点组成的网络,记为GT=(VT,ET),其中VT表示任务节点,ET表示任务节点之间的关系。任务节点是指装备系统能够执行的活动过程,记为T。此处任务是通用概念,例如飞行器的空中遮断、近距离空中支援、抵近侦察、电子对抗、空运等。根据决策层级不同,任务粒度大小也会不同。对于同一层任务,可以分为并列关系、顺序关系、无关联关系等;对于不同层任务,应自顶向下分解任务,上层任务由下层任务组成,逐层分解直至不用分解为止。一般而言,层与层之间的关系可以包括一对一、一对多、多对一关系、多对多关系等。

装备网络是由装备节点组成的网络,记为GQ=(VQ,EQ),其中VQ表示装备功能节点,EQ表示装备功能节点之间的关系。装备节点是指具有一定功能,且能够独立完成特定任务的装备系统,记为Q,换句话说装备网络也可以认为是功能网络。根据观察-调整-决策-行动[30]流程,装备可以分为侦察装备、信息处理装备、指控装备、打击装备、评估装备、保障装备等类型。这些类型的节点通过功能依赖关系相互关联,如侦察无人机具有侦察功能,将收集的目标信息传递给指挥部;指挥部具有决策功能,但需要无人机提供的侦察数据;因此两类节点具备关联关系。

协同网络是由协同节点组成的网络,记为GC=(VC,EC),其中VC表示协同节点,EC表示协同节点之间的关系,例如信息协同、决策协同、行动协同等。协同节点是指用于处理信息、组织管理、决策计划、控制反馈等活动的逻辑节点,能够处理上下级之间的指令关系以及同级之间的协作关系,记为C。设计协同网络的目的是使得所有装备系统相互联系以达到预期使命。

任务网络中任务节点与装备网络中的装备节点映射关系可以抽象为二分图GTQ=(VT,VQ,ETQ),其中ETQ表示任务节点VT与装备节点VQ之间的关联关系。装备网络中装备节点与协同网络中的协同节点映射关系可以抽象为二分图GQ C=(VQ,VC,EQ C),其中EQ C表示装备节点VQ与协同节点VC之间的关联关系。

架构是由3类节点和5类关系组成的网络,架构超网络模型如图1所示。构建方法如下:第一,将装备体系使命任务分解为可以由装备执行的任务网络;第二,给出能够完成任务的装备及其对应关系,并根据任务网络构建装备网络;第三,每个装备节点都是一个协同节点,在此基础上建立协同网络。一般而言,如果超网络中具有更多的节点或者更复杂的关系,那么架构的原型化成本将会更大,架构能力可能也会更大。架构能力与超网络之间的映射关系是一个复杂课题,是面向特定领域和不同情况的。因此,本文直接给出每种架构的能力分布,不研究架构能力与超网络之间的具体映射关系。

图1 架构超网络模型示意图

2.2 架构方案空间搜索问题

对于装备体系架构选择问题,最终还是需要决策者做决策。本文旨在提出无人干预情况下的一种自动规划算法,最终提供若干架构方案以供决策者参考。假设最终需要推荐N个架构,此时可以认为有N个决策者进行决策,每个决策者从各自方案空间中选择一个架构。将决策者抽象为Agent,那么架构方案空间搜索问题可以抽象为多Agent系统动态规划问题。不失一般性,以Agentm∈M为例进行说明。

(1)

(2)

参照文献[28],Agent根据式(2)确定如何选择行动,其中:

(3)

3 动态规划算法

本节首先提出了一种基于顺次分配机制的方案空间搜索(sequential allocation mechanism based scheme space exploration,SAMSSE)算法,然后对SAMSSE算法进行理论分析。

3.1 SAMSSE算法

(4)

指标za,k相当于预期回报的评判值,如果该指标越大,则探索该架构所得的回报值越大,反之则越小。

根据式(4),可以推导出:

(5)

(6)

不失一般性,本文以Agentm为例进行说明。单个Agent搜索算法可以分为3个阶段:指标排序、指标判断和架构选择。指标排序是指根据等式(6)计算所有决策指标;指标判断是指如果Agentm要搜索未知体系架构,则选择具有最大指标的体系架构和行动;体系架构选择的准则是,当所收集的最大采样能力值大于所有未知体系架构的最大指标时,Agentm停止搜索并选择具有最高采样回报值的体系架构。SAMSSE算法分为IndicatorSorting和PolicyComputing两个程序。每次执行SAMSSE算法得到的是一次采样值,因而需要多次运行以求取期望值。

程序1 IndicatorSorting(K)开始 K,π←⌀ c←0 K←KForm∈M,km∈ Km,amk∈Amkdo za,k←Solving(ca,k=∫∞za,k(wk-za,k)dFk(wk)) EndFor Form∈Mdo πm←Sorting(za,k|k∈Km,a∈Amk) π∈π∪πm EndFor Returnπ结束

程序2 PolicyComputing(K,π)开始 Form∈Mdo w*m←0 Fori=1to|Km|do km←arcmaxkm∈ Km(πm) akm←arcmaxak∈Akm(πm(km)) Ifw*m

3.2 性能分析

本文的主要创新之处在于结合潘多拉规则与顺次分配方法,解决多无人装备体系架构方案选择问题。

SAMSSE计算时间复杂度与排序算法一致。从IndicatorSorting可以获知,SAMSSE算法的计算时间复杂度取决于排序算法的计算时间复杂度,例如堆排序的时间复杂度为O(nlgn)、冒泡排序的平均时间复杂度为O(n2)。每个Agent都根据体系架构的决策指标进行排序,在程序运行过程中该顺序始终保持不变。因此在整个程序运行过程中,该算法时间复杂度等于排序算法的时间复杂度。

4 仿真实验

本节设定若干场景,通过仿真实验分析SAMSSE算法的性能。

4.1 实验设置

假设要建立一种由无人机集群和无人车集群组成的新质力量体系,完成诸如边境巡逻、持续侦察和电磁干扰等任务。对于这样的新使命新力量,如何建立无人体系是首要问题。本文提供的模型框架是一种可选择的方法:第一,将使命分解为任务网络;第二,这些任务可由具有某些功能的无人机或无人车完成,由此建立无人系统与任务之间的关系,以及无人系统之间的功能依赖关系;第三,每个无人平台都是一个协同节点,根据需求建立协同网络。

本实验定义了一些算法性能评估指标如下。

(1)回报值:采样能力值和累计原型化成本之间的差值。回报值不仅体现了装备体系架构的能力值,同时也体现了架构筛选是需要花费代价的。

(2)运行时间:运行一轮仿真实验耗费的时间。

本文设计了3个场景来评估算法的可扩展性。架构方案空间大小|K|分别为50、500、5 000。每种架构的原型化有3种,其原型化成本分别遵守不同的均匀分布c1～U(10,20),c2～U(5,30),c3～U(15,25)。每个架构k的能力值服从概率分布wk～U(p1,p2),其中p1～U(500,1 000),p2～U(1 000,2 000)。令选择的架构方案数量(number of selection,NoS)为1到10,排序方法为冒泡排序法。

场景 1在|K|=50的方案空间中搜索。

场景 2在|K|=500的方案空间中搜索。

场景 3在|K|=5 000的方案空间中搜索。

4.2 实验结果

(1)场景1

图2(a)展示了场景1中SAMSSE、EVP和RS的平均回报值,表明随着NoS的增加,平均回报值增加,且SAMSSE的平均回报值略高于其他算法。图2(b)展示了场景1中SAMSSE、EVP和RS的平均运行时间,表明SAMSSE平均运行时间略高于其他两种算法。

图2 场景1仿真运行结果

(2)场景2

图3(a)展示了场景2中SAMSSE、EVP和RS的平均回报值,表明SAMSSE的平均回报值略高于其他算法。图3(b)展示了3种算法的平均运行时间,表明SAMSSE平均运行时间略高于其他两种算法。

图3 场景2仿真运行结果

(3)场景3

图4(a)展示了场景3中SAMSSE、EVP和RS的平均回报值,其中部分RS结果未显示,这是因为其结果为负数。与前面的实验结果一样,SAMSSE的平均回报值远高于其他算法。图4(b)展示了场景3中SAMSSE、EVP和RS的平均运行时间,实验结果表明SAMSSE平均运行时间略高于其他两种算法。

图4 场景3仿真运行结果

(4)纵向对比

对场景1～场景3中SAMSSE算法的平均回报值和平均运行时间进行比较,平均回报值如图5(a)所示。实验结果表明,随着NoS的增加,平均回报值随之而增加。平均运行时间如图5(b)所示,实验结果表明随着NoS的增加,平均运行时间呈多项式增长。

图5 不同场景下SAMSSE仿真实验结果

总的来说,这些实验结果表明SAMSSE的性能优于RS和EVP。原因在于SAMSSE通过基于最优决策指标的方法顺次选择架构,从而能够找到最优的搜索路线。

4.3 实验分析

根据以上仿真结果,可以发现SAMSSE算法有一些有趣的现象。首先,SAMSSE算法是一种顺序分配方法,因而随着变量NoS的增加,回报值也会增加。其次,运行时间增加幅度可能会随着NoS的增加而降低。一方面,每轮都会重新筛选并选择一种新架构,因而总运行时间将逐渐增加;另一方面,已经探索了但未选择的架构可以用作后续采样的先验条件,故后续Agent可能在探索更少的架构情况下便停止搜索,因此运行时间的增量可能会减少。第三,实验结果表明SAMSSE的性能优于RA和EVP。原因是SAMSSE通过基于决策指标的方法贪婪地选择架构。该指标是根据特定的问题特征计算的,并被证明是在特定条件下得到最优搜索策略,从而可以找到较好的搜索路径并选择最佳的架构。

5 结 论

本文提出了一种面向任务的装备体系架构设计方法,为无人体系等新质力量装备体系架构的构建及选择提供思路。本文提出了一种基于超网络的装备体系架构模型,并提出一种方案空间搜索算法。该问题的目标是在给定架构方案空间中选择若干最优架构。具体而言,架构空间搜索过程被建模为一种多Agent动态规划问题。假设在搜索之前获知每种架构能力的概率分布,但在架构被原型化之前其具体能力是未知的。为了解决这一问题,提出了一种基于决策指标的顺次分配算法。通过理论分析和仿真实验,证明和验证了该算法的计算时间复杂度是多项式的且回报值可能是最优的,回报值远高于其他基准算法而运行时间与其他算法相近。