多Agent合作：社会化的协作系统节点结构

多Agent系统可以看成由一群自主并自私的Agent所构成的一个社会。在这个社会中，每个Agent都有自己的利益和目标，并且它们的利益有可能存在冲突，目标也可能不一致。但是，正像人类社会中具有不同利益的人为了实现各自的目标需要进行合作一样，多Agent系统也是如此。

（一）Agent的协调

协调问题是多Agent合作中的一个主要问题。协调是指对Agent之间的相互作用和Agent动作之间的内部依赖关系的管理，描述的是一种动态行为，反映的是一种相互作用的性质。协调中有两个基本成分：一是“有限资源的分配”，二是“中间结果的通信”。例如，当多个Agent都需要使用某一共享资源时，涉及的是有限资源的分配问题；当一个Agent需要另一个Agent的输出作为其输入时，则涉及的是中间结果的通信问题。下面讨论三种常用的Agent协调方法。

1.基于部分全局规划的协调

部分全局规划（Partial Global Planning，PGP）是指将一个Agent组的动作和相互作用进行组合所形成的数据结构。该数据结构是通过Agent之间交换信息而合作生成的。基于部分全局规划的协调的基本原理是：在由多Agent构成的分布式系统中，为了达到关于某个问题求解过程的共同结论，合作的Agent之间需要交换各自的规划信息。所谓规划是部分的，是指系统不能产生整个问题的规划。所谓规划是全局的，是指Agent通过局部规划的交换与合作，可以得到一个关于问题求解的全局视图，进而形成全局规划。

基于部分全局规划的协调由以下三个迭代阶段构成：

（1）每个Agent决定自己的目标，并且为实现这一目标产生短期规划。

（2）Agent之间通过信息交换，实现规划和目标的交互。

（3）为协调动作和相互作用，Agent需要修改自己的局部规划。

为了实现上述迭代过程的连贯性，可以使用一个元级结构来指导系统内部的合作过程。该元级结构用来指明一个Agent应该与哪些Agent、在什么条件下交换信息。基于部分全局规划协调主要适应于内在具有分布特征的协作问题的求解，其典型应用是分布式感知和检测问题。

2.基于联合意图的协调

意图是Agent为达到愿望而计划采取的动作步骤。联合意图则指一组合作Agent对它们所从事的合作活动的整体目标的集体意图。例如，赛场上的一支球队，每个队员都有自己的个体意图，但整个球队必须有一个对整体目标的联合意图，并且这个联合意图是队员之间合作的基础。可见，基于联合意图的协调是一种以合作Agent的联合意图作为Agent之间协调基础的协调方法。

在基于联合意图的协调中，意图扮演着重要的角色，提供了社会交互必需的稳定性和预见性，以及应付环境变化必要的灵活性和反应性。支撑意图的两个重要概念是承诺和协议。承诺实际上是一种保证或许诺。协议则是监督承诺的方法，描述了Agent可以放弃承诺的条件，以及当Agent放弃其承诺时应该为自己和其他Agent所做的善后处理工作。

承诺的一个重要特性是其持续性，即Agent一旦做出承诺，就不能轻易放弃，除非由于某种原因使它变为多余时才行。承诺是否为多余的条件在相关协议中描述。这些条件主要包括：目标的动机已经不存在，或者目标已经实现，或者目标已不可能实现等。

基于联合意图协调的典型例子，是Agent机器人竞赛中同一队内Agent机器人之间的协调问题。这些Agent既有自己的个体意图，又有全队的联合意图。

3.基于社会规范的协调

基于社会规范的协调是以每个Agent都必须遵循的社会规范为基础的协调方法。规范是一种建立的、期望的行为模式。社会规范可以对Agent社会中各Agent的行为加以限制，以过滤某些有冲突的意图和行为，保证其他Agent必需的行为方式，从而确保Agent自身行为的可能性，以实现整个Agent社会行为的协调。

在基于社会规范的协调方法中，一个重要的问题是社会规范如何产生，即在Agent社会中用什么样的方法来制定社会规范。实际上，常用的制定社会规范的方法有两种：离线设计、系统内产生。离线设计是指在Agent系统运行前所进行的规范设计，其最大优点是简单，缺点是动态性差。系统内生成是指规范不是事先建立的，而是在系统活动过程中由策略更新函数的过程来建立的。策略更新函数描述了Agent的决策过程。可见，如何建立一个更好的策略更新函数是这种方法的关键。

（二）Agent的协作

协作是指Agent之间相互配合，一起工作，是非对抗Agent之间保持行为协调的一个特例。像人类社会一样，协作也是Agent社会的必然现象。常用的协作方法主要有合同网、市场机制、黑板模型和结果共享等，下面主要讨论合同网和市场机制。

