分布式人工智能41

分布式人工智能与分布式人工智能与Agent分布式人工智能DAIw传统AI理论与方法在很大程度上只适用于串行处理结构，但大型智能问题都存在着潜在的并行性、分布性和开放性特点，而并行计算技术和计算机网络的发展为利用这些特性以提高问题求解效率和质量提供了实现基础。在这种情况下，DAI的研究逐渐引起了人们的注意。分布式人工智能DAIwDAI一词来源于1980年在MIT召开的第一届DAI国际会议“The Workshop on Distributed Artificial Intelligence”，为DAI的发展和推广起到很大推动作用。 wAvouris N.M个体的自治性和粒度角度将DAI的研究分为三个分支：分布式问题求解(DPS, Distributed Problem Solving)、多Agent系统(MAS, Multi-Agent System)和并行人工智能(PAI, Parallel Artificial Intelligence) 分布式人工智能DAIwDPS的研究目标是创建大粒度协作群体，待求解的问题被分解为多个子问题，并分配给DPS系统中的个体，各个体进行各自的部分求解，所得到的部分解按照一定的方法综合起来得到整体解。在求解过程中可能进行协作，但这种协作是可预知的，并被事先安排在问题的求解过程的描述中，个体间的协作是命令/服从式的，不需进行协商 wDPS系统的特点是：环境条件已知，设计按自顶向下的方向展开，算法专用 分布式人工智能DAIwPAI主要研究AI的并行计算体系结构，系统通常由多个紧密耦合的问题求解器组成，每个求解器是一个细粒度的知识体，PAI研究的观点与方法结合了符号主义和联结主义，神经元计算机也属于此研究范畴 w传统的DAI主要包括多专家系统、分布式专家系统、群体决策支持系统等新的分布式人工智能理念MASwMAS系统中各个Agent是自主的，生命周期不全为其他Agent所知，可以有共同的目标，也可以有各自不同的目标，Agent间即可能协作，也可能对抗，协作形式多种多样（如命令/服从式、投票式、磋商式等），MAS系统需要协调这些自治的Agent的行为。而由于各Agent空间上的分布性、时间上的并行性和逻辑上的依赖性使得MAS系统的问题求解过程更为复杂。DAI的三个分支并没有严格的定义和区别，互有交叉 什么是Agentw1980年代末开始，Agent的研究从DAI领域拓展开来，并与经济学、社会学等其他领域相互借鉴与融合，在许多最初不属于DAI的应用领域得到更为广泛的应用，面向Agent的思想技术作为开发设计软件系统的新方法也日益引起学术界和企业界的广泛关注 什么是Agentw在应用Agent技术的系统中，Agent的含义和表现各不相同，给Agent下一个无争议的定义是很困难的，Hewitt甚至认为定义什么是Agent和定义什么是智能一样困难wAgent定义可分为强定义和弱定义，弱定义强调Agent的自治性、社会性、感知环境并作出反应，强定义在此基础上增加了心智状态等高层次的属性Agent的分类w普遍的看法是Agent可分为思考型Agent、反应型Agent和混合型Agent w思考型Agent(deliberative Agent)是一种知识系统，用符号AI的方法来实现Agent的表示和推理。将Agent看作一种作为人类个体或社会行为的智能代理的意识系统，引入意识态度(intentional instance)，如信念、愿望、意图、目标、承诺、责任等，以表现出被代理者的意识态度w代表性的工作是Rao和Georgeff对BDI模型的研究，他们采用三个模态算子刻划信念(Belief)、愿望(Desire)和意图(Intention)，提出了描述Agent意识态度的BDI逻辑 w这些研究的目的是实现Agent的理性平衡，以保证Agent正确的执行赋予其的职责Agent的分类w从形式逻辑的角度对Agent理性的研究仍缺乏实用性，而且不能保证Agent做出最优决策 w另一种研究Agent理性行为的方法是基于对策论和决策理论的方法，其信念模型是将Agent每个行为的可能后果（到达何种状态）赋予概率，愿望模型用实数表示那些可能状态的效用，Agent的合理行动就是期望效用最优化的行动，可以根据信念和愿望得到，这就是效用理性 w这种方法的实用性较强，但忽视了推理环节，需要与形式逻辑方法进行融合 Agent的分类w思考型Agent的设计与建造上的复杂性以及在理论上还存在许多问题，使其缺乏实用性，于是有研究者提出了反应型Agent(reactive Agent) w反应型Agent的思想基础行为主义心理学，认为Agent不需要知识，只需感知环境的变化并作出相应的反应动作。反应型Agent虽然对外环境的变化有很高的响应速度，但智能程度低，缺乏灵活性。 Agent的分类w混合型Agent(hybrid Agent)的结构可分为两层，底层是反应层，不采用符号表示和推理，可快速响应并处理外部环境的突发性变化，通常具有较高的优先级；高层采用传统的AI方法进行规划、推理和决策。混合型Agent综合了前两者的优点，既有高响应速度，又有较高的智能和灵活性，是当前研究的主流多Agent系统MASw导致MAS研究兴起的最直接原因是MAS的合作问题求解能力大于单个Agent，其它原因包括：求解具有分布性的问题、提高系统的效率和鲁棒性、与已有软件系统的互操作等。近年来Internet的飞速发展为MAS提供了广阔的应用前景，对MAS研究起到了巨大的推动作用，出现了基于MAS的移动Agent、电子商务、网格计算等研究方向 MAS的特点及研究内容wMAS具有如下特点：成员Agent所拥有的信息和问题求解能力是不完全的，因而其观点是有局限性的；不存在全局控制；数据是分散或分布的；计算是异步、并发或并行的。此外，在应用系统中，Agent可能具有不同的角色和目的，Agent之间的关系也因此不同，可能是合作的，也可能是竞争甚至对抗的，可以是从属关系，也可能是平行关系wMAS的研究内容主要包括：.组织的形成；协商与协调机制；合作机制与任务分配；个性、社会性和规范 Agent组织的形成wAgent组织的形成主要研究组织结构设计、组织结构到Agent组织的映射和Agent组织的演化w具体方法目前主要有联盟形成方法、交互形成方法和面向结构的方法。联盟形成方法w代表性研究是Sheory等以对策论中多人合作博弈为基础，提出的联盟形成方法，从一群无联系的Agent中构造出有联系的Agent联盟w其过程包括：w（1）联盟结构的形成w（2）联盟值求解w（3）联盟值在成员中的分配w上述三个步骤反复迭代，直至得到稳定解 交互形成方法w交互方法是指在Agent不明确组织结构的前提下，通过交互形成组织的方法，主要有：w基于协商的合同网协议w基于依赖关系的社会推理，即Agent找出与其目标有依赖关系的其他Agent，通过协商与其形成合作组织w基于价格调控的市场方法，通过市场价格的调整达到供求平衡时，Agent形成买卖关系w组织自设计，Agent组织可以根据情况排斥或合并Agent.面向组织结构的方法w面向结构的方法人类社会的组织结构产生机制类似，以组织结构为前提，进行角色的分配与调整w一个Agent的能力符合角色要求时可以承担该角色；若Agent承担某角色有利可图，则会期望承担该角色；若Agent组织中存在还未被承担的角色时，则会接受合适的Agent加入MAS的协商机制w协商(negotiation)是指Agent之间通过交互对某些问题达成一致，是MAS实现协作、冲突消解和矛盾处理的关键环节 w协商方法主要有基于对策论的协商和基于劝说的协商两种类型 w基于对策论的协商以Zotkin和Rosenschein的工作为代表，但这种方法未考虑人类社会的协商所具有的劝说特点，计算量大，效率较低。wParsons和Jennings最早提出通过论据来协商的方法,基于劝说的协商是目前主要的协商方法w基于劝说的协商的原理是，一个Agent在提出一项建议时要同时给出原因，这样对方就可以了解提议方的思维状态，在更为完全的信息基础上做出更好的反应，从而加快协商进程。MAS的协商机制wAgent之间的协商还离不开协商协议，协商协议包括Agent通信语言（ACL）的定义、表示、处理和语义解释w协商协议的表示方法主要有BNF表示、有限状态自动机表示和纯语义表示，BNF简洁明了，且为研究者所熟悉，成为最广为使用的一种表示方法。MAS的协调机制w协调是指具有不同目标的多个Agent对其目标、资源、思维状态等进行合理安排，调整各自行为，以最大程度实现各自目标w协调的目标是解决各个Agent在按照各自的目的、知识与能力进行活动时可能出现的矛盾与冲突w协调方法分为显式协调和隐式协调两类 MAS的协调机制w显式协调是指在MAS中各Agent之间存在明确的协调机制，对Agent之间的潜在冲突进行推理，如有必要，与其他Agent协商，调整各自行为以消除冲突w显式协调方法又可分为完全集中的协调、集中与分布结合的协调和完全分布的协调三种 MAS的协调机制w完全集中的协调是指MAS中存在一个主控Agent来控制其他Agent的行为，给出其他Agent的行为规划，并保证各Agent行为彼此协调。这种方法可以降低系统复杂性，减少Agent间由协商产生的通信开销，但对主控Agent提出了很高的要求。如果各Agent的行为比较复杂，则难以得出一个全局一致的行为规划，且不适合动态、开放环境，在MAS中较少采用。w集中与分布结合的协调中也存在一个主控Agent，但只起到管理者的作用，不需给每个Agent一个完整的行为规划，只需给出部分规划或一个目标，其他Agent根据自己的知识来完成，这样可以降低对主控Agent的要求。w完全分布的协调方法是指MAS中各Agent的地位是平等的，通过相互间的协商来协调各自行为，具体方法有基于对策论的方法、基于规划的方法等 MAS的协调机制w隐式协调是通过为每个Agent制定行为规范，这种规范在设计Agent时就被嵌入，使各个的行为符合这种规范，从而表现出整体行为的一致性w代表性工作是Shoham等提出的社会规则，认为应当为MAS制定一套社会规则，每个Agent都遵守这一规则，且在规划行为时要相信其他Agent也遵守规则，从而保证Agent行为的可实现性，同时实现整个社会的行为协调w从本质上说，社会规则就是约束Agent状态空间搜索的准则w此外，Briggs提出了一种称为“灵活社会规则”的方法，是对社会规则方法和显式协调方法的一种折衷，吸收了两者的优点，既降低了通信开销又缩短了Agent规划时间。 MAS中的Agent合作机制 w合作是一种特殊的协调，是指多个Agent通过协调各自的行为来完成共同的目标w合作的原因可能是单个Agent无法完成其目标，需要其它Agent的帮助，也可能单个Agent可以完成目标，但若与其它Agent合作，则可以提高完成目标的效率或质量。 MAS中的Agent合作机制 w在前一种情况下，对于待完成的目标而言，Agent之间存在着依赖关系，承担任务的Agent必须了解其他Agent的能力，找出Agent间的这种依赖关系，作出规划，将任务分解为多个子任务，分配给相应的Agent。w若考虑到Agent的自私性以及可能有各自不同的目标，有能力完成某个子任务的Agent未必愿意承担任务，则需通过协商机制，使得Agent可以通过协商形成联合意图，作出联合承诺，并建立联合规划w后一种情况多用于群体决策支持系统（GDSS）、多专家系统合作推理等，通过多个Agent的合作可以避免单个Agent的能力缺陷，以得到更好的结果，、 MAS中的Agent合作机制 w此外，还有一种情况是团队工作(team work)，团队中各个Agent扮演不同的角色，但有共同的目标，Agent所扮角色和行为可根据环境变化转换，团队行动也要根据环境变化修改，各个体的行为要保持一致，这是目前的研究热点之一w最具代表性的是机器人足球（robotic soccer），团队工作模型应用范围广泛，适用于教育、培训、信息收集、企业管理、群体机器人协作以及软件开发环境（Agent Team 模型，Michael ，2000）等 MAS中的Agent合作机制 w多Agent合作经常涉及任务分配问题，在MAS中如果考虑到Agent的理性（或自私性），则会使任务分配问题大为复杂w常用的任务分配方法有经典的合同网方法、规划图方法、基于市场的方法等w合同网方法适用于成员之间是平等、自主关系的MAS系统，规划图方法适用于Agent间存在从属关系的情况，基于市场的方法则适用于在大量自私的Agent间分配任务。Agent的个性、MAS的社会性及社会规范w研究目标：这一方面的研究者注重从心理学和社会学的角度对Agent和MAS进行理论上的研究，试图让Agent和MAS表现出人类的行为特点及人类社会的群体行为规律模式，认为这样可以提高MAS的智能程度wAgent的个性描述的是Agent之间的差异，如问题求解能力、领域知识、目标倾向等。而社会性则是指Agent之间存在各种各样的关系，如信任、依赖、从属等，从这些个体间的关系可以导致合作、联盟、对抗等群体性行为。对MAS的社会性研究目的是对这些关系以及从关系导致群体行为进行形式化表示并建立相应的逻辑体系 Agent的个性、MAS的社会性及社会规范w这方面的研究还未有系统性的理论成果。所采用的方法与Agent思维状态研究类似，多以模态逻辑和可能世界语义学为基础，在BDI模型等的基础上引入联合意图、集体承诺等社会属性。w社会规范不仅是一种隐式协调方法，它还体现了MAS的社会性w通过制定规范可以平衡个体利益与群体利益的矛盾，保证Agent行为的理性w这方面的研究可分为两类，即基于模态逻辑的方法和基于对策论的方法，但也还未有很好的研究成果。Software Agent和AOP wSoftware Agent并没有准确的定义，通常理解为体现了Agent思想的软件w开发Soft Agent需要AOP (Agent Oriented Programming)思想 wSoftware Agent的特征：持久运行，不像通常的软件例程那样被特定任务激活，执行后休眠或消失；自治性，不需人的控制和监督；能感知环境变化并作出反应；自适应性，能根据用户或环境特点调整自身行为；智能性，如能够推理、学习、规划等；能感知其他Agent，推测其行为并能够与之交互；移动性，能够在网络中移动；拟人性，能够表现出人的心智特征和行为特征w在实际应用中，Software Agent不需要具备全部这些特征，可以根据需要各有侧重。Software Agent和AOP wAOP是Shoham最早在1989年提出的，他认为AOP是一种从社会观点出发的程序设计思想，应当用能够表示Agent性质的意识态度来设计和开发Agent。w从1994年以来，在Internet的推动下，AOP思想得到了很大发展，Agent概念得到广泛的应用w现在的AOP研究已不再局限于以Agent的意识态度为核心，而是包括一切用于开发Software Agent的技术和方法w现有的AOP语言已有多种，Shoham最早提出了以意识态度为核心的Agent-0语言，在此基础上发展为PLACA，此外，还有面向反应型Agent的Telescript语言以及结合了OOP思想的AOP语言如LALO、Z+a等 Software Agent和AOP wSoftware Agent和AOP的研究分为NES( Nouvelle Expert System)、EDS(Exotic Distributed System)和AD三类，下图表示各自的技术成熟程度和发展前景 NESEDSAD沿箭头方向技术成熟度降低，潜在影响增加，实现目标所需时间增加 Software Agent和AOP wNES目的是在AI相关技术的基础上，发展新的应用领域，或更有效的应用于已有领域，目前多用于管理大量的在线数据，如个人事务助理、自动信息采集、Web数据挖掘等wEDS目的是构建具有Agent特性的新型中间件(middleware),以提高软件开发效率，支持网络应用，真正实现“网络就是计算机”wAD的目的是计算机人性化，表现出人的行为特征，与用户实现人性化交互。Software Agent和AOP wShoham认为：wNES技术上已经成熟，但发展潜力不大wEDS技术上有一定的实现基础，发展前景较好，应用范围较广，可视作是CORBA、COM/DCOM等OOP技术的进一步发展和跨越，KQML等AOP语言以及一些用于电子商务的软件系统均体现了这一思想w面向AD的Agent研究应当说是最令人激动的，但也是难度最大的，缺乏研究基础，其发展前景还无法确定。Internet环境下的Agent/MAS研究 wInternet的发展给社会和经济的各个方面都带来了巨大的影响,使得人们比以往任何时候都更加能够大范围地共享各种信息和资源w在Internet的基础上，可以将很大范围上地理分布的异构计算机系统组织起来形成团体性的任务处理系统。这使得传统的DAI研究从传统封闭的、基于局域网的系统结构转向开放的、基于Internet的、以Multi-agent理念为思想基础的体系结构w另一方面，Internet上的信息量之大使得人们必须发展更为智能化的信息收集和管理工具，这也促进了面向Internet的Agent技术研究。Internet环境下的Agent/MAS研究 wAI技术在Internet上的应用大致分为四类：w用户建模(user modeling)w信息源发现与分析w信息集成(information integration)和Web站点管理w在前三个领域中，Agent技术尤其被重视，得到了广泛的应用。这里Agent通常成为用户与Internet之间的接口，代理用户提交的Internet服务请求 Internet环境下的Agent/MAS研究 w用户建模在AI、认知科学等领域已有较长的研究历史，目的是针对用户的行为特征，建立一个有预测能力的模型w根据这种模型开发出的软件系统就是用户代理Agent，能够按照用户的行为习惯自动完成规定的任务，如安排日程，过滤无用信息，e-mail处理等w在Internet上的一个突出的应用是智能化Web搜索，例如根据用户浏览Web的历史记录，得出用户对各种类型信息的感兴趣度，自动搜索相关页面，将这些页面按照权威性排序并提供给用户w有的Agent给用户提供的不是页面，而是相关领域的专家，并能够自动引导用户与专家联系（如自动将e-mail发给相应的专家）w用户建模通常采用归纳学习、决策树、BP网、贝叶斯网等机器学习方法Internet环境下的Agent/MAS研究 w为了使用户能够高效的利用Internet信息资源，作为用户智能代理的Agent应当具有信息源的发现与分析能力w信息源发现与分析可归结为四个问题：w信息源发现，即及时发现用户所需信息的信息源w信息提取，即如何以正确的方式访问信息源，并从信息源提供的各种形式信息中提取所需的有用信息w信息翻译，即给得到的信息赋予正确的语义，从而能够将信息准确提交给相应的任务，例如要确定从信息源得到的数据列表中哪一列是商品名，哪一列是价格等w信息评价，即评价各个信息源提供的信息是否准确、是否及时以及能否及时响应Agent提出的服务请求等 Internet环境下的Agent/MAS研究 w相对于用户提出的要求，Internet上每个信息源提供的信息通常是不完整的，因此Agent还要解决信息集成问题，即要从不同的信息源得到不同部分的信息，并将其组合起成为用户所需的完整信息w如用户需要知道某一农产品的价格、距离最近的供应商及联系方式，Agent则可能从某一站点得到该产品的价格，从另一站点得到附近区域的供应商和联系地址，合成完整的信息提交给用户w这一领域引起了AI研究者的研究热点 Internet环境下的Agent/MAS研究 wInternet还给Agent/MAS提供了更为广阔和更有挑战性的应用环境。如电子商务领域中通过Agent进行竞价、谈判等已成为当前的研究热点w从更一般的意义上讲，Internet给人们提供了资源共享的途径，信息共享只是资源共享的一种方式，此外还可以有知识的共享、智 能 的 共 享 和 计 算 资 源 的 共 享 ， 而 这 些 共 享 都 离 不 开Agent/MAS技术w例如Internet使得人们可以方便的远程访问大型数据库，如果数据库所在站点上有智能Agent,它不仅能够提供查询服务，而且可以通过KDD技术提供隐含在数据库中的知识，这对用户的决策更有价值；如果Agent能够在数据库和知识的基础上为用户提供决策服务，则实现了智能的共享，更进一步提高了资源共享的效率和价值，基于传统的专家系统、决策支持系统构建的Agent也可以通过Internet提供更大范围的服务；如果将这些Agent组织成MAS，则可以帮助用户解决更为复杂的问题，使“网络就是计算机”有了更深一层的含义，这也是“网格”概念日益引起重视的原因，而网格的实现离不开Agent/MAS技术