信息傳遞法求解與維護(hù)不確定狀態(tài)系統(tǒng)的可達(dá)關(guān)系.pdf

1、智能規(guī)劃是隸屬于人工智能領(lǐng)域的一個(gè)重要研究方向，近年來受到許多學(xué)者的關(guān)注。而不確定規(guī)劃則是其中的一個(gè)重要分支。近幾年來，有較多針對(duì)不確定規(guī)劃的研究，但由于在求規(guī)劃問題的解時(shí)，缺少引導(dǎo)信息，會(huì)導(dǎo)致許多無用狀態(tài)和動(dòng)作被搜索，造成冗余計(jì)算。因此在求規(guī)劃解之前，先對(duì)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中的狀態(tài)之間的關(guān)系進(jìn)行預(yù)處理，找出它們之間的可達(dá)關(guān)系，這樣能加快對(duì)于規(guī)劃問題的求解。有學(xué)者運(yùn)用鄰接矩陣來表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng)，運(yùn)用矩陣自乘來模擬系統(tǒng)的中控制器的位

2、置轉(zhuǎn)移，能求出狀態(tài)之間的可達(dá)關(guān)系，但該類算法對(duì)于規(guī)模較大的系統(tǒng)效率比較低。因此，本文仔細(xì)分析了現(xiàn)有算法的優(yōu)勢之處，找出了其存在的不足之處，設(shè)計(jì)了一種全新的求可達(dá)關(guān)系算法，能高效的求解大規(guī)模不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達(dá)關(guān)系。并對(duì)不確定系統(tǒng)中可能存在動(dòng)作變化（確定動(dòng)作因某種因素?zé)o法執(zhí)行），設(shè)計(jì)了一種局部更新其可達(dá)關(guān)系算法，避免了重新求解狀態(tài)之間的可達(dá)關(guān)系，提高了效率。
　　本研究主要內(nèi)容包括：⑴參考了計(jì)算機(jī)網(wǎng)絡(luò)中的RIP路由協(xié)議，提出了用

3、信息傳遞法來求解可達(dá)關(guān)系，仍舊用鄰接矩陣表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng)，并且將每一行中的可達(dá)關(guān)系視為其他狀態(tài)到達(dá)該狀態(tài)的可達(dá)信息；通過狀態(tài)之間的信息的收集、狀態(tài)之間信息傳遞、狀態(tài)自身信息的更新，分三個(gè)階段求得不確定系統(tǒng)的狀態(tài)可達(dá)關(guān)系，避免了大量的矩陣運(yùn)算，并通過分析算法的時(shí)間復(fù)雜度，從理論上證明了該算法的高效性。與此同時(shí)，對(duì)每個(gè)狀態(tài)的可達(dá)信息進(jìn)行標(biāo)記，避免了對(duì)不確定規(guī)劃系統(tǒng)是否有回路進(jìn)行分類及設(shè)計(jì)不同的算法，降低了算法實(shí)現(xiàn)的難度。最后通過實(shí)例以

4、及實(shí)驗(yàn)，運(yùn)用信息傳遞法求解非循環(huán)和循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達(dá)關(guān)系，進(jìn)行了詳細(xì)的說明。⑵提出了針對(duì)非循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)在確定動(dòng)作無法執(zhí)行的情況下，維護(hù)該系統(tǒng)可達(dá)關(guān)系的算法。在信息傳遞法的基礎(chǔ)之上，提出了對(duì)于非循環(huán)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的最小信息傳遞集(簡稱MIDS)，分析了MIDS的性質(zhì)。通過 MIDS，可以快速判斷無法執(zhí)行的確定動(dòng)作是否會(huì)對(duì)系統(tǒng)的可達(dá)關(guān)系產(chǎn)生影響。同時(shí)，對(duì)于每個(gè)狀態(tài)的可達(dá)信息建立索引，通過索引，可以實(shí)現(xiàn)對(duì)系統(tǒng)的可達(dá)