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

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

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

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

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

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