改进合同网协议在防空武器目标分配中的应用*

郭智杰，糜玉林，肖阳，姜文志，贺林波

(海军航空工程学院a.研究生管理大队；b.训练部；c.兵器科学与技术系，山东 烟台 264001)

改进合同网协议在防空武器目标分配中的应用*

郭智杰a，糜玉林b，肖阳a，姜文志c，贺林波a

(海军航空工程学院a.研究生管理大队；b.训练部；c.兵器科学与技术系，山东 烟台 264001)

针对现代防空作战呈现出的协同性和动态性，引入多智能体系统的概念，对武器目标分配问题进行描述，建立了基于改进合同网的武器目标分配体系结构。在此基础上对传统合同网的招投标策略、中标策略及签约策略进行设计改进，提出了一种基于改进合同网的防空武器目标分配策略。最后以防空作战想定为例，通过仿真实验对基于合同网和改进合同网的武器目标分配策略进行了比较分析。实验结果表明，后者更具合理性和有效性。

武器目标分配； 智能体； 多智能体系统；防空体系； 合同网；NetLogo

0 引言

武器目标分配(weapon target assignment，WTA)问题一直以来都是防空作战研究的热点，最初来源于防空领域的资源分配问题，其重点解决如何在时间T内合理地分配M个武器到N个目标，使得防空作战效能最大化[1-2]。随着防空作战面临的战场环境日益复杂，如何在有限时间内对武器进行快速有效地调配是一个较为复杂的问题。

目前绝大部分的多Agent系统采用合同网机制，并且合同网协商机制的求解质量和收敛性已被广泛认同[3]。为了适应防空作战中涌现出的协同性和动态性，这里采用相对成熟的合同网协议(contract net protocol，CNP)进行作战任务分配[4]。国内不少学者对此进行大量的研究，提出基于扩展合同网的任务分配方法[5-8]，国外学者针对传统合同网的不足进行了不同程度的改进[9-10]。本文正是基于前人的研究基础上，提出一种基于多智能体系统(multiple agent systems，MAS)的改进合同网策略，并将其用于解决防空作战武器目标分配领域，有效解决防空作战单元的动态协同问题，提升了系统整体效率。

1 要地防空WTA问题描述

现代要地防空作战中的WTA问题，通常是指处于不同空间位置的多种作战平台、多种武器单元协同打击目标，以最小代价来换取整体防空作战效能的最大化。为了更好地对问题进行描述，这里将防空作战武器目标分配映射成一个MAS[11]，在该MAS中定义3类智能体：武器智能体(weapon agent，WA)，平台管理智能体(platform management agent，PMA)，指控智能体(command agent，CA)。其中CA本质上是从多个PMA中选择出来的指控中心。表1对系统中各符号参数进行说明。

表1 MAS符号参数说明

防空作战武器目标分配实质就是Z求极值的过程，即MAS中各智能体如何协作以求系统效能最优的过程。则系统整体效能Z可表示为

(1)

式中：Mj表示第j个目标的威胁度；Xij表示第j个目标是否分配给第i个武器作战单元，若成功分配则取值为1，否则取值为0；Vi和Vj分别表示武器作战单元和目标的能力价值；p表示武器作战单元拦截目标概率；p′表示武器作战单元被目标攻击概率。

2 基于改进CNP的防空WTA体系结构

2.1 传统CNP

CNP是Smith在1980年对分布式问题研究过程中提出的一种Agent协同手段[12-13]，其基本原理是引入市场经济中的招标-投标-中标-签约机制。基于合同网协议的整个任务分配过程中，招标者以广播形式发布任务信息，投标者根据自身能力相应地进行投标，招标者对投标者完成任务的能力进行评估，从而决定是否与其签订任务合同。传统合同网基本原理如图1所示。

图1 传统CNP基本原理Fig.1 Basic principle of traditional CNP

2.2 改进CNP

针对传统CNP理论的不足，主要对合同网协议进行以下3方面的改进：

