等一種用激活集來求解派生問題的改進方法

1、一種用激活集來求解派生規(guī)劃問題的改進方法12，廣州，510275）1 , 2（中山大學（暨南大學計算機系，廣州，510632）1摘要 動作的派生前提和動作刪除效果的“”是處理派生規(guī)劃問題中的難點問題，基于激活集的方法是一種簡單、有效的方法，但是激活集的計算時間往往過多，本文提出一種新的方法來計算激活集。LPG-td規(guī)劃系統(tǒng)所激活集是與狀態(tài)有關的并且需要在規(guī)則圖上反復計算，而本文激活集是與狀態(tài)無關的，通過規(guī)則來對規(guī)則集進行“基化”以及利用動態(tài)規(guī)劃的方法保存中間的計算結果，使得尋找激活集的時間逐漸地由指數級降為線性級。實現(xiàn)了一個新的能夠處理派生規(guī)劃問題的規(guī)劃系統(tǒng)LPGSIAS，通過對基準問題的求解

2、，表明LPGSIAS比LPG-td在大部分情況下更高效。與狀態(tài)無關的激活集可以方便地轉化為與狀態(tài)有關的激活集，本文通過提出一種求解與狀態(tài)無關的激活集的改進方法來加快了對派生規(guī)劃問題的求解速度。關鍵字：派生規(guī)劃問題；激活集；基化An Improved Method for Dealing with Derived Plannings Based on Activation SetsZhi-hua JIANG1Yun-fei JIANG2（Software Research Institution，Zhong Shan University，Guang zhou，China, 510275）1,2

3、（Dep. of Computer Science，Ji Nan University，Guang zhou，China, 510632）1Abstract Derived preconditions and the chain-reacting in deletion effects of actions are the maindifficulties in a derived planning. The method based on activation sets is a simple andeffective way to deal with derived plannings;

4、however, the calculation of activation sets isoften time-consuming. Therefore,roe a new way to calculate activation sets efficiently.by LPG-td planner, which are closely related to theUnlike the activation setsroducedcurrent se and have to be recalculated on the rule graph once the se changes, activ

5、ation setst we calculate on the rule graph are se-independent, whieans they are stable and havenothing to do with the se. In order to reduce the time of searching activation sets, we can persiston grounding out the rule set by the technologies of rule-splitting and dynamic programming,whiake itsible

6、t the complexity of calculating finallyes linear. We realize a news, called LPGSIAS, and some experiments onplanner which can deal with derived planningbenark problems showt it is more efficientn LPG-td plannerost cases. To sum up,our work is to present the concept of se-independent activation sets

7、of a derived fact, which canbe conveniently convertedsearch activation sets soo thoset are se-related, and proe an efficient method tot derived plannings may be quickly solved.Key Words: Derived Plannings; Activation Sets; Ground Out在人工智能領域，智能規(guī)劃(AI Planning)問題是指從某個特定問題的初始狀態(tài)出發(fā)，尋找達到解決該問題的目標狀態(tài)的動作序列。國際智

8、能規(guī)劃大賽IPC（ ernational PlanningCompetition）從 1998 年開始，每兩年一次，是最有的規(guī)劃系統(tǒng)競賽。比賽所用的規(guī)劃問題描述語言PDDL（PlanningDescription Language）總是在不斷地進行擴充和增加新的特性，以測試規(guī)劃系統(tǒng)對于實際問題的近似問題的求解能力。PDDL2.2 語言1是 2004- 1 -年國際規(guī)劃競賽IPC-4 所采用的規(guī)劃問題描述語言，它在原來的PDDL2.12的基礎上，增加了兩個新的特性：派生謂詞（Derived Predicate）和時間初始文字（Time Initial Literal）。這些特性往往被稱為“Syn

9、tax Sugar”，例了派生謂詞，動作模型只需要描述動作的最直接效果，而事物之間千絲萬縷的因果聯(lián)系可以用派生規(guī)則來表示，則整個問題描述領域變得非常的簡潔和清晰。定義派生謂詞的規(guī)則稱為派生規(guī)則，包含派生謂詞的規(guī)劃問題稱為派生規(guī)劃問題（Derived Plannings）。規(guī)劃問題的描述是基于一階謂詞邏輯，其中謂詞分成兩類：基本謂詞和派生謂詞4。二者的差別是，基本謂詞可以出現(xiàn)在領域動作的效果中，而派生謂詞不受動作的直接影響，它們在當前狀態(tài)下的真值是由封閉世界假設中某些謂詞通過領域規(guī)則所推導出來。派生謂詞不能作為動作的直接效果，但是可以出現(xiàn)在動作的前提（也稱為派生前提）和目標狀態(tài)中。因此，如何處理

10、動作的派生前提和動作效果的“”是派生規(guī)劃問題中的難點問題。在IPC-4 上，在參加決賽的 19 個規(guī)劃系統(tǒng)中，只有 4 個規(guī)劃系統(tǒng)（LPG-td5、SGPlan7、Marvin8、Downward9）能夠求解這一類型的規(guī)劃問題?？梢娕缮^詞對于大部分規(guī)劃系統(tǒng)提出了一定難度的。目前來說，對派生謂詞的處理方法大致分為兩類：編碼方法和基于激活集的方法。編碼方法主要是把派生規(guī)則轉換為新的動作，或者轉換為條件效果融合到已有的動作模型中。例如，Gazen和Knoblock把每條派生規(guī)則（if then P）轉化為一個新的動作，稱為推導動作（Deduction Operators），規(guī)則中的作為動作的前提條

