多Agent排队系统结构研究

邱培呸呸呸

  摘  要  协调与协作是多Agent研究的核心之一。排队是实现多Agent协调与协作的关键技术。所谓多Agent排队系统是指由多个申请服务的顾客Agent和多个提供服务的服务台Agent组成的一个较为松散的组织，由协调Agent通过调度来协调它们的行为。多Agent服务台休假排队系统是在经典排队系统的基础上再添加一个休假策略，针对不同的应用背景，引人各种各样的休假行为和多Agent群集的思想，而形成的计算机系统。
    关键字  agent；排队；MAS


1  基本概念
    多Agent系统的混合式结构一般是由集中式和分布式两类结构组成，它包含一个或多个管理服务机构，此结构只对部分成员Agent以某种方式进行统一管理，参与解决Agent之间的任务划分和分配、共享资源的分配和管理、冲突的协调等。其他Agent之间是平等的，它们的所有行为由自身做出决策。此种结构平衡了集中式和分布式两种结构的优点和不足，适应分布式MAS复杂、开放的特性，因此是目前MAS普遍采用的系统结构。[2]
    鉴于多Agent系统的混合式体系结构，我们设计多Agent排队系统。在多Agent排队系统中主要由两类Agent组成，分别是顾客Agent和服务台Agent。由于系统中服务台数量是有限的，而顾客数是无限的，怎样来协调顾客Agent的行为呢?为了防止在申请服务台的时候发生冲突以及减少顾客与服务台交互的负担，在多Agent排队系统中，我们设置了一个队列Agent和一个协调Agent[3]。多Agent排队系统结构如图1。协调Agent主要承担调度任务，协调顾客Agent和服务台Agent的行为，以及管理服务台Agent。队列Agent是连接顾客Agent和协调Agent的纽带，主要管理队列中的顾客Agent，以及代替顾客向协调Agent申请服务台。服务台Agent主要提供服务给顾客Agent。

图1  多Agent排队系统体系结构
    在我们设计的多Agent排队系统中，约定：①只有一个队列Agent；②顾客遵循以λ 的到达率到达系统；③服务台Agent的能力是相同的，都能够服务任何的顾客；④服务台之间是并联关系，服务台的服务率遵循指数分布；⑤协调Agent采取先到先服务（FCFS）的调度策略。顾客Agent是分散的，而且是平等的，它们的行为由自身做出决策。
    在多Agent排队系统中，Agent为了实现自己的目标的同时，必须相互协调，以至达到协作，那么必须以通信为基础。顾客Agent与队列Agent之间、服务台Agent与队列Agent之间，协调Agent和服务台Agent之间，我们采用消息传送的方式。为了减轻过多的通信给系统带来的负担，我们暂且不支持顾客之间的通信。
    由此可知，构造Agent的基本要素要有：Agent的心智状态、Agent的知识库、Agent的感知器、Agent的通信。下面给出这几个要素的基本相关理论。
2  单Agent的构造
    在多Agent排队系统中，顾客Agent、队列Agent、服务台Agent以及协调Agent都需要一个基本的Agent为基础来建造。每个Agent都存在自己的心智状态、知识库、感知器以及通信模块等。为了适应环境的动态变化和协调各自的行为，Agent必须利用知识，修改内部状态，即心智状态（mental state）。知识需要感知器感知环境以及通过通信器与其它Agent进行交互而获得。
