那接下來我們談論一個叫做Planning Graphs的東西，那Planning Graphs呢它基本上是

類似像PDDL有的概念所產生的一個Graph，那這個Graph的重點是什麽呢？它可以產生

保證產生admissible的heuristic，因爲就有點像我們剛剛講的就是，我們剛講的那方法，就是heuristic

decomposition，然後缺點就是直接，你直接做你不知道怎麽把goal去做decomposition，那Plan-

ning Graphs可以幫你某種程度上suggest你做到這件事情。

好，那等一下我們先講一下Planning Graphs怎麽產生heuristic，那之後我們最後

一部分會講到，其實你也可以直接在Planning Graphs上做search，而不是在PDDL上做search

這個不同的方法有不同的優缺點。

那Planning Graphs基本上很有趣的事情是它先把 graphs先organize成levels，然後它有兩種level，一種叫做S-

tate level，就兩種，一種State level，一個叫 Action

level，那它基本上是互相是interleave的，就是你一個 State level後面一定接著一個Action

level，那Action level後面接著State level，所以基本上你看起來會像這個樣，從S0然後到A0，然後

就是簡單講，就是S level S0，然後你做所有很多可能的Action

然後你會得到S1，然後之後再做A1，然後你到S2，然後這樣一直點點點，點下去好，那

我們會，基本上我們會有一個Action，我們會產生一個我們叫做persistence action，或者我們也簡稱

no-op，也就是説你可以在某個state你可以不做任何事情，那它所有的狀態就會保- 留到下一個

level，那還有一個很重要的事情就是你必須要compute我們稱爲mutex的東- 西，mutex

link就是某些狀態，action也有，就是某些狀態不可能同時存在

最簡單想法就是，比如説你A跟Not A它不可能同時存在

那Action也會，就是某些Action它不能同時做到，等一下我們會介紹這個東西。

好，那我們這個Graph，Planning Graphs

這樣往下做，要做到什麽時候呢？這下面是S2嘛，然後再來是A2 好，點點點點點。

你要做到什麽時候呢？你一直做下去，遲早你會發現有兩個State level是

一樣的，是identical，遲早你會做到這件事情，那我們其實會跟你講，它一定會做到這個，一定遲早會發生

那如果到這個時間，我們就停止，那這個時候我們就稱爲這個graph叫做leveled off

好，因爲很明顯的，如果任兩個 state level它們是一樣的話，接下來你就一直重複，就是如果如果從，譬如說

S1，然後經過一個Action的話，跟S2，假設這兩個是identical的

那從S2做所有可能的Action，到下面一個S3，一樣會，這個一樣會相等，這兩個都- 一直相等下去

好，等一下我們會看到這是什麽東西。

好，那我們現在舉一個例子，這是課本一個很簡單例子，這當然也是一個英文諺語，就是Have

cake and eat it too，那基本上就是怎麽翻譯，就是大概什麽都想要，什麽都占盡了

不過這是當然開一個玩笑，就是反正也許可以做到，那所以我們目標呢

Initially就是你有Have(Cake)，那我們的goal就是你要Have(- Cake)，而且又Eaten(Cake)

所以這聽起來有點奇怪，如果衹有一個蛋糕，那你要吃完了，還要有。

所以很明顯的我的Action呢必須要有一個，就是除了Eat(Cake)之外，我還有一個Action，就是我可以Bake(-

Cake)，那我可以再烤一個蛋糕出來，所以我可以吃掉蛋糕，然後再烤個蛋糕，所以我就Have cake and

eat it too，okay？好，那這邊你可以看下一些precondition應該蠻簡單的，我們先看一下這整個問題

也就是PDDL所定的整個problem，那Initially你有Have(Cake) 我的Goal是Have(Cake) and

Eaten(Cake)，那我的兩個Action，一個Eat(Cake)的Acti- on，那

你要Eat(Cake)你的precondition就是你必須Have(Cake)，- okay？那你如果吃掉了，那你就Not

have(Cake) 然後而且你的狀態會變成Eaten(Cake)，你吃過cake了，然後你沒有cake

好，那你也可以Bake(Cake) 好，那precondition是你沒有cake，你才能Bake(Cake)，這個問-

