合同网协议的研究与应用

摘 要 本文分析了合同网的体系结构,阐述了合同网协议的原理及其应用中存在的问题,并提出了一种利用联盟机制、相关参数更新规则以及中标概率公式,以联盟为基本的投标单元的MACMIDCNP算法,实验证明本文提出的MACMIDCNP算法有效地提高了任务完成的效率,降低了通讯量,使得系统整体性能得到提高,在任务数不断增大的大规模系统中,该算法具有明显的优势。

关键词 多Agent系统;合同网协议;联盟;MACMIDCNP

中图分类号TP393 文献标识码A 文章编号 1674-6708(2010)24-0233-02

0 引言

Agent技术已经被广泛用于人工智能和Internet领域的研究活动中。多Agent系统是分布式人工智能的研究热点,其研究重点在于如何保证Agent间能够有效、有序地进行协作,这是多Agent系统成功运转的关键,也是增强整个系统可靠性、降低系统通信开销以及提高系统效率的关键。其主要问题可描述为,在MAS中,当某一个Agent接收到某一项任务时,如何在系统中利用最小的通信代价高效地选出一组符合条件的Agent来共同协作完成任务。

在目前对MAS的研究中提出了许多解决该问题的方法,在所有协作方法中,基于协商机制的合同网协议(Contract net protocol,CNP)是最著名且应用最广泛的一种协作方法,是用于分布式问题求解环境下各节点进行通信和控制的一种协作协议。

1 合同网协议

合同网协议是由美国国家科学基金会和美国国防高级研究计划局于20世纪70年代末共同出资研究,用于分布式问题求解的高级通讯和控制协议,是MAS中采用最为广泛的控制结构。目前,合同网已经应用于通讯网络管理系统、敏捷制造系统、空中交通管理系统、分布式感知系统等多Agent系统。

合同网协议是用于解决分布式问题求解环境下各节点之间的任务分配而进行的一种合约协作过程。合同网的节点构成包括:本地数据库节点、通讯处理器、合同处理器和任务处理器,如图1所示。

本地数据库包括与节点有关的知识库、协调当前状态和问题求解过程的信息。通信处理器与其它节点进行通信,节点仅通过该部分直接与网络相接,通信处理器的主要功能是理解消息的发送、接收及实现。合同处理器主要负责合同网协议的执行过程,在任务分配过程中,合同网协议模拟人类商业活动中的招标-投标-中标过程,合同处理器判断招标所提供的任务,发送投标和完成合同。同时分析和解释到达的消息,执行全部节点的协作。任务处理器的任务是实际处理赋予它的任务的求解,从合同处理器接受所要求解的任务,利用本地数据库进行求解,并将结果送到合同处理器。

1.1 基本合同网协议

基本合同网协议的基本思想是将任务的委派通过节点之间的招投标过程实现,将协作引入到招标方和投标方的双向选择过程中,节点之间通过招标―投标―中标机制进行任务分配,使系统以较低的代价、较高的质量完成分布式任务。

在合同网协议中,所有Agent可以归纳为两种角色:管理者和承包商。其中,管理者的职责包括:对每一个待求解任务建立任务通知书,将任务通知书发送给有关的承包商Agent;接收并评估来自承包商的投标;从投标中选择最合适的承包商,与之建立合同;监督任务的完成,并综合结果。承包商的职责包括:接收相关任务通知书;根据自己的能力判断是否接受任务,不接受发送拒标通知,否则发送投标通知;如果投标被接受,按合同执行分配给自己的任务,向管理者发送求解结果。

在合同网协作方法中,不需要预先规定Agent的角色,任何Agent通过任务通知而成为管理者;任何Agent通过应答任务通知而成为承包商。系统中的每一待求解任务,由承担该任务的Agent负责完成。当该Agent无法独立完成该任务时,它就将履行管理者职责,为该任务发送任务通知书;然后从返回的投标中选择“最合适”的Agent,将任务分配给此Agent,建立相应的合同。

1.2 基本合同网协议的优缺点

在经典的合同网中,任务的产生、分配、管理者以及承包商的产生均是动态的,系统的灵活性好。但传统的合同网协议中仍然存在着诸多不足,影响了实际协商过程以及任务的分配的效率。这些不足包括以下方面:

首先,标书的公布时存在的问题。在经典合同网协议中,为了最大限度地发现问题求解者并从中选择合适的最终问题求解者,管理者Agent需要将招标信息以广播方式发送给系统中所有的承包商Agent,所有的承包商Agent均可以参加投标。这不但容易造成系统中通信频繁,管理者还必须对大量的投标申请作出评价,耗费了系统中的大量资源。可见,这种不加选择的标书公布方式不仅会造成管理者负载过重,还可能导致网络阻塞。