2.1  Agent心智状态的形式化描述
    在我们的多Agent排队系统中，Agent需要和其它Agent或环境交互，因此，Agent需要表示和维护环境的当前状态，这些信息可以根据新的信息的获取而改变，并且可以以Agent的信念或知识的形式存在。另外Agent的存在是为了实现自己的目标或问题的解决，而目标的实现需要多个Agent相互协调。因此，我们在构造Agent心智状态的时候，主要考虑Agent的信念（B）、愿望（D）、意图（I）、目标（G）等因素。单个Agent心智状态可以用下面的六元组表示：
    Agent＝{B，D，I，G，brf，drf，irf}
    其中：
    B：信念，描述的是Agent关于环境和自身的信息，这些信息可能不完整，甚至是不正确的。可以分为确定的客观事实和不确定的主观态度。例如“Tom的父亲是Jim”，“我相信明天会下雨”，前者是确定的客观事实，而后者的正确性是不确定的。
            Belief：：=FactBasedBelief|AttitudeBasedBelief；
            FactBasedBelief：：=fact(x) |aboutfact(x)；
            aboutfact：：=fact；
            AttitudeBasedBelief：：=believe(id，t，s)；
    含义是Agent的信念含有客观事实类信念和主观态度类信念，客观事实类信念包括事实以及有关此事实的知识。主观态度类信念表示Agent在时间t，相信标识符为id的Agent处于状态s。
    D：愿望，描述了Agent能够响应的事件和可能采纳的目标，由一个目标集组成。这些愿望可以具有不相容性，而且Agent也不必相信它的愿望是可实现的。
    I：意图，描述了Agent在自己未来的时间内对自己行动的预先安排，是Agent未来的行动方向。根据当前自身和环境状态和目标连接起来，建立计划集合。
Intention：：=intend(t，g)time(t)|believe(id，t，g)|goal(g)
    含义为：表示Agent感知到外界环境在时间t发生的事件或状态所蕴含的意图g后，判断Agent是否相信在该时间能实现该目标，然后向Agent提出实现目标的请求。
    G：目标，即Agent希望进入何种状态，是Agent从愿望中选择的子集，Agent可能要加以追求的。目标是Agent当前拥有的选择，然而，Agent还没有采取具体行动的承诺。
            Goal：：=goal(x)|aboutfact(x)；
            aboutfact(x)：：=fact(x)|aboutfact(x)
    含义是当Agent获得所要达到的目标x时，将查询该目标所需的知识。
    brf：Agent信念修正函数。brf： ，该函数依据当前感知（P）和当前的信念确定一个新的信念集合。
    drf：愿望修正函数。drf： ，该函数根据Agent关于环境和目前意图的当前信念确定一个愿望。该函数的作用：一是Agent的愿望的产生是一个循环求精的过程，不断地考虑和承诺局部实现的意图，直到最后获得目标；二是它产生的愿望必须与Agent当前的信念和当前的意图相一致，
    irf：意图修正函数。irf： ，该函数基于Agent当前信念、愿望和意图确定一个新意图。
2.2  Agent感知器算法
    我们知道人的感知器有眼、耳、鼻以及其它器官，机器人Agent有摄像机等。而软件Agent是通过字符串编码来实现感知的。
    感知器是一个多输入、单输出的运算系统[4]。主要有把感知的信息进行预处理后输出。我们把感知的信息进行分类，[5] w2类表示对紧急或简单的情况； w2类表示需要慎思的信息。
算法的基本步骤如下：
    （1）给定一个增广的训练模式集 {x1，x2，...，xN}，其中每个模式类别已知，分属 w1类和 w2类。
    （2）置步数k=1，令增量ρ =某正的常数，分别赋予初始增广权矢量 w（1）的各分量较小的任意值。
    （3）输入训练模式 xk，计算判别函数值 。
    （4）调整增广权矢量，规则是：
    ①  如果 和 ，则 ；
    ②  如果 和 ，则 ；
    ③  如果 和 ，或 和 ，则 。
    得到判别函数 d（x）之后，就可以进行判别，将待识别模式x 代入d（x） 之中，当d（x）>0 时则判x∈w1；若d（x）<0 时则判 x∈w2；若 d（x）=0：则 x的类属不能判定。紧迫的任务可以立即得以处理，对时间要求不高的任务可以通过推理选择最优方案。