題裏面的設定就是你不可以有兩個cake，就是你一定要一吃掉你才能，你才能你才能Bake，好，那你如果precondition這樣，那你Bake(Cake)-

以後，你就會得到的Effect就是Have(Cake) 好，定義這些東西之後，我們產生的，我們接下來，上面是PDDL

我們base on這個PDDL，我們可以建造下面的這個Planning

Graph，就是這下面這整個東西接下來我們就要秀給你看就是這整個東西是怎麽

做到的，第一個是一開始呢是一開始基本上我先把所有可能的，所有

可以在時間里發生的所有的ground狀態全部把它列上去，然後接下來

我把所有可以做的Action就列在A0，然後接下來S1就是它們所做到的

所以initial的時候，大家可能參照就這張投影片，一起看，initially你有-

哪個狀態就是我們說S0，就是你在時間0可以發生的事情，基本上就是Have(Cake)

[空白_錄音] 然後同時你要把所有的狀態，我說所有，那包含你還沒有吃過

[空白_錄音]

你還沒有吃過，這是時間0所有可以發生的事情，那你的A0呢？

好，你先看一下你的A0可以做些什麽事情，因爲你是Have(Cake)，你現在衹有兩個Action，所以你基本上A0可以做什麽，你唯一能做的事情就是吃Cake

好，你還不能Bake(Cake)，因爲你要Bake(Cake)的話，你沒有它的pr- econdition

沒有Bake(Cake)的precondition，Bake(Cake)的prec- ondition是Not

have(Cake)嘛，那它沒有發生在S0 所以你不能做，所以你可以做一件事情就是Eat(Cake)

好，Eat(Cake)它的precondition是

這一個，所以你把它，就可以連，這是它的precondition，那它的Effect- 呢，兩個

就是Not have(Cake)，以及Eaten(Cake)

[空白_錄音]

Okay，好，那這是我的S1，還沒有畫完，好那我們剛才有講到，就是説除了

除了原來的Action之外，我們還introduce新的叫no-op，就是你如果不做任何事情的話，你的狀態會live下去，就是你讓A0可以考慮

做Eat(Cake)動作，但你也可以考慮不做任何動作，所以你不做任何動作的話，我們- 是這樣畫

這是就是no-op的意思，那它的狀態仍然保留著Have(Cake)

[空白_錄音] 那這個的狀態一樣你可以做no-op，就是not

Eaten(Cake) 好，那這邊畫完這些就是所有

S1，你會發現S1，你會發現，你看一下S1，你會發現有點有趣，就是説這些狀態不可能- 同時全部出現，你不可能

Have(Cake)，也同時Not have(Cake)，所以這邊在一個Planning

Graph它的意義是什麽呢？它的意義其實就是説在S1 可以發生的全部的ground的literal全部放在這邊

就是它可以是positive或negative，就在S1的情況的時間，在Time1的時候，我可能是Have(Cake)，可能是

Not have(Cake)，Eaten(Cake)跟Not eaten(Cake)，就是説我可能去放在這邊

那同樣的道理，我就不再繼續，下面有點瑣碎，你可以試試看。

當你有這些狀態譬如說像這個情況你就可以，已經可以，在A1的時候你就可以做到

你就可以做到Bake(Cake)，在A0我們不能做因爲A0的時候，你沒有Not

have(Cake)，但在A1的時候，因爲你有Not have(Cake)，所以你可以

做一個Bake(Cake)的動作，然後你會得到Have(Cake)這個東西就是你可以用類似的做法，把A1做出來，把S2做出來

好，那這邊在這個圖上還有一些東西就是你們會發現這個灰色的這個link

這個link，這個link，我現在畫的這些東西，這個東西所謂的mutex，那mut- ex怎麽定義呢？

好，mutex怎麽定義我們看一下，mutex基本上我們先定義在Action上的

mutex，然後利用在Action上的mutex，我們再定義在State上的mut- ex，mutex的意思就是説這些事情是不可能同時發生

那大家可能會覺得爲什麽要先定義Action的，爲什麽不先定義在 State上的，因爲State上好像蠻明顯的，State上如果是A發生，你就不可以

