多agen系统中的承诺度模型

多agen系统中的承诺度模型

1mas体系内协作agent的模型多媒体系统（mas）合作关系的研究主要要解决两个问题：（1）任务分配模式；（2）资源之间的信息交换。所以,MAS能否协调有效地合作关键在于对这两个问题的解决上。与任务分配问题相关的是在MAS中寻找合作Agent的问题。一个Agent的知识和问题求解能力是有限的,为了完成任务,在很多情况下需要与其他Agent合作。所以,寻找合作Agent是问题求解的关键。那么如何确定合作Agent呢?文献提出了合同网协议,使用广播标书和参加投标的形式来确定合作Agent。由于合同网协议需要向所有其他Agent广播标书,对系统的通信和资源提出了很高的要求。文献采用集中协调的方式来降低系统通信开销。中心协调方法降低了广播通信的代价,但仍然需要大量向中心管理Agent请求查找协作Agent的通信开销。文献在MAS体系结构内为每一Agent设计了一个自我模型来表示自身信息,一个熟人模型来表示其他熟人Agent资源和能力方面的信息,通过对熟人的信息进行评估来确定协作Agent。这种方法降低了系统的通信开销,但增加了在本地建立和维护熟人模型的系统资源开销。文献设计了一个Agent模型,为系统建立一个公共合作库。这个合作库根据不同Agent能力的变化而修改,需要合作的Agent从合作库里寻找合适的Agent。但是,此模型要求每一个Agent监视其他Agent的活动,以便得到有关其他Agent的统计值、忙闲值、个性值等作为选择合适Agent的辅助信息。同样,需要大量工作放在维护熟人信息上。文献改造了上述熟人模型,不再需要为MAS中的每一Agent建立熟人模型,也不需要专门设立一个中间协调Agent,而是通过熟人链来寻找可能合作的Agent,实现了完全分布式访问和维护Agent信息。但是,其设计的模型存在两大类问题:(1)在一个MAS中,比较难以形成具有m路平衡树结构的熟人链。(2)通过熟人链来传递任务,在所有能执行任务的Agent执行完任务后,通过一些标准下达任务者从所有任务结果中选出理想的结果以及相应的任务执行者,即先执行任务后选择合作Agent。存在的问题是,可能在平衡树中有许多分支都成功地完成了此任务。只有一个Agent被用户选中实现价值,而其余Agent既消耗了自身资源(计算资源、硬件资源等),其价值又没得到认可。理性的合作Agent是不希望看到这样的事情发生的。本文针对上述文献存在的不足,把PingXuan和VictorRLesser提出的不确定承诺的思想和简化的熟人模型相结合,提出一个依据承诺度在简化的熟人模型中寻找合作Agent的方法,较好地解决了上述多Agent系统通信代价和在本地建立、维护熟人模型所带来的资源开销问题。2重新认识下的承诺策略承诺指Agent关于其行为和信念做出的保证。这些保证可能是有关未来的,也可能是有关过去的。承诺也是表现Agent理性的动态过程。在多Agent系统中,承诺被看作是协调各个Agent之间行动的桥梁。一些文献对承诺的程度和承诺的重新考虑进行了研究。文献给出了三种承诺策略:完全承诺、松散承诺和部分承诺(将来承诺修改的可能性),并比较了三种承诺策略对系统的影响,得出部分承诺策略使系统拥有较大的灵活性和收益。部分承诺把承诺值从0或1拓展到区间上,使Agent认真、理性地对未来进行承诺。文献提出了三个导致不确定承诺因素:(1)任务本身的不确定;(2)Agent的决定、计划过程的不确定;(3)提供承诺的Agent仅有关于接收承诺Agent的部分知识)。部分承诺就是由其中的第二个因素引起的。本文提出的承诺度是一个概率值,由导致不确定承诺的第一个因素引起。这种不确定承诺是由执行任务的不确定性导致的,所以我们提出在接受任务前如果Agent对任务进行推理、预测后才得出的承诺值,那么这个值拥有较高的理性和可信度。2.1任务的承诺值为了便于讨论,我们假设任务T={q,c,dl}(可能包括更多的参数),其中q为任务完成的质量,c为执行任务的代价,dl为任务的截止日期。q(20%,0)(30%,2)(50%,6)表示Agent在接受任务前推测出将来可能的任务质量结果。其中,(20%,0)表示q=0的可能性是20%,通常情况下q=0代表任务失败;q=2代表任务完成的较好;q=6代表任务完成得最好。同样,Agent在接受任务前对任务T中的c、dl有类似的推测。对于Agent而言,许多情形下会出现任务T或其下的一个子任务依赖于任务A或其下的子任务执行的情况,如图1所示。这样,Agent对任务T的承诺值C(T)也依赖于C(A)。假设P(M)表示任务依次依赖于其前面任务结果的概率,任务T的初始概率表示为P0(T),那么Agent对任务T承诺质量q为x、代价为y、截止日期为z的概率分别表示为:p(q(C(T))=x)=(∏M∈pred(T)p(q(M)＞0))*P0(q(T)=x)(1)p(c(C(T))=y)=(∏M∈pred(T)p(c(M)＞0))*P0(c(T)=y)(2)p(dl(C(T))=z)=(∏M∈pred(T)p(dl(M)＞0))*P0(dl(T)=z)(3)p(q(C(Τ))=x)=(∏Μ∈pred(Τ)p(q(Μ)＞0))*Ρ0(q(Τ)=x)(1)p(c(C(Τ))=y)=(∏Μ∈pred(Τ)p(c(Μ)＞0))*Ρ0(c(Τ)=y)(2)p(dl(C(Τ))=z)=(∏Μ∈pred(Τ)p(dl(Μ)＞0))*Ρ0(dl(Τ)=z)(3)各个指标对每个Agent来说重要程度不同,所以每个Agent在计算承诺度值时,对各个指标的侧重不同。况且各个指标在不同的领域也有不同的重要性,所以比较难于对各指标得出一致的重要性值。本文介绍一个寻找合作Agent的方法,不涉及具体领域。所以,我们这里仅形式地给出一个表达式如下:Pi,j,k(C(T))=W1*p(q(C(T))=i)+W2*p(c(C(T))=j)+W3*p(dl(C(T))=k)(4)Ρi,j,k(C(Τ))=W1*p(q(C(Τ))=i)+W2*p(c(C(Τ))=j)+W3*p(dl(C(Τ))=k)(4)其中,i、j、k分别表示各个参数的取值。任务成功的概率记为P(C(T)),当i、j、k分别取各参数中代表任务成功的各值时,则P(C(T))=Pi,j,k(C(T))。具体地,W1、W2,W3的值可以通过文献中有关几种确定权的方法给出,如德尔菲法、相邻指标比较法等。2.2承诺概率值对合作关系的影响承诺不仅具有保证动作或目标持续性的作用,而且是协调各个Agent之间行动的桥梁。承诺是一种保证,可以向接收承诺的Agent提供一定的信任感。从接收方来说,承诺值不同,那么其对发送承诺方能否完成任务的信任感也就不同。借鉴这种信任感,我们提出基于承诺度来选择合作Agent的方法。但是,我们的这种承诺不是随意的保证,而是Agent接受任务前对自身能力和任务本身进行分析后得出的承诺概率值。由于任务失败、执行超期以及任务的执行依赖于先前一些动作的情形都会导致承诺无法履行,Agent在接受任务前若考虑到这些可能引起任务失败的因素而做出相应的承诺告知对方,那么这样的承诺就具有较高的可信度,可以作为选择合作Agent的依据。3组织中熟人的相关信息本文基于承诺度寻找合作Agent的方法是建立在简化的熟人模型上。正如引言所述传统熟人模型可以减少系统的通信开销和资源限制,但增加了维护熟人模型所带来的局部开销。我们建立的熟人模型与以往的熟人模型不同,不需要为系统中的每一个Agent都建立熟人模型,仅需要一个简单的熟人通信录。MAS经过一段时间的运行后,很多Agent可能根据待求解任务的类型形成相对稳定且成功的联盟。这样,每个Agent就会把与自己近期经常合作成功(一般为不同的任务)的Agent当作自己的熟人,保存在自己的熟人通信录中。熟人通信录中的熟人所能完成的任务可以相同,也可以不相同。本文构建的组织中包含两类Agent:第一类Agent是组织中的一般Agent(除包含慎思计算所需的各种库,如知识库、能力库外),包括的属性主要有Name、Address、Contact_list。其中,Name(a)表示Agenta的名称;Agenta的联系地址Address(a)可表示为常见的Name.IP_Address.Port的形式;用Contact_list(a)表示Agenta的通信录,即Agenta所有熟人通信信息的列表,表示为Contact_list(a)=〈L1,L2,…,Ln〉。列表中的每个元素称为一条通信记录Li,i∈{1,2,…,n},称为Agenta的熟人i的联系信息,有Li=〈Name,Address〉,其中Name(i)、Address(i)分别表示Agenta的熟人i的名称、联系地址。通信录中各Agent的通信录的容量定义为通信列表Contact_list(a)中所含熟人的个数,记为Sizeof(Contact_list(a));用Contact_list(a).Name(i)表示Agenta的熟人i的名称,而Contact_list(a).Address(i)表示Agenta的熟人i的地址。通信录中的熟人信息可以随联系的紧密程度而改变,超过一定时间界限没有联系的熟人可以变得陌生,被Agent从通信录中删除;而通过熟人的熟人介绍,原先不熟悉的Agent也可以变得熟悉,在合作商Agent那里登记注册,从而被加入通信录中。第二类Agent称为合作商Agent,它负责对进入组织的Agent进行登记和地址交换;当组织中有多个任务时为每个任务建立临时的任务表,协调组织中的各个任务。4承诺概率的执行一个Agent在接受一个任务时是经过理性分析的,相信自己或者自己的熟人可以完成此任务时才接管这个任务。假如自己或自己的熟人都不能成功地完成此任务,那么Agent只能理性地放弃此任务。当Agent发现自己无法解决或无法单独完成此任务,但通过以往经历知道自己熟人圈中的熟人可能可以解决此类问题时,这个Agent成为任务的管理者,需要在熟人中选择合适的合作Agent。经过下列步骤后合作Agent被选出:(1)通过熟人记录把任务通知给各个熟人Agent。(2)接到任务通知的熟人Agent根据自身状态预测任务执行的各种可能结果,然后依据公式(1)、(2)和(3)求出任务T中各参数取相应值时的承诺概率。根据公式(4)求出成功完成任务的概率值,决定自己是否参与此次任务执行。(3)决定要执行任务的Agent,把各自的承诺概率值告知下达任务的Agent。(4)管理任务的Agent将接收到的各承诺值排队后选择出承诺值最大的、作为此次任务的执行者。任务能成功完成的概率是P(C(T)),任务失败的概率是(1-P(C(T)))。当任务失败时,管理Agent从剩余决定执行此任务的Agent中再选择出承诺值次大的Agent作为合作Agent执行任务。如果最终所有执行任务的Agent都未能成功地执行此任务,则这些Agent包括管理Agent都应受到相应的惩罚。当然,选择承诺值是有一定范围的。一般地,若P(C(T))<50%,管理Agent会认为与这样的Agent合作有较大的风险,因而拒绝选择这样的Agent作为合作Agent。当然,50%的界限是本文为了说明问题而给出的,我们认为这样的界限应该因系统的不同而不同。偏好风险性较大的系统,那么界限会低一些,反之会高一些。当然,小概率事件也可能会发生(任务能成功完成的概率P(C(T))很小,但任务也有可能被完成)。是否选择P(C(T))值小的Agent作为合作者,要依据管理Agent的风险观判断,但带着这样的较小P(C(T))进入组织的Agent,为了获得收益也同样愿意冒任务失败带来的惩罚风险。P(C(T))由公式(4)计算出。从2.1节承诺度的给定过程可以看出,由于Agent接受任务前对任务的各可能结果进行预测,所以带有较大的主观性。有些Agent为能够执行任务采用欺骗手段,可能故意报高承诺值。对待这样的Agent,管理Agent可以采取相应的惩罚策略进行惩罚。当然,我们认为一个Agent社会应该是积极向上的,社会中的Agent都应该是诚实的,都有力图通过和同伴成功合作使自己在同伴中的可信任度得到提高的强烈愿望。5任务p的预测结果我们以卡车运输调度问题为例,具体说明怎样选择合作Agent。一个车场AgentA接收到用户的任务,根据目前情况A难以完成,但知自己的熟人解决过类似问题。A由通信录Contact_list(A)=〈L1,L2,L3〉(假设A的通信录中只有三个熟人分别为AgentB、AgentC、AgentD)知各熟人的地址Name.IP_Address.Port,这时向他们发送任务P(q,dl)。接到任务P通知的B、C、D根据自己目前情况对p的各参数q、c、dl预测可能的执行结果。我们假设:(1)不确定的参数只有q;(2)B、C和D对P中的各个指标分别有相同的权值;(3)对B、C和D来说P分别依赖于它们中的一个任务(或子任务)b、c、d,依赖关系如图2所示。AgentC和AgentD的任务依赖的表示类似于AgentB。AgentC:qc(30%,0)(70%