第十四章分布式人工智能81.pptx

1、高级人工智能第十四章第十四章 分布式人工智能分布式人工智能 史忠植史忠植 中国科学院计算技术所2022-4-171内容10.1 概述10.2 分布式问题求解10.3 主体10.4 主体理论10.5 主体结构10.6 主体通信10.7 主体的协调与协作10.8 多主体环境MAGE2022-4-17210.1 概述分布式人工智能主要研究在逻辑上或物理上分散的智能系统如何并行的、相互协作地实现问题求解。两种解决问题的方法： 自顶向下：分布式问题求解 自底向上：基于主体的方法2022-4-173分布式人工智能系统的特色1) 系统中的数据、知识, 以及控制不但在逻辑上, 而且在物理上是分布的, 既没有全

2、局控制, 也没有全局的数据存储。2) 各个求解机构由计算机网络互连, 在问题求解过程中, 通信代价要比求解问题的代价低得多。3) 系统中诸机构能够相互协作, 来求解单个机构难以解决, 甚至不能解决的任务。2022-4-174分布式人工智能系统的主要优点1) 提高问题求解能力。2) 提高问题求解效率。3) 扩大应用范围。4) 降低软件的复杂性。2022-4-175分布式人工智能分布式人工智能的研究可以追溯到分布式人工智能的研究可以追溯到7070年代末期。早期分布式人工智能的年代末期。早期分布式人工智能的研究主要是分布式问题求解，其目研究主要是分布式问题求解，其目标是要创建大粒度的协作群体，它标是

3、要创建大粒度的协作群体，它们之间共同工作以对某一问题进行们之间共同工作以对某一问题进行求解。求解。2022-4-176合同网 19801980年年Davis Davis 和和 SmithSmith提出了合同网提出了合同网(CNET) (CNET) CNET CNET使用投标使用投标-合同方式实现任务在多合同方式实现任务在多个节点上的分配。合同网系统的重要贡献个节点上的分配。合同网系统的重要贡献在于提出了通过相互选择和达成协议的协在于提出了通过相互选择和达成协议的协商过程实现分布式任务分配和控制的思想。商过程实现分布式任务分配和控制的思想。2022-4-177分布式车辆监控测试系统 DVMT19

4、801980年麻萨诸塞大学的年麻萨诸塞大学的Lesser, Corkill Lesser, Corkill 和和 Durfee Durfee 等人主持研制等人主持研制DVMTDVMT该系统对市区内行驶的车辆轨迹进行监控该系统对市区内行驶的车辆轨迹进行监控, , 并以此环境为基础并以此环境为基础, , 对分布式问题求解对分布式问题求解系统中许多技术问题进行研究。系统中许多技术问题进行研究。DVMTDVMT是以是以分布式传感网络数据解释为背景，对复杂分布式传感网络数据解释为背景，对复杂的黑板问题求解系统之间的相互作用进行的黑板问题求解系统之间的相互作用进行了研究，提供了抽象和模型化分布式系统了研究

5、，提供了抽象和模型化分布式系统行为的方法。行为的方法。2022-4-178ACTOR模型19831983年年Hewitt Hewitt 和他的同事们研制了基于和他的同事们研制了基于ACTORACTOR模型的并发程序设计系统。模型的并发程序设计系统。ACTORACTOR模型提供了分布式系统中并行计算理论模型提供了分布式系统中并行计算理论和一组专家或和一组专家或ACTORACTOR获得智能行为的能力。获得智能行为的能力。在在19911991年年HewittHewitt提出开放信息系统语义提出开放信息系统语义, , 指出竞争、承诺、协作、协商等性质应作指出竞争、承诺、协作、协商等性质应作为分布式人工

6、智能的科学基础，试图为分为分布式人工智能的科学基础，试图为分布式人工智能的理论研究提供新的基础。布式人工智能的理论研究提供新的基础。2022-4-179MACE系统是一个实验型的分布式人工智能系统开发环境是一个实验型的分布式人工智能系统开发环境(Gasser 1987)(Gasser 1987)。MACEMACE中每一个计算单元都称作主体，它们具有知识表示和中每一个计算单元都称作主体，它们具有知识表示和推理能力，主体之间通过消息传送进行通信。推理能力，主体之间通过消息传送进行通信。MACEMACE是是一个类面向对象环境，但避开了并发对象系统中难于一个类面向对象环境，但避开了并发对象系统中难于理

