浙江大学计算机学院研究生人工智能引论课件ppt课件.ppt

《浙江大学计算机学院研究生人工智能引论课件ppt课件.ppt》由会员分享，可在线阅读，更多相关《浙江大学计算机学院研究生人工智能引论课件ppt课件.ppt（89页珍藏版）》请在三一文库上搜索。

1、1,浙江大学计算机学院研究生人工智能引论课件,第13讲 智能Agent及多Agent系统 Chapter 13 Intelligent Agent & Multi-Agent Systems 徐从富 浙江大学人工智能研究所 2003年第一稿 2005年10月修改补充 2007年10月第二次修改,2,内容,概述 2. 分布式问题求解 3. Agent 4. Agent理论 5. Agent结构 6. Agent通信 7. Agent的协调与协作 8. 多Agent环境MAGE 9. 面向Agent的软件技术 Mobile Agent 若干前沿问题讨论,3,13.1 概述,分布式人工智能（DAI）

2、主要研究在逻辑上或物理上分散的智能系统如何并行的、相互协作地实现问题求解。 两种解决问题的方法： 自顶向下：分布式问题求解 自底向上：基于Agent的方法,4,DAI系统的特色,系统中的数据、知识, 以及控制不但在逻辑上, 而且在物理上是分布的, 既没有全局控制, 也没有全局的数据存储。 各个求解机构由计算机网络互连, 在问题求解过程中, 通信代价要比求解问题的代价低得多。 系统中诸机构能够相互协作, 来求解单个机构难以解决, 甚至不能解决的任务。,5,DAI系统的主要优点,提高问题求解能力 提高问题求解效率 扩大应用范围 降低软件的复杂性,6,13.2 分布式问题求解,特点： 数据、知识、控

3、制均分布在系统的各节点上，既无全局控制，也无全局数据和知识存储。 两种协作方式： 任务分担 结果共享,7,13.2.1 分布式问题求解系统分类,根据组织结构，分布式问题求解系统可以分为三类： 层次结构类 平行结构类 混合结构类,8,13.2.2 分布式问题求解过程,分布式问题求解过程可以分为四步： 任务分解 任务分配 子问题求解 结果综合,9,分布式问题求解系统中协作的分类,按节点间协作量的多少，协作分为三类： 全协作系统 无协作系统 半协作系统 常用的通信方式有： 共享全局存储器 信息传递 黑板模型,10,13.3 智能Agent及多Agent系统,多Agent系统主要研究在逻辑上或物理上分

4、离的多个Agent协调其智能行为，即知识、目标、意图及规划等，实现问题求解。可以看作是一种由底向上设计的系统。,11,Agent的思想,智能Agent的几个典型的实例： Microsoft的Office助手 计算机病毒（破坏Agent） 计算机游戏或模拟中的智能角色 贸易和谈判Agent（如Ebay的拍卖Agent） 网络蜘蛛Web Spider（搜索引擎中的数据搜集和索引Agent，如Google）,12,Agent概念的出现,面向过程的方法,面向实体的方法,面向对象的方法,面向Agent的方法,软件开发方法的进化,13,Agent的定义,在计算机和人工智能领域中，Agent可以看作是一个实

5、体，它通过传感器感知环境，通过效应器作用于环境。,14,Agent的强定义,基于某种场景，并具有灵活、自主的行为能力，以满足设计目标的计算机系统。,15,Agent的弱定义,满足如下特征的基于硬件或（更经常是）软件的计算机系统： 自主性(Autonomy) 社会性(Social ability) 反应性(Reactivity) 主动性(Pro-activeness)（或称“前 瞻性”） 基于场景性(Situatedness) 灵活性(Flexibility),16,移动性(Mobility) 理性(Rationality) 此外，许多学者还提出一些其它特性： 诚实性(Veracity) 友好性

