010章 經典規劃

Post date: 2012/10/13 上午 02:32:31

本章中,我們將看到代理人是如何利用問題的結構來構造行動的複雜規劃。

這一章談的是單一代理人於完全可觀察的、確定性的、靜態的環境。第11 與17 章涵蓋具有數

個代理人於部份可觀察的、隨機性的、動態的環境。

經典規劃的定義

第3 章的問題求解代理人能夠找出能引導至目標狀態的行動順序。但它處理的是原子狀態的表

示式,遂也需要好的特定領域啟發式才能有好的效能。第7 章的混合命題邏輯代理人可在沒有特定

領域啟發式之下找出規劃,因為它根據問題的邏輯架構,使用了領域無關的啟發式。但它依賴基本(無

變數)命題的推理,意指當有許多的行動與狀態時,它可能會被淹沒。

為應付這一種情況,規劃研究人員決定以分解表示法(factored representation)來解決——此表示

式將世界的一個狀態被表示成一群變數的組合。我們使用一個叫做PDDL 語言,規劃領域定義語言

(Planning Domain Definition Language),它可以讓我們以一個行動模式表達全部的4Tn2 個行動。PDDL

的版本有好幾個,我們選擇其中一個簡單的版本,並改變其語法使之與本書其餘部份一致[1]。我們

現在示範PDDL 是如何描述我們定義一個搜尋問題所需要的四個事件:初始狀態、某個狀態下可採

取的行動、行動採取後發生的結果,以及目標測試。

資料庫語義

集合語義

行動模式

範例:航空貨物運輸

航空貨物運輸問題,包括裝載及卸載貨物,以及從一地運送飛到另一地。這

個問題可以定義3 個行動:Load(裝載),Unload(卸載)和Fly(飛行)。行動用於兩個述詞:In(c, p)表示

貨物c 在飛機p 內,At(x, a)表示物體x(飛機或貨物)在機場a。

範例:備用輪胎問題

考慮更換一個洩了氣的輪胎的問題(圖10.2)。更加準確地說,目標是把一個好的備用輪胎合適地

裝配到汽車輪軸上,初始狀態是有一個漏氣的輪胎在輪軸上和一個好的備用輪胎在後備箱內。為了

保持簡單,我們這個問題的版本是一個十分抽象的,沒有難卸的固定螺母或其他複雜因素。只有4

種行動:從後備箱(trunk)中取出備用輪胎(spare),從輪軸(axle)卸下漏氣的輪胎(flat),將備用輪胎裝

在輪軸上(putting on),徹夜將汽車留下(leaving it overnight)無人看管。我們假設汽車存放的環境特別

差,這樣將它徹夜留下的效果是輪胎消失。這個問題的一個解答是[Remove(Flat, Axle),Remove(Spare,

Trunk), PutOn(Spare, Axle)]。

範例:積木世界

一個最著名的規劃領域稱為積木世界。這個領域由一組放在桌子上的立方體形狀的積木組成

[2]。積木能夠被疊放,但是只有一塊積木能夠直接放在另一塊的上面。一個機器臂能夠拿起一塊積

木並把它移到別的位置,無論是在桌子上還是在另一塊積木上。機械臂每次只能拿起一塊積木,所

以它不能拿起一塊上面有其他積木的積木。目標總是建造一堆或多堆的積木,根據哪些積木在其他

積木的上面進行指定。例如,目標是把積木A 放到積木B 上並且把積木C 放在積木D 上(見圖10.4)。

我們用On(b, x)表示積木b 在積木x 上,其中x 是另一塊積木或是桌子。用Move(b, x, y)來表示

將積木b 從積木x 的上面移到積木y 的上面。現在,移動b 的一個前提是沒有其他積木在它的上面。

於一階邏輯,這會是¬∃x On(x, b)或換個寫法,∀x ¬On(x, b)。基本的PDDL 不允許量詞,所以取而

代之我們引進一個述詞Clear(x),當沒有任何東西於x 時此述詞會為真(完整的問題描述於圖10.3)。

經典規劃的複雜度

PlanSAT 問的是是否存在

任何規劃可以解出一個規劃問題的問題。Bounded PlanSAT 問的是是否存在一個長度不長於k 的解

答;這能夠被用於尋找一個最佳的規劃。

最佳的規劃通常很難,但是次佳的規劃有時候卻是很簡單的。想要在比最壞情況問題還容易的情況下做的好,我們將需要好的搜尋

