多Agent排队系统结构研究

1、多Agent排队系统构造研究摘要协调与协作是多Agent研究的核心之一。排队是实现多Agent协调与协作的关键技术。所谓多Agent排队系统是指由多个申请效劳的顾客Agent和多个提供效劳的效劳台Agent组成的一个较为松散的组织，由协调Agent通过调度来协调它们的行为。多Agent效劳台休假排队系统是在经典排队系统的根底上再添加一个休假策略，针对不同的应用背景，引人各种各样的休假行为和多Agent群集的思想，而形成的计算机系统。关键字agent；排队；AS多Agent系统的混合式构造一般是由集中式和分布式两类构造组成，它包含一个或多个管理效劳机构，此构造只对部分成员Agent以某种方式进展

2、统一管理，参与解决Agent之间的任务划分和分配、共享资源的分配和管理、冲突的协调等。其他Agent之间是平等的，它们的所有行为由自身做出决策。此种构造平衡了集中式和分布式两种构造的优点和缺乏，适应分布式AS复杂、开放的特性，因此是目前AS普遍采用的系统构造。2鉴于多Agent系统的混合式体系构造，我们设计多Agent排队系统。在多Agent排队系统中主要由两类Agent组成，分别是顾客Agent和效劳台Agent。由于系统中效劳台数量是有限的，而顾客数是无限的，怎样来协调顾客Agent的行为呢?为了防止在申请效劳台的时候发生冲突以及减少顾客与效劳台交互的负担，在多Agent排队系统中，我们设

3、置了一个队列Agent和一个协调Agent3。多Agent排队系统构造如图1。协调Agent主要承当调度任务，协调顾客Agent和效劳台Agent的行为，以及管理效劳台Agent。队列Agent是连接顾客Agent和协调Agent的纽带，主要管理队列中的顾客Agent，以及代替顾客向协调Agent申请效劳台。效劳台Agent主要提供效劳给顾客Agent。图1多Agent排队系统体系构造在我们设计的多Agent排队系统中，约定：只有一个队列Agent；顾客遵循以的到达率到达系统；效劳台Agent的才能是一样的，都可以效劳任何的顾客；效劳台之间是并联关系，效劳台的效劳率遵循指数分布；协调Agent

4、采取先到先效劳FFS的调度策略。顾客Agent是分散的，而且是平等的，它们的行为由自身做出决策。在多Agent排队系统中，Agent为了实现自己的目的的同时，必须互相协调，以致到达协作，那么必须以通信为基矗顾客Agent与队列Agent之间、效劳台Agent与队列Agent之间，协调Agent和效劳台Agent之间，我们采用消息传送的方式。为了减轻过多的通信给系统带来的负担，我们暂且不支持顾客之间的通信。由此可知，构造Agent的根本要素要有：Agent的心智状态、Agent的知识库、Agent的感知器、Agent的通信。下面给出这几个要素的根本相关理论。在多Agent排队系统中，顾客Agen

5、t、队列Agent、效劳台Agent以及协调Agent都需要一个根本的Agent为根底来建造。每个Agent都存在自己的心智状态、知识库、感知器以及通信模块等。为了适应环境的动态变化和协调各自的行为，Agent必须利用知识，修改内部状态，即心智状态entalstate。知识需要感知器感知环境以及通过通信器与其它Agent进展交互而获得。2.1Agent心智状态的形式化描绘在我们的多Agent排队系统中，Agent需要和其它Agent或环境交互，因此，Agent需要表示和维护环境的当前状态，这些信息可以根据新的信息的获取而改变，并且可以以Agent的信念或知识的形式存在。另外Agent的存在是为

6、了实现自己的目的或问题的解决，而目的的实现需要多个Agent互相协调。因此，我们在构造Agent心智状态的时候，主要考虑Agent的信念B、愿望D、意图I、目的G等因素。单个Agent心智状态可以用下面的六元组表示：AgentB，D，I，G，brf，drf，irf其中：B：信念，描绘的是Agent关于环境和自身的信息，这些信息可能不完好，甚至是不正确的。可以分为确定的客观事实和不确定的主观态度。例如“T的父亲是Ji，“我相信明天会下雨，前者是确定的客观事实，而后者的正确性是不确定的。Belief：=FatBasedBelief|AttitudeBasedBelief；FatBasedBelie

