基于決策理論的多智能體系統(tǒng)規(guī)劃問題研究.pdf

1、不確定性環(huán)境下的決策和規(guī)劃是人工智能的基本問題之一。決策論為這類問題的最優(yōu)化求解提供了標(biāo)準(zhǔn)的理論框架。近年來，單智能體的決策理論取得了長(zhǎng)足的發(fā)展，經(jīng)典的MDP和POMDP算法已經(jīng)能求解較大規(guī)模的問題。但多智能體的分布式?jīng)Q策卻依然處在研究的初級(jí)階段，通常只能求解極小規(guī)模的問題。作為馬爾科夫決策理論在多智能體系統(tǒng)上的擴(kuò)展，DEC-POMDP模型涵蓋了大多數(shù)的多智能體合作問題，但同時(shí)也具有極高的問題復(fù)雜度（NEXP難）。因?yàn)樵诙嘀悄荏w系統(tǒng)中，

2、每個(gè)智能體不僅要考慮環(huán)境的變化還需要關(guān)注其他智能體的可能行為。DEC-POMDP的復(fù)雜度具體表現(xiàn)在求解上就是問題具有極大的策略空間。如何對(duì)巨大的策略空間進(jìn)行表示和推理并從中找出最優(yōu)的策略是DEC-POMDP問題求解的關(guān)鍵。受限于問題復(fù)雜度，精確算法通常只能求解極小規(guī)模的問題。因此，本文研究的重點(diǎn)是為一般性的DEC-POMDP問題設(shè)計(jì)高效的近似算法。從求解方式上看，大體可分為在線和離線算法兩類。本文在這兩類算法上均有相應(yīng)的工作，同時(shí)還求解

3、了一類更具挑戰(zhàn)的無模型規(guī)劃問題。在線規(guī)劃算法在智能體與環(huán)境交互的過程中進(jìn)行規(guī)劃，因此只需要考慮智能體當(dāng)前遇到的情況。由于每次執(zhí)行過程中，智能體實(shí)際遇到的情況只是各種可能中很小的一部分。而且在線算法只需要為智能體當(dāng)前的行動(dòng)作出選擇，而不需要計(jì)算完整的策略。因此在大規(guī)模問題求解上，在線算法更具有優(yōu)勢(shì)。同時(shí)，在線算法還能夠更加方便的完成智能體之間的通訊，從而提高決策質(zhì)量。但在線算法本身也有需要解決的問題。因?yàn)橹悄荏w需要實(shí)時(shí)的對(duì)環(huán)境做出反應(yīng)，因

4、此每次可用于規(guī)劃的時(shí)間非常的有限。在DEC-POMDP問題中，每個(gè)智能體獲得的是各自不同的局部觀察，所有需要一個(gè)分布式的計(jì)算框架來保證智能體行為之間的協(xié)調(diào)。為了與其他智能體進(jìn)行合作，每個(gè)智能體必須把握其他智能體所有可能擁有的信息，而這些信息隨著時(shí)間的增加會(huì)不斷的暴漲。同時(shí)由于帶寬、環(huán)境和計(jì)算資源的限制，智能體之間的通訊往往是受限的。因此如何最大限度的發(fā)揮通訊的效用也是在線算法需要解決的問題。為解決這些問題，本文提出的MAOP-COMM算

5、法至少具有以下幾點(diǎn)創(chuàng)新：一、提出了基于線性規(guī)劃的快速策略搜索算法用于滿足在線算法的時(shí)間需求；二、提出了基于獨(dú)立維護(hù)的共享信念池的分布式規(guī)劃保證了智能體之間的協(xié)調(diào)；三、提出了基于策略等價(jià)的歷史信息歸并方法使得智能體能在有限的存儲(chǔ)空間中保留對(duì)后繼決策更加有用的信息；四、提出了基于信念不一致性檢測(cè)的通訊策略來更加有效的使用通訊確保了信念池信息的精度從而提高決策效果。從實(shí)驗(yàn)結(jié)果上看，MAOP-COMM算法在各種DEC-POMDP的測(cè)試問題中具有