1.合同网

合同网（contract net）是Agent协作中最著名的一种协作方法，被广泛应用于各种多Agent系统的协作中。合同网的思想来源于人们在日常活动中的合同机制。

（1）合同网系统的节点结构(www.xing528.com)

在合同网协作系统中，Agent节点的结构如图14－2所示，它主要由本地数据库与通信处理器、合同处理器和任务处理器组成。其中，本地数据库包括与节点有关的知识库、当前协作状态的信息和问题求解过程的信息，通信处理器、合同处理器和任务处理器利用它来执行各自的任务。通信处理器负责与其他节点进行通信，所有节点都仅通过通信服务器与网络连接。合同处理器负责处理与合同有关的任务，包括接受和处理任务通知书、投标、签订合同及发送求解结果等。任务处理器负责各种具体任务的处理，从合同处理器接受需要求解的任务，利用本地数据库进行求解，并将结果送给合同处理器。

图14-2　合同网系统中Agent节点的结构

（2）合同网系统的基本过程

在合同网系统中，所有Agent被分为管理者（manager）和工作者（worker）两种不同的角色。其中，管理者Agent的主要职责包括：

第一，对每个需要求解的任务建立其任务通知书（task announcement），并将任务通知书发送给有关的工作者Agent。第二，接受并评估来自工作者Agent的投标（bid）。第三，从所有投标中选择最合适的工作者Agent，并与其签订合同（contract）。第四，监督合同的执行，并综合结果。

工作者Agent的主要职责包括：

第一，接受相关的任务通知书。第二，评价自己的资格。第三，对感兴趣的子任务返回任务投标。第四，如果投标被接受，按合同执行分配给自己的子任务。第五，向管理者报告求解结果。

合同网系统的基本工作过程如图14－3所示。在该图中，左侧的字母是前面给出的管理者Agent职责中的相应职责的序号，右侧的字母是前面给出的工作者Agent职责中的相应职责的序号，其工作过程由上到下进行。

图14-3　合同网系统的基本工作过程

需要指出的是，在合同网协作方法中不需要预先规定Agent的角色。任何Agent都可以通过发布任务通知书成为管理者，都可以通过应答任务通知书成为工作者。这一灵活性使任务能够很方便地被逐层分解并分配。当一个Agent觉得自己无法独立完成一个任务时，就可以将该任务进行分解，并履行管理者职责。即该Agent为分解后的每个子任务发送任务通知书，并从返回投标的Agent中选择“最合适”的工作者Agent，与它们签订合同，再把这些子任务交给它们去完成。

2.市场机制

合同网协作方法一般只适用于较小数量Agent间的协作求解，而随着Internet及其应用的迅速发展，分布异构环境下大数量Agent间的协作问题需要探索新的、更有效的协作技术。市场机制就是在这种背景下产生的。

市场机制协作方法的基本思想是：针对分布式资源分配的特定问题，建立相应的计算经济（即标价或代价），以使Agent间能通过最少的直接通信来协调它们的活动。在这种方法中，需要对Agent关心的所有事物（如技能、资源等）都给出其标价，以作为计算经济的基础。

在市场机制协作方法中，所有的Agent被分为两类：生产者Agent、消费者Agent。其中，生产者Agent用于提供服务，即将一种商品转换为另一种商品；消费者Agent用于进行商品交换，所有商品交换都按当前市场标价进行。Agent应该以各种价格对商品进行投标，以获得最大的利益和效用（即性能价格比）。具体市场机制可以有多种，如各种拍卖协议、协商策略等。在一般情况下，采用市场机制解决问题需要说明以下四项：

第一，进行贸易的商品。第二，进行贸易的消费者Agent。第三，能够用自己的技能和资源将一种商品转换为另一种商品的生产者Agent。第四，Agent的投标和贸易行为。

由于商品市场是互连的，所以一个商品的价格将影响到其他Agent的供应和需求。市场有可能达到竞争性的平衡，这种平衡应满足的条件如下：

第一，消费者Agent根据其预算约束投标的价格，以期获得最大的效用。

第二，生产者Agent受其技能的限制进行投标，以期获得最大的盈利。

第三，所有商品的网络需求为零。

在一般情况下，平衡可能不存在或不唯一。如果假定每个单个Agent在市场中的作用都很小，并可忽略不计，就可保证这种平衡唯一存在。市场机制假定Agent给予的偏好与其所获得的效用或盈利相一致，因此Agent的推理行为是要对Agent的偏好最大化。

市场机制的主要优点是使用简单，适合大量或未知数量的自私Agent之间的协作。其主要缺点是用户的偏好难以量化和比较。