(1) 为了筛选合适的WA，这里引进黄页服务的思想，要求所有的WA将自身的能力、类型及服务内容注册在CA的系统目录里，这样CA就能随时掌握WA的状态，从而筛选合适的个体进行任务分配，减少与个体的协商次数，从而提高系统执行效率。

(2) 通常来说，一方面，系统中的Agent存在自私性，会隐瞒自身所能承受的任务负荷和自身所具备的能力[14]，因此，这里假设系统个体均诚实可靠；另一方面，针对WA无限制的投标和评标机制，这里引入新的投标策略和评标策略，用于在规定时间内完成对系统Agent的投标和评标工作。

(3) 针对系统动态性不足的问题，设计一种可解约的风险合同用于解决。系统中Agent可能随时进入和退出，会导致原有分配方案受到影响，设计该合同可降低任务冲突和执行缺失的情况，一定程度上可避免死锁现象。

改进后的CNP方案与传统CNP方案的特性比较如表2所示。

表2 传统CNP与改进CNP特性比较

2.3 体系结构

为了更好地对防空WTA问题进行研究，建立如图2所示基于改进CNP的防空WTA体系结构，这里作出以下假设：

(1) 整个防空体系采用理想的网络化结构。在CA有限的集中指挥方式下，各网络作战节点WA均可进行独立或协同作战。防空作战网络里的信息实现动态共享，网络体系中WA，PMA和CA三者之间通信链路可靠，随时可用。

(2) 体系中所有的Agent处于理想状态，指控中心CA下达给武器平台的任务，都是经过分解之后所得到的最小粒度的任务，并且各子任务之间是相互独立的。所构建的武器目标分配体系，是针对多目标的多平台协同决策；对于单一来袭目标则无需进行协同。

(3) 体系中各执行任务的Agent地位均等，所构建目标分配体系中所有Agent只存在与外界交互，以及Agent之间进行交互协作。Agent自身不带有其他特性，在目标分配期间CA，PMA和WA三者之间不存在互相干扰，也考虑外界来袭目标的物理或电子干扰。

图2 基于改进CNP的防空WTA体系结构Fig.2 Structure of WTA based on improved CNP

3 基于改进CNP的防空WTA策略

3.1 招标准备

这里引入黄页服务的概念，黄页是国际上对照企业性质或产品类别编排的商业电话号码固称，因其惯用黄色纸张印刷，故称黄页[15-16]。

招标开始前，防空体系结构下的所有WA需要向PMA注册自己的信息，包括武器类型、射程及飞行速度等战技指标，初始化后形成完整的黄页目录由PMA进行管理，系统目录则由CA进行统一管理，体系中各PMA共享该目录。在每一次目标分配完成后，都需要更新目录，尤其是当防空作战过程中有新平台进入或平台因故障退出时，也需要向系统注册或注销自身信息，随时保持目录动态更新。

3.2 招标阶段策略

当初始集中分配结果不理想或目录发生更新时，此时可根据需要进行公开招标。若此时只有1个目标需要分配，则通过查询目录向具备完成此目标的WA发送招标书；若此时有多批目标需要进行分配，则按照目标威胁程度进行排列，依次发送招标书至WA。其中招标任务书的信息如表3所示。

3.3 投标阶段策略

在向PMA发送招标书后，各火力平台所属的武器单元WA进行公开招标，由底层的WA进行投标。假设Wi接收到招标书时已签订k个合同，此时对自身投标能力进行评估决定是否投标。设计Wi的投标规则如下：

表3 招标书内容描述

(1) 时间约束估计

Wi根据发来的任务目标信息计算击毁目标所需的时间Ti，k+1、完成上一个任务所需时间Ti，k以及Wi所能等待任务响应时间T(i，k+1)，则此时应满足Ti，k+1TEva。

(2) 投标值估计

Wi首先计算自身目前整体效能和投标后预计的整体效能，然后按照式(2)计算此次投标值Bi，k+1，若Bi，k+1>0，则可以考虑投标。

(2)

Wi将计算结果写入投标书并反馈给Ai，体系里所有PMA将投标书发送汇总至CA等待进行处理。

3.4 中标阶段策略