11、件，派生謂詞P作為動作的增加效果10。Garagnani在轉換為推導動作的基礎上，增加了“推導事實”（deduction facts）來派生規(guī)則的應用，推導事實規(guī)則應用的所有實例，以至于當規(guī)則的前提被刪除時，只有確實地由該規(guī)則推導出來的派生謂詞才被刪除11。Davidson通過把新增加的謂詞不斷地和派生規(guī)則進行合一，使得派生規(guī)則所有可能產生的影響都編碼成領域動作中的條件效果，包括條件增加效果和條件刪除效果13。這些編碼方法的共同特點是改變已有的動作模型，在預處理階段把派生規(guī)劃問題轉換為等價的非派生規(guī)劃問題，使得傳統(tǒng)的規(guī)劃系統(tǒng)可以對其進行求解。但是這類方法在于引入大量的新動作或新謂詞從而使得動作

12、模型變得非常復雜，問題的復雜性隨著領域描述規(guī)模的增加而指數級地增長4，甚至某些轉化過程在特殊領域中還不終止，例如，Davidson方法在Towns and Roads領域中就不能終止，因此在應用性13。上帶來了一定的而基于激活集的方法不改變已有的動作模型，而是在額外的數據結構規(guī)則圖上計算能夠替代派生事實的基事實集合。基于激活集的方法是 LPG-td 規(guī)劃系統(tǒng)在 IPC-4 上采用的方法，在處理 PSR 和 PROMELA 等兩個競賽領域都有較好的效果。LPG-td 一向采用規(guī)劃圖（Plan Graph）的子圖動作圖（Action Graph）來求解規(guī)劃問題，對派生謂詞的支持也是在動作圖上進行擴

13、充，形成規(guī)則動作圖（Rule Action Graph）?；诩せ罴姆椒ㄊ且环N比較簡單、直觀、有效的方法，但是也存在不少問題，例如：派生規(guī)則要進行實例化之后產生基規(guī)則集合，基于基規(guī)則集合建立的規(guī)則圖往往非常的龐大，隨著領域所包含的實體個數指數級地增長，在這之上計算派生事實的激活集的時間花銷是值得商榷的；LPG-td 所定義的激活集是與狀態(tài)相關的，同一個派生事實所處的狀態(tài)哪怕發(fā)生了稍微的變化，都要在規(guī)則圖中重新計算其激活集；一個派生事實往往同時有多個激活集，選擇一個適合當前狀態(tài)的激活集，不僅可以影響求解速度還可以影響解的質量，因此如何恰當地定義最佳激活集？而本文是對基于激活集的方法的一種改進方

14、法，定義與狀態(tài)無關的激活集并且通過規(guī)則集“基化”結合動態(tài)規(guī)劃的本文第 1 節(jié)介紹來計算激活集，從而降低計算激活集的復雜性。派生規(guī)劃問題，包括派生謂詞的語法和語義。第 2 節(jié)介紹規(guī)則動作圖和激活集，定義與狀態(tài)無關的激活集，并它和與狀態(tài)有關的激活集之間的關系。第3 節(jié)介紹規(guī)則集的“基化”并結合動態(tài)規(guī)劃的來計算激活集。第 4 節(jié)通過實驗比較LPGSIAS和LPG-td在求解PSR等基準問題上的性能。最后給出相關工作和結論。- 2 -派生規(guī)劃問題派生謂詞的語法派生謂詞不出現(xiàn)在動作模型中，而是由派生規(guī)則來定義在什么條件下派生謂詞的真值為真。PDDL2.2 語言1中對派生謂詞的定義規(guī)定如下：:= (:de

15、rived )其中，“:derived”是派生謂詞定義的標志，“atomic formula”是原子謂詞公式，即所定義的派生謂詞，“GD”表示“goal description”，是形成派生規(guī)則觸發(fā)條件（Triggering Conditions）的謂詞公式。為了使得在規(guī)劃方法容易處理派生謂詞，PDDL2.2 對派生謂詞的使用有如下的限制：1)2)動作不直接影響派生謂詞，即派生謂詞不出現(xiàn)在動作的任何效果中；派生謂詞的真值實質上是由以下的規(guī)則推導出來：if x then P(x)，其中，P表示派生謂詞，x是變量向量，并且是中的變量向量；3)是一階謂詞公式并且滿足其否定范式NNF（Negated

