大家好，我們上兩講講了 propositional logic以及first-order logic，都是屬於邏輯的範疇，那它們 使用邏輯的方式對問題做一些描述，那我們在這一講所要提到的是 planning，那planning基本上使用了邏輯上的概念，那針對問題的描述- 特性做更 有效的應用，那它對應到課本的部分是10.1到10.3的 地方。 那首先我們會先提一個叫做Planning Domain Definition Language 簡稱PDDL，那PDDL它、 如果我們使用PDDL來描述問題的話，那這整個問題會有一個比較結構化的 方式，那基本上我們之後可以直接使用PDDL描述完的問題直接在 State-Space上去做Search，那當然我們在做search的時候最重要的- 一件事情就是有個heuristic，那 這也是我們為什麼需要使用PDDL的 技巧的原因，那就是如果使用first-order logic以及propositional logic的話，其實我們沒辦法很容易產生一個很好的heuristic 基本上你會需要一些domain的knowledge。 那如果你使用DPPL來描述問題的話，一旦你描述問題完成了，那我們等一下會看到的就是 就是我們可以使用一種、 一些方式做到，我們稱為 a problem domain independent 的heuristic，那接下來，我們可以使用這樣的heuristic建一個所謂pl- anning graph，我們使用planning graph可以 幫助我們更有效率地拿到這樣的heuristic。 那最後我們介紹一個graphplan 這個演算法，那這個演算法其實直接可以在planning graph上做search，然後直接解掉問題 好，首先我們為什麼要做planning呢？那基本上我們對一個問題，那我們使用 搜尋的方式，那它的結果就是產生一個一連串，一個sequence of action，那基本上從initial state 經過這一連串的動作以後能夠帶領你到goal state 那我們在做search的時候最基本需要兩個東西，一個就是 對于每個state我需要一個atomic的representation，那我不希望- 對於同樣的 state我有兩三種或多種以上的表示法 因為這樣會增加search的困難度，你可能search到你認為是不同的state- ，但其實 在意涵上是同一個，所以我們希望它是一個atomic的方式。 那接下來就是、 第二個就是在你來做search的時候，你需要一個好的heuristic，一旦你 有好的heuristic，通常講好的heuristic，typically，我們指 的就是admissible，那我們在前幾講在astar那邊我們對admissibl- e的heuristic有一些 比較深入的探討。 好，那如果我們使用，我們考慮 一下，如果我們使用前兩講的這些logic的方式來做會怎麼樣呢？ 如果我們使用propositional logic來做的話 那第一個事情就是我們要domain，domain specific的 heuristic，這是第一個，那第二個事情是你的表現手法還是 還是太過複雜。 好，就是基本上你會，你propositional logic它是ground choose，所以它基本上是variable-free的 inference，所以像，大家如果想象一下像我們在wumpus world，就是那個有怪獸的 迷宮裡面，那基本上你有四個action。 那你有四、 然後每個你的agent那裡走的時候，你有四個方向 再加上你有time step，你有時間軸，再加上你有n乘n，假如說我們一共是 n乘n的square的話，那基本上你需要這麼多就是，就是四個 位置，然後加上T一個step，然後加上n square的location，你需要用這些東西來 表達，那基本上會非常地浪費時間，那n很大的時候，你這個 這個ground inference會非常非常多，沒有效率，假如說我們想象如果一個迷宮是 100萬乘100萬的話，那基本上這是一個非常難做到的事情。 那 我們在first-order logic的時候，我們有看到有比較的方式，因為它 介紹了variable嘛，介紹了變數以後，我們比較能描述譬如說像只要有 wumpus的格子，那旁邊你會聞到wumpus的臭味，好，那或是像只要是 在pit的旁邊，就是在洞的旁邊的四周，那我們都會感覺到breeze，有微風的存在 好，那這是用有變數以後你可以比較有效率地表達 我剛剛所講的這些規則，但是first-order logic 等一下我們會看到的就是它沒有、 它不容易給你一個比較好的heuristic，但是PDDL 就可以，那這就是我們要談PDDL的主因 好，那我們介紹PDDL，首先我們要先講什麼是一個state，在PDDL裡面 一個state呢，它就是一個conjunction，就是and 然後，with ground，好，然後，就是沒有，不可以有variable，然後function-- less function-less的atoms，好，主要是這一些東西 好，那一個，然後PDDL一樣它採用了database的semantics 也就是我們接下來三個假設，就是close-world，好，close-world裡- 面講的就是只要 沒有被提到的任何東西都是false，只要沒有被提到 的都是不對的，不正確的，那接下來是unique names，就是只要 只要我講的是不同的名字，它基本上就是不同的人，譬如說我講一個是John，一個是Ma- rk，你可以 很安全地假設他們兩個是不同的，我指的是兩個不同的人。 那接下來是domain closure，也就是說只有 我的提到的東西它才存在。 好，這三個假設 database semantics其實我們之前有看到過，這邊再提醒一下 好，所以備上這個我們剛剛的定義，那你可以知道下面 這幾個都不是state，譬如說像這個 At(x, y)，好，就是x在y這個地方，為什麼呢？為什麼這不是一個 這不可以是個state？因為因為x和y，我們用小寫，習慣上小寫，那它就是，它就是v- ariable，它不是ground 好，它是變數。 好，以及像第二個，是¬Poor，¬Poor，因為我用大寫 Poor，那大寫的P，所以它基本上是ground term，但是它 仍然不可以是一個state，因為我們說必須是，不可以是 就atomic嘛，所以它基本上它不可以有negation在前面。 然後最後是像這個 At(Father(Fred),Sydney)，那這一個的問題是，我有了一個fun- ction，有一個function 好，那Father是個function，所以、 所以一樣不符合我們的定義 好，那接下來我們談一下什麼是一個action，我們剛講了 什麼是state，那我們接下來講什麼是個action。 那action基本上是 可以有變數的，變數在這個時候所用到，那我們稱為lifted的 representation，就是所謂可以有變數，那它基本上是一個subset of first-order logic的東西，是個subset of first-order logic，那 我們一個action，描述一個action的時候，我們需要幾件事情，一個是acti- on的名稱 然後就是，我們需要action的名稱，然後我們需要你定義的變數 以及你能執行這個動作所需要的precondition 以及做完這個動作所得到的效果，我們需要這四個部分 好，那譬如，舉例而言，我們在下面這個，這是一個action，這是一個PDDL的 action，那基本上是Fly然後(p,from,to)，那p還有from還有to- 前面都是小寫嘛 那意思就是，在這例子裡面就是它們都是變數。 那它的precondition呢，我們這邊指的是一個飛機，就是一個 飛機，那它可以，p是一個飛機，那它可以從from這個airport飛到to這個ai- rport 那它的precondition，第一件事情就是你的p，這個plane 是個變數，那它必須一開始要在from這個airport，就是At (p,from)，而且p是一個plane 好，p是個飛機，不然它不能飛。 那接下來，from是個airport，from是個airport 以及to是個airport，好，這幾個precondition統統符合的話，你就- 可以執行 把p這個plane從from fly到to這個airport，那它所造成的效果呢。 就是下面 所寫的，它的效果就是你飛完以後那p就不在 不會在from這個airport，而且p，p這個plane會在to這個airp- ort。 好，這樣的，這樣的定義就是 一個，這是一個例子，就是完整地定義一個在PDDL裡面我們說一個飛機p可以從from- 飛到to的action 好，那這個、 這個 action基本上有可被執行的情況下，那當然就是你的state必須要符合 我們的precondition，就是你這個action的precondition的- 定義，那一個action a 可以被執行，在一個state s可以被執行，這邊if only if 那我們之前講過的s entails precondition，a的precondition，那這entails是一個很- 重要的概念，我們在 logic，first-order還有propositional logic都談過，大家還記得嗎？就是如果說s entail 某個東西，後面precondition of a，那意思就是說只要 s為真的這些事件裡面，a的precondition 都為真，你可以把它想象成一種比較 非常廣義的implication，也就是在所有的事件裡面，s都imply imply a的precondition。 也就是只要s這個state是真的，也就是說我在這s這樣的state下 那a的precondition都為真，也就是說像我們剛剛的例子，p是個飛機 而且from是個airport，然後to是個airport，那在這些情況下我們就說 你在s可以執行a這個動作，那我們用之前的寫法就是，就是前面 這是之前的寫法，我們如果用search的時候，這是之前的寫法，那我們的條件就是 這個，這個entailment必須成立，在這個情況下，你在s這個state就可以執- 行a這個動作 好，那我們定義完了state，定義完了action 那接下來我們要能做search，我們要能做search的話還需要第三個，也就是tr- ansition 好，就是我如果在一個s，在一個s state做了a這個action以後，它會帶領我到 s'嗎？通常我們習慣上就是寫成譬如說s'然後等於譬如說result 好，(s,a)，這是我們之前的寫法，那我們在s 這個state做了a這個action以後，我必須能，我必須要能知道它帶領我們到下一- 個state去，好 那我們現在在PDDL裡面要怎麼定義這些東西呢？那我可以看到第一件事情是 我們剛剛的，所有的effect裡面 好，我們剛剛的effect裡面，你會發現，我們effect沒有規定要 不能negative，所以你的effect裡面可能有negative的part，然- 後可能有positive的part 好像我剛剛的例子就是你飛完以後那p就不在from這個airport，而在to這個a- irport，那我們把所有 負的，有negation的這些literal，我們都稱為，就是你把它集合起來我們稱- 為一個delete list delete list，好，那所有正的，positive literal，我們都稱為是add list，把它集合起來稱為一個add list 那你的result呢，s'，就你在a s這個state執行a這個動作以後，你會帶領到s'，這s'要 怎麼定義呢？大家記得嗎，我們剛剛講，s這個state是一堆，一堆 positive ground的conjunction，就是and 那接下來，我就是把所有a這個action所有的delete list全部拿掉 然後把裡面正的東西全部union回去，好，這樣就會到，帶領我到s這個新的state 那舉例而言，我們舉個例子，譬如說像 如果我的s是，譬如說 P1，說at P1在，等一下我們看到譬如說San Francisco這個airport 好，那這是現在飛機一個P1，我用大寫的P，所以是，P1是一個飛機，然後 SFO當然也是一個機場，那它有些and我就不寫了，就是 就是你要知道就是，而且P是個plane，P1是個plane，而且 SFO是個機場，好，那如果我做了一個動作就是fly，譬如說我做了fly P1從SFO我飛到JFK 好，如果我做這個動作，那基本上你會知道這個effect就是減掉，你會減掉 這個At (P1,SFO)，然後你會union回去 At P1的JFK 你會做這個動作，如果我做這個，這個fly這個動作，那最後得到的結果很明顯，這兩個c- ancel掉 好，也就是P1，做完這個動作以後P1就會在JFK這個機場 好，那基本上我們定義完了，其實我們差不多已經定義完了，我們講了 什麼是state，我們講了什麼是action，我們講了什麼是transition model，那接下來我要做 search的話，只要再兩個東西就好，你要給我講你的initial state還有你的goal state 就這樣而已，那基本上在PDDL裡面，initial是一個state沒錯，initi- al基本上就是 ground state，ground state就是我們剛剛講的，它必須是conjunction，就是一對and of ground atoms 好，那麼在PDDL比較不一樣的地方是它的 goal不需要是個，它的goal不需要是個 state，它的goal基本上是一種precondition，就是跟precond- ition差不多，它不再是 一個state，它基本上是conjunction of literal，那我講literal的時候它就是可以是positive或者是neg- ative的都可以，因為我的目標可能是 可能不光是用正的來表示，我的目標可能需要用負的，譬如說我的目標 是要某個飛機不在某個機場，那這也可以是我的目標，OK？ 好，那你會發現一些事情，就是我們還是可以試著用 propositionalize的概念來做，來解PDDL，但是它會，並不是很有 效率，舉例而言，課本這邊例子就是說，如果你有一個action，它基本上有v個var- iable 然後每個variable它有，基本上在我domain裡面有k個unique names，有這些東西，它基本上你需要 課本上面是寫v的k次方，不過說實話，我個人是認為這邊可能有點小小的錯誤，我個人- 認為應該 是，應該是k的v次方，就是每一個variable你有k個unique name替換，然後 你需要替個換v個variable，這全部應該是k的v次方，不過這個概念是這個樣子，- 那這一點我們沒有，還沒有跟 教科書的這個確認，所以我這邊留了，我這邊投影片上保留原始教科書的寫法 好，就是v的k次方，那我剛剛講過，我個人認為應該是反過來 好，但是anyway，這邊講的就是說你要，你可以，你PDDL 定完以後，因為仍然裡面有變數，還是可以做我們之前這樣在 first-order logic裡面你可以對一個first-order logic knowledge base，也可以做propositionalize，使得整個 整個變得propositional的logic，然後你用propositional logic裡面 我們有介紹很多方法來解，一樣可以這樣做，所以你可以 propositionalize一個PDDL，好，那基本上，可是這個做法我們也講過- ，在v和k 很大的時候，當你variable很多，然後每個ground term又很多的時候，這是蠻沒有效率的做法 好，那我們當然更直覺的就是我一個 問題一旦用PDDL定完以後，因為我們現在已經有所有東西，我們有initial state 好，那我們有goal，還是要記得，現在goal不再是一個state，那就是goal- ，我們通常直接稱它為goal，然後，我們又定義了action，我已經有transi- tion 好，這基本上說我們就整個，你一個problem 一個planning problem你只要用PDDL描述完以後，基本上它會變成一個 search problem，那我們就可以繼續用我們之前的search的算法 我們剛剛講了什麼是一個state，然後講了什麼是action，那接下來我們要在se- arch problem裡面 唯一還有差的就是transition，那我們要知道怎麼樣從一個state s 然後做了action a以後，那我們之前的方法就是叫result 好，就是你從state s做了action a以後，它會帶領你到另外一個新的state s'，那我們這個是transition model，我們需要在PDDL把這個東西給定義出來 那做法是這個樣子，我們剛剛在 我們剛剛在定action的時候大家應該有注意到我們的effect裡面其實可以有負的- ，譬如說像我們fly，from，to，那你fly 完以後，p就不在from這個airport，而在to這個airport，那我們 把有negation的那一個部分稱為delete list 好，稱為delete list，那把positive的那些東西稱為add list，然後 為什麼叫delete和add呢？等一下我們就會看到，因為我們要用這個方法來創一個新- 的state 那你的result，我們要真的要的是這個東西嘛，就是 你從s做了a到哪個state了呢？方法很簡單，你的s是一堆conjunction of ground literal，那你就是把裡面所有你effect，做這個action的時候 所有負的部分把它拿掉，然後加上那些正的部分，我們舉例而言，就是剛剛的fly的話 那假設我做了一個動作，假設我fly P1從 SFO我fly到JFK 那你剛才還記得它的effect呢，它的effect 就是，就是¬，你飛完以後就是¬At P1，就是P1就不會在SFO，而且 P1會在JFK 好，這是我的effect，好，那照我們剛才的講法，這一個就是我們的 delete list，那這一個就是add list OK？那如果我的，像我的state，那我的state必須要entails 這一個action我才能做嘛，那這個，我要能fly P1從SFO到JFK的話，它 有很多，有很多部分，那第一個，有些太瑣碎我就不寫了，當然P1必須是個plane 然後SFO還有JFK兩個都必須是機場，那還有一個很重要的就是P1必須在 必須在SFO嘛，不然我不能從SFO開始起飛，所以我的state，譬如說s 我只寫一個好了，好，裡面就是它至少有一個這個東西，At P1一開始要在SFO 好，那你的，我剛剛講那些P1是plane還有SFO還有JFK都是airport我就 不再寫，因為那個比較無所謂，好，那接下來我的s'呢也做這個action以後會變成- 什麼呢？ 它其實就是變成原來的s 好，然後你要減掉你的delete list，就是At (P1,SFO)，然後再union回來它的add list (P1,JFK)，好，那你可以發現就是這個 delete list跟這個cancel out就沒有，所它的s'其實就是 At P1在 JFK，OK？好 那我們會發現一件事情，因為我們delete list的裡面是 negation，那negation要拿掉，我剛剛在做的時候negation是拿掉- ，然後就是，所以delete list裡面東西都是 你要delete的東西都是positive，然後你要增加的東西也是positive 那我們回想一下我們剛剛講s是什麼呢？一個state它是一些conjunction，- 就是一堆 positive的東西的and，positive的東西的and，那你把這些posi- tive的東西扣掉，然後你加回來的這些add add list裡面也都是positive的，所以你做完這個動作以後的s'一定仍然是個st- ate，就是我們剛剛有講，就是一定是一些 positive的東西的and，它不會有負的東西，所以我們說基本上ground state 是在，是closed under result，也就是在result這個動作里 就像我們剛剛在定義完以後，你在state做完一個action，用我們這個定義的算法- ，算出來的 一定仍然是個state，好，它不會變成一個無法定義的一個東西，所以我們稱它為clo- sed，那 跟propositional logic還有first-order logic不太一樣的東西是 在PDDL裡面，基本上我們稍微有 有一種，有稍微去處理時間，好，基本上它沒有，我們如果，你用 propositional logic的時候我們之前有提過你可能要定義一個 叫做T的變數，然後你T time要怎麼改，所以說每次，每走一步，你T要變 T加1，那在PDDL裡面，我們時間是直接embodied在我們的 概念裡面，就是說你每次做一步，你做一個，所以你的precondition永遠都是- 在前一個 時間，那你做完以後，你的effect永遠都在下一個時間，好，這就我們T就不再定義 另外一個變數，不再個別處理，而直接embodied在整個PDDL system裡面處理
