基于服务的异质作战实体协同优化研究

宦 婧，周伟祝，陈 健，孙 媛

（海军航空工程学院 科研部，山东 烟台264001）

0 引 言

目前，在基于Agent的计算机生成兵力 （computer generate force，CGF）作战仿真中，作战实体也就是CGF开发时缺乏统一的规范，导致异质CGF的存在，使得CGF实体间难以实现信息的共享和交互，如果无法保证异质CGF协同分配的连贯性和高效性，仿真系统性能将会出现震荡，因此如何实现异质CGF交互并高效地实现任务分配是CGF完成复杂任务的关键，也是CGF协同的研究热点［1］。

目前，协同任务分配的研究方面，基于合同网的任务分配方法得到了广泛的研究与应用，R.Zlot等人［2－3］采用面向任务树的竞价拍卖合同网法分配一类松耦合子任务取得了较好的效果，裘杭萍［4］等人从投标Agent的负载、能力和信任度3个方面进行综合考虑和权衡，提出了一种基于多属性评价中标策略的动态任务分配算法，对传统的合同网协议进行了改进。但是，上述工作或多或少的存在以下几点缺陷：未考虑异质实体间的交互问题；较少考虑系统通信开销要求；在确定分配方案的过程中，忽略了CGF间的约束关系，从而导致问题求解难以达到全局最优。

本文旨在提高异质CGF平台互操作和交互能力的基础上，使作战实体高效地完成任务分配从而协同完成上级作战目标。Web服务技术可以较好地解决异质应用之间互操作的问题，已成为系统间功能发布和共享的重要方式［5］。本文将Web服务的思想引入到多CGF任务分配中，提出了一种基于服务的协同任务分配模型，以解决异质CGF交互过程中的兼容性问题，同时采用基于能力效用函数的任务分配策略，建立效用函数模型优化任务分配质量和效率。

1 基于服务的协同任务分配模型

作战仿真组织内部，被分解的子任务在作战仿真实体之间分配，接受任务的所有作战实体组成团队，通过内部协同完成任务。本文将作战实体按作战角色分为指挥实体和成员实体，按仿真角色分为资源需求型实体 （Req＿CGF）和资源提供型实体 （Sup＿CGF）。指挥实体负责任务的分配和管理，有协作需求的指挥实体的仿真角色为Req＿CGF。因此，任务分配是指Req＿CGF通过一定的方式将任务分配给愿意并有能力协作完成子任务的Sup＿CGF，将其转化为成员实体，并组成团队共同完成使命任务的过程。

合同网络模型［6］下的任务分配流程是：Req＿CGF通过广播声明任务，系统中的Sup＿CGF根据自身能力向任务管理员投标，Req＿CGF在标书截至期限内，选择满意的投标者来完成任务。由于采用了广播模式来声明任务，因此该模型对网络负载的要求较高，且没有考虑异质实体间的交互通信问题。为改善原有的任务分配模型，本文引入服务机制，建立基于服务的CGF任务分配模型，各CGF将其所能提供的功能封装为服务，向控制中心中的服务注册中心发布服务，CGF之间的协同交互均以服务注册中心为媒介的，该方式一方面解决了异质CGF通信交互的问题，另一方面，由于网络传递的并非实际的功能，而是经过封装的服务，所需要传递的数据量大大减少，因此能有效的减轻网络负载。

1.1 基于服务的多CGF系统

传统的仿真服务主要指为仿真运行提供服务的仿真应用系统或组件，与传统的仿真服务不同，本文所提到的仿真服务是一种具有可持久状态，能够通过标准协议进行描述、发布和访问的Web服务［5］，是把原有的仿真组件封装为具有独立行为逻辑或计算功能的仿真组件。

基于服务的多CGF系统结构如图1所示，系统通过发布服务、查询、返回服务列表、绑定控制成员的方式，满足组织内成员实时交互并实现对组织内各CGF运行状况的控制，主要包括两部分：融合了服务的CGF主体模型和基于服务的控制中心。融合了服务的CGF主体模型是指，在传统的基于Agent的CGF模型基础上增加服务层，服务层可以根据需要将CGF功能封装为服务向外发布，并接受来自其它CGF的服务请求，提供具体的服务，以此实现异质CGF主体间的交互；基于服务的控制中心是多CGF系统的控制单元，负责对系统中的CGF主体及其服务进行统一的控制和管理，提供系统内CGF之间交互的接口［7］，主要包括CGF注册中心、服务注册中心和本体。CGF注册中心为CGF提供运行时的管理服务，包括为CGF提供注册和注销服务，同时也为CGF提供角色的注册和注销服务；服务注册中心需要提供仿真服务管理服务，用于维护一个CGF仿真服务注册表，它主要负责对已经注册的CGF主体所提供的服务进行注册管理；本体是对CGF系统的描述，主要包括：①仿真服务管理中心所提供的服务，这些服务中的操作及说明；②CGF类，以及这些CGF类所提供服务的描述；③CGF类之间的联系、CGF类与所提供服务之间的关系、服务与操作之间的关系。