6、(Benevolence) 长寿性（或时间连贯性） 自适应性(Adaptability),17,Agent的特性,Agent弱概念： 自治性、社会能力（可通信性）、反应能力、自发行为 Agent强概念： 知识、信念、意图、承诺等心智状态 其它属性： 长寿性、移动性、推理能力、规划能力、学习和适应能力、诚实、善意、理性,18,13.4 Agent理论,智能Agent的理论模型研究主要从逻辑、行为、心理、社会等角度出发，对智能Agent的本质进行描述，为智能Agent系统创建奠定基础。,19,可能世界模型(Possible Worlds Model),地位：Agent理论基础的开创性工作之一。思想

7、：将Agent的知识、信念等特征化为一 系列“可能世界”，在可能世界模型中包括对象、属性及其关系。 优点：理论基础（特别是模态逻辑）比较完善。 缺点：存在“逻辑万能”(Logical Omniscience)问题。,20,“意图系统”(Intentional System),作用：用于描述其行为可用信念、愿望等理性智慧来预测的实体。分为：一阶和二阶两种形式。对象、属性及其关系。,21,“意图姿态”(Intentional Stance),意义：启发AI学者将信念(Belief)、愿望(Desire)、承诺(Commitment)等人类特有的思想和概念应用于Agent。,22,13.4.1 理性

8、Agent（BDI模型）,思想：认为Agent行为可由信念、愿望和意图来表达 作用：已成为经典模型，并被广泛采用 Belief信念，Agent对环境的基本看法。 Desire愿望，Agent想要实现的状态，即目标。 Intention意图，目标的子集。,23,13.4.2 BDIAgent模型,BDIAgent模型可以通过下列要素描述： 一组关于世界的信念； Agent当前打算达到的一组目标； 一个规划库，描述怎样达到目标和怎样改变信念； 一个意图结构，描述Agent当前怎样达到它的目标和改变信念。,24,BDI解释器,BDI-Interpreter initialize-state(); d

9、o options := 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 quit,25,13.4.3 RAO逻辑框架,目标：以一种自然的方式描述多Agent系统

10、中关于别的Agent的状态的推理过程。 系统的分类：由于多Agent系统太复杂，建立一种通用的推理模式的想法是不现实的，有必要对系统分类以便区别对待。 常识的获得：和单个Agent情形一样，常识问题是阻碍推理的大难题。,26,13.4.4 换位推理,思想：模仿语言学中的虚拟语气，即为了对某个Agent在某种场景下的状态或行为进行推测，设想自己处于那种场景时的状态或行为，再把这种设想结果作为被猜测Agent的状态或行为。 作用：使得一Agent对其它Agent的状态和行为的推理过程变得简单明了。,27,13.4.5 动作理论,情景演算是描述动作的主要的形式框架。 在情景演算中引入了状态和动作的概

11、念，并利用两条逻辑公理来描述动作与状态的关系。一条公理描述一个动作在满足什么条件的状态之下可能发生，另外一条描述在一个状态之下某个动作发生以后当前状态如何改变。,28,13.4.6 “言语行为”理论(Speech Acts Theory),地位：这是多Agent交互（通信）的重要理论基础之一。 思想：任何行为都可以等价地表示为言语行为（既任何行为的含义都可用言语来表达），甚至认为所有的行为都是言语行为。 作用：大大简化了Agent之间交互的复杂度。,29,规划库的形式化表示,环境状态： State = P1, P2, Pn 目标： Goal= 动作模板： Act_template = Agen

12、t能力： Ability=,30,13.5 Agent结构,Agent结构需要解决的问题包括： Agent由那些模块组成， 模块之间如何交互信息， Agent感知到的信息如何影响它的行为和内部状态， 如何将这些模块用软件或硬件的方式组合起来形成一个有机的整体。,31,Agent基本结构,环境,Agent,感知,作用,黑箱软件Agent,32,智能Agent的工作过程,环境,交互,信息融合,信息处理,作用,交互,感知,作用,33,Agent骨架程序,function Skeleton-Agent(percept) return action static: memory /* Agent的世界记

13、忆 */ memory Update- Memory(memory,percept) action Choose-Best-Action(memory) memory Update-Memory(memory,action) return action,34,Agent的分类,根据人类思维的层次模型，可以将Agent分成四类： 反应Agent 形象思维Agent 抽象思维Agent 复合式Agent 形象思维Agent和抽象思维Agent也可以合称为认知Agent,35,13.5.1 反应Agent,环 境,当前世界,传感器,动 作,效应器,条件-动作 规则,Agent,36,反应Agent程

