動機
一批效果有用的行動,尚未構成計劃。每個行動開始時前提必須成立,之後的行動也不能破壞較後步驟需要的事實。同一批行動換個次序,就可能由成功變失敗。規劃因此既要找誰產生事實,也要保護事實到使用之時。
狀態空間搜尋每步承諾一個完整後繼狀態;計劃空間搜尋則細化行動出現及次序約束,把暫不重要的順序押後決定。一個偏序可同時表示多個合法順序,但其因果承諾要仔細驗證。沒有指定先後,並不自動表示能在物理上同時執行。
本節沿用有限、確定、正前提 STRIPS,再給兩套有明確假設的完備算法:有限狀態圖的廣度優先搜尋,以及在指定行動數上界內完備的偏序細化。
定義
定義 6.1.1
(STRIPS 規劃問題與狀態轉移)
設有限命題集 、初始狀態 、正目標 及有限基項行動集 。行動有正前提、互斥的加入與刪除集;可用時後繼為 。最短長度結果假設每個行動成本為一。可能狀態至多 個,其中一些根本不可達。
定義 6.1.2
(行動出現與偏序計劃)
行動出現指某一個特定步驟,同一基項行動可在計劃出現多次。偏序計劃含有限出現、嚴格無環先後關係,以及兩特殊步:Start 加入恰好 且無前提;Finish 以前提 作檢查且無效果。Start 先於 Finish 及所有普通步,普通步先於 Finish。線性化是延伸所有先後約束的全序。
定義 6.1.3
(因果連結、威脅與開放條件)
因果連結 聲稱 建立 所需的 ,且中間保持它。要求 、、。步驟 若刪除 ,而次序未強制 或 ,便威脅此連結。兩種排除把刪除者放在受保護區間之外。尚無支持連結的前提出現,稱為開放條件。不能用 :行動後才產生的效果不能支持自己行動前的前提。
定義 6.1.4
(完整受保護計劃)
完整受保護計劃沒有開放條件,所有連結均無威脅,且次序無環。它是可驗證證書,但可有多餘行動或連結;最小性另論。其語義只保證合法順序執行,不包含持續時間、同時動作及資源容量。
定理/命題
定理 6.1.5
(有限狀態圖上的最短長度完備搜尋)
由 廣度優先搜尋,產生每個可用基項行動,並在入隊時只記錄每個狀態一次,便會終止。若目標可達,返回行動數最少的計劃;否則報失敗。狀態鍵必須保留所有會影響可用性及效果的事實。
定理 6.1.6
(受保護計劃與有界細化完備性)
完整受保護計劃的每個線性化都可執行並達到 。對有限上界 ,下述窮盡細化程序會終止,且恰在存在至多 個普通行動的有效計劃時成功。完整性要求嘗試每種行動指定、支持者及相容威脅解法;一條貪婪細化路徑不足。
證明思路
證明
(廣度優先次序與最短路徑)
廣度優先先把 入隊、標為已訪。反覆取最早入隊狀態,檢查目標,並計算每個可用行動的後繼。後繼未訪才入隊,同時標記並保存前驅狀態與行動;取出目標時倒追前驅重建序列,隊列空則失敗。
按圖距離歸納,距離 的狀態必先於新發現距離 的狀態取出。若某可達狀態遺漏,取它最短路的前驅,前驅已被生成,最後合法行動便會生成它,矛盾。故首個取出的目標距離最小。最多 個狀態入隊,加上每步有限工作,便證終止。
證明
(受保護計劃的可靠性)
偏序可靠性取任一線性化,依步驟歸納。下一步 的每個前提 均有較早 的支持連結。Start 建立相應初始事實,普通支持者執行後建立加入效果;所有會刪 的其他步均被安排在 之前或 之後,所以沒有中途刪除。故執行 前 仍真,所有前提都成立。套到 Finish 即得所有目標。
證明透視
因果連結證明一段區間內的持續性
支持者只證事實在某時成立,威脅保護則證它在使用前不被破壞,缺一不可。可靠性不要求所有事實永遠保持,只保護計劃真正需要的各個時間區間。這比一句含糊的「行動不會互相影響」更準確。
有界程序如下。對每個 建立 個標記普通出現,窮舉把基項行動指定給它們的所有方式。先加 Start、Finish 的基本次序,把普通步全部前提及 Finish 目標放入開放議程。選 ,對所有能加入 且不是 的出現 (包括 Start)分支,加 及連結,再移除該開放條件;次序成環便丟棄分支。對威脅 ,再分別嘗試 或 ,同樣棄環。繼續至條件與威脅清空,或所有分支失敗。
證明
(有界細化的終止性與完備性)
指定方式與前提出現均有限。每次選支持者永久減一個開放條件,每次解威脅加入一個先前未被強制的先後關係,且不再撤除。步驟對有限,所以每枝長度及分支數均有限,窮盡程序終止。成功分支的拓撲序由可靠性給可執行計劃。
要證完整,假設有 不超 的有效序列,某種指定必包含恰好這些出現。每個前提選最近的較早加入者,若從初始一直保持則選 Start。有效性保證有支持者,且中間沒有刪除;若有重加者,它才是更近支持者。每個威脅依見證序列放在支持前或使用後。所有約束均符合該序列,故不成環,此枝會完成。上界不可略: 為三的失敗只否定三步內計劃,不否定更長計劃。
例題詳解
例題 6.1.7
(最短計劃可先破壞已達目標)
初始 表示有蛋糕,目標 要求有蛋糕且吃過。Eat 要求 ,加入 ,刪 ;Bake 無前提,只加入 。空計劃與任何單步都失敗。Eat 再 Bake 依次得 、,兩步成功。Bake 再 Eat 則最後刪掉 而失敗。已為真的目標可能必須暫時放棄。
例題 6.1.8
(威脅解法決定有用次序)
用 Start 支持 Eat 的 ,Eat 支持 Finish 的 ,Bake 支持 Finish 的 。Eat 刪 ,威脅 Bake Finish。Finish 在 Eat 前不合法,只能令 Eat 在 Bake 前,得成功序列。若試以 Start 直接支持 Finish 的 ,Eat 的兩種排除都違反 Start、Finish 基本次序,此枝應失敗。
概念視角組合
計劃是一組線性延拓
受保護計劃描述的是一整組動作序列:可執行的次序恰是延拓優先關係的全序,即該偏序的線性延拓。在蛋糕計劃中,「先吃後烤」的約束只留下一個序列。若有 個普通步驟而彼此沒有約束,便有 個序列,受保護計劃保證它們全部有效。每多一條因果或威脅約束,就減少一部分這種彈性。
例題 6.1.9
(獨立子目標不用任意排序)
初始 。A 要求 並加 ,B 要求 並加 ,皆不刪事實,目標 。由 Start 各支持 ,A、B 各支持 Finish 的目標,便得無須比較 A、B 的完整計劃。A,B 與 B,A 都合法。但單一機器可能有未建模共享資源禁止重疊,兩個合法順序不等於可同時做。
常見錯誤
反例模式
有用行動可破壞彼此前提
初始 。A 要求 ,加 並刪 ;B 要求 並加 ,目標 。Start B 被 A 威脅,只能令 B 先於 A,因 A 不能先於 Start。A 再 B 會在 B 的前提失敗。因此只有行動名稱集合不足以證計劃。
常見錯誤
(把刪除集當作全部變化)
框架問題在此模型內有局部答案:刪除集外事實保持。但這依賴描述已包含所有相關變化。若開鎖透過間接機制關掉警報,而警報影響未來,就要把效果表示出來,或明訂擴充語義推導;規劃器不會自動發現物理定律。
常見錯誤
(只對直接邊檢查威脅)
威脅檢查必須使用傳遞關係。若多條約束已蘊涵 ,即使沒有直接邊也已排除威脅;多步隱藏環同樣無效。需要可達性或拓撲檢查,不能只看新邊兩端。
常見錯誤
(把完備性當作對真實任務的保證)
完備性亦假設相關行動全部已基項化並生成;缺少行動庫可令真實有解而模型失敗。資訊收集、不確定性、時間及資源都是此模型外的重要問題。
總結
廣度優先給有限完備基準及最短行動數。因果連結說誰建立所需事實,威脅解決保護它到使用。窮盡有界細化之所以完備,是因每個界內有效見證都有相容分支。次序、持續性及模型充分性,各自需要論證。
練習
練習 6.1.10
(在蛋糕例題中列出由 可達的所有狀態,並說明廣度優先搜尋只保存狀態而非每段行動歷史,為何不失完整性。)
核心
解答(3)
- 1
列出可達狀態
在 時 Bake 不改變狀態,Eat 得 。由 出發,Bake 得 ,Eat 不可用。由 出發,Eat 回到 ,Bake 不變。可達狀態為 、 與 。
- 2
論證狀態已足夠
關鍵一步
兩段歷史若終於同一狀態,之後可行的延續完全相同,因為可用性與效果只依賴狀態。
依據: 狀態包含全部可用性及效果的資訊。
- 3
保留首段歷史
保留廣度優先搜尋到達每個狀態的首段歷史,就保留了到該狀態的最短路徑,所以丟棄其後的歷史既不損失完整性,也不損失最短長度。
練習 6.1.11
(對常見錯誤的例子,給出成功的受保護計劃的全部因果連結及一個線性化,並指出威脅及唯一一致的解法。)
核心
解答(3)
- 1
列出因果連結
使用 Start B、Start A、A Finish 及 B Finish。
- 2
找出威脅及解法
關鍵一步
A 刪除 ,所以威脅連結 Start B。A 先於 Start 不可能,因為 Start 先於所有步驟,所以只剩 B 先於 A。A 的刪除不威脅它自己的入連結,因為前提先測、效果後施。
依據: A 刪除 ,而 B 需要來自 Start 的 。
- 3
寫出一個線性化
合法順序 B,A 同時達成 和 。
練習 6.1.12
(設 是連結,而相異的刪除步 已被約束為 。證明兩種一般威脅解法都不能成功。更換因果連結後,甚麼新支持可能修復計劃?)
綜合證明
解答(3)
- 1
嘗試第一種解法
解法 要加到已有的約束 之上。
- 2
嘗試第二種解法
關鍵一步
解法 要加到已有的約束 之上。兩種解法各自形成兩條約束的環,所以兩枝都被棄去。
- 3
考慮修復
∎若有行動 能在 與 之間重新加入 ,把連結換成 便可能修復支持,條件是 本身的前提有支持,且所有新威脅都獲解決。這是選新支持者的另一枝,不是忽略舊威脅。
練習 6.1.13
(若有界細化程序在 窮盡所有分支都失敗,證明了甚麼?說明遞增上界一般為何只給半判定程序,以及在本節假設下,有限狀態搜尋為何有更強的、會終止的判定程序。)
綜合
解答(3)
- 1
說明失敗證明了甚麼
在窮盡生成且檢查正確的前提下,它否定零、一、二個普通行動的所有計劃,但不能否定更長的計劃。
- 2
描述半判定程序
逐一嘗試遞增的有限上界,若有有限計劃就終會找到,但若無計劃,單憑此法沒有停止準則。
- 3
與有限狀態搜尋比較
廣度優先搜尋窮盡有限狀態圖,因此能證明失敗。事實上,任何可達目標都有至多 步的簡單狀態路徑,用此上界也能有限窮盡,只是成本通常極大。
依據: 在有限命題的假設下,狀態圖是有限的。