多Agent系统通信策略

第12卷　第1期2007年2月哈尔滨理工大学学报JOURNAL HARB I N UN I V .SC I .&TECH.Vol 112No 11　Feb .,2007多Agen t 系统通信策略陈海龙(哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080)摘　要:针对多Agent 系统通信机制中的关键性问题———Agent 通信策略,在分析多Agent 系统中几种常见通信策略的基础上,以Agent 获取信息的途径为主线,进一步引入超时思想,给出多Agent 系统的传递方式及通信策略,并在这一通信策略中,对Agent 通信进行时间上的限制,从而使Agent 通信的鲁棒性得到很大提高.关键词:多Agent 系统;Agent 通信策略;传递方式;超时中图分类号:TP18文献标识码:A 文章编号:1007-2683(2007)01-0086-04The Re sea rch on Comm uni ca ti o n S tra tegy ofMulti -agents SystemCHEN Ha i 2long(Computer Science &Technol ogy College,Harbin Univ .Sci .Tech .,Harbin 150080,China )Abstract:A i m ed at the p r oble m of communicati on mechanis m of multi -agents syste m ———Agent communica 2ti on strategy,based on intr oducing s ome co mmunicati on strategies of multi -agents system ,this paper advances a ne w agent communicati on strategy ———transfer mode with the concep t of ti m eout by the app r oach of agent cap turing inf or mati on .The paper als o li m its the agent communicati on ti m e in order t o i m p r ove the agent communicati on r o 2bustness .Key words:multi -Agents syste m;Agent communicati on strategy;transfer mode;ti m eout收稿日期:2006-03-02作者简介:陈海龙(1975-),男,哈尔滨理工大学讲师. Agent 之间的通信是实现Agent 间相互作用的基础.Agent 通信策略问题是多Agent 系统通信机制所需解决的关键性问题之一.事实上,如同人类社会一样,人际交流中的语言和文字也是最重要的手段.1　常见的Agent 通信策略多Agent 系统中,Agent 间的通信策略一般分为两类:信息传递方式和黑板方式[1].信息传递方式中,一个Agent 向另一个Agent 传递信息时,采用点对点传递,这就要求对方的名字和地址应该是事先已知的.因而,信息传递方式需要Agent 间相互了解的多一些.这种方式的特点为保密性好、实时性高.黑板方式,即把信息放在广泛可存取的“黑板”上,实现广播通信.在黑板方式中,黑板是一个共享的知识结构,Agent 可以向它张贴信息,也可以从其上读取其他过程张贴的信息.和信息传递方式比,黑板方式要求Agent 的相互了解可以少一些,但这种方式实时性不高,难以满足紧急情况的要求.2　Agent 获取信息的途径就通信内容来讲,Agent 通信实质上就是信息的传递.基于这点考虑,本文将以Agent 获取信息的途径作为主线,来对通信策略进行分析.Agent 获取信息的途径主要有查询、预订、传递和中介4种,分别介绍如下:1)查询.Agent 直接到系统或组织的公开信息库中查询感兴趣的信息,这是一种主动行为.2)预订.Agent 向系统或组织中专门负责预订的Agent 中预订自己感兴趣的信息.这种信息在预订当时可能存在,也可能根本不存在.一旦公开信息库中有相应信息存在时,该预订管理Agent 就会将信息发给预订者.这种方式中的Agent 是被动的(其之前的预订行为是主动的).3)传递.Agent 直接找到信息所有者,请求其向它提供信息.这是一种信息需求者与信息提供者之间的交互行为.双方可以直接进行通信,也可以把信息放在一个第三方位置进行通信.4)中介.向专门的中介Agent 发出求助请求,由中介Agent 帮助该Agent 找到相应的信息或信息提供者.3　多Agent 系统的通信策略———传递方式根据Agent 获取信息的途径,在多Agent 系统的通信中可分别设计出4种不同的通信策略方式[2]:查询方式(Query Mode )、预订方式(O rder Mode )、传递方式(Transfer Mode )和中介方式(M iddle man Mode ).本文主要给出多Agent 系统传递方式的通信策略.采用传递方式的前提条件是:Client -Agent 已经知道Server -Agent 的地址信息.Client -Agent 向Server -Agent 发出询问,在询问同时,Client -Agent 还应告知对方自己希望采用的回复方式以及相应的回复地址.回复方式有两种:直接回复方式(D irect Back )和间接回复方式(I ndi 2rect Back ).前者的回复地址是Client -Agent 本身的地址,后者的回复地址是一个第三方地址.在直接回复方式中,Client -Agent 发一询问到Server -Agent 并等待回答,Server -Agent 将回答直接回复给Client -Agent,如图1所示.图1　直接回复方式在间接回复方式中,Client -Agent 发一查询到Server -Agent 并等待回答,Server -Agent 将回答放到第三方地址处,然后Client -Agent 再去该地址取走回答,如图2所示.图2　间接回复方式有两点须特别说明:①Client -Server 并不知道Server -Agent 的回答将于何时到达第三方地址,它须每隔一段时间去该地址查看,直至回答到来;②Server -Agent 除提供回答外,还应提供足够多的匹配信息,以使Client -Agent 能进行匹配,找到该回答.两种回复方式相比较,前者的优点是实时性比较高.其最小通信时间为:线路上的延迟和Server -Agent 的延迟之和;后者的最小通信时间为:线路上的延迟、Server -Agent 的延迟以及Client -Agent 本身的耽搁之和,即T D irect =t L ine +t Server T Indirect =t L ine +t Server +t C lient另外,在直接回复方式中,Client -Agent 至少在T D irect 时间范围内要始终保持某种内部状态,这将占用其一部分内部资源.而间接回复方式中,Client -Agent 只需周期性地查看第三方地址,只有在真正接收时,才恢复原来的内部状态.4　超时思想的引入在前面所提出的传递方式通信策略中,并没有考虑时间限制的概念,在这里引入超时思想来进行时间限制.4.1　超时技术引入的必要性在传递方式通信策略中之所以引入超时技术,主要是基于以下原因:1)在Agent 处理某一工作的过程中,用于通信的时间往往在其整个计算时间内占很大比重,因而通信时间是不能忽视的;2)通信一般具有时效性,超过了一定的时间范围将失去原有意义;3)作为客户的Client -Agent 根本无法知道Server -Agent 的内部状态(如正常、出错、空闲、繁忙等),无法预测将产生的结局,因而,它只能够根据时间来决定自己的下一步动作,否则有可能会陷入漫长而无意义的等待.78第1期陈海龙:多Agent 系统通信策略4.2　超时技术引入的可行性1)Agent具有自治性、协同性、社会性等特性,其内部结构可根据环境的需要进行自治改变,以适应社会环境的需求是可行的;2)通过在Agent结构内部增加超时检查及超时状态,来解决、控制通信过程中对Agent内部状态的检测是可行的;3)根据传递方式中线路上的延迟、Server-Agent的延迟以及Client-Agent本身的耽搁,可确定出相应超时时间及超时检测状态值设置是可行的.5　超时方案的提出把那些Agent为完成某一目标而执行的一系列动作称为事件.根据其轻重缓急程度,事件可被分为以下三类:1)灵活事件.Agent既可以延迟考虑,也可以忽略掉的事件.2)不可避免事件.Agent必须执行(不可忽略),但可以延迟考略的事件.3)紧急事件.Agent必须立即执行,既不能延迟也不能忽略的事件.此三类事件相互独立.不存在那种可以忽略但不能延迟的事件.因为,忽略实质上就是无穷期的延迟.下面以直接回复方式为例来说明传递方式中超时思想引入所带来的工作流程的改善.5.1　未引入超时思想前的和端工作流程5.1.1　Client端Agent的工作流程1)Client-Agent向Server-Agent发出请求;2)等待Server-Agent的响应.收到Server-A2 gent的拒绝,转3);收到答复则转4);3)因对方拒绝,退出;4)成功,退出.5.1.2　Server端Agent的工作流程1)Server-Agent接收Client-Agent发来的请求.2)决定是否接受.若接受,则转第三步;不接受,转7).其中:①紧急事件,Server-Agent必须接受;②不可避免事件,Server-Agent必须接受;③灵活事件,Server-Agent可以接受,也可以不接受.接受与否取决于通信双方的信任程度以及Server-A2 gent对该信息的理解程度.3)决定是否立即执行.若立即执行,则转4);否则,等待一段时间后,继续执行3).其中:①紧急事件,Server-Agent必须立即执行;②其他事件,Serv2er-Agent可以立即执行,也可以延迟执行.是否延迟由Agent根据忙闲情况、通信方式等因素综合决定.4)执行事件.事件执行成功,则转5),失败转6).5)执行成功,提交结果,退出.6)执行失败,退出.7)通知对方拒绝该请求,退出.5.1.3　内部状态转换图未引入超时思想之前,Client端Agent和Server端Agent的内部状态转换如图3所示.图3　未引入超时时Client-Agent与Server-Agent 的内部状态转化图分析上述流程,可以发现一些问题:在Client端Agent的流程中,若由于某种原因没有收到Server-Agent的响应,则Client-Agent将陷入漫长的等待.而在Server端Agent的流程中,Server-Agent可能接受了某一事件,但却由于某原因不得不一再延迟执行,当经过一段时间后,即使再去执行这个事件,对Client-Agent也没有意义了.于是,引入超时思想.即在Client-Agent向Server-Agent发出请求时,请求中包含了超时参数t out.这样,在Client-Agent等待对方响应时,若超过t out仍无响应,Client-Agent则退出此延迟事件.而Server-Agent接收到Client-Agent的请求后,将根据事件性质以及自身情况等因素,决定是否接受此事件.以及接收后是否立即执行.它将尽量保证在t′out以内完成该事件,若在t′out内无法完成,Server-Agent就退出此延迟的事件.注意t out与t′out不同.5.2　引入超时后的Client端Agent和Server端A2gent工作流程.5.2.1　Client端Agent的工作流程1)Client-Agent向Server-Agent发出请求.t′out=t out-t line2)等待Server-Agent的响应.若未收到应答,则转3).收到对方的拒绝转4),收到答复则转5).3)进行超时检查.若超时,转6),否则,延迟一个时间段后转2).4)因对方拒绝,退出.88哈　尔　滨　理　工　大　学　学　报 第12卷　5)成功,退出.6)因超时退出.5.2.2　Server 端Agent 的工作流程1)Server -Agent 接收Client -Agent 发来的请求.2)决定是否接受.若接受,则转3);不接受,转9).其中:紧急事件,Server -Agent 必须接受;不可避免事件,Server -Agent 必须接受;灵活事件,Serv 2er -Agent 可以接受,也可以不接受.接受与否取决于通信双方的信任程度以及Server -Agent 对该信息的理解程度.3)决定是否立即执行.若不立即执行,则转4);否则,转5).其中:紧急事件,Server -Agent 必须立即执行;其他事件,Server -Agent 可以立即执行,也可以延迟执行.是否延迟由Agent 根据忙闲情况、通信方式以及事件的最大超时参数等因素综合决定.4)进行超时检查.超时,转8);否则,延迟一个时间段后转3).5)执行事件.事件执行成功,则转6),失败转7).6)执行成功,提交结果,退出.7)执行失败,退出.8)超时,退出.9)通知对方拒绝该请求,退出.5.2.3　内部状态转换图引入超时后,Client 端Agent 和Server 端Agent 的内部状态转换如图4所示:图4　引入超时时C li en t -Agen t 与Server -Agen t 的内部状态转化图图3、图4中椭圆表示Agent 的内部状态.其中,粗线椭圆表示该状态为结束状态,虚线椭圆表示可能会陷入无限循环的状态.6　超时技术的实现及结果分析在上述超时思想引入及超时方案提出的指导下,给出如下的超时技术实现过程及相应的结果分析.6.1　超时技术实现的主要过程1)改变Agent 自身的内部结构:增加新的内部状态———超时检查及超时状态;2)消息原语中引入超时参数t out ;3)根据传递方式中线路上的延迟、Server -A 2gent 的延迟以及Client -Agent 本身的耽搁,计算出相应的超时时间及超时检测状态值;4)在t out 的控制范围内进行事件的检测、执行与控制.6.2　结果分析超时方案的实现大大改善了Agent 间通讯及事件执行的效果.主要表现如下:1)提高了Agent 适应环境的需要,改善了Agent 的自适应性和自治能力;2)增强了Agent 对事件、周围环境及自身因素的判断分析能力;3)加快了Agent 处理消息、事件的能力;4)改善了多Agent 社会的环境,并增强了Agent 间的通讯能力.7　结　语本文在传递方式的通信策略中引入了必要的超时方案,使Agent 可以通过超时手段退出延迟的事件,避免陷入漫长而无意义的等待,大大提高了系统的鲁棒性.通过对传递方式及相关策略的研究,使这些通信方式各有所长,又彼此弥补不足,并且有时候还可以相互转换,从而使Agent 在通信时有了更多的途径可供选择,提高了通信的自适应性.参考文献:[1]　蔡自兴,徐光佑.人工智能及其应用(第二版)[M ].北京:清华大学出版社,1996.[2]　刘海燕,王献昌,王兵山.多Agent 系统的研究[J ].计算机科学,1995,22(2):57-62.[3]　WOOLDR I D GE M,JENN I N GS N R.I ntelligentagents:Theoryand Practice [J ].The Knowledge Engineering Revie w,1995,10(2):115-1522.[4]　朱　冰.Agent 研究[J ].计算机科学,1996,23(2):35-40.(编辑:付长缨)98第1期陈海龙:多Agent 系统通信策略。