14、序,function Reactive-Agent(percept) returns action static: rules, /* 一组条件-动作规则 */ state Interpret-Input(percept) rule Rule-Match(state,rules) action Rule-Actionrule return action,37,13.5.2 认知Agent,环 境,信息融合,传感器,动 作,效应器,Agent,规 划,知识库,目标,内部状态,38,认知Agent程序,function Cognitive-Agent(percept) returns action

15、 static: environment, /* 描述当前世界环境 */ kb, /* 知识库 */ environment Update-World-Model(environment,percept) state Update-Mental-State(environment,state) action Decision-Making(state,kb) environment Update-World-Model(environment,action) return action,39,BDI结构,知 识,信 念,规 划,意 图,目 标,愿 望,40,13.5.3 复合式Agent,决策

16、生成,规 划,反 射,建 模,通 信,感 知,行 动,其他 智能Agent,智能Agent,外部世界,预测,协作与协商,动作,请求或应答信息,一 般 情 况,紧急情 况和简 单情况,41,规划模块,世界的模型 （包括其他 Agent的模型）,经 验 库,目标集合,局 部 规 划 器,决 策 生 成,重新 规划,规划,规划,目标,42,建模模块,世界的模型 （包括其他 Agent的模型）,模 型 库,模 型 生 成 和 维 护,预 测,规划,决策生成,感 知,通 信,建模,43,通信模块,词 法 库,语 法 库,词 义 库,物理通信,语言生成,语言理解,通信,44,13.6 Agent通信,策

17、略,对 话,消 息,黑 板,协 议,通 信,协 作,协 议,45,Agent通信中的主要问题,语义：全部有关的Agent必须知道通信语言的语义，消息的语义内容知识是分布式问题求解的核心部分。 言语行为：通信语言也是一种动作，说话是为了使世界的状态发生改变。 交互协议：Agent之间消息交换的典型模式 通信语言：传递消息的标准语法。 Foundation for Intelligent Physical Agents http:/www.fipa.org,46,Agent间的消息传递,消息发送/传输服务器,转换到传输格式,从传输格式转换,消息M,言语行为,意图I,目标G,Agent i,消息M,

18、Agent j,47,本体论（Ontology）,本体论是概念化的明确的表示和描述。 对某一领域中的概念有共同理解，可以提高交流和协作的效率，从而提高了软件的重用性。,48,言语行为,有关言语行为理论的研究主要集中在如何划分不同类型的言语行为。 在Agent通信语言的研究中，言语行为理论主要用来考虑Agent之间可以交互的信息类型。,49,FIPA通信动作库,Accept Proposal 接受提议 Agree 同意 Cancel 取消 Call for Proposal 要求提议 Confirm 确认 Disconfirm 确认为否定 Failure 失败 Inform 通知 Inform

19、If 通知 是否 Inform Ref 通知 有关对象 Not Understood 不理解,50,Propagate 传播 Propose 提议 Proxy 代理 Query If 询问 是否 Query Ref 询问 有关对象 Refuse 拒绝（请求） Reject Proposal 拒绝提议 Request 请求 Request When 请求 某个条件下执行 Request Whenever 请求 一旦某个条件成立就执行 Subscribe 预定 详细说明： http:/www.fipa.org/repository/cas.html,51,交互协议,Agent之间的会话常常形成典型

20、模式，这种情况下某些消息序列是可知的，这些消息交换的典型模式称为协议。 Agent间交互的理想情况：Agent充分地理解消息的含意和意图，然后根据自身的信念、目标等心智状态，做出相应的回答 比较实际的实现：预先规范这些协议，规定好消息的顺序。,52,FIPA 英国拍卖协议,53,通信语言,KQML：由美国ARPA的知识共享计划中提出，规定了消息格式和消息传送系统，为多Agent系统通信和协商提供了一种通用框架。 ACL：由FIPA制定的一种规范。与KQML非常相似,54,KQML,一个例子： (ask-all : sender A : receiver B : in-reply-to ido

21、: reply-with idl : language Prolog : ontology foo : content “bar (X, Y)”),55,FIPA 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 ),消息结构开始,通信动作类型,消息参数,消息内容表达式,参数表达式,56,XMLeXtens

