动机
存储事实的系统必须分清“知道”与“没有记录”。数据库没有房间有人占用的记录,并不自动证明房间空置。会采取行动的系统还有另一区分:行动前为真的事实,行动后可能变假。因此,知识与行动需要两套清楚的语义,分别说明真确性与状态改变。
例如,机器人与包裹在同一房间时,一条规则可推出包裹可接触。移动行动却可能只移动机器人,留下包裹。若一味累积所有事实而不删除,机器人很快便会同时“位于”多个房间;若删掉所有旧事实,又会遗失未受影响的包裹数据。我们必须说明行动改变什么,以及保留什么。
本节选择可完整证明的小范围模型:有限基项 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
为什么只靠前提无法补救
前提 明明已经满足,却拦不住这个错误。前提控制行动何时可以开始,删除效果才控制什么不再成立。