A1筆記 42 - Planning Graphs for PDDL

Relaxing Problems

一個problem可以被所謂“relaxed"，意指把忽略某些problem定義的條件，變成一個更好解決的問題，而且在relaxation的過程中，可以自動產生admissible domain-independent heuristics來幫助解題。

Heuristics for planning

PDDL是使用factored representation來表現state，所以某一些factor fluents的組合可以拿掉(所謂拿掉就是某個state的ground fluent用variable取代）變成一個relaxed representation，意即problem也被relaxed了。這樣我們能夠程式化做relaxation，而相對應的heuristics會從中長出，這樣能夠達成 domain-independent heuristics。

如果search過程是一個graph，這相當於把一些相同屬性的node group起來變成一個更大的abstract node，形成一個更abstract graph。所以graph變簡單了，因為抵達goal state的path可能大大縮短（對abstract graph而言）。

另一個可能縮短抵達goal state的方式就是在search graph中加入edge，直接跳過某些nodes，這在PDDL裡面可以由忽略action的precondition來達到，因為這意味著所有的action都對所有的states applicable，這事實上產生了所謂“ignore precondition heuristics”，這是最relaxing problem的方法之一，一但任何action都能apply在任何state，則從initial state抵達某個goal state的過程，相當於只要考慮action effects是否能滿足此goal state包含的fluents。(這變成一個set cover problem，其實是NP-hard，但是有不一定保證admissible的greedy algorithm可以linear time approximate）。

如果只忽略action precondition的subset，也能達到relaxing problem的效果，在PDDL裡面，action schema已經清楚列出action preconditions，所以這個relaxation能夠程式化，不需要人腦介入。

Planning Graphs

簡單來說planning graph就是一個admissible planning heuristics，用來估計從initial state抵達某個state G所需要的步數 ，不過planning graph不能回答從initial state出發是否一定能抵達G，但是它可以確認“無法從initial state抵達G"的情況，因為一但graph建立完成，如果goal state沒有出現在graph中，表示這個problem是無解的。

舉一例來說：

planning graph是一個directed graph，有以下state->action交錯的level 結構：

基本上就是state level -> action level -> state level -> action level ... ，action壹定要applicate to it parent state，然後child state就是action result，一直循環下去直到actions再也產生不了新的states（上圖中的S2和S1一樣），此時我們稱graph leveled-off。

當然某個state也可以選擇不作動(no-op)，稱為persistent action，這樣state就會原封不動複製再下一個state。

上圖中某些level會有灰線連接不同的actions或fluents，這表示“disjoint"，不能同時發生的，或說"mutually exclusive" or "mutex"。

簡單來說，每個level Si包含了所有Action Ai-1能夠造成的fluents / terms / literals，而且也包含了哪些fluents互斥的關係。同樣的，每個level Ai也包含了所有可以對state Si-1 作動的actions (包括no-op)，以及記錄所有互斥的actions。

Mutex relation

對mutex actions來說，定義如下：

對mutex literals來說，除了是彼此的negation之外，另一個可能就是mutex actions造成的literals勢必也是mutex literals，因為不可能同時發生此兩個actions。

planning graph的size growth = polynomial。

Level sum heuristics using planning graphs

level cost: 從initial state s出發，抵達某個literal gi第一次出現的state，經過的level count 就稱為level cost，其實就是graph中的state level index（記住applicable action level index與其parent state level index相同）。

level sum heuristics: 為了使用heuristics來簡化問題，我們使用"subgoal independence assumption"這個假設為前提，其意義是一個問題可以分解成獨立的許多小問題分別獨立解決，而total cost = sum(這些所有小問題的cost)。在這個前提下，我們可以用sum of level costs來逼近真正問題的解決cost，因為每次一但發現了某個goal literal，相當於解決了一個subgoal，而且也知道其cost。最終goal literals = 聯集(這些分別的goal literals)，cost = sum of level costs。

我們的例子中，goal literals包括：

根據建立的planning graph，Have(Cake) 的level cost = 0，而 Eaten(Cake)的level cost = 1，所以此goal的level sum = 0 + 1 = 1。不過如果對照planning graph，正確的cost實際上是兩個actions才能抵達：

不過本來這個heurisitics只能說是admissible，本來就不是true cost。