16、Normal Form）不包含任何否定形式的派生謂詞。任何一個謂詞公式可以通過以下“否定符號內移”的轉化變成其NNF：x: x: ；x: x: ；i i ；i i。派生謂詞提供了一種準確而且自然的方式來表達動作的非直接效果。在一個領域所包含的所有謂詞中，凡是出現(xiàn)在某條派生規(guī)則的頭部的謂詞都稱為派生謂詞，不是派生謂詞的稱為基本謂詞。例如，在下圖所示的 BlockWorld 領域中，謂詞“on(x, y)”和“above(x, y)”的含義分別如圖 1(a)和圖 1(b)所示，前者是基本謂詞，而后者是派生謂詞，下規(guī)則來推導它的實例在當前狀態(tài)中的真值：(:derived (above ?x ?y)

17、(or (on ?x ?y)(exists (?z) (and (on ?x ?z)(above ?z ?y)設初始狀態(tài)如圖 1(c)所示，如果目標要求為“積木塊 C 在積木塊 A 的上方”，則可以通過以可以表示為“above(C, A)”，但是假如沒有引入派生謂詞，則該目標只能表示為“on(C, A) (on(C, B)on(B, A) (on(C, D)on(D, A) (on(C, B)on(B, D)on(D, A) (on(C, D)on(D, B)on(B, A)”，可見非常繁瑣。BCAD(a) on(x, y)(b) above(x, y)圖 1 BlockWorld 領域(c)

18、 初始狀態(tài)1.2 派生謂詞的語義粗略地說，派生謂詞的一個實例（參數全部常量化）為真，當且僅當它可以由某些規(guī)則派生出來，這比較類似于非單調推理。假設有這樣的一規(guī)則：if B then P，P 是派生謂詞的一個實例，稱為派生事實（Derived Facts），B 是基本謂詞的實例基本事實（BasicFacts）組成的公式，稱為該規(guī)則的觸發(fā)條件。在當前狀態(tài)中，如果 B 成立，則 P 也成立，而另一方面，如果由于某個動作刪除了 B 中的成員，并且沒有其他的規(guī)則能夠派生出 P，則P 也被該動作刪除。因此，每次產生一個新狀態(tài)，都要對其進行擴展，使其包含在該狀- 3 -xyxy態(tài)下所有成立的派生謂詞的實例。

19、定義一個函數 ，將基本事實集合 s下的擴充集合：為在規(guī)則集 R(s) := s | s s, (P(x), x) R : c, |c| = |x| : (s c) P(c) s 可以看到，(s)是在規(guī)則集 R 下的閉包運算。在 PDDL2.2 對派生謂詞使用的第三個限制條件下，即 NNF 不包含任何否定形式的派生謂詞，任何一種合法的應用規(guī)則的順序都產生相同的 (s)。這個結論可以通過一反例來說明，如果在 NNF 中允許否定形式的派生謂詞，設基本事實集合是a, b, e，規(guī)則集為a, b, not A B; a, eA，先用第一條規(guī)則而后用第二條規(guī)則，能夠推出a, b, e, B, A，先用第二

20、條規(guī)則而后用第一條規(guī)則，則只能推出a, b, e,A，導致了不同的結果狀態(tài)。對于包含了派生謂詞的規(guī)劃問題，要對 PDDL2.1 中的某些相關的語義進行相應的修改。例如，初始狀態(tài)為 s，在應用了動作 a 之后，后繼狀態(tài) s定義為：UUs = (s Del) Add ) D)aa在此定義中，A表示在某個時刻可以應用的所有動作的集合，Adda表示動作a的增加效果集合，Dela表示動作a的刪除效果集合。D是s中的派生事實集合。此定義可以確保刪除那些觸發(fā)條件已不成立又沒有其他規(guī)則能夠推出的派生事實。Axioms）4 及動作的衍生問題還需要的是，派生謂詞和領域公理（ （Ramification Probl

21、em）15,16有著非常密切的聯(lián)系。領域公理在最早的PDDL3語言定義，但是從未在IPC的任何競賽問題中使用過。派生謂詞和領域公理以及表示動作衍生效果的因果關系是非常相似的，但是后兩者都沒有派生謂詞的第三條使用限制，因此在它們的規(guī)則集中，規(guī)則的使用次序不同，可能導致不唯一的結果狀態(tài)。包含派生謂詞的規(guī)劃問題稱為派生規(guī)劃問題，一般地說，一個派生規(guī)劃問題是一個六元組：B是該領域的基本謂詞集合；D是派生謂詞集合；I表示問題的初始狀態(tài)；G表示目標狀態(tài)；A是領域動作集合； R表示派生規(guī)則集合。派生規(guī)劃問題的解仍然是一個動作序列，通過應用它使得初始狀態(tài)可以轉換到目標狀態(tài)，只不過在每次應用完一個動作之后，要對

22、新產生的狀態(tài)進行規(guī)則集R下的閉包運算，使得后繼動作的派生前提能夠包含在新狀態(tài)中。例如，在圖 1 的示例中，初始狀態(tài)如圖 1(c)所示，目標狀態(tài)為“above(A, C)”，動作序列“move(B, C, A); move(C,D, B)”是一個規(guī)劃解，轉換過程如下圖所示：move(B, C, A)move(C, D, B)圖 2 規(guī)劃狀態(tài)的改變過程2激活集本文所方法是對基于激活集來求解派生規(guī)劃問題的一種改進方法。因此，先激活集（Activation Set）。引入激活集的意義在于：派生謂詞不能出現(xiàn)在任何來看看動作的效果中，但是可以作為動作的派生前提。在動作圖上，如果由于引入了某個動作而引入了其

23、未被支持的派生前提，這時不能通過增加新的動作來支持該派生前提，只能將其轉化為某些基本事實（激活集），而這些基本事實能夠通過規(guī)則集R將該派生前提在當前狀態(tài)下推導出來。激活集需要在規(guī)則圖上進行計算，而規(guī)則圖是通過基規(guī)則集建立起來的與或圖，因此，首先要對派生規(guī)則進行實例化以產生基規(guī)則集。一個任意的派生規(guī)則（if x then P(x)），在一個具體的規(guī)劃問題中，可以轉化成一個與之等效的基規(guī)則集（規(guī)則中不含任何變量）。- 4 -ontable(A), ontable(D) on(C, B), on(B, A)above(C, B), above(C, A)above(B, A)ontable(A),

24、ontable(D) on(B, A), on(C, D)above(B, A) above(C, D)ontable(A), ontable(D) on(B, C), on(C, D)above(B, C), above(B, D) above(C, D)轉換過程如下：a) x實例化后轉換為其NNF；b) 存在量詞用所有實例的析取來代換；c) 全稱量詞用所有實例的合取來代換；d) 然后被轉換成析取范式12k；e) 對每個i建立一 規(guī)則（if i then P）。在本文的剩余部分，如無特別的說明，所說的規(guī)則集都是指基規(guī)則集。2.1 LPG-td 所定義的與狀態(tài)有關的激活集LPG-td規(guī)劃系統(tǒng)的

25、求解過程是在規(guī)劃空間中進行搜索，而每個規(guī)劃則是一個動作圖（Action Graph）。動作圖A是必須包含astart和aend兩個啞動作的規(guī)劃圖（Plan Graph）子圖，如果某個動作a位于A中，則它的前提和增加效果也在A中?？談幼饔脕硎聦?，領域動作的刪除效果用該領域動作和對應空動作的互斥邊來表示。線性動作圖（Linear Action Graph）的提出是為了便于求解，如果動作圖的每一個動作層至多包含一個領域動作和任意多個空動作，則該動作圖為線性動作圖。線性動作圖上動作的層數并不表示執(zhí)行的順序，不在同層的領域動作只要之間沒有也可以并發(fā)執(zhí)行。為了求解派生規(guī)劃問題，LPG-td定義了規(guī)則動作圖

26、（Rule-Action Graph）。規(guī)則動作圖是滿足以下條件的線性動作圖：1）每個事實層增加兩種結點：規(guī)則結點和派生結點。規(guī)則結點用基規(guī)則的來標記，派生結點用派生事實來標記。2）規(guī)則結點有出邊和入邊，入邊來自同層的形成規(guī)則條件的事實結點，出邊指向同層的由該規(guī)則所推導出的派生事實結點。規(guī)則動作圖能夠很好地解決動作刪除效果的“連鎖反應”，因為在規(guī)則動作圖中，規(guī)則的觸發(fā)條件和所推導出的派生事實之間有規(guī)則邊相連，當動作刪除了某一基本事實，可以根據規(guī)則邊來判斷是否要刪除該基本事實所推導的派生事實。如果不存在其他組的規(guī)則邊，則該派生事實被刪除，而由該派生事實所推出的其他派生事實也要依次考慮。規(guī)則動作圖

27、的方法不需要像編碼方法一樣引入大量的導事實或者條件效果。一個規(guī)則動作圖的例子如下圖所示：規(guī)則應用的推圖 3 規(guī)則動作圖的示例。矩形結點表示動作結點，橢圓形結點表示事實結點，包括基本事實和派生事實，菱形結點是規(guī)則結點。規(guī)劃問題的初始狀態(tài)是P1，P2，P3，P4，目標狀態(tài)是P7，P8 。圖中所示的有三條規(guī)則：(r1) P3d1，(r2) P6d3，(r3) d3P4d4。對于派生前提來說，如在本層中已經有規(guī)則推出，則是已支持的，反之，是未支持的。例如在第 3 層的d4 是已支持的，第 3 層的d2 是未支持的?！癿.e.”是互斥邊，表示動作的刪除效果，例如動作a2 的刪除效果是p3。在基于激活集的

28、方法中，動作的派生前提用其激活集來進行替換。在 LPG-td 規(guī)劃系統(tǒng)中，對派生事實的激活集定義如下：定義 1 在規(guī)則動作圖的某一層L中，如果存在一個還未支持的派生前提d，那么d的激活集是一個最小的基本事實集合F，使得S(L) F |=R d，S(L)表示組成層L的事實集合，R是基規(guī)則集。由此定義，可以看出，派生事實的激活集是指在當前狀態(tài)已有的事實的情況下，還需要哪些基本事實來推導出該派生事實。激活集是在當前狀態(tài)下未支持的基本事實集合，它引入到動作圖中，通過增加新的動作來支持它所包含的基本事實，可以產生規(guī)劃空間搜索的候選動作圖。一個派生事實在當前狀態(tài)下可以有多個激活集，所有激活集組成一個集合，

29、稱為激- 5 -活集集合。激活集是在規(guī)則圖（Rule Graph）上計算的。規(guī)則圖是由兩類結點組成的與或圖（AND-raph）：與結點是由基本事實標記的葉子結點或者由派生事實標記的結點，而或結點是由基規(guī)則標記的結點。對于一個規(guī)則結點來說，它的入邊（只有一條）來自于由該規(guī)則所推導的派生事實，而它的出邊（若干條）則指向該規(guī)則的所有觸發(fā)條件（由基本事實或派生事實組成）。在規(guī)則圖上計算某個派生事實的激活集，是與搜索過程和或搜索過程的交替進行。在與搜索過程中，如果當前結點是一個不在當前狀態(tài)的基本事實，則放到激活集集合中，如果是一個派生事實，則對它的每一個規(guī)則結點（或結點）調用或搜索過程。在或搜索過程中，

30、對于它的每一個觸發(fā)條件（與結點）進行與搜索過程。例如，在圖 4(a)所示的初始狀態(tài)和圖 4(b)所示的規(guī)則圖中，派生事實“Above(A, C)”的激活集集合是： =on(A,D),on(D,C),on(A,D),on(D,B),on(A,C),on(A,B)。BCAD(a) 初始狀態(tài)(b)基規(guī)則集和規(guī)則圖圖 4 一個BlockWorld實例的規(guī)則圖12.2 與狀態(tài)無關的激活集從以上激活集的定義和示例中，可以看出 LPG-td 所定義的激活集是與當前狀態(tài)有關的。從 LPG-td 規(guī)劃求解的算法上來看，在動作圖的去 flaw 過程中，如果出現(xiàn)了派生前提，則找出其在當前狀態(tài)下的所有激活集（And-

31、Search(g, , , , I F)，g 是派生事實，I F表示當前狀態(tài)，該函數返回激活集集合 ），對它們進行估值，找出一個最好的激活集（HBestActivationSet()）來替代該派生前提（GG - g H）。以以上例子為基礎，如果把木塊 D 和木塊 C 的位置調換一下，則當前狀態(tài)變?yōu)?table(A), table(C), on(B,D),on(D,C)，而派生事實“Above(A, C)”的激活集集合變?yōu)椋?= on(A,D), on(A,C),on(A,B) 。如前面所說，規(guī)則圖是一個比較龐大的數據結構，隨著規(guī)則實例數目的增多而指數級地增長，當動作的前提中包含較多的派生前提時