7、解和实现的继承问题。理解和实现的继承问题。MACEMACE的各个机构并行计算的各个机构并行计算, , 并提供了描述机构的描述语言并提供了描述机构的描述语言, , 具有跟踪的具有跟踪的demonsdemons机制。机制。 该课题研究的重点是在实际并行环境下运行该课题研究的重点是在实际并行环境下运行分布式人工智能系统，保持概念的清晰性。分布式人工智能系统，保持概念的清晰性。2022-4-1710分布式运输调度系统DTDS-I19891989年清华大学石纯一等主持研制了分布式年清华大学石纯一等主持研制了分布式运输调度系统运输调度系统DTDS-I(DTDS-I(石纯一石纯一 1989) 1989)。该

8、系统以运输调度为背景，提出了分布式问该系统以运输调度为背景，提出了分布式问题求解系统的体系结构，对问题分解、任题求解系统的体系结构，对问题分解、任务分布算法和基于元级通信的协作机制等务分布算法和基于元级通信的协作机制等方面进行了探讨。方面进行了探讨。2022-4-1711分布式知识处理系统DKPS19901990中国科学院计算技术研究所史忠植等研中国科学院计算技术研究所史忠植等研究了分布式知识处理系统究了分布式知识处理系统DKPSDKPS。该系统采用逻辑该系统采用逻辑-对象知识模型，研究对象知识模型，研究了知识共享和协作求解等问题。了知识共享和协作求解等问题。2022-4-1712多主体系统

9、90年代，多主体系统年代，多主体系统Multiagent systems)的研究成为分布式人的研究成为分布式人工智能研究的热点。多主体系统主要研究自主的智能主体之间工智能研究的热点。多主体系统主要研究自主的智能主体之间智能行为的协调，为了一个共同的全局目标，也可能是关于各智能行为的协调，为了一个共同的全局目标，也可能是关于各自的不同目标，共享有关问题和求解方法的知识，协作进行问自的不同目标，共享有关问题和求解方法的知识，协作进行问题求解。题求解。 基于智能主体的概念，人们提出了一种新的人工智能定义：基于智能主体的概念，人们提出了一种新的人工智能定义：“人工智能是计算机科学的一个分支，它的目标是

10、构造能表现人工智能是计算机科学的一个分支，它的目标是构造能表现出一定智能行为的主体出一定智能行为的主体”。 所以，智能主体的研究应该是人工智能的核心问题。斯坦福所以，智能主体的研究应该是人工智能的核心问题。斯坦福大学计算机科学系的大学计算机科学系的 Hayes-Roth在在IJCAI95的特邀报告中谈到：的特邀报告中谈到：“智能的计算机主体既是人工智能最初的目标，也是人工智能智能的计算机主体既是人工智能最初的目标，也是人工智能最终的目标。最终的目标。”2022-4-1713多主体系统关于主体的研究不仅受到了人工智能研究人关于主体的研究不仅受到了人工智能研究人员的关注，也吸引了数据通信、人机界面

11、员的关注，也吸引了数据通信、人机界面设计、机器人、并行工程等各领域的研究设计、机器人、并行工程等各领域的研究人员的兴趣。有人认为：人员的兴趣。有人认为：“基于主体的计基于主体的计算（算（Agent-Based ComputingAgent-Based Computing， 简称简称ABCABC）将成为软件开发的下一个重要的突破。将成为软件开发的下一个重要的突破。”2022-4-1714 分布式问题求解分布式问题求解特点：数据、知识、控制均分布在系统的各节点上，既无全局控制，也无全局数据和知识存储。2022-4-1715 分布式问题求解分布式问题求解两种协作方式：两种协作方式： 任务分担任务分担

12、 结果共享结果共享2022-4-1716任务分担任务分担 Smith Smith 和和Davis Davis 提出了任务分担方式。提出了任务分担方式。在任务分担系统中在任务分担系统中, , 结点之间通过分担结点之间通过分担执行整个任务的子任务而相互协作执行整个任务的子任务而相互协作, , 系统系统中的控制以目标为指导中的控制以目标为指导, , 各结点的处理各结点的处理目标是为了求解整个任务的一部分。目标是为了求解整个任务的一部分。 任务分担的问题求解方式适合于求解具有层任务分担的问题求解方式适合于求解具有层次结构的任务次结构的任务, , 如工厂联合体生产规划、如工厂联合体生产规划、 数数字逻辑

