分布式人工智能41

分布式人工智能与Agent第一页，共四十二页。分布式人工智能—DAI传统AI理论与方法在很大程度上只适用于串行处理结构，但大型智能问题都存在着潜在的并行性、分布性和开放性特点，而并行计算技术和计算机网络的发展为利用这些特性以提高问题求解效率和质量提供了实现基础。在这种情况下，DAI的研究逐渐引起了人们的注意。第二页，共四十二页。分布式人工智能—DAIDAI一词来源于1980年在MIT召开的第一届DAI国际会议“TheWorkshoponDistributedArtificialIntelligence”，为DAI的发展和推广起到很大推动作用。AvourisN.M个体的自治性和粒度角度将DAI的研究分为三个分支：分布式问题求解(DPS,DistributedProblemSolving)、多Agent系统(MAS,Multi-AgentSystem)和并行人工智能(PAI,ParallelArtificialIntelligence)第三页，共四十二页。分布式人工智能—DAIDPS的研究目标是创建大粒度协作群体，待求解的问题被分解为多个子问题，并分配给DPS系统中的个体，各个体进行各自的部分求解，所得到的部分解按照一定的方法综合起来得到整体解。在求解过程中可能进行协作，但这种协作是可预知的，并被事先安排在问题的求解过程的描述中，个体间的协作是命令/服从式的，不需进行协商DPS系统的特点是：环境条件已知，设计按自顶向下的方向展开，算法专用第四页，共四十二页。分布式人工智能—DAIPAI主要研究AI的并行计算体系结构，系统通常由多个紧密耦合的问题求解器组成，每个求解器是一个细粒度的知识体，PAI研究的观点与方法结合了符号主义和联结主义，神经元计算机也属于此研究范畴传统的DAI主要包括多专家系统、分布式专家系统、群体决策支持系统等第五页，共四十二页。新的分布式人工智能理念—MASMAS系统中各个Agent是自主的，生命周期不全为其他Agent所知，可以有共同的目标，也可以有各自不同的目标，Agent间即可能协作，也可能对抗，协作形式多种多样（如命令/服从式、投票式、磋商式等），MAS系统需要协调这些自治的Agent的行为。而由于各Agent空间上的分布性、时间上的并行性和逻辑上的依赖性使得MAS系统的问题求解过程更为复杂。DAI的三个分支并没有严格的定义和区别，互有交叉第六页，共四十二页。什么是Agent1980年代末开始，Agent的研究从DAI领域拓展开来，并与经济学、社会学等其他领域相互借鉴与融合，在许多最初不属于DAI的应用领域得到更为广泛的应用，面向Agent的思想技术作为开发设计软件系统的新方法也日益引起学术界和企业界的广泛关注第七页，共四十二页。什么是Agent在应用Agent技术的系统中，Agent的含义和表现各不相同，给Agent下一个无争议的定义是很困难的，Hewitt甚至认为定义什么是Agent和定义什么是智能一样困难Agent定义可分为强定义和弱定义，弱定义强调Agent的自治性、社会性、感知环境并作出反应，强定义在此基础上增加了心智状态等高层次的属性第八页，共四十二页。Agent的分类普遍的看法是Agent可分为思考型Agent、反应型Agent和混合型Agent思考型Agent(deliberativeAgent)是一种知识系统，用符号AI的方法来实现Agent的表示和推理。将Agent看作一种作为人类个体或社会行为的智能代理的意识系统，引入意识态度(intentionalinstance)，如信念、愿望、意图、目标、承诺、责任等，以表现出被代理者的意识态度代表性的工作是Rao和Georgeff对BDI模型的研究，他们采用三个模态算子刻划信念(Belief)、愿望(Desire)和意图(Intention)，提出了描述Agent意识态度的BDI逻辑这些研究的目的是实现Agent的理性平衡，以保证Agent正确的执行赋予其的职责第九页，共四十二页。Agent的分类从形式逻辑的角度对Agent理性的研究仍缺乏实用性，而且不能保证Agent做出最优决策另一种研究Agent理性行为的方法是基于对策论和决策理论的方法，其信念模型是将Agent每个行为的可能后果（到达何种状态）赋予概率，愿望模型用实数表示那些可能状态的效用，Agent的合理行动就是期望效用最优化的行动，可以根据信念和愿望得到，这就是效用理性这种方法的实用性较强，但忽视了推理环节，需要与形式逻辑方法进行融合第十页，共四十二页。Agent的分类思考型Agent的设计与建造上的复杂性以及在理论上还存在许多问题，使其缺乏实用性，于是有研究者提出了反应型Agent(reactiveAgent)反应型Agent的思想基础行为主义心理学，认为Agent不需要知识，只需感知环境的变化并作出相应的反应动作。反应型Agent虽然对外环境的变化有很高的响应速度，但智能程度低，缺乏灵活性。第十一页，共四十二页。Agent的分类混合型Agent(hybridAgent)的结构可分为两层，底层是反应层，不采用符号表示和推理，可快速响应并处理外部环境的突发性变化，通常具有较高的优先级；高层采用传统的AI方法进行规划、推理和决策。混合型Agent综合了前两者的优点，既有高响应速度，又有较高的智能和灵活性，是当前研究的主流第十二页，共四十二页。多Agent系统—MAS导致MAS研究兴起的最直接原因是MAS的合作问题求解能力大于单个Agent，其它原因包括：求解具有分布性的问题、提高系统的效率和鲁棒性、与已有软件系统的互操作等。近年来Internet的飞速发展为MAS提供了广阔的应用前景，对MAS研究起到了巨大的推动作用，出现了基于MAS的移动Agent、电子商务、网格计算等研究方向第十三页，共四十二页。MAS的特点及研究内容MAS具有如下特点：成员Agent所拥有的信息和问题求解能力是不完全的，因而其观点是有局限性的；不存在全局控制；数据是分散或分布的；计算是异步、并发或并行的。此外，在应用系统中，Agent可能具有不同的角色和目的，Agent之间的关系也因此不同，可能是合作的，也可能是竞争甚至对抗的，可以是从属关系，也可能是平行关系MAS的研究内容主要包括：.组织的形成；协商与协调机制；合作机制与任务分配；个性、社会性和规范第十四页，共四十二页。Agent组织的形成Agent组织的形成主要研究组织结构设计、组织结构到Agent组织的映射和Agent组织的演化具体方法目前主要有联盟形成方法、交互形成方法和面向结构的方法。第十五页，共四十二页。联盟形成方法代表性研究是Sheory等以对策论中多人合作博弈为基础，提出的联盟形成方法，从一群无联系的Agent中构造出有联系的Agent联盟其过程包括：（1）联盟结构的形成（2）联盟值求解（3）联盟值在成员中的分配上述三个步骤反复迭代，直至得到稳定解第十六页，共四十二页。交互形成方法交互方法是指在Agent不明确组织结构的前提下，通过交互形成组织的方法，主要有：基于协商的合同网协议基于依赖关系的社会推理，即Agent找出与其目标有依赖关系的其他Agent，通过协商与其形成合作组织基于价格调控的市场方法，通过市场价格的调整达到供求平衡时，Agent形成买卖关系组织自设计，Agent组织可以根据情况排斥或合并Agent.第十七页，共四十二页。面向组织结构的方法面向结构的方法人类社会的组织结构产生机制类似，以组织结构为前提，进行角色的分配与调整一个Agent的能力符合角色要求时可以承担该角色；若Agent承担某角色有利可图，则会期望承担该角色；若Agent组织中存在还未被承担的角色时，则会接受合适的Agent加入第十八页，共四十二页。MAS的协商机制协商(negotiation)是指Agent之间通过交互对某些问题达成一致，是MAS实现协作、冲突消解和矛盾处理的关键环节协商方法主要有基于对策论的协商和基于劝说的协商两种类型基于对策论的协商以Zotkin和Rosenschein的工作为代表，但这种方法未考虑人类社会的协商所具有的劝说特点，计算量大，效率较低。Parsons和Jennings最早提出通过论据来协商的方法,基于劝说的协商是目前主要的协商方法基于劝说的协商的原理是，一个Agent在提出一项建议时要同时给出原因，这样对方就可以了解提议方的思维状态，在更为完全的信息基础上做出更好的反应，从而加快协商进程。第十九页，共四十二页。MAS的协商机制Agent之间的协商还离不开协商协议，协商协议包括Agent通信语言（ACL）的定义、表示、处理和语义解释协商协议的表示方法主要有BNF表示、有限状态自动机表示和纯语义表示，BNF简洁明了，且为研究者所熟悉，成为最广为使用的一种表示方法。第二十页，共四十二页。MAS的协调机制协调是指具有不同目标的多个Agent对其目标、资源、思维状态等进行合理安排，调整各自行为，以最大程度实现各自目标协调的目标是解决各个Agent在按照各自的目的、知识与能力进行活动时可能出现的矛盾与冲突协调方法分为显式协调和隐式协调两类第二十一页，共四十二页。MAS的协调机制显式协调是指在MAS中各Agent之间存在明确的协调机制，对Agent之间的潜在冲突进行推理，如有必要，与其他Agent协商，调整各自行为以消除冲突显式协调方法又可分为完全集中的协调、集中与分布结合的协调和完全分布的协调三种第二十二页，共四十二页。MAS的协调机制完全集中的协调是指MAS中存在一个主控Agent来控制其他Agent的行为，给出其他Agent的行为规划，并保证各Agent行为彼此协调。这种方法可以降低系统复杂性，减少Agent间由协商产生的通信开销，但对主控Agent提出了很高的要求。如果各Agent的行为比较复杂，则难以得出一个全局一致的行为规划，且不适合动态、开放环境，在MAS中较少采用。集中与分布结合的协调中也存在一个主控Agent，但只起到管理者的作用，不需给每个Agent一个完整的行为规划，只需给出部分规划或一个目标，其他Agent根据自己的知识来完成，这样可以降低对主控Agent的要求。完全分布的协调方法是指MAS中各Agent的地位是平等的，通过相互间的协商来协调各自行为，具体方法有基于对策论的方法、基于规划的方法等第二十三页，共四十二页。MAS的协调机制隐式协调是通过为每个Agent制定行为规范，这种规范在设计Agent时就被嵌入，使各个的行为符合这种规范，从而表现出整体行为的一致性代表性工作是Shoham等提出的社会规则，认为应当为MAS制定一套社会规则，每个Agent都遵守这一规则，且在规划行为时要相信其他Agent也遵守规则，从而保证Agent行为的可实现性，同时实现整个社会的行为协调从本质上说，社会规则就是约束Agent状态空间搜索的准则此外，Briggs提出了一种称为“灵活社会规则”的方法，是对社会规则方法和显式协调方法的一种折衷，吸收了两者的优点，既降低了通信开销又缩短了Agent规划时间。第二十四页，共四十二页。MAS中的Agent合作机制合作是一种特殊的协调，是指多个Agent通过协调各自的行为来完成共同的目标合作的原因可能是单个Agent无法完成其目标，需要其它Agent的帮助，也可能单个Agent可以完成目标，但若与其它Agent合作，则可以提高完成目标的效率或质量。第二十五页，共四十二页。MAS中的Agent合作机制在前一种情况下，对于待完成的目标而言，Agent之间存在着依赖关系，承担任务的Agent必须了解其他Agent的能力，找出Agent间的这种依赖关系，作出规划，将任务分解为多个子任务，分配给相应的Agent。若考虑到Agent的自私性以及可能有各自不同的目标，有能力完成某个子任务的Agent未必愿意承担任务，则需通过协商机制，使得Agent可以通过协商形成联合意图，作出联合承诺，并建立联合规划后一种情况多用于群体决策支持系统（GDSS）、多专家系统合作推理等，通过多个Agent的合作可以避免单个Agent的能力缺陷，以得到更好的结果，、第二十六页，共四十二页。MAS中的Agent合作机制此外，还有一种情况是团队工作(teamwork)，团队中各个Agent扮演不同的角色，但有共同的目标，Agent所扮角色和行为可根据环境变化转换，团队行动也要根据环境变化修改，各个体的行为要保持一致，这是目前的研究热点之一最具代表性的是机器人足球（roboticsoccer），团队工作模型应用范围广泛，适用于教育、培训、信息收集、企业管理、群体机器人协作以及软件开发环境（AgentTeam模型，Michael，2000）等第二十七页，共四十二页。MAS中的Agent合作机制多Agent合作经常涉及任务分配问题，在MAS中如果考虑到Agent的理性（或自私性），则会使任务分配问题大为复杂常用的任务分配方法有经典的合同网方法、规划图方法、基于市场的方法等合同网方法适用于成员之间是平等、自主关系的MAS系统，规划图方法适用于Agent间存在从属关系的情况，基于市场的方法则适用于在大量自私的Agent间分配任务。第二十八页，共四十二页。Agent的个性、MAS的社会性及社会规范研究目标：这一方面的研究者注重从心理学和社会学的角度对Agent和MAS进行理论上的研究，试图让Agent和MAS表现出人类的行为特点及人类社会的群体行为规律模式，认为这样可以提高MAS的智能程度Agent的个性描述的是Agent之间的差异，如问题求解能力、领域知识、目标倾向等。而社会性则是指Agent之间存在各种各样的关系，如信任、依赖、从属等，从这些个体间的关系可以导致合作、联盟、对抗等群体性行为。对MAS的社会性研究目的是对这些关系以及从关系导致群体行为进行形式化表示并建立相应的逻辑体系第二十九页，共四十二页。Agent的个性、MAS的社会性及社会规范这方面的研究还未有系统性的理论成果。所采用的方法与Agent思维状态研究类似，多以模态逻辑和可能世界语义学为基础，在BDI模型等的基础上引入联合意图、集体承诺等社会属性。社会规范不仅是一种隐式协调方法，它还体现了MAS的社会性通过制定规范可以平衡个体利益与群体利益的矛盾，保证Agent行为的理性这方面的研究可分为两类，即基于模态逻辑的方法和基于对策论的方法，但也还未有很好的研究成果。第三十页，共四十二页。SoftwareAgent和AOPSoftwareAgent并没有准确的定义，通常理解为体现了Agent思想的软件开发SoftAgent需要AOP(AgentOrientedProgramming)思想SoftwareAgent的特征：持久运行，不像通常的软件例程那样被特定任务激活，执行后休眠或消失；自治性，不需人的控制和监督；能感知环境变化并作出反应；自适应性，能根据用户或环境特点调整自身行为；智能性，如能够推理、学习、规划等；能感知其他Agent，推测其行为并能够与之交互；移动性，能够在网络中移动；拟人性，能够表现出人的心智特征和行为特征在实际应用中，SoftwareAgent不需要具备全部这些特征，可以根据需要各有侧重。第三十一页，共四十二页。SoftwareAgent和AOPAOP是Shoham最早在1989年提出的，他认为AOP是一种从社会观点出发的程序设计思想，应当用能够表示Agent性质的意识态度来设计和开发Agent。从1994年以来，在Internet的推动下，AOP思想得到了很大发展，Agent概念得到广泛的应用现在的AOP研究已不再局限于以Agent的意识态度为核心，而是包括一切用于开发SoftwareAgent的技术和方法现有的AOP语言已有多种，Shoham最早提出了以意识态度为核心的Agent-0语言，在此基础上发展为PLACA，此外，还有面向反应型Agent的Telescript语言以及结合了OOP思想的AOP语言如LALO、Z++a等第三十二页，共四十二页。SoftwareAgent和AOPSoftwareAgent和AOP的研究分为NES(NouvelleExpertSystem)、EDS(ExoticDistributedSystem)和AD三类，下图表示各自的技术成熟程度和发展前景

