为什么规则系统需要执行策略
诊断系统可以从同一组观察推得几个可能行动。例如电池电量低时,一条规则要求充电;外壳损坏时,另一条则禁止充电并要求检查。单靠观察,机器无法知道应执行哪个行动。规则作者还要指明怎样找出可触发的规则、怎样从中选择,以及每个行动如何改变状态。
本节研究一个小型产生式系统。与正 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。要用定理,必须证明非负整数秩在每个状态的每一次(如定理所要求)可触发且改变状态的触发中严格下降;只检查一条样本轨迹并不足够。