图1 基于服务的多CGF系统模型

1.2 基于服务的任务分配流程

基于服务机制建立的任务分配模型执行步骤如图2所示，详细描述如下。

步骤1 服务注册：所有参与仿真的CGF向控制中心

Service＝ ｛服务名称，服务ID，服务链接地址｝

步骤2 上级下达的使命任务后，作战实体 （Req＿CGF）产生协作需求，对分解后的子目标分别在组织中寻求协作成员，首先向服务注册中心请求查询服务，查询与的CGF注册中心注册CGF信息，已完成注册的CGF将其可以提供的功能资源打包成服务，上传到控制中心，并向服务注册中心注册服务信息，服务注册中心以服务列表的形式存储为以下格式，方便为其它CGF提供查询和调用。子目标相关的作战实体。

步骤3 服务注册中心将相关的服务列表返回给Req＿CGF；

步骤4 发布标书：Req＿CGF根据服务列表向各个能

图2 基于服务的协同任务分配流程

提供相应功能的Sup＿CGF以标书的形式发送请求资源／功能请求。

标书格式：标书＝ ｛ID，Manger，Description，Restriction，Grade，ExpireTime｝，其中ID为标书标识号；Manger为发起协作的CGF标识；Description为任务的具体描述，Restriction为任务的限制条件，如：时间要求，质量要求等；Grade为任务优先级，ExpireTime为投标截止时限。

步骤5 投标：收到资源请求的Sup＿CGF，向服务注册中心请求查询服务和能力评估服务，根据评估结果决策是否提供协作服务，并将决策结果以标书的形式返回给Req＿CGF；

步骤6 发放标书：Req＿CGF根据所有反馈信息，请求综合能力评估服务，根据得出的结果选择最终愿意合作的Sup＿CGF成为成员CGF，协调制定协作计划，形成团队。

1.3 基于效用函数的任务分配算法优化

上述基于服务的协同分配流程虽可以有效地实现异质CGF之间的交互并实现任务分配，但由于合同网络算法没有考虑作战实体之间的约束关系，因此最终的分配结果难以达到全局最优，为此，在上述分配流程的基础上，本文提出一种基于效用的任务分配全局优化算法，该算法建立了基于能力向量的CGF效用函数，结合遗传算法易于实现全局优化的特点对投标CGF进行全局规划，从而在一定程度上解决动态环境下全局分配优化问题。

1.3.1 基于能力向量的效用函数

作战仿真中，任务所要求的能力和CGF所能提供的能力随作战环境的变化而变化，各CGF对任务的适应程度也随之变化。本文引入效用函数来量化CGF对子任务的胜任程度，CGFfi相对子任务tj的效用函数uj（i）可以表示为当前任务需求能力 （Ctj）和CGF能力 （）的函数，表达式表示为［8］

式中：uj（i）——CGFfi对子任务tj的效用函数值，即CGFfi对子任务tj的胜任程度。Uj（Cfi，Ctj）——与子任务tj对应的效用函数。vij——投标情况，vij∈ ｛0，1｝，vij＝1表示CGFfi向子任务tj投标，反之则表示CGFfi未向子任务tj投标。

不同的子任务对CGF的要求不同，对应的效用函数也不同，即如tk≠tj，则Uk（·）≠Uj（·）。对于某一子任务tj而言，所有CGF对其的效用函数构成效用向量Uj，Uj＝［uj（1），uj（2），…，uj（i）］T。为了使uj（i）与uk（i）具有可加性，对向量Uj进行归一化处理

不失一般性，考虑m个CGF对n个子任务的投标情况，可得效用函数矩阵

式中uij＝珘uj（i），表明对同一个子任务而言，CGF对于子任务的执行能力随着效用函数值的增大而增强，也就是对子任务的胜任能力越强［9］。

任务T分解为n个子任务tk（k＝1，2，…，n），应用合同网络分配方法对m个CGF实体分配n个子任务，生成关于所有投标CGF的标书矩阵RT［10］，RT可表示为