指控中心CA在收到投标书后，需要对投标者进行多指标综合评价，以此避免或减少资源重复使用次数。假设投标书数量为l，这里采用时间、效能、代价3类主要指标对标书内容进行综合评估，具体评标策略如下：

(1) 任务完成时间指标评估

对于打击同一目标任务，招标者CA希望以最快的时间完成任务，故需要从所有投标者中筛选出完成任务耗时最少的为中标者，则有

(3)

(2) 作战能力指标评估

对每个投标者进行作战能力的评估主要是从2方面的因素进行考虑，一方面考虑投标者反馈的投标值Bi，j，另一方面则考虑投标者已有负载Qi大小，则有

(4)

(3) 执行任务代价指标评估

所有WA执行任务都会付出相应代价，这些代价包括通信代价、作战资源消耗成本及武器保障成本等，则有

(5)

这里综合考虑以上3种指标影响，对其进行加权评价。其中各项指标的权重系数由防空作战指挥员的决策意图和任务的客观需求来具体确定，其中αt+αa+αc=1，最终得出综合评价指数

(6)

根据综合评价指标筛选最优的武器单元WA执行任务，当筛选出的WA无法完成任务时，即可进行二次筛选，在已投标的WA中选择最优的个体进行协同作战，以此循环直到任务完成为止。

3.5 签约阶段策略

CA在对所有投标者进行评估之后筛选出最优的中标者并与之签订合同，此时中标的WA更新黄页目录上注册的信息，可有效降低二次招标时通信量。为了适应防空作战的动态性及协同性，这里设计一种可解约的风险合同。风险合同规定描述如下：

(1) 正常情况。CA与中标者签订合同之后，中标WA正常执行并顺利完成任务。

(2) 任务出现死锁现象。在签订合同之后，由于战场态势变化使得任务复杂度增大导致WA无法正常完成任务。此时在保证系统整体作战效能不发生较大变化的前提下，CA寻找其他适合的WA与当前任务WA进行合同交换。通过交换任务避免系统陷入死锁，保证系统任务完成率。

(3) 武器作战单元WA无法独立完成任务。随着防空作战资源的消耗，原本有能力执行合约的WA由于不再满足发射条件而无法进行独立作战，这时可由该WA充当招标者重新对任务进行公开招标，通过与其他WA进行协商招标请求与其进行协同作战。

3.6 策略流程

本文对CNP的招投标策略、中标策略以及签约策略进行设计改进，结合防空WTA问题得出基于改进CNP的防空WTA策略。具体策略流程如图3所示。

由以上工作流程可以看出，改进的WTA分配策略有以下特点：

(1) 在招标阶段引入黄页服务的手段，通过查询黄页目录可以减少防空作战网络体系中不必要的通信负载，大大降低CA计算量。

(2) 在选择中标者阶段，采用多指标综合评价的方法对投标者进行整体作战能力的评估，避免由于单一指标评价带来的决策失误。

(3) 在合同签约阶段，设计双向可解约的风险合同具有一定程度的容错能力，可以避免死锁现象带来的防空间隙，增强系统的协同性。

4 仿真实验

为验证本文提出策略的有效性，采用多主体建模仿真平台NetLogo，设计基于改进CNP的防空WTA模型并对其进行仿真实验。为方便开展仿真实验，并根据前文的假设，这里对模型进行简化处理。

假设防空作战在正常的气象条件下发生，目标分配期间不考虑地形环境以及电磁干扰等外界影响，在一个长300 km，宽300 km的仿真区域内，存在1个固定要地K位于仿真区域中心，整个防空作战体系主要由1个区域防空指挥中心CA(位于仿真区域中心)和3个防空武器作战平台PMA组成，每个武器平台PMA下属4个武器作战单元WA。其中区域指控中心CA的警戒范围包括整个仿真区域，各作战武器单元探测范围为边长150 km的矩形区域，整个防空体系里各Agent个体以链相连接，以此保证各智能体之间的信息传递以及任务的正常执行。设定3个武器作战平台PMA的初始能力价值分别为4.5，5，5.5，评标的时间约束、作战能力及作战代价的权重系数分别设为0.1，0.5，0.4。整个防空作战区域内随机产生n个威胁等级相同的敌方目标，并设置来袭目标的威胁度大小为0.5，能力价值设置为5。整个防空作战区域随机产生的n个目标，不予考虑自身电磁干扰特性，攻防作战在正常条件下进行，因此，这里设置防空武器作战单元被目标攻击的平均概率为0.3，各平台内部的武器作战单元对来袭目标的平均杀伤概率为0.65。

