分布式人工智能课件

高级人工智能第十四章分布式人工智能史忠植

中国科学院计算技术所2022/12/111史忠植高级人工智能高级人工智能第十四章分布式人工智能2022/12/81史内容10.1概述10.2分布式问题求解10.3主体10.4主体理论10.5主体结构10.6主体通信10.7主体的协调与协作10.8多主体环境MAGE2022/12/112史忠植高级人工智能内容10.1概述2022/12/82史忠植高级人工智10.1概述分布式人工智能主要研究在逻辑上或物理上分散的智能系统如何并行的、相互协作地实现问题求解。两种解决问题的方法：自顶向下：分布式问题求解自底向上：基于主体的方法2022/12/113史忠植高级人工智能10.1概述分布式人工智能主要研究在逻辑上或物理上分散的分布式人工智能系统的特色系统中的数据、知识,以及控制不但在逻辑上,而且在物理上是分布的,既没有全局控制,也没有全局的数据存储。各个求解机构由计算机网络互连,在问题求解过程中,通信代价要比求解问题的代价低得多。系统中诸机构能够相互协作,来求解单个机构难以解决,甚至不能解决的任务。2022/12/114史忠植高级人工智能分布式人工智能系统的特色系统中的数据、知识,以及控制不但在分布式人工智能系统的主要优点提高问题求解能力。提高问题求解效率。扩大应用范围。降低软件的复杂性。2022/12/115史忠植高级人工智能分布式人工智能系统的主要优点提高问题求解能力。2022/12分布式人工智能分布式人工智能的研究可以追溯到70年代末期。早期分布式人工智能的研究主要是分布式问题求解，其目标是要创建大粒度的协作群体，它们之间共同工作以对某一问题进行求解。2022/12/116史忠植高级人工智能分布式人工智能分布式人工智能的研究可以追溯到70年代末期。早合同网

1980年Davis和Smith提出了合同网(CNET)CNET使用投标---合同方式实现任务在多个节点上的分配。合同网系统的重要贡献在于提出了通过相互选择和达成协议的协商过程实现分布式任务分配和控制的思想。2022/12/117史忠植高级人工智能合同网2022/12/87史忠植高级人工智能分布式车辆监控测试系统DVMT1980年麻萨诸塞大学的Lesser,Corkill和Durfee等人主持研制DVMT该系统对市区内行驶的车辆轨迹进行监控,并以此环境为基础,对分布式问题求解系统中许多技术问题进行研究。DVMT是以分布式传感网络数据解释为背景，对复杂的黑板问题求解系统之间的相互作用进行了研究，提供了抽象和模型化分布式系统行为的方法。2022/12/118史忠植高级人工智能分布式车辆监控测试系统DVMT1980年麻萨诸塞大学的LeACTOR模型1983年Hewitt和他的同事们研制了基于ACTOR模型的并发程序设计系统。ACTOR模型提供了分布式系统中并行计算理论和一组专家或ACTOR获得智能行为的能力。在1991年Hewitt提出开放信息系统语义,指出竞争、承诺、协作、协商等性质应作为分布式人工智能的科学基础，试图为分布式人工智能的理论研究提供新的基础。2022/12/119史忠植高级人工智能ACTOR模型1983年Hewitt和他的同事们研制了基于MACE系统是一个实验型的分布式人工智能系统开发环境(Gasser1987)。MACE中每一个计算单元都称作主体，它们具有知识表示和推理能力，主体之间通过消息传送进行通信。MACE是一个类面向对象环境，但避开了并发对象系统中难于理解和实现的继承问题。MACE的各个机构并行计算,并提供了描述机构的描述语言,具有跟踪的demons机制。该课题研究的重点是在实际并行环境下运行分布式人工智能系统，保持概念的清晰性。2022/12/1110史忠植高级人工智能MACE系统是一个实验型的分布式人工智能系统开发环境(Gas分布式运输调度系统DTDS-I1989年清华大学石纯一等主持研制了分布式运输调度系统DTDS-I(石纯一1989)。该系统以运输调度为背景，提出了分布式问题求解系统的体系结构，对问题分解、任务分布算法和基于元级通信的协作机制等方面进行了探讨。2022/12/1111史忠植高级人工智能分布式运输调度系统DTDS-I1989年清华大学石纯一等主持分布式知识处理系统DKPS1990中国科学院计算技术研究所史忠植等研究了分布式知识处理系统DKPS。该系统采用逻辑------对象知识模型，研究了知识共享和协作求解等问题。2022/12/1112史忠植高级人工智能分布式知识处理系统DKPS1990中国科学院计算技术研究所史多主体系统

90年代，多主体系统Multiagentsystems)的研究成为分布式人工智能研究的热点。多主体系统主要研究自主的智能主体之间智能行为的协调，为了一个共同的全局目标，也可能是关于各自的不同目标，共享有关问题和求解方法的知识，协作进行问题求解。基于智能主体的概念，人们提出了一种新的人工智能定义：“人工智能是计算机科学的一个分支，它的目标是构造能表现出一定智能行为的主体”。所以，智能主体的研究应该是人工智能的核心问题。斯坦福大学计算机科学系的Hayes-Roth在IJCAI'95的特邀报告中谈到：“智能的计算机主体既是人工智能最初的目标，也是人工智能最终的目标。”2022/12/1113史忠植高级人工智能多主体系统90年代，多主体系统Multiag多主体系统关于主体的研究不仅受到了人工智能研究人员的关注，也吸引了数据通信、人机界面设计、机器人、并行工程等各领域的研究人员的兴趣。有人认为：“基于主体的计算（Agent-BasedComputing，简称ABC）将成为软件开发的下一个重要的突破。”2022/12/1114史忠植高级人工智能多主体系统关于主体的研究不仅受到了人工智能研究人员的关注，也分布式问题求解特点：数据、知识、控制均分布在系统的各节点上，既无全局控制，也无全局数据和知识存储。2022/12/1115史忠植高级人工智能分布式问题求解特点：2022/12/815史忠植高级分布式问题求解两种协作方式：任务分担结果共享2022/12/1116史忠植高级人工智能分布式问题求解两种协作方式：2022/12/816史忠植任务分担