啟發式。這是經典規劃形式主義真正優越之處:它已經減輕非常準確之領域無關啟發式的開發工作,

然而以一階邏輯後繼狀態公理為本的系統在獲致好的啟發式方面的成效並不顯著。

規劃演算法作為狀態空間搜尋

現在我們把注意力轉到規劃演算法上。我們已看到規劃問題的描述如何的定義出一個搜尋問

題:我們能夠從初始狀態出發走遍狀態空間,來搜尋一個目標。行動模式之陳述表示式的好處之一

是我們也能夠從目標逆向搜尋,搜尋初始狀態。圖10.5 比較了前向與逆向搜尋。

前向狀態空間搜尋

現在,我們已經展示規劃問題如何映射到搜尋問題,我們能夠以第3 章任何一個啟發式搜尋演

算法或是第4 章的區域搜尋演算法來解出規劃問題(只要我們持續的追蹤到達目標所使用到的行

動)。從規劃搜尋的初期(約1961 年)直到最近(約1998 年),人們認為前向狀態空間搜尋太無效率而不

能實際應用。想要得出箇中理由並非難事。

第一,前向搜尋傾向發掘無關聯的行動。考慮一個購買AI 書籍的神聖任務:摩登的方法是透過

線上書店。假設有一個行動模式Buy(isbn)具有效果Own(isbn)。ISBNs 是10 個數字,所以這個行動

模式代表10 億個基本行動。一個茫然無知的前向搜尋演算法將必須開始一一列舉這10 億個行動以

尋找出一個可以走到目標者。

第二,規劃問題常常有非常龐大的狀態空間。考慮一個有10 個機場,每個機場有5 架飛機和

20 件貨物的航空貨物問題。目標是將所有的貨物從機場A 運送到機場B。這個問題有一個簡單的解:

將20 件貨物裝載到機場A 的一架飛機上,飛機飛到機場B,卸載所有貨物。找到解可能很困難,因

為平均分支因數是巨大的:50 架飛機中的任何一架可以飛到9 個其他的機場,200 件包裹中的每一

件也能一樣被卸載(如果已經裝載了)或者裝載到機場的任何一架飛機上(如果還沒裝載)。所以於任何

狀態下最少時會有450 個行動(當所有的貨物都在機場但沒有任何飛機)最多時會有10,450 個行動(當

所有的貨物與飛機都在相同的機場)。平均而言,我們說存在大約2000 個可能的行動,所以達到明

顯解的深度的搜尋樹大約有200041 個節點。

顯然地,即使這個相當小型的問題實例也沒有一個正確的啟發式。儘管許多的規劃在實際世界

的應用仰賴於領域特定的啟發式,不過(如同我們在第10.2.3 節所見)強的領域無關啟發式能夠被自動

地導出;這也使得前向搜尋變得可行。

逆向相關聯狀態搜尋

於逆向搜尋我們從目標開始並逆向地實踐行動直到我們找出能抵達初始狀態的一系列步驟。此

稱之為相關聯狀態搜尋。因為我們僅僅考慮與目標(或目前的狀態)有所關聯的行動。如同於信度狀態

搜尋(第4.4 節),在每一個步驟都會有一組相關聯狀態要考慮,而不僅是單一個狀態。

因該行動而加入之效果在行動之前不必已經為真,同時前提在行動之前必須已經成立

舉例來說,假設目標是運送特定的貨物到SFO:At(C2, SFO)。這提議了行動Unload(C2, p′,

SFO):