13、电路设计、字逻辑电路设计、 医疗诊断。医疗诊断。2022-4-1717结果共享结果共享 Lesser Lesser 和和 Corkill Corkill 提出了结果共享方式。在提出了结果共享方式。在结果共享方式的系统中结果共享方式的系统中, , 各结点通过共享部分结果各结点通过共享部分结果相互协作相互协作, , 系统中的控制以数据为指导系统中的控制以数据为指导, , 各结点在各结点在任何时刻进行的求解取决于当时它本身拥有或从其它任何时刻进行的求解取决于当时它本身拥有或从其它结点收到的数据和知识。结点收到的数据和知识。 结果共享的求解方式适合于求解与任务有关的各结果共享的求解方式适合于求解与任务

14、有关的各子任务的结果相互影响子任务的结果相互影响, , 并且部分结果需要综合才能并且部分结果需要综合才能得出问题解的领域。如分布式运输调度系统、分布式得出问题解的领域。如分布式运输调度系统、分布式车辆监控实验系统车辆监控实验系统DVMTDVMT 2022-4-1718分布式问题求解系统分类分布式问题求解系统分类根据组织结构，分布式问题求解系统可以分为三类： 层次结构类 平行结构类 混合结构类2022-4-1719分布式问题求解过程分布式问题求解过程分布式问题求解过程可以分为四步： 任务分解 任务分配 子问题求解 结果综合2022-4-1720任务分解任务分解 合同网络合同网络 动态层次控制动态

15、层次控制 自然分解自然分解, 固定分配固定分配 部分全局规划部分全局规划2022-4-1721分布式问题求解系统中协作的分类 按节点间协作量的多少，协作分为三类： 全协作系统 无协作系统 半协作系统常用的通信方式有： 共享全局存储器 信息传递 黑板模型2022-4-1722 主主 体体多主体系统主要研究在逻辑上或物理上分离的多个主体协调其智能行为，即知识、目标、意图及规划等，实现问题求解。可以看作是一种由底向上设计的系统。2022-4-1723主体的思想主体的思想智能主体的几个典型的实例： Microsoft的Office助手 计算机病毒（破坏主体） 计算机游戏或模拟中的智能角色 贸易和谈判主

16、体（如Ebay的拍卖主体） 网络蜘蛛Web Spider（搜索引擎中的数据搜集和索引主体，如Google） 2022-4-1724主体程序设计主体程序设计面向过程的方法面向实体的方法面向对象的方法面向主体的方法软件开发方法的进化2022-4-1725主体的定义在计算机和人工智能领域中，主体可以看作是一个实体，它通过传感器感知环境，通过效应器作用于环境。2022-4-1726主体的特性主体的特性主体弱概念：自治性交互性协作性可通信性长寿性2022-4-1727主体的特性主体的特性主体强概念：知识、信念、意图、承诺等心智状态其它属性：移动性推理能力规划能力学习和适应能力诚实、善意、理性2022-4

17、-1728 主体理论智能主体的理论模型研究主要从逻辑、行为、心理、社会等角度出发，对智能主体的本质进行描述，为智能主体系统创建奠定基础。2022-4-1729理性主体（BDI主体）Belief信念，主体对环境的基本看法。Desire愿望，主体想要实现的状态，即目标。Intention意图，目标的子集。2022-4-1730 BDIBDI主体模型主体模型BDI主体模型可以通过下列要素描述： 一组关于世界的信念； 主体当前打算达到的一组目标； 一个规划库，描述怎样达到目标和怎样改变信念； 一个意图结构，描述主体当前怎样达到它的目标和改变信念。2022-4-1731BDIBDI解释器解释器BDI-I

18、nterpreterinitialize-state();dooptions := option-generator(event-queue, B, G, I);selected-options := deliberate(options, B, G, I);update-intentions(selected-options, I);execute(I);get-new-external-events();drop-successful-attitudes(B,G,I);drop-impossible-attitudes(B,G,I);until quit2022-4-1732 动作理论情景

