規劃必須追蹤動作破壞了甚麼
計劃不只是各自有用的動作清單。駕車到目的地,會使「身處起點」變假;交付物件,會使「正在攜帶」變假。因此後來動作可能破壞先前已建立的條件。要推理整個計劃,就須精確說明前提、效果及哪些事實保持不變。
本節採用有限命題 STRIPS 模型:前提與目標均為正事實,動作確定,而且每動作成本為一。這是有用的核心規劃模型,不涵蓋不確定感知、隱藏事實、否定前提或條件效果。
狀態指定全部目前為真的事實
定義 18.1.1
(狀態、動作與目標)
設 為有限命題事實集合。狀態是子集 ,恰好其中成員為真,其餘為假。本模型中缺席表示假,不是未知。
動作 有集合 、、,皆為 子集,加入與刪除集合互不相交。當 時動作可用,後繼為
正目標是集合 ,當 時滿足。計劃是逐步可用的動作序列,最後狀態滿足 。每動作成本一,因此計劃成本就是長度。
前提在執行之前檢查,也可以被該動作刪除,所以容許消耗必需資源。不在加入或刪除集合的事實保持原真假值。這個持續不變約定(frame rule),讓我們不必在每個動作逐項列出所有不受影響事實。
事實名字本身不施加邏輯限制。例如任意 子集中,兩個地點事實不自動互斥。領域可透過初始狀態及動作維持互斥,但必須為可達狀態證明此不變量。
一個需要返回起點的送貨領域
使用 atA、atB 表示位置,parcelA 表示包裹在 A,carrying 表示正在攜帶,delivered 表示已交付。初始狀態為 ,目標為 。動作為:
| 動作 | 前提 | 加入效果 | 刪除效果 |
|---|---|---|---|
pickup | atA, parcelA | carrying | parcelA |
driveAB | atA | atB | atA |
driveBA | atB | atA | atB |
deliver | atB, carrying | delivered | carrying |
這些符號描述一個小型形式領域,除此明訂事實與動作以外,不暗中假定其他物理規則。
例題 18.1.2
(送達後仍須返回,才完成整個目標)
執行以下四動作計劃:
| 步數 | 剛執行動作 | 結果狀態 |
|---|---|---|
| 0 | 無 | atA, parcelA |
| 1 | pickup | atA, carrying |
| 2 | driveAB | atB, carrying |
| 3 | deliver | atB, delivered |
| 4 | driveBA | atA, delivered |
取件不改位置,駕車不改攜帶狀態,交付不改位置。這些都由持續不變規則推出,不是要猜測的遺漏效果。
計劃最短:只有 deliver 加入 delivered,它要求攜帶物件且身處 B;只有在 A 可用的 pickup 產生攜帶狀態。因此交付前至少要一次 driveAB。由下文將證的地點不變量,交付在 B 時 atA 必假;最後要求在 A,所以之後還要 driveBA。四種不同必需動作給出四步下界,上述計劃恰好達到。
命題 18.1.3
(地點與包裹階段不變量)
由 出發,經任何可用動作序列到達的狀態,恰含 atA、atB 其中一個,也恰含 parcelA、carrying、delivered 其中一個。
證明
(對計劃長度歸納)
初始狀態恰有 atA、atB 之一。取件與交付不改兩事實。若在恰有一地點的狀態中 driveAB 可用,則 atA 真、atB 假;刪前者加後者,仍恰有一個。反向駕駛同理。對計劃長度歸納,證明全部可達狀態保持此性質。
同樣,parcelA、carrying、delivered 恰有一個成立:取件把第一個變第二個,交付把第二個變第三個,駕車全部不改。
證明透視
不變量依賴甚麼
歸納逐一檢查本領域四個動作,每次檢查都用到動作的完整三元組。driveAB 保持恰有一個地點,是因為前提 atA 連同歸納假設迫使 atB 為假,而且它刪 atA、加 atB。若多加一個動作 teleport,無前提、加入 、沒有刪除效果,不變量立即失效:在 施行後得到 。所以不變量描述的是這組動作,不是任意的 子集。論證能夠收尾,因為動作只有有限個,每個都保持此性質,而初始狀態具備此性質。
目標回歸問的是前一步必須滿足甚麼
前向搜尋把動作用於狀態,向後的目標回歸則把可能的最後動作用於目標條件。結果是對前一狀態的要求,不是模擬出一個完整前狀態。
定理 18.1.4
(正目標的精確回歸)
對動作 與目標集合 :
- 若 ,不存在任何狀態能把 當最後動作,之後滿足 。
- 否則定義
在此沒有刪除衝突的情況,對每個狀態 ,「 可用且後繼滿足 」恰好等價於 。
證明
(分開動作造成的目標與必須持續的目標)
若某目標被刪除,加入與刪除集合互不相交,保證它不會再加回,後繼必缺該事實,所以動作不能是達成 的最後一步。
現在假設沒有目標被刪除。可用性恰好要求 。加入集合內的目標執行後必真,不要求之前已真。加入集合以外的目標,因不被刪除,執行後為真恰好等價於在 已真,故剩餘要求為 。
兩條件合併就是所列聯集,正反方向都成立。這在正前提、正目標模型中精確,但不暗中處理否定目標或條件效果。
此等價描述形式狀態的條件;某狀態是否由指定初始狀態可達,是另一個問題。
回歸整個計劃,不是各目標分開處理
由送貨目標開始,反向選擇最後動作:
| 動作之後的目標 | 擬定最後動作 | 回歸到動作之前的目標 |
|---|---|---|
atA, delivered | driveBA | atB, delivered |
atB, delivered | deliver | atB, carrying |
atB, carrying | driveAB | atA, carrying |
atA, carrying | pickup | atA, parcelA |
最後回歸集合包含於 。把所選動作按正向讀,就得到已驗證四步計劃。回歸子目標不必指定前狀態的全部事實;沒列出的事實,不受此目標條件限制。
若嘗試把 deliver 當完整目標的最後動作,回歸會得到 atA, atB, carrying。刪除集合雖沒有直接衝突,但前提 atB 與必須保留的 atA 產生了依已證地點不變量不可達的子目標。分開達到 atA 與 delivered,不足以安排整個計劃,因駕車會破壞位置目標。
例題 18.1.5
(導向不可達子目標的回歸步驟)
取目標 。有兩個動作加入其中一個事實。
經 pickup:刪除集合 不碰目標,所以
對形式狀態而言公式是精確的:此集合確實容許取件,並到達含目標的狀態。但它同時含兩個地點,依地點不變量,沒有可達狀態滿足它,這個分支合法卻是死路。
經 driveAB:刪除集合 同樣不碰目標,。再經 pickup 回歸,得 。這個分支恢復出前綴 pickup, driveAB。
反例模式
略過刪除衝突檢查會使回歸不可靠
取目標 atA, delivered 與動作 driveAB。若盲用聯集公式,回歸仍是 atA, delivered。恰有這兩事實的可達狀態符合此條件,動作也可用,但後繼為 atB, delivered,因 atA 被刪而不符合目標。
所以 不可省略。沒有檢查刪除效果,就不能對任意最後動作使用回歸公式。
前向廣度優先搜尋提供完備基準
狀態至多有 個。動作有限時,在可用轉移上做廣度優先搜尋,便完備,且在每步成本一的假設下找到最短計劃。狀態入隊時就標記已見,避免反覆駕車等環造成無限重複工作。
PLAN_BFS(initial, goal):
queue = [initial]
seen = {initial}
predecessor[initial] = NONE
while queue is not empty:
S = remove first state from queue
if goal is a subset of S:
return reconstruct action sequence from predecessor
for each action a:
if Pre(a) is a subset of S:
T = (S minus Del(a)) union Add(a)
if T is not in seen:
add T to seen
predecessor[T] = (S, a)
append T to queue
return NO_PLAN
定理 18.1.6
(廣度優先規劃在單位成本下完備且最優)
設事實集合 有限,動作成本皆為一,則 PLAN_BFS 必然終止。初始狀態已滿足目標時,且僅在此時回傳空計劃;有計劃時回傳最短計劃;沒有計劃時,且僅在此時回傳 NO_PLAN。
證明
(隊列的層次就是計劃長度的層次)
每個狀態入隊時即標記已見,所以至多入隊一次,而狀態至多 個,迴圈因此終止。每條生成邊都是合法動作,所以重建計劃可靠。隊列先進先出:某層後繼都排在該層剩餘狀態之後,歸納可知出隊次序按最小動作數不遞減,因此第一個出隊的目標狀態長度最小。隊列清空時,全部可達狀態都已檢查,故沒有計劃。若初始已滿足目標,就得到空計劃。
有限狀態完備不表示便宜,因狀態數對 是指數。
本領域兩不變量只容許六種組合:兩地點乘三包裹階段。表中計劃經過五種,第六種 atB, parcelA 可由初始直接駕車到達,所以六者都可達。抽象冪集上界為 32,而 BFS 在深度四首次到達完整目標。若動作成本不同,普通 BFS 不再證明最小成本,搜尋方法須配合成本模型。
忽略刪除給出下界,不給出另一個真實計劃
把每個刪除集合改為空,得到刪除鬆弛模型,轉移為 ,前提與目標仍相同且為正。固定目標 ,以 表示原問題最短計劃長度, 表示鬆弛最短長度;相應目標不可達時用 。
定理 18.1.7
(刪除鬆弛從不高估)
對每個狀態 與正目標 ,皆有 ,其中 大於任何數。特別地,若鬆弛問題沒有計劃,原問題也沒有計劃。
證明
(在鬆弛模型中模擬原計劃)
由同一狀態開始,在原模型及鬆弛模型執行相同動作序列。起初兩狀態相同。若原目前狀態包含於鬆弛狀態,原可用的正前提在鬆弛狀態仍真。原後繼刪部分事實再加效果,鬆弛後繼只加同樣效果,所以包含關係保持。
歸納可知原計劃也是同長度鬆弛計劃。因此原解存在時 ;用 的延伸次序,也涵蓋不可達情況。若連鬆弛問題都無解,原問題必無解。
證明透視
正性在哪裏被用到
歸納中唯一傳遞的不變量是包含關係:原狀態是鬆弛狀態的子集。正前提具單調性,較大的狀態仍滿足它們;正目標同樣單調,所以較大的最終鬆弛狀態仍包含 。在本模型中,刪除從不有利,刪除鬆弛利用的正是這一點。離開本模型,這一步就失效。設 、、目標 ,動作 前提為 並刪除 ,動作 有否定前提「 為假」並加入 。計劃 解決原問題,但鬆弛後 永不被移除, 永不可用,於是 。
送貨例子中,pickup, driveAB, deliver 是三步鬆弛計劃,因 driveAB 不再刪除 atA。三步也必需:攜帶、在 B 及交付須由三個不同動作取得。因此 ,原最優則是 4。精確鬆弛最優值本身也可能難算;定義鬆弛不自動使其最短距離容易計算。
鬆弛事實層給出較簡單的可採納估計
由目前狀態開始,建立遞增事實集合:
每輪全部前提只讀舊層 ,不讀本輪剛加入的事實。以 表示首個滿足 的層數 ;若到不動點仍無目標,則為 。每個嚴格增長輪至少加一個原本缺席事實,所以至多有 個增長輪;需要時,再一輪無增長即可偵測不動點。
命題 18.1.8
(鬆弛事實層給出下界)
對每個狀態 與正目標 ,
若各層到達不動點仍不含 ,則鬆弛問題沒有計劃,原問題亦沒有計劃。
證明
(鬆弛計劃不會越出事實層)
設 是由 出發的鬆弛計劃, 為執行 個動作後的鬆弛狀態。對 歸納證 。 時 。若 ,則 的前提在 內,其加入效果因此屬於 ;由 得 。長度為 的鬆弛計劃終止時 ,所以 。
若各層在不動點 停止增長而仍不含 ,則每個 ,沒有鬆弛計劃能達到 ;於是 。第二個不等式就是上一條定理。
一層可以同時加入數個動作效果,不是順序動作數,也不是考慮刪除衝突的可執行並行排程。
本例 含 atA, atB, parcelA, carrying, 再含 delivered,三個界為 。 同時有兩個地點,刻意違反原不變量:這些集合是求界用的過度近似,不是真實可達狀態。
例題 18.1.9
(計劃中途的估計)
設 ,目標 。此時只有 driveBA 與 deliver 可用,所以 ,。沒有單一動作同時加入兩個目標事實,而 driveBA, deliver 不論次序都是鬆弛計劃,故 。在原模型中,driveBA 先做會刪去 atB,使 deliver 不可用;deliver, driveBA 則可行,所以 。三個界為 :鬆弛丟失的是次序限制,不是長度;層估計偏低,則因為一層裝著兩個動作的效果。
常見錯誤
常見錯誤
(前提不會自動被刪除,除非它是刪除效果)
把初始狀態施 pickup 的後繼寫成只有 carrying,理由是 atA 與 parcelA「用掉了」。只有 的成員才會被移除。後繼是 atA, carrying:atA 由持續不變規則保留,只有 parcelA 被刪。資源恰好在領域把它列為刪除效果時才被消耗。
常見錯誤
(鬆弛層不是狀態)
把 當成智能體可以處於的狀態,再對它施 driveBA 或由它回歸。它同時含兩個地點與兩個包裹階段,不變量禁止任何可達狀態如此。事實層收集的是 個鬆弛動作之後可能為真的事實;它們唯一的作用是給出界 。
有解練習
快速檢查
(1. 檢查可用性與持續不變規則)
在初始送貨狀態施 pickup。atA 會否因為是前提而被刪?取件能否立即再做一次?
解答 · 解答 1
後繼是 atA, carrying,只刪 parcelA。前提不會只因曾被要求就消失,atA 由持續不變規則保留。再取件失敗,因 parcelA 已假。每次嘗試動作,都先在當前狀態檢查前提。
快速檢查
(2. 回歸被動作破壞的目標)
把單一目標 carrying 經 deliver 回歸。為何聯集公式本身不足?給一個可用前狀態,說明不完整規則會受騙。
解答 · 解答 2
交付刪除 carrying,刪除衝突檢查已排除它作最後動作。只用聯集公式會得到 atB, carrying;該狀態容許交付,但後繼是 atB, delivered,攜帶已假,直接反駁省略衝突檢查的規則。
快速檢查
(3. 計算鬆弛層並解讀結果)
列出送貨初始狀態的 ,給出層估計、最短鬆弛順序長度及真正最短長度。 是原問題可達狀態嗎?
解答 · 解答 3
為 atA, parcelA。第一層由取件加 carrying、由駕車加 atB,得到 atA, atB, parcelA, carrying。第二層加 delivered,故 。鬆弛順序最優為 3,原最優為 4。 不是原可達狀態,因同時含兩地點,也同時含 parcelA 與 carrying。它用於可靠下界,不是執行追蹤。
快速檢查
(4. 同一動作可以服務兩個目標)
由沒有事實開始,目標為 。一動作無前提、無刪除,同時加入 。比較計劃長度與兩個單獨目標距離之和。再改用兩動作,一個只加 ,一個只加 ,比較順序距離與鬆弛層估計。
解答 · 解答 4
聯合動作下,原及鬆弛計劃長度都是 1,層估計也是 1。單獨每目標都花 1,相加成 2,便高估;逐目標相加可重複計算共用動作,不一定可採納。改成兩個獨立動作,順序最優為 2,但兩效果都在第一鬆弛層出現,層估計為 1,仍是下界。這說明不能把層數回報為可執行順序計劃長度。