動(dòng)態(tài)多Agent決策問(wèn)題建模與求解算法研究.pdf

1、動(dòng)態(tài)不確定環(huán)境下的多Agent決策問(wèn)題,因其更加貼近現(xiàn)實(shí)世界,具有更高的實(shí)用價(jià)值,而成為人工智能領(lǐng)域研究的重點(diǎn)和熱點(diǎn),且有著廣泛的應(yīng)用前景。但是,多Agent決策面臨巨大的物理環(huán)境狀態(tài)空間的不確定性、其他Agent決鏢的不確定性和多樣性等問(wèn)題,建立行之有效的決策模型是解決問(wèn)題的關(guān)鍵。交互式動(dòng)態(tài)影響圖(I-DID)模型憑借其高效的圖形表達(dá)結(jié)構(gòu),突破傳統(tǒng)模型表達(dá)和求解復(fù)雜度的瓶頸,已經(jīng)成為解決多Agent決策問(wèn)題的一個(gè)有效工具。
　　

2、 I-DID作為交互式部分可觀察馬爾可夫決策過(guò)程(I-POMDP)的圖模型,在I-POMDP理論下得到了嚴(yán)密的數(shù)學(xué)論證,但I(xiàn)-DID狀態(tài)空間太大,候選模型數(shù)量隨時(shí)間片增加呈指數(shù)級(jí)增長(zhǎng)等因素使求解面臨計(jì)算量的困擾。此外,I-DID缺乏對(duì)Agent通信能力的建模,降低了模型描述問(wèn)題的能力,導(dǎo)致應(yīng)用的局限性。尋求新的算法,以高效地求解I-DID模型,并建立包含通信行為的新模型是急需解決的問(wèn)題。本文在I-DID的基礎(chǔ)上展開(kāi)工作,主要涉及以下幾

3、方面的內(nèi)容:
　　 (1)系統(tǒng)地分析了與Agent決策相關(guān)的概率圖模型,包括:貝葉斯網(wǎng)(BNs)、影響圖(ID)、動(dòng)態(tài)影響圖(DID)、交互式影響圖(I-ID)、交互式動(dòng)態(tài)影響圖(I-DID),其中重點(diǎn)研究了與本文密切相關(guān)的I-DID模型,并分析其求解困難的原因。
　　 (2)提出基于分段行為等價(jià)的交互式動(dòng)態(tài)影響圖的改進(jìn)算法。基于行為等價(jià)原理對(duì)候選模型聚類,是簡(jiǎn)化計(jì)算的有效方法。但是,形成行為等價(jià)類的過(guò)程需獲得候選模型在

4、所有時(shí)間片上的解,計(jì)算量大、時(shí)間消耗非常高?？紤]到基于行為等價(jià)原理對(duì)候選模型聚類,在最后一個(gè)時(shí)間片上保留的模型個(gè)數(shù)不大于動(dòng)作集合中的元素個(gè)數(shù)。利用這一點(diǎn),在已有的精確行為等價(jià)算法的基礎(chǔ)上提出分段處理I-DID模型的改進(jìn)算法。通過(guò)與精確行為等價(jià)算法的實(shí)驗(yàn)結(jié)果對(duì)比分析,證明分段行為等價(jià)算法能夠緩解候選模型空間不斷增長(zhǎng)的趨勢(shì)。
　　 (3)提出基于信度-行為圖的交互式動(dòng)態(tài)影響圖的近似算法。采用分段處理I-DID模型的方法,當(dāng)乃(每一子

5、段包含的時(shí)間片長(zhǎng)度)很小時(shí),得不到令人滿意的結(jié)果;當(dāng)Tt很大時(shí)算法優(yōu)勢(shì)不明顯。因此提出基于信度.行為圖的近似算法:首先,把信度空間距離相近的模型聚為一類,對(duì)候選模型進(jìn)行一次壓縮。然后,采用差別模型更新的操作對(duì)候選模型進(jìn)行二次壓縮。多Agent老虎問(wèn)題和多Agent機(jī)器維修問(wèn)題上的仿真結(jié)果驗(yàn)證了該算法的有效性。
　　 (4)建立通信交互式動(dòng)態(tài)影響圖(IDID-Corn)模型。在I-DID模型的基礎(chǔ)上引人通信行為,建立包含顯式通信動(dòng)

6、作的IDID.Com模型,使高層Agent共享其觀察信息,即當(dāng)位于,層的Agenti選擇通信動(dòng)作并傳遞其當(dāng)前時(shí)間片的觀察信息時(shí),位于l-1層上的Agent j可準(zhǔn)確接收該信息,同時(shí),Agenti和j能夠利用該信息更新其信度狀態(tài)。在IDID-Com中,區(qū)別對(duì)待通信動(dòng)作和通常意義上的常規(guī)動(dòng)作,使每一時(shí)間片上的決策都包含通信子階段與常規(guī)動(dòng)作子階段,在常規(guī)動(dòng)作之前先決策是否通信。分析通信前后Agent信度狀態(tài)的變化,及其對(duì)常規(guī)動(dòng)作選擇的影響,并