19、演算是描述动作的主要的形式框架。 在情景演算中引入了状态和动作的概念，并利用两条逻辑公理来描述动作与状态的关系。一条公理描述一个动作在满足什么条件的状态之下可能发生，另外一条描述在一个状态之下某个动作发生以后当前状态如何改变。2022-4-1733规划库的形式化表示规划库的形式化表示环境状态：State = P1, P2, Pn 目标： Goal=动作模板： Act_template = 主体能力： Ability= 2022-4-1734主体结构主体结构需要解决的问题包括： 主体由那些模块组成， 模块之间如何交互信息， 主体感知到的信息如何影响它的行为和内部状态， 如何将这些模块用软件或硬件

20、的方式组合起来形成一个有机的整体。2022-4-1735主体基本结构主体基本结构环境主体感知作用黑箱软件主体2022-4-1736智能主体的工作过程智能主体的工作过程环境交互信息融合信息处理作用交互感知作用2022-4-1737主体骨架程序主体骨架程序function Skeleton-Agent(percept) return actionstatic: memory /* 主体的世界记忆 */memory Update-Memory(memory,percept)action Choose-Best-Action(memory)memory Update-Memory(memory,act

21、ion)return action2022-4-1738主体的分类 根据人类思维的层次模型，可以将主体分成四类： 反应主体 形象思维主体 抽象思维主体 复合式主体 形象思维主体和抽象思维主体也可以合称为认知主体2022-4-1739 反应主体反应主体环境当前世界传感器动 作效应器条件-动作规则主体2022-4-1740反应主体程序反应主体程序function Reactive-Agent(percept) returns action static: rules, /* 一组条件-动作规则 */ state Interpret-Input(percept) rule Rule-Match(st

22、ate,rules) action Rule-Actionrule return action2022-4-1741认知主体认知主体环境信息融合传感器动 作效应器主体规 划知识库目标内部状态2022-4-1742认知主体程序认知主体程序function Cognitive-Agent(percept) returns actionstatic: environment, /* 描述当前世界环境 */ kb, /* 知识库 */ environment Update-World-Model(environment,percept) state Update-Mental-State(enviro

23、nment,state) action Decision-Making(state,kb) environment Update-World-Model(environment,action) return action2022-4-1743BDIBDI结构结构知识信念规划 意 图目 标愿 望2022-4-1744复合式主体复合式主体决策生成规 划反 射建 模通 信感 知行 动其他智能主体智能主体外部世界预测协作与协商动作请求或应答信息一般情况紧急情况和简单情况2022-4-1745规划模块规划模块世界的模型（包括其他 主体的模型）经 验 库目标集合局 部 规 划 器决 策 生 成重新规划规划

24、规划目标2022-4-1746建模模块建模模块世界的模型（包括其他 主体的模型）模 型 库模 型 生 成 和 维 护预 测规划决策生成感 知通 信建模2022-4-1747通信模块通信模块词 法 库语 法 库词 义 库物理通信语言生成语言理解通信2022-4-1748主体通信主体通信策 略对 话消 息黑 板协 议通信协作协 议2022-4-1749主体通信中的主要问题主体通信中的主要问题2022-4-1750主体间的消息传递主体间的消息传递消息发送/传输服务器转换到传输格式从传输格式转换消息M言语行为意图I目标GAgent i消息MAgent i2022-4-1751本体论本体论本体论是概念化

25、的明确的表示和描述。对某一领域中的概念有共同理解，可以提高交流和协作的效率，从而提高了软件的重用性。2022-4-1752言语行为言语行为 有关言语行为理论的研究主要集中在如何划分不同类型的言语行为。 在主体通信语言的研究中，言语行为理论主要用来考虑主体之间可以交互的信息类型。2022-4-1753通信语言通信语言KQML：由美国ARPA的知识共享计划中提出，规定了消息格式和消息传送系统，为多主体系统通信和协商提供了一种通用框架。ACL：由FIPA制定的一种规范。与KQML非常相似2022-4-1754KQML一个例子：(ask-all: senderA: receiverB: in-repl

26、y-toido: reply-withidl: languageProlog: ontologyfoo: content“bar (X, Y)”)2022-4-1755FIPA ACL(inform: sender agent1: receiver hpl-auction-server: content (price (bid good02) 150): in-reply-to round-4: reply-with bid04: language s1: ontology hpl-auction)消息结构开始通信动作类型消息参数消息内容表达式参数表达式2022-4-1756FIPAFIPA通

