分布式人工智能41

分布式人工智能与Agent分布式人工智能—DAI传统AI理论与方法在很大程度上只适用于串行处理结构，但大型智能问题都存在着潜在的并行性、分布性和开放性特点，而并行计算技术和计算机网络的发展为利用这些特性以提高问题求解效率和质量提供了实现基础。在这种情况下，DAI的研究逐渐引起了人们的注意。分布式人工智能—DAIDAI一词来源于1980年在MIT召开的第一届DAI国际会议“TheWorkshoponDistributedArtificialIntelligence”，为DAI的发展和推广起到很大推动作用。AvourisN.M个体的自治性和粒度角度将DAI的研究分为三个分支：分布式问题求解(DPS,DistributedProblemSolving)、多Agent系统(MAS,Multi-AgentSystem)和并行人工智能(PAI,ParallelArtificialIntelligence)分布式人工智能—DAIDPS的研究目标是创建大粒度协作群体，待求解的问题被分解为多个子问题，并分配给DPS系统中的个体，各个体进行各自的部分求解，所得到的部分解按照一定的方法综合起来得到整体解。在求解过程中可能进行协作，但这种协作是可预知的，并被事先安排在问题的求解过程的描述中，个体间的协作是命令/服从式的，不需进行协商DPS系统的特点是：环境条件已知，设计按自顶向下的方向展开，算法专用分布式人工智能—DAIPAI主要研究AI的并行计算体系结构，系统通常由多个紧密耦合的问题求解器组成，每个求解器是一个细粒度的知识体，PAI研究的观点与方法结合了符号主义和联结主义，神经元计算机也属于此研究范畴传统的DAI主要包括多专家系统、分布式专家系统、群体决策支持系统等新的分布式人工智能理念—MASMAS系统中各个Agent是自主的，生命周期不全为其他Agent所知，可以有共同的目标，也可以有各自不同的目标，Agent间即可能协作，也可能对抗，协作形式多种多样（如命令/服从式、投票式、磋商式等），MAS系统需要协调这些自治的Agent的行为。而由于各Agent空间上的分布性、时间上的并行性和逻辑上的依赖性使得MAS系统的问题求解过程更为复杂。DAI的三个分支并没有严格的定义和区别，互有交叉什么是Agent1980年代末开始，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），团队工作模型应用范围广泛，适用于教育、培训、信息收集、企业