仿真开始运行时，系统随机生成n个目标，CA感知外界目标存在，系统中各武器作战单元WA的状态信息进行目录注册，并统一由CA进行管理。当敌方目标进入到矩形探测范围之内，由战术单位决策中心CA开始执行策略，各火力单元PMA组网协同完成目标分配。

由NetLogo所构建的WTA模型如图4所示。

这里以n=10，m=12进行作战仿真实验，研究防空作战整体效能在2种合同网策略下的变化情况。图5为在CNP和改进CNP策略下系统效能随时间变化的曲线。

由图5可以得出，与传统CNP 相比，改进CNP策略下的系统整体效能较优，主要是因为改进CNP中引进多指标的评标策略和风险合同机制，在CA筛选武器单元的过程中对其进行综合能力评估而不是单一的局部评估，加上引入风险合同机制可以使得WA根据战场态势决定是否改签，其中每个转折处代表一次合同签订，WA之间通过协商进行协同作战从而减少局部最优现象。

图3 基于改进CNP的防空WTA策略流程Fig.3 Process of WTA strategy based on improved CNP

图4 仿真实验界面示意图Fig.4 Sketch map of simulation interface strategies

图5 2种策略下系统整体效能比较Fig.5 Comparison of system efficiency between two strategies

这里以n=11，m=12为例进行100次仿真实验，研究2种策略下任务完成时间的变化情况，经过多次仿真得出如图6所示的实验结果。

图6 2种策略下任务完成时间比较Fig.6 Comparison of task completion time between two strategies

由图6可以看出基于改进CNP的WTA策略比基于CNP的WTA策略完成所有作战任务耗时更少。这主要是因为改进策略里引进黄页服务，相较于传统CNP广播式的招标方式更能够迅速地找到合适的招标对象和协同单元，因此更有利于提高武器作战反应速度，减少不必要的计算时间。

这里利用NetLogo的行为空间实验工具对目标数为5～12的情况分别进行100次仿真实验，研究作战单元之间协同次数随目标数量变化的情况，经过多次仿真得到如图7所示的实验结果。

图7 2种策略下作战单元协同次数比较Fig.7 Comparison of cooperative frequency between two strategies

由图7可知，总体上改进CNP策略比传统CNP策略作战单元之间的协同次数要高，当n<8时2种策略下的协同次数基本呈上升趋势，但是当n>8时，CNP策略下的协同次数出现下降趋势，而改进CNP策略下的协同次数依旧保持上升。主要原因是在CNP策略下随着目标数量的增加，作战单元的目标分配逐渐趋于饱和，单一的合同使得作战单元之间的协同性减弱；而在改进CNP策略下引进多类型的合同可以使得作战单元之间进行灵活的协同交互，作战单元在目标分配趋于饱和时，通过黄页目录查询可以迅速找到合适的作战单元签订风险合同来执行协同作战。

由图5，7可以看出，作战单元之间的协同性一定程度上决定系统整体效能的变化，加强作战单元之间的协同能力具有提高系统整体作战效能的潜力。

上面的实验均是在防空作战单元数量和空袭目标数量固定的静态条件下进行的，虽然可以体现策略的协同性，但是对于策略的动态适应性还未进行研究分析。这里考虑作战单元由于故障退出作战的情况，对所构建防空作战WTA模型在静态和动态分配情况下的系统效能变化情况进行研究。假设系统在目标分配之初n=10，m=12，保持来袭目标数量和威胁度大小不变，初始作战平台单元能力不变。系统中的武器作战单元执行策略进行协同作战，在系统进行目标分配过程中，随机选取1个武器单元退出系统，2种策略在动态调整前后系统效能的仿真结果如图8，9所示。

