派生規(guī)劃問題的理論與算法研究.pdf

1、PDDL公理的研究與應(yīng)用推理重新成為目前智能規(guī)劃研究領(lǐng)域的熱點(diǎn)。派生謂詞是PDDL2.2語言的新特性之一，派生規(guī)劃問題是最新的將邏輯推理融合到規(guī)劃求解技術(shù)中的規(guī)劃問題。如何推導(dǎo)動作前提中的派生謂詞和處理動作效果對派生謂詞的間接影響，是派生規(guī)劃問題中的兩個關(guān)鍵問題。 激活集是指使得派生謂詞的實(shí)例在當(dāng)前狀態(tài)下成立的一組由基本謂詞的實(shí)例所構(gòu)成的集合?；贚PG-td規(guī)劃系統(tǒng)的已有工作，本文定義了與狀態(tài)無關(guān)的激活集(簡稱為SIAS)。S

2、IAS完全由規(guī)則集推導(dǎo)出來，即當(dāng)當(dāng)前狀態(tài)發(fā)生變化時，不需要在規(guī)則圖上重新計算新的激活集。這使得在提取動作解的過程中，避免了對派生謂詞的激活集的重復(fù)計算，從而減少了總的規(guī)劃求解時間。本文提出了在規(guī)則圖上計算與狀態(tài)無關(guān)的激活集的SIAS-search算法，以及將與狀態(tài)無關(guān)的激活集應(yīng)用到啟發(fā)式估值的DP-relax-plan算法。 基規(guī)則集是指用規(guī)劃問題所包含的實(shí)體進(jìn)行實(shí)例化的領(lǐng)域理論。規(guī)則圖是基于基規(guī)則集建立的與或圖，事實(shí)節(jié)點(diǎn)是與節(jié)

3、點(diǎn)，規(guī)則節(jié)點(diǎn)是或節(jié)點(diǎn)。當(dāng)規(guī)劃問題所包含的實(shí)體個數(shù)增多，規(guī)則圖的規(guī)模呈指數(shù)增長。在這樣龐大的規(guī)則圖上，即使計算與狀態(tài)無關(guān)的激活集也是很耗費(fèi)時間的。為此，盡量避免在規(guī)則圖上計算激活集。根據(jù)派生謂詞的語義，派生事實(shí)的激活集集合可以證明是該派生事實(shí)的一個析取范式。用這樣的析取范式在基規(guī)則集中進(jìn)行推導(dǎo)，使得基規(guī)則集包含更多的基本謂詞，可以推導(dǎo)出其它的派生謂詞的與狀態(tài)無關(guān)的激活集。這個過程稱為規(guī)則集的基化過程，它使得規(guī)則集發(fā)生等價變換而不改變原有規(guī)