（模式识别与智能系统专业论文）基于博弈论的多机器人个性化协作研究.pdf

中南人学硕士学位论文 摘要 摘要 随着计算机、通讯、电予、传感、控制等技术以及人工智能的飞速发展，智 能机器人应用领域不断地扩展，对于一些复杂的工作任务和多变的工作环境，利 用多台机器人协调合作完成任务引起越来越多的专家学者和工程技术人员的研 究兴趣，成为机器人研究领域的热点。 对于多机器人协作系统，其体系结构是机器人系统中所有结构的模型和相互 关系的结构化集合，是整个系统的基础。在协作过程中，机器人在体系结构的基 础上，拔照一定的策略、协调机制、控制规则等有机地组织起来并可获得关于 系统整体行为的全局观点，从而采取有效策略引导局部控制实现协作。 本沦文将多义真体系统理论与进化控制相结合，提出了基于个性化水平的混 合式多机器人控制体系结构。该体系结构融合了分层递阶式结构和包容式结构的 优点，使系统兼顾了行为的智能性和响应的实时性。通过对个性化水平参数的衡 最将进化控制理论融入体系结构中，将进行协作的机器人个体看成具备自治能力 的艾真体，使系统还具备进化性和开发性。本文还研究了博弈论中纳什均衡和反 复博弈，将其理论运用于基于个性化水平的多机器人协作系统进行协作策略的选 择。将协作过程看成一个博弈过程，协作的结果就是求得一个最优决策的集合， 也就是求得各博弈方的策略集合使得整个博弈达到一个均衡稳定的状态。最后简 单介绍了本系统的试验情况，对本系统开发中的工作予以总结，同时展望令后的 研究工作目标。 关键词：自主式移动机器人、多机器人系统、分布式人工智能、多艾真体系统、 体系结构、个性化水平、黑板系统、多机器人协作、纳什均衡、反复博弈、特征 分布函数 第1 页 ! 壹叁堂堡：i 二堂堡笙苎垒生! ! ! ! 堕 a b s t r a c t w i t ht h eh i g hd e v e l o p m e n to fc o m p u t e rs c i e n c ea n da n i n c i a li n t e l l i g e n c e ，r o b o t s h a v eb e e na p p l i e dw i d e l yi na l lf i e l d ss u c ha ss o c i a lp r o d u c t i o n ，d e f b n s ei n d u s t r y ， s e r v i c et r a d e ，i n t e i i e c t u a le d u c a t i o na n ds oo n f o rt h er e a s o no fm o r ea n dm o r e c o m p l e xa n dd i f f 呈c u l tt a s k ，t h es t u d yo fm u l t i p i e r o b o ts y s t e m sn a t u r a l l y e x t e n d s r e s e a r c ho n s i n g i e r o b o ts y s t e m s m a n ye x p e r t s a n d e n g i n e e r s f 如md i f f 爸r e n t c o u n t “e sa r e a c h i e v i n gs y s t e m so fm u l t i p l em o b i l er o b o t se n g a g e d i nc o u e c t i v e b e h a v i o r f o rt h ec o o p e r a t i v es y s t e m s ，t h ea r c h i t e c t u r ec o n c i u d e sa l lt h es t r u c t u r a lm o d e l s a n dt h e i rr e l a t i o n s h i p so ft h em u l t i r o b o ts y s t e n la n di ti st h ef o u n d a t i o no ft h ew h o l e s y s t e m b a s e do nt h ea r c h i t e c t u r e ，t h er o b o t so r g a n i z ea c c o r d i n gt os o m es t r a t e g y ， c o o p e r a t i n gm e c h a n i s m ，a n dc o n t r o lr u l e s t h e yc o l i a b o r a t ew i t he a c ho t h e rt og e tt h e w h 0 1 ev i e wo ft h es y s t e ma c t i o n sa n da d o p tt h ee 疗 e c t i v e s t r a t e g yt oa c c o m p l i s ht h e 1 0 c a lc o n t r 0 1 t h e p a p e ri n t e g r a t e s t h e m u l t i a g e n ts y s t e m a n de v o l u t i o n c o n t r o 】， a n d e s t a b l i s h e st h eh y b r i da r c h “e c t u r eo fm u l t i r o b o ts y s t e mb a s e do ni n d i v i d u a t i o nl e v e l ，l h ea r c h i t e c t u r ec o m b i n e st h ev i n u eo ff u n c t i o n a l a r c h i t e c t u r ea n db e h a v i o r a l a r c l l i t e c l u r ea n d i n t e g r a t e s t h eb e h a v i o r i n t e l i i g e n c e a n dr e a l t i m e r e s p o n s e t h e d e 厅n i t i o no fi n d i v i d u a t i o nl e v e li sr e l a t e dt ot h ee v o l u t i o nc o n t m lt h e o r v ，w h i c h e n a b l e st h es y s t e mt oe v o l u t i o n t h er o b o ti sd e 行n e da sa na g e n ti nt h es y s t e m 、w h i c h i n s u r et h e s y s t e mo ft h e o p e ne x p l o i t a t i o n w e i n t r o d u c e dt h em a i n i d e a ， t h e i o r l l l a l i z e d d e s c r i p t i o na n dt h eb a s i cn o wo fg a m et h e o r y ，a n de x p l o r e dt h en a s h e q u i i i b r i u ma n di t e r a t e dg a m e st h e o r y w el o o ku p o no n ec o l l a b o m t i o na c t i o na s o n eg a m er o u n d ，a n dt h er e s u l to ft h ec o l l a b o r a t i o ni s t og e tt h es e to ft h eb e s t s t r a t e g i e s ，w h i c hi se q u i v a l e n tt oa c h i e v et h en a s he q u i l i b r i u mi na g a m e s ow ec a n a p p l yt h eg a m et h e o r yi n t ot h em u l t i r o b o tc o l l a b o r a t i v es v s t e m i nc o n c l u s i o n ，w eg i v et h er e s u l t so f e x p e r i m e n t ，m e a n w h i l e ，w es u m m a r i z eo u r w o r ka n d p u tu p o u r g o a l sf o rt h ef u r t h e rr e s e a r c h k e y w o r d s： a u t o m o b i l e r o b o t ，m u l t i r o b o t s y s t e m ，d i s t r i b u t e da n i f l c i a l i n t e l l i g e n c e ， m u l t i a g e n ts y s t e m ，s y s t e ma r c h i t e c t u r e ，i n d i v i d u a t i o nl e v e l b l a c k b o a r d s y s t e m ，m u l t i - r o b o tc 0 0 p e r “o n ，n a s h e q u i l i b r i u m ，i t e r a t e dg a m e s t h e 0 1 y ，c h a r a c t e r i s t i cd i s t r i b u t i o n s 第1 i 页 中南人学硕十学位论文 第一章绪论 第一章绪论 1 1 多移动机器人协作的研究意义 随着计算机、通讯、电子、传感、控制等技术以及人工智能的飞速发展，机器人的 川：发与应用得到了不断地提高，出现了带有多种传感器，具有自适应能力、自学习能力 的臼主式移动机器人，即所谓的“智能机器人”。同时，伴随着社会发展的需要，机器人 应用领域不断地扩展，从自动化生产线到海洋资源的勘探乃至太空探索，从传统工业生 产到农业、制造业以及服务行业乃至军枣国防工业，都可以见到机器人的身影。在这些 应用t l j ，一些复杂的工作任务和多变的工作环境，单体的机器人能力不足，需要由多台 机器人协渊合作完成复杂任务。例如，在军事应用领域由移动机器人构成的侦察或作战 小组，危险地区多移动机器人清除危险物，进行排险及搜索作业，或者在码头、仓库、车 m 利| j 多移动机器人构成具有更高柔性的物料传输系统等。因而，多机器人系统研究成 了机器人聊f 究领域的热点。 多移动机器人系统的协调合作的意义在于： ( 1 ) 由于某些任务本身的复杂性，难以使用单个机器人完成，亦或是利用多机器人 进行协作司以获得比单个机器人更好的效果和更高的效率。 ( 2 ) 设计出若干具备简单功能的机器人，进行组合协作完成任务，比起为具体任务 设计功能强大的单体机器人更容易实现、可以节省经费降低代价，并且系统可以增强冗 余度、提高容错性、柔性。 ( 3 ) 社会科学( 组织学、经济学、认知科学) 和生命科学( 动物行为学，生物学) 巾一些基本理论可以在多机器人系统得到应用并引起对其更深入的探索，同时，关了二多 机器人协作系统的研究可以为复杂系统和先进制造系统等工程应用的研究提供有益的启 示8 1 。 如何构建一个多机器人协作系统，如何有效的解决多机器人系统中的协作与控制问 题，使得系统表现出“复杂的群体行为”成了多机器人系统研究的关键问题。 1 2 多移动机器人系统的协作研究进展 早在2 0 世纪4 0 年代中期，g r e yw a l t e r ，w i e n e r 和s h a n n o n 在研究其带有光和触觉 ! 塑叁堂堡竺兰生堡苎墨二里竺堡 传感器的龟形机器人e l m e r 和e l s i 。时，发现这些简单机器人在相对运动的反应中表现 h 一种复杂的群体行为】。从7 0 年代早期开始，在分布式人工智能( d i s t r i b u t e d a r t i f i c i a li n t e l l i e n c e d a i ) 领域中，关于多智能艾真体( a g e n t ) 间相互协调和交互控 制的论题得到了广泛的研究，然而包括分布式人工智能的研究范围在内，这些研究对象 均集中在对于软件形式的艾真体。对于机器人领域内进行多机器人协调研究是起源于8 0 年代初期当单个机器人不能完成某一作业而需要多机器人时，如何保持多机器人之间 运动的协渊毁成为研究的热点。在接下来的1 0 多年里，对多机器人协调研究集中在系 统控制巾的载荷分配、运动分解、避碰轨迹规划、操作柔性体或大型物体。由于研究的 内容主要是多机器人臂如何协作搬运物体，形成的闭链控制系统存在受限运动以及冗余 度控制问题，因而协调控制显得十分复杂，但系统基本上不涉及合作决策，协调机制等 高层的控制问题。在实施协调控制策略算法时，人为地事先确定了机器人之涮的组织与 合作关系，通过建立一个集中式的计算机控制系统来控制机器人间的协调运动，这种集 中式舰划与控制方式，要求主计算机系统必须有足够强大的运算存储能力，来应付大量 的在线计算和数抛交互。所以，当协作的主体不再仅仅限于少量机器人臂的紧耦合运动 控制，加入了移动式自主机器人，并要求系统具有结构柔性和可扩展性酬，这种集中式 控制无法在实际中继续适用了【”。 8 0 年代术，一些研究机器人的学者，借鉴了分布式系统和分布式人工智能的理论， 引对集中式控制结构的不足，提出了多种基于分散化( d e c e n t r a i i z e d ) 和分布式 ( d i s t r i b u t e d ) 的多机器人系统的合作组织策略、方法及协调机制1 5 】。其中比较成功的系统 有c e b o t ，s w a r m ，a c t r e s s 和a l l i a n c e 等o 川，这些方法将多机器人视为 一个群体，个社会，从社会学的组织和系统的角度研究机器人群体的协作机制，充分 发挥多机器人系统中各个机器人的智能，根据环境和任务的变化能灵活、快速地重新组 织多机器人系统。这些研究正逐渐形成“协作机器人学”( c o o p e r a t i v e r o b o t i c s l 【6 】o 9 0 年代迅速发展的协作机器人学的研究主要是围绕着系统( s y s t e m s ) 、理论 ( t h e o r i e s ) 和问题( p r o b l e m s ) 交织进行的。为解决某特定的问题，系统被预想，仿 真，进而构建起来：同时，从其他学科借鉴引入关于协作( c o o p e r a t i o n ) 的理论协助实 现多机器人合彳乍，新的问题随之产生，从而又促进了系统和理论的更深入的研究。现在 关于多移动机器人协作系统的文献中，机器人主要完成如交通控制、推箱子、编队进行、 捡垃圾、搜索营救或追赶等问题和任务。 2 ! ：! _ ! 塑叁堂堡堂笪堡苎兰二! l ! i 堕 在m 作机器人学中，基于多艾真体概念研究多机器人系统的合作问题j 下受到越来越 多的注意。一般地，艾真体被认为是一个物理的或抽象的实体。它是一个运行于动态环 境中的具有较高自治能力的实体( 即自治体，可以是系统、机器也可以是一个计算机软 件程序等等) ，其根本目标是接受另一个实体( 即主体，可以是用户、计算机程序、系统 或机器等) 的委托并为之提供帮助或服务，能够在目标任务的驱动下主动采取包括学习、 通讯、社交等各种手段感知、适应其外在环境的动态变化并做出适当地反应f 】。同时， 艾真体与其所服务的主体还应具有较为松散和相对独立的响应关系。此外，它具有智能 并能通过协作解决某些传统方法所无能为力的复杂问题。 多艾真体系统可以咖调一组自治的艾真体的行为( 知识、目标、方法和规划等) ，以 i 同地动作或求解问题。将艾真体概念应用于多机器人系统的研究中，其基本思想是依 掘多艾真体系统的特性组织、控制多机器人系统，使系统具有能合作完成人所赋予的任 务的能力。这种多机器人系统称为“多艾真体机器人系统m a r s ”( m u i t i a g e n tr o b o t s y s t e m ) 。在这种系统中，系统中的每个机器人都被视为个具有智能行为的自主系统， 每个艾真体一般只处理与自身相关的局部目标和局部信息，进行自主运动，同时又可以 j 其他艾真体交流共享资源信息，具有合作的能力。在多艾真体机器人协作系统中，各 机器人可根据系统总任务目标，动态地规划各自的运动序列，而不是山集中规划器进行 规划。各机器人可充分发挥其智能和自主行为来与其他机器人进行协作限。 多机器人系统研究的重点是合作机制问题，即给定了任务、环境和一组机器人，如 何产生合作行为。其主要问题包括如何构建群体的体系结构，如何决定协调策略，选择 协作方式，如何进行通信，如何防止死锁以及感知与学习问题，建模与规划问题，等等。 1 。3 基于混合结构的多移动机器人分布式协作概述 实现合作行为必须依赖于某种系统的体系结构。群体结构( g m u pa r c h i t e c t u r e ) 是整个 系统执行协调合作行为的基础，决定了系统的整体能力和局限性。从控制方式和信息交 互方式行看，群体体系结构分为集中式和分散式，而分散式又分为分层和分布两种类型。 不同的类型的体系结构有着各自的特点，普遍的看法是分散式结构在某些方面，如故障 冗余、可靠性、并行开发的自然性和可扩展性等，比集中式结构要好。任务类型的不同， 协作控制的月的不同，可导致实现任务所需的体系结构的不同。同时，对于多移动机器 人协作的研究从研究对象一移动机器人的个体差异上可分为两种：对于同质个体 ! 塑叁堂堕堂堡笙茎 一一笙二皇! 塑堡 ( h o m o e n e o u sr o b o t s ) 构成的多机器人系统的群体协作( s w a r m - t y p ec o o p e r a t i o n ) 和对 于异质个体( h e t e m g e n e o u sr o b o t s ) 构成的多机器人系统的意i ：! 协作( “i n t e n t i o n a l c 0 0 d e r a t i o n ) 眦1 l l 。同构系统巾每个机器人的能力是一样的，异构系统则相反。异构系统 虽具有普遍性，但带来问题的复杂性，任务分配更加困难。在异构系统中，任务分配一 般按个体的能力来确定。在同构系统中，各义真体需要被区分为不同的角色，以便控制 时的识别。群体结构要能适应动态自组织的要求。在系统拓扑结构可变情况下，动态选 举t 艾真体和建立多艾真体之问的关系是体系结构研究要解决的问题之一。 本论文着重介绍了糅合了集中式和分散式优点的混合式体系结构，在麻省理工：学院的 r ，b r o o k s 提出的包容式体系结构系统的基础 二，加入了商层智能机构一一个中心黑板系 统进行全局的指导和协调。低层的分散式结构是在基于功能行为集成的进化控制结构基 础l 二，构建多艾真体协作体系结构。暴于功能行为的体系结构，既县有基于行为的系统 的实时性，又保持了基于功能的系统的日标可控性，即规划功能，同时，该系统结构具 有f _ _ | 学习能力，能够根据先验知识，历史经验，对当前环境情况的判断和f i 身的状况， 调整自己的h 标、行为、以及十h 应的仂，调机制，以达适应卅：境、完成任务h 的。于系 统建立在艾真体的技术基础至上，从而融合了艾真体的自治性、丌发性和主动性特点， 自然地使得泼体系结构具有了丌发性等特点。使得用户可以很容易地按照自己的方式组 合多机器人系统，或者对系统进行功能拓展。高层的中心黑板系统分为黑板数据存储器、 推理机构和个协进化艾真体三部分，能够起到事件集中、形势评估，行动决策和群体 进化的作用。 在机器人群体协作中，机器人要按照一定的策略、协调机制、控制规则等有机地组织 起来，机器人通过组织结构知识获得关于系统整体行为的全局观点，从而采墩有效策略 引导局部控制实现协作。多机器人协调是指具有不同目标的多个机器人对其目标、资源 等进行合理安排，咀调整各自的行为，最大程度地实现各自的目标，而多机器人协作是 指多个机器人通过协调各自的行为，合作完成共同的目标，协作是一种特殊类型的协调。 目前国际上已经发展了很多方法，并且形成了相对分明的几个流派，根据这些理论方法 的流派，大致可以分为以下几种：基于符号推理系统的协调策略、基于行为主义的协调 策略和基于协进化的协调机制f 1 2 。 ! 堕查堂堡主堂堡堡茎生二重型 1 4 课题来源 本课题研究与开发的内容来源于国家自然科学基金、湖南省科委科技专项基金、中 南大学“2 1 1 ”工程实验室建设基金等项目。 1 5 论文结构 多移动机器人系统的协作与控制是一个在理论和技术上均具有很高难度的研究课题， 本学位论文针对该研究领域已有成果在研究方法上的不足以及传统智能控制方法的局限 性，剥多移动机器人协作系统的体系结构、协调策略、协作机制等方面进行了研究。 本论文的第一章主要介绍了多移动机器人系统协作研究的意义，并结合多移动机器人 协作系统的研究过程，简单介绍了多移动机器人协作研究的主要内容、研究方法和研究 脱状。并简单介绍了本论文研究的概况和重点内容。 定论文第一誓，系统地介绍了在开发研究中需要用到的一些基本理论和实现方法。 简单介绍了分郁式人工智能的特征和基本问题，和艾真体的基本概念及多艾真体系统的 协调与合作机制。同时还分析了协作多移动机器人系统存在的问题和多机器人系统的几 种体系结构。 第三章全面阐述了本论文提出的基于个性化水平的多移动机器人协作的体系结构， 在研究分析祭自兴教授、周翔博士提出的基于功能，彳亍为集成的自主机器人进化控制体系 在个体机器人控制应用上，综合了个体进化，协进化的理论，提出了个性化水平参数， 并将其廊用于多移动机器人协作体系结构的构建，以便提高系统的灵活性和适应性。 第叫章中，介绍分析了博弈理论中的纳什均衡和反复博弈论等理论，重点研究了特 钮：分如函数的定义及其应用，并结合第三章提出的个性化水平参数，介绍如何结合个性 化水平参数应用特征分布函数和贪婪慷慨策略选择多机器人系统的协作策略。 第五章介绍了本系统试验仿真情况，在第六章里总结了本论文工作的主要结论和成 果，指出了多移动机器人分布式协作与控制有待进一步研究，指出了这一研究的技术难 点和重点，展望了今后研究工作的目标。 ! 塑叁兰堕! 卫望鲨塞 笙三童圭茎壅堡墨竺兰坠堡垒垫竖二i ! 丝 第二章多艾真体系统与协作多机器人系统 2 1 分布式人工智能 2 1 1 分布式人工智能的特征和基本问题 自从人工智能诞生以术，大多数人j 二智能的研究在于如何使单个义其体展示其智能 行为，而人类活动大部分都涉及社会群体人的智能的体现更多是在对于大型复杂问题 求解时，通过群体组织协作方式完成任务的过程中。随着埘高效的计算机的丌发，计算 机阚络技术的r 益成熟以及人们对许多涉及到群体的人类问题求解与活动的认识，人们 对人工智能中的并发性与分布性越来越感兴趣，从而导致了分布式人工智能系统的产 t 卜。 分斫i 式人 二智能( d i s l r i b u t e d a r t m c i a l i n t e l l i 2 e n c e d a i ) 已经成为人二1 ：智能研究的 一个蕈婴分支，它山多个艾真体( a g e n t ) 组成，每一个艾真体都足1 个f i 治或、仁r j 治 系统，往艾真体之涮以及艾真体与环境之问是并发工作的。需要进 j ：交互，d a i 主要研 究这”j 在逻辑上或物理上分散的智能系统如何并行地、相互协作地进 j ：问题求解。 分枷式人工智能研究可分为两个主要的予领域一分布式问题求解( d p s ) 和多艾真 体系统( m a s ) 。 1 分布式人工智能系统的特征 分前i 式人工智能系统主要有三个方面的基本特征：分如性、异构性、自主性f “1 。 ( 1 ) 分布性。分布式人工智能系统中的分布性不仅指知识的垂直和水平划分，还 包括知识的复制和传播。对知识的划分和组织的原因在于有限合理性原则，即任何主体 单个地处理能力是有限的，不可能同时处理问题的所有因素，因此对问题进行分解和划 分是丌发问题求解体系结构的最快捷方法。 ( 2 ) 异构性( h e t e r o g e n e i t y ) 。异构性有三个方面：语法、控制和语义。语法异 构性来自语不同的知识表达之问的差别；控制的异构性来自于不同的推理机制，如归纳、 演绎、类比等等；语义异构性来自于对相关知识的涵义、解释和使用的不同理解。对异 构性进行处理时必须保持各艾真体的自主性，其有效方法是通过分层交互结构将异质系 统的特点局域化。 中南人学硕十学位论文 第- 二章多艾真体系统与协作多机器人系统 ( 3 ) 自主性( a u t o n o m y ) 。这罩的自主性体现在系统的各个方面：构建自主性是在 设计系统时每个艾真体的个性化选择；通信自主性指叟真体可以决定自己在系统范幽内 的通信中充当什么角色；执行自主性是指每个义真体有局部的本地的功能，不必借助外 部操作就可以执行任务；联系自主性足艾真体可以决定多大程度上允许本地资源被共 亭；结构自主性是艾真体集合自主组织成各种问题求解的体系结构的能力。 由丁分布式人工智能系统具备以上基本特性，使得整个系统又具备了以下特性：适应 性，逻辑的、语义的、时问的和空间的分布性使分斫i 式人工智能系统对不同的环境能提 各种选择的余地并具有更大的适应能力；扩充式的丌发与管理：分以】式人i 智能系统t i ， 的各个单元可由特定的领域专家独立地玎发，分布式人工智能系统足可扩充的或与已有 的计算机系统集成：高效率：并行处理可提高计算与推理的速度；可霏性：由于采j h 了 冗余、互检等技术，分布式人工智能系统比集巾式系统更可靠。 2 分布式人工智能的基本问题 在分和式人j ：锣能系统的研究中，通常涉及到以下u ! 基本问题： ( 1 ) 对于给定任务的描述、分解和分嘶j 。其叶r ，对于任务的舶述是嫩肚小的题。 ( 2 ) 通信问题包括交互语言和协议。 ( 3 ) 保证系统行为的协调一致性。这是分柿式人工智能系统一个最具有挑战性的 问题。 ( 4 ) 智链系统的行为建模。它是当时研究的热点之一。 ( 5 ) 资源冲突消解。冲突消解方法与采用的组织结构有很大关系，也足当自u 的研 究热点，并且已经产生了大量的研究成果。 ( 6 ) 实际工程问题。比如，在实际建立分布式人工智能系统时如何实现分斫i 性，难 以观察系统的并发活动以及缺乏编译与调试工具等等。 这些基本问题并不是相互孤立的，针对某一个问题的研究往往要涉及到多个方面。 例如，部分全局规划问题就需要涉及到通信、协调一致性和冲突消解等问题。 2 1 2 分布式问题求解系统的协作方式 分布式问题求解是分布式人工智能研究的一个分支。分布式问题求解系统有两种协 作方式，即任务分担( t a s k s h a r i n g ) 和结果共享( r e s u l t ss h a r i n g ) 。在任务分担系统中， 结点之间通过分担执行整个任务的子任务而相互协作，系统中的控制以日标为指导，各 中南人学硕 ：学佩论文 第一二章多艾史体系统1 。协”多机器人系统 结点的处理目标是为了求解整个任务的一部分。任务分担的问题求解方式适合于求解具 有层次结构的任务，如工j 。联合体生产规划、数字逻辑电路设计、医疗诊断。 在结果共享方式的系统中，各结点通过共享部分结果相互协作，系统中的控制以数 据为指导，各结点在任何时刻进行的求解取决于当时它本身拥有或从其他结点收到的数 据和知识。结粜共享的求解方式适合于求解与任务有关的各子任务的结果相互影响，并 且部分结果需要综合才能得出问题解的领域，如分以i 式运输调度系统、分布式车辆峪控 实验系统等m 2 ”。 在分布式问题求解系统一亿常用的通信方式有共享全局存储器、信息传递以及者 的结合。黑板模型足分都式阎题求解系统qz 使用较多的框架结构。l e s s e r 等入托d v m t 系统的黑板模型中，增加l 了日标黑板、抽象级黑板以及复杂的胤划机制。系统r ”聚合器 根掘数据黑板上的信息产乍舰划所片j 的抽象数据，并将其存放在抽象级黑板k 标处 理器负责目标的分解，并产生知识源例示队列。规划程序结合_ f f | 象级数据、知谚 源例示 队列以及| 网络系统的组织结构信息进行处理产生规划队列。系统运行时揪扒，牝体黑板 信息的变化状态以及例络中其他求解器的状态，对肌划的实施进行动态渊枢。存分机式 问题求解系统一 j 保持全局一致性意i 味着各结点的问题求解朝着有利于实现系统lf 标的 方向进行。 2 2 多艾真体系统 作为分粕式人工智能一个分支的多艾真体系统是目f i 分伽式人工智能研究c 限一 个热点，也是本论文研究的基础所在。下面将从艾真体的基本概念，多艾真体的概念出 发，分析多艾真体组织结构的研究方法、多义真体系统的求解框架以及多艾真体吲的协 调与合作。 2 2 1 艾真体的基本概念 艾真体( a g e n t ) 这个概念无论在人工智能领域还是在其他计算环境中都越来越常 见，它在不同的应用范圈内具有不周的涵义，很难找出一个大家都能接受的定义。f i p a ( f o u n d a t i o nf o ri n t e l l i g e n tp h y s i c a l a g e n t ) ，一个致力于艾真体技术标准化的组织，对艾 真体的定义如下： 艾真体是一个运行于动态环境的具有较高自制能力的实体( 即自制体，可以是系统、 中南人学硕十学位论文第一章多艾真体系统与协作多机器人系统 机器等：软件艾真体是一个计算机软件程序) ，其根本目标是接受另外一个实体( 即主 体，可以是用户、计算机程序、系统或机器等) 的委托并为之提供帮助和服务能够在 该目标的驱动下主动采取包括社交、学习等手段在内的各种必要的行为以感知、适应并 对动态环境的变化进行适当的反应，它与其服务主体之问具有较为松散和相对独立的关 系【2 ”。 在人工智能领域中，艾真体的涵义随着问题类型的不同也有所不同。在细粒度的并 行人工智能系统，如神经网系统，艾真体是一些紧密耦合的、简单的、无智能的用来表 示一个个知识片断( 如一。个符号、概念等) 的处理币元。它们以异步的。+ 式工作，通过 相之 的连接进行通信，可以灵活地对数据做出反应，从而在整体上看，它们是有智 能的。在车h 粒度的分前i 式问题求解系统中，这些艾真体是松散耦合的、可以求解复杂问 题的半自治的结点或模块，并形成一个分和式网络。每个艾真体实个复杂的行为j ! l ! 划 器，可以随坏境变化做出响应，可以规划自己的通信和与其他曼真体的协作策略。艾真 体的存在形式又包括软件艾真体、硬件型艾真体或者两者般而订之型。 、o l d r i d g e 和j e n n i n g s 吲从狭义和j 。义两个方m i 珊解艾真体的特性挺：5 了艾真体 的强弱概念。从。义上把具备了自主性( a u t o n o m y ) 、通信，p 】：( c o m m u n i c a b y ) 、响 应性( r e a c t i v i t y ) 和自发性( p r o - a c t i v e n e s s ) 特性的软件和硬件系统成为艾真体。最简 单的艾真体可以是。个计算机进程。若在研究使用中，为艾真体加j ：一些人类的特性如 社交性、移动性、友善性、理性、适应性、诚实性和代理性等，一些研究者提出了强概 念的艾真体定义【6 0 】。 在分布式人丁智能下的多叟：真体系统含义是，有一组自治型的义真体，它们既可以 各自完成局部的问题求解，而且还能协作地求解单个目标问题或者多个目标问题。一般 而言，这罩的义真体拥有推理机、通信接口、冲突检测与消解三个执行部件，推理所用 的长期知识分布来自事实、规划、启发式知识和解标准四个知口 模块，黑板存放协商过 程中的中间信息。另外通过外部接口可调整外部知识库，进而协调事实与规则两个知识 模块。( 见图2 1 ) 9 堕叁堂堕堂堡堡奎 笙三垩墨茎塑堡墨丝兰塑堡至塑堡二! 墨丝 外界环境一外部接u 一 j 他叟真体一 j 通信接l ih - 黑板系统b j 一一 2 2 2 多艾真体的协调与合f f 矿如社会总体智能优1 二任何个人一样多艾真体的协作求解能力也超过单个艾真 体。协调与协作是多艾真体系统研究的核心问题之一，以自主的艾真体委最心，使多艾 真体的知以、愿槊、意图、规划、ij ：动协调，以至达到协作，是多艾真体系统的主要目 标。 协调是指一组智能主体先成些集体活动时相互作用的性质。协调般是通过改变 环境中运行的主体的意图来实现对其环境的适应。协调的原因是山于其他主体的意图存 在。协作是非对抗的主体之问保持行为协调的一种特例。多艾真体系统是以人类社会为 范例进彳研究的。在人类社会中，人与入之剧的交互是无所不在地。人类交互一般在纯 冲突和无冲突之问进行。同样，在丌放、动态的多艾真体爿、境中，具有不同日标的多个 艾真体必须对其目标、资源的使用进行协调。当山现资源冲突时，若有双方l 司时需要抢 f 与某个时间或地点资源，而又没有协调机制，则二者都可能陷入死锁境地；另一种情况 下，双方都没有能力完成自己的目标，需要对方的帮助爿能完成，此时，如果没有一个 艾真体主动去帮助对方，则只能处于永久等待帮助的状态，这是一种活锁状念，即多个 艾真体不断工作，却无任何紧张的状态。 从社会心理学的角度上d c o 肌a h 和p w a r i s h 对多艾真体之阳j 的协作加以总结， 得出三种协作风格，仁慈好施型、利他主义型和自私自利型2 ”。在这基础上，加以细分 具体化，又可分为： 协作型：将协作放于第一位，同时考虑个体需求。 自私型：将个体需求放于第一位，协作放于第二位。 完全协作型：完全不考虑个体需求。 识1h 什一发 _ l 一 中南人学硕士学位论文第二二章多艾真体系统与协作多机器人系统 完全自私型：完全不考虑任何协作。 协作与自私相混合型。 在现阶段，针对主体协作的研究大体上可分为两类，一类是基于符号推理的逻辑学 方法，从艾真体的目标、意图、规划等心智态度出发来研究多艾真体的协作陋2 9 1 。 另 一种是将其他领域( 如经济学、生态学等) 研究多实体行为的方法和技术用于多艾真体 协作的研究 3 0 】。 基于符号推理系统的协调机制以b r a t m a n 提出的信念、愿望、意图( b r i e fd e s i r e i n t e n t i o n ，b d l ) 理论为基础，采用传统人工智能中符号推理的基本原理，试图通过建立 比较完整的符号系统迸行知识推理来使艾真体具有自主思考、决策的能力以及与其他艾 真体和环境进行协调行动的能力。基于符号推理系统的协调理论分别简单介绍如下： 1 联合意图理论 b d i 理论中信念包括艾真体对环境的基本看法，艾真体使用它们可以表达将来可能 发生的状态：愿望直接从信念中得到，它们包括义真体对将来情景的判断；意图制约着 艾真体的行动是目标的子集。c o k n l e v e s q u e 基于b d l 理论进一步提出了承诺 ( c o m m i t m e n t ) 和公约( c o n v e n t i o n ) 的概念叭32 1 ，基于联合意图构建的系统的协作策略要 点如下所示：多个艾真体在完成一个共同任务时会形成一个共同承诺，如果不出现下列 三种情况之一，艾真体就应该遵守公约，即坚持承诺，直到成功完成共同任务。 艾真体发现共同任务已经完成； 义真体发现共同任务是不可能完成的； 艾真体发现执行该共同任务是不必要的。 否则艾真体就会设法通知f 在合作执行共同任务的其它艾真体，自己将退出承诺。 这样，其它艾真体就能够适时做出调整。通过这样的承诺和公约机制，多个艾真体就能 协调完成一个弛同任务。1 1 a m e 在他的文章 3 3 】里提出的队工作模型s r e a m 就是应用了 联合意图理论和联合规划理论。 2 共享计划理论 g r o s z 等提出了共享计划理论，它是建立在一种联合精神状态之上的，其中最重 要的概念就是它引入的概念算予：“打算”( i n t e n t i o n t h a t ) 和打算做”( 【n t e n t i o n t o ) ， 它们通过一系列原子操作符定义，引导智能体采取包括通信在内的行动来使得个体、子 团体和整个合作团体能够协调一致的执行所赋予的任务。所有参与联合任务的各个智 中南人学硕+ 学位论文 第二章多艾真体系统与协作多机器人系统 能体首先要达成一个共享计划，共享计划中包含了要完成联合行动的各种方面细节和具 体步骤，每个智能体都彼此相信它们都打算要进行联合行动并接受共享计划。对于共享 计划中的每一步，又会有一些智能体形成子团体组合来完成，子团体之外的其他智能体 都相信子团体能够完成该步计划，并对该步也有一个共享计划。这样通过共享计划的协 调，各个智能体就能合作完成共同任务。共享计划理论通过一个全队的共享计划实现多 个智能体的动态组合及分工协作，这种思想是很好的，在这方面它强于联合意图理论， 但它没有涉及到当智能体在不能很好完成共享计划时的保证机制，这方面又比联合意图 理论为弱，因此，将二者结合起来研究就能扬长避短。 3 部分全局规划 部分全局规划( p a r t i a lg l o b a lp l a n l l i n g ，p g p ) 适用于系统中每个艾真体的能力是 给定的，可以收集到当前状念的信息，了解其他艾真体达到的目标。使用p g p 的基本 条件就是需要几个分如式主体为整个问题求解工作。一个艾真体作为p g p 的一部分， 考虑同组其他艾真体的动作和关系来形成自己的结论，并可以使用知识优化自己的任 务。这种知识称作部分全局规划，它反映求解全局问题的一个艾真体决定的部分规划知 识。协调过程丌始之前，每个艾真体创建局部规划，求解指派的任务。当局部规划完成， 艾真体之间交换知识。每个艾真体必须具备一定数量的专门组织的知识，它可以决定在 问题求解中其他艾真体的角色。一旦义真体收到其他艾真体发来的规划信息，它必须以 p g p 形式组织，检查是否有新的信息包括对它内部规划的依赖关系，然后，将这些相关 的子规化分组成逻辑部分。p g p 规划器产生修改的局部规划作为最终结果具体规划送 到具体主体后，规划器要使用整个系统当前的知识进行优化和充实细节。使用局部规划 器的优点是高度动态的系统行为，所有规划任何时候都能适应新的环境求解，整个系统 具备高度灵活性和有效性。缺点是存在一些限制，特别在多艾真体系统中异构艾真体不 同问题求解时，如何处理动念艾真体重复改变求解策略。 4 计划的队行为 k i n n y 提出了计划的队行为方法f 3 6 j ，其要点是，计划是事先由设计者赋予的，而不 是由多智能体动态产生的，智能体在行动之前就被赋予了关于完整计划的详细信息，这 种方法适合于对智能体的行为环境事先能够确切把握并且精细计划的场合，不适合于动 态环境，因此应用比较有限。 将经济学、生态学的一些研究多实体行为的方法和技术用于多艾真体协作的研究， 1 2 主塑查堂堡主堂垡垒壅 苎三兰童茎塞笪墨丝皇坐堡垒垫矍尘：i 坠 就产生了基于博弈论的协作与基于协进化的协调策略。 1 基于博弈论的协作 8 0 年代中期，r o s e n s c h e i n 在其博士论文中对于艾真体在目标有冲突情况下的交互 进行了深入研究，运用博弈论建立了合理主体”( r a t i o n a 】a g e n t ) 交互的静态模型卅。 基于博弈论对多艾真体的协商、规划进行的研究，都是在自主主体目标矛盾的前提下， 研究如何建立对方模型或通过协作实现目标的形式化研究。博弈论关注研究对象的理性 特质，以它为基础研究多艾真体的协作机制融合了逻辑推理的形式化建模方法和以决策 理论和动态规划为基础的建模方法。 以博弈论为框架的多艾真体的交互，在实施中遇到了一些问题，比如，艾真体在对 策过程中如何推理出决策策略。有学者通过应用决策树的方法来解决这个问题。决策树 的一种重要形式是扩展形式对策的表达。扩展形式对策也是一种动念对策，它指明了所 有艾真体的执行序列和它们的最终支付。一个扩展形式对策是一个有限节点的对策树， 树中每个节点表示一个艾真体的执行步骤，一个节点的分支对应于节点表示的艾真体的 可能行为。在树的术端节点指明了义真体的支付，在有限时间区间具有有限行动和状态 的随机对策均可表示成为扩展形式对策，也即对策树。其缺点是不适合无限区间，并且 也不适合于连续或无限的行为空间。 2 基于协进化的协调策略 为了克服传统进化算法的不足解决一类更为广泛的机器学习、共同适应以及多智 能体间的协调问题，人们模仿自然界中的协进化机制，提出了协进化计算 ( c e c ，c o e v o l u t i o n a r yc o m p u t i n g ) 的思想【3 7 】。在协进化计算中，通常存在多个物种群体， 每个物种群体都有自己的物种个体类型，各个物种群体都采用进化算法实现进化过程， 而在对个体进行适应度评价时，则加入对群体间交互协调的处理。对那些有利于群体间 协调的个体赋予较高的适应度，而不利的则赋予较低的适应度，这样各个群体就会向着 有利于相互协调适应的方向进化，从而产生协调行为。 在对协进化方法的研究上，目前的大多数方法是针对具体问题领域而采用不同的个 体适应度控制策略。它们缺乏一种比较通用和概念化的方法指导和分析评价，尤其是在 利用合作型协进化方法产生协作行为的问题上更是如此。作为遗传算法进