7、f：=fat(x)|abutfat(x)；abutfat：=fat；AttitudeBasedBelief：=believe(id，t，s)；含义是Agent的信念含有客观事实类信念和主观态度类信念，客观事实类信念包括事实以及有关此事实的知识。主观态度类信念表示Agent在时间t，相信标识符为id的Agent处于状态s。D：愿望，描绘了Agent可以响应的事件和可能采纳的目的，由一个目的集组成。这些愿望可以具有不相容性，而且Agent也不必相信它的愿望是可实现的。I：意图，描绘了Agent在自己将来的时间内对自己行动的预先安排，是Agent将来的行动方向。根据当前自身和环境状态和目的连接起来，

8、建立方案集合。Intentin：=intend(t，g)tie(t)|believe(id，t，g)|gal(g)含义为：表示Agent感知到外界环境在时间t发生的事件或状态所蕴含的意图g后，判断Agent是否相信在该时间能实现该目的，然后向Agent提出实现目的的恳求。G：目的，即Agent希望进入何种状态，是Agent从愿望中选择的子集，Agent可能要加以追求的。目的是Agent当前拥有的选择，然而，Agent还没有采取详细行动的承诺。Gal：=gal(x)|abutfat(x)；abutfat(x)：=fat(x)|abutfat(x)含义是当Agent获得所要到达的目的x时，将查询该

9、目的所需的知识。brf：Agent信念修正函数。brf：，该函数根据当前感知P和当前的信念确定一个新的信念集合。drf：愿望修正函数。drf：，该函数根据Agent关于环境和目前意图的当前信念确定一个愿望。该函数的作用：一是Agent的愿望的产生是一个循环求精的过程，不断地考虑和承诺部分实现的意图，直到最后获得目的；二是它产生的愿望必须与Agent当前的信念和当前的意图相一致，irf：意图修正函数。irf：，该函数基于Agent当前信念、愿望和意图确定一个新意图。2.2Agent感知器算法我们知道人的感知器有眼、耳、鼻以及其它器官，机器人Agent有摄像机等。而软件Agent是通过字符串编码来

10、实现感知的。感知器是一个多输入、单输出的运算系统4。主要有把感知的信息进展预处理后输出。我们把感知的信息进展分类，52类表示对紧急或简单的情况；2类表示需要慎思的信息。算法的根本步骤如下：1给定一个增广的训练形式集x1，x2，.，xN，其中每个形式类别，分属1类和2类。2置步数k=1，令增量=某正的常数，分别赋予初始增广权矢量1的各分量较小的任意值。3输入训练形式xk，计算判别函数值。4调整增广权矢量，规那么是：假如和，那么；假如和，那么；假如和，或和，那么。得到判别函数dx之后，就可以进展判别，将待识别形式x代入dx之中，当dx0时那么判x1；假设dx0时那么判x2；假设dx=0：那么x的类

11、属不能断定。紧迫的任务可以立即得以处理，对时间要求不高的任务可以通过推理选择最优方案。2.3Agent的知识库设计Agent的知识表示对自身和外界的认识，是Agent问题求解的根底6。这些知识可能预先给定的，也可能是通过部分感知或与其它Agent的通信而获得的。Agent知识库是Agent活动的根据，也是向外界承诺的基矗在这里知识库主要存放Agent的各个方面的知识，主要包括以下内容。关于系统组织构造、智能、目的等有关整体性质和行为的知识。关于理解自身的知识、行为、求解才能和目的等的知识。关于其它Agent的知识，即具有关于外部其它Agent的职责、技能、信念、目的、规划等多方面的知识。关于A

12、gent间互相作用与通信的知识。关于领域世界及待求解问题的知识。这些知识是Agent进展一切活动的基矗Agent还知道哪些Agent与自己由横向或纵向的联络，这些知识在进展推理时起着关键的作用，它们同样可以看作是Agent的知识。这些知识可以映射为事实、规那么等。对于知识库我们可以用以下形式表示：KB:=FatBase|RuleBaseFatBase:=FatFat:=lauselause:=bjet1njuntinbjet2bjet:=bjet1njuntinbjet2RuleBase:=RuleRule:=Nae(prenditin1，result1)|(prenditin2，result

13、2)|.(prenditinn，resultn)Nae:=stringprenditini:=lauseresulti:=lause由于Agent每一次决策后都要进展知识的更新。下面给出Agent的知识更新定理。定义1.1知识量7设X为Agent的某一领域，均为有限集或可列集，j=1，2，.，N(N为有限或)为X的一个表达，为Agent的一个表达测度，对任意的令那么称I(xj)为表达中的一个基元xj的自蕴含知识量，其中对数底数b1。定义1.2设xn，n=1，2，.是所有领域中一列独立同分布的Agent知识量，分布函数均为Ft，假定F01。记这里，平均期望更新时间间隔，Tn是第n次更新发生的时间