Smith和Davis提出了任务分担方式。在任务分担系统中,结点之间通过分担执行整个任务的子任务而相互协作,系统中的控制以目标为指导,各结点的处理目标是为了求解整个任务的一部分。

任务分担的问题求解方式适合于求解具有层次结构的任务,如工厂联合体生产规划、数字逻辑电路设计、医疗诊断。2022/12/1117史忠植高级人工智能任务分担Smith和Davis提出结果共享

Lesser和Corkill提出了结果共享方式。在结果共享方式的系统中,各结点通过共享部分结果相互协作,系统中的控制以数据为指导,各结点在任何时刻进行的求解取决于当时它本身拥有或从其它结点收到的数据和知识。结果共享的求解方式适合于求解与任务有关的各子任务的结果相互影响,并且部分结果需要综合才能得出问题解的领域。如分布式运输调度系统、分布式车辆监控实验系统DVMT

2022/12/1118史忠植高级人工智能结果共享Lesser和Corkill分布式问题求解系统分类根据组织结构，分布式问题求解系统可以分为三类：层次结构类平行结构类混合结构类2022/12/1119史忠植高级人工智能分布式问题求解系统分类根据组织结构，分布式问题求解系统可以分分布式问题求解过程分布式问题求解过程可以分为四步：任务分解任务分配子问题求解结果综合2022/12/1120史忠植高级人工智能分布式问题求解过程分布式问题求解过程可以分为四步：2022/任务分解

合同网络动态层次控制自然分解,固定分配部分全局规划2022/12/1121史忠植高级人工智能任务分解2022/12/821史忠植高级人工智能分布式问题求解系统中协作的分类按节点间协作量的多少，协作分为三类：全协作系统无协作系统半协作系统常用的通信方式有：共享全局存储器信息传递黑板模型2022/12/1122史忠植高级人工智能分布式问题求解系统中协作的分类按节点间协作量的多少，

主体多主体系统主要研究在逻辑上或物理上分离的多个主体协调其智能行为，即知识、目标、意图及规划等，实现问题求解。可以看作是一种由底向上设计的系统。2022/12/1123史忠植高级人工智能主体多主体系统主要研究在逻辑上或物理上分离的多个主主体的思想智能主体的几个典型的实例：Microsoft的Office助手计算机病毒（破坏主体）计算机游戏或模拟中的智能角色贸易和谈判主体（如Ebay的拍卖主体）网络蜘蛛WebSpider（搜索引擎中的数据搜集和索引主体，如Google）

2022/12/1124史忠植高级人工智能主体的思想智能主体的几个典型的实例：2022/12/824史主体程序设计面向过程的方法面向实体的方法面向对象的方法面向主体的方法软件开发方法的进化2022/12/1125史忠植高级人工智能主体程序设计面向过程的方法面向实体的方法面向对象的方法面向主主体的定义在计算机和人工智能领域中，主体可以看作是一个实体，它通过传感器感知环境，通过效应器作用于环境。2022/12/1126史忠植高级人工智能主体的定义在计算机和人工智能领域中，主体可以看作是一个实体，主体的特性主体弱概念：自治性交互性协作性可通信性长寿性2022/12/1127史忠植高级人工智能主体的特性主体弱概念：2022/12/827史忠植高级人主体的特性主体强概念：知识、信念、意图、承诺等心智状态其它属性：移动性推理能力规划能力学习和适应能力诚实、善意、理性2022/12/1128史忠植高级人工智能主体的特性主体强概念：2022/12/828史忠植高级人

主体理论智能主体的理论模型研究主要从逻辑、行为、心理、社会等角度出发，对智能主体的本质进行描述，为智能主体系统创建奠定基础。2022/12/1129史忠植高级人工智能主体理论智能主体的理论模型研究主要从逻辑、行为、心理、社会理性主体（BDI主体）Belief——信念，主体对环境的基本看法。Desire——愿望，主体想要实现的状态，即目标。Intention——意图，目标的子集。2022/12/1130史忠植高级人工智能理性主体（BDI主体）Belief——信念，主体对环境的基本

BDI主体模型BDI主体模型可以通过下列要素描述：一组关于世界的信念；主体当前打算达到的一组目标；一个规划库，描述怎样达到目标和怎样改变信念；一个意图结构，描述主体当前怎样达到它的目标和改变信念。2022/12/1131史忠植高级人工智能BDI主体模型BDI主体模型可以通过下列要素描述：202BDI解释器BDI-Interpreterinitialize-state();do options:=option-generator(event-queue,B,G,I); selected-options:=deliberate(options,B,G,I); update-intentions(selected-options,I); execute(I); get-new-external-events(); drop-successful-attitudes(B,G,I); drop-impossible-attitudes(B,G,I);untilquit2022/12/1132史忠植高级人工智能BDI解释器BDI-Interpreter2022/12/8

动作理论情景演算是描述动作的主要的形式框架。在情景演算中引入了状态和动作的概念，并利用两条逻辑公理来描述动作与状态的关系。一条公理描述一个动作在满足什么条件的状态之下可能发生，另外一条描述在一个状态之下某个动作发生以后当前状态如何改变。2022/12/1133史忠植高级人工智能动作理论情景演算是描述动作的主要的形式框架。在情景演规划库的形式化表示环境状态：State={P1,P2,…Pn}目标：Goal=<State,weightiness>动作模板：Act_template=<name,roles,preconditions,effects,resources>主体能力：