32、，需要反復到規(guī)則圖上去查找其在當前狀態(tài)下的激活集集合，因此，這部分的時間花銷是比較大的。為此，定義與狀態(tài)無關的激活集，一個派生事實的與狀態(tài)無關的激活集集合是唯一的，只需要在規(guī)則圖中計算一次。定義 2 一個派生事實d的與狀態(tài)無關的激活集（Se-Independent Activation Set, SIAS）是一個基本事實集合F，使得F |=R d，R是基規(guī)則集，并且不存在F，使得FF且F |=R d。把與狀態(tài)無關的激活集集合稱為*，在文獻【19】中，給出了一個算法（SIAS-search (d, A, Path, Open)），在規(guī)則圖上計算與狀態(tài)無關的激活集集合*。d是派生事實，A是構建中的

33、激活集，Path用來保存已過的派生事實結點，Open用來存放未的結點，該函數返回*。由于規(guī)則圖是有限的，該算法可以保證終止性和返回唯一的解。LPG-td所定義的激活集是與狀態(tài)相關的，相應地把它稱為Se-Related Activation Set（）,1已在當前狀態(tài)成立的基本事實不包含在激活集中，如on(B,C) r8 above(B,C)，above(B,C)on(A,B) r3 above(B,C)，on(B,C)已在(a)所示的初始狀態(tài)中，所以激活集為 on(A,B)。- 6 -由這樣的激活集組成的集合記為。*可以很容易地轉化為，算法描述如下：Algorithm. Transform (

34、*, S)輸入：與狀態(tài)無關的激活集集合*，當前狀態(tài)S；輸出：與狀態(tài)有關的激活集集合 。Begin(1) For every activation set A, sucht A *A A S, AFor every pair (B, B), sucht B, B If B B Then - BReturn End.例如，通過算法SIAS-search (d, A, Path, Open)，可以得到在圖 4(b)所示的規(guī)則圖中派生事實“Above(A,C)”的與狀態(tài)無關的激活集集合：* = on(A,D), on(D,C), on(A,D), on(D,B), on(B,C), on(A,C),

