多Agent系统模型的结构研究

Journal of Zhejiang Sci 2Tech U niversity

Vol.26,No.1,J an.2009

文章编号:167323851(2009)0120098206

收稿日期:2008-09-19

作者简介:程　奕(1973-　),男,浙江杭州人,硕士研究生,工程师,主要从事人工智能、数据库技术、多媒体技术的研究。

多Agent 系统模型的结构研究

程　奕,王申康

(浙江大学计算机科学与技术学院,杭州310027)

　　摘　要:在分析Agent 联邦中具有管理功能的Agent 结构的基础上,探讨具有联合意向的管理Agent 的协商、规划、执行等功能,刻画出Agent 的多种特征,并提出一个基于Agent 结构的数据仓库ETL 模型。

关键词:多Agent 系统;Agent 结构;数据抽取过程

中图分类号:TP311　　　文献标识码:A

0　引　言

多Agent 系统是由多个Agent 组成的集合,是为了解决单个Agent 不能解决的复杂问题,有多个Agent 协调合作形成的问题求解网络。在多Agent 系统中,主Agent 通过与其它Agent 的通信,可以开发新的规划或求解方法来处理不完全的、不确实的知识。通过Agent 间的合作,多Agent 系统不仅改善了每个Agent 的基本能力,而且从Agent 的交互中进一步理解了社会行为。

Agent 系统的结构研究是Agent 理论与技术研究的重要内容[123]。目前研究表明,Agent 结构可分为三类:a )基于行为(behavior 2based )的结构,典型工作是M IT 的Brooks 提出的包容结构(subsumption archi 2tect ure ),其优点是Agent 能及时而快速地响应外来信息和环境的变化,缺点是其智能程度较低,缺乏足够的灵活性;b )层次结构(layered architect ure ),典型模型是IN TERRA P ,其优点是Agent 具有较高的智能、较强的灵活性以及快速响应性,缺点是各层需要不同的规范语言,如反应层语言、规划层语言以及协调层语言等,另外与BDI 结构相比,缺乏完善的理论基础;c )BDI 结构,典型结构有PRS ,J AM 等,其优点是具有完善的理论基础,较强的灵活性以及快速响应性,缺点是缺乏行动本身的推理及面向目标的规划。由于Agent 往往处于动态的环境之中,要体现Agent 的根本特征———自主性,仅有上述研究是不够的,还必须刻画各种心智成分如何随环境的变化而变化,这就需要Agent 具有对行为的推理能力。文献[4]构造一个能表现Agent 自主性等多种特征的Agent 结构AASC ,并描述了其协商和规划、监控算法,能体现Agent 一定的自主性等特征。本文对具有联合意向的管理Agent 的协商、规划、执行等功能进行描述,刻画出Agent 的多种特征,并以实例应用进行说明。

1　Agent 联邦

一个多Agent 系统包含多个Agent 联邦及其子联邦,联邦内各软件Agent 都建立在本地信息的基础上,并具有程度不同的交互作用,由联邦管理Agent 集中调度。为了降低交互作用的复杂性,联邦内各软件Agent 只与管理Agent 通信,相互之间并不通信,除非在特殊情况下经管理Agent 授权才能进行。联邦可以嵌套,上层联邦中的普通Agent 或许就是下层某联邦的管理Agent 。联邦也可以转化为单一软件Agent 。各联邦的管理者为了实现信息流的最终目标,在平等协商的基础上进行协调和合作,包括联邦规划、联邦活

动和合作协调,以实现紧凑一致的协同工作[5]

。

图1　典型Agent 联邦配置结构

Agent 联邦的基本结构为:一个管理软件Agent 、一个

接口Agent 和若干个工具Agent 。如图1所示。

管理Agent 是整个系统中最关键的核心部件,是信息

流运行的“引擎”。

2　管理Agent (MA )的结构和功能

2.1　管理Agent