元素rtij为bi对任务元tj进行投标的标书信息，rtij可表示为

其中：cj是表示任务tj的代码；uij表示bi完成任务tj的效能；gij＝1表示选择bi完成任务tj；规定任一任务仅能由一个CGF完成，即

以最大化任务完成效能为目标，建立如下任务分配目标函数

对应的 ｛θ1，θ2，…，θm｝即为任务分配方案。

1.3.2 基于遗传算法的任务分配优化

上文所述任务分配算法的复杂度随着子任务的数量以及参与任务的CGF实体数量的增加而剧增，为保证任务分配的时效性，通常的做法是随机选择若干可行解，在这些可行解中根据任务完成效能选择最优解作为任务分配方案。这种方法虽可以实现任务分配，但获得全局最优解的可能性较小，因此需对其进行有效地改进。遗传算法通过模仿生物进化过程优化全局方案［11］，具有简单通用的特性，很适合用于任务分配中对任务空间的搜索和优化。因此本文结合遗传算法，对合同网络任务分配方案进行优化，适应度函数选用基于能力向量的效用函数，算法具体执行步骤如下：

（1）生成标书矩阵。Sup＿CGF从所有发布的任务中选择能够执行的任务，计算出每个任务的执行时间和执行效用值；并对每一个投标CGF重复以上步骤，直至计算出每个投标CGF的执行时间及效用，以此形成标书矩阵RT。

（2）生成初始种群。从实现任务分解的T中依次读取子任务tj，并在标书矩阵中找出与tj对应的投标结果集RTj＝ ［rt1j，rt2j，…，rtmj］，从中随机提取某CGFfi的投标方案作为初始方案。对每一个子任务重复这一过程，直到它们都得到初始方案，这一方案就是种群中的个体。重复上述步骤则初始种群ρ（T）形成。

（3）计算个体适应度。依次提取ρ（T）中的个体，将其代入式 （5）中，计算个体适应度。依据此值运用赌轮选择法，从种群中选择（N表示种群中个体的数量）个个体对；令杂交概率为pc，变异概率为pm，首先，依据概率pc进行杂交操作产生N个个体；然后根据概率pm进行变异操作并产生新种群。

（4）任务分配方案确定，即提取最优分配方案。利用适应度函数评价最后一代种群，提取最优个体作为最终任务分配方案ρ（T′）。

（5）形成面向作战任务的CGF团队。根据步骤 （4）中确定的最优分配方案，Sup＿CGF将方案结果发布出去，所有受领任务的CGF形成面向任务T的CGF团队。

2 作战仿真验证

本文利用Mak仿真平台构建了一个简单的直升机协同反潜仿真实例，验证优化后协同任务分配模型的性能。

作战想定：某敌对势力在我海域进行非法侦察活动，我方兵力侦察到敌方潜艇的航迹，指挥调遣3架反潜直升机对这一海域进行反潜搜索，并进行海域划分和任务分配。反潜直升机在受领作战任务后迅速飞临指定空域，搜索到敌方潜艇后迅速锁定并通报上级指挥所，敌潜艇发现被锁定后进行规避，我方则继续跟踪并在情况允许范围内实施打击。仿真过程截图如图3所示。

图3 仿真过程截图

从初始状态到搜潜成功称为一个回合，任务分配优化模型的目的是通过优化模型使得每一回合中以尽可能少的时间实现任务分配，并达到全局最优分配方案。根据待搜索海域的大小及直升机性能将其划分为300个搜索块，分别运用文中方法和原先方法为3架反潜直升机分配任务，试验中遗传算法参数设置为：种群大小为300，进化次数为100次，交叉概率取0.7，变异概率取0.2。仿真实验共进行30次，仿真结果如图4，图5所示，本文以执行任务分配所需时间和完成作战任务所需时间为指标，验证模型优化程度。

仿真结果显示：从完成任务分配的时间上来看，与未经优化的任务分配模型相比，优化后的模型完成任务分配所需时间略有增加，增加幅度在5%左右，这主要是由于未经优化的算法在随机选定的部分解空间中寻求最优解，当设定的部分解空间规模较小时，耗时相对较少，而采用遗传算法进行优化，需要对整个解空间进行随机最优搜索，因此耗时增加；从搜潜效能上来看，采用优化后的模型所计算出的任务分配方案，搜潜成功率平均要提高50%左右，搜潜效能大大高于未经优化的算法。综合来看，采用遗传算法优化后的任务分配模型在基本相近的任务分配所需时间内，能有效提高任务分配方案的优劣程度，使得分配方案更逼近全局最优。