35、on(A,B), on(B,D), on(D,C), on(A,B), on(B,C)。假設當前狀態(tài)如 4(a)所示，經過上述算法的步驟(2)，激活集集合變?yōu)閛n(A,D), on(D,C), on(A,D), on(D,B) ,on(A,C), on(A,B), on(B,D), on(D,C) , on(A,B) ，再經過步驟(3)，則得到的激活集集合為on(A,D), on(D,C), on(A,D), on(D,B), on(A,C), on(A,B) ，這與LPG-td通過And-Search(g, , , , I F)算法所得到的激活集集合是一樣的。另外，從這個示例可以看出，對于同

36、一派生事實來說，*一般要比大，但是它的好處在于只需要在規(guī)則圖中計算一次，而當狀態(tài)發(fā)生變化時，需要在規(guī)則圖上重新計算。3規(guī)則集的“基化”如前所述，在派生規(guī)劃問題中，動作的派生前提可以用激活集來代換，但是激活集的計算時間開銷不容忽視。例如，PSR（er Supply Restoration）問題是IPC-4 競賽上包含派生謂詞的兩個基準問題之一，該問題描述的是在供電系統(tǒng)中，當某些電線出現(xiàn)故障，要重新調14。這類問題所包含的動作和規(guī)則都非常多，整電源開關給受影響的設備和線路供電如一個最小的實例（PSR/MIDDLE/DerivedStrips/P01_.PDDL）包含 30 個基動作和 503派生規(guī)