2.3  Agent的知识库设计
    Agent的知识表示对自身和外界的认识，是Agent问题求解的基础[6]。这些知识可能预先给定的，也可能是通过局部感知或与其它Agent的通信而获得的。Agent知识库是Agent活动的依据，也是向外界承诺的基础。
    在这里知识库主要存放Agent的各个方面的知识，主要包括以下内容。
    ①关于系统组织结构、智能、目标等有关整体性质和行为的知识。
    ②关于理解自身的知识、行为、求解能力和目标等的知识。
    ③关于其它Agent的知识，即具有关于外部其它Agent的职责、技能、信念、目标、规划等多方面的知识。
    ④关于Agent间相互作用与通信的知识。
    ⑤关于领域世界及待求解问题的知识。
    这些知识是Agent进行一切活动的基础。Agent还知道哪些Agent与自己由横向或纵向的联系，这些知识在进行推理时起着关键的作用，它们同样可以看作是Agent的知识。这些知识可以映射为事实、规则等。
    对于知识库我们可以用下列形式表示：
<KB>::=[<Fact Base>]|<Rule Base>
<Fact Base>::={<Fact>}
<Fact>::=<Clause>
<Clause>::=<object1><conjunction><object2>
<object>::=<object1><conjunction><object2>
<Rule Base>::={<Rule>}
<Rule>::=<Name><(precondition 1，result 1)|(precondition 2，result 2)|...(precondition n，result n)>
<Name>::=<string>
<precondition i>::=<Clause>
<result i>::=<Clause>
    由于Agent每一次决策后都要进行知识的更新。下面给出Agent的知识更新定理。
    定义1.1  知识量[7]

    设X为Agent的某一领域， 均为有限集或可列集，j=1，2，...，N(N为有限或＋∞)}为X的一个表达，w 为Agent的一个表达测度，对任意的 令


则称I(xj)为表达∑中的一个基元xj的自蕴含知识量，其中对数底数b>1。
    定义1.2  设 {xn，n=1，2，...}是所有领域中一列独立同分布的Agent知识量，分布函数均为 F（t），假定F（0）<1 。记
    这里，υ平均（期望）更新时间间隔，Tn 是第n次更新发生的时间， N（t）表示Agent在时间[0，t]中发生的知识更新次数。
    其中，m(t)=E[N（t）] 称为Agent知识的更新函数，有 。
    m(t)的导数 。 fn(t)是Fn(t) 的知识更新强度。
2.4  Agent的通信模块
    在多Agent排队系统中，每个Agent自主的运行，但是由于每个Agent仅拥有不完全的信息和问题求解能力，所以多个Agent必须相互通信、协同工作。通信是协作的基础。采用消息通信是实现灵活复杂的协调策略的基础。使用规定的协议、Agent彼此交换的信息可以用来建立通信和协作机制。
    通信模块主要包含如下的部分[1]：
    （1）socket接口：它的功能是将直接与协议有关的通信部分组合在一起，并给通信模块的其它部分提高一种通信方式，使通信模块的其它部分不用再考虑与发送协议有关的部分。socket接口包含以下内容。
    服务线程：socket接口中有一个服务线程，它使用一个ServerSocket不停地监听Agent的端口地址，一旦发现有消息到来，就启动一个消息线程处理这个消息，然后继续监听。
    消息线程：由服务线程启动。它的任务是读入消息，并将消息送到接受缓冲区。
    客户线程：由发送线程启动。它的任务是将消息通过socket发出。
    （2）接受缓冲区：用来缓存从外界发来的消息。
    （3）发送缓冲区：用来缓存向外界发送的消息。
    （4）发送进程：是一个常驻线程。它的任务是不断监视发送缓冲区，一旦有消息进入发送缓冲区就启动socket接口中的方法来将消息发出。
    （5）接受线程：它的任务是不断查看接受缓冲区，一旦有消息进入接受缓冲区就启动一个过滤线程来对消息进行解释和处理。
    （6）过滤线程：由接受线程启动。它调用语法分析将接受到的字符流的消息转换成符合语法结构的原语，然后调用解释器来对原语解释。
    （7）解释器：解释并处理一些简单的且仅与通信模块有关的一些通信原语。
    （8）地址薄：通信模块保留Agent的地址薄信息。
    （9）消息发送函数：调用转化函数将原语转化成字符流放入发送缓冲区。
    下面介绍几种常用的消息：