NESEDSAD沿箭头方向技术成熟度降低，潜在影响增加，实现目标所需时间增加第三十三页，共四十二页。SoftwareAgent和AOPNES目的是在AI相关技术的基础上，发展新的应用领域，或更有效的应用于已有领域，目前多用于管理大量的在线数据，如个人事务助理、自动信息采集、Web数据挖掘等EDS目的是构建具有Agent特性的新型中间件(middleware),以提高软件开发效率，支持网络应用，真正实现“网络就是计算机”AD的目的是计算机人性化，表现出人的行为特征，与用户实现人性化交互。第三十四页，共四十二页。SoftwareAgent和AOPShoham认为：NES技术上已经成熟，但发展潜力不大EDS技术上有一定的实现基础，发展前景较好，应用范围较广，可视作是CORBA、COM/DCOM等OOP技术的进一步发展和跨越，KQML等AOP语言以及一些用于电子商务的软件系统均体现了这一思想面向AD的Agent研究应当说是最令人激动的，但也是难度最大的，缺乏研究基础，其发展前景还无法确定。第三十五页，共四十二页。Internet环境下的Agent/MAS研究Internet的发展给社会和经济的各个方面都带来了巨大的影响,使得人们比以往任何时候都更加能够大范围地共享各种信息和资源在Internet的基础上，可以将很大范围上地理分布的异构计算机系统组织起来形成团体性的任务处理系统。这使得传统的DAI研究从传统封闭的、基于局域网的系统结构转向开放的、基于Internet的、以Multi-agent理念为思想基础的体系结构另一方面，Internet上的信息量之大使得人们必须发展更为智能化的信息收集和管理工具，这也促进了面向Internet的Agent技术研究。第三十六页，共四十二页。Internet环境下的Agent/MAS研究AI技术在Internet上的应用大致分为四类：用户建模(usermodeling)信息源发现与分析信息集成(informationintegration)和Web站点管理在前三个领域中，Agent技术尤其被重视，得到了广泛的应用。这里Agent通常成为用户与Internet之间的接口，代理用户提交的Internet服务请求第三十七页，共四十二页。Internet环境下的Agent/MAS研究用户建模在AI、认知科学等领域已有较长的研究历史，目的是针对用户的行为特征，建立一个有预测能力的模型根据这种模型开发出的软件系统就是用户代理Agent，能够按照用户的行为习惯自动完成规定的任务，如安排日程，过滤无用信息，e-mail处理等在Internet上的一个突出的应用是智能化Web搜索，例如根据用户浏览Web的历史记录，得出用户对各种类型信息的感兴趣度，自动搜索相关页面，将这些页面按照权威性排序并提供给用户有的Agent给用户提供的不是页面，而是相关领域的专家，并能够自动引导用户与专家联系（如自动将e-mail发给相应的专家）用户建模通常采用归纳学习、决策树、BP网、贝叶斯网等机器学习方法第三十八页，共四十二页。Internet环境下的Agent/MAS研究为了使用户能够高效的利用Internet信息资源，作为用户智能代理的Agent应当具有信息源的发现与分析能力信息源发现与分析可归结为四个问题：信息源发现，即及时发现用户所需信息的信息源信息提取，即如何以正确的方式访问信息源，并从信息源提供的各种形式信息中提取所需的有用信息信息翻译，即给得到的信息赋予正确的语义，从而能够将信息准确提交给相应的任务，例如要确定从信息源得到的数据列表中哪一列是商品名，哪一列是价格等信息评价，即评价各个信息源提供的信息是否准确、是否及时以及能否及时响应Agent提出的服务请求等第三十九页，共四十二页。Internet环境下的Agent/MAS研究相对于用户提出的要求，Internet上每