基于合同网的分布式动态任务分配算法

肖玉杰，李 杰，刘 方

(1.海军工程大学 电子工程学院，湖北 武汉430033;2.海军工程大学 动力工程学院，湖北 武汉430033;3.海军工程大学 兵器系，湖北 武汉430033)

0 引 言

信息化技术在军事领域的应用，使得动态任务分配问题成为提高协同作战能力的关键［1］。一方面，战场复杂多变，指挥决策系统需要对新产生的作战任务动态分配;另一方面，各作战平台内部各节点作战能力可能会发生变化，需要对未完成的任务快速有效的再分配。这就要求指挥决策系统选择合理的分配策略，进行任务动态分配。故研究动态任务分配问题具有重要意义。

目前，用于实现多智能体系统(Multi- Agent System，MAS)智能控制的算法主要包括合同网模型、黑板模型、马尔科夫决策过程模型、节点规划方法、集合覆盖理论和市场协议方法等［2］，其中合同网在动态任务分配方面取得了较好效果。合同网模型(Contract Net Protocol，CNP)是Smith R.G.和Davis R.提出的关于人物和资源分配的经典协调策略。其基本思想是节点之间通过“招标—投标—中标”这一市场机制进行任务分配，系统以较低代价、较高质量完成委托和承揽构成的合同关系。

合同网模型现已广泛应用到机器人、编队协同作战、卫星和多UCAV［1-6］等领域。文献［7］指出了任务分配的目标是代价最小，效能最大，并限制了允许分配的最大任务数以减小计算的复杂度。文献［8］提出了利用包含价格和时间的代价时间Petri 网来模拟合同网的协商过程，完善了合同网的运行机制。文献［9-10］在传统合同网协议的基础上引入信任度和惩罚机制，来限制发送标书的范围和控制评价标书的数量来减少通信量。文献［11］引入各种心智参数来对招标范围进行限制，并设置缓冲池来限制投标者接收标书的数目，提出了一种自适应的投标策略，减少了合同网协议时的通信量。

本文在以上基础上，针对传统合同网的不足，有针对性地总结了基于联盟、公告板及优先级的3 种合同网改进模型，解决了合同网在任务发布阶段和协商阶段的信息阻塞以及承诺失败等问题，减少了系统的通信量，满足控制系统实时性等要求，提高了协商效率，扩展了合同网模型的使用范围，有助于MAS 在复杂大系统中的应用。最后介绍2 种常用的MAS 软件仿真平台-JADE和Repast 仿真平台。

1 基本合同网任务分配算法

1.1 合同网基本思想

图1所示为合同网的工程应用原理图。在实际应用中，由于单个Agent 无法实现对现有任务的求解，需要多个节点之间的协作。其基本思想是“任务的解耦—任务的发布—任务的协商—任务的耦合”，最终得到复杂任务的控制决策结果，以较低消耗满足系统在特定情况下的运行需求。

1.2 合同网运行机制

在合同网模型中，任务Agent 负责任务的解耦、发布和任务耦合，资源Agent 负责子任务的协商，保证任务的正常运行。其中，资源Agent 之间满足对等关系，既是子任务的管理者，又是子任务的接收者，通过直接或间接的交互通信最终实现复杂任务的求解［12］。合同网的交互协商过程如图2所示。

图2 合同网的交互协商流程图Fig.2 The flow chart of interaction and cooperation in CNP

1)任务Agent 发出任务信息CFP，将自己的任务或不能完成的任务用招标的信息向资源Agent 发布，等待资源Agent的反应信息，包括“投标”、“拒绝”和“不明”，直至到任务信息截止时间。

2)资源Agent 根据任务要求和自己的状态进行投标，此时，资源Agent 等待任务Agent的反应时间，包括“拒绝”和“请求”，同时资源Agent 可以向其他任务Agent 发送任务的请求信息;

3)任务Agent 对任务的请求决策处理，选择能够满足任务需求的最佳资源Agent，并发送任务执行邀请。参与者在接收到执行邀请后，如果向任务Agent 发送接收任务邀请的信息，则任务Agent 发出任务执行“接受”确认信息，向其他发送任务请求的资源Agent 发送“拒绝”信息。

4)执行任务的资源Agent 向任务Agent 提交任务的反馈信息，实现任务Agent 对任务的监督和管理。

1.3 任务分配基本描述

多Agent 任务分配问题是指各Agent 分布式的自主执行任务，由于任务类型的不同，各个Agent的能力不同，当发现新的任务时，各Agent 能够根据当前态势快速、合理实现任务的动态分配［3］。

下面以多无人水下潜航器 (Unmanned Underwater Vehicle，UUV)为研究对象，构建多UUV 协同作战的动态任务分配模型。