同時發生not A，所以A跟not A在State上當然是mutex 可是我們等一下會看到我們爲什麽先定義在Action上，因爲其實有一些

State它其實不是complement，但是譬如說A和B，但是

它因爲Action的關係它也不可能同時發生，所以我們要找出這些東西來，所以我們會- 先定義在

Action上面，那Action上面基本上，我們先定義在 Action上，衹要這三個條件發生，就任意發生，我們都

把它，就都會劃mutex，基本上這三個就是我的條件了那第一個就是所謂的inconsistent

effect，就衹要這兩個Action的 effect，它們之間有互相爲negation

就是譬如一個Action它產生A，那另外一個Action產生Not A 那這樣的話，這兩個Action就不可以，就基本上就是一個mutex，那或是inte-

rference，好那interference就是某一個的 effect它是你get另外一個人的precondition

這樣的話我們就稱爲interfere，就是因爲你不能做這個再做那個，那另外一個就是competing

need，就是如果有一個action的precondition，它是它是A，那另外一個action的precondition是not

A，那這樣的話它們就是你們在compete嘛，在compete，一個要A，一個要not

A，那也不行好，其實這三個可能這有不同名稱了，這可能方便爲了記憶，但是其實很簡單地講就是

任兩個action，它們衹要effect和precondition之間互有nega- tion的狀態，它們就它們就是mutex，很簡單，就是這個樣子。

我們看一下我們剛剛這一個。

好，這邊其實像如果我們衹是看部分的話我們的A0的狀態衹有三個action，就是這個action，然後Eat(Cake)-

，還有這個這個action，那我們看一下，譬如說，譬如說像上面這兩個，這兩個是mutex

我這邊要畫一個mutex，爲什麽呢？因爲 Eat(Cake)它產生的結果有個not

Have(Cake) 那上面這個no-op，它產生有Have(Cake)，這兩個互爲negation

所以它們就是根據我們剛才定義它必須要有mutex，你也可以找別的了，別的講法。

譬如說這一個的precondition是 Have(Cake)，那這一個的結果有，effect有not

Have(Cake)，那這樣也行好，就是任何一個成立你都要mutex，那我也可以再看一下，這兩個也是mutex

好，這兩個是mutex的原因是，這個

Eat的結果產生了Eaten(Cake)，對不對？那no-op的結果產生not Eaten(Cake)

所以這兩個也是互爲negation，那你也可以再check一下，譬如說像這兩個

這兩個就沒有，這兩個no-op它基本上它們沒有mutex，因爲它們不管是，這前面這precondition是Have(Cake)嘛，那它的

effect是Have(Cake)，那這個precondition是not Eaten，它的effect是

not Eaten，那你會發現它們既沒有，都沒有互爲negation的狀態，所以這兩個基本-

上沒有mutex 好，我們把action的先畫出來，畫完以後，接下來我們就可以畫

畫state的mutex，好 state的mutex很簡單，就兩個條件，一個條件就是說如果你是A和not

A 那他們之間一定有mutex，它們不可以同時發生，那接下來就是inconsistent

support，就是説如果你能達成，譬如說A和B好了，你能達成A的所有，這要所有

所有的action，它全都是達成B的

action，它們之間全都是mutex，那這樣A和B它們之間就是mutex

也就假設，舉例而言，假設這邊有m個action可以達到A，這邊有n個action

可以達到B，那基本上你必須n乘上m所有的pair，它們這些action全都是m- utex

那A和B就是mutex，這樣聽起來很合理嘛，就是你所有達成A的手段跟達成B的這些

action，它們基本上全部都互爲mutex，那A跟B就是無法在這個時間點同時達成

好，我們來看一下在這個例子上，我們可以看一下，好

譬如說像這邊的話，很明顯這兩個就是mutex 好，這是因爲就是A和not

A，那這兩個當然也是 state上也是，那還有一些是，譬如說像

這兩個是，這兩個是，這兩個是的原因是因爲

這一個，達成這一個所得到的action是，唯一的action是Eat(Cake) 那這一個所唯一的action是這個no-op，那它們兩個是mutex

所以你這邊就必須是mutex，就達成這兩個的唯一的 action是mutex，那還有的話就是這一個