bind（agenturl，sendername，receiverurl）
//发送注册消息给对方
shutdown(content，sendername，receiverurl)；
//发送注销信息给对方
inquire(content，sendername，receiverurl，senderurl)；
//询问接受Agent信息
request(content，sendername，receiverrurl，senderurl)；
//向接受Agent发送请求信息
2.5  Agent的规划模块
    在AI领域，规划是通过模拟人类求解复杂问题的过程而形成的一种方法。规划的问题求解方法分为两个过程：规划过程和执行过程。其中，规划过程是针对某一任务，求取完成该任务的动作序列，这一动作序列称为计划。计划是规划过程的输出结果。执行过程是指按照集合实现问题求解，并监控问题求解的进行，当出现意外情况计划无法执行时，调整行为集合或再次规划，直至任务完成。
    Agent的规划模块负责建立中短期的行动计划。它是一个局部的规划。每个Agent根据目标集合、自身的状态、对环境和其它Agent的了解，以及以往的经验规划自身的行为。
Agent规划常用方法之一是将Agent的计划库定义为一个与或图结构，其中，每一条计划由4部分组成。
    （1）计划目标表示该计划能达到的目标；
    （2）计划的前提表示计划执行需要满足的条件；
    （3）计划体表示计划内容，由计划序列和计划子目标组成；
    （4）计划执行结果表示执行计划后外部世界的更新结果。
    有了这些基本要素以后，我们可以根据需求构造基本的Agent了，下面给出Agent的工作流程及算法。
2.6  Agent工作流程及算法
    1）Agent的工作原理
    Agent工作过程如图2所示，当事件到达时，Agent根据前感知的环境信息、自身信息以及自己的能力，若感知的信息比较简单或紧急，则直接反应式决策，否则，要慎思以后进行规划，最后产生决策，即，由信念修正产生目标，并做出相应的计划集，然后选取相应的行为集来完成一系列的计划，如果计划失败，则继续更新信念集。

图2  Agent的工作流程
    2）Agent的工作流程算法
    根据Agent的工作原理，可将其工作流程算法描述为：
function Agent()
Begin
    事件到达；
    将感知信息进行分类；
if P is essy or urgency then reaction；
else
{
L1：B：=brf(P，B)；//根据感知和当前信念集产生新的信念
options：=Option_Generator(Envent_Queue，B，I，G)；
//根据环境和目前意图的当前信念产生愿望
Selected_Options：=deliberate(options，B，I，G)；//慎思过程
Update_Intentions(selected_options，I)； //更新意图
Make_Plan(I)；//根据当前意图制定计划
execute(plans)；//执行计划
if fail then
{
Update_Belief()；
goto L1；
}
}
End；
3  小结
    本文参照多Agent系统的体系结构建立了多Agent排队系统结构，并且构造了单Agent的基本要素，即Agent的心智状态形式化描述、Agent的感知器算法、Agent的知识库、Agent的规划模块和通信模块等。最后给出了Agent的工作机制和算法。
参考文献
[1]史忠植. 智能主体及其应用. 北京： 科学出版社，2002.12
[2]何炎祥，陈莘萌. Agent和多Agent系统的设计与应用. 武汉：武汉大学出版社，2001.6
[3]毛新军，赵建民，王怀民. 多Agent系统抽象合作模型. 计算机研究与发展，2004，41（5）：787-795
[4]李凡长，佘玉梅. 感知Agent的基本模型研究. 计算机科学，2004，31（2）：120-122
[5]余腊生，蔡莹皓. 实时环境下Agent决策机制研究. 小型微型计算机系统，2005，26（6）： 1032-1036
[6]毛新军，陈火旺，刘凤歧. Multi-Agent系统中Agent知识获取地合作模型.软件学报，2001，12（2）： 256-262
[7]李凡长. 基于Agent的知识表达度量理论. 计算机科学，2001，28(8)：110-113