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

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

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

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

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

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

6、相當(dāng)出色的表現(xiàn)離線規(guī)劃算法在智能體與環(huán)境進(jìn)行交互前，通過(guò)給定的模型計(jì)算出完整的策略。其主要優(yōu)勢(shì)在于有充足的時(shí)間來(lái)進(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é)合的辦法來(lái)構(gòu)建一套完整的策略。對(duì)于大規(guī)模問(wèn)題，其主要瓶頸在于每一步迭代都會(huì)產(chǎn)生極其多的子策略。這些子策略會(huì)快速的耗盡所有

7、的存儲(chǔ)空間或者導(dǎo)致運(yùn)算嚴(yán)重超時(shí)。為了解決這一問(wèn)題，本文在前人工作的基礎(chǔ)上提出了PBPG和TBDP這兩個(gè)算法。PBPG算法的主要?jiǎng)?chuàng)新點(diǎn)在于徹底的改變了之前先枚舉再選擇的策略生成模式，直接構(gòu)建最優(yōu)化的模型為每個(gè)信念點(diǎn)直接生成所需的策略。因此在動(dòng)態(tài)規(guī)劃過(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è)試問(wèn)題。TBDP算法主要針對(duì)的是大狀態(tài)DEC-POMDP問(wèn)題。其主要的創(chuàng)新點(diǎn)是使用基于測(cè)試的方法只為可達(dá)的狀態(tài)和需要使用到的策略計(jì)算值函數(shù)。之前的算法，籠統(tǒng)的為所有的狀態(tài)和策略計(jì)算值函數(shù)，因此帶來(lái)了極高的計(jì)算量，無(wú)法求解大規(guī)模問(wèn)題。TBDP算法的另一個(gè)創(chuàng)新點(diǎn)是提出了具有層次結(jié)構(gòu)和隨機(jī)參數(shù)的新的策略表示方法。該方法能夠?qū)⒉呗陨赊D(zhuǎn)變?yōu)椴呗詤?shù)的最優(yōu)化過(guò)程，從而進(jìn)一步的提高了策略求解的效率

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

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