基于解釋圖剪枝算法的概率規(guī)劃識別系統(tǒng)的研究及實(shí)現(xiàn).pdf

1、規(guī)劃識別是指規(guī)劃識別器根據(jù)觀察到的智能體(一個(gè)或多個(gè))的片斷的、瑣碎的動(dòng)作，推測出在一定程度上具有合理因果關(guān)系的智能體將要執(zhí)行的動(dòng)作和欲實(shí)現(xiàn)的目標(biāo)，即推導(dǎo)出智能體正在執(zhí)行的規(guī)劃。但是，通常無二義性地確定一個(gè)規(guī)劃假設(shè)是很困難的，因?yàn)樵谠S多領(lǐng)域，或者一個(gè)動(dòng)作服務(wù)于多個(gè)目標(biāo)，或者被識別域中存在多規(guī)劃甚至是多智能體多規(guī)劃并行執(zhí)行，而且，其中的許多領(lǐng)域僅僅是部分可觀察的等等。這些問題的存在限制了許多規(guī)劃識別方法的應(yīng)用。比如，沒有狀態(tài)轉(zhuǎn)移概率模型的

2、復(fù)雜領(lǐng)域的大規(guī)模特性使得抽象馬爾可夫模型的應(yīng)用變得困難；基于概率語法的方法無法處理多規(guī)劃交替并行實(shí)現(xiàn)的問題；采用語法分析的方法，雖然搜尋速度快，但無法處理時(shí)序約束等等。Goldman和Geib于1999年提出了一種新的基于規(guī)劃執(zhí)行的規(guī)劃識別模型，之后又于2005年加以完善，其方法不僅可以識別偏序規(guī)劃及多規(guī)劃交替執(zhí)行，還可以處理域的部分可觀察問題。但是，隨著考慮的未觀察動(dòng)作在整個(gè)規(guī)劃假設(shè)中所占比例的增加，其效率將明顯下降。 在本文

3、中，我們提出了一種新的規(guī)劃識別方法-基于解釋圖剪枝技術(shù)的規(guī)劃識別算法，該算法在給出新的軟時(shí)序約束和硬時(shí)序約束的概念的基礎(chǔ)上，以高效的圖搜索為基礎(chǔ)，以解釋圖的剪枝技術(shù)為核心，利用本文中定義的兩種時(shí)序約束來推測未觀察動(dòng)作，擴(kuò)展解釋圖，并利用軟時(shí)序約束對當(dāng)前解釋圖進(jìn)行剪枝，以精確目標(biāo)假設(shè)集合，然后計(jì)算各目標(biāo)假設(shè)的概率，并以之對目標(biāo)假設(shè)進(jìn)行分級與選擇，最后對所選目標(biāo)假設(shè)子樹進(jìn)行擴(kuò)展，即可得到完整的規(guī)劃假設(shè)。同時(shí)，本文還引入了支持程度的概念，以使

4、規(guī)劃識別可以隨著收集到越來越多的證據(jù)而合理地改變。該算法不僅可以有效處理域的部分可觀察問題和偏序規(guī)劃及多規(guī)劃交替執(zhí)行等問題，還可以排除智能體的誤導(dǎo)動(dòng)作，這將在網(wǎng)絡(luò)安全及入侵檢測等許多領(lǐng)域都有廣闊的應(yīng)用前景。 在給出算法的基礎(chǔ)上，本文采用C++語言對該算法進(jìn)行了實(shí)現(xiàn)，設(shè)計(jì)了基于解釋圖剪枝技術(shù)的概率規(guī)劃識別系統(tǒng)EGPPR，并用實(shí)例對其性能加以測試，結(jié)果表明，該系統(tǒng)完全可以達(dá)到理論預(yù)期效果，即不僅可以識別出智能體的目標(biāo)和已經(jīng)發(fā)生卻未被