Ability=<Act_template,role,cost>2022/12/1134史忠植高级人工智能规划库的形式化表示环境状态：2022/12/834史忠植主体结构主体结构需要解决的问题包括：主体由那些模块组成，模块之间如何交互信息，主体感知到的信息如何影响它的行为和内部状态，如何将这些模块用软件或硬件的方式组合起来形成一个有机的整体。2022/12/1135史忠植高级人工智能主体结构主体结构需要解决的问题包括：2022/12/835史主体基本结构环境主体感知作用黑箱软件主体2022/12/1136史忠植高级人工智能主体基本结构环境主体感知作用黑箱软件主体2022/12/83智能主体的工作过程环境交互信息融合信息处理作用交互感知作用2022/12/1137史忠植高级人工智能智能主体的工作过程环境交互信息融合信息处理作用交互感知作用2主体骨架程序functionSkeleton-Agent(percept)returnactionstatic:memory/*主体的世界记忆*/memory←Update-Memory(memory,percept)action←Choose-Best-Action(memory)memory←Update-Memory(memory,action)returnaction2022/12/1138史忠植高级人工智能主体骨架程序functionSkeleton-Agent主体的分类根据人类思维的层次模型，可以将主体分成四类：反应主体形象思维主体抽象思维主体复合式主体形象思维主体和抽象思维主体也可以合称为认知主体2022/12/1139史忠植高级人工智能主体的分类根据人类思维的层次模型，可以将主体分成四类

