code

2017年4月22日 星期六

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。


沒有留言:

張貼留言