（計算機應用技術專業(yè)論文）結合圍捕問題的合作多智能體強化學習研究.pdf

結合圍捕問題的合作多智能體強化學習研究 摘要 機器學習一直是a i 領域的研究熱點。作為應用廣泛的一種機器學習方 法，強化學習在單a g e n t 情況下的研究己趨于成熟，而在多a g e n t 系統(tǒng)中的研 究仍處于上升階段，因為多a g e n t 系統(tǒng)本身的復雜性和動態(tài)不確定性增加了 對學習算法研究的困難。應用數學領域中研究多人交互的對策論理論，為多 a g e n t 系統(tǒng)中的學習算法的研究提供了一個很好的理論支撐。對策論與馬爾可 夫決策過程相結合便構建了一個用于研究交互式多a g e n t 學習的理論框架一 隨機對策。 在此框架下的學習研究已經取得了些成果，如對抗、非合作和完全合 作系統(tǒng)中的學習以及重復對策中的學習等。本文針對隨機對策框架下完全合 作和理性合作的多a g e n t 學習進行了研究。 完全合作的多a g e n t 系統(tǒng)中，在單a g e n t 學習算法的基礎上研究偏差技術， 并利用多a g e n t 系統(tǒng)的信息共享優(yōu)勢，提出了基于先驗知識的共享策略學習 算法。此外，用于實現學習的神經網絡性能也會直接影響學習結果。針對反 向傳播神經網絡收斂速度慢和易陷入局部最優(yōu)等缺陷，提出利用合作粒子群 優(yōu)化方法對網絡權值進行訓練。它可以實現快速全局優(yōu)化，改善網絡學習性 能從而有益于強化學習的效果。以上兩方面都對加快學習速度發(fā)揮了很好的 作用。 理性合作情況下的多a g e n t 學習研究較少，關鍵問題在于兩方面。一方 面是目標函數的選擇和計算，另一方面是學習過程中的決策協(xié)調，二者都在 很大程度上影響著學習的效果。在理性合作情況下，提出利用p a r e t o 占優(yōu)解 作為目標函數進行學習，它可以在提高個體理性的同時增加整體理性。為了 減小學習過程中用于協(xié)調的時間費用和通信費用，而且不影響學習的速度， 提出利用社會規(guī)則的方法完成學習過程中的隱式協(xié)調。制定的一系列互利性 社會規(guī)則實現了多a g e n t 系統(tǒng)決策的統(tǒng)一和較高的整體性能。 采用追捕逃跑任務作為完全合作多a g e n t 學習的應用研究背景。構建一 哈爾濱工程大學博士學位論文 個連續(xù)空間的追捕逃跑系統(tǒng)，實現搜索、圍捕、押送等任務，并在圍捕任務 中提出了一種編隊方法，它可以在競標合作的方式下降低路徑總消耗。將先 驗知識的強化學習用于圍捕機器人行為融合機制中，彌補了規(guī)則設計的不完 整性，實現了靈活有效的行為規(guī)則。 設計了一個追捕逃跑仿真系統(tǒng)，對各任務階段進行了仿真，并對行為融 合的性能作了比較說明，實驗結果表明機器人部隊可以在障礙物相對密集的 環(huán)境下靈活調整隊形，快速包圍并成功押送目標機器人。 關鍵詞：多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 學習是一個很必要卻又很富有挑戰(zhàn)性的問題，因為多a g e n t 系統(tǒng) 越來越流行，且環(huán)境變得越來越動態(tài)化。“結合圍捕問題的多智能體學習算法 研究”這一課題所涉及的主要技術領域包括強化學習( 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 ) 強化學習是一種應用廣泛的機器學習方法，學習器可以通過“交互試錯” 白適應于動態(tài)未知的環(huán)境。目前它已經應用到了制造過程控制、任務調度、 機器人和游戲等各個領域。隨著單a g e n t 學習研究的成功，多a g e n t 系統(tǒng)的學 習問題正成為近年來的研究重點。多a g e n t 任務環(huán)境下，個體的回報和環(huán)境 的轉移不再是只依賴于自身的行為，而是由所有a g e n t 的聯(lián)合行為決定，從 而環(huán)境對單個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 ) 。通常的做法是將整個系統(tǒng)看作一 個整體，對系統(tǒng)的聯(lián)合動作進行分析，聯(lián)合動作導致環(huán)境發(fā)生轉移，該轉移 對系統(tǒng)而言就仍然滿足m a r k o v 特性。每個狀態(tài)下的系統(tǒng)內部格局對各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 研究者追隨的一個熱門話題。 多機器人任務的研究平臺很多，如編隊、機器人足球及追捕- 逃跑游戲等。 其中，編隊側重的是團隊的合作，不涉及對抗關系；機器人足球涉及到合作 和對抗的關系，但游戲本身的規(guī)則很多，增加了問題的復雜性；追捕一逃跑游 戲中涉及到同類機器人的合作及“獵物”與“追捕者”間的對抗，且游戲本 身的規(guī)則約束少。它的這些特點使其對多機器人學習系統(tǒng)的研究比較直接便 利，在問題的說明上具有代表性，且具有很大的研究空間。該任務在實際中 的應用可以擴展到海上搜救、災難現場勘查以及多種軍事任務中，所以對追 捕逃跑問題的研究本身具有很好的實用價值。另外，選擇追捕一逃跑作為多 a g e n t 學習算法在多機器人系統(tǒng)中的應用平臺，具有很重要的實際意義。 1 2 多a g e n t 學習 多a g e n t 強化學習機制被廣泛應用到各個領域，例如游戲1 2 3 i 、郵件路 由選擇h l 、口語對話系統(tǒng)5 1 以及機器人足球等等。對多a g e n t 學習進行研究 時要考慮一個很重要的問題，就是a g e n t 間為什么要交互? 為了回答這個問題，并理論分析多a g e n t 系統(tǒng)中的交互作用，我們借助 于對策論( 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 系統(tǒng)中每個離散狀態(tài)s 形 式化為一個對策g 。那么強化學習的馬爾可夫決策模型擴展為多a g e n t 系統(tǒng)的 馬爾可夫對策模型。 根據學習過程中對策形式的不同，我們將多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 強化學習中，由于在任意離散狀態(tài)，馬爾可夫對 策的聯(lián)合獎賞函數尼對每個a g e n t 來說是一致的、相等的。因此，每個a g e n t 第1 章緒論 最大化自身期望折扣獎賞和的目標與整個多a g e n t 系統(tǒng)的目標是一致的。在 這種情況下，可以直接應用單a g e n t 強化學習的方法，并利用多a g e n t 系統(tǒng)本 身的優(yōu)勢對算法做適當的改善。 1 2 1 2 對抗型多a g e n t 強化學習 在對抗型多a g e n t 強化學習中，任意離散狀態(tài)下馬爾可夫對策的聯(lián)合獎 賞函數月，對每個a g e n t 來浼是互為相反的。因此每個a g e n t 自身目標與其他 a g e n t 的目標是完全相反的。為敘述方便，我們以兩個a g e n t 為例，即系統(tǒng)中 包含a g e n t a 和對手a g e n t b 。圖1 1 給出兩個a g e n t 系統(tǒng)中某一狀態(tài)下的對策 模型。顯然該模型滿足零和對策的定義：在任何策略下所有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 的動作，因此傳 統(tǒng)單a g e n t 強化學習算法在對抗型多a g e n t 強化學習中不適用。解決這一問題 最簡單的方法是采用極小極大q 算法( m i n i m a x - q ) ：在每個狀態(tài)s ，a g e n t a 的最優(yōu)策略就是選擇可以使自己最小獎賞最大的動作。 顯然，如果將馬爾可夫對策中每個狀態(tài)都形式化為如圖1 1 的零和對策 模型，那么極小極大q 算法可以發(fā)現最優(yōu)的策略。 1 2 1 3 非合作型多a g e n t 強化學習 在許多實際多a g e n t 系統(tǒng)中，往往單個a g e n t 的所得獎賞并不是其他a g e n t 所得獎賞和的負值，所以多a g e n t 系統(tǒng)中離散狀態(tài)s 只能形式化為非零和對策。 一個典型事例是圖】2 表示的囚犯兩難問題。對于不存在交流和約定的多 a g e n t 系統(tǒng)，其對策的最優(yōu)解即對策的n a s h 平衡解。所以圖1 2 情況的最優(yōu) 解為( 一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 間不能進行協(xié)商，也就無法 實現一個互利基礎上的最優(yōu)解( 一l ，1 ) 。如果允許a g e n t 間進行交流并制定一定 的約束從而形成一定意義上的聯(lián)盟結構，則從長遠利益考慮，每個a g e n t 都 會堅持選擇合作解( 1 ，1 ) 。 非零和對策模型更能反映多a g e n t 系統(tǒng)中個體理性( 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 研究現狀 依據研究的側重點及隨機對策中狀態(tài)空間的不同，可以將隨機對策中的 學習分為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 算法收斂于對策論中的最優(yōu)值；h ua n dw e l l m a n i 描述了一個 m i n i m a x q 的擴展算法，稱為n a s h q ，通過在學習規(guī)則中加入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 研究了在幾個小的、很有用的環(huán)境中n a s h q 的收斂行為； 4 第1 章緒論 l i t t m a n f b i 針對收斂問題提出了一種區(qū)分敵我的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 平衡的最優(yōu) 策略。這方面的代表性作品主要包括文獻 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 系統(tǒng)中的擴展也有少量的研究。 離線算法q 一學習的收斂目標是最優(yōu)策略的q 值，而在線算法s a r s a 的收斂 目標則是當前策略的最優(yōu)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 硐 算法學習多機器人系統(tǒng)的高層決策。3 8 提出了基于s a r s a 的多a g e n t e x o r l 算法，通過特定情況下取消n a s h 平衡計算和加入啟發(fā)式算法簡化了 學習的更新過程。多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 系統(tǒng)中的大規(guī)模搜索空間的問題，但很難預 定義其r _ s t a t e 集和r a c t i o n 集，且不能保證找到最優(yōu)解【2 5 。還有很多學者通 哈爾濱二r 程大學博士學位論文 過學 - j 分類系統(tǒng)、加權策略共5 1 4 1 1 方式來研究多a g e n t 的學習等。 對策論的發(fā)展是循著從零和到非零和、完全信息到非完全信息、靜態(tài)到 動態(tài)的方向進行的。所以，該框架下的多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 的協(xié)商問題【4 ”，清華大 學石純一等研究將拍賣方法引入多a g e n t 系統(tǒng)的協(xié)商中【4 6 l ，另外，西南師范 大學的張虹等利用在多a g e n t 學習中引入可信第三方的方法研究了對策的協(xié) 商問題【4 ”，等等。 1 2 3 存在的問題及解決方案 多a g e n t 學習領域目前仍然存在的問題咀及研究的熱點主要集中于以下 幾個方面： 1 ) 加快學習速度 學習速度慢在單a g e n t 領域已經是一個很明顯的問題，在多a g e n t 系統(tǒng)中 則更為突出，尤其是需要對其他a g e n t 建模時，時間復雜度會隨a g e n t 的數量 成指數倍增加【2 1 1 。這嚴重限制了多a g e n t 學習在實際中應用，迫切要求加快 學習的速度。梯度法、嵌入先驗知識、模糊學習、狀態(tài)空間劃分、分層學習 等現有加速算法對特定任務背景依賴性很強，而且都是針對單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 ) 減小空間需求 復雜的任務、動態(tài)連續(xù)的環(huán)境和對其他a g e n t 的預測都急劇地膨脹著多 a g e n t 學習的空間需求。連續(xù)空間的表示一直是實際應用中的巨大障礙，- - l o e 解決方法是對狀態(tài)和動作進行抽象，包括條件和行為提取、成員內部建模、 關系一狀態(tài)估計及狀態(tài)向量量子化【2 ”。但所有的這些都可以看作是單a g e n t 學 習的變體，因為它將其他a g e n t 建模成環(huán)境中一部分或使用固定策略，而對 第1 蘋緒論 于其他白適應a g e n t 的情況，尚需繼續(xù)研究。使用抽象算法后的收斂性說明 仍沒有令人滿意的結果。另外，函數逼近和泛化方法也可用來減小空間需求 1 5 0 1 ，但逼近和泛化本身的不確定性為學習的收斂增加了一定的困難，需要進 一步優(yōu)化。 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 最優(yōu)解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 系統(tǒng)中快速有效地獲得平衡解的問題，正被 多個研究領域共同關注。 4 ) 平衡解的選擇 存在多個對策平衡解的時候，如何保證所有a g e n t 選擇統(tǒng)一的解向量從 而實現最優(yōu)的聯(lián)合動作，并保證最終的學習收斂，對于多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 的實驗中利用 特定的求解方法來約束解的選擇，規(guī)定所有a g e n t 都選擇l e m k e h o w s o n 算 法求得的第一個平衡解，這實際上相當于在系統(tǒng)中作了強制性的約定，而且 它也不能保證選到p a r e t on a s h 平衡解。因此，如何在保證a g e n t 自主性的同 時使他們選擇統(tǒng)一的平衡解，又不花費太長的協(xié)商時間，是目前大多數多 a g e n t 學習研究者所關心的問題。 5 ) 信度分配 前面介紹的工作主要集中于狀態(tài)值的確定，而在合作的多a g e n t 系統(tǒng)中， 如何分配強化信號，即信度分配問題，也同樣需要關注。已有的桶群算法比 較常用，另外一些針對模塊化學習系統(tǒng)的算法和針對分類器系統(tǒng)的算法都在 一定程度上解決了信度分配m 題，但他們都不是根據a g e n t 對任務的貢獻來 哈爾濱t 程大學博士學位論文 分配的，而是根據他們以往收到的強化值折扣或其它類似指標進行分配。這 種方法顯然不公平，它容易使得偶然體現出高性能的a g e n t 不斷獲得大的強 化值份額，個體過于突出1 4 刖。較合理的分配方式在對策論中有相應的研究， s h a p l e y 值是一個較成熟的利益分配方式口3 1 ，可以考慮在該方向中做進一步 的探索。 6 ) 聯(lián)盟的形成 多個a g e n t 如何針對不同的任務自主結成聯(lián)盟或達成合作協(xié)議，實現統(tǒng) 一的目標且防止利益之爭，這對任務的完成效率非常重要。已有的拍賣、平 衡、投機和打工等形式5 4 i ，先將任務分解，然后按照不同的標準選擇參與a g e n t 并分配給它們相應的任務，從而形成一個具有約束力的聯(lián)合體?！? 5 】利用聯(lián) 合承諾構造聯(lián)盟，但容易使某些優(yōu)勢個體發(fā)展過快，錯過最好的組合方式。 如何選擇a g e n t 形成相應的聯(lián)盟，聯(lián)盟形成之后，如何實現利益劃分、設定 懲罰機制防止成員背叛05 , 2 0 】及根據任務狀態(tài)解散聯(lián)盟，這都是目前需要進一 步研究的細節(jié)問題。 7 ) 協(xié)調機制 合作多a g e n t 的學習系統(tǒng)中通常需要引入協(xié)調機制使成員的選擇保持一 致，常用的有基于常規(guī)( 社會法則) 的協(xié)調和基于通訊的協(xié)調1 5 6 1 。社會規(guī)則 是在所有a g e n t 及其相關動作的完全排序都己知的條件下，采用各種不同的 方法對最優(yōu)動作集合進行排序。它的缺點在于每個a g e n t 都必須事先知道所 有a g e n t 及其相關動作的排序，通常只適用于固定的場合?；谕ㄓ嵉膮f(xié)調 是一種最自然的協(xié)調機制，a g e n t 之間通過相互傳遞各自的意圖來進行協(xié)調。 但是它需要設計通訊和協(xié)商協(xié)議，不可避免的會發(fā)生通訊失敗和錯誤解釋等 問題，且過多的通信時間會延遲學習的速度。所以，制定一套較通用的社會 規(guī)則或設計一種快速有效的通訊方式對于學習的效果和應用都有很大的作 用。 8 ) 不完全信息睛況 在不完全信息的對策中，a g e n t 無法獲得對方的回報函數等信息，它需要 對狀態(tài)進行預測，這就涉及到對預測狀態(tài)的表示及計算 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 規(guī)則對系統(tǒng)模型信念及對手策略信 念進行推理，但完全的b a y e s i a n 更新需要很大的計算量。且從理論上看，在 學習中引入了不確定性，更增加了結果的不穩(wěn)定性，關于這些方面仍然存在 很多問題需要進一步的挖掘和研究。 g ) 新收斂標準的選取 n a s h q 在算法的執(zhí)行和最后所采用的收斂衡量標準都是n a s h 平衡解概 念。有的學者質疑n a s h 平衡在對策論中所起到的中心作用在a i 中是否仍然 成立。所以，一些新標準i t 6 l 的探索將為多a g e n t 學習的研究開辟新的發(fā)展道 路。 多a g e n t 學習作為多a g e n t 系統(tǒng)的重要研究內容之一，受n - l 越來越多的 重視。隨著多a g e n t 經濟的出現和發(fā)展，有效的多a g e n t 學習技術必將成為跨 學科的新研究領域。目前關于這方面的理論仍不夠成熟，有待進一步的探索 研究。 1 3 追捕一逃跑問題 追捕一逃避問題來源于自然界食肉動物捕食獵物的行動，因此又稱捕食者 一獵物問題( p r e d a t o rp r e yp r o b l e m ) ，它是研究分布式系統(tǒng)中多智能體合作 與協(xié)調的理想i ；q 題，而利用實際機器人研究追捕逃避的系統(tǒng)更是一個包括實 時視覺處理、無線通訊、多機器人控制與協(xié)作、實時動態(tài)路徑規(guī)劃等多學科、 多領域知識的多機器人分布式系統(tǒng)。在追捕問題中，獵物需要多個追捕者協(xié) 作才能捕獲，而且涉及到追捕方和逃避方兩個機器人群體的對抗。追捕過程 中局勢是時刻變化的，每個機器人必須實時了解環(huán)境的動態(tài)變化，通過實時 知識處理對當前對抗格局的判斷，及時做出變換角色、重新組隊或編隊等決 策。因此，追捕問題是被廣泛關注但至今尚未解決的動態(tài)環(huán)境下實時知識處 理的典型問題，也是研究多智能體合作與協(xié)調策略和對抗策略進化的通用問 題。 哈爾濱工程大學博士學位論文 1 3 1 研究內容 人工智能學者利用追捕一逃跑問題對追捕逃避雙方策略的競爭性協(xié)進化、 獵物的逃避行為6 2 1 、多智能體合作策略、多智能體通訊 6 3 , 6 4 等進行了大量的 研究。追捕逃跑問題的關鍵技術在軍事、工業(yè)等方面也有著廣泛的應用，如 機器人部隊合作包圍捕獲入侵者6 6 1 和空戰(zhàn) 6 7 - 7 0 1 1 等對抗領域都已經采用追 捕逃避問題來研究，此外，工件調度、交通運輸管理、并行計算【7 1 1 等也已用 追捕逃避模型進行了研究。 根據研究目的不同，追捕一逃跑問題可實例化為不同的具體問題。如己知 環(huán)境中追捕重點研究雙方的策略，而未知環(huán)境追捕還需同時識別并建立環(huán)境 的模型；再如單個追捕者和單個獵物的一對一追捕通常用來研究追捕逃避雙 方策略的協(xié)進化 7 2 , 7 3 】與獵物的自適應逃跑策略74 1 ，而多個追捕者追捕單個或 多個獵物的追捕問題通常用來研究追捕者間的合作與協(xié)調機制。 追捕- 逃跑問題本質上是分布式m a s ( m u l t i a g e n ts y s t e m ) 協(xié)作決策問題， 通過研究多個追捕者的合作追捕策略研究機器人社會中智能體腳的競爭與合 作、合作與協(xié)調策略和最優(yōu)合作決策機制及團隊最優(yōu)決策算法等，為此，需 要具體研究以下內容： ( 1 ) 通過多個追捕者組成團隊捕獲單個獵物的追捕問題，研究具有公共 目標的合作團隊內部成員間的協(xié)調問題，給出智能體協(xié)調自身行為達到個體 和團隊雙重的最優(yōu)的決策機制與協(xié)調算法。 ( 2 ) 設計最優(yōu)的任務分配機制，追捕團隊通過協(xié)商選出足夠的、最合適 追捕者組織的追捕子團隊，捕獲動態(tài)出現的獵物。 ( 3 ) 針對環(huán)境與任務的動態(tài)性，設計相應的學習和自適應算法，使追捕 團隊通過學習，最優(yōu)捕獲獵物的合作追捕策略。 1 3 2 研究現狀 本文研究的追捕逃避問題指的是多追捕者組成團隊圍捕并驅逐一個需要 多個追捕者合作才能捕獲的獵物的情況，由于該情況明確規(guī)定了追捕者問的 合作任務，因此從一開始就被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 個追捕 者合作追捕獵物。然而，在這兩個模型中追捕者和逃避者輪流運動，回合制 的附加條件使追捕過程不能收斂到穩(wěn)定狀態(tài)，也不符合問題的實際情況。因 此，合理的模型必須讓追捕者和逃避者同時運動。為了得到穩(wěn)定收斂的控制 策略，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 ) 自動生成并進化對抗雙方的控制策略，但由于僅采用貪心法控 制，控制策略完全通過學習獲得，且沒有任何合作機制，未能得出預期的協(xié) 進化效果，連采用簡單的直線逃避策略的獵物都無法捕獲。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 研究了保安機器入部隊，它可在發(fā)現入侵者后依靠路標 等自動導航，通過合作編隊將入侵者包圍擒獲，但目前僅針對靜止目標研究 機器人部隊的自適應隊形控制。 除了上述環(huán)境信息己知的確定性理論追捕研究外，南加州大學和其 b e r k e l e y 分校的ss a s t r y 研究小組1 8 2 47 1 在美國海軍部、空軍部資助下研究未 知環(huán)境下具有不精確傳感的多個空中和地面追捕者合作追捕地面上逃避者的 概率模型，重點研究追捕者在追捕的同時合作建立環(huán)境模型。 多獵物合作追捕的研究目前很少，且對合作的理解也不同。g r i n t o n f 8 8 j 利用承諾與公約合作機制研究了靜止的需要不同數目的追捕者合作才能捕獲 的多獵物追捕問題，重點研究多追捕者間相容承諾的生成算法，比較了不同 控制策略、通訊方案、追捕者數目等對追捕性能的影響。ki r w i g 和hb e r e n j i 等人提出了不同的合作概念，在他們研究的追捕問題( 更確切的說，是捕食 問題) 中，單個追捕者就可以捕獲任意一個獵物，研究目的是追捕團隊如何 協(xié)調才能使團隊捕獲的獵物總數最多，為了增加問題的難度，獵物在存在隨 啥爾濱工程大學博士學位論