任务效能定义［13］:AgentVi执行任务Tj的效能Ui(Tj)为完成任务的收益Rewardi(Tj)减去相应付出的代价Costi(Tj):

因为Rewardi(Tj)与Costi(Tj)具有不同的量纲，所以需要先分别对其进行归一化处理，统一到相同的量纲后再进行相减。

设Vi执行对某目标的确认任务Tj，Vi对该类型目标的确认概率为(Tj)，Tj的任务价值为Value(Tj)，则Vi执行Tj的收益为:

设Vi执行对某目标的攻击任务Tk，Vi对该类型目标的杀伤概率为(Tj)，则Vi执行Tk的收益为:

设Vi执行对某目标的毁伤评估任务T1，Vi对该类型目标的毁伤评估概率为(Tl)，则Vi执行T1的收益为:

得到任务效能的定义后，任务分配的目标可以描述为:

目标 3:使 UUV 完成任务所需的时间maxi∈VTimei(Si)为最小，其中Timei(Si)为Vi完成任务集Si的时间;

2 改进合同网任务分配算法

2.1 传统合同网的不足

传统的合同网模型可以成功解决一个任务在多个Agent 之间的分配问题，特别适合于单任务、单中标者、单回合的招标场景。MAS 利用合同网方法进行协商，虽可以实现任务分配，但随着任务的复杂和系统环境的变化，表现出以下不足［14-15］:

1)任务发布阶段，信息通信量大，资源消耗大

在传统的合同网中，任务Agent 采用广播的方式发送任务信息，获取任务信息的任何Agent 都可以对任务信息作出“投标”响应，而自身不需要支付额外费用或作出某种承诺。这种不对招标范围进行限制的运作机制，不仅浪费标书，造成系统通信的频繁，甚至造成系统堵塞，加大任务Agent的决策负担。

2)任务协商阶段，协商次数多、计算量大，效率低

任务Agent 在任务分配和协商过程中，需要多次交互通信，并通过匹配实现系统的智能决策。这一过程，任务Agent和资源Agent 之间能力的获取加大了系统的通信量，导致系统的相应时间变慢，协商成功率大大降低。

3)任务的耦合阶段，容易出现流标现象

管理者在接收到所有投标后，经过评估，未发现合适的Agent 或者各个投标者在规定的时限内不能完成任务，则此次任务出现流标现象。

目前，对于合同网模型的改进从任务解耦阶段到任务的耦合阶段，最终的落脚点都是能否实现系统的智能决策和控制。合同网模型对系统智能控制的能力主要体现在系统之间的交互协商通信量和通信时间。

2.2 合同网改进模型

2.2.1 基于Agent 联盟的改进合同网

在基于Agent 联盟的合同网模型中，Agents 之间依据能力互补性、合作信任度和低通信代价的原则形成Agent 联盟，不同联盟之间存在竞争，联盟内部即存在竞争又存在协作。这一改进模型是MAS竞争性和合作性的有效结合，充分发挥单个Agent问题求解能力，提高系统效率。基于Agent 联盟的合同网模型以Agent 为单位进行任务的协商，如图3所示。任务Agent 中有管理模块和决策模块，管理模块实现任务在Agent 联盟之间的交互协商，决策模块依据最优原则实现任务在Agent 联盟之间的分配，在管理模块的监督和管理下实现系统智能决策;联盟内通信能力较强的Agent 担任盟主，负责联盟内部任务的分配、协商和监督执行。

图3 基于Agent 联盟的合同网模型框图Fig.3 The CNP based on Agent alliance

基于Agent 联盟的合同网模型具有以下优点:

1)Agent 联盟的形成，降低了网络的通信量，方便任务Agent 对任务的管理和分配;

2)这一改进合同网模型合理的整合了Agents 之间的合作性和自利性，使任务完成更加合理、高效。

2.2.2 基于公告板模型的改进合同网

黑板模型是一种平行信息共享数据结构，它能解决分布式人工智能中多个计算实体的协作问题，实现异构Agent 集成，为多Agent 提供通信支持。图4 为黑板模型结构图［16-17］:①黑板用来储存数据、传递信息和处理方法的数据库，是系统中全局工作区。黑板根据处理知识领域的不同由上而下划分为多个信息处理层次，对各信息处理层次进行统一管理;②控制单元是黑板模型的核心，它负责以下工作:一是对Agent 激活和工作的分配;二是对黑板上信息的更新;三是负责通知Agent 读取黑板上的消息;③Agent 是黑板模型中被服务的主体，它们需要在控制单元中进行注册，才能在控制单元的协调下与黑板进行信息交互，完成信息和知识的共享。