22、ible Markup Language 可扩展标记语言,XML是用于标记电子文件使其具有结构性的标记语言。XML文件本身只是将文件资料结构化。 例如：下面的ACL消息 (inform :sender jklabrou :receiver grosof :content (CPU libretto50 pentium) :ontology laptop :language kif),57,转换为XML格式后如下： inform jklabrou grosof ,58, laptop (CPU libretto50 pentium) kif ,59,13.Agent的协调与协作,协调(coord

23、ination)与协作(cooperation)是多Agent研究的核心问题之一。 协调是指一组智能Agent完成一些集体活动时相互作用的性质。 协作是非对抗的Agent之间保持行为协调的一个特例。,60,协调,多Agent系统中的协调是指多个Agent为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望避免Agent之间的死锁或活锁。 死锁指多个Agent无法进行各自的下一步动作； 活锁指多个Agent不断工作却无任何进展。,61,协作,目前针对Agent协作的研究大体上可分为两类： 将其它领域研究多实体行为的方法和技术用于Agent协作的研究。如对策论和力学研究。 从Agent的目标

24、、意图、规划等心智态度出发来研究多Agent间的协作。,62,协作规划,协作的动机： 某个Agent相信通过协作能带来好处（如提高效率，完成以往单独无法完成的任务） 多个Agent在交流的过程中，发现它们能够通过协作来实现更大的目标。,63,协作过程,产生需求、确定目标 协作规划、求解协作结构 寻求协作伙伴 选择协作方案 实现目标 评估结果,64,13.8 多Agent环境MAGE,MAGE的主要特点： 运行于分布式网络环境 用java编写 使用模块化的能力 通过ADL来描述并生成Agent Agent之间通过ACL通信,65,13.9 面向Agent的软件技术,在面向Agent的软件开发方法

25、中，应用程序编写为软件Agent，这些Agent之间通过Agent通信语言可以进行比普通消息传递更规范、更明确的通讯。,66,Agent与对象的异同,共同点： 都具有封装性、继承性和多态性。 对象的内部状态映射为Agent的心智状态。 互操作。 不同点： Agent具有自治性，对象只能被动的被调用。 Agent之间交互使用通信语言，对象之间交互是通过互相调用方法。,67,AO与OO,对象是对现实世界中的被动实体的抽象，Agent是对主动实体的很好的抽象。 Agent支持用于表示智能的结构，如信念、承诺等。 Agent支持基于言语行为理论的高级交互，不同于对象之间频繁的消息发送和接收。 对象是通

26、过外部来进行控制的（白箱控制），相反，Agent有自治性，不能直接从外部进行控制（黑箱控制）。,68,主要的基于Agent的方法,Gaia方法：Wooldridge，Jennings和Kinny在1999年提出了面向Agent分析与设计的Gaia方法学。 多Agent工程方法学：Wood和DeLoach提出了多Agent工程方法学MaSE。 AUML： Odell等人提出了对UML语言的扩充AgentUML语言AUML语言。,69,Gaia方法,Gaia是一种同时支持微观级（Agent结构）和宏观级（Agent社会与组织结构）的Agent开发的一般方法。 分析过程 第一步是找到系统中的角色，

27、第二步是对角色之间的交互进行建模。每个角色包含四个属性：责任、许可、活动和协议 设计阶段 第一步是把角色映射到一定的Agent类型，然后对不同的Agent类型创建适当的Agent实例； 第二步是确定一个和多个Agent中角色所需要的服务模块； 最后一步是为Agent之间的通信表示建立熟人模块。,70,MaSE,MaSE在一般性及应用领域上类似于Gaia，MaSE的目的是引导设计者怎样从初始的系统规范说明到Agent系统的实现。 MaSE在逻辑上被分为七段流水线：捕获目标、应用用例、精练角色、创建Agent类、构造会话、编译Agent类、系统设计。,71,AUML,Odell、Parunak和B

