為甚麼規則系統需要執行政策
診斷系統可以從同一組觀察推得幾個可能行動。例如電池電量低時,一條規則要求充電;外殼損壞時,另一條則禁止充電並要求檢查。單靠觀察,機器無法知道應執行哪個行動。規則作者還要指明怎樣找出可觸發的規則、怎樣從中選擇,以及每個行動如何改變狀態。
本節研究一個小型產生式系統。與正 Horn 閉包不同,觸發規則可以刪除事實,因此較後規則是否可觸發,可能取決於之前的選擇。下面規則是刻意設計的教學政策,並不聲稱適用於所有真實設備;真實安全決策需要獨立驗證條件和控制措施。
精確的執行模型
定義 25.1.1
(規則、可觸發與觸發)
設 是有限原子集合, 是有限規則集合。狀態 是 的子集。規則 有有限正條件 、刪除集 、加入集 ,以及整數優先級 。假設 。當且僅當 ,規則在 中可觸發。觸發後的狀態是
定義 25.1.2
(衝突集與選擇政策)
衝突集由所有可觸發且觸發後確實改變 的規則組成。每一步選取衝突集中優先級最高的規則;若有同級規則,便按規則識別碼的固定全序選第一個。衝突集為空時停止。固定次序令下一個狀態確定,但這是政策選擇,並非所選行動最好的定理。排除不改變狀態的觸發可避免反覆執行無效果的規則,但單憑這點不能保證終止。
定義 25.1.3
(執行軌跡)
軌跡記錄初始狀態及每一步所選規則、已滿足條件 、實際刪除的事實 和加入的事實 、所得狀態。解釋衝突時,也應記錄其他候選規則及其優先級。實際系統須把事實識別碼與證據來源另外保存:來自不同觀察的相同事實,其溯源未必相同。一次執行紀錄本身並不能證明其他政策不會導致不同結果。
定理 25.1.4
(用遞減秩證明終止)
假設存在函數 ,使每條規則在每個可觸發狀態中,只要觸發會改變狀態,便滿足 。那麼從任意初始狀態 出發,對每個在每一步從衝突集選規則並恰在衝突集為空時停止的政策,執行都會在最多 次觸發後終止。採用上述最高優先級與固定次序決勝政策時,給定初始狀態的整條終止軌跡是唯一的。
證明及假設的作用
證明
(遞減的秩限制步數)
按衝突集的定義,每一步都改變狀態。假設因此令非負整數秩在每一步至少減少一。經過 步後,秩至多為 ,故 不可能大於 。因此執行不可能多於 步。由於衝突集非空時執行會繼續,故它在此上界內到達衝突集為空的狀態。
給定狀態時,有限衝突集已確定。若它非空,最高優先級存在;固定識別碼次序從同級規則中選出唯一一條。轉移公式亦唯一決定下一狀態。對步數歸納,任何兩條由 開始的執行都一致直至停止;終止性保證這條唯一軌跡有限。證明沒有說不同優先級表必然有相同終態,也沒有證明政策正確反映應用領域。
證明透視
狀態有限本身不足以保證終止
有限狀態空間只保證無限執行會重複某個狀態,並不保證停止。嚴格遞減的秩排除這種循環。必須檢查每個可觸發且改變狀態的觸發,而不只檢查一個例子的首條軌跡。
算例:互相衝突的建議
例題 25.1.5
(互相衝突的建議:檢查優先於充電)
取原子 ,依次代表電量低、損壞、充電、檢查和待處理。初始狀態為 。政策有兩條規則:
- :條件 ,刪除 ,加入 ,優先級 2。
- :條件 ,刪除 ,加入 ,優先級 1。
初始時兩條規則都可觸發,且都改變狀態。衝突集為 ;因為 2 高於 1,檢查勝出。觸發 得 。兩條規則此時都缺少 ,所以執行停止。軌跡同時解釋為何檢查及為何沒有充電:選中的檢查規則消耗了待處理標記。若從 出發只有 觸發(例如規則庫沒有 ),結果便是 。
對這個規則庫,若 ,取 ;否則取 。每次可觸發都刪去 ,且沒有規則加入 ,因此可應用定理。這個標記是限制每次處理最多一個行動的模型工具,並非電池的物理性質。開始新一輪處理需要明確的重設政策。
例題 25.1.6
(平手與無效果觸發)
設 。規則 的條件為 ,刪除集 ,加入集 ;規則 的條件為 ,刪除集為空,加入集 。兩者優先級都是 3,識別碼次序把 排在 之前。由 出發,兩條規則都可觸發且都改變狀態,所以衝突集是 ,平手時選 。觸發後得 ,兩條規則都不可觸發,終態是 。若把識別碼次序倒轉, 先觸發,得 。此時 可觸發且會改變狀態; 則只會加入已存在的 、又不刪除任何事實,屬於無效果觸發,被排除在衝突集之外。因此 觸發,終態是 。取秩 ,其中 在命題成立時為 ,否則為 : 令第一項下降, 只要改變狀態便令第二項下降。所以 就是這次執行的上界,兩種識別碼次序分別觸發一次和兩次。
例題 25.1.7
(一次觸發也沒有的執行)
在電池例子中,從 開始,此時待處理標記 不在狀態內。兩條規則都不可觸發,衝突集為空,執行立即停止,觸發次數為零;軌跡只有初始狀態。秩為 ,與零次觸發的上界一致。空軌跡並不表示不需要充電或檢查,只表示在這個政策下,沒有待處理標記就沒有規則符合資格。
概念視角算法
推論、決策與執行
觀察 和 可以在正推論層支持互相競爭的候選結論,並不構成矛盾。決策層根據指定優先級選擇檢查;執行層刪除 並記錄所選行動。三層回答不同問題;把充電的推導展示成充電已實際發生,便會錯誤描述軌跡。
反例與限制
反例模式
不同優先級可以改變結果
保持相同初始狀態,但倒轉兩條規則的優先級。此時 先觸發,得到 ;之後由於 不存在, 不能觸發。終態與檢查的結果不同。兩次執行都會終止;終止和確定的決勝次序並不代表結果與政策無關。
有限原子和排除無效果觸發,也不能防止振盪。
反例模式
每一步都改變狀態,執行卻永不結束
設一條規則以 取代 ,另一條以 取代 ,各自以要刪除的原子為條件。從 出發,每步都改變狀態,卻永遠在兩個狀態之間交替。不可能有對兩個轉移都嚴格遞減的自然數秩,否則須有 。
常見錯誤
常見錯誤
(「只觸發一次」是另一種語義)
已觸發的規則可能因狀態改變而再次可觸發。硬性規定「每條規則只觸發一次」可以防止循環,但會改變語義,並可能錯過稍後合理的行動。在上面的兩規則循環中,每條規則只觸發一次,會在 經 後停止,第一條規則其實可觸發的狀態卻被報告為終態。同樣,給予某規則較高優先級並不能證明安全:優先級只編碼設計者選擇的次序。條件、證據、重設行為及後果都要另行檢查。
常見錯誤
(看似合理的秩必須對每次觸發逐一檢驗)
取 看似自然,因為狀態有限。條件為 、刪除集 、加入集 的規則把 變成 , 仍是 ,所以這個 並不下降,不能用它套用定理。某個候選秩失敗,並不能說明執行不會終止;某個秩在一條軌跡上成功,也不能說明甚麼:必須對每個狀態、每次可觸發且改變狀態的觸發證明嚴格下降。
練習
快速檢查
(在電池例子中,設初始狀態為 ,優先級不變。求衝突集、下一狀態及終態。若初始狀態為 ,結果如何?)
列出可觸發的規則,再只保留會改變狀態的。
解答 · 答案
在 的衝突集為 ,觸發後得 ,之後沒有規則可觸發。從 出發的衝突集為 ,得到終態 。只有多於一條規則可觸發且改變狀態時,才需要比較優先級。
快速檢查
(設 ,一條規則要求並刪除 ,加入 ;另一條要求並刪除 ,加入 。優先級可以任意。證明所有執行都終止,並求從 開始的步數上界。若初始狀態是 又如何?)
定義一個秩,計算鏈上還剩多少步。
解答 · 答案
取 。以 取代 至少令秩下降一,即使 已存在也是如此;以 取代 則令秩下降一,即使 已存在也是如此。兩條規則都刪去各自的條件,每次可觸發都改變狀態。故定理適用於所有初始狀態。從 出發秩為 2,最多觸發兩次:。從 出發初始上界為 3;兩種規則次序都會在最多三步內到達 。
快速檢查
(兩條規則都要求並刪除 。第一條加入 ,第二條加入 ,兩者優先級都是 4。識別碼次序先第一條後第二條,初始狀態為 。求軌跡。現在把 視為事實,並把兩條規則的條件和加入項視為 Horn 蘊涵 和 。每個模型是否都令 為真?比較 Horn 閉包與執行結果。)
把執行結果與同一組蘊涵式的閉包比較。
解答 · 答案
初始時兩條規則都屬於衝突集。指定的識別碼次序選第一條,得到 ;第二條隨即不能觸發,軌跡結束。在指定的 Horn 詮釋下, 和 蘊涵 :它在每個模型中都為真,最小 Horn 閉包為 。執行終止於 ,因為所選規則消耗 。執行結果不含 甚至不代表它不被蘊涵,更不代表其否定被蘊涵。
快速檢查
(設計者提出用 作為終止秩。給出一條可觸發且改變狀態、但不令此秩下降的規則,並解釋要應用定理須證明甚麼。)
找一條觸發後事實總數不變的規則。
解答 · 答案
要求並刪除 、加入 的規則,將 變成 ;狀態改變,但 一直是 1。要用定理,必須證明非負整數秩在每個狀態的每一次(如定理所要求)可觸發且改變狀態的觸發中嚴格下降;只檢查一條樣本軌跡並不足夠。