反应主体环境当前世界传感器动作效应器条件-动作规则主体2022/12/1140史忠植高级人工智能反应主体环当前世界传感器动作效应器条件-动作主体2反应主体程序functionReactive-Agent(percept)returnsactionstatic:rules,/*一组条件-动作规则*/state←Interpret-Input(percept)rule←Rule-Match(state,rules)action←Rule-Action[rule]returnaction2022/12/1141史忠植高级人工智能反应主体程序functionReactive-Agent(认知主体环境信息融合传感器动作效应器主体规划知识库目标内部状态2022/12/1142史忠植高级人工智能认知主体环信息融合传感器动作效应器主体规划知认知主体程序functionCognitive-Agent(percept)returnsaction static:environment,/*描述当前世界环境*/ kb,/*知识库*/environment←Update-World-Model(environment,percept)state←Update-Mental-State(environment,state)action←Decision-Making(state,kb)environment←Update-World-Model(environment,action)returnaction2022/12/1143史忠植高级人工智能认知主体程序functionCognitive-AgentBDI结构知识信念规划意图目标愿望2022/12/1144史忠植高级人工智能BDI结构知信规意图目标愿望复合式主体决策生成规划反射建模通信感知行动其他智能主体智能主体外部世界预测协作与协商动作请求或应答信息一般情况紧急情况和简单情况2022/12/1145史忠植高级人工智能复合式主体决策生成规划反射建模通规划模块世界的模型（包括其他主体的模型）经验库目标集合局部规划器决策生成重新规划规划规划目标2022/12/1146史忠植高级人工智能规划模块世界的模型经验库目标集合局部规划器决建模模块世界的模型（包括其他主体的模型）模型库模型生成和维护预测规划决策生成感知通信建模2022/12/1147史忠植高级人工智能建模模块世界的模型模型库模型生成和通信模块词法库语法库词义库物理通信语言生成语言理解通信2022/12/1148史忠植高级人工智能通信模块词法库语法库词义库物理通信语主体通信策略对话消息黑板协议通信协作协议2022/12/1149史忠植高级人工智能主体通信策略对话消息黑板协主体通信中的主要问题2022/12/1150史忠植高级人工智能主体通信中的主要问题2022/12/850史忠植高级人工主体间的消息传递消息发送/传输服务器转换到传输格式从传输格式转换消息M言语行为意图I目标GAgenti消息MAgenti2022/12/1151史忠植高级人工智能主体间的消息传递消息发送/传输服务器转换到传输格式从传输格式本体论本体论是概念化的明确的表示和描述。对某一领域中的概念有共同理解，可以提高交流和协作的效率，从而提高了软件的重用性。2022/12/1152史忠植高级人工智能本体论本体论是概念化的明确的表示和描述。2022/12/85言语行为有关言语行为理论的研究主要集中在如何划分不同类型的言语行为。在主体通信语言的研究中，言语行为理论主要用来考虑主体之间可以交互的信息类型。2022/12/1153史忠植高级人工智能言语行为有关言语行为理论的研究主要集中在如何划分不同类型的言通信语言KQML：由美国ARPA的知识共享计划中提出，规定了消息格式和消息传送系统，为多主体系统通信和协商提供了一种通用框架。ACL：由FIPA制定的一种规范。与KQML非常相似2022/12/1154史忠植高级人工智能通信语言KQML：由美国ARPA的知识共享计划中提出，规定了KQML一个例子：(ask-all :sender A :receiver B :in-reply-to ido :reply-with idl :language Prolog :ontology foo :content “bar(X,Y)”)2022/12/1155史忠植高级人工智能KQML一个例子：2022/12/855史忠植高级人工智FIPAACL(inform :senderagent1 :receiverhpl-auction-server :content (price(bidgood02)150) :in-reply-toround-4 :reply-withbid04 :languages1 :ontologyhpl-auction)消息结构开始通信动作类型消息参数消息内容表达式参数表达式2022/12/1156史忠植高级人工智能FIPAACL(inform消息结构开始通信动作类型消息FIPA通信动作库AcceptProposal 接受提议Agree 同意Cancel 取消CallforProposal 要求提议Confirm 确认Disconfirm 确认为否定Failure 失败Inform 通知InformIf 通知是否InformRef 通知有关对象NotUnderstood 不理解2022/12/1157史忠植高级人工智能FIPA通信动作库AcceptProposal 接受提议2FIPA通信动作库2022/12/1158史忠植高级人工智能FIPA通信动作库2022/12/858史忠植高级人工智XML—eXtensibleMarkupLanguage

可扩展标记语言

XML是用于标记电子文件使其具有结构性的标记语言。XML文件本身只是将文件资料结构化。

例如：下面的ACL消息

(inform :senderjklabrou :receivergrosof :content(CPUlibretto50pentium) :ontologylaptop :languagekif)2022/12/1159史忠植高级人工智能XML—eXtensibleMarkupLanguage2022/12/1160史忠植高级人工智能2022/12/860史忠植高级人工智能2022/12/1161史忠植高级人工智能2022/12/861史忠植高级人工智能主体的协调与协作协调(coordination)与协作(cooperation)是多主体研究的核心问题之一。协调是指一组智能主体完成一些集体活动时相互作用的性质。协作是非对抗的主体之间保持行为协调的一个特例。2022/12/1162史忠植高级人工智能主体的协调与协作协调(coordination)与协作(c协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望避免主体之间的死锁或活锁。死锁指多个主体无法进行各自的下一步动作；活锁指多个主体不断工作却无任何进展。2022/12/1163史忠植高级人工智能协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工协作目前针对主体协作的研究大体上可分为两类：将其它领域研究多实体行为的方法和技术用于主体协作的研究。如对策论和力学研究。从主体的目标、意图、规划等心智态度出发来研究多主体间的协作。2022/12/1164史忠植高级人工智能协作目前针对主体协作的研究大体上可分为两类：2022/12协作规划协作的动机：某个主体相信通过协作能带来好处（如提高效率，完成以往单独无法完成的任务）多个主体在交流的过程中，发现它们能够通过协作来实现更大的目标。2022/12/1165史忠植高级人工智能协作规划协作的动机：2022/12/865史忠植高级人工协作过程产生需求、确定目标协作规划、求解协作结构寻求协作伙伴选择协作方案实现目标评估结果2022/12/1166史忠植高级人工智能协作过程产生需求、确定目标2022/12/866史忠植高协作模式从社会心理学的角度看，多主体之间的协作情形大致可分为：

·协作型：同时将自己的利益放在第二位。

·自私型：同时将协作放在第二位。

·完全自私型：不考虑任何协作。

·完全协作型：不考虑自身利益。

·协作与自私相混合型。2022/12/1167史忠植高级人工智能协作模式从社会心理学的角度看，多主体之间的协作情形大致可分为协作策略·计算生态学

·对策论

·规划2022/12/1168史忠植高级人工智能协作策略·计算生态学2022/12/868史忠植高计算生态学80年代末，在计算机中出现了一个崭新的学科---计算生态学(theecologofcomputation)。计算生态学是研究关于开放系统中诀定计算结点的行为与资源使用的交互过程的学科。它摒弃了封闭、静止地处理问题的传统算法，将世界看作是开放的、进化的、并发的,通过多种协作处理问题的＂生态系统＂(ecosystem)加以研究。它的进展与开放信息系统的研究息息相关。2022/12/1169史忠植高级人工智能计算生态学80年代末，在计算机中出现了一个崭新的学科-计算生态学

计算生态学将计算系统看作是一个生态系统，它引进了许多生物的机制，如变异(mutation)即物种的变化。这些变化导致生命基因的改变，从而形成物种的多样性，增强了适应环境的能力。这类变异策略成为人工智能系统提高其自身能力的一种方法。Lenat与Brown成功地将变异机制引入他们的AM与Eurisko系统中,通过小型Lisp程序的语法变异发现数学概念。他们认为未来成功的系统应该是一系列进化的、自组织的符号知识结构的``社会"系统。2022/12/1170史忠植高级人工智能计算生态学计算生态学将计算系统看作是一个生态系统，它生物生态模型这是最著名的生态系统，具有典型的进化特征和层次性。这种特性反映在“食物链”中。对于复杂的生物生态系统而言，各物种组成了紧密相连的网络－---食物网。这个系统的主要角色是捕食者与被食者。生命依赖于生命，共同进化，由小的生态环境组成大的生态系统。2022/12/1171史忠植高级人工智能生物生态模型这是最著名的生态系统，具有典型的进化特征和层次性物种进化模型物种进化的“复制者”是基因。从门德尔的植物遗传研究到现代遗传学的成果，都说明了在物种进化过程中，基因的组合与变异起着关键作用。在一个物种的某一群体中基因的集合称为基因池。生物组织是基因的载体。如果环境变化，选择的机制就会改变。这种变化必然引起基因池的变化。特定种群的基因变化称为基因流。一个物种总是不断地经历隔绝、基因流动、变化的循环。开始时，一组地理上隔绝的群体自己孤立地发展，基因在内部快速地流动。随着开放，通过交流和竞争，优胜劣汰。2022/12/1172史忠植高级人工智能物种进化模型物种进化的“复制者”是基因。从门德尔的植物遗传研经济模型经济系统在某种意义上类似于生物生态系统。在商品市场和理想市场中，进化决定于经济实体的决策。选择机制是市场奖励机制。进化是快速的，企业与消费者之间、企业之间主要是一种互相依赖的合作关系。决策者为了追求长远利益，可以采取各种有效的方法，甚至可以暂时做赔本买卖。2022/12/1173史忠植高级人工智能经济模型经济系统在某种意义上类似于生物生态系统。在商品市场和协商模型Zlotkin的面向领域的协商理论Zlotkin的协商理论假设：各主体追求本身效用最大。知识完备。无历史信息。目标集固定。协商在两主体之间同时进行。主体操作集相同。世界仅当主体操作之后发生变化。2022/12/1174史忠植高级人工智能协商模型Zlotkin的面向领域的协商理论2022/12/8面向领域的协商理论在协商过程中，若存在一个双方满意的分配，可以得到一个联合规划,使协商终止的条件是：(1)达成协议：如果Utility(P(i,t))Utility(P(i,t-1)),这一协商过程将在有限步内结束。(2)冲突：如果Utility(P(i,t))=Utility(P(i,t-1)),则无法达成协议。2022/12/1175史忠植高级人工智能面向领域的协商理论在协商过程中，若存在一个双方满意的分配，可最佳平衡传统的协商是基于Nash平衡的,它的缺点是Nash平衡产生多个平衡点,对结果约束较少。Kraus使用Rubinstein的“最佳”平衡(PerfectEquilibrium,简称P.E.)理论,建立了一种基于P.E.的协商方法,需要在协商的任一阶段都产生平衡,即在协商的任一阶段,假设

主体

A使用P.E.策略,则

主体

B除了自己的

P.E.,策略外没有更好的策略可遵循。故若有唯一的

P.E.,并假定主体要使用该策略,则它在协商的每一阶段都只用这一策略。可证明,存在唯一的P.E.,在第一阶段后就可以终止协商。Kraus还将对时间的偏好引入这一理论中。结果表明,时间偏好可以提高协商效率,并仅对某一主体有利。这一理论对于主体的构造和主体之间的协作很有用处,如果为主体提供唯一的P.E.策略,并通知其他主体,则其他主体的最佳选择也是P.E.策略。该理论的缺陷是:缺乏动态性特色,应用面窄,因为尽管存在唯一的P.E,但如何求出仍未得到解决。2022/12/1176史忠植高级人工智能最佳平衡传统的协商是基于Nash平衡的,它的集中式协商方法

Ephrati使用了一种集中式的协商方法,用一个“masteragent”或组投票机制以达成协议。在这种方法中,一组主体的协作与组规划进程相关。Ephrati使用一种动态的、迭代的搜索过程,通过一组约束,使主体递增式地构成一个最大“社会效用”规划。在每一步,各主体对于组规划的下一个联合行动投票。使用这一技术,主体无需完整地展示其偏好,可选状态集在投票之前产生。2022/12/1177史忠植高级人工智能集中式协商方法Ephrati使用了一种集中开放环境多智能体协作方法

Osawa

(1)需求者(requestor)向公告板主体发送需求建议RFP(2)空闲主体向公告板主体申请一个RFP(3)公告板将RFP发到提出申请的空闲主体

(4)空闲主体产生个体规划

(5)空闲主体将其规划发给需求者

(6)需求者调查协作的可能

(7)需求者发送协作奖励

(8)申请者组成协作规划2022/12/1178史忠植高级人工智能开放环境多智能体协作方法Osawa2022/12/8开放环境多智能体协作方法其效用值可用下式计算：

utility(a,g)=worth(a,g)-cost(plan(a,g))

效用的平均是协作的原则。尽管Osawa在一定程度上解决了开放环境中主体协作的问题,但将各主体效用简单相加再平均的方法仍然太弱,因为主体效用仅是主体本身对目标偏好的一种排序关系,不同主体效用一般不能用数值比较。2022/12/1179史忠植高级人工智能开放环境多智能体协作方法其效用值可用下式计算：2022/12交互协议主体之间的会话常常形成典型模式，这种情况下某些消息序列是可知的，这些消息交换的典型模式称为协议。主体间交互的理想情况：主体充分地理解消息的含意和意图，然后根据自身的信念、目标等心智状态，做出相应的回答比较实际的实现：预先规范这些协议，规定好消息的顺序。2022/12/1180史忠植高级人工智能交互协议主体之间的会话常常形成典型模式，这种情况下某些消息序FIPA英国拍卖协议2022/12/1181史忠植高级人工智能FIPA英国拍卖协议2022/12/881史忠植高级人高级人工智能第十四章分布式人工智能史忠植

中国科学院计算技术所2022/12/1182史忠植高级人工智能高级人工智能第十四章分布式人工智能2022/12/81史内容10.1概述10.2分布式问题求解10.3主体10.4主体理论10.5主体结构10.6主体通信10.7主体的协调与协作10.8多主体环境MAGE2022/12/1183史忠植高级人工智能内容10.1概述2022/12/82史忠植高级人工智10.1概述分布式人工智能主要研究在逻辑上或物理上分散的智能系统如何并行的、相互协作地实现问题求解。两种解决问题的方法：自顶向下：分布式问题求解自底向上：基于主体的方法2022/12/1184史忠植高级人工智能10.1概述分布式人工智能主要研究在逻辑上或物理上分散的分布式人工智能系统的特色系统中的数据、知识,以及控制不但在逻辑上,而且在物理上是分布的,既没有全局控制,也没有全局的数据存储。各个求解机构由计算机网络互连,在问题求解过程中,通信代价要比求解问题的代价低得多。系统中诸机构能够相互协作,来求解单个机构难以解决,甚至不能解决的任务。2022/12/1185史忠植高级人工智能分布式人工智能系统的特色系统中的数据、知识,以及控制不但在分布式人工智能系统的主要优点提高问题求解能力。提高问题求解效率。扩大应用范围。降低软件的复杂性。2022/12/1186史忠植高级人工智能分布式人工智能系统的主要优点提高问题求解能力。2022/12分布式人工智能分布式人工智能的研究可以追溯到70年代末期。早期分布式人工智能的研究主要是分布式问题求解，其目标是要创建大粒度的协作群体，它们之间共同工作以对某一问题进行求解。2022/12/1187史忠植高级人工智能分布式人工智能分布式人工智能的研究可以追溯到70年代末期。早合同网

1980年Davis和Smith提出了合同网(CNET)CNET使用投标---合同方式实现任务在多个节点上的分配。合同网系统的重要贡献在于提出了通过相互选择和达成协议的协商过程实现分布式任务分配和控制的思想。2022/12/1188史忠植高级人工智能合同网2022/12/87史忠植高级人工智能分布式车辆监控测试系统DVMT1980年麻萨诸塞大学的Lesser,Corkill和Durfee等人主持研制DVMT该系统对市区内行驶的车辆轨迹进行监控,并以此环境为基础,对分布式问题求解系统中许多技术问题进行研究。DVMT是以分布式传感网络数据解释为背景，对复杂的黑板问题求解系统之间的相互作用进行了研究，提供了抽象和模型化分布式系统行为的方法。2022/12/1189史忠植高级人工智能分布式车辆监控测试系统DVMT1980年麻萨诸塞大学的LeACTOR模型1983年Hewitt和他的同事们研制了基于ACTOR模型的并发程序设计系统。ACTOR模型提供了分布式系统中并行计算理论和一组专家或ACTOR获得智能行为的能力。在1991年Hewitt提出开放信息系统语义,指出竞争、承诺、协作、协商等性质应作为分布式人工智能的科学基础，试图为分布式人工智能的理论研究提供新的基础。2022/12/1190史忠植高级人工智能ACTOR模型1983年Hewitt和他的同事们研制了基于MACE系统是一个实验型的分布式人工智能系统开发环境(Gasser1987)。MACE中每一个计算单元都称作主体，它们具有知识表示和推理能力，主体之间通过消息传送进行通信。MACE是一个类面向对象环境，但避开了并发对象系统中难于理解和实现的继承问题。MACE的各个机构并行计算,并提供了描述机构的描述语言,具有跟踪的demons机制。该课题研究的重点是在实际并行环境下运行分布式人工智能系统，保持概念的清晰性。2022/12/1191史忠植高级人工智能MACE系统是一个实验型的分布式人工智能系统开发环境(Gas分布式运输调度系统DTDS-I1989年清华大学石纯一等主持研制了分布式运输调度系统DTDS-I(石纯一1989)。该系统以运输调度为背景，提出了分布式问题求解系统的体系结构，对问题分解、任务分布算法和基于元级通信的协作机制等方面进行了探讨。2022/12/1192史忠植高级人工智能分布式运输调度系统DTDS-I1989年清华大学石纯一等主持分布式知识处理系统DKPS1990中国科学院计算技术研究所史忠植等研究了分布式知识处理系统DKPS。该系统采用逻辑------对象知识模型，研究了知识共享和协作求解等问题。2022/12/1193史忠植高级人工智能分布式知识处理系统DKPS1990中国科学院计算技术研究所史多主体系统

90年代，多主体系统Multiagentsystems)的研究成为分布式人工智能研究的热点。多主体系统主要研究自主的智能主体之间智能行为的协调，为了一个共同的全局目标，也可能是关于各自的不同目标，共享有关问题和求解方法的知识，协作进行问题求解。基于智能主体的概念，人们提出了一种新的人工智能定义：“人工智能是计算机科学的一个分支，它的目标是构造能表现出一定智能行为的主体”。所以，智能主体的研究应该是人工智能的核心问题。斯坦福大学计算机科学系的Hayes-Roth在IJCAI'95的特邀报告中谈到：“智能的计算机主体既是人工智能最初的目标，也是人工智能最终的目标。”2022/12/1194史忠植高级人工智能多主体系统90年代，多主体系统Multiag多主体系统关于主体的研究不仅受到了人工智能研究人员的关注，也吸引了数据通信、人机界面设计、机器人、并行工程等各领域的研究人员的兴趣。有人认为：“基于主体的计算（Agent-BasedComputing，简称ABC）将成为软件开发的下一个重要的突破。”2022/12/1195史忠植高级人工智能多主体系统关于主体的研究不仅受到了人工智能研究人员的关注，也分布式问题求解特点：数据、知识、控制均分布在系统的各节点上，既无全局控制，也无全局数据和知识存储。2022/12/1196史忠植高级人工智能分布式问题求解特点：2022/12/815史忠植高级分布式问题求解两种协作方式：任务分担结果共享2022/12/1197史忠植高级人工智能分布式问题求解两种协作方式：2022/12/816史忠植任务分担

Smith和Davis提出了任务分担方式。在任务分担系统中,结点之间通过分担执行整个任务的子任务而相互协作,系统中的控制以目标为指导,各结点的处理目标是为了求解整个任务的一部分。

任务分担的问题求解方式适合于求解具有层次结构的任务,如工厂联合体生产规划、数字逻辑电路设计、医疗诊断。2022/12/1198史忠植高级人工智能任务分担Smith和Davis提出结果共享

Lesser和Corkill提出了结果共享方式。在结果共享方式的系统中,各结点通过共享部分结果相互协作,系统中的控制以数据为指导,各结点在任何时刻进行的求解取决于当时它本身拥有或从其它结点收到的数据和知识。结果共享的求解方式适合于求解与任务有关的各子任务的结果相互影响,并且部分结果需要综合才能得出问题解的领域。如分布式运输调度系统、分布式车辆监控实验系统DVMT

2022/12/1199史忠植高级人工智能结果共享Lesser和Corkill分布式问题求解系统分类根据组织结构，分布式问题求解系统可以分为三类：层次结构类平行结构类混合结构类2022/12/11100史忠植高级人工智能分布式问题求解系统分类根据组织结构，分布式问题求解系统可以分分布式问题求解过程分布式问题求解过程可以分为四步：任务分解任务分配子问题求解结果综合2022/12/11101史忠植高级人工智能分布式问题求解过程分布式问题求解过程可以分为四步：2022/任务分解

合同网络动态层次控制自然分解,固定分配部分全局规划2022/12/11102史忠植高级人工智能任务分解2022/12/821史忠植高级人工智能分布式问题求解系统中协作的分类按节点间协作量的多少，协作分为三类：全协作系统无协作系统半协作系统常用的通信方式有：共享全局存储器信息传递黑板模型2022/12/11103史忠植高级人工智能分布式问题求解系统中协作的分类按节点间协作量的多少，

主体多主体系统主要研究在逻辑上或物理上分离的多个主体协调其智能行为，即知识、目标、意图及规划等，实现问题求解。可以看作是一种由底向上设计的系统。2022/12/11104史忠植高级人工智能主体多主体系统主要研究在逻辑上或物理上分离的多个主主体的思想智能主体的几个典型的实例：Microsoft的Office助手计算机病毒（破坏主体）计算机游戏或模拟中的智能角色贸易和谈判主体（如Ebay的拍卖主体）网络蜘蛛WebSpider（搜索引擎中的数据搜集和索引主体，如Google）

2022/12/11105史忠植高级人工智能主体的思想智能主体的几个典型的实例：2022/12/824史主体程序设计面向过程的方法面向实体的方法面向对象的方法面向主体的方法软件开发方法的进化2022/12/11106史忠植高级人工智能主体程序设计面向过程的方法面向实体的方法面向对象的方法面向主主体的定义在计算机和人工智能领域中，主体可以看作是一个实体，它通过传感器感知环境，通过效应器作用于环境。2022/12/11107史忠植高级人工智能主体的定义在计算机和人工智能领域中，主体可以看作是一个实体，主体的特性主体弱概念：自治性交互性协作性可通信性长寿性2022/12/11108史忠植高级人工智能主体的特性主体弱概念：2022/12/827史忠植高级人主体的特性主体强概念：知识、信念、意图、承诺等心智状态其它属性：移动性推理能力规划能力学习和适应能力诚实、善意、理性2022/12/11109史忠植高级人工智能主体的特性主体强概念：2022/12/828史忠植高级人

主体理论智能主体的理论模型研究主要从逻辑、行为、心理、社会等角度出发，对智能主体的本质进行描述，为智能主体系统创建奠定基础。2022/12/11110史忠植高级人工智能主体理论智能主体的理论模型研究主要从逻辑、行为、心理、社会理性主体（BDI主体）Belief——信念，主体对环境的基本看法。Desire——愿望，主体想要实现的状态，即目标。Intention——意图，目标的子集。2022/12/11111史忠植高级人工智能理性主体（BDI主体）Belief——信念，主体对环境的基本

BDI主体模型BDI主体模型可以通过下列要素描述：一组关于世界的信念；主体当前打算达到的一组目标；一个规划库，描述怎样达到目标和怎样改变信念；一个意图结构，描述主体当前怎样达到它的目标和改变信念。2022/12/11112史忠植高级人工智能BDI主体模型BDI主体模型可以通过下列要素描述：202BDI解释器BDI-Interpreterinitialize-state();do options:=option-generator(event-queue,B,G,I); selected-options:=deliberate(options,B,G,I); update-intentions(selected-options,I); execute(I); get-new-external-events(); drop-successful-attitudes(B,G,I); drop-impossible-attitudes(B,G,I);untilquit2022/12/11113史忠植高级人工智能BDI解释器BDI-Interpreter2022/12/8

动作理论情景演算是描述动作的主要的形式框架。在情景演算中引入了状态和动作的概念，并利用两条逻辑公理来描述动作与状态的关系。一条公理描述一个动作在满足什么条件的状态之下可能发生，另外一条描述在一个状态之下某个动作发生以后当前状态如何改变。2022/12/11114史忠植高级人工智能动作理论情景演算是描述动作的主要的形式框架。在情景演规划库的形式化表示环境状态：State={P1,P2,…Pn}目标：Goal=<State,weightiness>动作模板：Act_template=<name,roles,preconditions,effects,resources>主体能力：

Ability=<Act_template,role,cost>2022/12/11115史忠植高级人工智能规划库的形式化表示环境状态：2022/12/834史忠植主体结构主体结构需要解决的问题包括：主体由那些模块组成，模块之间如何交互信息，主体感知到的信息如何影响它的行为和内部状态，如何将这些模块用软件或硬件的方式组合起来形成一个有机的整体。2022/12/11116史忠植高级人工智能主体结构主体结构需要解决的问题包括：2022/12/835史主体基本结构环境主体感知作用黑箱软件主体2022/12/11117史忠植高级人工智能主体基本结构环境主体感知作用黑箱软件主体2022/12/83智能主体的工作过程环境交互信息融合信息处理作用交互感知作用2022/12/11118史忠植高级人工智能智能主体的工作过程环境交互信息融合信息处理作用交互感知作用2主体骨架程序functionSkeleton-Agent(percept)returnactionstatic:memory/*主体的世界记忆*/memory←Update-Memory(memory,percept)action←Choose-Best-Action(memory)memory←Update-Memory(memory,action)returnaction2022/12/11119史忠植高级人工智能主体骨架程序functionSkeleton-Agent主体的分类根据人类思维的层次模型，可以将主体分成四类：反应主体形象思维主体抽象思维主体复合式主体形象思维主体和抽象思维主体也可以合称为认知主体2022/12/11120史忠植高级人工智能主体的分类根据人类思维的层次模型，可以将主体分成四类

反应主体环境当前世界传感器动作效应器条件-动作规则主体2022/12/11121史忠植高级人工智能反应主体环当前世界传感器动作效应器条件-动作主体2反应主体程序functionReactive-Agent(percept)returnsactionstatic:rules,/*一组条件-动作规则*/state←Interpret-Input(percept)rule←Rule-Match(state,rules)action←Rule-Action[rule]returnaction2022/12/11122史忠植高级人工智能反应主体程序functionReactive-Agent(认知主体环境信息融合传感器动作效应器主体规划知识库目标内部状态2022/12/11123史忠植高级人工智能认知主体环信息融合传感器动作效应器主体规划知认知主体程序functionCognitive-Agent(percept)returnsaction static:environment,/*描述当前世界环境*/ kb,/*知识库*/environment←Update-World-Model(environment,percept)state←Update-Mental-State(environment,state)action←Decision-Making(state,kb)environment←Update-World-Model(environment,action)returnaction2022/12/11124史忠植高级人工智能认知主体程序functionCognitive-AgentBDI结构知识信念规划意图目标愿望2022/12/11125史忠植高级人工智能BDI结构知信规意图目标愿望复合式主体决策生成规划反射建模通信感知行动其他智能主体智能主体外部世界预测协作与协商动作请求或应答信息一般情况紧急情况和简单情况2022/12/11126史忠植高级人工智能复合式主体决策生成规划反射建模通规划模块世界的模型（包括其他主体的模型）经验库目标集合局部规划器决策生成重新规划规划规划目标2022/12/11127史忠植高级人工智能规划模块世界的模型经验库目标集合局部规划器决建模模块世界的模型（包括其他主体的模型）模型库模型生成和维护预测规划决策生成感知通信建模2022/12/11128史忠植高级人工智能建模模块世界的模型模型库模型生成和通信模块词法库语法库词义库物理通信语言生成语言理解通信2022/12/11129史忠植高级人工智能通信模块词法库语法库词义库物理通信语主体通信策略对话消息黑板协议通信协作协议2022/12/11130史忠植高级人工智能主体通信策略对话消息黑板协主体通信中的主要问题2022/12/11131史忠植高级人工智能主体通信中的主要问题2022/12/850史忠植高级人工主体间的消息传递消息发送/传输服务器转换到传输格式从传输格式转换消息M言语行为意图I目标GAgenti消息MAgenti2022/12/11132史忠植高级人工智能主体间的消息传递消息发送/传输服务器转换到传输格式从传输格式本体论本体论是概念化的明确的表示和描述。对某一领域中的概念有共同理解，可以提高交流和协作的效率，从而提高了软件的重用性。2022/12/11133史忠植高级人工智能本体论本体论是概念化的明确的表示和描述。2022/12/85言语行为有关言语行为理论的研究主要集中在如何划分不同类型的言语行为。在主体通信语言的研究中，言语行为理论主要用来考虑主体之间可以交互的信息类型。2022/12/11134史忠植高级人工智能言语行为有关言语行为理论的研究主要集中在如何划分不同类型的言通信语言KQML：由美国ARPA的知识共享计划中提出，规定了消息格式和消息传送系统，为多主体系统通信和协商提供了一种通用框架。ACL：由FIPA制定的一种规范。与KQML非常相似2022/12/11135史忠植高级人工智能通信语言KQML：由美国ARPA的知识共享计划中提出，规定了KQML一个例子：(ask-all :sender A :receiver B :in-reply-to ido :reply-with idl :language Prolog :ontology foo :content “bar(X,Y)”)2022/12/11136史忠植高级人工智能KQML一个例子：2022/12/855史忠植高级人工智FIPAACL(inform :senderagent1 :receiverhpl-auction-server :content (price(bidgood02)150) :in-reply-toround-4 :reply-withbid04 :languages1 :ontologyhpl-auction)消息结构开始通信动作类型消息参数消息内容表达式参数表达式2022/12/11137史忠植高级人工智能FIPAACL(inform消息结构开始通信动作类型消息FIPA通信动作库AcceptProposal 接受提议Agree 同意Cancel 取消CallforProposal 要求提议Confirm 确认Disconfirm 确认为否定Failure 失败Inform 通知InformIf 通知是否InformRef 通知有关对象NotUnderstood 不理解2022/12/11138史忠植高级人工智能FIPA通信动作库AcceptProposal 接受提议2FIPA通信动作库2022/12/11139史忠植高级人工智能FIPA通信动作库2022/12/858史忠植高级人工智XML—eXtensibleMarkupLanguage

可扩展标记语言

XML是用于标记电子文件使其具有结构性的标记语言。XML文件本身只是将文件资料结构化。

例如：下面的ACL消息

(inform :senderjklabrou :receivergrosof :content(CPUlibretto50pentium) :ontologylaptop :languagekif)2022/12/11140史忠植高级人工智能XML—eXtensibleMarkupLanguage2022/12/11141史忠植高级人工智能2022/12/860史忠植高级人工智能2022/12/11142史忠植高级人工智能2022/12/861史忠植高级人工智能主体的协调与协作协调(coordination)与协作(cooperation)是多主体研究的核心问题之一。协调是指一组智能主体完成一些集体活动时相互作用的性质。协作是非对抗的主体之间保持行为协调的一个特例。2022/12/11143史忠植高级人工智能主体的协调与协作协调(coordination)与协作(c协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望避免主体之间的死锁或活锁。死锁指多个主体无法进行各自的下一步动作；活锁指多个主体不断工作却无任何进展。2022/12/11144史忠植高级人工智能协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工协作目前针对主体协作的研究大体上可分为两类：将其它领域研究多实体行为的方法和技术用于主体协作的研究。如对策论和力学研究。从主体的目标、意图、规划等心智态度出发来研究多主体间的协作。2022/12/11145史忠植高级人工智能协作目前针对主体协作的研究大体上可分为两类：2022/12协作规划协作的动机：某个主体相信通过协作能带来好处（如提高效率，完成以往单独无法完成的任务）多个主体在交流的过程中，发现它们能够通过协作来实现更大的目标。2022/12/11146史忠植高级人工智能协作规划协作的动机：2022/12/865史忠植高级人工协作过程产生需求、确定目标协作规划、求解协作结构寻求协作伙伴选择协作方案实现目标评估结果2022/12/11147史忠植高级人工智能协作过程产生需求、确定目标2022/12/866史忠植高协作模式从社会心理学的角度看，多主体之间的协作情形大致可分为：

·协作型：同时将自己的利益放在第二位。

·自私型：同时将协作放在第二位。

·完全自私型：不考虑任何协作。

·完全协作型：不考虑自身利益。

·协作与自私相混合型。2022/12/11148史忠植高级人工智能协作模式从社会心理学的角度看，多主体之间的协作情形大致可分为协作策略·计算生态学

·对策论

·规划2022/12/11149史忠植高级人工智能协作策略·计算生态学2022/12/868史忠植高计算生态学80年代末，在计算机中出现了一个崭新的学科---计算生态学(theecologofcomputation)。计算生态学是研究关于开放系统中诀定计算结点的行为与资源使用的交互过程的学科。它摒弃了封闭、静止地处理问题的传统算法，将世界看作是开放的、进化的、并发的,通过多种协作处理问题的＂生态系统＂(ecosystem)加以研究。它的进展与开放信息系统的研究息息相关。2022/12/11150史忠植高级人工智能计算生态学80年代末，在计算机中出现了一个崭新的学科-计算生态学

计算生态学将计算系统看作是一个生态系统，它引进了许多生物的机制，如变异(mutation)即物种的变化。这些变化导致生命基因的改变，从而形成物种的多样性，增强了适应环境的能力。这类变异策略成为人工智能系统提高其自身能力的一种方法。Lenat与Brown成功地将变异机制引入他们的AM与Eurisko系统中,通过小型Lisp程序的语法变异发现数学概