這個也是，這一對也是好，因爲要達成這一個，唯一來源就是這個action，要達成這個唯一的來源是這個ac-

tion，那這兩個action 是mutex，所以它們兩個就是mutex，那這樣這邊應該是這樣畫完，那其他的應該沒-

有畫應該就不是好，大家可以check一下。

那有興趣的同學就繼續往下畫，基本上你應該要能畫出跟原來

就是跟上面這個圖其實一樣的，建議，强烈建議了，因爲這個在這邊畫會很messy，但

各位同學在家裏拿一張大一點的紙，慢慢畫，慢慢check，應該可以把這個完全畫出來，-

就是這個可以畫出來，這個也可以畫出來 check一下，中間的mutex，裏面其實沒有很多，就是這幾個。

然後還有一個 check，我們爲什麽這個圖畫到S2就不再畫下去了呢，它有沒有S3？

其實有，等你畫到S3的時候，你會發現 S2跟S3長相完全一樣，那我們這邊講長相完全一樣，它要

包含它的mutex，也就是説像這裏，你看S1跟S2，它們有沒有一樣 S1出現了四個，Have(Cake)、 not Have(Cake)、

Eaten(Cake)、 not Eaten(Cake)其實都出現了，跟S2出現的是一模一樣的，但是它們的mutex狀態不同

你會發現S2少了幾個mutex，少了一個mutex，少了這個mutex 有沒有？也就是説在S1的情況下，Have(Cake)和not

Have(Cake)跟 Eaten(Cake)這兩件事無法同時發生，可在S2的時候，這兩個可能可以同時發生

好，這樣的話就是不一樣，我們是把mutex算進去，所以這是不一樣的，所以這時候還沒- level

off，那有興趣的同學繼續往下畫，你如果畫出S3，你會發現它們mutex的狀態跟S2也完全一-

樣，所以這時候我們的graph就 level off，我們就衹畫到S2。

好，我們剛剛介紹了就是從一個PDDL的problem，那我們怎麽樣把planning graph給畫出來，給做出來。

那接下來我們看一下我們需要多少的時間可以完成這個planning graph。

我們假設一個planning problem它基本上有L個literal，以及a個

action的話，那我們先看一下在state level的話，那最多最多state

level衹有 L個node，對不對？因爲你全部衹有，我全部衹有L個literal，所以你最多

衹有L個ground state，然後還有你把mutex也算上去的話，最多就是

L平方，就L乘L，其實係數有取2了，差不多就L平方的狀態，最多這麽多mutex

好，那每個action level呢它基本上最多有 action

level，所以最多有a個action，我剛才已經講a個action，那這邊我- 還加一個

L，L是怎麽來的呢？就是每一個，拉進的每一個 state level都可以有個no-op，所以這個東西其實就是no-op

的數量，最多最多，因爲我全部就是有個literal，那每個literal 都可以有個no-op，所以我的action，最多的action就是全部就是a加L個

好，那這些action裏面它的mutex有多少個呢？最多就是a加L嘛，然後你再

全部平方，全部就這麽多，我有這麽多action互相之間最多這麽多個mutex

然後再來就是那我有多少個precondition和effect呢？這也蠻明顯的，-

其實就是 a加L，我有這麽多個部分，然後乘上

L個，因爲我的condition和 effect就必須是state那邊，我有這麽多，在action

level有這麽多，那這是我state，你全部，假設就按全部都是它precondition和effect的話，那這些link最多也衹有這麽-

多，然後再加上precondition算一個嘛，effect算一個，所以就兩倍 link最多這麽多，就是這個就是這個部分

好，那我全部加起來，全部算完，然後再加上，假設我是，我的planning

graph衹是有n個level的話那你可以看得出來，就是，假設有n個level的話，那其實全部全部最多的size就是

衹有這麽大，就是O(n(a+L)²) 算這些東西，其實最後就是要跟大家講其實

planning graph，你給我個PDDL problem，然後我要做出一個就compute

從這裏compute出一個planning graph的時間其實是蠻低的，其實并不會花很多時間，我就可以把那個planning

graph給做出來好，那接下來