的体系结构注:“→”表示信息流,“ ”表示信息模块,“ ”表示功能模块图2　联邦管理Agent 体系结构

管理Agent 集Agent 能力配置和Agent 联邦配

置的需求于一身,进行意向的规划、执行,合作的协

商,技能的执行控制。管理Agent 的体系结构如图2

所示。

管理Agent 为实现联邦内外相关Agent 间协作

的联合调度,需要联合调度机制、协作知识库和信息

黑板三部分。联合调度机制由合作协商模块、意向规

划模块构成。后者执行面向特定目标(即意向)的联

合规划,并通过合作协商模块与其它Agent 联系和协

商,实现紧凑协调的规划和行动。协作知识库包括两个知识模型:熟人模型和自身模型,后者又由配置模型和意向模型集构成。这些模型成为管理Agent 作联合调度的依据。信息黑板记载联合调度过程中接收的信息或产生的结果。

意向模型实例的执行过程中,执行模块产生执行调度,激活管理Agent 自身拥有的技能,按技能模型中给出的执行方式(状态—反应规则组)加以解释性执行,并通过领域接口启动常规软件或构件。

管理Agent 的能力配置由两个层次来描述:意向和技能。意向是确定管理Agent 能执行的目标,并由意向模型来定义如何通过调度自身技能和其它管理Agent 的能力(意向),来达到拟定目标。技能是可供管理Agent 调度的功能单元,用相应的技能模型加以定义。每个管理Agent 可有多个意向,简单情况下,意向可由单一技能达到,从而意向转化为技能。

自身模型是对本Agent 的描述,记录了其意向、技能、当前状态等,是管理Agent 开展行为控制的依据。通信模块提供标准的会话层服务。当要求其它Agent 提供协作时,管理Agent 的行为控制器经由通信模块发送活动分配和协商消息。通信模块正是利用熟人模型来找到对特定事物感兴趣的Agent 。

为了与Agent 联邦内外的Agent 协同工作,在管理Agent 中设置合作协商模块。合作协商模块的协商对象是其它联邦中的管理Agent 或单一的Agent ,而不是联邦内Agent ,由于联邦内Agent 的合作实行集中调度,意向规划中管理Agent 无需与这些联邦内的Agent 进行协商。

联合调度机制中的合作协商模块、意向规划模块和执行模块均设计为管理Agent 运行进程下的线程,可以并发运行,并允许多个同类线程的同时存在,以适应于多目标(意向)并发执行的要求。联邦内普通Agent (非下层联邦的管理Agent ,而是界面Agent ,工具Agent 等)不作联合调度,只经由消息传送机制接收管理Agent 分配的任务,返回结果和报告意外事件的发生,从而只需一个简化的体系结构。

2.2　合作协商模块

管理Agent 设置合作协商模块的目的是为了与Agent 联邦内外的Agent 协同工作。合作协商模块依据管理Agent 中意向规划模块提出的需其它联邦协助完成的子目标,从熟人模型中寻找候选的联邦(由其管理Agent 为代表)或单一Agent ,按一定的协议(投票或招标)发送消息,并接收返回的消息,再转交给意向规划模块决策。

当意向模型的实例(作为意向规划的结果)启动执行时,合作协商模块将遵从意向规划模块的要求,经由通信接口模块发送子目标执行通知和有关信息给联邦内外参与协作的Agent ,接收返回信息,并在协作发生冲突或意外事故时,遵从意向规划模块的指令接发紧急通知和作协商处理。

99第1期程　奕等:多Agent 系统模型的结构研究

hrati的集中式协商方法,采用一个“mas2

ter agent”或组投票机制以达成协议。在这个方法中,一组Agent的协作与组规划进程有关。Ep hrati使用一种动态、迭代的搜索过程,通过一组约束条件,使Agent递增式地构成一个最有效的方案。在每一步,各Agent对于组方案的下一个联合行动投票。使用这一技术,Agent无需完整地表示其意向,可选子目标集在投票之前产生。

