A1筆記 41 - Planning Domain Definition Language (PDDL)

Classical Planning

之前提過search agents，這當然也是planning的一種，不過這依賴domain knowledge，因為state是完全atomic的，也就是state不能參數化，一個獨特的representation只能表現一個state。

logical agents不需要domain specific knowledge也能plan，但是依賴ground truth(knowledge base)的inference，ground truth可能多到無法計數。

這邊要提的是可以參數化表現的state，利用所謂的PDDL語言（Planning Domain Definition Language)。

PDDL States

這邊先介紹一個名詞 fluent，意指某個為真的boolean value，用來描述某個state的variable。
所以一個state其實就是一堆fluents的交集(這種表示方法稱為factored representation，相對於不能拆成變數組合的atomic representation，例如用64個int組成的array來表現8-queens state)，例如某個包裹運送的state可能是以下兩個fluents的聯集：

fluents必須是atoms (terms)，不能是變數組成。

PDDL Actions

Actions類似以下的action schema:

一個所謂的ground action，意即不能有任何變數，所以一個ground action中的所有變數必須被atoms替換掉：

precondition可以看成是某個state s的truth subset，用邏輯術語來說就是s entails precondition of a:

當precondition對s來說成立的時候，我們說action a is applicable。

PDDL Result Function

action的effect相當於對state s的一個正負子集合，把相對於s中的負的fluents去掉，加上正的fluents。

PDDL Initial State和Goal Test

initial state必須要是atoms，也就是要明確，不能參雜變數去形容。但是goal倒是可以參雜變數，主要是可能多個atom替代的變數都滿足我們的goal需求，例如飛去SFO或是飛去LAX都是goal可以接受的atoms。Goal就是一個precondition，所以是一堆正或負literals的交集。

goal test:
所謂的找到goal，意思是發現一系列的actions，使得抵達某個state s entails goal。記住goal 也就一堆literals的交集，所以當所有goal中的literals都出現在s中，且都為真，那代表此state s也符合goal這個precondition了。

假設goal為：

對某個state s進行goal test:

會發現s entails goal，則此s為goal state (蠻幽默的，僅管rich and famous，達到目標了但是.....miserable)。


另外state:

entails goal:

Cargo Example

下圖是一個cargo planning problem:

Forware Search algorithm (progression) 

從initial state出發，探討所有actions造成的new states，然後再繼續重複此動作，所以ground actions (把所有參數填入所有實際可填的組合）可能會多到爆，意即branching factors太大了。

所以forward search通常需要domain heurisitics來縮減search space。

Backward search (regression)

從goal往回找，所以只會沿著能抵達goal的路徑（relevant states)前溯。不過這必須要有辦法知道如何前溯。PDDL state和action因為有特別寫入preconditions和effects，所以讓regression變得可能：

對前一個可能的relevant state g'來說，g'可能原本就有a的positive effects Add(a) 也可能沒有，但是g拿掉Add(a)得出的state保證是一個最低限度未受到action a影響的relevant state。

此外action a要能被g' apply的前提是 g' entails a的precondition，所以g'最低限度要包含所有Precond(a)中的fluents。

那為何不用把action a帶來的false fluents Neg(a)加回去g'呢？因為g'可能有也可能沒有Neg(a)中的fluents，如果g'沒有的話，把Neg(a)放回去有可能會造成g' 不entails Precond(a)。

舉例來說，假設goal state要包含此fluent:

則從這個fluent去找會造成包含這個fluent 的result的action，其中（沒有之一）就是：

plane p'是變數，因為任意plane組成的unload ground action都可以抵達goal state。

藉由regression，我們可以找一個合法的g':

如果要再regress到前一個g''，我們不用急著去把各個atomic plane帶入p' ，這會讓search branching factor增大，可以繼續讓p'保持變數，這樣branching factor完全不改變。這就是PDDL的好處。不過使用變數反而難以找出好的heuristics（是效能的關鍵），所以目前主流系統還是使用forward search。