（计算机应用技术专业论文）多智能体协作学习方法的研究.pdf

摘要 在多a g e n t 系统中，由于环境是动态变化的，其他a g e n t 的行为是未知的， 所以多a g e n t 系统及系统中的每个a g e n t 应当具备学习或自适应能力。强化学习 作为一种不需要环境模型的机器学习方法，现已成为多a g e n t 系统的研究热点。 与此同时，由于单个a g e n t 的资源和能力的有限性，需要多个a g e n t 之间的协作 来共同完成任务。 。 r 本文的主要研究工作包括以下几个方面： ( 1 ) 论文首先介绍了a g e n t 和多a g e n t 系统的研究基础，然后分别围绕多a g e n t 学习方法、多a g e n t 协作机制和强化学习三个方面简要阐述了多a g e n t 协作学习 的基础知识。 ， 、 ( 2 ) 将黑板模型、融合算法以及强化学习技术相结合，提出了一种改进的多智 能体协作学习方法。其中，黑板是一块共享的存储区域，可以实现信息共享；融 合算法用来对共享信息进行融合；强化学习技术利用融合结果进行动作选择。 ( 3 ) 追捕问题是一个多a g e n t 系统，同时存在多a g e n t 之间的协作与竞争，被 广泛用来测试人工智能领域的学习算法。本文利用追捕问题对改进的多智能体协 作学习方法进行实例分析与仿真验证。实验结果表明，该方法能够有效地提高多 a g e n t 系统中a g e n t 的协作学习能力。 关键词：智能体：多智能体系统；强化学习；协作；追捕问题 a b s t r a c t i nm u l t i _ a g e n ts y s t e m ，t h ee n v i r o n m e n ti s d y n a m i ca n dt h eb e h a v i o r so fo t h e r a g e n t sa r eu n k n o w n ，t h e r e f o r et h em u l t i a g e n ts y s t e ma n de a c ha g e n ti nt h es y s t e m s h o u l db ea b i l i t yt ol e a r no rs e l f - a d a p t a sam a c h i n el e a r n i n gt h a td o e s n tn e e dt h e e n v i r o n m e n tm o d e l ，r e i n f o r c e m e n tl e a r n i n gh a sb e e nt h eh o t p o ti n t h em u l t i a g e n t s y s t e m a tt h es a m et i m e ，b e c a u s et h er e s o u r c ea n da b i l i t yo fs i n g l ea g e n ta r el i m i t e d ， i tn e e d sc o o p e r a t i o no fs e v e r a la g e n tt oc o m p l e t et h et a s kt o g e t h e r t h em a i nr e s e a r c ho ft h i st h e s i si sa sf o l l o w s ： ( 1 ) t h i st h e s i sf i r s t l yi n t r o d u c e st h er e s e a r c hf o u n d a t i o no fa g e n ta n dm u l t i - a g e n t s y s t e m ，t h e ni n t r o d u c e sb r i e f l yt h ee s s e n c ek n o w l e d g eo fm u l t i a g e n tl e a r n i n gm e t h o d ， m u l t i 。a g e n tc o o p e r a t i o nm e c h a n i s ma n dr e i n f o r c e m e n tl e a r n i n g ( 2 ) a ni m p r o v e dm u l t i a g e n tc o o p e r a t i o nl e a r n i n gm e t h o di s p r o p o s e dw i t h b l a c k b o a r dm o d e l ，f u s i o na l g o r i t h ma n dr e i n f o r c e m e n tl e a r n i n ga l g o r i t h mu n i f i e d i n t h em e t h o d ，t h eb l a c k b o a r di sam e m o r yr e g i o nt h a tm a yr e a l i z ei n f o r m a t i o ns h a r i n g ； t h ef u s i o na l g o r i t h mi su s e dt of u s i o nt ot h es h a r e di n f o r m a t i o n ，a n dr e i n f b r c e m e n t l e a r n i n ga l g o r i t h mi su s e dt os e l e c ta c t i o nw i t ht h ef u s e dr e s u l t ( 3 ) p u r s u i tg a m ep r o b l e mi sam u l t i a g e n ts y s t e ma n ds i m u l t a n e o u s l yh a st h e c o o p e r a t i o na n dc o m p e t i t i o na m o n gm u l t i a g e n t s ，s oi ti sw i d e l yu s e dt ot e s tt h en e w l e a r n i n ga l g o r i t h m si nt h ea r t i f i c i a li n t e l l i g e n c ef i e l d t h i st h e s i sm a k e se x a m p l e a n a l y s i sa n de m u l a t i o nv a l i d a t i o nt ot h ei m p r o v e dm e t h o d t h r o u g hp u r s u i tg a m e p r o b l e m ，t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h em e t h o dc a ne f f i c i e n t l yi m p r o v et h c c o o p e r a t i o nl e a r n i n ga b i l i t yo fa g e n t si nt h em u l t i a g e n ts y s t e m k e yw o r d s ：a g e n t ；m u l t i - a g e n ts y s t e m ；r e i n f o r c e m e n tl e a r n i n g ；c o o p e r a t i o n ； p u r s u i tg a m e 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 葛嗣华 日期：矽昭年f 月，7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ) 作者签名： 芬硒华 刷程轹彬 日期：纱咿年r 月j 日 第一章绪论 学习是a g e n t 的一项重要能力，它体现了a g e n t 的智能程度，使得a g e n t 能 够在开放、复杂、动态的环境中提高适应性。同时，单个a g e n t 常常由于其有限 的资源和能力不能完成复杂的任务，因此多个a g e n t 之间的协作就显得非常必要。 学习是实现多a g e n t 系统协作的有效解决方法之一，一方面，为多a g e n t 系统增 加学习机制可以有效地实现a g e n t 之间的协作；另一方面，为多a g e n t 系统增加 协作机制也能够加速多a g e n t 的学习进程。二者是相互促进，相辅相成的。 本文主要研究多a g e n t 协作学习方法，研究的目的是使a g e n t 通过学习技术 不断积累知识并通过相互协作来提高a g e n t 的协作学习能力。文中以追捕问题为 研究背景，提出一种改进的多a g e n t 协作学习方法并给出了相应的实验结果。 1 1 研究的背景及意义 随着计算机网络、分布式计算等技术的不断发展，所要研究的系统往往异常 复杂、庞大并呈现出分布式特性，在解决问题时，单个a g e n t 因个体所拥有的知 识和计算资源的限制已经不能胜任所面临的任务，这就需要多个学习a g e n t 之间 协作求解。因此，自2 0 世纪9 0 年代以来，对多a g e n t 系统的研究迅速发展，逐 渐成为分布式人工智能研究的一个热点。 多a g e n t 系统代表了一类开放、复杂和动态的系统，系统的变化是由多个a g e n t 之间的交互所引起的n ，。目前典型的多a g e n t 系统包括机器人足球、股票交易市场、 电力市场、追捕问题和c o o r d i n a t i o ng a m e s 等等啼，。其中追捕问题，是一个典型的多 a g e n t 协作与竞争系统，它为分布式人工智能的研究提供了一个标准的试验平台。 虽然协作问题已经研究了很多，但是利用协作来改善学习效果方面的研究并 不多见。因此，多a g e n t 学习与协作仍是当今人工智能领域研究的难点与热点。 首先，在近二十年有关多a g e n t 系统学习问题的研究中，强化学习作为一种不需 要环境模型、通过a g e n t 与所处环境进行自主交互的机器学习方法，被直接移植 到多a g e n t 系统中d ，。事实上，多a g e n t 系统的学习过程相当复杂，它直接依赖于 多个a g e n t 的存在和交互，所以多a g e n t 系统的学习并不是传统单a g e n t 强化学 习的简单增强；其次，近年来，通过自我学习来实现多a g e n t 系统的协作已成为 新的研究热点，其关键问题是用学习技术增强多a g e n t 系统的智能，改善a g e n t 的动作策略来实现协作。 本文以追捕问题为背景，采用协作机制和独立强化学习技术来研究多a g e n t 系统中的协作学习问题，在多a g e n t 系统的协作学习方面做了一定的研究，目的 是使a g e n t 通过学习提高智能从而更好地协作，而协作又可以加快学习进程。本 文所涉及的主要内容包括强化学习、多a g e n t 协作学习和追捕问题等。 1 2 强化学习概述 1 2 1 强化学习的发展历史 强化学习的思想来源于人类对动物学习过程的长期观察。强化学习，是人工 智能领域既崭新而又古老的课题，其发展历史可以粗略地划分为两个阶段：第一 阶段是五十年代至六十年代，可以称为强化学习的形成阶段；第二阶段是八十年 代以后，可以称为强化学习的发展阶段。 在第一阶段，靠强化一和“强化学习一这些术语由m i n s k y n ，于1 9 6 0 年首次提 出。在控制理论中，由w a l t z 和付京孙，于1 9 6 5 年分别独立提出这一概念。这些 词描述了通过奖赏和惩罚的手段进行学习的基本思想。学习是通过试错 ( t r i a l a n d e r r o r ) 的方式进行的，当一个行为带来正确( 或错误) 的结果时，这种 行为就被加强( 或削弱) 。在六七十年代，强化学习的研究陷入了低谷。j 进入八十年代以后，随着人们对人工神经网络的研究不断取得进展以及计算 机技术的进步，强化学习的研究又呈现出一个高潮，逐渐成为机器学习研究中的 活跃领域。s u t t o n ，于1 9 8 4 年，在他的博士论文中提出了a h c 算法，比较系统地 介绍了a h c 思想，文中采用a h c 和r l 两个神经元对不同的算法进行了大量实 验；s u t t o n 又于1 9 8 8 年在 m a c h i n el e a r n i n g ) ) 上发表了题为“l e a r n i n gt op r e d i c t b yt h em e t h o d so f t e m p o r a ld i f f e r e n c e s 一的著名论文，可以说这是一篇经典之作。 论文中提出了瞬时差分t d ( t e m p o r a ld i f f e r e n c e s ) 方法，解决了强化学习中根据时 间序列进行预测的问题，并且在一些简化条件下证明了t d 方法的收敛性；d a y a n 对t d ( 名) 方法的收敛性作了进一步的证明。许多学者对t d 方法进行了分析和改 进；在强化学习方法中，另一个比较著名的算法就是w a t k i n s t ”，等人提出了的 q 1 e a r n i n g 算法，它可以被看作一种离策略t d 算法。w a t k i n s 1 对q l e a r n i n g 算法 的收敛性进行了证明；j i n gp e n g 及w i l l i a m s 等人提出了多步q l e a r n i n g 方法： s i n g h “2 1 采用随机逼近的方法来解决最优控制问题，提出了替换迹( r e p l a c i n g e l i g i b l i t yt r a c e s ) 计算方法并对替换迹进行了理论分析，证明了替换迹具有学习速 度快而且也比较可靠的特点。 ： 从国内情况看，强化学习还处于起步阶段。阎平凡n ，于1 9 9 6 年在 ( 3 2 = 石( s ，口) 瑶【+ ，( ，) 】 口， 式中，是，时刻a g e n t 从环境状态& 到s ，+ l 转移后所接收到的瞬时奖赏值，其值 1 7 可以为正、负或零。7 【0 ，l 】是累计奖赏折扣参数。 r 首先通过( 3 1 ) 式构造一个返回函数马，用于反映系统在某个策略i t 指导下的 一次学习循环中，从状态函往后所获得的所有折扣累计奖赏和。由于环境是不确 定的，系统在某个策略石指导下的每一次学习循环中所得到的尼有可能是不同的。 因此在s 状态下的值函数要考虑不同学习循环中所有返回函数的数学期望。因此 在石策略下，系统在s 状态下的值函数由( 3 2 ) 式定义，其反映了如果系统遵循石 策略，所能获得的期望的折扣累计奖赏和。 ； 定义3 5 动作值函数 妒 动作值函数q ( s ，口) 定义为：从状态s 开始执行动作a 的瞬时奖赏值加上以后遵 循最优策略万所获得的折扣奖赏和的期望。 i q 。( j ，口) = e r ，s t = s ，口l = 口) = e ：厂r t + t + l l 岛= j ，a t = 口) ( 3 3 ) k = o q 值是对奖赏的一种预测估计，对于一个状态j ，如果它的奖赏值低，并不意 味q 值就低，因为如果s 的后续状态产生较高的奖赏，仍然可以得到较高的q 值。 估计值函数的目的是得到更多的奖赏，然而动作的选择主要是基于q 值判断的。 也就是说，a g e n t 选择的动作是使产生的新状态具有最高q 值，而不是转移到新 状态时有最高的瞬时奖赏，因为从长远来看，这些动作将产生最多的奖赏。 _ ：。强化学习的最终目的是寻找最优策略万：一个从状态集到动作集的映射，使，。 每个状态j 的矿f ( j ) ( 或q 。( s ) ) 的值都同时达到最大。y ( s ) 和q ( j ，a ) 是最优值函 数，分别定义如下： ，。 + ， ，y ( j ) = r e = r f ( j ) = 蕊；瑶【匙+ y v o 明，s ， 、( 3 4 ) ： j ： q 。( s ，口) - m 。a x q ( s , a ) 2 车瑶【匙+ 7 嬲q ( s ，口) 】，v s s ，v 口彳( 引 ( 3 5 ) _ ， 4 一 上式是b e l l m a n 最优方程，不依赖某一个具体的最优策略。由此可以得出相 应的最优策略定义为： 7 1 ( s ) = a r g m ，a x ( ，( s ，口) + 7 p ( s ，口，s g v ( s ) ，v se s ( 3 6 ) 万( j ) = a r g m a x q ( j ，口) 。-一 ( 3 7 ) a e a ( s ) 3 1 4 经典的强化学习算法。 强化学习问题可以有两种解决方法，即有模型的学习和无模型的学习。这里 的模型包括了状态转移概率函数t ( s ，a ，s ) 和奖赏函数r ( s ，a ) 的知识。有模型的学习 是指在已知环境模型r 和j f c 的情况下学习最优策略，其可以根据已知的模型知识 1 8 使用动态规划中的值迭代或者策略迭代算法来求解：无模型学习是指在环境模型 知识未知时学习一种最优策略。 ， 一 解决无模型学习有两种方法m 1 ：一种是基于a g e n t 与环境的交互，先学习环境 模型知识，再利用学习到的环境模型知识，使用动态规划技术学习a g e n t 的优化 行为，该方法称为基于模型的方法( m o d e l b a s e d ) ：另一种是a g e n t 和环境交互但 不学习模型知识，而是直接学习行为策略，该方法称为模型无关法( m o d e l f r e e ) 。 根据这两种分类可得到为强化学习的二维分类表，如表3 1 。 表3 1 强化学习二维分类表 强化学习折扣型平均型 无模型 t d 、q - l e a r n i n g 、s a r s ar - l e a r n i n g 、a r l 有模型 d y n a q 、a r t d p 、p r i o r i t i z e ds w e e p i n g h l e a r n i n g 这里介绍几种经典的强化学习算法：动态规划( d y n a m i cp r o g r a m m i n g ，d p ) 算 法、蒙特卡罗( m o n t ec a r l o ，m c ) 算法、瞬时差分( t e m p o r a ld i f f e r e n c e s ，t d ) 算法、 q - l e a r n i n g 算法和s a r s a 算法。 。 1 d p 算法 - d p 是由b e l l m a n t 伽于1 9 5 7 年提出来的，他证明了d p 方法可以用来解决很广 泛的问题。原本d p 用于控制领域，特别在1 9 6 1 年m i n s k y 第一次提出可将d p 和 强化学习问题联系起来，这样问题应该有类似于s a m e u l 的回退分析。1 9 8 9 年 w a t k i n s 明确的将强化学习与d p 联系起来，并定义了一类被称为增量动态规划的 强化学习。 。 简单地说d p 是利用值函数来搜索好的策略，适用于解决大规模问题。如果环 境模型即策略x ( s ，a ) 、奖赏函数尺三和状态转移概率函数瑶已知，那么可以采用值 迭代或者策略迭代的方法来近似的求出g o ，k ，哆，其更新公式如式( 3 8 ) 和( 3 9 ) 所 示： 以+ l ( s ) = a r g m a x 瑶【瑶+ 形。明 a j 圪+ i ( s ) 卜e a r , + l + ，圪( 量+ i ) i = s 卜万( s ，a ) e 瑶【匙+ ，圪o ) 】 口j ( 3 8 ) ( 3 9 ) 显然，当圪= 旷时算法就可以终止了，因为此时更新公式已不起作用，b e l l m a n 方程保证了这一点。d p 算法的回溯图如图3 3 所示。 d p 容易出现“维数灾一和“建模灾一问题，其计算量会随状态变量的数量呈 指数增长：它还要求事先知道系统的确切模型信息，而在实际应用中，这些环境 信息往往是不知道的，这时d p 方法就不适用了。 1 9 ( e p i s o d e ) 。图3 4 给出了它的回溯图。 9 西 f r t + l 十 。 囱终止状态t 图3 4 蒙特卡罗方法计算值函数的回溯图 这个回溯图即是一段情节( 幕) 。当环境状态为终止状态时，将得到的累积奖 赏赋予开始状态s 的值函数。可以想象的到从s 出发到达终止状态t 的过程中，s 可能出现不止一次。这样对s 的值函数的更新就至少有两种方法：一种是 f v m c ( f i r s tv i s i tm c ) ，另一种是e v m c ( e v e r yv i s i tm c ) 。前者将奖赏赋予第一次访 问的s ，后者是将每次访问s 到终止状态r 的奖赏平均后赋予s 的值函数。二者在 理论上是有区别的，但它们都收敛到矿彳。其值函数更新公式如下： y ( ) 卜y ( 墨) + 口 墨一y ( ) ( 3 1 0 ) 冠表示第疗次累积奖赏值。m c 除了有以上提到的一些优点以外，它在计算一 个状态的值函数时不依赖于其它状态的值函数，这样可以只计算我们感兴趣的状 态。m c 的另一个优点是它对马尔可夫性要求的不是很严格。 3 t d 算法 q t d 算法是由s u t t o n 1 于1 9 8 8 年为了解决延迟回报引起的时间信度分配问题而 提出的一种增量式在线学习预测算法，是强化学习技术中最主要的学习技术之一。 t d 学习是m c 思想和d p 思想的融合，即一方面t d 算法在不需要外部环境模型 情况下可以直接从a g e n t 原始经验学起；另一方面t d 算法在更新状态值函数的估 计时部分依赖于其它已经学到的估计。 最简单的t d 算法是一步t d 算法，即t d ( 0 ) 算法，其迭代公式为： y ( 岛) 4 - - y ( ) + 口【，；+ i + 厂y ( 焉“) 一y ( 岛) 】 y 石( s ) = e 冠l 墨= s ) = t y 。b = 田 k 1 0 ( 3 1 1 ) ( 3 1 2 ) = 乓+ 7 7 。b = s k - 0 ， = 乓 ，：+ l + y v 霄( s t + 1 ) l 焉= s ) t d ( 0 ) 的目标是+ l + ( + ) ，m c 把第一行公式的估计作为它的目标，而d p 把最后一行的公式的估计作为它的目标。t d ( 0 ) 算法的回溯图如图3 5 所示，图3 6 为t d ( 0 ) 学习算法。 v r t + i 占o 图3 5t d ( 0 ) 方法计算值函数的回溯图 图3 6t d ( 0 ) 算法 4 q l e a r n i n g 算法 q l e a r n i n g 算法“町是由w a t k i n s 于1 9 8 9 年提出的一种与模型无关的、增量式动 态规划强化学习算法，也被称为离策略t d 学 - - ( o f f - p o l i c yt d ) 。它实质上是m d p 的一种变化形式。q l e a r n i n g 的思想是不去估计环境模型，而是通过对状态动作 对的评价来估计学习的值函数q ( s ，a ) 来学习最优行动策略。该算法简单、收敛速 度快、易于使用，近年来受到广泛的关注，被誉为强化学习算法发展中的一个重 要里程碑。 2 l 定义q 值是在状态研执行动作a ，且此后遵循最优策略执行下去，将得到的折 扣累计奖赏值，如式( 3 1 3 ) ： 矿( s ，口) = 以，- i s ，口 + 厂丁( s ，口，s ) 1 搿矿( j ，口) ( 3 1 3 ) ： j 定义a g e n t 的最优q 值q ( s ，a ) 定义是执行相关的动作并按照最优策略执行下 去将得到的回报的总和，即在每一状态选用q 值最大的行为。q ( s ，口) 和万。( s ) 求解 如公式( 3 1 4 ) 和( 3 1 5 ) 所示： 郎，口) = 口) + r e 硒口，s ) 呼幽，口) 3 1 4 矿( s ) = a r g m a x q ( s ，口) 。i ( 3 1 5 ) a e a 其中，丁( j ，a ，s 表示在状态j 执行动作a 后转移到后继状态s l 的概率；o f 是【o ，1 】 上学习速率，在学习过程中随着智能体自身素质的不断提高，口会逐渐衰减从而 使学习算法收敛；r ( o 7 - - j 都是贪婪的。 。q l e a r n i n g 的回溯图如图3 7 所示。 图3 7q - l e a r n i n g 方法计算值函数的回溯图 a g e n t 的每一次学习过程可以看作是从一个随机状态开始采用一个策略来选 择动作，如贪婪策略或b o i t z m a n n 分布策略。采用随机策略是为了保证a g e n t 能够搜索所有可能的动作对每个q ( s ，口) 进行更新。a g e n t 在执行完所选的动作后， 观察新的状态和回报，然后根据新状态的最大q 值和回报来更新上一个状态和动 作的q 值。a g e n t 将不断根据新的状态选择动作，直至到达一个终止状态。 q 1 e a r n i n g 算法如图3 8 所示： 图3 8q - l e a r n i n g 算法 。 q 1 e a r n i n g 相关环境信息较少，为了达到好的性能指标就需要大量的经验数据 ( 样本数据) ，学习效率不高，尤其是当状态空间和决策空间较大时。 5 s a r s a 算法 s a r s a 算法是r u m m e r y 和n i r a n j a n 于1 9 9 4 年提出的一种基于模型的强化学习 算法，最初被称为改进的q 1 e a r n i n g 算法。它们都是通过学习q 值来获得策略万， 不同点在于对状态动作值q ( s ，a ) 的修正，即s a r s a 是一种在策略t d 学习( o n p o l i c y t d ) 。 一个强化学习算法基本上可以分为两个部分：学习策略部分和更新准则部分。 在学习策略部分中，将经验映射为当前动作的选择，而构成非静态策略；更新准 则部分则确定算法怎样利用经验改变其对最优值函数的估计。根据学习策略和更 新准则之间的关系，s u t t o n 和b a r t o 将强化学习分为离策略算法和在策略算法。 在一个离策略算法中，更新准则不需要和学习策略有任何关系，它是基于并 不实际执行的假设动作来估计和更新值函数。q 1 e a r n i n g 是一类离策略算法，根据 q - l e a r n i n g 的更新法则，q ( 毛，a 1 ) 4 - ( 1 - a , ) q ( s , ，口f ) + q 【+ y 哩擎q + l 6 ) 】可知， q ( s ，口f ) 的更新依赖于m a x 砌q ( s ，+ ，b ) ，即依赖与各种假设的动作，所以这种算法 是一种离线算法。s a r s a 算法是一种在策略算法，它严格的基于执行某个策略所获 得的经验来更新值函数。s a r s a 的更新准则是： q ( 墨，口f ) 4 - - ( 1 一q ) q ( 岛，口，) + q 阮+ 厂q ( 西+ i ，口，+ 1 ) 】 ( 3 1 7 ) 可见，s a r s a 是利用基于学习策略所选择的实际动作a t + l 来更新q 值的。 旗 图3 9s a r s a ( 0 ) 学习算法 3 1 5 有待进一步研究的问题 尽管在过去的二十年中，强化学习的研究已取得了突破性进展，但仍然存在 很多问题有待解决t 。 1 系统地研究强化学习理论。虽然国内外许多学者对强化学习理论进行了研 究并取得了一定的成果，但有关理论问题还未得到完全解决，还需要进行系统的 研究。 。 2 加强强化学习的应用研究。虽然强化学习应用的范围比较广泛，但它比较 适合应用于智能控制及智能机器人领域。从国内的研究现状来看，强化学习的应 用研究还不广泛，尤其在实际系统中的应用更少，应加大这方面的研究力度。 3 提高强化学习速度的理论和方法研究。虽然强化学习在理论及应用方面的 研究取得了一系列进展，但真正应用到实际还有许多工作要做。在强化学习中， 环境给出的只是定性评价，正确的答案并不知道。系统学习的难度势必增大，学 习时间也会增长。因此，如何提高强化学习速度是一个最重要的研究问题。 强化学习目前研究的热点包括：强化学习与其他学习方法相结合、函数估计、 非马氏决策过程中新型强化学习算法、建立经验模型来加速学习、连续状态和连 续动作问题、部分可观察马尔可夫决策过程p o m d p ( 即不完全感知问题) 、强化 学习算法的规则抽取、从延迟的强化中学习、探索与利用的折衷、泛化和层次化 方法的研究、结构信度分配、多a g e n t 强化学习算法研究、关系强化学习、以及 如何把强化学习算法应用到实际问题中等等。 3 2 多a g e n t 强化学习 随着a g e n t 技术的发展，应用分布式算法实现多a g e n t 间的分工、协作逐渐 成为研究的热点，同时也促进了分布式人工智能的发展以及应用，推动了m a r l 的研究。最初人们把应用于单a g e n t 的强化学习算法应用到多a g e n t 系统中，但 是效果都不是很理想。主要原因是传统的单a g e n t 强化学习方法中的每个a g e n t 所处的环境都是马尔科夫决策过程，在马尔科夫决策过程中，环境状态的转移是 由与时间无关的转移概率函数决定的；而在多a g e n t 系统中，每个a g e n t 将不断 地改变动作，当环境包括其它a g e n t 动作时，转移概率函数就将成为与时间有关 的函数，因此需要新的理论框架。m a r l 的研究也因此受到了学术界的广泛关注， 成为强化学习研究中非常重要的研究方向之一。 3 2 1m a r l 方法及其发展 m a r l 分为集中式强化学习和分布式强化学习“。集中式强化学习就是将整 个多a g e n t 系统的协作机制( 多个a g e n t 为同一个目标而协同工作) 看成学习目 的，有一个全局性的中央学习单元协调多个a g e n t 的合作。那么，学习单元需要 整个多a g e n t 系统的状态作为输入，把对各个a g e n t 的动作指派作为输出，学习 算法就用标准的强化学习。这种多a g e n t 系统中的各个a g e n t 只是执行学习的结 果，并不具有学习能力；分布式强化学习就是每个a g e n t 都是学习的主体，学习 分为对环境响应策略的学习和对多个a g e n t 相互之间协作策略的学习。 分布式强化学习又分为独立强化学习和群体强化学习。独立强化学习中，每 个a g e n t 采用单a g e n t 的强化学习方法，把其他a g e n t 的状态和动作作为本a g e n t 的外部环境来处理，以自我为中心，a g e n t 间的协作只能通过通信来完成，通过通 信共享状态信息和强化信号。缺点就是不易达到最优目标且学习时间长；群体强 化学习将所有的a g e n t 状态和动作看作组合状态或组合动作，每个a g e n t 都必须 考虑其他a g e n t 的状态，在选择动作的时候都必须考虑其他a g e n t 将要执行的动 作。缺点就是状态空间和动作空间庞大，需要花费大量的学习时间，因此只用于 a g e n t 很少且问题较简单的情况。 w e i s s 和d i l l e n b o u r g ”将多a g e n t 学习方法分成三类：乘积( m u l t i p l i c a t i o n ) 形式、 分割( d i v i s i o n ) 形式和交互( i n t e r a c t i o n ) 形式。这种分类方法要么将多a g e n t 系统作 为一个可计算的学习a g e n t ；要么是每个a g e n t 都有独立的强化学习机制，通过与 其他a g e n t 适当交互、合作学习加快学习过程。该算法称为交互强化学习 ( i n t e r a c t i v er l ) ；而每个a g e n t 拥有独立的学习机制，并不与其他a g e n t 交互的强 化学习算法称之为并发独立强化学习c i r l ( c o n c u 盯e n ti s o l a t e dr l ) ，该算法只能够 应用在合作多a g e n t 系统，并只在某些环境中优于单a g e n t 强化学习。但该分类 并不能覆盖当前多a g e n t 强化学习的大部分研究内容，且该分类方法是针对一般 的多a g e n t 系统学习而言的，不便于从强化学习的角度分析问题。 ； 高阳等针对m a r l 方法，在a g e n t 学习领域，根据环境的不同，可以给出如 表3 3 所示的三种主要的m a r l 方法：合作m a r l ( 包括共享状态经验策略建 议等方法) 、基于平衡解对策的m a r l ( 包括m i n i m a x q 、n a s h q 、c e q 、w 6 l f 等方法) 和最佳响应m a r l ( 包括p h c 、i g a 、g i g a 、g i g a w o l f 等方法) 。 m a r l 研究较多的是非合作强化学习算法，本文主要是对合作多a g e n t 的强 化学习进行探讨。研究合作多a g e n t 的学习就是利用多个学习a g e n t 的相互协作、 交互、通信等完成复杂的任务。 ： 表3 3m a r l 的三种类型 问题空间主要方法算法准则 交换状态 ，1 交换经验 合作m a r l分布、同构、合作环境提高学习收敛速度 交换策略 交换建议 极小极大- q 基于平衡解同构或异构、合作或竞 n a s h - q 理性和收敛性 m a r l争环境 c e - q w r o l f p h c 最佳响应i g a 异构、竞争环境收敛性和不遗憾性 m a r lg l g a g i g a w o l f 3 2 2 合作m a r l 一 多a g e n t 合作学习是指多个a g e n t 在追求一个共同的目标过程中彼此相互通 信、合作，通过交换信息影响其它a g e n t 的学习，通过共享信息选择最优策略。 合作m a r l ( c o o p e r a t i v em u l t i a g e n tr e i n f o r c e m e n tl e a r n i n g ) 方法更多地是强 调如何利用分布式强化学习来提高强化学习的学习速度，其基本思想在于：在 a g e n t 进行动作选择前，相互交互，共享信息，产生更新后的值函数，而动作的选 择基于新的值函数。学术界关于合作强化学习的研究较少，还没有完整的理论。 t a n 于1 9 9 3 年以追捕问题为研究背景，研究了a g e n t 之间以通信为合作方式 的m a r l 问题。他提出在合作的多a g e n t 环境下采用三种合作强化学习的方式， 即共享环境状态信息、共享策略和共享阶段性经验。这些方法可以减少所需的训 练样例，加快学习过程，还可以最大程度地避免各自为战进行无谓探索的现象。 共享感知是指一个具有学习能力a g e n t 和一个不具有学习能力但感知能力很强的 a g e n t 协同工作，两个a g e n t 共享所感知的信息。这样可以提高任务完成的速度， 但是在状态信息量大的时候会导致很高的通信量，且容易导致状态空间的膨胀； 共享策略是指由一个a g e n t 维护所学到的策略，另一个a g e n t 每走完一步之后将 其有关感知和奖赏的信息传递给前一个a g e n t 统一进行维护，前一个a g e n t 将学 习所得到的策略给后一个a g e n t 共享。共享经验是指一个a g e n t 维护所学到的策 略，且共享另一个a g e n t 所经历的事件，这样即便自己经历的事件不多，却可以 把另一个a g e n t 所经历的事件同样作为学习的依据，就好像自己曾经经历过一样。 t a l l 给出的实验结果表明多个a g e n t 的整体工作效果在采用这三种协同强化学习方 法时都要优于没有采用该方法时的情况。不过，这三种协作强化学习方法的共同 之处在于系统中每个时刻只有一个a g e n t 在学习，其余a g e n t 辅助其学习。 中国科学技术大学的蔡庆生和张波n 引以q 1 e a r n i n g 算法为基础，于2 0 0 0 年提 出了一种基于a g e n t 团队的强化学习模型。该模型最大特点是引入主导a g e n t 的 角色作为团队学习的主角，并通过a g e n t 角色的变化实现整个团队的学习。作者 把该模型应用于机器人足球。实际上该模型只有主导a g e n t 承担学习任务，即每 次同时最多只有一个a g e n t 在学习。 i r w i g 1 将t d ( 0 ) 算法和q - , l e a r n i n g 算法应用到t i l e w o r d 领域，提出了一种促进 a g e n t 学习协作动作的替代强化方法，即a g e n t 采取动作所得到的回报，不应该只 考虑得到直接回报，还应该考虑其它a g e n t 的回报，该动作的真正回报应该是自 己的回报和其它a g e n t 回报的加权和。 合作m a r l 适用于多a g e n t 合作的情况，其研究还仅处于初步的探索阶段， 尚未形成比较完整的方法学和成熟的理论。本文中主要针对合作多a g e n t 强化学 习进行研究。 3 2 3 基于对策或平衡解的m a r l 单a g e n t 强化学习的马尔可夫决策过程模型扩展为多a g e n t 系统的随机对策 模型或者称之为马尔可夫对策模型，我们称这种形式的m a r l 为基于对策平衡解 的m a r l ( g a m e e q u i l i b r i u m b a s e dm u l t i a g e n tr e i n f o , r c e m e n tl e a r n i ng ) 。它是m a r l 研究较多的，其基本思路是基于马尔可夫对策框架对学习过程进行模型化，再利 用已有的强化学习算法，如q 1 e a r n i n g ，进行学习。 对策m a r l 方法以对策论为基础，学习算法必须满足两个性质理性和收 敛性，前者说明当其它a g e n t 采用固定策略时，对策m a r l 算法应能够收敛到最 优策略，而后者强调当所有a g e n t 都采用m a r l 算法时，算法必然收敛到稳定策 略，而不能出现振荡现象。对策m a r l 方法的基本思想在于：在a g e n t 进行动作 选择时，选择动作不再仅仅依赖自身的值函数，而必须同时考虑其它a g e n t 的值 函数，选择的动作是在当前所有a g e n t 值函数下的某种对策平衡解。 研究人员将对策论与m d p 相结合构建了一个适用于交互式多a g e n t 学习的理 论框架马尔可夫对策，并在此基础上提出了多种多a g e n t 强化学习算法。通 常都使用马尔科夫对策来模型化非协同多a g e n t 的学习过程。 ， 定义3 5 马尔科夫对策“们 假定在时刻点t = t i ，t 29 * * * g t b ，处观察系统，一个有刀个a g e n t 的马尔可夫对策 模型用五元组( 刀，墨a ，zr ) 表示。其中 刀是参与对策的智能体的个数； s 是系统的状态空间； 彳是刀个智能体的动作空间似，4 疗) ，彳，是智能体f 的可选动作空间； t ：s x4 x4 寸p d ( s ) 是当前状态下采取组合动作环境转移到下一个状态 的状态转移函数，p d ( s ) 说明了当前状态下采取组合动作使环境转移到下一个状态 的概率； r ：s x 4 4 t 专孵表示智能体f 的奖赏函数。 马尔可夫对策中的智能体的目标是在每个状态摹学习到一个能最大化长期奖 赏的最优策略。智能体f 的策略万是一个定义了在具体状态下动作选择概率的映 射。通常，s x a 哼【0 ，1 】，并且对于任意的s s ，有s x a 一【o r l 】。 。 在给定的状态s 下，所有的智能体独立选择动作a i ，a - ，并接受奖赏 ，。( s ，口，a ”) ，扛1 , - - , n 。然后状态基于转移概率转移到下一个状态s ，并且转移 概率满足，k s p ( ，i s ，口1 ，口一) = l 的限制。在折扣的马尔可夫对策中，智能体的目