3 结束语

任务分配是作战仿真领域的核心问题，本文为解决异质CGF任务分配问题，将服务的思想引入到任务分配中，建立了基于服务的协同任务分配模型。该模型使得CGF的功能结构不再是影响任务分配的重要因素，对异质CGF系统具有较好的通用性；在此基础上，给出了基于效用函数的分配方案优化算法，算法充分考虑到环境因素对CGF能力、子任务要求能力的影响，采用遗传算法对分配方案进行了全局优化。仿真实验表明：基于遗传算法改进的合同网络任务分配模型可以有效地提高CGF仿真系统的作战效能，但是对于任务间相关的任务分配策略和对任务分配效果的评估还有待进一步的研究。

［1］LI Weixiang，ZHANG Guangming，LI Bangyi.Research on multi

attributes task allocation mechanism in MAS ［J］.Systems Engineering and Electronics，2009，31 （5）：1113－1116 （in Chinese）.［李为相，张广明，李帮义.一种多属性的MAS任务分配机制研究 ［J］.系统工程与电子技术，2009，31 （5）：1113－1116.］

［2］Zlot R，Stentz A.Market－based multi－robot coordination for complex tasks ［J］.International Journal of Robotics Research，2006，25 （1）：73－101.

［3］MB Dias，Zlot R.Market－based multirobot coordination：A survey and analysis ［C］／／Proc of IEEE，2006：1257－1270.

［4］QIU Hangping，QIN Yao，HU Rui，et al.Study on the task allocation based on improved contract net in multi－agent system ［J］.Computer Science，2012，39 （B6）：279－282 （in Chinese）. ［裘杭萍，覃垚，胡汭，等.多Agent系统中基于改进合同网模型的任务分配研究 ［J］.计算机科学，2012，39 （B6）：279－282.］

［5］WU Zebin，WU Huizhong，LI Weiqing.Run－time infrastructure of distributed simulation based on Web services ［J］.Computer Integrated Manufacturing Systems，2009，15 （10）：2064－2068 （in Chinese）.［吴泽彬，吴慧中，李蔚清.Web服务化的分布仿真运行支撑环境 ［J］.计算机集成制造系统，2009，15 （10）：2064－2068.］

［6］DING Zhiqin，LIU Yong，WANG Kai.Bidding－based optimization of task allocation in multi－Agent system ［J］.Journal of Computer Applications，2010，30 （7）：1907－1910 （in Chinese）.［丁芝琴，刘永，王凯.多Agent系统中基于招投标的任务分配优化 ［J］.计算机应用，2010，30 （7）：1907－1910.］

［7］YAO Xifan，LIAN Zhaotong，LI Yongxiang，et al.Serviceoriented architecture and integrated development environment for cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2012，18 （10）：2312－2322 （in Chinese）.［姚锡凡，练肇通，李永湘，等.面向云制造服务架构及集成开发环境 ［J］.计算机集成制造系统，2012，18 （10）：2312－2322.］

［8］HUAN Jing，ZHOU Weizhu，LI Jiying，et al.Utility based task allocation optimized for CGF collaboration ［J］.Science Technology and Engineering，2012，12 （28）：7421－7424 （in Chinese）. ［宦婧，周伟祝，李季颖，等.基于效用函数的CGF协同任务分配优化研究 ［J］.科学技术与工程，2012，12 （28）：7421－7424.］

［9］LI Hao，DAI Jinhai.Agent－based modeling and simulation supported system effectiveness analysis for complex systems［J］.Journal of System Simulation，2008，20 （15）：3911－3914（in Chinese）.［李昊，戴金海.基于Agent的建模与仿真支持下的复杂系统效能分析法 ［J］.系统仿真学报，2008，20 （15）：3911－3914.］

［10］ZHANG Yu，LI Fanzhang.Research on multi－agent dynamic task allocation algorithm and based on dynamic fuzzy set ［J］.Acta Electronica Sinica，2009，37 （11）：2552－2555 （in Chinese）.［张瑜，李凡长.基于DFS的多Agent动态任务分配算法研究 ［J］.电子学报，2009，37 （11）：2552－2555.］

［11］LI Shujuan，LI Yan，LIU Yong，et al.A GA－based NN approach for make span estimation ［J］.Applied Mathematics and Computation，2007，185 （2）：1003－1014.