针对黑板模型本身的局限性，提出了基于公告板模型的合同网改进方案，公告板作为控制系统中Agent 协商交互的基础，是系统的信息中心。因此，公告板的创建方便了信息的调用，有效提高了合同网的性能。如图5所示为基于公告板的合同网改进模型工作流程。该模型通过公告板的协助实现任务的分布、协商和监督，具有以下优点:

1)管理者发送任务消息，由公告板进行任务匹配，并以公告板的反馈信息为依据，通过与部分资源Agent 交互和协商，实现对被控系统的管理和控制。因此，减少管理者与资源Agent 之间的交互和协商，提高任务的协商效率，减少控制系统的响应时间;

2)公告板为资源Agent 提高了统一的信息格式，解决了黑板模型中Agent信息格式异构的难题，为Agent信息注册和任务匹配等提供了方便。

2.2.3 基于优先级的改进合同网

为了方便紧急任务条件和故障状态下的智能控制，提出了基于优先级的合同网模型。在该模型中，定义了任务的优先级，优先实现优先级相对高的任务，最终实现多任务发布、协商和执行;以不同的优先级定义资源Agent 之间的主备用和并行关系，实现突发情况、故障状态下主备用的切换和满足不同条件下Agents的协同工作。如图6所示为基于优先级的合同网模型的工作流程。

图5 基于公告板的合同网模型框图Fig.5 The CNP based on bulletin board

图6 基于优先级的合同网模型框图Fig.6 The priority-based CNP

任务Agent 在虚拟工作区以优先级为依据，得到系统的任务序列;资源Agent 以实物模型为基础，得到资源Agent的并行关系。

依据优先级的高低，由管理者实现任务的发布、协商，得到资源Agent的响应。

结合协商结果和虚拟工作区上的资源Agent的并行关系，得出系统仿真结果。

3 合同网软件仿真平台

3.1 JADE 仿真平台

JADE (Java Agent Development Framework)是一个完全由Java 语言编写的多Agent 开发框架，遵循FIPA (Foundation Intelligent Physical Agents)规范，提供基本的命名服务、黄页服务、通信机制等，能够与多种软件集成，兼容性较强，极大简化了多Agent 系统在开发过程中的各个环节。

在JADE 平台中，1个平台可以有多个容器，1个容器可容纳多个Agent。容器可以位于不同的主机上，1个JADE 平台有且仅有1个主容器。每个Agent 在JADE 平台中都有唯一的名字，Agents 之间在通信协议下，通过名字标识实现不同平台之间的信息交互。

为了便于多Agent 系统的开发，JADE 提供了2个重要组成部分:遵循FIPA 规范的Agent 开发平台和开发Agent的软件包。前者定义了Agent 平台提供的若干服务:其中Agent 管理系统(MAS)、黄页服务(DF)和消息传递服务(MTS)为3 种最基本的服务。这一开发平台可以实现多平台的集成，方便多Agent控制系统的开发;后者为程序设计者提供完备的功能接口和规范的抽象性界面。在JADE 平台中，单个Agent 满足基于FIPA 规范的Agent 管理参考模型，提供最基本的服务，通过消息传输系统实现不同Agent 之间的信息交互。

JADE 智能体最重要的特征之一就是这一平台具备通信能力［18-19］。Agents 之间的通信模式是异步消息传递。在JADE 平台中，每个Agent 都有一个消息队列，如果其他Agents 需要与其通信时，JADE就把相应的消息投递到其队列中。

JADE 在处理消息发送时，会根据不同情形选择最合适的信息传输方法:

如果消息发送者与接收者在同一容器中时，用Java 对象代替ACL 消息，通过运行线程发送给指定Agent，不存在任何消息传输;

如果消息发送者与接收者位于同一JADE 平台，但不在同一容器中时，ACL 消息通过Java RMI 发送。对于接收者而言，Agent 也只是接收到1个Java 对象;

如果消息发送者与接收者不在同一平台时，JADE 将根据FIPA 标准，利用HOP 协议和OMG IDL界面来进行消息发送。消息发送者将ACL 消息对象翻译为字符串，并把HOP 协议视为一个中间协议来执行远程调用;消息接收者收到一个相应的HOP 序列，并生成一个Java的String 对象，随后该对象被解析成一个ACL 消息对象，最终该消息对象通过Java 事件或RMI 调用发送给指定的Agent。

总之，JADE 平台能够实时维护Agent 地址列表，以便有效提供Agent 之间的消息传输，它使用标准的ACC Agent 向外界提供唯一接口，可远程调用。JADE 这种多方式通信机制大大降低了系统通信的开销。

3.2 Repast 仿真平台

Repast (Recursive Porous Agent Simulation Toolkit)是芝加哥大学社会科学计算研究中心研制的Multi-Agent 建模工具。它提供了一系列用以生成、运行、显示和收集数据的类库，并能对运行中的模型进行“快照”，记录某一时刻模型的当前状态，还可以生成模型运行过程中状态动态演化的视频资料。Repast 从Swarm 中借鉴了不少设计结构和方法，所以常常称Repast 为类Swarm的架构。