37、則，而規(guī)模最大的實例（P50_.PDDL）包括 5214 個基動作和 7450派生規(guī)則。動作的前提中大部分也是由派生事實所的派生前提，激活集的計算非常地頻繁，在規(guī)劃求解的總體時間中占有不小的比例。因此，本文的工作是在保留規(guī)則動作圖的總體求解框架的前提下，提出一種計算激活集的高效方法。計算過程采用動態(tài)規(guī)劃的體框架如下：，總查表在表中d的*不在表中基化更新規(guī)則圖中基于 *的規(guī)則- 7 -在規(guī)則圖中計 算*將新得到的所 有派生事實（包括d）的*加入 Lookup表中 = Transform (*, S)Lookup 表中存放 已求出*的派生事實求派生事實 d 在狀態(tài) S下的圖 5 采用動態(tài)規(guī)劃的來計

38、算激活集因為在給定的基規(guī)則集中，一個派生事實與狀態(tài)無關的激活集集合*是唯一的，并且固已經給出了*和之間的轉換關系，定不變的，因此可以把它存在一張查找表Lookup中在規(guī)劃求解過程中，如果要求某個派生事實d在狀態(tài)S下的，先檢查一下d的*是否已求出。如果已求出，則利用算法Transform (*, S)得到。如果沒有求出，則在規(guī)則圖上利用SIAS-search (d, A, Path, Open)過程找出d的*。在圖 3 所示的總體框架中，有一個步驟是非常重要的，稱為“基化”（Ground Out），這是因為當派生事實d的*求出來之后，通過規(guī)則集R下的規(guī)則推導，可能會推出其他一些派生事實的*，這樣

39、可以順便得到這些派生事實的*。把它們在查找表中，如果以后要用到這些派生事實的，可以直接從查找表中得知其*，就不需要在規(guī)則圖上計算了。在規(guī)則圖上計算激活集的時間是指數級的，在查找表中查找是線性時間的，當求解過程進行了一段時間后，大部分的派生事實的*已登記在表中，這時整個規(guī)劃的求解時間就會大大縮短了。下面具體來介紹“基化”的概念和過程?！盎边^程的依據是基化前后兩個規(guī)則集是等價的。定義 3 兩個規(guī)則集R和R是等價的，當且僅當對于任何一個命題集合F和任意命題p，如果有F|=R p，則有F|=R p，反過來也一樣，如果有F|=R p，則有F|=R p2。定理 1 設有一命題集合P1, P2,Pn，每

40、個Pi(i=1,2,n)都在規(guī)則集R的至少一條規(guī)則中出現(xiàn)，如果有P1, P2,Pn|=R C，對于規(guī)則集R將所有形如“B1 B2 BkCD”的規(guī)則 r，分別用新的規(guī)則r“B1 B2 Bk P1 P1 Pn D”來進行替換，得到一個新的規(guī)則集R，則R和R是等價的。證明：對于任何一個命題集合F和任意命題p，如果有F|=R p，設推導路徑為r1, r2,rm，ri R（i=1,2,m）。分兩種情況：（1）如果存在ri = r（1im），則ri R。因為P1,P2,Pn|=R C，則存在推導路徑為r*1,r* ,r* ，r* R且r* R（j=1,2,o），所以原推導路2ojj徑r1, r2,ri-1

41、,ri, ri+1,rm可以轉化為r1, r2,ri-1,r* ,r* ,r* , r,r ,r ，其中r R且r R1 2oi+1mj（ji），F(xiàn)|=R p；（2）如果任何ri r（1im），則ri R（i=1,2,m），所以F|=R p。因此，無論哪一種情況，都可以得到結論：如果有F|=R p，則有F|=R p。反過來，如果有F|=R p，通過與以上類似的證明過程，可以得到F|=R p。因此，根據定義 3，R和R是等價的。以上定理表明，兩個規(guī)則集是等價的，意味著在派生規(guī)劃問題中將規(guī)則集進行等價的變換，則不改變原來的規(guī)劃問題。定義 4 設派生事實d的*已知，如下圖所示：P11, P12, ,

42、 P1,k1P21, P22, , P2,k2Pn1, Pn2, , Pn,knk1, k2,kn均為正常數，Pij均為基本事實。對于規(guī)則集R中任何形如“B1 B2 BmdD”的規(guī)則r，都可以產生n的規(guī)則ri :“B1 B2 Bm Pi1 Pi2 Pi, ki D”, i=1, 2,n。這稱為基于派生事實d的*的規(guī)則。根據定理 1，基于派生事實d的*的規(guī)則所產生的規(guī)則集和原來的規(guī)則集是等價的。這樣的規(guī)則共有兩種情況，如下圖所示：2“F|=R p”是指命題p可以由F在規(guī)則集R下推出。- 8 -d1d1d2(a)d1d1d3d2d3(b)。黑色圓圈表示派生事實，白色圓圈表示基本事實，八角形表示激活

