基于可能性決策圖的可能性規(guī)劃.pdf

1、學校代碼：10200分類號：趾鰳研究生學號：2QQ821822密級：五東北jIf予冠大孽碩士學位論文基于可能性決策圖的可能性規(guī)劃PossibilisticPlanningUsingPossibilisticDecisionDiagrams作者：王樂指導教師：學科專業(yè)：研究方向：學位類型：谷文祥教授殷明浩副教授計算機應用技術智能規(guī)劃與規(guī)劃識別學歷碩士東北師范大學學位評定委員會2011年5月摘要人工智能規(guī)劃是近十年來發(fā)展最為迅速的研究領域之

2、一，被廣泛應用于機器人研究、航空航天技術、大規(guī)模工業(yè)生產等各個領域，在理論和應用研究上都有長足的進展，前景廣闊。早期智能規(guī)劃研究一直集中在“封閉世界”假設之下的經典規(guī)劃領域，然而很多實際問題并不滿足這樣的假設條件，因此，一些學者將目光投向了不確定性規(guī)劃的研究，其中概率規(guī)劃的研究取得了一定的成績，由于人工智能研究中的不確定性通常是順序的、定性的，動作效果的概率存實際中往往很難獲得，一些研究認為，可能性理論更適合解決那些概率模型無法解決或者

3、概率信息很難獲得的問題，提出可能性規(guī)劃的概念，在可能件規(guī)劃中，規(guī)劃的初始世界狀態(tài)足部分已知的，規(guī)劃動作的效果按照對最終目標的完成效用被分成各個等級。然而，求解可能性規(guī)劃的可能性價值迭代和可能性策略迭代往往只能商效地求解較小的問題，尤其，伴隨著域特征數日的增加狀態(tài)空問的規(guī)模往往呈指數級增長，會陷入Bellman的維度災難。同時，智能規(guī)劃的求解方法也發(fā)生著革命性的改變，由最初的用歸結定理證明的方法求解規(guī)劃，擴展為用STRIPS方法求解規(guī)劃問

4、題，接著有的研究者提出將規(guī)劃問題轉化為町滿足問題來求解，以及采用圖形的方式來求解規(guī)劃問題和采用模型檢測的方法來求解規(guī)劃問題。其中利用模型榆測的方法求解規(guī)劃取得了很好的成績，在2000年規(guī)劃大賽上，基于模型檢測的MIPS(TheModelCheckingIntegratedPlanningSystem)規(guī)劃系統(tǒng)，采用一元決策圖(BinaryDecisionDiagrams)來壓縮地表示規(guī)劃狀態(tài)，使得規(guī)劃解的搜索空間得到有效的擴展，并在20

5、02年～PS大賽卜以其m眾的表現奪得了優(yōu)秀獎。本文基于可能性理論和決策圖理論提出一種新的決策圖：可能性決策圖，用于對巧i確定環(huán)境下的4i精確的和模糊的信息進行編碼，并用定理謅卜明所提出的可能件決策圖能規(guī)范地表示可能性命題公式，而且定義了可能件決策圖上可應用的運算：取MAX運算、取MIN運算和取N運算。并將可能件決策圖應用于求解可能性規(guī)劃問題，提出了新的算法PPUPDDs，來創(chuàng)建最優(yōu)可能性策略：利用可能性決策圖來壓縮地表示可能性價值函數和