作为完全协作型的系统,Agent联邦中的Agent组成层次性结构,以发送子目标的管理Agent为上层的监控Agent,其它管理Agent或单一Agent为受控Agent,在上下层之间可能有三种控制关系:

a)监控Agent产生一个完整的方案并发给受控Agent;

b)监控Agent没有(或不能)生成一个完整方案,只生成部分方案(抽象方案),并发给受控Agent;

c)监控Agent无法生成或改善部分或完整的方案(由于知识),只发给受控Agent一个高层目标。

在a)情况下,受控Agent只是对方案的每一个子目标进行执行,把结果返回监控Agent,而无须进行规划,监控Agent根据返回的结果来确定每一个子目标。这是一种完全集中式控制关系。

由于监控Agent对具体环境知识的缺乏,它的完整方案中可能有错误。在b)、c)两种情形下,受控Agent必须依靠自己更为精确的知识产生完整方案,这个方案不能偏离监控Agent的原有目标太多。当存在较大的差异时,很可能有一方的知识有错,需通过通信来纠正,否则即按受控Agent的方案。

合作协商的算法步骤如下:

Negotiation(Ω,G);

//Ω为熟人模型;G为公共目标

Begin

While没有收到意向规划模块的结束信号DO

接收到意向规划模块子目标信息;

分析子目标信息,从协商信息中获取相关信息;

从自身模型中获得相关信息;

W HIL E执行结果EXECU TIN G(R)<期望EXP(R)DO

IF自身能产生完整子目标规划处方R T H EN

1)把此信息发送给意向规划模块和信息黑板;

2)接收意向规划模块产生的一个方案R;

3)获得反馈信息,传送给领域信息集;

EL SE

IF自身能产生部分子目标规划

T H EN1)把此信息传送给信息黑板和意向规划模块;

2)接收意向规划模块产生的一个抽象方案R;

3)发送R给相关联邦Agent要求投标以获得完整的方案集;

EL SE

发送一个子目标概要S给相关联邦Agent要求投标以获得完整的方案集;

END_IF

END_IF

接收反馈的方案集;

W HIL E　决定协商方式为投标DO

1)发送给意向规划模块;

2)接收意向规划模块产生的一个方案R;

3)发出要求投票信息;

END_W HIL E

其他Agent进行投票并返回投票信息;

接收投票信息;

把此信息传送给信息黑板和意向规划模块;

选择自身或Agent(A∈Ω)执行R,把结果反馈;

001　　　　　　　　　　　　　　浙　江　理　工　大　学　学　报2009年　第26卷

END_W HIL E

END_W HIL E

END 2.3　意向规划模块

意向规划模块包含实现目标所需的联合规划模板,联合系指(部分)子目标需由联邦内其它Agent 或其它联邦合作完成。规划模板具有若干个可选的方案,每个方案包括若干方案步骤。每个方案步骤表示为子目标的“与”、“或”组合,“与”指示必须同步完成的子目标,而“或”则表示可选。对于联邦管理Agent ,子目标可以通过执行Agent 自身的技能去完成,或是作为要由其它Agent 或Agent 联邦去完成的意向。联邦内的普通Agent ,若非下层管理Agent ,则其子目标均由自身的技能完成。子目标的分配约束和候选Agent (管理Agent 自身、联邦内普通Agent 和其它管理Agent )的描述支持了规划模板的结构。

每当意向模型因触发(由来自人机界面、网上信息传来等事件触发)而激活时,当前管理Agent 就通过意向规划模块自主进行规划,即生成具体的规划模板,并将产生的意向实例置于信息黑板。然后管理Agent 启动执行模块进行解释性执行。

规划模板其实是一棵“与或”树,实际过程中可以有多个规划供选择,即规划模板可以是一棵有多个分支的树,一个意向是每棵树的根,各规划是它的子树,末端的规划步是树的叶子。为了便于算法的实现,可以把这棵树转换为二叉树,因为它们具有相同的二叉链表,只是解释不同而已。

