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

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

2、IAS完全由規(guī)則集推導(dǎo)出來(lái)，即當(dāng)當(dāng)前狀態(tài)發(fā)生變化時(shí)，不需要在規(guī)則圖上重新計(jì)算新的激活集。這使得在提取動(dòng)作解的過(guò)程中，避免了對(duì)派生謂詞的激活集的重復(fù)計(jì)算，從而減少了總的規(guī)劃求解時(shí)間。本文提出了在規(guī)則圖上計(jì)算與狀態(tài)無(wú)關(guān)的激活集的SIAS-search算法，以及將與狀態(tài)無(wú)關(guān)的激活集應(yīng)用到啟發(fā)式估值的DP-relax-plan算法。 基規(guī)則集是指用規(guī)劃問(wèn)題所包含的實(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ī)劃問(wèn)題所包含的實(shí)體個(gè)數(shù)增多，規(guī)則圖的規(guī)模呈指數(shù)增長(zhǎng)。在這樣龐大的規(guī)則圖上，即使計(jì)算與狀態(tài)無(wú)關(guān)的激活集也是很耗費(fèi)時(shí)間的。為此，盡量避免在規(guī)則圖上計(jì)算激活集。根據(jù)派生謂詞的語(yǔ)義，派生事實(shí)的激活集集合可以證明是該派生事實(shí)的一個(gè)析取范式。用這樣的析取范式在基規(guī)則集中進(jìn)行推導(dǎo)，使得基規(guī)則集包含更多的基本謂詞，可以推導(dǎo)出其它的派生謂詞的與狀態(tài)無(wú)關(guān)的激活集。這個(gè)過(guò)程稱為規(guī)則集的基化過(guò)程，它使得規(guī)則集發(fā)生等價(jià)變換而不改變?cè)幸?guī)