分布式人工智能与MAS.ppt

分布式人工智能与多Agent系统,计算机科学技术发展趋势,1、智能化 2、个性化 3、网络化 4、并行化,分布式人工智能(DAI),一、基本概念 研究在逻辑上或物理上分散的智能系统如何并行地、相互协作地实现问题求解。,分布式人工智能(DAI),二、特点 1)系统中的数据、知识以及控制不但在逻辑上，而且在物理上分布的，既没有全局控制，也没有全局的数据存储。 2)各个求解机构由计算机网络互连，在问题求解过程中，通信代价要比求解问题的代价低得多。 3)系统中诸机构能够相互协作，来求解单个机构难以解决，甚至不能解决的任务。 注：DAI的实现可克服原有专家系统、学习系统等弱点，极大提高知识系统的性能，可提高问题求解能力和效率，扩大应用范围、降低软件复杂性。,分布式人工智能(DAI),三、主要内容 分布式问题求解(DPS)和多Agent系统(MAS)。 1)分布式问题求解(DPS) 主要考虑怎样将一个特殊问题求解工作在多个合作的、知识共享的模块或结点之间划分。 2)多Agent系统(MAS) 主要研究自主的智能Agent之间智能行为的协调，为了一个共同的全局目标，也可能是关于各自的不同目标，共享有关问题和求解方法的知识，协作进行问题求解。 注：基于Agent的计算将成为软件开发的下一个重要的突破口。,分布式问题求解(DPS),一、协作方式 任务分担(task sharing)和结果共享(results sharing) 二、求解过程 1、任务分解 2、任务分配 3、子问题求解 4、结果综合 注：1)典型的任务分解和任务分配的方法有：合同网络(类似于“招标”)、动态层次控制、自然分解、固定分解、部分全局规划； 2)在DPS中常用的通信方式有：共享全局存储器、消息传递及二者的结合。 3)黑板模型是DPS中使用较多的框架结构。,Agent及多Agent系统(MAS),智能体最早出现在20世纪70年代的人工智能领域，它所具有的智能性和灵活性，使得该技术成为研究复杂系统的重要手段。单个智能体的能力、知识和计算资源都很有限，而多个智能体组成的多智能体系统已成为解决大型、复杂、分布式及难预测问题的重要手段。90年代以来，多智能体系统已经成为分布式人工智能研究的热点，对智能体以及MAS的研究已经成为人工智能的核心问题。多智能体系统对许多学科和技术的发展起到了很大的指导和促进作用，由于Agent的出现，人们可以对人工智能进行以下全新的诠释： “人工智能是计算机科学的一个分支，其目标是构造能表现出一定智能行为的智能体”。计算智能体甚至被认为是人工智能研究的最初和最终目标。,Agent及多Agent系统(MAS),多智能体理论对于促进经济、工业、社会、军事等方面的进步都具有深远的意义。 主要研究内容 1、微观 Agent本身，包括Agent基本特性、相应理论、内部实现框架。 2、宏观 Agent与环境及其它Agent的关系，包括，多Agent系统体系结构、Agent通信语言、Agent交互与协商、Agent协作与合作、多Agent知识交互与信息共享、多Agent学习。,Agent,一、Agent的定义（尚未形成统一定义） 关于Agent有多种称呼：代理、主体 、智能体、智能主体、艾真体等。 能够自主连续地在一可动态变化的、存在其它Agent的环境中运行的，并可与环境进行交互的实体，称为Agent。 广义地讲，Agent是具有自主性、社会能力(交互性)和反应特征的计算机软/硬件系统。 Agent是可以感知其所处环境，并能根据自身的目标作用于环境的计算实体。 在没有人的干预下能够自主地完成给定任务的对象都可以称为Agent。 在人工智能领域，Agent被定义为具有感知能力、问题求解能力和与外界通信能力的实体，是完全自治或半自治的。,Agent,三、Agent特性 1、自治性 对自己的行为和内部状态有一定的控制权。 2、社会性或称可通信性 能够通过某种Agent通信语言与其它Agent进行信息交换。 注：任务的承接、多Agent的协作、协商等均以通信为基础。 3、交互性 对环境的感知，并通过行为改变环境。 4、主动性 主动感知周围环境的变化，并作出基于目标的行为。,Agent,5、协作性 通过协作提高多Agent系统的性能。 6、持久性 在“相当长”的时间内连续运行。 7、自适应性 根据过去的经验积累知识，并且修改其行为以适应新的环境。 8、情态特性 具有信念、意图、愿望等情态。 9、可推理性 可根据当前知识和经验，以理性的方式进行推理或预测。,Agent,10、可移动性 可从一个地方移动到另一个地方而保持其内部状态不变。 注：Agent可以携带数据，且可在远处执行智能指令。 11、诚实性 不会故意提供错误信息。 12、友善性 Agent之间不存在互相冲突的目标，总是尽力帮助其它Agent。 13、理性 总是尽力实现自己的目标。,Agent,,四、智能体分类 本地智能体或网络智能体 集中式智能体或分布式智能体 固定智能体或移动智能体,多Agent,,多智能体系统是在逻辑上或物理上呈分布状态的多个智能体组成的较为松散的联合体，各智能体按照预先规定的协议，根据系统的目标状态及自身的目的、资源和知识，利用通信网络，相互之间通过协商来确定各自的任务，并通过协调和协作来共同完成任务并达到整体目标。,多Agent,,基于多智能体系统研究复杂系统时，首先要根据系统的特点对单个智能体作出定义，赋予其一定的行为能力和参数，并对各个智能体之间以及智能体与环境之间的交互规则作出规定，以此描述系统及其变化过程。在复杂的动态环境下，由于存在时间和资源的约束，多智能体系统需要解决的关键问题就是如何进行资源分配、任务调度、行为协调和冲突消解，使功能独立的智能体通过协商、协调来完成复杂的控制任务或解决复杂的问题。,多智能体系统体系结构和协调机制,,多智能体系统体系结构及其协调机制是多智能体系统理论研究的核心问题，它研究如何把多个智能体组织为一个群体并使各个智能体有效地进行协调合作，从而达到解决整体问题的目标。对于多智能体系统体系结构及其协调机制的研究，目前大致可以分为三种学派：基于符号推理系统的体系结构及协调机制，基于行为主义的体系结构及协调机制，基于协作进化方法的体系结构及协调机制。,基于符号推理系统的体系结构及协调机制,,这种学派的基础是Bratman等提出的BDI(Brief Desire Intention)理论通过建立比较完整的符号系统并基于经典人工智能的符号处理，来进行知识推理以使智能体具有自主思考、决策以及与其他智能体和环境进行协调行动的能力。这种学派包括三种代表性的理论：,基于符号推理系统的体系结构及协调机制,,（1）联合意图理论 这是目前最为系统和成熟的多智能体协调理论框架，由Cohen和Levesque在BDI理论的基础上，提出了承诺（Commitment）和公约（Convention）等概念。其基本思想是：多个智能体在完成共同的任务时会形成一个共同的承诺，并坚守承诺，直到成功完成共同任务，除非出现下列任何一种情况：①智能体发现共同任务已经完成；②智能体发现共同任务不可能完成；③智能体发现没有必要执行该共同任务。如果发生以上情况，智能体就把“自己将要退出承诺”的意图设法通知正在联合执行任务的其他智能体，以便适时地进行调整。通过这样的承诺和公约机制，多个智能体就能协调完成共同的任务。所以，联合意图理论只是为了各个智能体在完成共同任务时参与和坚持的一致性提供了一个框架，而没有确定联合行为中的具体分工和协作问题。,基于符号推理系统的体系结构及协调机制,,（2）共享计划理论 该理论由Grosz等提出。其基本思想是：参与联合行动的各个智能体先达成一个包括具体行动步骤和各方面细节的共享计划，并且相信所有智能体都打算参与联合行动并接受共享计划；数个智能体组建形成子团体，不同的子团体或单独或组合地完成共享计划的每一个具体步骤；子团体之外的其他智能体都相信子团体能够完成相应的具体步骤，并形成相应的共享计划。于是，通过共享计划的协调，各个智能体就能合作完成共同的任务。,基于符号推理系统的体系结构及协调机制,,（3）计划的队行为 计划由设计者事先确定，而不是由MAS动态产生，各个智能体在行动之前就被赋予有关完整计划的详细信息。这种方法要求事先对智能体的行为环境有确切了解并做详细计划，所以不适合于动态环境，其应用比较有限。,基于符号推理系统的体系结构及协调机制,,基于符号系统的多智能体体系结构与协调机制存在的主要问题是：①符号主义要求对环境有比较完整和复杂的模型，而如何使智能体自身模型的计算和推理与环境保持同步就是一个棘手的问题；②复杂模型计算和推理使智能体对环境的适应能力变差，并且难以满足模型与领域无关性的要求；③对于大型复杂动态系统而言，符号模型建立过程的繁琐和效率低下等问题表现的尤为严重。,基于行为主义的体系结构及协调机制,,基于行为主义的MAS以Brooks的基于行为的系统分析与设计方法为基础，其系统设计有三个基本原则：最小性：系统应尽量简单以便与环境进行快速交互；无状态性：系统本身没有关于外部环境的状态模型，其行为是基于感知——行为的模式进行的；鲁棒性：系统能够有效地处理而不是去除实际环境中的不确定性。 基于行为主义的智能体设计的一般过程：首先确定一些基本行为，通过基本行为的选择和组合来完成所要求的任务，因此，行为选择机制的研究非常重要，也是多智能体协调研究的热点和核心问题。,基于行为主义的体系结构及协调机制,,其基本思想是：由各种基本行为构成一个网状结构，各个结点表示相应的基本行为，而各个结点之间的连接表示为行为的活性，即行为对目标的贡献和效能的一种度量，如果行为促使目标的实现，其活性值为正，反之为负，并且，这种效能越大，其活性值就越大。各种行为之间存在激励或抑制的相互作用影响，于是，相应的活性值就在行为网中进行传播，通过相应的活性传播控制算法就可以对行为进行有效的组合、调度和协调，从而完成复杂任务。,基于协进化方法的体系结构及协调机制,,自然界中的各个物种共同生存于同一个生态系统中，每个物种在其中都有自己的生存环境。由于资源有限，各个物种必须通过竞争和合作才能获得自己生存所需的资源。竞争和合作又促使物种不断进化和改变，并影响彼此的进化过程，这样的过程就称为协进化。 协进化是克服传统进化算法的不足而提出的更为通用的机器学习过程，并适用于多智能体的协调。在协进化计算中，通常考虑多个物种群体，每个物种都有相应的个体类型，各个物种群体采用进化算法实现其进化过程。与常规模拟进化不同的是，在对个体进行适应度评价时，增加对群体间交互协调作用的考虑，对于有利于协调的个体赋予较高的适应度，反之则赋予较低的适应度。这样，促使各个群体向相互协调和适应的方向进化，从而产生协调行为。,多智能体技术的应用,,MAS的应用研究开始于20世纪80年代中期，并表现出明显增长的趋势。 1、智能机器人 智能机器人通常包括多个信息处理子系统，如二维三维视觉处理、信息融合、规划决策以及自动驾驶等。在多机器人系统中，每个机器人作为一个智能体，当多机器人同时从事同一项或多项工作时，利用多智能体技术建立多智能体机器人的协调系统，避免冲突的出现，共同完成复杂并行的作业任务。,多智能体技术的应用,,2、交通控制 如分布式路径指导系统，把交通图知识库中的信息与路径边界搜索算法相结合，项驾驶员提供最佳路径的行驶建议。 3、分布式预测、监控及诊断 再对暴风雨气象观测中，把各区域观测站分别作为一个智能体，各智能体根据观测数据作出局部观测，进行分布式问题求解，然后通过网络和协调机制，最终形成关于整个区域的可靠一致的全局预测。,多智能体技术的应用,,4、柔性制造： 在大型分布式复杂制造系统中，可以把复杂的企业活动划分成多组任务单元，各任务单元由一个智能体执行，同时，把人的行为也看作一类智能体。利用多媒体界面和人-机及机-机等交互方式，通过大量智能体的交互和协调，实现各个地域分散的生产部门之间的知识共享和协调，实现复杂问题的求解和企业各项功能的集成。,多智能体技术的应用,,5、虚拟现实和多智能体社会 虚拟现实是营造人工环境的仿真技术，用户在该环境中能与其他对象进行相互作用。如电子市场，提出了买和卖这两种智能体及其直接交互和代理交互算法，实现了市场中的货物储藏和买卖机制以及银行信贷和金融管理机制。,多智能体技术的应用,,6、网络自动化和智能化 在互联网中为用户自动查找存储于不同地点的资料，帮助用户进行网络搜索，为异地用户建立多媒体会议进程。以一组协同工作的智能体为核心的应用环境下的用户之间的协同工作。 7、网络化的办公自动化 采用智能体分别实现信息的收集、存储、交换、加工和决策，可实现办公自动化系统的人机一体化。,多智能体技术的应用,,8、作战智能体模型研究 作战系统是社会复杂系统，现代战争呈现许多复杂系统的特征，如复杂非线性交互作用、自组织和自适应性、分层的体系结构。近年来，美国等发达国家对复杂性科学和多智能体技术等新方法在作战仿真中的应用进行了探索。,