43、集，為了簡便圖 6 基于*的規(guī)則起見，圖中只畫了兩個不同的激活集，分別用白色和灰色表示。圖 6 是一個簡化的規(guī)則圖，同一規(guī)則用與邊來表示，不同規(guī)則用或邊來表示。圖 4(a)和(b)均表示在派生事實d2 的*（共有兩個激活集）求出來之后，由于派生事實d1 的規(guī)則條件中包含了d2，因此對d1 的該規(guī)則進行。在圖 4(a)中，之后d1 的規(guī)則中只包含基本事實，因此實際上是求出了d1 的兩個與狀態(tài)無關的激活集。而在圖 4(b)中，d1 的規(guī)則中還包含其他的派生事實d3，如果稍后d3 的激活集也求出來了，再進行規(guī)則到d1 的激活集。，就可以得*定義 5 當某個派生事實d的d 通過規(guī)則圖計算得出之后，對規(guī)

44、則集進行基于d 的規(guī)則*。如果因此得到其他的派生事實d1, d2, dn的激活集集合，分別記為d1 , d2 , dn ，*則對規(guī)則集進行基于di 的規(guī)則（i=1,2,n）。此過程不斷地進行，直到不再產生新的派生事實的激活集集合為止。這個過程稱為規(guī)則集的“基化”。對規(guī)則集進行基化，其目的是使得規(guī)則的觸發(fā)條件盡可能多地包含基本事實而減少派生事實，以便于激活集的計算?；^程的算法描述如下：*Algorithm. Ground_out (DL, d , R, Lookup)*輸入：派生事實列表DL，d的與狀態(tài)無關的激活集集合d ，規(guī)則集R，查找表Lookup；輸出：規(guī)則集 R，查找表 Lookup

45、。 BeginOpen d; Open* d*While Open Dod *_member(Open) ; d _member(Open*)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)End.Open Open d; Open* Open* d*Lookup Lookup (d, d )For every rule r R, sucht r: p1 p2 pk dC*For every activation set A d , A is a1, a2,anr = p1 p2 pk a1 a2 an C R R r rR refine(R, d);For

46、every d DL, and d appear in R If all_basic_precondition(d) Then* find(d)dOpen Open d; Open* Open* d *在上述算法中，函數_member表示取列表中的第 1 個元素。函數refine是對規(guī)則集進行精- 9 -簡，具體的功能包括：1）刪除以d為結論的所有規(guī)則；2）刪除規(guī)則中不一致的條件；3）刪除重復出現(xiàn)的規(guī)則。因為d的所有激活集已全部登記在Lookup表中，并且規(guī)則集中的d已被其激活集取代，所以規(guī)則集中不需要有推導d的規(guī)則，對應上述的功能 1）。當激活集引入到規(guī)則的條件中，可能會跟原有的條件，例如B

47、lockworld領域中，如果規(guī)則條件中同時出現(xiàn)on(A, B)和on(B,A)，則為不一致的規(guī)則條件，因此需要上述功能 2)。引入的規(guī)則可能跟原有的規(guī)則重復，所以需要上述功能 3）。此外，函數all_basic_precondition是檢查某個派生事實的所有規(guī)則的條件是否全為基本事實，如果全為基本事實，則調用find函數給出其激活集集合，find函數只需把每個規(guī)則條件部分所包含的基本事實合并為一個激活集即可。通過“基化”過程，原先的規(guī)則集實際上 為兩部分：精簡規(guī)則集和用來存放*的查找表。下面通過一個具體的例子來看看這樣的“基化”過程。以圖 4(b)中的規(guī)則集做為初始規(guī)則集，已知派生事實“a

48、bove(A, C)”的*已求出：*above(A, C)on(A,D), on(D,C),on(A,D), on(D,B), on(B,C), on(A,C), on(A,B), on(B,D), on(D,C), on(A,B), on(B,C)，在經過步驟(6)(9)和步驟(10)的功能 1)之后，規(guī)則集的變化如下（變化部分用粗斜體表示）： r4, 1: if on (D, A) on (A, D) on (D, C) then above (D, C)r4, 2: if on (D, A) on (A, D) on (D, B) on (B, C) then above (D, C)