14、，Nt表示Agent在时间0，t中发生的知识更新次数。其中，(t)=ENt称为Agent知识的更新函数，有。(t)的导数。fn(t)是Fn(t)的知识更新强度。2.4Agent的通信模块在多Agent排队系统中，每个Agent自主的运行，但是由于每个Agent仅拥有不完全的信息和问题求解才能，所以多个Agent必须互相通信、协同工作。通信是协作的基矗采用消息通信是实现灵敏复杂的协调策略的基矗使用规定的协议、Agent彼此交换的信息可以用来建立通信和协作机制。通信模块主要包含如下的部分1：1sket接口：它的功能是将直接与协议有关的通信部分组合在一起，并给通信模块的其它部分进步一种通信方式，使通

15、信模块的其它部分不用再考虑与发送协议有关的部分。sket接口包含以下内容。效劳线程：sket接口中有一个效劳线程，它使用一个ServerSket不停地监听Agent的端口地址，一旦发现有消息到来，就启动一个消息线程处理这个消息，然后继续监听。消息线程：由效劳线程启动。它的任务是读入消息，并将消息送到承受缓冲区。客户线程：由发送线程启动。它的任务是将消息通过sket发出。2承受缓冲区：用来缓存从外界发来的消息。3发送缓冲区：用来缓存向外界发送的消息。4发送进程：是一个常驻线程。它的任务是不断监视发送缓冲区，一旦有消息进入发送缓冲区就启动sket接口中的方法来将消息发出。5承受线程：它的任务是不断

16、查看承受缓冲区，一旦有消息进入承受缓冲区就启动一个过滤线程来对消息进展解释和处理。6过滤线程：由承受线程启动。它调用语法分析将承受到的字符流的消息转换成符合语法构造的原语，然后调用解释器来对原语解释。7解释器：解释并处理一些简单的且仅与通信模块有关的一些通信原语。8地址薄：通信模块保存Agent的地址薄信息。9消息发送函数：调用转化函数将原语转化成字符流放入发送缓冲区。下面介绍几种常用的消息：bindagenturl，sendernae，reEiverurl/发送注册消息给对方shutdn(ntent，sendernae，reeiverurl)；/发送注销信息给对方inquire(ntent，

17、sendernae，reeiverurl，senderurl)；/询问承受Agent信息request(ntent，sendernae，reeiverrurl，senderurl)；/向承受Agent发送恳求信息2.5Agent的规划模块在AI领域，规划是通过模拟人类求解复杂问题的过程而形成的一种方法。规划的问题求解方法分为两个过程：规划过程和执行过程。其中，规划过程是针对某一任务，求取完成该任务的动作序列，这一动作序列称为方案。方案是规划过程的输出结果。执行过程是指按照集合实现问题求解，并监控问题求解的进展，当出现意外情况方案无法执行时，调整行为集合或再次规划，直至任务完成。Agent的规划

18、模块负责建立中短期的行动方案。它是一个部分的规划。每个Agent根据目的集合、自身的状态、对环境和其它Agent的理解，以及以往的经历规划自身的行为。Agent规划常用方法之一是将Agent的方案库定义为一个与或图构造，其中，每一条方案由4部分组成。1方案目的表示该方案能到达的目的；2方案的前提表示方案执行需要满足的条件；3方案体表示方案内容，由方案序列和方案子目的组成；4方案执行结果表示执行方案后外部世界的更新结果。有了这些根本要素以后，我们可以根据需求构造根本的Agent了，下面给出Agent的工作流程及算法。2.6Agent工作流程及算法1Agent的工作原理Agent工作过程如图2所示

19、，当事件到达时，Agent根据前感知的环境信息、自身信息以及自己的才能，假设感知的信息比拟简单或紧急，那么直接反响式决策，否那么，要慎思以后进展规划，最后产生决策，即，由信念修正产生目的，并做出相应的方案集，然后选取相应的行为集来完成一系列的方案，假如方案失败，那么继续更新信念集。图2Agent的工作流程2Agent的工作流程算法根据Agent的工作原理，可将其工作流程算法描绘为：funtinAgent()Begin事件到达；将感知信息进展分类；ifPisessyrurgenythenreatin；elseL1：B：=brf(P，B)；/根据感知和当前信念集产生新的信念ptins：=ptin_Generatr(Envent_Queue，B，I，G)；/根据环境