第十四章分布式人工智能

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

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

1980年Davis和Smith提出了合同网(CNET)CNET使用投标---合同方式实现任务在多个节点上的分配。合同网系统的重要贡献在于提出了通过相互选择和达成协议的协商过程实现分布式任务分配和控制的思想。2023/1/157分布式车辆监控测试系统DVMT1980年麻萨诸塞大学的Lesser,Corkill和Durfee等人主持研制DVMT该系统对市区内行驶的车辆轨迹进行监控,并以此环境为基础,对分布式问题求解系统中许多技术问题进行研究。DVMT是以分布式传感网络数据解释为背景，对复杂的黑板问题求解系统之间的相互作用进行了研究，提供了抽象和模型化分布式系统行为的方法。2023/1/158ACTOR模型1983年Hewitt和他的同事们研制了基于ACTOR模型的并发程序设计系统。ACTOR模型提供了分布式系统中并行计算理论和一组专家或ACTOR获得智能行为的能力。在1991年Hewitt提出开放信息系统语义,指出竞争、承诺、协作、协商等性质应作为分布式人工智能的科学基础，试图为分布式人工智能的理论研究提供新的基础。2023/1/159MACE系统是一个实验型的分布式人工智能系统开发环境(Gasser1987)。MACE中每一个计算单元都称作主体，它们具有知识表示和推理能力，主体之间通过消息传送进行通信。MACE是一个类面向对象环境，但避开了并发对象系统中难于理解和实现的继承问题。MACE的各个机构并行计算,并提供了描述机构的描述语言,具有跟踪的demons机制。该课题研究的重点是在实际并行环境下运行分布式人工智能系统，保持概念的清晰性。2023/1/1510分布布式式运运输输调调度度系系统统DTDS-I1989年清清华华大大学学石石纯纯一一等等主主持持研研制制了了分分布布式式运运输输调调度度系系统统DTDS-I(石纯纯一一1989)。该系系统统以以运运输输调调度度为为背背景景，，提提出出了了分分布布式式问问题题求求解解系系统统的的体体系系结结构构，，对对问问题题分分解解、、任任务务分分布布算算法法和和基基于于元元级级通通信信的的协协作作机机制制等等方方面面进进行行了了探探讨讨。。2022/12/3111分布布式式知知识识处处理理系系统统DKPS1990中国国科科学学院院计计算算技技术术研研究究所所史史忠忠植植等等研研究究了了分分布布式式知知识识处处理理系系统统DKPS。该系系统统采采用用逻逻辑辑------对象象知知识识模模型型，，研研究究了了知知识识共共享享和和协协作作求求解解等等问问题题。。2022/12/3112多主体体系统统90年代，，多主主体系系统Multiagentsystems)的研究究成为为分布布式人人工智智能研研究的的热点点。多多主体体系统统主要要研究究自主主的智智能主主体之之间智智能行行为的的协调调，为为了一一个共共同的的全局局目标标，也也可能能是关关于各各自的的不同同目标标，共共享有有关问问题和和求解解方法法的知知识，，协作作进行行问题题求解解。基于智智能主主体的的概念念，人人们提提出了了一种种新的的人工工智能能定义义：““人工工智能能是计计算机机科学学的一一个分分支，，它的的目标标是构构造能能表现现出一一定智智能行行为的的主体体”。。所以，，智能能主体体的研研究应应该是是人工工智能能的核核心问问题。。斯坦坦福大学计计算机机科学学系的的Hayes-Roth在IJCAI'95的特邀邀报告告中谈谈到：：“智智能的的计算算机主主体既既是人人工智智能最最初的的目标标，也也是人人工智智能最最终的的目标标。””2022/12/3113多主体系统统关于主体的的研究不仅仅受到了人人工智能研研究人员的的关注，也也吸引了数数据通信、、人机界面面设计、机机器人、并并行工程等等各领域的的研究人员员的兴趣。。有人认为为：“基于于主体的计计算（Agent-BasedComputing，简称ABC）将成为软件件开发的下下一个重要要的突破。。”2022/12/3114分布式问题题求解特点：数据、知识识、控制均均分布在系系统的各节节点上，既既无全局控控制，也无无全局数据据和知识存存储。2022/12/3115分布式问题题求解两种协作作方式：：任务分担担结果共享享2022/12/3116任务分担担Smith和Davis提出了任任务分担担方式。。在任务务分担系系统中,结点之间间通过分分担执行行整个任任务的子子任务而而相互协协作,系统中的的控制以以目标为为指导,各结点的的处理目目标是为为了求解解整个任任务的一一部分。。任务分担担的问题题求解方方式适合合于求解解具有层层次结构构的任务务,如工厂联联合体生生产规划划、数数字逻辑辑电路设设计、医医疗诊诊断。2022/12/3117结果共享享Lesser和Corkill提出了结果共共享方式。在在结果共享方方式的系统中中,各结点通过共共享部分结果果相互协作,系统中的控制制以数据为指指导,各结点在任何何时刻进行的的求解取决于于当时它本身身拥有或从其其它结点收到到的数据和知知识。结果共享的求求解方式适合合于求解与任任务有关的各各子任务的结结果相互影响响,并且部分结果果需要综合才才能得出问题题解的领域。。如分布式运运输调度系统统、分布式车车辆监控实验验系统DVMT2022/12/3118分布式问题求求解系统分类类根据组织结构构，分布式问问题求解系统统可以分为三三类：层次结构类平行结构类混合结构类2022/12/3119分布式问题题求解过程程分布式问题题求解过程程可以分为为四步：任务分解任务分配子问题求解解结果综合2022/12/3120任务分解合同网络动态层次控控制自然分解,固定分配部分全局规规划2022/12/3121分布式问题题求解系统统中协作的的分类按节点间协协作量的多多少，协作作分为三类类：全协作系统统无协作系统统半协作系统统常用的通信信方式有：：共享全局存存储器信息传递黑板模型2022/12/3122主体体多主体系统统主要研究究在逻辑上上或物理上上分离的多多个主体协协调其智能能行为，即即知识、目目标、意图图及规划等等，实现问问题求解。。可以看作作是一种由由底向上设设计的系统统。2022/12/3123主体的思想想智能主体的的几个典型型的实例：：Microsoft的Office助手计算机病毒毒（破坏主主体）计算机游戏戏或模拟中中的智能角角色贸易和谈判判主体（如如Ebay的拍卖主体体）网络蜘蛛WebSpider（搜索引擎中中的数据搜搜集和索引引主体，如如Google）2022/12/3124主体程序设设计面向过程的的方法面向实体的的方法面向对象的的方法面向主体的的方法软件开发方方法的进化化2022/12/3125主体体的的定定义义在计计算算机机和和人人工工智智能能领领域域中中，，主主体体可可以以看看作作是是一一个个实实体体，，它它通通过过传传感感器器感感知知环环境境，，通通过过效效应应器器作作用用于于环环境境。。2022/12/3126主体体的的特特性性主体体弱弱概概念念：：自治治性性交互互性性协作作性性可通通信信性性长寿寿性性2022/12/3127主体体的的特特性性主体体强强概概念念：：知识识、、信信念念、、意意图图、、承承诺诺等等心心智智状状态态其它它属属性性：：移动动性性推理理能能力力规划划能能力力学习习和和适适应应能能力力诚实实、、善善意意、、理理性性2022/12/3128主体体理理论论智能能主主体体的的理理论论模模型型研研究究主主要要从从逻逻辑辑、、行行为为、、心心理理、、社社会会等等角角度度出出发发，，对对智智能能主主体体的的本本质质进进行行描描述述，，为为智智能能主主体体系系统统创创建建奠奠定定基基础础。。2022/12/3129理性性主主体体（（BDI主体体））Belief————信念念，，主主体体对对环环境境的的基基本本看看法法。。Desire————愿望望，，主主体体想想要要实实现现的的状状态态，，即即目目标标。。Intention————意图图，，目目标标的的子子集集。。2022/12/3130BDI主体模型型BDI主体模型型可以通通过下列列要素描描述：一组关于于世界的的信念；；主体当前前打算达达到的一一组目标标；一个规划划库，描描述怎样样达到目目标和怎怎样改变变信念；；一个意图图结构，，描述主主体当前前怎样达达到它的的目标和和改变信信念。2022/12/3131BDI解释器BDI-Interpreterinitialize-state();dooptions:=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/3132动作理论情景演算是是描述动作作的主要的的形式框架架。在情情景演算中中引入了状状态和动作作的概念，，并利用两两条逻辑公公理来描述述动作与状状态的关系系。一条公公理描述一一个动作在在满足什么么条件的状状态之下可可能发生，，另外一条条描述在一一个状态之之下某个动动作发生以以后当前状状态如何改改变。2022/12/3133规划库的形形式化表示示环境状态：：State={P1,P2,…Pn}目标：Goal=<State,weightiness>动作模板：：Act_template=<name,roles,preconditions,effects,resources>主体能力：：Ability=<Act_template,role,cost>2022/12/3134主体体结结构构主体体结结构构需需要要解解决决的的问问题题包包括括：：主体体由由那那些些模模块块组组成成，，模块块之之间间如如何何交交互互信信息息，，主体体感感知知到到的的信信息息如如何何影影响响它它的的行行为为和和内内部部状状态态，，如何何将将这这些些模模块块用用软软件件或或硬硬件件的的方方式式组组合合起起来来形形成成一一个个有有机机的的整整体体。。2022/12/3135主体基本结构构环境主体感知作用黑箱软件主体体2022/12/3136智能主体的工工作过程环境交互信息融合信息处理作用交互感知作用2022/12/3137主体骨骨架程程序functionSkeleton-Agent(percept)returnactionstatic:memory/*主体的的世界界记忆忆*/memory←←Update-Memory(memory,percept)action←←Choose-Best-Action(memory)memory←←Update-Memory(memory,action)returnaction2022/12/3138主体的的分类类根据人人类思思维的的层次次模型型，可可以将将主体体分成成四类类：反应主主体形象思思维主主体抽象思思维主主体复合式式主体体形象思思维主主体和和抽象象思维维主体体也可可以合合称为为认知知主体体2022/12/3139反应应主主体体环境当前前世世界界传感感器器动作作效应应器器条件件-动动作作规则则主体体2022/12/3140反应应主主体体程程序序functionReactive-Agent(percept)returnsactionstatic:rules,/*一组组条条件件-动动作作规规则则*/state←←Interpret-Input(percept)rule←←Rule-Match(state,rules)action←←Rule-Action[rule]returnaction2022/12/3141认知主体体环境信息融合合传感器动作作效应器主体规划划知识库目标内部状态态2022/12/3142认知主体体程序functionCognitive-Agent(percept)returnsactionstatic: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/3143BDI结构知识信念规划意图图目标标愿望望2022/12/3144复合式主体体决策生成规划划反射射建模模通信信感知知行动动其他智能主体智能主体外部世界预测协作与协商商动作请求或应答答信息一般情况紧急情况和简单情况2022/12/3145规划模块世界的模型型（包括其他他主体的模型型）经验库库目标集合局部规规划器器决策生生成重新规划规划规划目标2022/12/3146建模模块世界的模型型（包括其他他主体的模型型）模型库库模型生生成成和和维护护预测测规划决策生成感知通信建模2022/12/3147通信模块词法库库语法库库词义库库物理通信语言生成语言理解通信2022/12/3148主体通信策略略对话话消息息黑板板协议议通信协作协议议2022/12/3149主体通信中的的主要问题2022/12/3150主体间的消息息传递消息发送/传传输服务器转换到传输格格式从传输格式转转换消息M言语行为意图I目标GAgenti消息MAgenti2022/12/3151本体论本体论是概念念化的明确的的表示和描述述。对某一领域中中的概念有共共同理解，可可以提高交流流和协作的效效率，从而提提高了软件的的重用性。2022/12/3152言语行行为有关言言语行行为理理论的的研究究主要要集中中在如如何划划分不不同类类型的的言语语行为为。在主体体通信信语言言的研研究中中，言言语行行为理理论主主要用用来考考虑主主体之之间可可以交交互的的信息息类型型。2022/12/3153通信信语语言言KQML：：由美美国国ARPA的知知识识共共享享计计划划中中提提出出，，规规定定了了消消息息格格式式和和消消息息传传送送系系统统，，为为多多主主体体系系统统通通信信和和协协商商提提供供了了一一种种通通用用框框架架。。ACL：：由FIPA制定定的的一一种种规规范范。。与与KQML非常常相相似似2022/12/3154KQML一个例子子：(ask-all:senderA:receiverB:in-reply-toido:reply-withidl:languageProlog:ontologyfoo:content““bar(X,Y)”)2022/12/3155FIPAACL(inform:senderagent1:receiverhpl-auction-server:content(price(bidgood02)150):in-reply-toround-4:reply-withbid04:languages1:ontologyhpl-auction)消息结构开开始通信动作类类型消息参数消息内容表表达式参数表达式式2022/12/3156FIPA通信动作库库AcceptProposal接受提议Agree同意Cancel取消CallforProposal要求提议Confirm确认Disconfirm确认为否定定Failure失败Inform通知InformIf通知是否否InformRef通知有关关对象NotUnderstood不理解2022/12/3157FIPA通信动作库库2022/12/3158XML—eXtensibleMarkupLanguage可扩展标记记语言XML是用于标记记电子文件件使其具有有结构性的的标记语言言。XML文件本身只只是将文件件资料结构构化。例如：下面面的ACL消息(inform:senderjklabrou:receivergrosof:content(CPUlibretto50pentium):ontologylaptop:languagekif)2022/12/31592022/12/31602022/12/3161主体体的的协协调调与与协协作作协调调(coordination)与协协作作(cooperation)是多多主主体体研研究究的的核核心心问问题题之之一一。。协调调是是指指一一组组智智能能主主体体完完成成一一些些集集体体活活动动时时相相互互作作用用的的性性质质。。协作是非对抗抗的主体之间间保持行为协协调的一个特特例。2022/12/3162协调多主体系统中中的协调是指指多个主体为为了以一致、、和谐的方式式工作而进行行交互的过程程。进行协调调是希望避免免主体之间的的死锁或活锁锁。死锁指多个主主体无法进行行各自的下一一步动作；活锁指多个主主体不断工作作却无任何进进展。2022/12/3163协作目前针针对主主体协协作的的研究究大体体上可可分为为两类类：将其它它领域域研究究多实实体行行为的的方法法和技技术用用于主主体协协作的的研究究。如如对策策论和和力学学研究究。从主体体的目目标、、意图图、规规划等等心智智态度度出发发来研研究多多主体体间的的协作作。2022/12/3164协作规规划协作的的动机机：某个主主体相相信通通过协协作能能带来来好处处（如如提高高效率率，完完成以以往单单独无无法完完成的的任务务）多个主主体在在交流流的过过程中中，发发现它它们能能够通通过协协作来来实现现更大大的目目标。。2022/12/3165协作过程程产生需求求、确定定目标协作规划划、求解解协作结结构寻求协作作伙伴选择协作作方案实现目标标评估结果果2022/12/3166协作模式式从社会心心理学的的角度看看，多主主体之间间的协作作情形大大致可分分为：·协作型：同时时将自己的利利益放在第二二位。·自私型：同时时将协作放在在第二位。·完全自私型：：不考虑任何何协作。·完全协作型：：不考虑自身身利益。·协作与自私相相混合型。2022/12/3167协作策略·计算生态学学·对策论·规划2022/12/3168计算生态学学80年代末，在在计算机中中出现了一一个崭新的的学科---计算生态学学(theecologofcomputation)。计算生态态学是研究究关于开放放系统中诀诀定计算结结点的行为为与资源使使用的交互互过程的学学科。它摒摒弃了封闭闭、静止地地处理问题题的传统算算法，将世世界看作是是开放的、、进化的、、并发的,通过过多多种种协协作作处处理理问问题题的的＂＂生生态态系系统统＂＂(ecosystem)加以以研研究究。。它它的的进进展展与与开开放放信信息息系系统统的的研研究究息息息息相相关关。。2022/12/3169计算算生生态态学学计算算生生态态学学将将计计算算系系统统看看作作是是一一个个生生态态系系统统，，它它引引进进了了许许多多生生物物的的机机制制，，如如变变异异(mutation)即物物种种的的变变化化。。这这些些变变化化导导致致生生命命基基因因的的改改变变，，从从而而形形成成物物种种的的多多样样性性，，增增强强了了适适应应环环境境的的能能力力。。这这类类变变异异策策略略成成为为人人工工智智能能系系统统提提高高其其自自身身能能力力的的一一种种方方法法。。Lenat与Brown成功功地地将将变变异异机机制制引引入入他他们们的的AM与Eurisko系统统中中,通过过小小型型Lisp程序序的的语语法法变变异异发发现现数数学学概概念念。。他他们们认认为为未未来来成成功功的的系系统统应应该该是是一一系系列列进进化化的的、、自自组组织织的的符符号号知知识识结结构构的的``社会会"系统统。。2022/12/3170生物生生态模模型这是最最著名名的生生态系系统，，具有有典型型的进进化特特征和和层次次性。。这种种特性性反映映在““食物物链””中。。对于于复杂杂的生生物生生态系系统而而言，，各物物种组组成了了紧密密相连连的网网络－－---食物网网。这这个系系统的的主要要角色色是捕捕食者者与被被食者者。生生命依依赖于于生命命，共共同进进化，，由小小的生生态环环境组组成大大的生生态系系统。。2022/12/3171物种进进化模模型物种进进化的的“复复制者者”是是基因因。从从门德德尔的的植物物遗传传研究究到现现代遗遗传学学的成成果，，都说说明了了在物物种进进化过过程中中，基基因的的组合合与变变异起起着关关键作作用。。在一一个物物种的的某一一群体体中基基因的的集合合称为为基因因池。。生物物组织织是基基因的的载体体。如如果环环境变变化，，选择择的机机制就就会改改变。。这种种变化化必然然引起起基因因池的的变化化。特特定种种群的的基因因变化化称为为基因因流。。一个个物种种总是是不断断地经经历隔隔绝、、基因因流动动、变变化的的循环环。开开始时时，一一组地地理上上隔绝绝的群群体自自己孤孤立地地发展展，基基因在在内部部快速速地流流动。。随着着开放放，通通过交交流和和竞争争，优优胜劣劣汰。。2022/12/3172经济模模型经济系系统在在某种种意义义上类类似于于生物物生态态系统统。在在商品品市场场和理理想市市场中中，进进化决决定于于经济济实体体的决决策。。选择择机制制是市市场奖奖励机机制。。进化化是快快速的的，企企业与与消费费者之之间、、企业业之间间主要要是一一种互互相依依赖的的合作作关系系。决决策者者为了了追求求长远远利益益，可可以采采取各各种有有效的的方法法，甚甚至可可以暂暂时做做赔本本买卖卖。2022/12/3173协商模型型Zlotkin的面向领领域的协协商理论论Zlotkin的协商理理论假设设：各主体追追求本身身效用最最大。知识完备备。无历史信信息。目标集固固定。协商在两两主体之之间同时时进行。。主体操作作集相同同。世界仅当主体体操作之后发发生变化。2022/12/3174面向领域的协协商理论在协商过程中中，若存在一一个双方满意意的分配，可可以得到一个个联合规划,使协商终止的的条件是：(1)达成协议：如如果Utility(P(i,t))Utility(P(i,t-1)),这一协商过程程将在有限步步内结束。(2)冲突：如果果Utility(P(i,t))=Utility(P(i,t-1)),则无法达成协协议。2022/12/3175最佳平衡传统的协商商是基于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/3176集中中式式协协商商方方法法Ephrati使用用了了一一种种集集中中式式的的协协商商方方法法,用一一个个““masteragent””或组组投投票票机机制制以以达达成成协协议议。。在在这这种种方方法法中中,一组组主主体体的的协协作作与与组组规规划划进进