自动化科学与技术(杨宜民)第7章.ppt

自动化科学与技术,第七章 人工智能(二-DAI),杨宜民,研究生示范课程课件,7.1 概述 7.1.1 研究背景及研究意义 20世纪80年代末出现了人工智能（AI）基础的反思辩论。Brooks构造的机器虫表明无需知识表示及无需理性智能，但其应付复杂环境的能力可以超过现有的一些机器人。这以及AI研究中遇到的困难使人们认识到解释和模拟人类智能、智能行为及其规律，建立智能系统是长远的目标。而已有的AI方法和技术只能处理一些较为成型的问题，如利用成功的经验知识进行问题求解。对开放的动态现实环境，在没有现成方法可用时，专家系统就显得无能为力，依靠无限地加大知识库的CYC计划目前只停留在探索阶段。因此，有必要研究新的理论、方法和技术，以促进AI的向前发展。,第七章 人工智能（二-ADI）,20世纪80年代分布式人工智能（DAI）提出后，很快成为研究热点。1996年Minsky提出了“Agent”概念，认为社会中的某些个体（Agent）经过协商之后可以求得问题的解，这些个体具有社会交互性和智能性。此后，Agent和多Agent系统（Multi-Agent Systems多Agent系统）的研究就很快发展起来，认为这一研究能促进AI向前发展，并把AI推向一个新的台阶。 由此可见，多Agent系统研究是AI研究过程中碰到困难和问题时而出现的，希望通过对它的研究来解决现有的AI方法和技术不能解决的问题，进一步深化AI的理论、方法和技术，并发展AI的应用。因此，多Agent系统的研究具有重大的科学意义和价值。,7.1.2 应用领域,多Agent系统是由多个可以相互交互的Agent组成的系统。每个Agent在某种程度上是自治的，Agent之间的交互不但可以进行数据交换，而且可以进行合作，并决定各自的行动以完成任务。一开始，Agent作为软件工程的一种新风格引起人们的兴趣。随着计算技术的发展，开发基于Agent的软件技术是目前对计算技术的最大挑战，因为它为研究和使用大规模分布式开放系统（如Internet）提供了可能性。但是多Agent系统的作用远不止此。多Agent系统的思想并不局限于某个特定的领域，它能理解和构建各种人工社会系统。因此，多Agent系统理论和技术可以应用在许多不同的领域：,工业中的计算机集成制造系统、虚拟企业等； 军事的指挥决策支援系统； 交通的智能管理与控制； 电力系统中的智能调度与安全保护； Internet网的信息管理； 电子商务、商业过程管理与金融业务管理； 医学应用中的患者监控和医疗保健； 在娱乐方面的应用。,7.1.3 国内外的研究概况 7.1.3.1 国外研究概况 1986年Minsky在思维的社会一书中提出了“Agent”概念，认为社会中的某些个体（Agent）经过协商后可以求得问题的解。1988年Bratman给出BDI模型的概念框架，讨论了意图在实用推论中的作用问题，并给出了BDI型Agent的结构（称为IRMA）。1986年Brooks研究了反应型Agent结构。Agre和Chapman所研究的PENGI系统、Rosenschein和Kaelbling所研究的情景自动机等都对反应型Agent结构作了较深入的研究。Innes Fergusion所研究的Touring机和Jorg Muller的InteRRaP都对混合型Agent结构作了较深入的表述。,1980年Smith提出合同网（Contract Net）方法用作商务管理的合作机制。Mellon大学提出黑板模型，并研制了黑板系统HEARSAY-II，它解决语言理解问题。Smith和Davis提出了结果共享的合作问题求解模型。Lesser和Corkill等人提出功能精确的协同方法（FA/C），它提供了不确定环境下多Agent间动态合作求解的一种方法。Lesser、Erman、Corkill等人研制的分布式车辆监测测试床（DVMT）是全工化的开发分布式问题求解网络的测试床，它采用部分全局规划（PGP）的方法。此外，Levesque等人还研究了通过联合意图的协调、相互模仿的协调、规范和社会法律的协调等合作机制和方法。,KQML和KIF是两个已开发了的多Agent系统通信语言，并由FIPA机构对其进行标准工作。Kraus、Sierra、Sandholm和Makoto等人研究了以Agent为介质的电子商务的理论基础，并研究了在电子商务中的应用。称为“OASIS”的航空运输控制系统已在悉尼机场进行过现场试验。澳大利亚皇家空军的称为“SWARMM仿真系统”、称为“SPOC”的商务管理系统已在市场中出售。ADEPT系统是基于Agent的业务过程管理系统，目前得到较广泛的应用。以“机器人足球比赛系统”作为多Agent系统的研究和应用平台，日本的北田和韩国的金钟焕分别发起“RoboCup”和“FIFA”系列机器人足球比赛，近七、八年来已有近30个国家参加。,7.1.3.2 国内研究概况 陆汝铃院士提出联合黑板模型用于问题求解。张维明、姚莉等研究了多Agent系统在信息处理、智能办公系统中的应用。石纯一、吴启迪等研究了多Agent系统在现代制造中的应用。中国科技大学、重庆大学等7、8个单位从事多Agent系统在Internet中的应用研究。武汉大学、华南理工大学研究了多Agent系统在电力系统中的应用。东北大学、哈工大、广工大、中国科大、清华大学、上海交大等全国30多间高校通过机器人足球比赛系统对多Agent系统进行研究。 7.1.3.3 国内外达到的水平 从上述的介绍可以看到：国内外对Agent的理论模型已作了较深入的研究，对Agent之间的合作机制和方法、实现工具和应用作了一定研究，一些基于多Agent系统技术的系统已推向市场并得到应用。,7.2 多Agent系统的基础 7.2.1 Agent及多Agent系统的定义 7.2.1.1 Agent（Agent）的定义 Agent的定义有三种： Agent是指能在某一环境中运行，并能影响环境的变化，灵活、自主地采取行动，以满足其设计目标的计算实体。 Agent是能在某个环境中自主行动，以实现设计目标的计算机系统。 Agent是一个物理体或虚拟体，它 能和其它Agent进行通讯。 由一组意向（tendencies）所驱动（以各个对象的形式或以试图达到最佳的满足/生存函数的形式）。 能对环境起作用。 只能感知和表示局部环境。 拥有自己的资源。 具有一定技能，且能提供服务。 能自我复制。 其行为是力求目标得到满足（取决于它拥有的资源、技能、感知、表示及收到的信息）。,图7.1 Agent的概念图,7.2.1.2 多Agent系统（Multi-Agent Systems）的定义 多Agent系统的定义有两种： 它是由分布在网络上的多个Agent松散耦合而成的复杂系统，这些Agent相互作用以解决单个Agent所不能解决的问题。 多Agent系统又称为多Agent系统，它是由下列元素所组成的系统。 环境E. 即通常拥有一定空间。 对象集O. 这些对象在某一时刻有可能和环境E中的任何其它对象相联系。这些对象又是被动的，它们可能由Agent所感知、构建、毁坏和修改。 Agent集A. 它们是特殊的对象（ ），是系统中有源的实体。 关系集R. 它们把对象与对象、对象与Agent、Agent与Agent相结合起来。 操作集 它使Agent集A可以感知、生产、消耗、改变和操作对象 操作子. 它表示这些操作的应用和这一企图的世界反应，又称为世界律。,7.2.2 Agent及多Agent系统的分类 7.2.2.1 Agent的分类 Agent可分为理想Agent、智能Agent、软件Agent。 a) 理想Agent. 具有认识和理解世界环境的能力、问题求解能力、学习能力、自我适应能力和解决大型复杂问题的协作能力等五种能力。 b) 智能Agent. 是指能在某一环境中运行、并能响应环境的变化，灵活自主地采用行动以满足其设计目标的计算实体。 c) 软件Agent. 是一种在特定环境中连续、自主地运行的软件实体，通常与其它Agent一起联合解决问题。,Agent又可分为BDI型Agent、反应型Agent、混合型Agent。 BDI型AgentBelief-信念，Desire-愿望，Intention-意图，又称为慎思型Agent、实用推理Agent. 实用推理是权衡不同观点中的矛盾，这些不同的观点来自Agent的愿望、评价、关心问题以及Agent所相信的事情。实用推理由两个行为所组成：第一个行为称为慎思，它决定想要达到的状态；第二个行为称为手段目的推理，它决定为如何实现这些状态。 b)反应型Agent又称为归类式结构Agent. 首先，Agent是通过一个完成任务的行为集合来实现决策的，每一种行为都被看成一个单独的Action函数，可简化为情景动作。其次，很多行为可以同时“触发”,即进行。 c)混合型Agent. 具有反应行为能力和预动作能力（慎思）的Agent。,7.2.2.2 多Agent系统的分类 根据对动态性的适应性，多Agent系统可分为： a) 系统拓扑结构不变，即Agent的数目及其社会关系都不变的系统。 b) 系统拓扑结构可变，即Agent的数目及其社会关系都可变的系统。 根据系统功能结构，多Agent系统可分为： a) 同构型系统. 由功能结构相同的各个Agent所组成的系统。 b) 异构型系统. 由功能结构不同的各个Agent所组成的系统。 根据控制结构，多Agent系统可分为： a) 集中控制型系统. 由一个中心Agent负责整个系统的控制、协调工作。 b) 层次控制型系统. 每个Agent控制处于其下层的Agent的行为，同时又受控于其上层的Agent。 c) 网络控制型系统. 由信息传递构成控制结构，且该控制结构可灵活、动态地进行改变。,7.2.3 Agent的理论模型 7.2.3.1 BDI型Agent,图7.2 过程推理系统（PRS） PRS是由Stanford研究所开发的，是一个显式嵌入BDI模式的著名Agent结构，如图7.2所示 。,图7.3 GRATE* BDI Agent模型 GRATE*是由Jennings于1993年提出的，它与IRMA (Intelligent Resource Machine Architecture Bratman提出)相类似，它采用联合意图和联合责任来建立一个合作行为，并监控联合行为的执行，如图7.3所示 。,7.2.3.2 反应型Agent,图7.4 反应式Agent的理论模型,7.2.3.3 混合型Agent 混合型Agent同时具有反应行为能力和预动行为能力，至少应有二层，以分别加以处理。三种混合型Agent的理论模型如图7.5所示。,图7.5 三种混合型Agent的理论模型,水平层次结构的优点是概念上的简洁性：如果一个Agent表现有n种不同的行为，则可用n次来实现。但是，如果其结构有n层，每层可能有m种动作，则有mn种交互，此时，要求Agent有中心控制，其设计就显得困难而复杂。 垂直层次结构的层次交互复杂性降低：n层之间有n-1个接口，每层有m种动作，则有m2(n-1)种交互。但是，控制命令要经过每一层，任何一层的故障都会影响Agent的性能，其容错性差。,7.3 相互作用与通信 Agent间的相互作用(Interaction交互)是多Agent系统实现合作必不可少的。交互是通过通信来进行的。 言语行为理论直接提供和影响Agent通信语言的开发。美国DARPA资助的知识共享计划(KSE)发布两个主要文件： 知识查询与操纵语言(Knowledge Query and Manipulation Language KQML)。KQML是一种用作Agent通信的“外层”语言，它为消息定义了一个“信 封”格式，使用这个格式，Agent可以明显地说明一条消息不发音的言语想动 作的能力。 知识交换模式(KIF)。KIF是一种显式地对某特定的“谈论的领域”进行知识表示 的语言。它主要用于形成KQML消息的内容部分，也可单独使用。,美国智能物理Agent基金会(FIPA)也开发了Agent通信语言ACL。它与KQML相似：它定义消息的一个“外层”语言；定义了20种语用词，以规定对消息的预期解释；它没有为消息内容指定任何特定的语言；它的消息的具体语法与KQML非常相似。 Agent通信语言的明细可参考： 1 Michael Wooldridge著.石纯一等译.多Agent系统引论.电子工业版社, 2003.10 2 张维明主编.智能协作信息技术.电子工业出版社,2002.4,7.4 合作的基本原理和方法 7.4.1 合作的分类 根据Agent之间目标的关系以及合作的程度，合作可分为下列5种类型：完全合作型，合作型，自私型，完全自私型，合作与自私共存型。 a) 完全合作型. 系统中各个Agent没有自己的局部目标，所有Agent都围绕一个 共同全局目标全力以赴地合作。 b) 合作型. 系统中所有Agent具有一个共同的全局目标，同时每个Agent各具有 一个与全局目标一致的局部目标。 c) 自私型. 系统中不存在共同目标，各个Agent都为自己局部目标工作，且局 部目标可能存在冲突。 d) 完全自私型. 系统中不存在共同目标，各个Agent都为自己局部目标工作， 且不考虑任何合作行为。 e) 合作与自私共存型. 系统中既有一些共同的全局目标，某些Agent也可能具 有与全局目标无直接联系的局部目标。,7.4.2 合作机制 合作机制有协调、协同和协商三种。 协调(Coordination) 协调是指Agent对自己的局部行为进行推理，并估计其它Agent的行为，以保证行为以连贯的方式进行的一个过程。 Mintzberg提出三种基本的协调过程。 相互调整(Mutual Adjustment)是最简单的协调方式。它发生在多个Agent共享资源，以获得某个共同目标的多Agent系统系统中。此时，任何Agent没有优先权，决策是一个联合实现的过程。 直接管理(Direct Supervision)发生在一个Agent对其它Agent具有控制权的多Agent系统系统中。这种优先权关系通常是通过相互调整而建立。 标准化(Standardization)是常用的协调方式。在某些情况下，管理者通过标准化进行协调，即建立下属必须遵守的标准过程。公司中的操作规程以及计算机程序都是标准化协调的例子。,b. 协同(Cooperation) 一般情况下，协同是指多个Agent围绕一个共同目标而相互作用的合作过程。 Durfee提出协同的4个基本目标：通过并行性提高任务的完成效率；通过共享资源(信息、专家知识、物理设备等)扩展完成任务的范围；通过任务的重复分配增加任务完成的可能性；通过避免有害相互作用降低任务之间的干扰。 可用“协同度”定性刻画Agent的协同程度，其范围可从“完全协同”到“敌对”。,c. 协商(Negotiation) Durfee给协商下定义：协商是通过结构化地交换信息而改进有关共同观点或共同计划的过程，即 是合作各方为达成共识而减少不一致性或不确定性的过程。 协商是解决冲突的一种合作方法。Sycara认为在现实世界中，协商必须具有以下特性： 存在某些冲突，必须采用离散方式消除这些冲突。 自私Agent。 有限推理。 信息是不完全的。 在协商过程中，Agent间需通过通信反复地交流建议和反建议，还必须考虑信息的不完全性、多方协商、协商期限以及破坏合约的能力等问题。,7.4.3 合作方法 7.4.3.1 实用的合作方法 (a) 合同网法 合同网（Contract Net）方法是Smith于1980年提出的。其基本工作过程为图7.6所示。,在这种合作方法中，不需要预先规定Agent的角色，任何Agent通过发布任务通知书而成为管理者，任何Agent通过应答任务通知书而成为工作者。系统中的每一待求解任务，由承担该任务的Agent负责完成。当该Agent无法独立完成该任务时，就将该任务分解，并履行管理者的角色，为每一个子任务发送任务通知书；然后，从返回的投标书中选定最合适的工作者（Agent），与它建立合同。按合同执行子任务的工作者若不能独立完成该子任务，则这个工作者又需要扮演管理者的角色，将子任务继续分解，按照合同网的方法实行分配，如此进行下去，直到子任务能独立完成为止。可见，任务的分解分配过程形成一个动态的确定的树结构。,图7.6 合同网方法的基本工作工程,(b) 黑板模型法 黑板的概念最早由Newell提出。20世纪70年代，Carnagie-Mellon大学提出黑板的问题求解模型，并研制了语音理解系统HEARSAY-II。现已有多种改进形式，如陆汝铃院士的联合黑板等。 黑板模型方法的工作过程如图7.7所示。,图7.7 黑板模型的工作过程,在图7.7中，知识源（KS）是根据求解问题专门知识的不同而划分成的若干互相独立的专家（即Agent）；黑板是一个共享的问题求解工作空间；监控机制则根据黑板上的问题求解状态和各知识源的求解技能及某种控制策略，动态地选择和激活合适的知识源，使知识源能适时地响应黑板的变化。当问题和初始数据记录到黑板上时，问题的求解开始。所有专家（Agent）通过“看”黑板，寻找利用其专家知识求解问题的机会。当一个专家发现黑板上的信息足以支持它进一步求解问题时，它就将求解结果记录在黑板上。新增加的信息有可能使其他专家继续求解。重复此一过程，直到获得最终结果为止。,(c) 结果共享与功能精确法 * 结果共享法 结果共享的合作问题求解是由Smith和Davis于1981年提出的。其合作问题求解过程如图7.8所示。 在问题求解之前需进行任务的分解和分配。每当一个Agent求得某一个子问题的结果时，它根据合作知识判断哪些Agent需要这一结果，并将结果传送到相应的Agent。收到结果的Agent可以通过不同方式利用该结果，如将它集成到本地的问题求解，以产生一个更完整的结果，并传送给其他Agent，或用于证实是否是局部的问题求解结果，或作为启发式信息用于引导局部的问题求解等。,图7.8 结果共享的合作求解示意图,* 功能精确法 功能精确的合作方法（Functionally Accurate,Coorperative,FA/C）从本质上说也是一种结果共享的合作问题求解方法，是Lesser、Corkill等人提出的。该方法提供了一种不确定环境、多Agent间连续、动态地合作求解的一种方式，适合用于分布式解释和分布式诊断之类的合作问题求解。其基本思想是，通过多Agent求解过程中不断交换试验性中间结果来消除求解可能出现的错误，并汇集问题的最终解。FA/C方法是自底向上进行问题求解的，各Agent自动地求解内在具有分布特征的问题，允许Agent求解之间存在不一致性和冲突，然后通过互换试验性中间结果来消除矛盾，逐步建立系统的最终解。,(d) 市场机制法 上述所介绍的合作方法一般适合于小数量Agent间的合作求解。大量或未知数量Agent间的合作求解（电子商务和虚拟企业）通常使用市场机制的方法。 市场机制（例如各种拍卖协议，协商策略等）方法的基本思想是针对分布式资源分配的特定问题，建立相应的计算经济，通过最少的直接通信来协调Agent间的活动。在该方法中，对Agent关心的所有事物（如技能，资源等）都给予标价。系统存在生产者和消费者两种Agent，生产者Agent能够提供服务，即将某一商品转换为另一商品，消费者Agent能进行商品交换。Agent以各种价格对商品进行投标，但所有的商品交换都以当前市场价格进行，每一Agent通过投标以获取最大的利益或效用。,7.4.3.2 基于承诺和约定的合作方法 基于承诺和约定的合作方法是N.R.Jennings提出的，它采用分布目标搜索方法来模型化多Agent系统。所谓承诺（Commitment）是指Agent对承担一个特定的行动序列所作的保证，它使Agent在处理Agent间的依赖关系、全局约束和资源冲突时，能估计其他Agent的活动。所谓约定（Conventions）是指在变化的环境中监控承诺进展状况的手段，它为多Agent系统在动态环境下的合作提供了灵活性。 Durfee指出了这种合作方法的三要素： * 具有一种使Agent以预言方式进行交互的结构。 * 具有一定灵活性，使Agent能在动态环境下动作，并能处理不完整、不准确的数据。 * Agent具有足够的知识和推理能力，以便利用这种结构和灵活性。 这种合作方法可表示为： 合作承诺约定社会约定局部推理,7.4.3.3 基于规划的合作方法 规划与搜索、推理一样，是一种问题求解方法，通过它提高问题求解效率和增强系统求解的连贯性。通常，此种方法用于复杂问题的求解。 基于规划的问题求解方法分为两个过程：规划过程和执行过程。规划过程是指针对某一任务，求取完成该任务的动作序列（称为计划）。执行过程是指执行动作序列、监控问题求解过程，当出现意外情况计划无法进行下去时，调整行为计划或再规划，直到任务完成。 根据规划过程和执行过程参与的Agent的不同，这种合作方法又可分为：分布计划的集中规划方法，集中计划的分布规划方法和分布计划的分布规划方法。 由于多Agent系统系统是在一个变化环境中连续动态求解，计划执行过程中可能会出现意外情况。当Agent不能按计划继续执行时，就需协调，或调整原计划或再规划，此时涉及到规划的协调技术。,7.4.3.4 基于协调的合作方法 在多Agent系统系统中，协调主要用于消解冲突。 通过部分全局规划的协调 分布式车辆监测测试床（DVMT）是全工化的分布式问题求解网络测试床（Lesser and Corkill，1988）。为了协调DVMT中的Agent的动作，Durfee提出了称为“部分全局规划”（Partial Global Planning）方法。其原理是，在问题求解过程中，Agent的合作需要交换信息。规划是部分的，因为系统不能产生整个问题的求解计划。规划又是全局的，因为Agent通过局部规划的交换和合作，来得到问题求解的全局视图，进而形成全局计划。 部分全局规划包含三个迭代阶段： * 每个Agent决定自己的目标，并为实现该目标产生短期的规划。 * Agent之