意向规划模块的规划过程中,对每个可选的规划都必须进行分析,以选择可行的规划来产生意向实例。因此对每个规划步的子目标都要进行研究,以确定子目标的实现方法。这在数据结构中类似于树的查找,依据树与二叉树的对应关系,笔者先把意向规划模板的树形结构转化为二叉树,然后通过类似二叉树的查找实现对规划模板中每个规划步的某个子目标的访问。

意向规划的算法步骤如下:

Planning (Ω,G );

Begin

从人机界面获得一个意向消息C ;

生成规划模板二叉树;

//对规划模板二叉树进行遍历;

IF 节点T !=null T H EN

　　发送子目标信息给合作协商模块;

接收合作协商模块反馈信息;

IF 自身能实现T H EN

产生一个方案R ;

EL SE

1)接收合作协商模块发送方案集;

2)从方案集中选一种方案R ;

IF FIND (R )=FAL SE T H EN

1)该方案或方案步骤失败,规划终止;

2)把规划异常消息发送到合作协商模块;

END_IF

END_IF

发送给合作协商模块;

接收合作协商模块反馈信息;

IF 该方案可行T H EN

把方案内容放入T ;

EL SE 把规划异常消息发送到合作协商模块;

END_IF

访问T 的左子节点,进行递归操作;

1

01第1期

程　奕等:多Agent 系统模型的结构研究

访问T 的右子节点,进行递归操作;EL SE

RETURN END_IF

IF 规划正常结束

T H EN

产生的意向规划实例送到信息黑板中的意向实例集;

发送结束信号到合作协商模块;END_IF

END

2.4　执行模块

意向规划模块产生一个完整的可执行方案后,把这个方案发送到信息黑板中意向实例集中;执行模块从意向实例集获得它,产生执行调度,激活管理Agent 自身拥有的技能,按技能模型中给出的状态———反应执行方式加以解释性执行。所谓解释性执行是指在执行某一技能以前,先解释选择执行这个技能的理由,理由包括这个技能执行前的状态及该技能所能达到的目标,解释信息被发送到信息黑板中的领域信息集。执行模块还要通过领域接口启动常规软件或构件以实现整个方案。

执行模块的算法步骤如下:

EXECU TION (R );

Begin

W HIL E 意向实例未执行完毕DO

从意向实例集中获得意向实例的意向规划步;

产生执行调度信息;

搜寻技能模型集中相关技能S ;

IF FIND (S )=TRU E T H EN

产生解释信息;

解释信息发送到领域信息集;

执行该技能;

执行结果发送给领域信息集;

EL SE

把未搜寻到信息发送给领域信息集;

END_IF ;

END_W HIL E

把执行结束消息发送给领域信息集;

END

3　实例应用

在数据仓库系统中,数据的抽取过程(ETL )是数据进入仓库的入口[6]。为了OL A P 和OL TP 系统各自的执行效率,数据仓库绝大多数都需要一个于联机事务处理系统的数据环境。抽取过程所涉及到的数据源一般包括:联机事务处理系统的数据、外部数据源、脱机的数据存储介质等,数据抽取在技术上主要涉及互连、复制、增量、转换、调度和监控等几个方面。数据仓库的数据不需要实时响应,因此数据抽取可以定时进行,但多个抽取操作执行的时间、互相的顺序、成败对于数据仓库中信息的有效性则至关重要。数据抽取过程涉及数据格式的转换,理想情况是通过用户选定源数据和目标数据的对应关系、格式及类型,会自动生成数据抽取的代码。但是,目前市场上提供的大多数抽取工具支持的数据类型有限,难以制成动态抽取功能,这种情况使得抽取功能往往不能满足要求。因此,笔者引入多Agent 模型对数据抽取、清洗、转换流程过程进行协同管理,以提高ETL 过程的效率。基于MAS 的ETL 模型如图3所示。