27、信动作库通信动作库Accept Proposal接受提议Agree同意Cancel取消Call for Proposal要求提议Confirm确认Disconfirm确认为否定Failure失败Inform通知Inform If通知 是否Inform Ref通知 有关对象Not Understood不理解2022-4-1757FIPAFIPA通信动作库通信动作库2022-4-1758XMLeXtensible Markup Language 可扩展标记语言可扩展标记语言 XML是用于标记电子文件使其具有结构性的标记语言。XML文件本身只是将文件资料结构化。例如：下面的ACL消息(inform:

28、sender jklabrou:receiver grosof:content (CPU libretto50 pentium):ontology laptop:language kif)2022-4-17592022-4-17602022-4-1761主体的协调与协作主体的协调与协作协调(coordination)与协作(cooperation)是多主体研究的核心问题之一。 协调是指一组智能主体完成一些集体活动时相互作用的性质。 协作是非对抗的主体之间保持行为协调的一个特例。2022-4-1762协调协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望

29、避免主体之间的死锁或活锁。 死锁指多个主体无法进行各自的下一步动作； 活锁指多个主体不断工作却无任何进展。2022-4-1763协作协作目前针对主体协作的研究大体上可分为两类：1) 将其它领域研究多实体行为的方法和技术用于主体协作的研究。如对策论和力学研究。2) 从主体的目标、意图、规划等心智态度出发来研究多主体间的协作。2022-4-1764协作规划协作的动机：1) 某个主体相信通过协作能带来好处（如提高效率，完成以往单独无法完成的任务）2) 多个主体在交流的过程中，发现它们能够通过协作来实现更大的目标。2022-4-1765协作过程协作过程1) 产生需求、确定目标2) 协作规划、求解协作结

30、构3) 寻求协作伙伴4) 选择协作方案5) 实现目标6) 评估结果2022-4-1766协作模式协作模式从社会心理学的角度看，多主体之间的协作情从社会心理学的角度看，多主体之间的协作情形大致可分为：形大致可分为： 协作型：同时将自己的利益放在第二位。协作型：同时将自己的利益放在第二位。 自私型：同时将协作放在第二位。自私型：同时将协作放在第二位。 完全自私型：不考虑任何协作。完全自私型：不考虑任何协作。 完全协作型：不考虑自身利益。完全协作型：不考虑自身利益。 协作与自私相混合型。协作与自私相混合型。2022-4-1767协作策略协作策略 计算生态学计算生态学 对策论对策论 规划规划2022-

31、4-1768计算生态学计算生态学 80 80年代末，在计算机中出现了一个崭新的学年代末，在计算机中出现了一个崭新的学科科-计算生态学计算生态学(the ecolog of (the ecolog of computation)computation)。计算生态学是研究关于开放。计算生态学是研究关于开放系统中诀定计算结点的行为与资源使用的交系统中诀定计算结点的行为与资源使用的交互过程的学科。它摒弃了封闭、静止地处理互过程的学科。它摒弃了封闭、静止地处理问题的传统算法，将世界看作是开放的、进问题的传统算法，将世界看作是开放的、进化的、并发的化的、并发的, , 通过多种协作处理问题的通过多种协作处理

32、问题的生态系统生态系统(ecosystem)(ecosystem)加以研究。它的进展与开放信息系加以研究。它的进展与开放信息系统的研究息息相关。统的研究息息相关。2022-4-1769计算生态学计算生态学 计算生态学将计算系统看作是一个生态系统，它计算生态学将计算系统看作是一个生态系统，它引进了许多生物的机制，如变异引进了许多生物的机制，如变异(mutation)(mutation)即物种即物种的变化。这些变化导致生命基因的改变，从而形成的变化。这些变化导致生命基因的改变，从而形成物种的多样性，增强了适应环境的能力。这类变异物种的多样性，增强了适应环境的能力。这类变异策略成为人工智能系统提高其

33、自身能力的一种方法。策略成为人工智能系统提高其自身能力的一种方法。LenatLenat与与BrownBrown成功地将变异机制引入他们的成功地将变异机制引入他们的AMAM与与EuriskoEurisko系统中系统中, , 通过小型通过小型LispLisp程序的语法变异发程序的语法变异发现数学概念。他们认为未来成功的系统应该是一系现数学概念。他们认为未来成功的系统应该是一系列进化的、自组织的符号知识结构的列进化的、自组织的符号知识结构的社会社会 系统。系统。2022-4-1770生物生态模型生物生态模型这是最著名的生态系统，具有典型的进化这是最著名的生态系统，具有典型的进化特征和层次性。这种特性

