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

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

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

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

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