動機
儲存事實的系統必須分清「知道」與「沒有記錄」。數據庫沒有房間有人佔用的記錄,並不自動證明房間空置。會採取行動的系統還有另一區分:行動前為真的事實,行動後可能變假。因此,知識與行動需要兩套清楚的語義,分別說明真確性與狀態改變。
例如,機械人與包裹在同一房間時,一條規則可推出包裹可接觸。移動行動卻可能只移動機械人,留下包裹。若一味累積所有事實而不刪除,機械人很快便會同時「位於」多個房間;若刪掉所有舊事實,又會遺失未受影響的包裹數據。我們必須說明行動改變甚麼,以及保留甚麼。
本節選擇可完整證明的小範圍模型:有限基項 Horn 規則提供透明的推論程序,命題式 STRIPS 提供明確轉移。它們不等於任意一階推理或所有規劃問題的解法,而是讓較豐富系統所需處理的假設先變得可見。
定義
定義 2.1.1
(一階語言與解釋)
一階語言含常數、變量、函數符號,以及指定元數的謂詞符號。項在解釋下指稱物件;原子公式如 表示關係,邏輯連接詞與量詞再組成公式。解釋指定非空論域、常數與函數的意義,以及各謂詞所對應的關係;變量賦值處理自由變量。沒有自由變量的句子在每個解釋中有真值。
定義 2.1.2
(蘊涵、推導、可靠性與完備性)
若每個滿足知識庫 的解釋都滿足句子 ,稱 語義蘊涵 ,寫作 。若按形式規則能證出它,寫作 。可靠性指可推導必可蘊涵;完備性指在指定語言與程序中,蘊涵必可推導。這兩個性質都不表示一個數據不足的知識庫能決定每個句子的真偽。
量詞次序會改變意思。 容許見證 隨 改變, 則要求同一見證適用所有 。代入亦要避免變量捕獲:代入項中的自由變量若意外落入量詞作用域,所得公式便可能不是原來的意思。
定義 2.1.3
(確定 Horn 規則、前向推鏈與模型)
為得到有限可計算片段,固定有限基項原子集 ,並使用確定 Horn 規則:
沒有前提的規則就是事實。設已知事實為 ,從 開始,定義同步前向推鏈:
此片段的模型是包含事實且對所有規則封閉的子集 ;在其命題解釋中,屬於 的原子為真,其餘為假。這為有限片段提供語義,沒有聲稱已枚舉任意一階解釋。
定義 2.1.4
(STRIPS 狀態、行動與計劃)
規劃則固定有限流項集 。完整狀態是子集 ,採封閉世界約定:不在集合內的流項為假。行動 有正前提 、加入效果 與刪除效果 ,加入及刪除集互斥。若前提包含於狀態,行動可用,後繼為:
計劃是依次可用的有限行動序列,最後狀態包含正目標集 時便達標。任意否定前提、條件效果及不確定結果都在此基本形式之外。狀態的封閉世界約定,是建模選擇;它與一般知識庫中保留未知可能的開放世界蘊涵不同。
定理/命題
定理 2.1.5
(有限前向推鏈得到最小模型)
有限基項確定 Horn 知識庫的遞增序列 ,最多嚴格擴張 次便穩定。不動點 是按包含關係的最小模型。原子屬於 ,當且僅當它在所有滿足事實與規則的命題模型中為真。
命題 2.1.6
(用回歸驗證最後一個行動)
設行動 的加入及刪除集互斥, 是正目標集。若 ,執行 不可能達到 。否則定義
對任意狀態 , 當且僅當 在 可用,且 。
回歸把行動後所需的條件改寫為行動前的條件,卻未證明該前置條件從起始狀態可達。向後搜尋仍須處理可達性,不能把一個代數上可行的最後步驟當成完整計劃。
證明思路
證明
(封閉集是模型,且位於所有模型之下)
按定義遞增;每次嚴格變動至少增加一個原先沒有的原子,所以最多有 次。不動點包含事實,而且每條前提已成立的規則,其結論也在集合內,因此是包含 的模型。
任取模型 ,初始有 。若 ,下一輪觸發規則的前提全在 ,由封閉性其結論也在 ,故 。歸納給 。因此,不動點中的每個原子都在所有模型為真。反過來,若原子不在 ,不動點本身便是一個令它為假的模型,故它不被蘊涵。這同時證明程序的可靠性及對基項原子後果的完備性。
證明透視
反模型給出完備方向
逐次檢查規則保持真確性,只足以證可靠性。反方向需要更強的一步:最後封閉集本身必須是一個合法模型。它為每個未推出的原子提供反模型。此構造依賴確定 Horn 規則;任意加入否定或析取,最小模型性質便可能消失,原證明不能照搬。
證明
(行動造成的目標與必須持續的目標)
對回歸定理,若某目標被刪除,由於加入與刪除互斥,它不會再次加入,最後必不成立。否則,在可用行動下,加入集中的目標自動成立;加入集外的目標必須原先成立,而且由相容條件不會被刪除。故達標恰好要求原狀態包含 ;再加可用性所需前提,便是回歸集合。倒過來讀同一論證即證充分性。
按行動序列長度歸納,逐步檢查前提並套用 ,可得到此 STRIPS 模型指定的確切狀態。這是關於模型的驗證,不是感應器與機械操作必然可靠的證明。若真實移動有失敗可能,確定性轉移不能無聲地冒充物理世界保證。
一個實用不變量是「機械人恰在一處」。假設開始成立,每個移動以前提指定原位置,刪除原位置並加入另一位置,而其他行動不改位置,便可歸納保持。原先唯一性排除任何第三位置留下;刪除原位置再加入新位置,恰好保留一個。如果只加入新位置卻不刪舊位置,不變量會立刻失敗。
例題詳解
例題 2.1.7
(推出可接觸性,而不倒轉規則)
已知 、,以及兩者合取推出 的基項規則,一輪前向推鏈便加入可接觸性。若只知道可接觸,卻不能反推兩個位置事實。存在模型令可接觸為真而兩個前提皆假;蘊涵不是等價。儲存這條規則只授權前向推論。
例題 2.1.8
(三個行動的運送計劃)
以 表示機械人在 A 或 B、包裹在 A 或 B,以及攜帶包裹。初始 。拿起行動要求 ,加入 ,刪除 ;移動要求 ,加入 ,刪除 ;放下要求 ,加入 ,刪除 。依序得到 、、,故達成 。三個行動中,只有一次房間之間的移動。
例題 2.1.9
(回歸送達目標)
對放下行動及 ,目標不被刪除。扣去加入的 ,再加前提,得 。再經移動回歸,扣去新加入的 並加原位置,得 ;再經拿起回歸,得 ,正是起始狀態。若目標是 ,放下會刪除所需 ,故不能作最後一步;此模型不能同時要求仍在攜帶且已放下。
常見錯誤
反例模式
存在見證不一定能共用
論域為 ,關係 表示 。每個 都有相等的 ,所以 為真;沒有同一 同時等於零和一,所以 為假。修正方法是保留量詞次序,並記錄見證可依賴哪些較早變量。
常見錯誤
(推不出某原子,不等於推出它的否定)
未推出 ,表示 Horn 片段不蘊涵它,並不表示原知識庫蘊涵 。最小模型令它為假,其他模型仍可令它為真。一般古典知識庫若不一致,根本沒有模型,按定義便真空地蘊涵任何句子。因此,用蘊涵作決策時,一致性檢查有實質作用。
常見錯誤
(連結與欄位也需要明確語義)
語義網絡、框架及腳本可整理知識,但箭頭與欄位需要明確意思。「企鵝是鳥」與「鳥會飛」若同讀為無條件全稱規則,就不能同時保留企鵝例外。腳本記錄典型事件次序,未必列出所有合法事件。例外、缺失步驟及時間次序仍要另外規定。
概念視角結構
把規劃看成圖搜尋
STRIPS 狀態圖最多有 個頂點,可用行動產生有向邊,而目標集合通常對應多個可接受頂點。前向搜尋處理完整狀態,回歸處理足以達標的條件。這個觀點連接規劃與搜尋,同時提醒我們:一個部分目標條件不等於一個完整狀態。
框架問題關注如何表示未改變之物。基本轉移式保留刪除集外的流項,在此受限模型內提供答案,卻不會自動產生未建模的間接效果。刪掉「物件下有支撐」後是否下墜,需要另行描述物理後果;單純加入及刪除列表不會自行發現它。
變量取值於有限個常數時仍可有限地實例化,但函數符號會令閉包變成無限。
通往推廣的路徑
規則含變量時,甚麼會改變?
變量取值於有限個常數時仍可有限地實例化,但函數符號會令閉包變成無限。
若規則中的變量取值於有限個常數,它只代表有限條基礎規則,所以實例化之後,有限情形的定理依然適用。加入函數符號就不同了:由事實 和規則 ,前向推鏈會對每個 推出 ,閉包因而是無限的,也沒有最後一輪。
總結
蘊涵量化所有模型,推導按規則操作句子。有限 Horn 封閉透過最小模型,對基項原子後果同時可靠且完備。STRIPS 明確列出行動效果,回歸則把正目標透過指定行動往前置條件推回。這些保證都依賴表示方式;先檢查量詞、狀態約定及不變量,才信任計算答案。
練習
快速檢查
(事實為 ,規則為 、、、。求同步封閉序列,判斷 是否被蘊涵。移除初始事實後如何?)
逐輪套用規則,每輪只用上一層的結果。
解答 · 答案
、、、,之後不變,所以 被蘊涵。若沒有初始事實,空集已封閉,沒有規則的全部前提成立。循環規則不會自行產生證據, 不被蘊涵。包含所有原子的模型也可以存在;關鍵是最小模型,而不是所有模型唯一。
快速檢查
(給一個滿足 及 ,但不滿足 的模型,說明肯定後件為何不可靠。再證明 與 在古典邏輯中蘊涵 。)
找一個令前提為假、結論為真的賦值。
解答 · 答案
取 假、 真,蘊涵式及後件都真,前件卻假,構成反推的反模型。第二部分,任意滿足 的模型都令 假;若同時令 真, 便假。因此所有滿足兩前提的模型都令 假,證得 。
快速檢查
(行動要求 ,加入 ,刪除 。分別回歸目標 與 ;對相容目標,指出恰有哪些前置狀態足夠。)
對每個目標套用回歸公式,先檢查刪除條件。
解答 · 答案
不交刪除集,回歸為 ,故恰好包含 的狀態足夠,原先 真偽無關。 要求行動刪掉而不重加的 ,因此沒有前置狀態能經此最後行動達標。這不表示換其他最後行動也不能達標。
練習 2.1.10
(證明文中的位置不變量由正確移動保持。再給初始狀態及漏掉刪除效果的錯誤行動,使不變量失敗,並解釋只有前提為何無法修補。)
核心
解答(4)
- 1
假設恰有一個位置,並且移動可用
假設恰有一個機械人位置流項為真,而可用的移動由 去到 。前提保證 就是那個唯一為真的流項。
- 2
刪除舊位置,加入新位置
關鍵一步
刪去 後加入 ,恰有一處位置;其他位置流項仍為假。其他行動按假設不改位置,所以對計劃長度歸納便涵蓋整個計劃。
- 3
漏掉刪除效果
從 出發、只加入 的錯誤移動,產生 :有兩個位置,不變量失敗。
- 4
為甚麼只靠前提無法補救
前提 明明已經滿足,卻攔不住這個錯誤。前提控制行動何時可以開始,刪除效果才控制甚麼不再成立。