我們可以用planning graphs可以做什麽事呢？第一個我們可以直接做，最簡單最快的事情就是可以

用它來做heuristic，基本上第一件事情我planning graph一旦做完了以後，我可以馬上

decide說我的planning problem是不是solvable的，好，這個和這個decision是

semi-decidable，這個是semi-decidable，要注意一下，原因- 是因爲如果你原來

如果你原來的 PDDL你現在轉成planning

graph，那你如果在planning graphs上是unsolvable的，所謂unsolvable意思就是説你沒辦法在

你，它一定在finite的時間可以level off掉，那在level off掉之前你發現沒有你的，你的goal并沒有

可以同時存在的，就是它們，你的goal的這些ground 就conjunction

of 這些ground，你所需要的可能你的goal可能有negation了，但是你不管有沒有negation，這些東西它-

沒有辦法同時出現在最後一個state 好，就是它們之間有些mutex，等等，那如果是在planning

graphs上沒辦法沒辦法找到這樣的解的話，那你在原來的problem一定就是unsolvable

好，就是這一句話，這就你如果是unsolvable on planning

graphs，你就原本problem一定是unsolvable，那這個反之不亦然，所以我們

說這個decision是semi-decidable，也就是說如果原本的如果原本problem是unsolvable的話，你的planning

graphs上不一定是 unsolvable 的，原因是因為 Planning Graphs

它的限制比較少，舉例而言，我們可以下面舉個例子就是我們 Planning Graphs check

mutual text，它是 check 兩兩之間的關係，那它沒辦法 check 超過兩兩以上的

dependence，舉例，就是我們剛剛講的積木事件 block world

好，譬如說像積木事件，你要 On(A,B)，而且 On(B,C)，而且 On(C,A)

這個做不到嘛，在積木事件里我們沒有環狀的這種狀態。

你其實做不到這個東西，但是這是原本 problem is unsolvable，但你在 Planning Graphs

上無法發現這件事情因為它兩兩之間都是可以同時存在的，就是你可以

On(A,B) 而且 On(B,C) 嘛，這沒問題，那你也可以 On(B,C) 而且

On(C,A)，任兩個它都可以同時存在，但它沒辦法 Planning Graphs 無法發現這三個無法同時存在。

好，這是 Planning Graphs 的一個狀態。

所以你一旦做完，就是你把一個 PDDL 的 problem 你先做成一個

Planning Graphs，第一件你馬上可以講的事情就是，如果這個 Planning Graphs 是 unsolvable

的，你馬上就可以說這 problem，原始的 problem unsolvable，你根本就不用解

好，那接下來還有一件事情就是我們可以，第一個我們可以從上面來看你的一個

literal gi，然後我們看它說，它第一次出現在這個 Planning Graphs

在什麼 level，我們把那一個稱為它的 level cost 稱為它的 level cost。

我們舉例而言，譬如說，我們剛剛的 Have(Cake) and eat it too，那我們可以發現

就是 Have(Cake) 是 level cost 0，然後 Eaten(Cake) 是 level

cost 1，我們可以確定一下這件事情好，這是，Have(Cake)

的話在這裡好，第一次出現在這邊，就最早最早出現，好，那所以它的 level cost 是 0。

好，那 Eaten(Cake) 呢你會發現，在第一個時間，第 0 個時間也沒出現，它第一次出現在這邊

在這邊，好那所以它的 level cost，我們稱為 level cost 稱為

1，好，我們可以做這個動作好，那這個 level

cost 有什麼用呢？第一件事情就是，level

cost 一定是 admissible 的，就是，你如果，因為它是第一次，你會發現

Planning Graphs 它基本上就把所有可能在這個時間點所發生的 literal

全部列出來，所以將來只要發生了，第一次最早發生，它一定就你一定有辦法讓它發生。

那實際上要發生，可能也許要再久一點，但是這一定是 admissible的。

那，另外一個講法就是說，因為 Planning Graphs 基本上我們容許 multiple 的 action 在同一個時間點發生。

你會注意到，我們的 action 其實就譬如說像剛剛的例子，就是你可以在

A 1 的時候其實你可以做兩個動作，它並沒有說兩個動作不可以同時進行