图8 静态目标分配下系统效能Fig.8 Sketch map of system efficiency under SWTA

图9 动态目标分配下系统效能Fig.9 Sketch map of system efficiency under DWTA

结合图 8 静态目标分配下系统效能和图 9 动态目标分配下系统效能可以看出，一方面无论是在静态或者动态目标分配情况下，本文所提改进CNP策略的系统效能明显要高于传统CNP策略的系统效能；另一方面也可以看出，改进CNP策略下的系统效能相较于动态调整前系统效能基本没有发生变化，而传统CNP策略下系统效能相较于动态调整前来说，系统的效能下降幅度较大，远低于调整前的系统平均效能。由此可知，本文所提目标分配策略对于动态随机的作战情况具有良好的适应性。

5 结束语

现代防空作战充满不确定性，目标分配问题随着时间的推移呈现动态复杂性，需要智能自动化的决策方法用于解决。针对防空作战的特点，本文利用多智能体系统的自主性和适应性，结合CNP的分布协同特性建立基于改进CNP的防空WTA体系结构，提出改进CNP的WTA策略，最后利用NetLogo平台验证了该策略的有效性。下一步将考虑武器单元的动态进入、武器单元的自私性以及任务的紧迫程度，通过分析这些不定因素对策略进行动态调整，从而更好地为防空作战辅助决策提供服务。

[1] 刘传波，邱志明，吴玲，等.动态武器目标分配问题的研究现状与展望[J].电光与控制，2010，17(11)：43-48. LIU Chuan- bo，QIU Zhi- ming，WU Ling，et al.Review on Current Status and Prospect of Researches on Dynamic Weapon Target Assignment[J].Electronics Optics & Control，2010，17(11)：43-48.

[2] 于连飞，刘进，张维明，等.武器-目标分配问题算法研究综述[J].数学的实践与认识，2016，46(2)：26-32. YU Lian- fei，LIU jin，ZHANG Wei- ming，et al.Review of Weapon- Target Assignment Problem Algorithms[J].Mathematics in Practice and Theory，2016，46(2)：26-32.

[3] 刘刚，王瑛，张发，等.合同网协议协商机制收敛性与收敛速率分析[J].控制与决策，2014，29(6)：1027-1034. LIU Gang，WANG Ying，ZHANG Fa，et al.Convergence and Convergent Rate Analysis of Contract Net Protocol Negotiation Mechanism[J].Control and Decision，2014，29(6)：1027-1034.

[4] 赵良辉，熊作贞.基于R学习的合同网实时调度模型[J].计算机工程与应用，2014，50(10)：221-237. ZHAO Liang- hui，XIONG Zuo- zhen.Real- Time Contract- Net- Protocol Scheduling Model Based on R- Learning[J].Computer Engineering and Application，2014，50(10)：221-237.

[5] 唐苏妍，梅珊，朱一凡，等.基于扩展合同网协议的分布式武器目标分配方法[J].系统工程与电子技术，2011，33(3)：568-574. TANG Su- yan，MEI Shan，ZHU Yi- fan，et al.Distributed Weapon Target Assignment Algorithm Based on Extended Contract Net Protocol[J].Systems Engineering and Electronics，2011，33(3)：568-574.

[6] 杨颖，武健，魏鹏.基于多智能体和合同网的巡航导弹自主任务分配[J].战术导弹技术，2014(1)：63-66. YANG Ying，WU Jian，WEI Peng.Autonomous Task Assignment of Cruise Missile Based on Multi- Agent and CNP[J].Tactical Missile Technology，2014(1)：63-66.

[7] 李明，刘玮，张彦.基于改进合同网协议的多Agent动态任务分配[J].山东大学学报：工学版，2016，46(2)：51-63. LI Ming，LIU Wei，ZHANG Yan.Multi- Agent Dynamic Task Allocation Based on Improved Contract Net Protocol[J].Journal of Shandong University:Engineering Science ed，2016，46(2)：51-63.

