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

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

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

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

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

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

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