基于馬爾可夫決策理論的規(guī)劃問題的研究.pdf

1、近年來，智能體及多智能體規(guī)劃問題成為人工智能領域新的研究熱點，且有著廣泛的應用前景。本文針對馬爾可夫決策過程及其相關理論展開研究，對這些決策理論在接觸現(xiàn)實世界的應用時所面臨的問題及解決方法做了一定的探討，最后對相關的一類基本決策算法進行了一定的理論分析和改進。 主要涉及到以下幾個方面的工作： (1)較為系統(tǒng)的研究了與智能體及多智能體不確定性規(guī)劃相關的幾類基礎決策模型及算法。模型部分，首先是最基本的馬爾可夫決策模型，然后是

2、在此基礎上加入觀察不確定性的部分可觀察馬爾可夫決策模型，以及進一步加入多智能體合作的分布式部分可觀察馬爾可夫決策模型和多智能體對抗的部分可觀察的隨機博弈模型。算法部分，針對上述幾類模型，均按照后向迭代和前向搜索兩大類進行了對比分析。最后，進一步討論了與時間抽象相關的半馬爾可夫決策模型及Option理論，這一理論是設計分等級的規(guī)劃框架及算法的基礎。 (2)Robocup仿真2D提供了一個研究大規(guī)模不確定環(huán)境下多智能體規(guī)劃問題的標準

3、測試平臺。結合對該平臺的一些必要的說明，分析了在這種接近現(xiàn)實世界應用的問題中，進行整體規(guī)劃所需要處理的一些子問題的設計方法，并通過結合現(xiàn)有馬爾可夫決策過程相關理論對這些問題進行建模及分析，給出該平臺更一般的研究意義。 (3)Option理論對應了時間抽象的概念，它為馬爾可夫決策理論更多的接觸現(xiàn)實世界應用提供一個分等級規(guī)劃的研究方向。針對類似Robocup仿真2D這種帶有觀察不確定性的大規(guī)模多智能體系統(tǒng)的規(guī)劃問題，在部分可觀察隨機

4、博弈模型的基礎上，結合策略啟發(fā)，信念狀態(tài)壓縮，因子化表示法及Option理論，給出了一個新的基于動態(tài)行為生成器的決策框架，并在此基礎上設計了一個以快速尋找可行解為目標的實時啟發(fā)式搜索算法。最后，結合仿真2D這一標準平臺，對這一決策框架及算法的實用效果進行了檢驗。 (4)基于Option的理論分等級規(guī)劃時，大規(guī)模問題中子策略的求解效率也至關重要。實時動態(tài)規(guī)劃是求解馬爾可夫決策過程的一類較新的方法。這類方法除了具有求解效率上的優(yōu)勢外

5、，還很容易被設計成anytime的工作方式。實時動態(tài)規(guī)劃類算法結合了啟發(fā)式搜索與值迭代的技術，算法的核心問題是分支選擇策略與收斂判據(jù)。分支選擇策略決定了值迭代的收斂速度，收斂判據(jù)用以判定解的最優(yōu)性。通過對啟發(fā)式函數(shù)上界及下界的分析及利用，給出了一個新的收斂判據(jù)，稱為最優(yōu)行動判據(jù)，以及一個更適合實時算法的分支選擇策略。最優(yōu)行動判據(jù)可以更早的標定當前狀態(tài)滿足精度要求的最優(yōu)行動供立即執(zhí)行，而新的分支選擇策略可以加快這一判據(jù)的滿足。并據(jù)此設計了