基于不確定系統(tǒng)的狀態(tài)可達(dá)關(guān)系求規(guī)劃解的算法研究.pdf

1、智能規(guī)劃是人工智能近年來(lái)的熱點(diǎn)研究領(lǐng)域，而關(guān)于不確實(shí)規(guī)劃的研究是其中一個(gè)重要分支。不確定規(guī)劃問(wèn)題由于動(dòng)作的不確定性，已存在的用來(lái)求不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的強(qiáng)規(guī)劃解、弱規(guī)劃解及強(qiáng)循環(huán)規(guī)劃解的方法都是采取從目標(biāo)狀態(tài)開始進(jìn)行反向搜索的方法來(lái)求規(guī)劃解，但由于沒(méi)有任何引導(dǎo)信息，求規(guī)劃解時(shí)常常會(huì)重復(fù)搜索大量無(wú)用的狀態(tài)和動(dòng)作，所以如何獲得系統(tǒng)的引導(dǎo)信息，并用于求規(guī)劃解以提高求解的效率一直是研究的難點(diǎn)。
　　本文針對(duì)以上問(wèn)題，基于不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的

2、狀態(tài)可達(dá)關(guān)系，對(duì)于不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中規(guī)劃解的求解問(wèn)題，主要做了以下兩方面的研究：
　　1.在不確定規(guī)劃領(lǐng)域中，不確定狀態(tài)轉(zhuǎn)移系統(tǒng)求規(guī)劃解時(shí)常常存在大量冗余操作，造成不必要的搜索和計(jì)算。本文將不確定狀態(tài)轉(zhuǎn)移系統(tǒng)轉(zhuǎn)換為鄰接矩陣，使用鄰接矩陣的加和乘運(yùn)算獲得系統(tǒng)中的可達(dá)矩陣，即獲得了系統(tǒng)狀態(tài)間的可達(dá)關(guān)系。因此，我們基于這兩個(gè)矩陣設(shè)計(jì)了基于可達(dá)關(guān)系正向搜索強(qiáng)規(guī)劃解、弱規(guī)劃解的算法，在求規(guī)劃解的過(guò)程中，根據(jù)鄰接矩陣為系統(tǒng)確定下一步該選擇執(zhí)

3、行的動(dòng)作，在可達(dá)矩陣中判斷執(zhí)行該動(dòng)作到達(dá)的狀態(tài)是否可達(dá)目標(biāo)狀態(tài)，以此確定該狀態(tài)動(dòng)作序偶是否能夠加入到規(guī)劃解中。若執(zhí)行動(dòng)作到達(dá)的狀態(tài)不可達(dá)目標(biāo)狀態(tài)，則可以避免搜索這些對(duì)構(gòu)成規(guī)劃解沒(méi)有用的狀態(tài)和動(dòng)作。在搜索的過(guò)程中根據(jù)兩個(gè)矩陣的值判斷狀態(tài)和動(dòng)作是否有用，若無(wú)用，則直接避免了搜索，減少了大量冗余計(jì)算，提高了求規(guī)劃解的效率。
　　2.多agent規(guī)劃問(wèn)題首次的正式討論出現(xiàn)在2010年的ICAPS上，現(xiàn)在關(guān)于多agent規(guī)劃領(lǐng)域的研究多為具

4、有確定動(dòng)作的多agent規(guī)劃問(wèn)題，而具有不確定動(dòng)作的多agent規(guī)劃問(wèn)題的研究還是一個(gè)很新的領(lǐng)域。本文針對(duì)不確定多agent規(guī)劃系統(tǒng)協(xié)同規(guī)劃解的問(wèn)題，設(shè)計(jì)了基于可達(dá)關(guān)系求多agent規(guī)劃解的算法。在假設(shè)agent執(zhí)行每個(gè)動(dòng)作的時(shí)間相等的前提下，該算法利用鄰接矩陣和可達(dá)矩陣中關(guān)于狀態(tài)之間的轉(zhuǎn)移信息及可達(dá)信息，為多個(gè)agent確定下一步轉(zhuǎn)移的動(dòng)作，執(zhí)行動(dòng)作后，存在agent與上一個(gè)agent到達(dá)的狀態(tài)相同且總執(zhí)行時(shí)間相等的情況下，對(duì)該age