[8] 杨萍，刘颖，裴莹.改进合同网协议的Agent动态任务分配[J].火力与指挥控制，2011，36(10)：77-80. YANG Ping，LIU Ying，PEI Ying.Agent Dynamic Task Allocation Based on Improved Contract Net Protocol[J].Fire Control & Command Control，2011，36(10)：77-80.

[9] HSIEH F，CHIANG C.Workflow Planning in Holonic Manufacturing Systems with Extended Contract Net Protocol[C]∥Proc.of Industrial，Engineering and Other Applications of Applied Intelligent Systems，2009：701-710.

[10] KENSLER J A，AGAH A.Neural Networks- Based Adaptive Bidding with the Contract Net Protocol in Multi- Robot Systems[J].Applied Intelligence，2009，31(3)：347-362.

[11] 陈华东，王航宇，王树宗，等.基于合同机制的协同作战分布式目标分配研究[J].系统仿真学报，2009，21(16)：5116-5119. CHEN Hua- dong，WANG Hang- yu，WANG Shu- zong，et al.Distributed Target Assignment Based on Contract Mechanism in Corporative Engagement[J].Journal of System Simulation，2009，21(16)：5116-5119.

[12] SMITH R G.The Contract Net Protocol：High- Level Communication and Control in a Distributed Problem Solver[J].IEEE Trans on Computers，1980，29(12)：1140-1143.

[13] 李昌平.基于黑板结构的多智能体系统实现方法的研究[D].沈阳：东北大学，2011. LI Chang- ping.Research on the Realization Method of MAS Based on the Blackboard Architecture[D].Shenyang：Northeastern University，2011.

[14] 郝会成，姜维，李一军，等.基于Multi- Agent敏捷卫星动态任务规划问题[J].国防科技大学学报，2013，35(1)：53-59. HAO Hui- cheng，JIANG Wei，LI Yi- jun，et al.Research on Agile Satellite Dynamic Mission Planning Based on Multi- Agent[J].Journal of National University of Defense Technology，2013，35(1)：53-59.

[15] 曹佳.基于多Agent的合同网改进方案设计与实现[D].苏州：苏州大学，2012. CAO Jia.Design and Implementation of Improvement Scheme for Contract Network Based on Multi- Agent[D].Suzhou：Suzhou University，2012.

[16] 陈华东，刘忠，李云凡，等.黄页服务的合同网在编队武器目标分配中的应用[J].火力与指挥控制，2013，38(7)：103-106. CHEN Hua- dong，LIU Zhong，LI Yun- fan，et al.Application of Contract Net Protocol Based on Yellow Pages Service on Weapon Target Assignment of the Fleet[J].Fire Control & Command Control，2013，38(7)：103-106.

Application of Improved Contract Net Protocol on Weapon Target Assignment of Air Defense Combat

GUO Zhi- jieb，MI Yu- lina，XIAO Yanga，JIANG Wen- zhic，HE Lin- boa

(Naval Aeronautical and Astronautical University，a.Graduate Students’ Brigade；b.Department of Training； c.Department of Ordnance Science & Technology，Shandong Yantai 264001，China)

Due to the cooperativity and the dynamic in air defense operations, the concept of multiple agent systems is introduced to describe weapon target assignment (WTA)， and the architecture of WTA based on improved contract net protocol (CNP) is established. The strategies of announcement, biding and bid evaluation are designed, and WTA is realized by applying of the strategy based on improved CNP. A comparison was made between CNP and improved CNP based on WTA strategy through an operational scenario. Simulation results show that the proposed strategy is more reasonable and efficient.

weapon target assignment； agent； multiple agent systems； antiaircraft defense system； contract net protocol； NetLogo

2016-08-30；

2016-11-18 作者简介：郭智杰(1992-)，男，回族，福建莆田人。硕士生，主要研究方向为管理科学与工程。

10.3969/j.issn.1009- 086x.2017.04.017

E926；TN915.04

A

1009- 086X(2017)- 04- 0104- 08

通信地址：361021 福建省厦门市集美区西柯镇禹州大学城小区 E- mail：gzj_549@163.com