多Agent排队系统结构研究
日期:2023-01-24 阅读量:0次 所属栏目:信息管理
摘 要 协调与协作是多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] w
2类表示对紧急或简单的情况; w
2类表示需要慎思的信息。
算法的基本步骤如下:
(1)给定一个增广的训练模式集 {x
1,x
2,...,x
n},其中每个模式类别已知,分属 w
1类和 w
2类。
(2)置步数k=1,令增量ρ =某正的常数,分别赋予初始增广权矢量 w(1)的各分量较小的任意值。
(3)输入训练模式 x
k,计算判别函数值 。
(4)调整增广权矢量,规则是:
① 如果 和 ,则 ;
②如果 和 ,则 ;
③如果 和 ,或 和 ,则 。
得到判别函数 d(x)之后,就可以进行判别,将待识别模式x 代入d(x) 之中,当d(x)>0 时则判x∈w
1;若d(x)<0 时则判 x∈w
2;若 d(x)=0:则 x的类属不能判定。紧迫的任务可以立即得以处理,对时间要求不高的任务可以通过推理选择最优方案。
2.3 agent的知识库设计
agent的知识表示对自身和外界的认识,是agent问题求解的基础
[6]。这些知识可能预先给定的,也可能是通过局部感知或与其它agent的通信而获得的。agent知识库是agent活动的依据,也是向外界承诺的基础。
在这里知识库主要存放agent的各个方面的知识,主要包括以下内容。
①关于系统组织结构、智能、目标等有关整体性质和行为的知识。
②关于理解自身的知识、行为、求解能力和目标等的知识。
③关于其它agent的知识,即具有关于外部其它agent的职责、技能、信念、目标、规划等多方面的知识。
④关于agent间相互作用与通信的知识。
⑤关于领域世界及待求解问题的知识。
这些知识是agent进行一切活动的基础。agent还知道哪些agent与自己由横向或纵向的联系,这些知识在进行推理时起着关键的作用,它们同样可以看作是agent的知识。这些知识可以映射为事实、规则等。
对于知识库我们可以用下列形式表示:
::=[]|
::={}
::=
::=