所以基本上你只可能更快而不可能更慢，所以它基本上是 admissible 的

好，那如果，我剛才是說，我們剛才說它

admissible，它是我們是針對單一個 sub goal 來說。

如果我今天 care 的是 conjunction of 這些 goal 的話，就是一個 conjunction of

這些 goal，就我要 g1，而且 g2，而且 g3 等等等等，那我們可以用什麼方法？

第一個最簡單的方法就是你用 Max-level，Max-level 就是所有的 goal，那些

sub goal 的 level cost 的 Maximum 好，那因為剛剛我們提過嘛，每一個，每一個 sub goal

它基本上都是 admissible，那你取它的最大值還是仍然是 admissible，不可能高估，因為它只達成其中一個，所以它

admissible 但是跟實際值還差蠻遠的啦，你應該可以想象，假設我有 100 個 sub goal，那你只 Max 其中一個最大，那沒什麼用。

好那另外一個就是 Level sum，Level sum 最簡單，就是想法就是你

把它全部這些 goal 的 level cost 你全部 summation 起來，那

level，基本上它會比 Max-level accurate

很多，但是它沒辦法保證 admissibility，它可以高估

因為就一樣，你可能達成 g1 的可能不小心，你在做那個 action

的時候，可能不小心達成了 g3 這樣，所以它基本上不能保證是 admissible。

但是實際上呢，在 practice 上，就是實用上其實一樣，就是大家不要對 admissible 這件事太過太過執著。

就是我們在理論推導我們可以跟你講，如果 admissible heuristic

我們改成t，[聽不清]一些特性，但是實用上很多，因為 admissible

有一些仍然給我們很好 performance 好，這是第一個。

就是它仍然是可以用的一個狀態。

那接下來我們要談一個就是 Set-level，Set-level 其實是最好的，就是基本上它是，就是

你剛剛所有的 goal，它都出現，第一次全部都出現，然後

not mutually exclusive 就是它們彼此之間沒有 mutual text

的時候，假設你比如說三個 goal，那你就是要，你要，你就 check g1、

g2 g3 什麼時候第一次都出現，而且它們之間都沒有 mutual text，就這個都不可以出現。

那這樣的話就是，這樣的這樣的東西我們稱為 Set-level，那 Set-level 基本上是，仍然是

admissible，好，這個可以，可以，可以知道啦，因為就像我們剛剛講的，它可以儘管

g2、 g3 它們如果都沒有 mutual text，它們同時出現，那隻是代表在這個時間點可能出現

它仍然不一定保證能出現，就是我們剛才講，Planning Graphs 它有幾個問題，第一個是它同時可以執行若干個

action，而且它不能發現兩兩以上的 dependence，就像我們剛剛講的，On(A,B)

嘛，On(B,C)，On(C,A) 其實是不可以發生的，但是，但是 Planning Graphs

它無法發現它不能發生好，那這樣的話其實 admissible，而且我們可以，這個很容易證明啦，dominates

之前的 Max-level 就是當然這樣的話，當然 dominate 一定會大於等於之前的

max-level 嘛，就是所有裡面最大的那一個值好，那如果你希望這個 Summantion

能更準的話，還有一個辦法，你可以做serial 的 planning

graphs，我們剛才在一直強調 planning graphs 它沒有禁止說同一個時間點

只能有一個 action，所以你可以把這個特性加上去，那這個會造成，這樣的東西我們稱為

serial planning graph，那 serial planning graph

怎麼做呢？就是你把每個不是 No-OP 的 action 就是 No-OP 是我們自己加的嘛，那不是

No-OP 就是真正的 action 之間它們絕對都是 mutual text，你就直接把它加上去。

就我們上面那個例子的話也就是說，在這一個時間點，在這個時間點，這是真的

action，Bake(Cake) 是真的 action，然後 Eaten(Cake) 是真的

action，所以這兩個無條件你就加一個 mutual text 上去好，那當然你加上去以後，你的

state 上面有沒有新的 mutual text，你要再去檢查看看，所以 mutual

text 就會變多，那這樣的話，你這個 heuristic 其實會變得更準一點，OK

8-4 Planning Graphs

人工智慧(Artificial Intelligence)

Rencontrer les enseignants