Repast 共有近 130个类，封装在分析库Analysis、引擎库Engine、博弈库Games、因形用户界面库GUI、空间库Space、Util 类库6个库中。Repast 模型有批处理方式和非批处理方式(也称图形交互方式)2 种运行方式。批处理运行需要一个特殊格式的参数文件，在这个文件中要详细给出模型各个参数的起始值、终止值和增量值，以及运行的次数等;有了参数文件后，模型就可无须用户干预连续重复运行。一个非批处理的运行则需要通过图形用户界面来交互启动和终止模型，用户可以通过图形界面来设定初始参数值，可以在运行过程中图形化监控主体和模型的各种状态。

由于Swarm 对建模者来说还是有些过于复杂，Repast 项目提供一系列简化Swarm 模型开发的Java类库。设计者通过让模拟软件的底层结构具备抽象性、可扩展性以及“良好”的表现能力等优点。

4 结 语

本文简述了MAS 协作环境下的任务分配模型。描述了合同网的基本思想和运行机制，针对合同网本身的缺陷，给出了基于联盟、基于公告板、基于优先级的3 种合同网改进模型，改进模型解决了合同网在任务发布阶段和协商阶段的信息阻塞和承诺失败等问题，减少了系统的通信量，满足控制系统实时性要求，提高了协商效率，扩展了合同网模型的使用范围，有助于MAS 在复杂、大系统中的应用。最后介绍了2 种常用的MAS 软件仿真平台—JADE和Repast 仿真平台。

［1］孙庆声，缪旭东，陈行军.一种基于扩展合同网视为编队动态任务分配模型［J］.兵工自动化，2009，28(8):50-52.

［2］张阳，张睿，霍德才.遗传进化算法在多Agent 协作通信中的应用［J］.信息化，2010(26):74-75.

［3］郝莉莉，顾浩，杨慧珍，等.多机器人系统合同网任务分配方法的改进与仿真［C］//2012年水下复杂战场环境目标识别与对抗及仿真技术学术论文集，2012.

［4］陈华东，王航宇，王树宗，等.基于合同网的协同作战分布式目标分配研究［J］.系统仿真学报，2009，21(16):5116-5119.

［5］高黎，沙基昌.基于合同网的分布式威胁系统任务优化分配研究［J］.宇航学报，2007，28(2):352-357.

［6］龙涛，陈岩，沈林成.基于合同网机制的多UCAV 分布式协同任务控制［J］.航空学报，2007，28(2):352-357.

［7］FANG Tang，PARKER L E.A complete methodology for generating multi-robot task solutions using ASyMTRe-D and market-based task alloocation ［ C ］//2007IEEE International Conference on Robotics and Automation Roma，Italy，2007:3351-3358.

［8］张广胜，蒋昌俊，沙静，等.基于时间Petri 网的合同网模型研究［J］.系统仿真学报，2008，20(20):5438-5441.

［9］李彤，陈利，李功丽.面向对象Petri 网合同网协议模型的一种改进方案［J］.计算机应用与软件，2008，25(10):113-115.

［10］AARTI S，DIMPLE J.Introducing trust establishment protocol in contract NET protocol［C］//2010 International Conference on Advances in Computer Engineering，2010:59-63.

［11］高飞燕.基于扩展合同网的多Agent 任务分配机制的研究［D］.大连:大连海事大学，2009.

［12］刘海龙，吴铁军.基于合同网的多Agent 任务分配分布式优化算法［J］.浙江大学学报，2001，35(2):550-554.

［13］龙涛，沈林成.多UCAV 协同任务控制中分布式任务分配与任务协调技术研究［D］.长沙:国防科技大学，2006.

［14］杨萍，刘颖.改进合同网协议的Agent 动态任务分配［J］.火力与指挥控制，2011，36(10):77-80.

［15］宋海刚，张尧学，陈松乔.FIPA 合同网协议的一种改进方案［J］.华中科技大学学报，2004，32(7):31-33.

［16］蒋丽娟，刘卫国.基于层次黑板模型的多Agent 系统研究［J］.计算机系统应用，2008(5):10-13.

［17］孙隅隅，黄光球.基于黑板模型的多Agent 智能决策支持系统的研究［J］.嵌入式与单片机，2007，20(25):85-88.

［18］李晓瑜，余谦.一种多Agent 系统通信框架［J］.重庆理工大学学报，2010，24(5):100-103.

［19］赵辉，谭天晓，赵宗涛.基于MAS的作战指挥模型的通信技术实现［J］.微电子学与计算机，2007，24(11):107-109.