其次,管理者Agent分解任务时存在的问题。任务固有的分解方式可能会不适应开放的分布式环境。管理者Agent为每个子任务选择一个承包商Agent,并将子任务分配给该承包商Agent,没有一个承包商Agent通过自己的规划来获得一个子任务,就算采取子合同方式,将一个子任务分配给一个Agent的固定任务分配策略也会导致低效率。

2 改进的合同网协议

针对以上的问题,本文提出一种基于改进动态合同网协议的Multi-Agent协作模型(a Multi-Agent Cooperation Model based on Improved Dynamic Contract Net Protocol简称MACMIDCNP) 。MACMIDCNP中,以联盟为基本单位进行任务的投标,根据混合遗传蚁群算法求得能完成任务的最优联盟,根据可信度以一定概率直接选中该联盟作为承包商,将通信范围缩小至该联盟内部,从而大大降低了系统的通信代价,节省了系统的运行时间,提高了系统的整体性能。

2.1 基本概念

1)可信度

定义1管理者m相信承包商Ci能够顺利完成任务的程度称为可信度,记为

Trm(Ci),

可信度是进行任务委托的主要指标之一,对某个承包商的可信度越高,则将任务委托给它的可能性就越大。

2)中标概率

管理者m修改承包商Cj对任务Tj的效用为,其中u(C,T)为承包商Cj完成任务Tj的效用,代表可信度在投标决策过程中占的权值,使用修改后的效用进行中标者的筛选。中标概率用如下公式表示:

管理者分配任务时,根据相应策略探测承包商是否空闲,若空闲,则将任务直接以概率Pij发送给指定承包商Cj。

2.2 MACMIDCNP算法

利用联盟机制、相关参数更新规则以及中标概率公式,以联盟为基本的投标单元,构造MACMIDCNP算法如下:

算法:MACMIDCNP算法

输入:联盟集C,任务集T

输出:任务完成记录

步骤:

1)管理者利用任务分解推理机及知识库,将任务T分解为若干个独立的子任务,即;

2)管理者从T中随机选择任务Tj;if(T为空),输出任务完成记录,程序结束;

3)根据混和遗传蚁群算法求得完成任务Tj的最优联盟Ci及其效用;

4)对于任务Tj,以概率Pij选择特定的联盟Ci作为指定承包商,向其发送标书,并设定响应时间为deadline;

5)若承包商Ci同意执行任务,向管理者发送确认通知;否则,不发送确认消息;

6)若在时间deadline内管理者没有收到该承包商的确认消息,转9)并减少承包商Ci的可信度;否则管理者直接向承包商Ci发送中标通知,发送任务Tj,并监督执行,同时通知其他投标者投标失败;

7)承包商Ci收到任务Tj后,调用任务分解模块,将任务分解为Tj=(tj1,tj2,…,tjn ),在联盟内分配、求解。然后返回任务的执行结果给当前系统管理者,同时根据相应的规则更新相关的状态参数;

8)若承包商Ci没有完全完成任务,则根据公式减少该联盟的可信度,并设剩余任务为Tji,令Tj=Tji,将其加入任务集T中,同时承包商Ci成为新的管理者,转9);否则转11);

9)一轮协作结束;

10)若管理者决定进行新一轮招标,转2);

11)任务Tj成功完成,把Tj从T中删除,转2)处理下一个任务。

2.3 仿真实验结果及分析

实验环境:

1)硬件环境:CPU Intel P4 3.0GHz 内存 1.00GB;

2)软件环境:Windows XP;

3)软件平台:Repast(Recursive Porous Agent Simulation Toolkit)是芝加哥大学社会科学计算研究中心研制的Multi-Agent建模工具,设定有20个执行Agent,任务数由50增至1 500个,通信代价测试结果如图2所示,运算代价测试结果如图3所示。

3 结论

由以上结果可以看出,随着任务数的不断增加,MACMIDCNP算法的通信代价大大低于DCNP算法,这是因为在MACMIDCNP算法中,管理者根据可信度与承包商的效用进行决策,而不是单一的以信任度作为决策标准,以联盟为基本投标单元而不是以单一Agent为基本单位进行投标,而联盟的任务求解能力要远远大于单一Agent,很多单一Agent无法求解的任务可以在联盟内部成功完成,最终使得系统的通信代价大大降低。另外,MACMIDCNP算法使得管理者能够优先选择能力更强的承包商,从而节省了运行时间,提高系统的运行效率。

在MACMIDCNP算法中,管理者根据可信度与承包商的效用进行决策,而不是单一的以信任度作为决策标准,以联盟为基本投标单元而不是以单一Agent为基本单位进行投标,不仅有效地提高了任务完成的效率,而且大大减少了通讯量,使得系统整体性能得到提高。实验表明在任务数不断增大的大规模系统中,该算法比DCNP算法具有明显的优势。

参考文献

[1]万武南,王晓京,宋春雨,等.基于范例推理的合同网模 型[J].小型微型计算机系统,2005,26(9):1578-1581.

[2]张海俊,史忠植.动态合同网协议[J].计算机工程, 2004,30(21):44-47.