（计算机应用技术专业论文）结合围捕问题的合作多智能体强化学习研究.pdf

结合围捕问题的合作多智能体强化学习研究 摘要 机器学习一直是a i 领域的研究热点。作为应用广泛的一种机器学习方 法，强化学习在单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 学习研究较少，关键问题在于两方面。一方 面是目标函数的选择和计算，另一方面是学习过程中的决策协调，二者都在 很大程度上影响着学习的效果。在理性合作情况下，提出利用p a r e t o 占优解 作为目标函数进行学习，它可以在提高个体理性的同时增加整体理性。为了 减小学习过程中用于协调的时间费用和通信费用，而且不影响学习的速度， 提出利用社会规则的方法完成学习过程中的隐式协调。制定的一系列互利性 社会规则实现了多a g e n t 系统决策的统一和较高的整体性能。 采用追捕逃跑任务作为完全合作多a g e n t 学习的应用研究背景。构建一 哈尔滨工程大学博士学位论文 个连续空间的追捕逃跑系统，实现搜索、围捕、押送等任务，并在围捕任务 中提出了一种编队方法，它可以在竞标合作的方式下降低路径总消耗。将先 验知识的强化学习用于围捕机器人行为融合机制中，弥补了规则设计的不完 整性，实现了灵活有效的行为规则。 设计了一个追捕逃跑仿真系统，对各任务阶段进行了仿真，并对行为融 合的性能作了比较说明，实验结果表明机器人部队可以在障碍物相对密集的 环境下灵活调整队形，快速包围并成功押送目标机器人。 关键词：多a g e n t 强化学习；随机对策：多机器人；追捕，逃跑任务 结合围捕问题的合作多智能体强化学习研究 a b s t r a c t a m o n gt h em e t h o d so fm a c h i n el e a r n i n g ，t h er e i n f o r c e m e n tl e a r n i n gi st h e m o s tp o p u l a r , w h i c hh a ss u c c e e d e di ns i n g l ea g e n ts y s t e m t o d a y sw o r k sa r e f o c u s e do nt h e l e a r n i n gi nm u l t i a g e n ts y s t e m ，w h e r et h ec o m p l e x i t y a n d u n c e r t a i n t ym a k et h el e a r n i n gm o r ed i f f i c u l t g a m et h e o r yi s t h ef r a m e w o r kt o i n v e s t i g a t et h ei n t e r a c t i o no fs e v e r a lp l a y e r s w h e nc o m b i n e dw i t ht h em a r k o v d e c i s i o np r o c e s s ，i tp r o v i d e san e wf o r m a l i z a t i o ns u i t a b l ef o rm u l t i a g e n ts y s t e m t h a ti ss t o c h a s t i cg a m ec o n c e r n i n gt h ei n t e r a c t i v el e a r n i n gs y s t e mo f m u l t i a g e n t t h e r eh a v eb e e nm a n yw o r k si nt h i sf i e l d ，w h i c ha r el e a r n i n gi na d v e r s a r i a l s y s t e m ，n o n c o o p e r a t i o ns y s t e m ，f u l l c o o p e r a t i o ns y s t e ma n dr e p e a t e dg a m e r e s p e c t i v e l y t h el e a r n i n g m e t h o d si n f u l l c o o p e r a t i o ns y s t e m a n d r a t i o n a l c o o p e r a t i o ns y s t e ma r ec o n s i d e r e dh e r e i nt h ef u l l c o o p e r a t i o ns y s t e m ，t h el e a r n i n gm e t h o do fs i n g l ea g e n ti sa d o p t e d t h eb i a st e c h n o l o g ya n di n f o r m a t i o ns h a r ea r ec o n s i d e r e df u r t h e rt os p e e du pt h e l e a r n i n g ，a n dap o l i c y s h a r e dl e a r n i n gm e t h o db a s e do nt h ep r i o r - k n o w l e d g ei s p r o m p t e d 一 b e s i d e st h ea l g o r i t h m ，t h en e u r a ln e t w o r kr e a l i z i n gt h el e a r n i n gi sa l s o i m p o r t a n tf o ri t sp e r f o r m a n c eo fs p e e da n dc o n v e r g e n c e b pi so d eo ft h em o s t p o p u l a rt r a i n i n gm e t h o d sf o rm u l t i l a y e rn e u r a ln e t w o r k b u tt h e r es t i l la r es o m e u n s o l v e dp r o b l e m s ，s u c ha st h et r a i n i n gr e s u l tb e i n gi n f l u e n c e db yt h eo r d e ro f s a m p l e s ，l o c a lo p t i m i z a t i o na n dt h es l o wl e a r n i n gs p e e de t c am e t h o du s i n g c o o p e r a t i v ep a r t i c l es w a r m so p t i m i z a t i o ni sp r o p o s e dt or e p l a c et h eb pm e t h o d ，s o a st oo p t i m i z et h ew e i g h t so f n e t w o r kq u i c k l ya n dg l o b a l l y t h ew o r k so nr a t i o n a l - c o o p e r a t i o ns y s t e ma r en o ts om a n y , t h ec r i t i c a l t e c h n i q u e s d i s c u s s e dh e r ec o n t a i nt w oa s p e c t s o n ei st h es e l e c t i o na n d c o m p u t a t i o no fo b j e c t i v ef i m c t i o nt ob el e a r n e d ，a n dt h eo t h e ri st h ec o o r d i n a t i o n 哈尔滨工程大学1 尊士学位论文 o fd e c i s i o nm a k i n gd u r i n gl e a r n i n g t h e s et w op r o b l e m sa r eb o t hi m p o r t a n tf o r t h el e a r n i n go ft h es y s t e m p a r e t oo p t i m u mi st a k e na st h eo b j e c t i v ef u n c t i o no f r a t i o n a la g e n t s l e a r n i n g ，w h i c hw o u l di n c r e a s et h eb e n e f i to fi n d i v i d u a lw i t h o u t d e c r e a s i n gt h a to ft h eg r o u p as e r i e s o fs o c i a lc o n v e n t i o n sa r ec o m p i l e dt o c o o r d i n a t et h ep o l i c yd e c i s i o no fa l la g e n t sw i t h o u tc o m m u n i c a t i o n ，w h i c hw i l l a l s os a v et h en e g o t i a t i o nt i m ei nt h ep r o c e s so fl e a r n i n g t h i si sn o tb a df o rt h e l e a r n i n gs p e e da ta l l ，b u ti sr e a l l yg o o df o r t h ec o n v e r g e n c e t h ea p p l i c a t i o no fl e a r n i n gi nf u l l c o o p e r a t i o ns y s t e mp r o c e e d si nt h e “p u r s u i t e v a s i o n g a m e a no p t i m a lm e t h o do ff o r m a t i o ni sp r o m p t e df o rt h e p u r s u i n gg r o u p w h i c hc a u s e st h el e a s tt o t a lc o s t t 1 1 er e i n f o r c e m e n tl e a r n i n g b a s e do np r i o r - k n o w l e d g ei su s e dt of u s et h eb a s i ca c t i o n so fr o b o t ，s oa st o r e a l i z et h eb e h a v i o rc o n t r 0 1 t h i sm a k e su pt h el l n k n o w na n de r r o rd o m a i no f d e s i g n e dr u l e s ，a n dm a k e st h er o b o tm o v ef l e x i b l y as i m u l a t i o ns y s t e mi sb u i l tt o d e m o n s t r a t et h ep e r f o r m a n c eo f d i s c u s s e da l g o r i t h m s k e y w o r d s ：m u l t i a g e n t r e i n f o r c e m e n t l e a r n i n g ； s t o c h a s t i c g a m e s ； m u l t i r o b o t i c s ；“p u r s _ ! a i t - e v a s i o n g a m e s 第1 章绪论 萱i i i i i i i i i i 篁宣i i i 萱i i i 高i i i 誓i i i 1 1 i 1 1 i i 宣莓i i i i 第1 章绪论 1 1 引言 多a g e n t 学习是一个很必要却又很富有挑战性的问题，因为多a g e n t 系统 越来越流行，且环境变得越来越动态化。“结合围捕问题的多智能体学习算法 研究”这一课题所涉及的主要技术领域包括强化学习( r e i n f o r c e m e n t l e a r n i n g ) 、多a g e n t 学习( m u l t i - a g e n tl e a r n i n g ) 和追捕- 逃跑游戏 ( p u r s u i t - e v a s i o ng a m e s ，p e g ) 强化学习是一种应用广泛的机器学习方法，学习器可以通过“交互试错” 白适应于动态未知的环境。目前它已经应用到了制造过程控制、任务调度、 机器人和游戏等各个领域。随着单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 k o v 决策过程( m a r k o vd e c i s i o np r o c e s s ) 。通常的做法是将整个系统看作一 个整体，对系统的联合动作进行分析，联合动作导致环境发生转移，该转移 对系统而言就仍然满足m a r k o v 特性。每个状态下的系统内部格局对各a g e n t 而苦又形成一个阶段对策( s t a g eg a m e ) ，从而形成了分析分布式a g e n t 学习时 的随机对策( s t o c h a s t i cg a m e ，s o ) 框架。 随机对策是近几年兴起的一个用于研究多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 i 研究者追随的一个热门话题。 多机器人任务的研究平台很多，如编队、机器人足球及追捕- 逃跑游戏等。 其中，编队侧重的是团队的合作，不涉及对抗关系；机器人足球涉及到合作 和对抗的关系，但游戏本身的规则很多，增加了问题的复杂性；追捕一逃跑游 戏中涉及到同类机器人的合作及“猎物”与“追捕者”间的对抗，且游戏本 身的规则约束少。它的这些特点使其对多机器人学习系统的研究比较直接便 利，在问题的说明上具有代表性，且具有很大的研究空间。该任务在实际中 的应用可以扩展到海上搜救、灾难现场勘查以及多种军事任务中，所以对追 捕逃跑问题的研究本身具有很好的实用价值。另外，选择追捕一逃跑作为多 a g e n t 学习算法在多机器人系统中的应用平台，具有很重要的实际意义。 1 2 多a g e n t 学习 多a g e n t 强化学习机制被广泛应用到各个领域，例如游戏1 2 3 i 、邮件路 由选择h l 、口语对话系统5 1 以及机器人足球等等。对多a g e n t 学习进行研究 时要考虑一个很重要的问题，就是a g e n t 间为什么要交互? 为了回答这个问题，并理论分析多a g e n t 系统中的交互作用，我们借助 于对策论( g a m et h e o r y ) 这一数学工具对多a g e n t 强化学习进行进一步分析。 在对策模型中，每个a g e n t 获得的瞬时奖惩不仅仅取决于自身的动作，同时 还依赖于其他a g e n t 的动作。因此，可以将多a g e n t 系统中每个离散状态s 形 式化为一个对策g 。那么强化学习的马尔可夫决策模型扩展为多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 研究内容 1 2 1 1 完全合作型多a g e n t 强化学习 在完全合作型多a g e n t 强化学习中，由于在任意离散状态，马尔可夫对 策的联合奖赏函数尼对每个a g e n t 来说是一致的、相等的。因此，每个a g e n t 第1 章绪论 最大化自身期望折扣奖赏和的目标与整个多a g e n t 系统的目标是一致的。在 这种情况下，可以直接应用单a g e n t 强化学习的方法，并利用多a g e n t 系统本 身的优势对算法做适当的改善。 1 2 1 2 对抗型多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 和对手a g e n t b 。图1 1 给出两个a g e n t 系统中某一状态下的对策 模型。显然该模型满足零和对策的定义：在任何策略下所有a g e n t 的奖赏和 为0 。 a g e n t b 抚如 6 i( 1 ，一1 )( 4 ，- 4 ) a g e n t a a 2 ( 2 , - 2 ) ( 3 ，- 3 ) 图1 1 两个a g e n t 零和对策模型 f i g 。1 。1t h ez e r o s h i l lg a m em o d e li nt w oa g e n t ss y s t e m 由于a g e n t a 的奖赏值同时取决于自身的动作和a g e n t b 的动作，因此传 统单a g e n t 强化学习算法在对抗型多a g e n t 强化学习中不适用。解决这一问题 最简单的方法是采用极小极大q 算法( m i n i m a x - q ) ：在每个状态s ，a g e n t a 的最优策略就是选择可以使自己最小奖赏最大的动作。 显然，如果将马尔可夫对策中每个状态都形式化为如图1 1 的零和对策 模型，那么极小极大q 算法可以发现最优的策略。 1 2 1 3 非合作型多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 系统中离散状态s 只能形式化为非零和对策。 一个典型事例是图】2 表示的囚犯两难问题。对于不存在交流和约定的多 a g e n t 系统，其对策的最优解即对策的n a s h 平衡解。所以图1 2 情况的最优 解为( 一9 ，一9 ) 。 哈尔滨工程大学博士学位论文 a g e n t b b 1 b 2 口1 ( 9 , - 9 )( 0 , - 1 0 ) a g e n t a d t 2( 一1 0 ，0 )( - 1 ，一1 ) 图1 2 两个a g e n t 非零和对策模型 f i g 1 2t h eg e n e r a l s u mg a m em o d e li nt w oa g e n t ss y s t e m 1 2 1 4 理性合作多a g e n t 强化学习 针对图1 2 所示的事例，由于非合作多a g e n t 间不能进行协商，也就无法 实现一个互利基础上的最优解( 一l ，1 ) 。如果允许a g e n t 间进行交流并制定一定 的约束从而形成一定意义上的联盟结构，则从长远利益考虑，每个a g e n t 都 会坚持选择合作解( 1 ，1 ) 。 非零和对策模型更能反映多a g e n t 系统中个体理性( i n d i v i d u a l r a t i o n a l i t y ) 与集体理性( g r o u pr a t i o n a l i t y ) 冲突的本质。所以对于该对策 类型下的多a g e n t 学习算法的研究就显得尤为重要。 1 2 2 研究现状 依据研究的侧重点及随机对策中状态空间的不同，可以将随机对策中的 学习分为m a r k o v 随机对策学习和重复对策学习。m a r k o v 随机对策学习的核 心是对策解的学习，即a g e n t 精确学习每个对策形势下的对策解，每次的策 略选择都是为了最大化对策解的期望值；而重复对策学习的核心则是最好回 应，即不直接搜索学习对策解，而是精确学习对其他a g e n t 策略的最好回应， 并最终达到一个策略或回报上的对策解。 1 2 2 1m a r k o v 随机对策形式 近年来，i c m l ( i n t e m a t i o n a lc o n f e r e n c eo nm a c h i n el e a r n i n g ) 已经成为对 策解学习器研究中相关论文的集中处，l i t t r n a n i 4 1 介绍了一种q 学习算法称为 m i n i m a x q 算法，用于两人0 和对策中；l i t t m a n 和s z e p e s v a r i i 儿证明了 m i n i m a x q 算法收敛于对策论中的最优值；h ua n dw e l l m a n i 描述了一个 m i n i m a x q 的扩展算法，称为n a s h q ，通过在学习规则中加入n a s h 平衡， 使该算法扩展到了般和对策中；b o w l i n g 1 2 1 3 1 阐明了算法的收敛条件；h u a n dw e l l m a n 1 4 1 研究了在几个小的、很有用的环境中n a s h q 的收敛行为； 4 第1 章绪论 l i t t m a n f b i 针对收敛问题提出了一种区分敌我的f r i e n d o r - f o eq 学习算法； g r e e n w a l de ta l ，提出了一种c o r r e l a t e d q 学习算法。至此，大多的研究都集 中到了一般和对策中学习的理性和收敛性问题上。 1 2 2 2 重复对策形式 重复对策中的学习根据对手情况的不同，通常可以分为基于信任的重复 对策中的学习1 1 3 l 胁2 0 】，以及带有欺骗和威胁的重复对策中的学习i ：2 【1 i 。 在基于信任的学习中，r o b i n s o n 2 3 1 和b r o w n 2 4 1 曾提出过一个“f i c t i t i o u s 口l a v ”方法，k a l a i 也提出了一种“理性学习”1 2 6 1 。但是很多学者f 3 3 说明 该方法一般情况下不收敛。最近比较流行的是策略梯度方法，该方法不对其 他局中人作假设，而是通过迭代的策略梯度上升求得收敛于n a s h 平衡的最优 策略。这方面的代表性作品主要包括文献 18 】、文献 3 2 】以及文献 3 5 1 。在这 些算法中，若学习最好响应的算法在相互比赛时收敛了，那收敛点一定是一 个n a s h 平衡 3 5 1 。 在带有欺骗的学习中，l i t t m a n 2 0 给出了一种用来计算n a s h 平衡策略的 多项式级算法，给出了互利情况下，为了保证合作对背叛行为惩罚次数的计 算，以及非互利情况下n a s h 平衡的计算。但它过于依赖于平均回报标准，不 能够适用于有穷视线的对策及无穷视线的折扣回报对策中。 除了q 学习外，s a r s a i 强1 算法在多a g e n t 系统中的扩展也有少量的研究。 离线算法q 一学习的收敛目标是最优策略的q 值，而在线算法s a r s a 的收敛 目标则是当前策略的最优q ，值。b a n e r j e ee ta 1 设计了m i n i m a x s a r s a t 3 1 1 算 法，用于0 和随机对策中的学习。s t o n e 和s u t t o n 利用s m d ps a r s a ( a ) r 硐 算法学习多机器人系统的高层决策。3 8 提出了基于s a r s a 的多a g e n t e x o r l 算法，通过特定情况下取消n a s h 平衡计算和加入启发式算法简化了 学习的更新过程。多a g e n ts a r s a 算法在一般和对策中同样存在解选择的问 题，另外，因为同步学习中无法预知其他a g e n t 的动作，它对a g e n t 观察能力 的假设也不容易实现。多a g e n ts a r s a 算法还具有一个共同的开放性问题， 即“s a r s a ( 九) 是否收敛”，这仍未得到可靠的证明【2 5 1 。除此之外，m o r a l e s 提出r q 算法 3 9 用于处理多a g e n t 系统中的大规模搜索空间的问题，但很难预 定义其r _ s t a t e 集和r a c t i o n 集，且不能保证找到最优解【2 5 。还有很多学者通 哈尔滨二r 程大学博士学位论文 过学 - j 分类系统、加权策略共5 1 4 1 1 方式来研究多a g e n t 的学习等。 对策论的发展是循着从零和到非零和、完全信息到非完全信息、静态到 动态的方向进行的。所以，该框架下的多a g e n t 学习研究也已涉及到了非完 全信息对策中的b a y e s i a n - n a s h 平衡学习【42 ”1 等问题。 国内学者们对于多a g e n t 学习也作了很多的研究，主要集中于南京大学 的计算机软件新技术国家重点实验室和清华大学计算机系两大机构。南京大 学的高阳等人就曾利用元对策研究多a g e n t 问的学习j ，王立春等利用h u j u n l i n gn a s h - q 算法的思想研究了a o d e 中多a g e n t 的协商问题【4 ”，清华大 学石纯一等研究将拍卖方法引入多a g e n t 系统的协商中【4 6 l ，另外，西南师范 大学的张虹等利用在多a g e n t 学习中引入可信第三方的方法研究了对策的协 商问题【4 ”，等等。 1 2 3 存在的问题及解决方案 多a g e n t 学习领域目前仍然存在的问题咀及研究的热点主要集中于以下 几个方面： 1 ) 加快学习速度 学习速度慢在单a g e n t 领域已经是一个很明显的问题，在多a g e n t 系统中 则更为突出，尤其是需要对其他a g e n t 建模时，时间复杂度会随a g e n t 的数量 成指数倍增加【2 1 1 。这严重限制了多a g e n t 学习在实际中应用，迫切要求加快 学习的速度。梯度法、嵌入先验知识、模糊学习、状态空间划分、分层学习 等现有加速算法对特定任务背景依赖性很强，而且都是针对单a g e n t 学习的 1 4 8 1 。b r a f m a n 和b a n e r j e ee ta l 。对零和随机对策的加速学习做了初步的探 索，但仍缺乏一般和随机对策中的有效加速算法。 2 ) 减小空间需求 复杂的任务、动态连续的环境和对其他a g e n t 的预测都急剧地膨胀着多 a g e n t 学习的空间需求。连续空间的表示一直是实际应用中的巨大障碍，- - l o e 解决方法是对状态和动作进行抽象，包括条件和行为提取、成员内部建模、 关系一状态估计及状态向量量子化【2 ”。但所有的这些都可以看作是单a g e n t 学 习的变体，因为它将其他a g e n t 建模成环境中一部分或使用固定策略，而对 第1 苹绪论 于其他白适应a g e n t 的情况，尚需继续研究。使用抽象算法后的收敛性说明 仍没有令人满意的结果。另外，函数逼近和泛化方法也可用来减小空间需求 1 5 0 1 ，但逼近和泛化本身的不确定性为学习的收敛增加了一定的困难，需要进 一步优化。 3 ) 平衡解的计算 n a s h 平衡是多a g e n t 学习中的一个重要解概念，对策论提供了几种计算 方法，如划线法和l e m k e h o w s o n 算法等，但是其计算复杂度很大。很多学 者试图利用学习来计算平衡解，m u k h e r j e e 和s e n 提出a g e n t 通过交替或同时 揭示行动的方式来学习实现p a r e t o 最优解15 1 1 。v e r b e e c k 等提出a g e n t 不断寻 找并保留对策中的最大n a s h 平衡点，从而最终实现p a r e t on a s h 平衡【5 “。但 是，利用学习计算平衡解时，计算复杂度也是潜在的问题，因为学习复杂度 本身还没有定量给出。多a g e n t 系统中快速有效地获得平衡解的问题，正被 多个研究领域共同关注。 4 ) 平衡解的选择 存在多个对策平衡解的时候，如何保证所有a g e n t 选择统一的解向量从 而实现最优的联合动作，并保证最终的学习收敛，对于多a g e n t 的学习效果 很重要1 2 5j 。f f q 中a g e n t 需要告知对方是敌是友再选择解，这受到一些研究 者的质疑，他们认为这与a g e n t 的自主性要求相悖。n a s h q 的实验中利用 特定的求解方法来约束解的选择，规定所有a g e n t 都选择l e m k e h o w s o n 算 法求得的第一个平衡解，这实际上相当于在系统中作了强制性的约定，而且 它也不能保证选到p a r e t on a s h 平衡解。因此，如何在保证a g e n t 自主性的同 时使他们选择统一的平衡解，又不花费太长的协商时间，是目前大多数多 a g e n t 学习研究者所关心的问题。 5 ) 信度分配 前面介绍的工作主要集中于状态值的确定，而在合作的多a g e n t 系统中， 如何分配强化信号，即信度分配问题，也同样需要关注。已有的桶群算法比 较常用，另外一些针对模块化学习系统的算法和针对分类器系统的算法都在 一定程度上解决了信度分配m 题，但他们都不是根据a g e n t 对任务的贡献来 哈尔滨t 程大学博士学位论文 分配的，而是根据他们以往收到的强化值折扣或其它类似指标进行分配。这 种方法显然不公平，它容易使得偶然体现出高性能的a g e n t 不断获得大的强 化值份额，个体过于突出1 4 刖。较合理的分配方式在对策论中有相应的研究， s h a p l e y 值是一个较成熟的利益分配方式口3 1 ，可以考虑在该方向中做进一步 的探索。 6 ) 联盟的形成 多个a g e n t 如何针对不同的任务自主结成联盟或达成合作协议，实现统 一的目标且防止利益之争，这对任务的完成效率非常重要。已有的拍卖、平 衡、投机和打工等形式5 4 i ，先将任务分解，然后按照不同的标准选择参与a g e n t 并分配给它们相应的任务，从而形成一个具有约束力的联合体。【5 5 】利用联 合承诺构造联盟，但容易使某些优势个体发展过快，错过最好的组合方式。 如何选择a g e n t 形成相应的联盟，联盟形成之后，如何实现利益划分、设定 惩罚机制防止成员背叛05 , 2 0 】及根据任务状态解散联盟，这都是目前需要进一 步研究的细节问题。 7 ) 协调机制 合作多a g e n t 的学习系统中通常需要引入协调机制使成员的选择保持一 致，常用的有基于常规( 社会法则) 的协调和基于通讯的协调1 5 6 1 。社会规则 是在所有a g e n t 及其相关动作的完全排序都己知的条件下，采用各种不同的 方法对最优动作集合进行排序。它的缺点在于每个a g e n t 都必须事先知道所 有a g e n t 及其相关动作的排序，通常只适用于固定的场合。基于通讯的协调 是一种最自然的协调机制，a g e n t 之间通过相互传递各自的意图来进行协调。 但是它需要设计通讯和协商协议，不可避免的会发生通讯失败和错误解释等 问题，且过多的通信时间会延迟学习的速度。所以，制定一套较通用的社会 规则或设计一种快速有效的通讯方式对于学习的效果和应用都有很大的作 用。 8 ) 不完全信息睛况 在不完全信息的对策中，a g e n t 无法获得对方的回报函数等信息，它需要 对状态进行预测，这就涉及到对预测状态的表示及计算 4 3 , 5 7 - 6 1 1 以及对自己行 第1 苹绪论 为影响的推测。c h a l k i a d a k i s 和b o u t i l i e r 提出多a g e n t 强化学习的b a y e s i a n 方法，a g e n t 利用先前的经历和b a y e s i a n 规则对系统模型信念及对手策略信 念进行推理，但完全的b a y e s i a n 更新需要很大的计算量。且从理论上看，在 学习中引入了不确定性，更增加了结果的不稳定性，关于这些方面仍然存在 很多问题需要进一步的挖掘和研究。 g ) 新收敛标准的选取 n a s h q 在算法的执行和最后所采用的收敛衡量标准都是n a s h 平衡解概 念。有的学者质疑n a s h 平衡在对策论中所起到的中心作用在a i 中是否仍然 成立。所以，一些新标准i t 6 l 的探索将为多a g e n t 学习的研究开辟新的发展道 路。 多a g e n t 学习作为多a g e n t 系统的重要研究内容之一，受n - l 越来越多的 重视。随着多a g e n t 经济的出现和发展，有效的多a g e n t 学习技术必将成为跨 学科的新研究领域。目前关于这方面的理论仍不够成熟，有待进一步的探索 研究。 1 3 追捕一逃跑问题 追捕一逃避问题来源于自然界食肉动物捕食猎物的行动，因此又称捕食者 一猎物问题( p r e d a t o rp r e yp r o b l e m ) ，它是研究分布式系统中多智能体合作 与协调的理想i ；q 题，而利用实际机器人研究追捕逃避的系统更是一个包括实 时视觉处理、无线通讯、多机器人控制与协作、实时动态路径规划等多学科、 多领域知识的多机器人分布式系统。在追捕问题中，猎物需要多个追捕者协 作才能捕获，而且涉及到追捕方和逃避方两个机器人群体的对抗。追捕过程 中局势是时刻变化的，每个机器人必须实时了解环境的动态变化，通过实时 知识处理对当前对抗格局的判断，及时做出变换角色、重新组队或编队等决 策。因此，追捕问题是被广泛关注但至今尚未解决的动态环境下实时知识处 理的典型问题，也是研究多智能体合作与协调策略和对抗策略进化的通用问 题。 哈尔滨工程大学博士学位论文 1 3 1 研究内容 人工智能学者利用追捕一逃跑问题对追捕逃避双方策略的竞争性协进化、 猎物的逃避行为6 2 1 、多智能体合作策略、多智能体通讯 6 3 , 6 4 等进行了大量的 研究。追捕逃跑问题的关键技术在军事、工业等方面也有着广泛的应用，如 机器人部队合作包围捕获入侵者6 6 1 和空战 6 7 - 7 0 1 1 等对抗领域都已经采用追 捕逃避问题来研究，此外，工件调度、交通运输管理、并行计算【7 1 1 等也已用 追捕逃避模型进行了研究。 根据研究目的不同，追捕一逃跑问题可实例化为不同的具体问题。如己知 环境中追捕重点研究双方的策略，而未知环境追捕还需同时识别并建立环境 的模型；再如单个追捕者和单个猎物的一对一追捕通常用来研究追捕逃避双 方策略的协进化 7 2 , 7 3 】与猎物的自适应逃跑策略74 1 ，而多个追捕者追捕单个或 多个猎物的追捕问题通常用来研究追捕者间的合作与协调机制。 追捕- 逃跑问题本质上是分布式m a s ( m u l t i a g e n ts y s t e m ) 协作决策问题， 通过研究多个追捕者的合作追捕策略研究机器人社会中智能体脚的竞争与合 作、合作与协调策略和最优合作决策机制及团队最优决策算法等，为此，需 要具体研究以下内容： ( 1 ) 通过多个追捕者组成团队捕获单个猎物的追捕问题，研究具有公共 目标的合作团队内部成员间的协调问题，给出智能体协调自身行为达到个体 和团队双重的最优的决策机制与协调算法。 ( 2 ) 设计最优的任务分配机制，追捕团队通过协商选出足够的、最合适 追捕者组织的追捕子团队，捕获动态出现的猎物。 ( 3 ) 针对环境与任务的动态性，设计相应的学习和自适应算法，使追捕 团队通过学习，最优捕获猎物的合作追捕策略。 1 3 2 研究现状 本文研究的追捕逃避问题指的是多追捕者组成团队围捕并驱逐一个需要 多个追捕者合作才能捕获的猎物的情况，由于该情况明确规定了追捕者问的 合作任务，因此从一开始就被m a s 学者广泛用来研究、比较、测试各类合 作机制和合作追捕算法f ”1 。 b e n d a 等人首先提出四个蓝智能体( p r e d a t o r ) 通过占据一个红智能体( p r e y ) 第l 章绪论 周围的四个相邻栅格包围并捕获猎物的单猎物合作追捕问题f 7 ”，该研究的目 的是评价几种合作与控制的算法的效率，效率指标是追捕者捕获猎物的次数。 但这种只允许水平或垂直运动的直角对策模型( o n h o g o n a lg a m e ) 仅是一种粗 略的离散化方案。k o r m 】用允许对角线方向运动的对角对策模型( d i a g o n a l g a m e ) 代替改进了这种直角近似方案，它提出的贪心法可控制多达8 个追捕 者合作追捕猎物。然而，在这两个模型中追捕者和逃避者轮流运动，回合制 的附加条件使追捕过程不能收敛到稳定状态，也不符合问题的实际情况。因 此，合理的模型必须让追捕者和逃避者同时运动。为了得到稳定收敛的控制 策略，h a y n e s 7 2 ，7 7 ，7 8 1 使用强类型遗传编程算法( s t g p ：s t r o n gt y p eg e n e p r o g r a m m i n g ) 自动生成并进化对抗双方的控制策略，但由于仅采用贪心法控 制，控制策略完全通过学习获得，且没有任何合作机制，未能得出预期的协 进化效果，连采用简单的直线逃避策略的猎物都无法捕获。fh o 7 q 】用复杂性 较低的概率爬山法方案控制多智能体在线学习合作策略，追捕团队能捕获逃 避的目标，但逃避者的速度仅为追捕者的9 0 ，处于人为劣势。n o r i h i k o 8 0 1 研究了局部视野的追捕者和逃避者同时运动时的追捕，但他同时假定逃避者 的速度或者视野小于追捕者，因此没有将逃避者放到与追捕者同等的位置。 此外，y a m a g u c h i 1 l 研究了保安机器入部队，它可在发现入侵者后依靠路标 等自动导航，通过合作编队将入侵者包围擒获，但目前仅针对静止目标研究 机器人部队的自适应队形控制。 除了上述环境信息己知的确定性理论追捕研究外，南加州大学和其 b e r k e l e y 分校的ss a s t r y 研究小组1 8 2 47 1 在美国海军部、空军部资助下研究未 知环境下具有不精确传感的多个空中和地面追捕者合作追捕地面上逃避者的 概率模型，重点研究追捕者在追捕的同时合作建立环境模型。 多猎物合作追捕的研究目前很少，且对合作的理解也不同。g r i n t o n f 8 8 j 利用承诺与公约合作机制研究了静止的需要不同数目的追捕者合作才能捕获 的多猎物追捕问题，重点研究多追捕者间相容承诺的生成算法，比较了不同 控制策略、通讯方案、追捕者数目等对追捕性能的影响。ki r w i g 和hb e r e n j i 等人提出了不同的合作概念，在他们研究的追捕问题( 更确切的说，是捕食 问题) 中，单个追捕者就可以捕获任意一个猎物，研究目的是追捕团队如何 协调才能使团队捕获的猎物总数最多，为了增加问题的难度，猎物在存在随 啥尔滨工程大学博士学位论