6、相當(dāng)出色的表現(xiàn)離線規(guī)劃算法在智能體與環(huán)境進(jìn)行交互前，通過給定的模型計(jì)算出完整的策略。其主要優(yōu)勢(shì)在于有充足的時(shí)間來進(jìn)行規(guī)劃，而且不需要考慮分布式?jīng)Q策，只要求計(jì)算出的策略能被每個(gè)智能體進(jìn)行分布式的執(zhí)行。其主要劣勢(shì)在于需要完整的考慮整個(gè)策略空間，具有極高的計(jì)算量。當(dāng)前，最為先進(jìn)的離線規(guī)劃算法采用的是將動(dòng)態(tài)規(guī)劃和啟發(fā)式搜索相結(jié)合的辦法來構(gòu)建一套完整的策略。對(duì)于大規(guī)模問題，其主要瓶頸在于每一步迭代都會(huì)產(chǎn)生極其多的子策略。這些子策略會(huì)快速的耗盡所有

7、的存儲(chǔ)空間或者導(dǎo)致運(yùn)算嚴(yán)重超時(shí)。為了解決這一問題，本文在前人工作的基礎(chǔ)上提出了PBPG和TBDP這兩個(gè)算法。PBPG算法的主要?jiǎng)?chuàng)新點(diǎn)在于徹底的改變了之前先枚舉再選擇的策略生成模式，直接構(gòu)建最優(yōu)化的模型為每個(gè)信念點(diǎn)直接生成所需的策略。因此在動(dòng)態(tài)規(guī)劃過程中，備選的策略不再快速的塞滿內(nèi)存空間，同時(shí)每一步迭代后可保留的策略數(shù)大大增加，并最終大幅度的提高了規(guī)劃策略的質(zhì)量。從實(shí)驗(yàn)結(jié)果上看，PBPG算法在運(yùn)行時(shí)間上比之前最好的算法加快了一個(gè)數(shù)量級(jí)，并

8、隨著可保留策略數(shù)的增加近似最優(yōu)的求解了大部分的實(shí)驗(yàn)測(cè)試問題。TBDP算法主要針對(duì)的是大狀態(tài)DEC-POMDP問題。其主要的創(chuàng)新點(diǎn)是使用基于測(cè)試的方法只為可達(dá)的狀態(tài)和需要使用到的策略計(jì)算值函數(shù)。之前的算法，籠統(tǒng)的為所有的狀態(tài)和策略計(jì)算值函數(shù)，因此帶來了極高的計(jì)算量，無法求解大規(guī)模問題。TBDP算法的另一個(gè)創(chuàng)新點(diǎn)是提出了具有層次結(jié)構(gòu)和隨機(jī)參數(shù)的新的策略表示方法。該方法能夠?qū)⒉呗陨赊D(zhuǎn)變?yōu)椴呗詤?shù)的最優(yōu)化過程，從而進(jìn)一步的提高了策略求解的效率

9、。同時(shí)，TBDP算法可方便的運(yùn)行在多處理器的并行分布式計(jì)算資源上。在實(shí)驗(yàn)中，TBDP算法首次求解了上萬個(gè)狀態(tài)的DEC-POMDP問題。無論是離線算法還是在線算法，在問題求解的時(shí)候都需要用到完整的DEC-POMDP模型。但在大規(guī)模的現(xiàn)實(shí)問題中，完整的DEC-POMDP模型并不容易獲得。主要原因：一、環(huán)境和智能體之間有復(fù)雜的物理關(guān)系，無法準(zhǔn)確的用單一的概率函數(shù)來進(jìn)行描述；二、即便可以通過相應(yīng)的手段測(cè)量出概率值，太多的數(shù)據(jù)也將無法存儲(chǔ)和表示，

10、更無法用來計(jì)算策略。因此，設(shè)計(jì)能直接與環(huán)境進(jìn)行交互并獲得策略的規(guī)劃算法就成為求解此類問題的關(guān)鍵。因此本文還提出了基于展開式采樣的蒙特卡羅規(guī)劃算法DecRSPI。該算法僅需要能用于采樣的環(huán)境或者仿真器就能直接計(jì)算策略，而無需事先建立完整的DEC-POMDP模型。更重要的是該算法有別于之前的算法具有相對(duì)于智能體個(gè)數(shù)的線性的時(shí)間和空間復(fù)雜度。在實(shí)驗(yàn)中，DecRSPI算法順利的求解了超過20個(gè)智能體的問題，而之前的算法一般只能求解2到3個(gè)智能體