34、反映在特征和层次性。这种特性反映在“食物食物链链”中。对于复杂的生物生态系统而言，中。对于复杂的生物生态系统而言，各物种组成了紧密相连的网络各物种组成了紧密相连的网络-食食物网。这个系统的主要角色是捕食者与物网。这个系统的主要角色是捕食者与被食者。生命依赖于生命，共同进化，被食者。生命依赖于生命，共同进化，由小的生态环境组成大的生态系统。由小的生态环境组成大的生态系统。2022-4-1771物种进化模型物种进化模型物种进化的物种进化的“复制者复制者”是基因。从门德尔的植物遗传是基因。从门德尔的植物遗传研究到现代遗传学的成果，都说明了在物种进化过研究到现代遗传学的成果，都说明了在物种进化过程中，

35、基因的组合与变异起着关键作用。在一个物程中，基因的组合与变异起着关键作用。在一个物种的某一群体中基因的集合称为基因池。生物组织种的某一群体中基因的集合称为基因池。生物组织是基因的载体。如果环境变化，选择的机制就会改是基因的载体。如果环境变化，选择的机制就会改变。这种变化必然引起基因池的变化。特定种群的变。这种变化必然引起基因池的变化。特定种群的基因变化称为基因流。一个物种总是不断地经历隔基因变化称为基因流。一个物种总是不断地经历隔绝、基因流动、变化的循环。开始时，一组地理上绝、基因流动、变化的循环。开始时，一组地理上隔绝的群体自己孤立地发展，基因在内部快速地流隔绝的群体自己孤立地发展，基因在内

36、部快速地流动。随着开放，通过交流和竞争，优胜劣汰。动。随着开放，通过交流和竞争，优胜劣汰。2022-4-1772经济模型经济模型经济系统在某种意义上类似于生物生态系统。经济系统在某种意义上类似于生物生态系统。在商品市场和理想市场中，进化决定于经济在商品市场和理想市场中，进化决定于经济实体的决策。选择机制是市场奖励机制。进实体的决策。选择机制是市场奖励机制。进化是快速的，企业与消费者之间、企业之间化是快速的，企业与消费者之间、企业之间主要是一种互相依赖的合作关系。决策者为主要是一种互相依赖的合作关系。决策者为了追求长远利益，可以采取各种有效的方法，了追求长远利益，可以采取各种有效的方法，甚至可以

37、暂时做赔本买卖。甚至可以暂时做赔本买卖。2022-4-1773协商模型协商模型Zlotkin的面向领域的协商理论的面向领域的协商理论Zlotkin的协商理论假设：的协商理论假设： 各主体追求本身效用最大。各主体追求本身效用最大。 知识完备。知识完备。 无历史信息。无历史信息。 目标集固定。目标集固定。 协商在两主体之间同时进行。协商在两主体之间同时进行。 主体操作集相同。主体操作集相同。 世界仅当主体操作之后发生变化。世界仅当主体操作之后发生变化。2022-4-1774面向领域的协商理论面向领域的协商理论在协商过程中，若存在一个双方满意的分配，在协商过程中，若存在一个双方满意的分配，可以得到一