Action(Unload(C2, p′, SFO),

PRECOND: In(C2, p′) ∧ At(p′, SFO) ∧ Cargo(C2) ∧ Plane(p′) ∧ Airport(SFO)

EFFECT: At(C2, SFO) ∧ ¬In(C2, p′)

對於大多數的問題領域,逆向搜尋會將分支因數保持得低於前向搜尋者。不過,逆向搜尋事實

上使用的是一組狀態而非個別的狀態,使得它難以得到好的啟發式。這也就是為什麼目前多數的系

統仍偏愛於前向搜尋的主要理由。

更白話一點,當我在搜尋Scaleform相關功能時,我事先確認官方文件有做這個功能,我才去搜尋官方網站、論壇、估狗關鍵字,最後能夠有效地找出範例程式碼。

啟發式規劃

不論是前向或是逆向搜尋,若沒有好的啟發式函數,都不會是有效率的。

根據定義,並沒有任何辦法可以分析一個原子狀態,也因此它需要人類分析師的些許智巧去針

對原子狀態之搜尋問題定義一個好的領域特定啟發式。使用一個分解好的狀態與行動模式表示式來

規劃。就可能定義出好的領域無關啟發式,以及自動地對一個已知的問題運用一個好的領域無關啟

發式。

將搜尋問題想成是一個圖形,圖形的節點是狀態而其邊是行動。這個問題就是要找出從初始狀

態連至目標狀態的一條路徑。有兩個方式讓我們能夠鬆弛這個問題使之更加容易:加入更多的邊到

圖上,使得它極為容易地尋找出一條路徑,或是將數個節點集合在一起,構成一個有較少狀態數目

的精簡狀態空間,而因此變得容易搜尋。

我們首先看看增加圖形邊數的啟發式。舉例來說,忽略前提啟發式將所有的前提自行動身上取

掉。每個行動變成適用於每一狀態,且能以一步達到任何單一目標流(如果有可用的行動——若沒

有,問題是不可能的)。這幾乎暗示求解鬆弛問題所需的步驟數目等於未滿足的目標數目—幾乎但是

不全然,因為 (1) 某些行動能完成數個目標且 (2) 某些行動能抵消其他行動的效果。對許多問題,

一個準確的啟發式是透過考慮 (1) 並忽略 (2) 而得到。首先,我們拿掉所有的前提與所有的效果,

除了那些屬於目標中的文字外,來鬆弛行動。接著,我們計算所需行動的最小數目,而這些行動的

正效果的並集能夠滿足目標。這是一個涵蓋集問題的實例。有一個次要的惱人問題:涵蓋集問題是

NP 難題。幸運的是,一個簡單的貪婪涵蓋集演算法保證返回一個處於真正最小值的log n 倍範圍內

的值,其中n 是目標中的文字個數。不幸的是,貪婪演算法不能保證可採納性。

假設我一開始就找關鍵字,我也沒有相關知識,只知道搜尋Scaleform以及callbackfunting,此時會出現大量莫名的網站,雖然透過辜狗會幫我篩選,

卻也很沒效率,找到目標關鍵代碼的機率也不高,如果一開始我就知道去找官方網站、論壇,更多與Scaleform功能有關聯的啟發函式,時間成本就能大幅度減少。

使用清空刪除列表啟發式下,兩個規劃問題的狀態空間。點代表狀態,邊代表行動,而點在底平面上的高度代表啟發值。在底平面上的

狀態則為解。在兩問題中,存有一寬路徑到達目標。沒有死路,所以不需要回溯;簡單的爬山搜尋

法可輕易找出這些問題的解(雖然可能不是最佳解)。

一個有效使用啟發式的系統的範例是FF,或FASTFORWARD(Hoffmann,2005),是一個使用

清空刪除表啟發式的前向狀態空間搜尋器,在規劃圖的幫助下估算啟發式(見第10.3 節)。FF 然後使

用爬山搜尋法(略事修改過以便能追蹤該規劃)於該啟發式以尋找一個解答。當它爬到一個平台或是區

域最大值的時候——當沒有任何行動會讓一個狀態有更佳的啟發式分數——那麼FF 使用疊代式深

入搜尋法直到它找到一個更好的狀態,或是放棄並重新開始爬山搜尋工作。

規劃圖

規劃問題問的是我們是否能夠從一個初始狀態到達目標狀態。假設我們已經知道從初始狀態到

後繼狀態,以及它們的後繼者等等所有可能行動的樹。如果我們將這株樹予以適當地索引化,則只

需要看看它,我們就能夠立刻回答規劃問題「我們是否能夠從狀態S0 達到狀態G」。當然,這株樹

的規模是呈指數量級地成長,所以這方法是不實際的。一個近似這株樹而大小為多項式量級的規劃

圖能夠很快地被建構出來。規劃圖無法肯定地回答是否從S0 可以抵達G,但是它能夠估計抵達G 需

要走多少個步驟。當它回報說目標並非可達到者的時候,該估計都是正確的且它從不會過度的估計

步驟的數目,所以它是一個可採納的啟發式。

一張規劃圖是一種組織成好幾個階段的有向圖:首先初始狀態之S0 階段,由那些代表於 S0 為

真的各個流之節點所組成;然後A0 階段是由各個於S0 中適用於基本行動之節點所組成;那麼隨著

Ai 而更換到Si 階段;直到我們抵達一個終止條件 (稍後會討論)。

規劃圖只對命題規劃問題起作用——沒有變數的規劃。如在10.1 節所提,對一組行動模式進行

命題化是很直接的。儘管使問題描述的大小增加,規劃圖仍證明為解決困難規劃問題之有效工具。

我們現在為行動和文字定義互斥連接。如果下面3 個條件中的任何一個成立,那麼一個給定階

段的兩個行動之間的互斥關係成立:

● 不一致效果:

一個行動否定另一個行動的效果。例如,Eat(Cake)和Have(Cake)的持續有不一致效果,因為它

們在效果Have(Cake)上不一致。

● 衝突:

一個行動的效果之一是另一個行動的前提之一的否定式。例如,Eat(Cake)透過否定持續行動

Have(Cake)的前提而和它衝突。

● 競爭需要:

一個行動的前提之一和另一個行動的前提之一互斥。例如,Bake(Cake)和Eat(Cake)是互斥的,

因為它們在前提Have(Cake)的值上有競爭。

一個規劃圖一旦被建構,它就是關於問題的資訊的豐富來源。第一,如果任何目標文字沒有出

現在圖的最後一個階段,那麼該問題屬於無法被解出的。第二,我們能夠估計從狀態s 到達任何目

標文字gi 的成本,當gi 在由初始狀態所建構之規劃圖第一次出現的階段。我們稱這個為gi 的階段成

本。在圖10.8 中,Have(Cake)的階段成本為0,Eaten(Cake)的階段成本為1。很容易說明這些估計對

單獨目標是可採納的(習題10.10)。然而這個估計可能不是很好,因為規劃圖允許每一階段有數個行

動,而啟發式只對階段而不對行動數進行計數。由於這個原因,使用串列規劃圖計算啟發式是常見

的。串列規劃圖堅持在任何給定的時間步只能有一個行動實際發生;這是透過在除了持續行動之外

的每對行動間添加互斥連接而實作的。根據串列規劃圖提取的階段成本往往是對實際成本的一個相

當合理的估計。

為了估計目標連言的成本,有3 種簡單的方法。

最大階段啟發式簡單地選取任何目標的最大階段成本值;這是可採納的,但是不一定很準確。

階段總和啟發式,根據子目標獨立假設,返回目標的階段成本的總和;這是不可採納的,但是

在實際中對那些很大程度上可以分解的問題很有效。它比第10.2 節中的不可滿足目標數啟發式精確

得多。對於我們的問題,目標連言Have(Cake) ∧ Eaten(Cake)的階段總和啟發式估計會是0 + 1 = 1,

而正確的答案是2(由規劃[Eat(Cake), Bake(Cake)]達成)。那看起來並不是很糟。一個更嚴重的錯誤

是,如果Bake(Cake)不在行動集之中,當事實上目標連言為不可能的時候,該估計會仍然是1。

最後,固定階段啟發式找到一個階段,在這個階段目標連言中的所有文字都出現在規劃圖中,

而且其中不存在任何一對是互斥的。這個啟發式對我們的原始問題給出了正確的值2,對沒有

Bake(Cake)的問題給出無窮大。它優於最大階段啟發式,在子規劃之間有很多相互作用的任務中產

生了極好的效果。當然,它並不完美,舉例來說,它省略掉了三個或更多的文字之間的互動。

作為產生精確啟發式的工具,我們可把規劃圖視為一高效可解的鬆弛問題。為了理解鬆弛問題

的特性,我們需要確切理解文字g 在規劃圖中Si 階段出現的含義。理想地,我們希望它能保證存在

一個獲得g 的有i 個行動階段的規劃,同時希望當g 不出現時也就沒有這樣的規劃。不幸的是,要

得到這個保證與求解原始規劃問題一樣困難。所以規劃圖能夠提供後一半保證(如果g 不出現,就沒

有這樣的規劃),但是如果g 真的出現了,那麼規劃圖能承諾的全部是有一個規劃可能獲得g 而且沒

有「明顯的」缺陷。明顯缺陷是這樣定義的:在某個時刻透過考慮兩個行動或兩個文字就能檢測出

的缺陷——換句話說,透過觀察互斥關係。可能有涉及三個、四個或更多行動的複雜缺陷,但是經

驗顯示不值得為了明確這些可能的缺陷而耗費計算努力。這與從限制滿足問題中學到的經驗類似,

通常在搜尋解之前計算二元一致性是值得的,但通常計算三元或更高一致性就不值得了(參見6.2 節)。

一個同樣無法同樣地被規劃圖所認出的不可解的問題的例子之一是積木世界問題,其目標是讓

A 位在B 之上,B 在C 之上,且C 在A 之上。這是一個不可能的目標;一個塔的底部放在頂部的上

面。但是一張規劃圖無法察覺這樣的不可能性,因為三個子目標中的任何兩個都是可達成的。任何

一對文字之間沒有任何互斥,僅僅將三個文字之間視為一體時才有。想要察覺出這樣的問題是不可

能的,我們將必須從頭到尾的搜尋整張規劃圖。

GRAPHPLAN 演算法

這一子節說明如何從規劃圖中直接抽取一個規劃,而不只是使用規劃圖來提供啟發式。

GRAPHPLAN 演算法(圖10.9)重複地以EXPAND-GRAPH 將一個階段加到規劃圖中。一旦所有目標

於圖中以非互斥的面貌出現,GRAPHPLAN 呼叫EXTRACT-SOLUTION 來搜尋一個求解該問題的規

劃。如果失敗了,它展延到令一個階段並再試一次,當沒有任何理由再繼續時就以失敗告終。

GRAPHPLAN 的終止

到目前為止,我們略過了終止問題。這裡我們顯示 GRAPHPLAN 事實上會終止並且於解答不

存在時會傳回失敗。

第一件要了解的事是當圗已平整了,為什麼我們不能停止擴張它。考慮一個在機場A 有飛機一

架與貨物n 件的空中貨運領域,都是以B 機場為目的地:於這個版本的問題,同一個時間內只能有

一件貨物放在飛機上。該圖在階段4 會平整,反映了任何單一件貨物,我們能夠於三個步驟內將之

裝載、飛運、並卸載而抵達目的地的事實。但是這並非意謂著一個解答能夠於階段4 的時候從圖中

抽取出來;事實上解答需要4n − 1 個步驟:對於我們裝載、運送、並卸載的每一件貨物,以及所有

貨物,除最後一件之外,我們必須飛回機場A 以領取下一件貨物。

當圖已經被平整之後,我們必須持續地擴張多久?如果函數 EXTRACT-SOLUTION 尋找解答失

敗,那麼至少有一個目標集是無法達成的而會被標示為不良。所以如果在下一個階段會有較少的不

良數是有可能的,那麼我們就應該繼續下去。只要圖本身以及不良兩者都被平整,沒有找到任何解

答,我們便能夠以失敗告終,因為其後的更動會增加解答的可能性是不存在的。

現在我們必須做的就只有證明圖以及 不良必然會平整。第一步要注意到規劃圖的某些特性是單

調遞增或者遞減的。「X 單調遞增」的意思是i + 1 階段的X 集是階段集合的一個超集合(並不需要

嚴格意義上的)。特性如下:

● 文字單調遞增:

一旦一個文字在一個給定的階段中出現,它將在所有後繼階段中出現。這是持續行動造成的;

一旦一個文字露面,持續行動讓它永遠存在。

● 行動單調遞增:

一旦一個行動在一個給定的階段中出現,它將在所有後繼階段中出現。這是文字遞增的一個推

論;如果一個行動的前提在一個階段中出現,它們將出現在後繼階段中,因而行動也一樣。

● 互斥單調遞減:

如果在給定階段Ai 的兩個行動是互斥的,那麼它們在所有早先它們共同出現的階段中也是互斥

的。這對於文字之間的互斥同樣成立。不見得都會以那些圖所示的方式出現,因為 那些圖有些

簡化:它們既不顯示在階段Si 中不成立的文字,也不顯示在階段Ai 中無法執行的行動。我們可

以看到「互斥單調遞減」是正確的,如果你認為這些不可見的文字和行動與任何事物都互斥的

話。

證明能夠依情況來處理:如果行動A 和B 在階段Ai 是互斥的,它一定是由三種互斥類型中

的一種造成的。前兩種,不一致效果和衝突,是行動本身的特性,所以如果行動在階段Ai 互斥,

那麼它們將在每個階段都互斥。第三種情況,競爭需要,依賴於Si 階段的條件:階段必須包含

一個A 的前提與一個B 的前提互斥的情況。現在,這兩個前提可以是互斥的,如果它們是彼此

的否定式(這種情況下它們將在每一個階段都互斥)或者獲得其中一個的所有行動與獲得另一個

的所有行動互斥。但是我們已經知道可用的行動是單調遞增的,所以透過歸納,互斥肯定是遞

減的。

● 不良會呈單調性地減少:

如果一個目標集在某個給定的階段是不可達到的,那麼它們於任何前階段是不可達到的。這可

以用矛盾法予以證明:如果它們是在某個前階段可達到的,那麼我們只需要加入持續行動使它

們在後續的階段是可達到的。

因為行動與文字呈單調性地增加,且因為行動與文字的個數是有限的,所以必然會走到一個與前階

段有相同的行動與文字個數的階段。因為互斥與不良減少,且因為不可能存在比零個互斥或不良還

少的情況,必然會有一個階段其與前階段有相同之互斥與不良數的階段。一旦圖已經抵達這樣的狀

態,那麼如果其中一個目標漏失或與其他目標互斥,那麼我們能夠停止GRAPHPLAN 演算法並傳回

失敗的訊息。這歸結出證明方式的大致輪廓;進一步的細節請見Ghallab 等人(2004)。

其他的經典規劃方法

目前最廣為採用與有效的全面自動規劃方法是:

● 轉譯成一個布林滿足性(SAT)問題

● 前向狀態空間搜尋搭配精心裁剪出來的啟發式(第10.2 節)

● 使用規劃圖搜尋(第10.3 節)

於自動規劃的40 年歷史中,並非僅僅嘗試過這三個方法。圖10.11 顯示從1998 年起逐年舉辦之國

際規劃競賽中的某些頂尖系統。於這一節我們首先描述轉抑制滿足性問題然後描述三個其他流的方

法:規劃如一階邏輯歸納;如限制滿足;以及如規劃調整。

年度 主題 獲勝系統(方法)

2008 最佳化 GAMER (模型檢驗,雙向搜尋)

2008 滿意性的 LAMA (快速向下搜尋搭配 FF 啟發式)

2006 最佳化 SATPLAN,MAXPLAN (布林滿足性)

2006 滿意性的 SGPL 一個(前向搜尋;分割為獨立的子程式)。

2004 最佳化 SATPLAN (布林滿足性)

2004 滿意性的 FAST DIAGONALLY DOWNWARD (前向搜尋搭配因果圖)

2002 自動的 LPG (區域搜尋,規劃圖被轉換為 CSP)

2002 手寫 TLPLAN (時序行動邏輯搭配前向搜尋控制邏輯)

2000 自動的 FF (前向搜尋)

2000 手寫 TALPLANNER (時序行動邏輯搭配前向搜尋控制邏輯)

1998 自動的 IPP (規劃圖);HSP (前向搜尋)

圖10.11 於國際規劃競賽中的某些頂尖效能系統。每一年都有不同的主題:「最佳化」意指規劃器必須

產生最短的可能規劃,然而「滿意性的」意指非最佳解答也可以被接受。「手寫」意指領域特定之啟發

式是可允許的;「自動的」意指它們是不被允許的

經典規劃成為布林滿足性

於第7.7.4 節我們看到SATPLAN 是如何的將表示為命題邏輯之規劃問題解出。在這裡我們展示

如何轉譯一個 PDDL 描述為一個能夠被 SATPLAN 處理的形式。該轉譯是一連串直截了當的步驟:

● 命題化行動:

將各個變數代換為常數後所形成的基本行動集取代各行動模式。這些基本行動並非轉譯的一部

分,但是於後續的步驟會派上用場。

● 定義初始狀態:

在問題初始狀態中的每一個流F 都是斷言F0,初始狀態沒有提及的流則都是斷言¬F。

● 命題化目標:

於目標中的每一個變數,以一個常數的選言取代含有變數之文字。舉例來說,於一個具有物件

A,B 與C 的世界,要求積木A 在另一塊積木之上,On(A, x)∧Block(x)的目標,會被取代為下面

這個目標。

(On(A, A) ∧ Block(A)) ∨ (On(A, B) ∧ Block(B)) ∨ (On(A, C) ∧ Block(C))

● 加入後繼狀態公理:

對每一個流F,加入下述形式的公理

F

t+1 ⇔ ActionCausesF

t ∨ (F

t ∧ ¬ActionCausesNotF

t)

其中ActionCausesF 是一個所有基本行動之加入表中有F 者的選言,而ActionCausesNotF 是一

個所有基本行動之刪除表中有F 者的選言。

● 加入前提公理:

對每一個基本行動A,加入公理At ⇔ PRE(A)t,也就是說,如果一個行動在時間t 發生,那

麼前提必須已經為真。

加入行動排斥公理:

設說每一個行動都與其他行動涇渭分明。

所得到的轉譯是個讓我們能夠交付予SATPLAN 去尋找解答的形式。

規劃當成一階邏輯演繹:情景演算

規劃問題的命題邏輯表示也有限度,如時間的符號直接與流繫結在一起的事實。舉例來說,South2

意指「代理人在時間2 的時候面向南方。」以此表示,沒有任何方式可以說「如果在時間1 的時候

代理人向右轉,則它將會在時間2 的時候面向南方,否則它將會面向東方。」一階邏輯使用一個稱

之為情景演算的表示式,將線性時間的符號換成分支情況的符號,來讓我們周旋這樣的限制,這個

表示式的用法如下:

● 初始狀態被稱之為一個情景(situation)。如果s 是一個情景而a 是一個行動,那麼RESULT(s, a)

也是一個情景。不會有其他的情景。因此,一個情景相應於行動的一個序列,或是歷史。你也

能夠將情景想像成付諸行動之後的結果,但是請注意只有在情景的起點與行動都是一樣的時

候,那兩個情景才能說是一樣的:(RESULT(s, a) = RESULT(s′, a′)) ⇔ (s = s′ ∧ a = a′)。行動

與情景的某些例子示如圖10.12。

● 一個能夠從某個情景變換到另一個情景的函數或關係屬於一種流。慣例上,情景總是流的最後

一個參數,舉例來說At(x, l, s)是一個當物件x 於情景s 下在位置l 的時候會為真的關係流,

而Location 是一個使得與At(x, l, s)有相同的情景s 時,Location(x, s) = l 成立的函數流。

● 每個行動的前提會以一個可能性公理來描述,該前提說明什麼時候行動能夠被付諸實行。它具

有形式Φ(s) ⇒ Poss(a, s)其中Φ(s)是描述前提的某些與s 有關的公式。wumpus 世界中有一個

範例,說是如果代理人是活的而且有一根箭,就有射擊的可能:

Alive(Agent, s) ∧ Have(Agent, Arrow, s) ⇒ Poss(Shoot, s)

● 每個流以一個後繼狀態公理來描述,此公理指出什麼樣的事會發生在流的身上,必須看什麼行

動被付諸實行了。這類似於命題邏輯上我們所採取的方法。該公理的形式是

行動是可能的 ⇒

(流於所得到的狀態為真 ⇔ 行動的效果使之為真

∨ 它先前已經為真且行動對之無影響)

舉例來說,用於關係流Holding 之公理指出代理人執行一個可能的行動之後手上會持有一些金

子g 若且唯若該行動是g 的Grab,或若代理人已經持有g 而該行動並沒有將金子放下來:

Poss(a, s) ⇒

(Holding(Agent, g, Result(a, s)) ⇔ a = Grab(g) ∨ (Holding(Agent, g, s) ∧ a ≠ Release(g)))

● 我們需要唯一行動公理使得代理人能夠演繹出,舉例來說,a ≠ Release(g)。對每一對不同的行

動名之為Ai 與Aj 我們有一個公理說這些行動是不同的:

Ai(x, …) ≠ Aj(y, …)

對每一個名為Ai 之行動,我們有一個公理說使用該行動名稱的兩個名稱會是相等的,若且唯若

它們的引數都相同:

Ai(x1, ..., xn) = Ai(y1,..., yn) ∧ x1 = y1 ∧ ... ∧ xn = yn

● 一個解答是一個滿足目標的情景(也即是一系列的行動)。

於情景演算中許多的工作多投注在定義規劃的形式語義以及拓展先的探索領域。但迄今為止還沒有

任何一個實際的大型規劃程式是植基於情景演算上的邏輯演繹。這部分是因為於FOL,要作出有效

率的推理是很困難的,但主因為這個領域還沒有開發出適用於以情景演算所為之規劃的有效啟發式。

規劃當成限制滿足性

我們已見識過限制滿足與布林滿足性有相當大程度的共通性,而且我們已經見識過CSP 技術對

於排程問題是非常有向的,所以並不令人意外的它可以將一個受限制的規劃問題(也就是說,尋找一

個長度為k 之規劃的問題)當成一個限制滿足性的問題(CSP)來編寫。編寫類似於編寫到一個SAT 問

題(第10.4.1 節),但是有一個大大的簡化:在每一個單位時間,我們僅僅需要一個單一變數,Actiont,

其領域是可能的行動的集合。我們不再需要為每一個行動準備一個變數,且我們不需要行動排斥公

理。也可能編寫規劃圖於CSP 之中。這是GP-CSP(Do 及Kambhampati,2003)所採用的方法。

規劃看成是偏序規劃的調整

一個替代的做法是以偏序架構來表示規劃:一個規劃是一個行動集以及Before(ai, aj),說的是一

個行動先於另一個行動發生,之形式的限制集。於圖10.13 的下半部,我們看到一個偏序規劃也就

是說備胎問題的一個解答。行動是方框而前後順序的限制是箭頭。注意到,Remove(Spare, Trunk)和

Remove(Flat, Axle)可以在任一順序下進行,只要它們在行動PutOn(Spare, Axle)之前完成。

偏序規劃是經由搜尋規劃空間而非狀態空間所製作出來的。我們以空的規劃開始,此規劃由初

始狀態與目標所組成,其間沒有任何行動,如圖10.13 上方所示。搜尋程序然後尋找一個規劃中的

瑕疵(flaw),並加入該規劃以補正該瑕疵(或是如果無以補正,該搜尋會回溯並試試別的方法)。一個

瑕疵是個使得某部分規劃不能成為解答的任何東西。

規劃方法分析

規劃合併我們已經論述過的兩個主要AI 領域:搜尋和邏輯。也就是,規劃器既能被視為搜尋解

的程式,也能被視為(構造性地)證明解存在的程式。

作為一個更複雜的例子,對於指揮NASA 的深空一號太空船的遠端代理人規劃器,已經確定的

是涉及指揮航空器的命題可串列化。這可能並不令人感到驚奇,因為工程師設計的航天器要盡可能

地容易控制(服從其他限制)。利用目標的串列化排序,遠端代理人規劃器能夠消除大部分搜尋。這意

味著它能足夠快地即時控制航天器,這是在以前被認為是不可能的。

總結

在這一章中,我們在確定性的、完全可觀察的環境中定義了規劃問題。我們描述了用於規劃問

題的主要表示方法和一些用來求解它們的演算法方法。需要記住的幾點是:

● 規劃系統是問題求解演算法,它在關於狀態和行動的明確命題(或一階)表示上運轉。這些表示使

獲得高效啟發式和強有力且靈活的問題求解演算法成為可能。

● PDDL,規劃領域定義語言,將初始與目標狀態描寫成文字的連言,且以它們的前提與效果來表

示行動。

● 狀態空間搜尋可以前向(前進)或者後向(回歸)地運轉。可以透過子目標獨立假設和對規劃問題進

行各種鬆弛來獲得有效的啟發式。

● 規劃圖可以從初始狀態出發,漸進地構造。每一層包含一個所有在那個時間步出現的文字和行

動的超集合,並且對互斥(或簡稱mutex,文字之間或行動之間不能出現的關係)進行編碼。規劃

圖為狀態空間和偏序規劃器產生有用的啟發式,並能直接用於圖PLAN 中

● 其他的方法包括於情景演算公理之上的一階演繹;編寫規劃問題為布林滿足性問題或是為限制

滿足性問題;且直接在偏序規劃空間上進行搜尋。

● 規劃問題的每種主要方法都有它自己的擁護者,對哪一個是最好的還沒有達成一致。這些方法

之間的競爭和雜交導致規劃系統的效率獲得顯著提高。

自從規劃搜尋出現以來,它已經成為人工智慧的中心問題之一,關於規劃的論文是主流人工智

慧期刊和會議的重要來源。也有專門的會議,例如「人工智慧規劃系統國際會議」(International

Conference on AI Planning Systems,AIPS),「空間規劃和排程國際專題研討會」(International Workshop

on Planning and Scheduilng for Space)以及「歐洲規劃會議」(European Conference on Planning)。