基于效用理論的并行概率規(guī)劃算法的研究與實(shí)現(xiàn).pdf

1、智能規(guī)劃是人工智能研究領(lǐng)域近年來發(fā)展起來的一個(gè)熱門分支，由于其廣泛的實(shí)用性，受到研究者的高度重視。尤其是具有不完全信息和不確定信息的規(guī)劃問題已經(jīng)成為智能規(guī)劃研究中的重點(diǎn)。在各種研究方法中，由于概率方法能較準(zhǔn)確地對(duì)不確定信息進(jìn)行定量描述，因此研究動(dòng)作具有概率輸出的概率規(guī)劃方法體現(xiàn)了較強(qiáng)的優(yōu)越性，這個(gè)方法得到了研究者的肯定，并在此基礎(chǔ)上產(chǎn)生了大量的算法。 基于Graphplan算法的PGraphplan是概率規(guī)劃中較優(yōu)秀的一款規(guī)劃器

2、。PGraphplan在圖規(guī)劃框架下利用動(dòng)態(tài)規(guī)劃算法找到隨機(jī)規(guī)劃解。但規(guī)劃解是在“每個(gè)時(shí)間步只允許執(zhí)行一個(gè)非空動(dòng)作”的假設(shè)下求得的，這個(gè)假設(shè)的存在使得在規(guī)劃圖中無法使用互斥信息，找到的規(guī)劃解相對(duì)冗長(zhǎng)，浪費(fèi)求解時(shí)間。并且算法只考慮概率信息，沒有涉及狀態(tài)的效用值信息，不便于處理現(xiàn)實(shí)世界的問題。 本文針對(duì)概率規(guī)劃中存在的這兩點(diǎn)不足之處，提出了新的概率規(guī)劃算法UC-PGraphplan。 首先，我們通過添加結(jié)果結(jié)點(diǎn)，對(duì)經(jīng)典規(guī)劃圖

3、進(jìn)行了擴(kuò)展，并定義了并行有效軌跡及各種結(jié)點(diǎn)的互斥關(guān)系，盡可能多的包含所有的有效軌跡，使其在同一時(shí)間步實(shí)現(xiàn)了并行，打破了原有概率規(guī)劃算法中“每個(gè)時(shí)間步只允許執(zhí)行一個(gè)非空動(dòng)作"的限制，彌補(bǔ)了原有算法的不足，提高了規(guī)劃器的運(yùn)行速度和性能。 其次，在并行概率規(guī)劃中運(yùn)用了效用理論，使所有目標(biāo)都能以最大的期望效用值去實(shí)現(xiàn)，從而提高了規(guī)劃器的求解質(zhì)量。該算法更適合于求解現(xiàn)實(shí)世界中的概率規(guī)劃問題。 本文在給出算法的基礎(chǔ)上，利用C語言對(duì)該