28、auer提出了Agent交互协议AIP的三层表示方法。该方法不仅需要表达语义的修改，而且需要UML可视化语言的修改。 AUML已经被提交给UML标准委员会，作为一个建议包含在UML2.0中。,72,13.10 Mobile Agent,l 节约网络带宽 移动Agent直接在数据端执行处理,与客户端不需要进行中间结果的传输,只返回最后的结果。 l 提供实时的远程交互 在一些远程控制系统中，如外太空探测器的控制、网络的时延使得远程实时控制变得不可能，发送Mobile Agent实行远端的本地控制可解决该问题。,73,l 支持离线计算 用户派遣出Mobile Agent程序后，可以断开网络连接，而A

29、gent将在网络上自主运行。Agent完成任务后，当它发现用户设备重新连上网络时，就返回计算结果。 l 实现载荷卸载 对于一些计算能力弱的设备，如个人数字助理，可以把计算打包成Agent程序，发送到计算能力强的设备上进行计算。,74,l 提供定制化服务 使用Agent，客户端可以根据服务器端提供的底层操作函数，编写满足自己特定需要的服务程序，然后发送到服务器端运行。 l 易于分发服务 在采用Mobile Agent技术的分布式应用中，服务的更改变得非常简单，比如在电信网的管理中，当业务需要改变时，只需把新的服务程序发送到相应的服务节点上，用不着人力去一个一个节点地安装。,75,l 增加应用的强

30、壮性 移动Agent的工作方式减少了应用对网络连接可靠性的要求，它的自主性又使它具备对环境的反应能力，因此能建立更容错的分布系统。 l 提供平台无关性 移动Agent是跨平台运行的。移动代理应用编程不存在程序的移植问题，便于应用的快速开发。 l 提供更自然的电子商务模式 用移动Agent代表用户参与电子交易，买家可在网上自由寻找卖者，查询商品种类，商谈价格，卖家也可主动上门向买家推荐商品。,76,13.11 若干前沿问题讨论,当前AI中存在的“鸿沟” 解决“鸿沟”的主要思路 完全自主Agent 完全自主Agent的关键技术 完全自主Agent的典型应用,77,13.11.1 当前AI中存在的“

31、鸿沟”,Stuart J. Russell的观点 在1995年获得IJCAI-95的“Computers and Thought Award”杰出青年大奖时所作的学术报告Rationality and Intelligence 指出“AI是一个由其研究的问题而非方法所定义的领域。”（“AI is a field defined by its problems, not its methods.” Stuart J. Russell, 1995）,78,当前AI中存在的“鸿沟”（续1）,当前，AI中存在的最大问题是：如何填补基于抽象、非底层表示（Ungrounded representation

32、s）的高层推理（High-level reasoning）与建立底层表示（Grounded representations）的传感数据解释（Interpreting raw sensor data）之间的“鸿沟”。,79,当前AI中存在的“鸿沟”（续2）,2001年，Stanford大学计算机系的年轻教授Daphne Koller在获得IJCAI-01的“Computers and Thought Award”杰出青年大奖时所作的学术报告 传统AI中被广泛采用的分析、分解方法正面临着很大的挑战：在解决复杂问题时，人们往往很自然地采用分而治之的方法，将其分解为每个“小片”（Fragmentati

33、on），等每个“小片”都取得进展后，再进行综合集成以得到最终的结果。但遗憾的是，往往每个子问题都各自分家且相互远离，而且是离得越来越远，最后很难将它们综合集成起来。,80,当前AI中存在的“鸿沟”（续3）,“In AI, as in many communities, we have the tendency to divide a problem into well-defined pieces, and make progress on each one. But as we make progress, the problems tend to move away from each o