图3可见,在基于MAS 的ETL 模型中,主要包括三种类型的Agent 。

A )工具Agent 。工具Agent 能够接收管理Agent 的任务指令,从ETL 知识库Agent 得到有关规则和

201　　　　　　　　　　　　　　浙　江　理　工　大　学　学　报

2009年　第26卷

图3　基于多Agent 结构的ETL 模型数据后,调用内部推理模块和知识库进行求

解。按照所包装的工具软件类型的不同,工具

Agent 可以分为5个子类:a )数据库复制工具

类,这类工具特别设计来管理被复制的数据(分

布式数据库或数据仓库)。它们利用数据库触

发器或一个恢复日志捕捉在一个系统中的单个

数据资源的改变,并且将这些变化赋给位于不

同系统中的资源数据的备份;b )数据抽取类,

通过接口提取源数据,例如ODBC 、专用数据库

接口和平面文件提取器,并参照元数据来决定

数据的提取及其提取方式;c )数据转换类,将提取的数据,按照业务需要转换为目标数据结构,并实现汇总;d )数据加载类,将提取的数据,按照业务需要转换为目标数据结构,并实现汇总;e )数据库管理员,当可选的数据抽取工具都无效时,数据库管理员可面向具体的主题,编制特定的数据抽取算法。

B )管理Agent 具有调度功能和日志管理功能。调度功能包括基于事件和时间进行调度、运行、监测ETL 作业、管理错误信息、从失败中恢复等功能;日志管理功能包括管理作业调度日志和执行日志,提供对日志的查询、删除操作。

C )ETL 知识库Agent 。它负责对ETL 广义知识库进行管理和操作,提供一个关于ETL 设计和运行处理等相关定义、管理信息的元数据资料库。ETL 引擎在运行时和其它应用都可参考此资料库中的元数据;还提供一个图形化的映射环境,让开发者定义从源到目标的映射关系、转换、处理流程,并存储设计过程的各对象的逻辑定义。把工具Agent 的查询请求转换为对知识库的查询操作,并将查询结果返回给工具Agent 。4　结束语

通过对具有联合意向的管理Agent 的协商、规划、执行等功能的描述,刻画出Agent 的多种特征,从而为实际应用中根据特定的应用背景建构Agent 提供必要的理论基础,并介绍了基于多Agent 系统的ETL 模型构造。当然,在引入Agent 结构后,整个ETL 流程增加了不少通信开销,因此如何优化ETL 流程设计仍需要进一步研究。

参考文献:

[1]范玉顺,曹军威.多代理系统理论、方法与应用[M ].北京:清华大学出版社,2002:58-65.

[2]Liu Jiming.多智能体原理与技术[M ].靳小龙,张世武,Liu Jiming 译.北京:清华大学出版社,2003:76-82.

[3]Wooldridge M.多Agent 系统引论[M ].石纯一,张　伟,徐晋晖,等译.北京:电子工业出版社,2003:154-162.

[4]李　斌,唐小燕,吴梅丽.自主Agent 结构AASC 及其应用研究[J ].计算机应用研究:2005(7):21-23.

[5]钟凌燕.基于Agent 联邦的开放式工作流管理系统的研究[D ].杭州:浙江大学,2003.

[6]彭木根.数据仓库技术与实现[M ].北京:电子工业出版社,2002:33-67.

Research on Architecture of Multi 2Agent System Model

C H EN G Yi ,W A N G S hen 2kang

(School of Comp uter Science and Technology ,Zhejiang University ,Hangzhou 310027,China )

Abstract :Based on analysis of management Agent architect ure in Agent federation ,t his paper de 2scribes t he f unctio n of negotiation ,planning and execution wit h t he joint intentio ns management Agent and depictes various feat ures of Agent and importes a ETL model based on Agent architect ure in Data Ware 2house.

Key words :multi 2agent system ;agent architect ure ;ETL (责任编辑:张祖尧)301第1期程　奕等:多Agent 系统模型的结构研究