基于模型檢測的不確定規(guī)劃中的狀態(tài)可達(dá)性研究.pdf

1、智能規(guī)劃是人工智能的一個重要領(lǐng)域,不確定規(guī)劃是智能規(guī)劃的一個重要分支,它比經(jīng)典規(guī)劃更具有現(xiàn)實性。近年來,很多研究人員對基于模型檢測的不確定規(guī)劃進(jìn)行了大量而深入的研究并取得了很好的成績。基于模型檢測的不確定規(guī)劃中,求解規(guī)劃問題時需要反復(fù)的搜索動作來尋找目標(biāo)狀態(tài),這帶來大量的冗余計算和重復(fù)操作。獲得一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的狀態(tài)可達(dá)關(guān)系可以提高求解規(guī)劃問題的效率,減少冗余計算,構(gòu)建狀態(tài)轉(zhuǎn)移系統(tǒng)的引導(dǎo)信息。因此,本文做了如下研究:
　　1

2、.不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,采用傳統(tǒng)的求解規(guī)劃問題的方法去求解規(guī)劃問題會產(chǎn)生大量的冗余計算,從而降低了求解效率。獲得不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的非循環(huán)狀態(tài)可達(dá)關(guān)系可以使得求規(guī)劃問題的強規(guī)劃解和弱規(guī)劃解的效率大大提高。本文設(shè)計了求不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中非循環(huán)狀態(tài)可達(dá)關(guān)系的方法,以及在獲得不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的非循環(huán)狀態(tài)可達(dá)關(guān)系后求解強規(guī)劃解的算法,并通過分析算法時間復(fù)雜度和實驗得出結(jié)論:在獲得狀態(tài)可達(dá)性關(guān)系后求解強規(guī)劃解的效率有顯著的提高。從理論上證明了

3、求不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的非循環(huán)狀態(tài)可達(dá)關(guān)系方法的正確性。
　　2.設(shè)計了求不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中循環(huán)狀態(tài)可達(dá)關(guān)系的方法,循環(huán)可達(dá)關(guān)系是在不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中普遍存在的一個可達(dá)關(guān)系。循環(huán)可達(dá)關(guān)系是可達(dá)關(guān)系的一個重要部分,求循環(huán)可達(dá)關(guān)系可以完善可達(dá)關(guān)系,增加狀態(tài)可達(dá)關(guān)系的應(yīng)用范圍。本文首先分析了循環(huán)可達(dá)關(guān)系的特點,通過這些特點將循環(huán)可達(dá)關(guān)系進(jìn)行了分類。研究了各類循環(huán)可達(dá)關(guān)系之間的聯(lián)系;其次,定義了自身二可達(dá)關(guān)系并且證實了導(dǎo)致循環(huán)可達(dá)關(guān)系的