34、ther.” Daphne Koller, 2001,81,13.11.2 解决鸿沟的主要思路,Daphne Koller教授围绕着如何解决上述问题（即填补高层推理与底层数据解释之间的“鸿沟”），提出一种解决方法，就是建立连接的三座“概念桥梁”（Conceptual bridges），分别是： 表示（Representation） 推理（Reasoning） 学习（Learning）,82,解决鸿沟的主要思路（续1）,另一种代表性的解决方法是，美国德克萨斯大学奥斯汀分校（University of Texas at Austin）的Peter Stone在2007年获得IJCAI-07的“Co

35、mputers and Thought Award”杰出青年大奖时所作的学术报告 Peter Stone. Learning and multiagent reasoning for autonomous agents. In: Proceedings of 2007 International Joint Conference on Artificial Intelligence (IJCAI-07), pp.13-30.,83,解决鸿沟的主要思路（续2）,建立完全自主的Agents（Complete autonomous agents），这些Agents具有高度的鲁棒性和灵活性，它们可感知

36、环境，进行高层认知和决策，在环境中进行自主执行，即具有学习、交互、组合及合作等能力。他认为这种研究方法可分为两条基本路线： 基本算法研究，主要包括机器学习、多Agents系统（MAS）； 应用研究，主要包括实现面向特定的复杂环境的完全自主Agents，以及从面向特定应用的自主Agents实现中总结发现普遍规律。,84,解决鸿沟的主要思路（续3）,美国华盛顿大学的Pedro Domings教授提出的马尔可夫逻辑网络（Markov Logic Networks） 将谓词逻辑与统计学习方法有机地结合起来 可填补AI中存在的高层与底层之间的鸿沟,85,13.11.3 完全自主Agent的关键技术,Pe

37、ter Stone还指出，自从1983年Tom Mitchell获得“Computers and Thought Award”杰出青年大奖并做了关于机器学习的学术报告后，从机器学习的观点来看，面向分类和预测的有监督学习（Supervised learning）方法得到了极大发展，并涌现出很多通用的工具包。同时，面向数据聚类的无监督学习（Unsupervised learning）方法也取得了很大进展。 然而，从自主Agents的观点来看，最近出现的增强学习（Reinforcement learning）似乎更加重要，因为增强学习在很多序列决策问题中能够自主收集所需要的训练数据，学习到将状态映射

38、为行为的策略，并从延迟奖赏中（Delayed reward）学习如何选择正确的行为，它实现了探索（Exploration）与开发（Exploitation）之间的权衡。,86,13.11.4 完全自主Agent的主要应用,Peter Stone给出了当前完全自主Agents的四个主要应用领域，分别是： 足球机器人（Robot soccer） 无人驾驶车辆（Autonomous vehicles） 拍卖Agents（Bidding agents） 自主计算（Autonomic computing）。 其中，机器人足球和无人驾驶车辆是属于“物理Agents”（Physical agents），而拍

39、卖Agents和自主计算则属于“软件Agents”。这些应用充分展示了机器学习与多Agents推理的紧密结合，它涉及自适应及层次表达、分层学习、迁移学习（Transfer learning）、自适应交互协议、Agent建模等关键技术。,87,课外阅读论文（可选12篇）： Wooldridge M, Jennings N R. Intelligent agents: theory and practice. Knowledge Engineering Review, 1995, 10(2): 115-152 Jennings N R, Sycara K, Wooldridge M. A road

40、map of agent research and development. Autonomous Agents and Multi-Agent Systems. Boston: Kluwer Academic Publishers, 1998, 275-306 Peter Stone. Learning and multiagent reasoning for autonomous agents. In: Proceedings of 2007 International Joint Conference on Artificial Intelligence (IJCAI-07), pp.1

41、3-30,88,其它值得研读的论文（可选）： Intelligent agents: theories, architectures, and languages. Mobile software agents: an overview. A mobile agent based service architecture for Internet telephony. A mobile agent-based advanced service architecture for wireless Internet telephony: design, implementation, and evaluation. Intelligent agents on the Web: a review. 【注】：上述论文一般均可通过google搜索到。,欢迎批评指正， 谢谢！,