38、个联合规划可以得到一个联合规划, , 使协商终止的条件使协商终止的条件是：是：(1) (1) 达成协议：如果达成协议：如果 Utility(P(i,t) Utility(P(i,t) Utility(P(i,t-1), Utility(P(i,t-1), 这一协商过程将在有这一协商过程将在有限步内结束。限步内结束。(2) (2) 冲突：冲突： 如果如果 Utility(P(i,t) = Utility(P(i,t) = Utility(P(i,t-1), Utility(P(i,t-1), 则无法达成协议。则无法达成协议。2022-4-1775最佳平衡最佳平衡 传统的协商是基于传统的协商是基于

39、Nash平衡的平衡的,它的缺点是它的缺点是Nash 平衡产生多个平衡点平衡产生多个平衡点, 对结果约束较少。对结果约束较少。Kraus使用使用Rubinstein的的“最佳最佳”平衡平衡(Perfect Equilibrium, 简称简称P.E.)理论理论, 建立了一种基于建立了一种基于P.E.的协商方法的协商方法, 需要在协需要在协商的任一阶段都产生平衡商的任一阶段都产生平衡, 即在协商的任一阶段即在协商的任一阶段, 假设假设 主体主体 A 使用使用P.E. 策略策略, 则则 主体主体 B 除了自己的除了自己的 P.E., 策略外没有更好的策略可遵循。故若策略外没有更好的策略可遵循。故若有唯

40、一的有唯一的 P.E., 并假定主体要使用该策略并假定主体要使用该策略, 则它在协商的每一阶段都只用则它在协商的每一阶段都只用这一策略。可证明这一策略。可证明, 存在唯一的存在唯一的 P.E.,在第一阶段后就可以终止协商。在第一阶段后就可以终止协商。Kraus 还将对时间的偏好引入这一理论中。结果表明还将对时间的偏好引入这一理论中。结果表明, 时间偏好可以提时间偏好可以提高协商效率高协商效率, 并仅对某一主体有利。并仅对某一主体有利。 这一理论对于主体的构造和主体之这一理论对于主体的构造和主体之间的协作很有用处间的协作很有用处, 如果为主体提供唯一的如果为主体提供唯一的P.E.策略策略, 并通

41、知其他主体并通知其他主体, 则则其他主体的最佳选择也是其他主体的最佳选择也是 P.E. 策略。策略。 该理论的缺陷是该理论的缺陷是:缺乏动态性特色缺乏动态性特色,应用面窄应用面窄,因为尽管存在唯一的因为尽管存在唯一的P.E, 但如但如何求出仍未得到解决。何求出仍未得到解决。2022-4-1776集中式协商方法集中式协商方法 Ephrati使用了一种集中式的协商方法使用了一种集中式的协商方法, 用一个用一个“ master agent ”或组投票机制以达成协议。在这或组投票机制以达成协议。在这种方法中种方法中, 一组主体的协作与组规划进程相关。一组主体的协作与组规划进程相关。 Ephrati使用

42、一种动态的、迭代的搜索过程使用一种动态的、迭代的搜索过程, 通过一通过一组约束组约束,使主体递增式地构成一个最大使主体递增式地构成一个最大“社会效用社会效用”规划。在每一步规划。在每一步, 各主体对于组规划的下一个联合各主体对于组规划的下一个联合行动投票。行动投票。 使用这一技术使用这一技术,主体无需完整地展示其主体无需完整地展示其偏好偏好, 可选状态集在投票之前产生。可选状态集在投票之前产生。2022-4-1777开放环境多智能体协作方法开放环境多智能体协作方法 Osawa (1) 需求者(requestor)向公告板主体发送需求建议RFP (2) 空闲主体向公告板主体申请一个RFP (3)

43、 公告板将RFP发到提出申请的空闲主体 (4) 空闲主体产生个体规划 (5) 空闲主体将其规划发给需求者 (6) 需求者调查协作的可能 (7) 需求者发送协作奖励 (8) 申请者组成协作规划2022-4-1778开放环境多智能体协作方法开放环境多智能体协作方法其效用值可用下式计算：其效用值可用下式计算： utility(a,g)=worth(a,g)-cost(plan(a,g) 效用的平均是协作的原则。效用的平均是协作的原则。 尽管尽管Osawa在一定程度上解决了开放环境中主体协在一定程度上解决了开放环境中主体协作的问题作的问题,但将各主体效用简但将各主体效用简单相加再平均的方法仍然太弱单相加再平均的方法仍然太弱, 因为主体效用仅是主体因为主体效用仅是主体本身对目标偏好的一种排序本身对目标偏好的一种排序关系关系,不同主体效用一般不能用数值比较。不同主体效用一般不能用数值比较。2022-4-1779交互协议交互协议主体之间的会话常常形成典型模式，这种情况下某些消息序列是可知的，这些消息交换的典型模式称为协议。主体间交互的理想情况：主体充分地理解消息的含意和意图，然后根据自身的信念、目标等心智状态，做出相应的回答比较实际的实现：预先规范这些协议，规定好消息的顺序。2022-4-1780FIPA 英国拍卖协议2022-4-1781演讲完毕，谢谢观看！