49、r4, 3: if on (D, A) on (A, C) then above (D, C)r4, 4: if on (D, A) on (A, B) on (B, D) on (D, C) then above (D, C)r4, 5: if on (D, A) on (A, B) on (B, C) then above (D, C) r5: if on (D, C) then above (D, C)r6: if on (D, B) above (B, C) then above (D, C) r7: if on (B, D) above (D, C) then above (B, C

50、) r8: if on (B, C) then above (B, C)r9, 1: if on (B, A) on (A, D) on (D, C) then above (B, C)r9, 2: if on (B, A) on (A, D) on (D, B) on (B, C) then above (B, C) r9, 3: if on (B, A) on (A, C) then above (B, C)r9, 4: if on (B, A) on (A, B) on (B, D) on (D, C) then above (B, C)r9, 5: if on (B, A) on (A

51、, B) on (B, C) then above (B, C)規(guī)則r4和r9中包含“above(A, C)”，因此對它們要進行基于*的規(guī)則above(A, C)的功能 2)之后：r4, 1: if on (D, A) on (A, D) on (D, C) then above (D, C)r4, 2: if on (D, A) on (A, D) on (D, B) on (B, C) then above (D, C) r4, 3: if on (D, A) on (A, C) then above (D, C)r4, 4: if on (D, A) on (A, B) on (B, D

52、) on (D, C) then above (D, C)r4, 5: if on (D, A) on (A, B) on (B, C) then above (D, C) r5: if on (D, C) then above (D, C)r6: if on (D, B) above (B, C) then above (D, C) r7: if on (B, D) above (D, C) then above (B, C) r8: if on (B, C) then above (B, C)r9, 1: if on (B, A) on (A, D) on (D, C) then abov

53、e (B, C)r9, 2: if on (B, A) on (A, D) on (D, B) on (B, C) then above (B, C) r9, 3: if on (B, A) on (A, C) then above (B, C)r9, 4: if on (B, A) on (A, B) on (B, D) on (D, C) then above (B, C)r9, 5: if on (B, A) on (A, B) on (B, C) then above (B, C)刪除線部分是不一致的條件，當謂詞的實例不允許產生循環(huán)鏈時，則出現(xiàn)了不一致的規(guī)則條。經過步驟(10)- 10

54、 -件。經過步驟(10)的功能 3)之后： r4, 1: if on (D, C) then above (D, C)r4, 2: if on (D, B) on (B, C) then above (D, C)r4, 3: if on (D, A) on (A, C) then above (D, C)r4, 5: if on (D, A) on (A, B) on (B, C) then above (D, C) r6: if on (D, B) above (B, C) then above (D, C)r7: if on (B, D) above (D, C) then above (

55、B, C) r8: if on (B, C) then above (B, C)r9, 1: if on (B, A) on (A, D) on (D, C) then above (B, C)r9, 3: if on (B, A) on (A, C) then above (B, C)r9, 4: if on (B, D) on (D, C) then above (B, C)此時，查找表Lookup上登記的 是(above(A, C), *above(A, C)，因為all_basic_precondition (above(B, C)和all_basic_precondition (ab

56、ove(D, C)均不為真，因此基化過程結束。為了更進一步說明基化過程的優(yōu)點， 假設在隨后的過程中求出了派生事實“above(B, C)”的*為：*above(B, C)on (B, C), on (B, A), on (A, D), on (D, C), on (B, A), on (A, C), on (B, D),on (D, C), on (B, D), on (D, A), on (A, C)，在經過了基化過程的步驟(6)(10)后，規(guī)則集為： r4, 1: if on (D, C) then above (D, C)r4, 2: if on (D, B) on (B, C) the

57、n above (D, C)r4, 3: if on (D, A) on (A, C) then above (D, C)r4, 5: if on (D, A) on (A, B) on (B, C) then above (D, C)r6, 1: if on (D, B) on (B, C) then above (D, C)r6, 2: if on (D, B) on (B, A) on (A, D) on (D, C) then above (D, C)r6, 3: if on (D, B) on (B, A) on (A, C) then above (D, C)r6, 4: if o

58、n (D, B) on (B, D) on (D, C) then above (D, C)r6, 5: if on (D, B) on (B, D) on (D, A) on (A, C) then above (D, C)整理一下為：r4, 1: if on (D, C) then above (D, C)r4, 2: if on (D, B) on (B, C) then above (D, C)r4, 3: if on (D, A) on (A, C) then above (D, C)r4, 5: if on (D, A) on (A, B) on (B, C) then above

59、 (D, C)r6, 3: if on (D, B) on (B, A) on (A, C) then above (D, C)可以看到，all_basic_precondition (above(D, C)為真，因此查找表Lookup上登記的是*above(A, C),*above(B, C),*above(D, C)，其中，(above(A, C),(above(B, C),(above(D, C),*above(D, C)on (D, C), on (D, B), on (B, C), on (D, A), on (A, C), on (D, A), on (A, B),on (B, C

60、), on (D, B), on (B, A), on (A, C)。此時，規(guī)則集為空，原始規(guī)則集（圖 4(b)）等價于此時的查找表。以上示例表明，在從規(guī)則圖上計算出某個派生事實d的d*后，可以通過*“基化”過程順便找到其他派生事實d的d ，這大大減少了查找激活集的時間。4實驗比較基于以上方法，實現(xiàn)了一個新的能夠求解派生規(guī)劃問題的規(guī)劃系統(tǒng)LPGSIAS，它是在LPG1.2 規(guī)劃系統(tǒng)6上改編的。LPG1.2 規(guī)劃系統(tǒng)參加了IPC-3，在自動規(guī)劃系統(tǒng)系列中獲得了杰出性能獎，但它不能求解派生規(guī)劃問題，LPG-td是比它更新的版本，但是尚未源代碼。LPG1.2 的時態(tài)動作圖擴展為規(guī)則動作圖，采用LPG