（机械制造及其自动化专业论文）基于学习的多智能体协作方法研究及应用.pdf

西华大学学位论文独创性声明 1 1 1 11i i ii ilii i t1i i iiu l y 1 8 8 4 8 0 1 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行 研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢 的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不 包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：考讳 日期：加f 。争f 碉f 期 獬：彩毛 日期：驯。牟闱f 岁日 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 在校攻读学位期间论文工作的知识产权属于西华大学，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅，西华大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。( 保密的论文在解密后遵守此规定) 1r 学位论文作者签名：李玮指导教师签名：历名乞 日期：弘t 。年叫嗲q 、 日期：洲莩硐f f 二 西o # 大学硕t 学位论文 摘要 人工智能是一门新兴学科，近来来引起了学者们的广泛关注。多智能体系统( m a s ) 是人工智能的一个重要研究领域。多智能体系统是由多个高度自治的智能体( a g e n t ) 有机结合而形成的群体系统。由于智能体的高度自治性以及环境的实时性，多智能体系 统面临着数据的分布性、计算过程的分布性、异步性、并行性，环境信息的不完整性， 多目的和多重约束性等困难。目前对智能体系统的研究主要集中在系统体系结构、智能 体间的通信、智能体间的协作与协调以及多智能体学习等方面。 在西华大学机器人研究所支持下，本文围绕多智能体协作以及强化学习展开了深入 的研究，论文主要完成了以下的工作： 夺本文对多智能体的历史和发展进行了详细的追溯，并对多智能体研究的关键技 术进行了深入的了解，同时指出了多智能体系统目前遇到的一些困难和取得的 成果。 令本文从多个智能体组织层面和单个智能体层面入手，对现有的主要体系结构进 行了详细的分析和解释，并对其各自的优缺点进行了比较。 夺本文利用时序逻辑语言对多智能体协作和协调问题进行了形式化描述和建模， 同时根据协作模型提出了一种基于“竞争协作”机制的多智能体协作方案，并 且对协作方案进行了优化，可以有效的避免死锁问题的发生。 令本文详细的分析了目前用于智能体学习的主流学习算法，并对多种算法进行了 形式化描述和通俗的解释，同时也对多智能体分层学习算法进行了全面的理解， 在此基础之上提出了一种基于m a x q 的多智能体协作算法，提高了多智能体 系统的协调能力。 关键词：多智能体；协作；强化学习；m a x q 基于学习的多智能体协作方法研究及应用 a b s t r a c t 4 a r t i f i c i a li n t e l l i g e n c ei sa ne m e r g i n gd i s c i p l i n e ，a t t r a c t e dw i d ea t t e n t i o nf r o ms c h o l a r s r e c e n t l y m u l t i a g e n ts y s t e m ( m a s ) i sa l li m p o r t a n t f i e l do ft h ea r t i f i c i a li 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 mi sc o m p o s e do ft h em u l t i p l ea u t o n o m i ca g e n t s b e c a u s eo ft h eh i g hd e g r e e o ft h ea u t o n o m i ca g e n t sa n dt h er e a l t i m ee n v i r o n m e n t ，t h em a sf a c e dw i t hs u c ht r o u b l e s s u c ha st h ed i s t r i b u t i o no ft h ed a t aa n dt h ec a l c u l a t i o n ，a s y n c h r o n o u s ，p a r a l l e l ，i m p e r f e c t l yo f t h ee n v i r o n m e n t a li n f o r m a t i o n c u r r e n ta g e n ts y s t e mr e s e a r c hf o c u s e so ns y s t e ma r c h i t e c t u r e ， c o m m u n i c a t i o nb e t w e e nt h ea g e n t s ，t h ec o l l a b o r a t i o na n dc o o r d i n a t i o no fm a s ，l e a r n i n ga n d s oo n f i r s t ，t h i sp a p e rf o c u s e so nt h ec o l l a b o r a t i o no fm a s a n dt h es t u d yo ft h er e i n f o r c e m e n t l e a r n i n gi nd e p t h ，t h em a i nw o r k so f t h i sd i s s e r t a t i o na r e ： s e c o n d ，t h i sp a p e rs u m m a r i z e dt h eh i s t o r ya n dt h ed e v e l o p m e n to ft h em a s ，a n d r e s e a r c h e st h ek e yt e c h n o l o g i e so fm a si nd e p t h ，a n da l s op o i n t e do u tt h a tt h ed i f f i c u l t i e sa n d t h er e s u l t sa c h i e v e do ft h ea g e n ts y s t e mi sc u r r e n t l ye x p e r i e n c i n g t h i r d ，t h i sp a p e ra n a l y z e da n de x p l a i n e dt h ec u r r e n tm a i ns t r u c t u r eo fm a s b a s e do nt h e t h e o r yo fs i n g l ea g e n ta n dm u l t i - a g e n t ，a n da l s oc o m p a r e dt h e i rr e s p e c t i v ea d v a n t a g e sa n d d i s a d v a n t a g e s f o u r t h ，t h i sp a p e ru s e dt e m p o r a ll o g i cl a n g u a g et og i v et h ef o r m a ld e s c r i p t i o na n d m o d e l i n go ft h em u l t i a g e n tc o o p e r a t i o na n dc o o r d i n a t i o n ，a n dp r e s e n t sa v i a b l em o d e lb a s e d o nt h em u l t i - a g e n tc o l l a b o r a t i o n ，t h e no p t i m i z et h ec o l l a b o r a t i v em e t h o d ，i tc a ne f f e c t i v e l y a v o i dt h ep r o b l e mo fd e a d l o c k f i n a l l y ，t h i sp a p e ra n a l y z e d 。t h ec u r r e n tm a sl e a r n i n ga l g o r i t h m , t h ed e s c r i b e dk i n d so f a l g o r i t h m si nf o r m a la n de x p l a i nt h e mi np o p u l a rl a n g u a g e ，a n dc o m p r e h e n s i v eu n d e r s t o o d t h em a sh i e r a r c h i c a ll e a r n i n ga l g o r i t h m s a n dp r o p o s e dac o o p e r a t i v ea l g o r i t h mf o rm a s c o o p e r a t i o nb a s e do nt h em a x qt h e s i s ，a n di m p r o v et h ec o o r d i n a t i o no f t h em a s k e yw o r d s ：m u l t i - a g e n t ；c o o p e r a t i v e ；r e i n f o r c e m e n tl e a r n i n g ；m a x q 西华大学硕士学位论文 目录 摘要i a b s t r a c t i i l 绪论1 1 1 人工智能与多智能体系统1 1 2 多智能体系统应用领域2 1 2 1 多机器人搜索和救援- 2 1 2 2 机器人足球比赛二2 1 2 3 网络通信管理。3 1 2 4 多机器人搬运3 1 3 多智能体系统关键技术3 1 3 1 多智能体系统体系结构3 1 3 2 智能体间的通信5 1 3 3 智能体间的协作与协调一5 1 3 4 智能体学习5 1 4 多智能体系统发展现状6 1 5 多智能体系统目前存在的困难6 1 6 本文主要研究内容及论文结构7 1 6 1 论文研究内容7 1 6 2 论文结构7 2 多智能体系统结构设计8 2 1 引言8 2 2 单个智能体结构8 2 2 1 分层递阶式结构8 2 2 2 包容式结构9 2 2 3 简单反应式结构1 0 2 2 4 效率驱动的结构1 l 2 3多智能体群体系统结构1 2 2 3 1 集中式结构1 2 2 3 2 分布式结构1 3 2 3 3 分层式结构1 3 m 基于学习的多智能体协作方法研究及应用 2 3 4 对抗式结构1 4 2 3 5 拍卖结构1 5 2 4 小结1 5 3 多智能体协作研究16 3 1 引言1 6 3 2 多智能体的协作能力j 1 7 3 3 多智能体协作形式化描述1 8 3 3 1 时序逻辑18 3 3 2 多智能体协作基于时序逻辑语言的形式化描述1 8 3 4 协作模型及协作结构1 9 3 4 1 协作模型1 9 3 4 2 协作结构2 1 3 5 协作方案及其优化2 4 3 5 1 死锁现象及排除2 4 3 5 2 多智能体“竞争协作”2 5 4 多智能体协作中的强化学习2 8 4 1 引言2 8 4 2 强化学习。2 9 4 2 1 概述。2 9 4 2 2 强化学习基础2 9 4 2 3 动态规划算法3 l 4 2 4 时序差分算法3 2 4 2 5 蒙特卡洛算法3 5 4 2 6q 学习算法3 7 4 3 分层强化学习3 9 4 3 1 引言3 9 4 3 2 分层强化学习分层与抽象3 9 4 3 3 多智能体分层强化学习的现状4 0 5 基于m a x q 的多智能体分层学习4 1 5 1 引言4 l 5 2 半马尔科夫决策模型4 l 5 2 1 基于多智能体的半马尔科夫决策过程4 2 i v 西o # 大学硕士学位论文 5 3 基于m a x q 的多智能体分层强化学习算法4 4 5 3 1 m a x q 分层强化学习算法4 4 5 3 2 基于m a x q 的多智能体分层强化学习算法4 8 6 结束语5 3 参考文献5 4 作者在攻读硕士学位期间发表的论文5 8 致谢5 9 v 西华大学硕士学位论文 1 绪论 1 1 人工智能与多智能体系统 人工智能是一门新兴学科，特别是近来来引起了多个学科的专家学者们的广泛关注。 “人工智能一词最早由约翰麦卡锡( j o h nm c c a r t h y ) 等在达特莫斯( d a r t m o u t h ) 会议上提 出，标志着人工智能这门学科的诞生【m 】。麻省理工学院p w i n s t o n 给人工智能定义为： “人工智能就是研究如何使计算机去做过去只有人才能做的智能的工作。”通俗的讲， 人工智能就是想让计算机像人一样有智能，可以做过去人才能完成的事情。 在d a r t m o u t h 会议召开那年，塞缪尔( s a m u e l ) 研制出了跳棋机程序，这个跳棋 程序几年后战胜了美国一个跳棋州冠军，拉开了计算机挑战人类智能的序幕【3 】。不久后 纽厄尔( n c w c l l ) 和西蒙( s i m o n ) 开发的逻辑理论家数学定理自动推理程序【4 】以及通 用问题求解程序【5 】等都是对人工智能学科巨大的鼓舞，在随后的1 9 5 9 年，美籍华人王 浩教授在“自动定理证明”上获得了更大的成就【6 】，他在一台i b m 7 0 4 电脑上利用几分 钟的时间将罗素的数学原理中的全部定理证明了一遍，还给出了全部的推理过程。 当时塞缪尔等人乐观的估计不出l o 年在象棋等领域计算机智力会超过人类，事实上直 到近4 0 后，“深蓝”的出现，打败了国际象棋世界 冠军卡斯帕罗夫，才实现了这一梦想。“深蓝”是 中国台湾省的许峰雄( 图) 及其m m 团队设计的一 个计算机程序，在1 9 9 7 年5 月1 1 日扬名全世界， 经过9 天的精彩角逐，最终“深蓝”以3 5 比2 5 将 卡斯帕罗夫打败。这可谓是人工智能近年来的鼓舞 人心的大事件。除了在博弈和自动推理方向上，人 工智能另外一个非常重要的研究领域就是专家系统。 专家系统是为了充分利用各领域专家的知识进行自 动决策的一种系统。最早的专家系统可追溯到2 0 世 纪6 0 年代后期斯坦福大学开发的d e n d r a l 有机分 子结构推断系统【7 1 。随着人工智能水平的提高，专家 图1 1许峰雄 系统也取得了巨大的发展，专家系统以及涉及到多学科多领域，对社会带来了巨大的经 济效益。除此之外，人工智能研究方向还包括机器学习，模式识别，智能调度，分布 基于学习的多智能体协作方法研究及应用 式人工智能，人工生命，数据挖掘，多智能体等领域。可以说人工智能技术已经遍地开 花，而且定会得到越来越广泛的应用。 多智能体系统是分布式人工智能主要研究领域，多智能体系统利用相关技术将多个 智能体进行协同，规划，从而解决多种复杂问题。多智能体系统更能体现人类社会的智 能性，具有相当大的适应性和灵活性，能够很好的应对复杂不确定的环境因素，是当前 人工智能研究的一个重要方向。目前，多智能体系统在多机器人协调、工业自动控制、 网络通信、交通控制等领域得到了应用。 1 2 多智能体系统应用领域 多智能体系统是指由多个单智能体组合成的系统。其中的每个智能体都是独立自主 的个体，具有自治性，能够自己感知环境，对环境还能做出反应，还能够与其他的智能 体间进行通信，彼此协同工作，共同完成制定任务。因此说，多智能体本质上是一种分 布式智能系统，因此非常适合模拟像社会，大型机构等群体性工作。 多智能体系统因为其主要是研究协作，所以在很多领域内已经开始或者将要开始进 行应用： 1 2 1 多机器人搜索和救援 在执行多机器人搜索和救援任务时，环境事先一般无法预知，而且每个机器人只能 得到环境的部分信息，多机器人间必须进行准确的协调和分工，才能顺利的完成任务【8 1 。 1 2 2 机器人足球比赛 。 机器人足球比赛从提出到现在近 2 0 年的时间内f 9 】，取得了丰硕的成果， 越来越受到各界学者的广泛关注，又因 为是机器人进行的足球比赛，也越来越 得到了全社会的关注。科学家认为到本 世纪中叶，也就是2 0 5 0 年前后，由机 器人组成的足球队将会在赛场上战胜 人类11 1 0 机器人足球也是一种典型的多 智能体系统应用，需要机器人实时的进 行配合，赛场上的态势也是瞬息万变， 机器人必须要及时的判断态势，还要进 2 图1 2机器人足球小车比赛 两华大学硕士学位论文 行相互的通信来分配角色，最后还要进行动作规划，所以要设计出打败人类球队冠军的 机器人球队也是对人类智慧非常大的挑战。同时多机器人仿真比赛也是一个非常好的研 究多智能体策略，通信，协商等重要技术的平台，因此得到了世界各国广泛的关注。目 前世界上主要有f i r a 和r o b o c u p 两大国际赛事，f i r a 机器人足球比赛最早由韩国 高等技术学院金钟焕教授提出并于1 9 9 6 年在韩国举办了第一届国际比赛，r u b o c u p 是由日本学者m i n o ma s a d a 、y a s u ok u n i y o s h i 、h i r o a k ik i t a n o 等组织和发起的一项国际 性联合项目。 1 2 3 网络通信管理 目前网络通信越来越发达，远程通信系统需要对相连的各个终端进行实时的监控和 管理，因为网络关系的复杂性，当网络达到非常大规模的时候，如果网络中快速的添加 新个体或者新特性时，要确定各终端之间是否冲突非常困难，传统方法无法实现。如果 采用多智能体系统来进行网络管理，每个终端都是个智能体，则遇到冲突问题时，各个 终端之间能够相互协商，自动的进行冲突消解，直到建立合适的连接网络。除此之外， 在网络中经常发生通信堵塞，所以在网络负载均衡，故障诊断，传输等方面多智能体系 统都可以发挥其强大的功效【l l 】。 1 2 4 多机器人搬运 当被搬运物体体积过大，或者重量过大，单个机器人无法完成搬运，必须要多个机 器人协作来完成搬运任务时，这就涉及到各机器人间如何协作，如何通信的问题，因此 这也是多智能系统研究的一个范围【1 2 1 。 1 3 多智能体系统关键技术 由于多智能体系统是研究如何在多个自主的智能体间进行智能协调，通常情况下环 境又是实时变化，有相当大的不确定性。所以多智能体系统问题具有如下的特点：数据 的分布性，计算过程的分布性、异步性、并行性，环境信息的不完整性，多目的和多重 约束性等等。为了解决这些遇到的困难，所以多智能体系统主要研究系统体系结构、智 能体间的通信、智能体间的协作与协调以及学习等关键技术。 1 3 1 多智能体系统体系结构 多智能体系统结构决定了系统内每个智能体通信方式和协作模式。所以说体系结构 是多智能体理论的关键技术。从不同层次上来说多智能体系结构分为群体结构和个体结 构。 3 l - 。_ _ _ 。_ _ _ _ _ 。_ _ _ _ _ _ 。_ 。_ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。_ 一 基于学习的多智能体协作方法研究及应用 1 3 1 1 群体结构 要想让多个智能体实现对复杂任 务的处理，就不能简单的将多个智能 体简单的组合，必须要进行系统的设 计，将多个智能体有机的结合起来， 保证智能体间通信的流畅。 从控制上来看，群体结构可以分 为集中式和分散式两类【l3 1 。 集中式体系结构中有中央单元进 行任务分配和决策，能够找到全局最 优解，但是运算量大，如果中央单元 图1 3多智能体系统结构分类 出现故障，必须要有替补的中央单元，系统适应性较差。 分散式系统结构中每个智能体高度自治，系统的可靠性和容错性非常好，缺点就是 可能无法找到全局最优目标。分散式系统根据智能体间的组织方式，又可以分为分布式 和分层式两种不同的结构。 其中分布式是指每个智能体充当相同的角色，没有中央控制单元，这种结构的系统 具有高度的灵活性，但是可能导致资源分配不均衡。分层式结构包含小范围的控制单元， 同时具有分散式和集中式体系的优点，采用的比较多。 从智能体自生来看又可以分成同构系统和异构系统。在同构系统中每个智能体个体 都是完全相同的，因此在任务分配的时候比较容易进行平均分配。异构系统是指智能体 并非是完全相同的，每个智能体行为结构上都有差异，能力不完全相同，这样在进行任 务分配时就要根据智能体个体的差异进行任务的分配，一般在进行完成复杂任务时，就 可能需要多种不同的智能体来进行协作完成。 1 3 1 2 单个智能体自身结构 在分布式多智能体系统中，单个智能体是高度自治的，个体必须自己完成环境采集， 态势分析，决策，规划等不同的动作，所以智能体本身也要进行系统结构的设计。目前 众多学者以及提出了多种当智能体结构，如基于行为分解的包容式结构【1 4 1 ，反应式结构 1 5 1 等，下文中有详细的论述。 4 西华大学硕士学位论文 1 3 2 智能体间的通信 在多智能体系统中，环境的获取是靠每个智能体自身的传感器来进行感知，动态变 化的环境的变化引发的不可预知性和对传感器要求的变化，可能导致机器人得到的环境 是局部的，甚至是错误的。所以必须对多个智能体的数据进行融合，所以就要利用智能 体间的通信来进行数据交换以及协商等。 通信可以分为直接通信和间接通信。直接通信是指智能体的个体间直接进行通信双 方选择一种通信协议，进行握手协议之后就可以开始进行数据交换【1 6 4 7 】。由于受到带宽 的影响，随着智能体数目增多之后，通信量会急剧增加，所以如何减少通信量就成为了 多智能体系统的一个重要的研究问题。间接通信是指智能体不是进行直接进行通信，而 是整个系统包含一个共享区域，对所有的智能体都是可见的，就像是一块黑板，每个智 能体都可以阅读，也可以增加和修改【1 8 1 9 1 。采用这种机制后，智能体间不存在直接的信 息交换，所以不受到带宽的限制。但是这种异步性又会带来实时性变差的问题。所以在 解决复杂任务时，通常是将直接和间接两种方式结合使用，可以减小系统的通信量，还 可以提高系统的鲁棒性，缩短系统的反应时间。 1 3 3 智能体间的协作与协调 智能体间的协作是保证整个系统能够一起工作的关键。在多智能体系统中，协作与 协调是核心问题之一【别。协作指的是单个智能体无法独立完成任务，需要其他智能体的 帮助，这时就是协作。协调是指智能体为了避免和其他智能体发生冲突而改变自己的行 为，在资源冲突的情况下，如果没有良好的协调机制，则可能会发生死锁的情况。 从社会角色的角度上来讲，多智能体协作大概可以分为：协作型、自私型、完全协 作型、完全自私型、协作自私混合型。在多智能系统中，智能体不是孤立存在的，而是 要遵循社会规则，不能随心所欲，这样才能形成一个社会，这也是人类社会的缩影。因 此研究这些智能体间的依赖关系是多智能体系统必要的环节。 1 3 4 智能体学习 多智能体面临的环境通常是动态变化和不确定的，所以非常难建立精确的环境模型， 加上智能体获取的局部知识不一定完全精确等等，通过人为的事先设计好各项参数俨然 是不可行的。 为了使多智能体系统在未知的环境中有较强的适应性，采用学习的办法能够取得比 较好的效果。在对环境获取的过程中，智能体逐步的熟悉环境，认识到环境中的未知状 态，不断的调整自己来适应环境。在多智能体系统中，学习可以分为两个层面：一是智 基于学习的多智能体协作方法研究及应用 能体自身的学习，是指智能体在探知的过程中逐步的让自己适应环境；二是智能体系统 的学习，主要是指通过学习来改善智能体间的协作行为等等。 1 4 多智能体系统发展现状 经过二十多年的发展，多智能体系统取得了很大的进展。 从理论上来看，主要体现为： - 多智能体群集行为的研究。如鸟类迁徙，鱼群的躲避攻击等自然界典型群体行 为分析。r e y n o l d s 在1 9 8 7 年提出了模仿动物聚集的模型【2 ，该基本模型包含 三条规则：聚集、分离和调整。t a n n e r 等【2 2 】从理论上对r e y n o l d s 的模型进行厂 解释，建立了相应的数学模型，并用非平滑分析、代数图论等数学工具，设计 了局部分散控制策略，使得群体运动方向全局收敛到同一值并且相邻的智能体 间不发生碰撞。g a z i 等【2 3 】在群体模型中加入了环境模型，指出群体行为是智能 体间，智能体与环境相瓦作用，平衡的结果。 一致性问题的研究。在研究群体行为时，通常把位置和速度匹配单独拿出来研 究，并不考虑个体间的碰撞，这就是所说的一致性问题。一致性研究在一个多 智能体系统中，所有的智能体状态最终能够趋于一致。近年来，国内外专家在 这个问题上取得了不少成果。o l f a t is a b e r 等在文献1 2 4 。2 5 】中指出，如果多智能体 系统的拓扑结构是强连通的有向图，那么对于任意仞始状态，系统渐进收敛， 在强连通有向拓扑结构下，系统平均一致收敛的充要条件是信息交换图是平衡 图。r e n 等在文献 2 6 1 中指出一致收敛的充要条件是信息交换中包含生成树。 在应用方面，多智能体系统也得到了广泛的应用： 夺在军事上，p a r k e r 对飞机编队进行了研究【2 7 1 ，他利用局部信息和全局信息来保 持队形。此外，罗旭利用多智能体系统建立了防空火力分配模型【2 8 1 。 夺在机器人足球比赛上，在r o b o c u p 和f i r a 等赛事中，多智能体技术得到了 越来越广泛的应用。 夺在网络管理上，李章维【2 9 】等对多a g e n t 网络管理系统进行了研究，提高了网络 系统的响应速度，增加了系统的鲁棒性。 夺在交通管理方面，欧海涛【3 0 】等提出了基于多智能体技术的城市智能交通通知系 统，承向掣3 l 】等提出了基于多智能体的分布式交通信号协调控制方法。l i u n b e r g 等在1 9 9 2 年开发r 一种基于多智能体系统的空中交通控制系统。bb u r m e i s t e r 等在1 9 9 7 年开发了基于多智能体的交通和运输管理系统。 1 5 多智能体系统目前存在的困难 对于多智能体系统的研究，目前仍然有许多难点，还需要广大的学者进行深入的研 究。如学习算法收敛速度过慢：协同控制中信息交换时存在延迟等。 6 西华大学硕士学位论文 1 6 本文主要研究内容及论文结构 1 6 1 论文研究内容 本文围绕着多智能体系统，对多智能体系统进行了全面的论述和研究。主要研究内 容如下： 对多智能体关键技术，发展现状等进行了详细的论述。 对多智能体系统结构进行了深入的研究，对多种系统结构进行了比较。 对多智能体系统的协作进行了形式化描述，提出了一种基于“竞争协作”机制的多 智能体协作方案，并且对协作方案进行了优化，可以有效的避免死锁问题的发生。 对智能体强化学习问题进行了深入的研究，分析了目前多种主流学习算法，并对算 法进行了形式化描述和通俗的解释。 对多智能体系统分层学习进行了细致的研究，提出了一种基于m a x q 的多智能体 分层学习算法，改善了系统协调能力。 1 6 2 论文结构 论文分为6 章： 第1 章绪论：本章对多智能体系统的历史和发展进行了详细的追溯，并对多智能 体研究的关键技术进行了深入的了解，同时指出了多智能体系统目前取得的成果和遇到 的一些团难。 第2 章多智能体系统结构设计：本章从单个智能体结构层面和多个智能体组织层 面入手，对现有的主要体系结构进行了详细的分析和解释，并对其各自的优缺点进行了 比较。 第3 章多智能体协作研究：本章利用时序逻辑语言对多智能体协作和协调问题进 行了形式化描述和建模，同时根据协作模型提出了一种基于“竞争协作”机制的多智能 体协作方案，并且对协作方案进行了优化，可以有效的避免死锁问题的发生。 第4 章多智能体协作中的强化学习：本章详细的分析了目前用于智能体学习的主 流学习算法，并对多种算法进行了形式化描述和通俗的解释，同时也对多智能体分层学 习算法进行了系统的理解。 第5 章基于m a x q 的多智能体分层学习算法：本章在前几章基础之上提出了一种 基于m a x q 的多智能体协作算法，提高了多智能体系统的协调能力。 第6 章结束语：本章对全文进行了总结，对下一步的研究工作做了展望。 7 基于学习的多智能体协作方法研究及应用 2 多智能体系统结构设计 2 1 引言 多智能体系统是由多个高度自治的智能体有机结合的形成的系统。因此多智能体系 统的性能受到两个层面的影响，一是来自智能体本身层面，包括智能体自身的结构，对 外界环境的交互模式，反应能力，学习性等等：二是来自多个智能体间交互的层面，多 个智能间的组织方式不同，会大大的影响多智能体系统的性能。 本章主要从两个层面来研究多智能体系统结构设计，包括组织层面和单个智能体本 身层面，并对各种已有的系统结构进行了优缺点分析。 2 2 单个智能体结构 单个智能体必须是高度自治的，所以智能体个体涉及到环境获取、分析、决策、规 划等动作，为了更好地协调这些动作，就需要设计良好的结构去组织和调控智能体的各 项行为。目前已有的多智能体控制结构，大致可以分为两类：基于功能的结构和基于行 为的结构。 2 2 1 分层递阶式结构 分层递阶式跚结构将任务分成 多个层面来进行解决。最高层接到最 原始的任务，然后将问题进行理解， 然后交给下层处理。中间层在接到上 层交给的任务时，先将该任务转换成 自己层的问题，对问题进行分析和分 解，再将分解得到的子问题交给下一 层处理。 j o r gpm u l l e r 3 4 1 提出了一种三层 结构模型，将系统分成协作规划层、 协调规划层和行为控制层。其中各层 功能如下： l 、协作规划层 图2 1分层递阶式结构 西华大学硕士学位论文 协作规划层主要负责任务的分解和分配；智能体间的通信管理等。 2 、协调规划层 协调规划层用于协调智能体间的运动，主要进行冲突消解。 3 、行为控制层 行为控制层用于基本动作的执行。 采用分层递阶式结构使得系统层次分明，实现起来比较容易，但是由于分了多层， 导致整个系统反应不够迅速。 2 2 2 包容式结构 包容式结构是一种典型的基于 行为的控制结构，最早由b r o o k s 提 出。他将行为进行并行处理，每个 行为负责一个具体方面【1 4 1 。在包容 式结构中，下层级别表示动作更为 基础，上层可以对下层输出进行抑 制作用。采用这种体系，每一层可 以同时得到输入，各层之间没有依 赖关系，加快了系统的反应速度。 日 9 图2 2包容式结构 基于学习的多智能体协作方法研究及应用 图2 3b r o o k s 三层包容式结构 在b r o o k s 的设计中，第l 层为基本动作层，保证机器人不发生碰撞。第2 层添加 了漫游功能，并且对r u n a w a y 模块进行了抑制。第3 层添加了环境探测模块，能够进行 自动的搜索环境，抑制w a n d e r 模块。 2 2 3 简单反应式结构 简单反应式结构也是基于行为的，通常用于一些动作简单，但是要迅速反应的应用 场合。智能体感知环境，然后到自己内置的规则库中寻找匹配的规则，直接进行动作， 不需要额外的推理。这种反应结构实际上就是包容式结构的底层工作方式。a r g e 和 c h a p m a n 也提出了类似的观点，他们认为日常生活里大多数时间都在做常规的活动，只 要学会了，就可以例行公事一样去完成。他们设计了一个p e n g i 系统【3 5 】来验证他们的 想法。 1 0 两华大学硕仁学位论文 反应式结构虽然能够较迅速的对外界环境进行响应，但是由于其结构简单，通常不 具备学习能力，导致系统扩展性能比较差。 ，、 智能体 正b 艟旦墓 i 孓t 矿。口仃 环境状态 环境 i 规则库 动作 曲客；旦奠i 矾7 i j 口w 图2 4简单反应式结构 2 2 4 效率驱动的结构 为了高效的完成任务，有人提出了基于效率驱动的智能体结构。在该结构中，规划 器对目标规划时求出多个可行解，。效率比较器再根据具体的问题进行效率比较，选择效 率最高的动作序列。 智能体 内置状态卜 厂环境变钇婀一1 未订粕l 牟j t 仆目参蛆 i 历由动住昱幺晌i 一j 1 、岘扒忿l 7 l ：，t 必型卜删 规划 i 环境 陬荤比较藉_ 一f 1 目 妯仨盟t 厂嘞帘 扪jw 图2 5效率驱动结构 基f 学习的多智能体协作方法研究及应用 2 3 多智能体群体系统结构 群体系统结构主要研究如何对智能体进行组织和管理，不同的群体结构中智能体信 息交换，与其他智能体关系，系统中扮演的角色都不太相同，以适应不同的场合。 在多智能体系统结构设计时，要充分考虑系统的任务分解和分配能力、通信能力、 规划能力、学习能力等等。目前主要有如下几种系统体系结构： 2 3 1 集中式结构 在集中式控制结构中，存在一个主 控智能体( 中央处理单元) ，其余的智 能体都是等价的。主控智能体直接与每 个智能体进行交互。每个智能体将各自 的状态和信息等交给主控智能体，主控 智能体根据收集到的多个智能体的各 种信息进行统一规划和决策，然后再将 规划和决策结果反馈给单个智能体，实 现整个系统的控制。 由于采用了统一规划，所以集中式 这种控制结构能够实现全局最优规划， 整个系统协作斜率非常高，多个智能体 间结合的比较紧密。万事总有其两面性， o 图2 6集中式结构 有优点就必然有不足之处。采用集中式结构面临着如下几个问题： 由于所有规划都在主控智能体进行，导致主控智能体运算量非常大，在规模不太小 的情况下，主控智能体必须要有足够的规划运算能力。 夺整个系统命令执行都由主控智能体来决策和发布，这样使得整个系统对主控智能体 产生过多依赖，降低了系统的稳定性。 如果主控智能体发生故障，必须要有替补的主控智能体，这样增加了系统的设计难 度。 所有的智能体直接同主控智能体通信，势必会造成通信带宽紧张，很有可能发生信 息堵塞的情况。 西华大学硕士学位论文 2 3 2 分布式结构 分布式控制结构是指在系统中没 有主控智能体，每个智能体的地位是平 等的。系统中的每个智能体都是高度自 治的，能够与邻近的智能体自动的协作 与协调。这种系统结构使得决策和规划 都有智能体自身来完成，解决了集中式 控制主控智能体计算大的问题，还有系 统对单个智能体没有直接的依赖关系， 使得系统有比较高的灵活性、容错能力 及稳定性。但同时由于单个智能体过于 自由，在资源分配时候容易引发分配不 均问题，可能会导致系统利用率不高。 还有由于缺乏全局的规划，智能体不一 图2 7分布式结构 定能找到全局最优解，往往只能得到较好解。 2 3 3 分层式结构 分层式结构是一种介于集中式和分布式结构之间的混合式结构。综合了集中式和分 布式的优点，是一种经常采用的结构。这种结构借鉴了我们现实社会中企业里的人事机 构图，智能体根据层次分成不同的层面进行完成任务【3 2 1 ，下层必须绝对服从上层的命令， 同层之间唯协作关系，由他们的上层进行任务分配。整个系统中有组织者，有执行者， 这样就可以使得各尽其责，不至于太过散乱，核心层的负载也不会过重。这样带来的不 足之处就是系统结构在设计的时候比较复杂。 1 3 一体。， 一、唆爹酽 ，毙z潞、辫骂 基于学习的多智能体协作方法研究及应用 曰曰曰 图2 8分层式结构 2 3 4 对抗式结构 机器人足球比赛是一种典型的对抗结构3 2 1 。所谓的对抗结构指的是智能体系统在自 己达到目标的同时还要尽量阻止对手达到目标。在比赛的过程中，还有另外个角色来 充当裁判，以监督对抗过程是否符合比赛规则，是否公平。 回国 图2 9对抗式结构 1 4 西华大学硕士学位论文 2 3 5 拍卖结构 拍卖结构是根据市场运作机制而提出的一种结构。在现实社会中，通常由卖家根据 需要进行招标公布，多个买家进行竞拍，第三方的拍卖师对交易进行评估，选择利益最 大的进行交易。在多智能体系统中，某个智能体或智能体集团对任务进行“拍卖”，其 他的智能体进行竞拍，智能体拍卖师对各种情况进行分析，最后选择代价和效益间权衡 最佳的买卖进行交易。其中的关系为卖家和买家都依赖拍卖师，卖家和买家没有关系， 买家之间为竞争关系，所以说这个结构中“拍卖师”充当着非常重要的角色，拍卖师对 交易性价比的评定影响了系统的整体性能。 2 4 小结 图2 1 0拍卖师结构 本章围绕着多智能体系统结构展开研究，从群体和个体层面分析了多种现有的流行 结构，并对各种结构的优缺点进行了分析。 基于学习的多智能体协作方法研究及应用 3 多智能体协作研究 3 1 引言 多智能体协作和协调问题是多智能体系统研究的核心问题之一。多智能体协作是保 证整个系统能够协同工作的关键。多智能系统中，每个智能体的意图和能力可能不一定 相同，如何对多个智能体进行有效的组织，这影响到整个系统是否能有效的工作。多智 能体系统是一门多学科多领域的研究范围，目前已经有若干政治学、社会学、人类学、 组织学、经济学、法律学等多学科在内的研究成果应用到了多智能体系统之中。多智能 体协作就是要以自主的智能体为中心，通过各种手段进行组织，来进行协作，达到整个 多智能体系统的目的。 在研究多智能体协作的过程中，早期的多智能体协作主要集中在多机器人系统协作 的研究之上，对什么是多机器人协作，各国的学者提出了不同的定义。n o r e i l s l 3 6 1 把多机 器人协作定义为：多个机器人一起完成单个机器人无法完成的任务，或者多个机器人可 以使系统获得更高的性能。c a o t 3 7 1 提出：对于指定的任务，如果多机器人系统能够依靠 协作机制，使得系统的功能和效率得到提升，则多机器人系统表现出协作行为。上面两 个定义虽然略微有差别，但是核心都是说要存在一种协作的机制并且使得系统性能提高。 我们将这个定义应用到多智能体协作的上，我们可以认为所谓多智能体协作，是指多智 能体系统通过有效的组织手段，使得整个系统完成单个智能体不能完成的任务，或者整 个系统的性能得到了提升。多智能体协作问题可以分解为智能体分组、任务分解、任务 分配和调度、冲突消解等子问题。 多智能体协调与多智能体协作是个不同的概念。多智能体协调是指多