规划必须跟踪动作破坏了什么
计划不只是各自有用的动作清单。开车到目的地,会使“身处起点”变假;交付物品,会使“正在携带”变假。因此后续动作可能破坏先前已建立的条件。要推理整个计划,就要精确说明前提、效果及哪些事实保持不变。
本节采用有限命题 STRIPS 模型:前提与目标均为正事实,动作确定,而且每动作成本为一。这是有用的核心规划模型,不涵盖不确定感知、隐藏事实、否定前提或条件效果。
状态指定全部当前为真的事实
定义 18.1.1
(状态、动作与目标)
设 为有限命题事实集合。状态是子集 ,恰好其中成员为真,其余为假。本模型中缺席表示假,不是未知。
动作 有集合 、、,都为 子集,加入与删除集合互不相交。当 时动作可用,后继为
正目标是集合 ,当 时满足。计划是逐步可用的动作序列,最后状态满足 。每动作成本一,因此计划成本就是长度。
前提在执行之前检查,也可以被该动作删除,所以允许消耗必需资源。不在加入或删除集合的事实保持原真假值。这个持续不变约定(frame rule),让我们不必在每个动作逐项列出所有不受影响事实。
事实名字本身不施加逻辑限制。例如任意 子集中,两个地点事实不自动互斥。领域可通过初始状态及动作维持互斥,但必须为可达状态证明此不变量。
一个需要返回起点的送货领域
使用 atA、atB 表示位置,parcelA 表示包裹在 A,carrying 表示正在携带,delivered 表示已交付。初始状态为 ,目标为 。动作为:
| 动作 | 前提 | 加入效果 | 删除效果 |
|---|---|---|---|
pickup | atA, parcelA | carrying | parcelA |
driveAB | atA | atB | atA |
driveBA | atB | atA | atB |
deliver | atB, carrying | delivered | carrying |
这些符号描述一个小型形式领域,除此明定事实与动作以外,不暗中假定其他物理规则。
例题 18.1.2
(送达后仍要返回,才完成整个目标)
执行以下四动作计划:
| 步数 | 刚执行动作 | 结果状态 |
|---|---|---|
| 0 | 无 | atA, parcelA |
| 1 | pickup | atA, carrying |
| 2 | driveAB | atB, carrying |
| 3 | deliver | atB, delivered |
| 4 | driveBA | atA, delivered |
取件不改位置,开车不改携带状态,交付不改位置。这些都由持续不变规则推出,不是要猜测的遗漏效果。
计划最短:只有 deliver 加入 delivered,它要求携带对象且身处 B;只有在 A 可用的 pickup 产生携带状态。因此交付前至少要一次 driveAB。由下文将证的地点不变量,交付在 B 时 atA 必假;最后要求在 A,所以之后还要 driveBA。四种不同必需动作给出四步下界,上述计划恰好达到。
命题 18.1.3
(地点与包裹阶段不变量)
从 出发,经任何可用动作序列到达的状态,恰含 atA、atB 之一,也恰含 parcelA、carrying、delivered 之一。
证明
(对计划长度归纳)
初始状态恰有 atA、atB 之一。取件与交付不改这两个事实。如果在恰有一个地点的状态中 driveAB 可用,则 atA 为真、atB 为假;删去前者、加入后者,仍恰有一个。反方向开车同理。对计划长度归纳,可知全部可达状态都保持此性质。
同样,parcelA、carrying、delivered 恰有一个成立:取件把第一个变成第二个,交付把第二个变成第三个,开车则全都不改。
证明透视
不变量依赖什么
归纳逐一检查本领域的四个动作,每次检查都用到动作完整的三元组。driveAB 能保持恰有一个地点,是因为前提 atA 连同归纳假设迫使 atB 为假,而且它删去 atA、加入 atB。如果多加一个动作 teleport,无前提、加入 、没有删除效果,不变量立刻失效:在 上执行后得到 。所以不变量刻画的是这一组动作,而不是任意的 子集。论证之所以能收尾,是因为动作只有有限个,每个都保持此性质,而初始状态具备此性质。
目标回归问的是前一步必须满足什么
前向搜索把动作用于状态,向后的目标回归则把可能的最后动作用于目标条件。结果是对前一状态的要求,不是模拟出一个完整前状态。
定理 18.1.4
(正目标的精确回归)
对动作 与目标集合 :
- 如果 ,不存在任何状态能把 当最后动作,之后满足 。
- 否则定义
在此没有删除冲突的情况,对每个状态 ,“ 可用且后继满足 ”恰好等价于 。
证明
(分开动作造成的目标与必须持续的目标)
如果某目标被删除,加入与删除集合互不相交,保证它不会再加回,后继必缺该事实,所以动作不能是达成 的最后一步。
现在假设没有目标被删除。可用性恰好要求 。加入集合内的目标执行后必真,不要求之前已真。加入集合以外的目标,因不被删除,执行后为真恰好等价于在 已真,所以剩余要求为 。
两条件合并就是所列并集,正反方向都成立。这在正前提、正目标模型中精确,但不暗中处理否定目标或条件效果。
此等价描述形式状态的条件;某状态是否从指定初始状态可达,是另一个问题。
回归整个计划,不是各目标分开处理
从送货目标开始,反向选择最后动作:
| 动作之后的目标 | 拟定最后动作 | 回归到动作之前的目标 |
|---|---|---|
atA, delivered | driveBA | atB, delivered |
atB, delivered | deliver | atB, carrying |
atB, carrying | driveAB | atA, carrying |
atA, carrying | pickup | atA, parcelA |
最后回归集合包含于 。把所选动作按正向读,就得到已验证四步计划。回归子目标不必指定前状态的全部事实;没列出的事实,不受此目标条件限制。
如果尝试把 deliver 当完整目标的最后动作,回归会得到 atA, atB, carrying。删除集合虽没有直接冲突,但前提 atB 与必须保留的 atA 产生了依已证地点不变量不可达的子目标。分开达到 atA 与 delivered,不足以安排整个计划,因为开车会破坏位置目标。
例题 18.1.5
(通向不可达子目标的回归步骤)
取目标 。有两个动作会加入其中一个事实。
经 pickup:删除集合 与目标不相交,所以
对形式状态而言公式是精确的:这个集合确实允许取件,并到达含目标的状态。但它同时含两个地点,按地点不变量,没有可达状态满足它,这个分支合法却是死路。
经 driveAB:删除集合 同样与目标不相交,。再经 pickup 回归,得到 。这个分支还原出前缀 pickup, driveAB。
反例模式
略过删除冲突检查会使回归不可靠
取目标 atA, delivered 与动作 driveAB。如果盲用并集公式,回归仍是 atA, delivered。恰有这两事实的可达状态符合此条件,动作也可用,但后继为 atB, delivered,因 atA 被删而不符合目标。
所以 不可省略。没有检查删除效果,就不能对任意最后动作使用回归公式。
前向广度优先搜索提供完备基准
状态至多有 个。动作有限时,在可用转移上做广度优先搜索,就完备,且在每步成本一的假设下找到最短计划。状态入队时就标记已见,避免反复开车等环造成无限重复工作。
PLAN_BFS(initial, goal):
queue = [initial]
seen = {initial}
predecessor[initial] = NONE
while queue is not empty:
S = remove first state from queue
if goal is a subset of S:
return reconstruct action sequence from predecessor
for each action a:
if Pre(a) is a subset of S:
T = (S minus Del(a)) union Add(a)
if T is not in seen:
add T to seen
predecessor[T] = (S, a)
append T to queue
return NO_PLAN
定理 18.1.6
(广度优先规划在单位成本下完备且最优)
设事实集合 有限,动作成本都为一,则 PLAN_BFS 必定终止。当且仅当初始状态已满足目标时返回空计划;有计划时返回最短计划;当且仅当没有计划时返回 NO_PLAN。
证明
(队列的层次就是计划长度的层次)
每个状态入队时即标记已见,所以至多入队一次,而状态至多 个,循环因此终止。每条生成边都是合法动作,所以重建计划可靠。队列先进先出:某层的后继都排在该层剩余状态之后,归纳可知出队顺序按最小动作数不递减,因此第一个出队的目标状态长度最小。队列清空时,全部可达状态都已检查,所以没有计划。如果初始已满足目标,就得到空计划。
有限状态完备不表示便宜,因为状态数对 是指数。
本领域两不变量只允许六种组合:两地点乘三包裹阶段。表中计划经过五种,第六种 atB, parcelA 可从初始直接开车到达,所以六者都可达。抽象幂集上界为 32,而 BFS 在深度四首次到达完整目标。如果动作成本不同,普通 BFS 不再证明最小成本,搜索方法要配合成本模型。
忽略删除给出下界,不给出另一个真实计划
把每个删除集合改为空,得到删除松弛模型,转移为 ,前提与目标仍相同且为正。固定目标 ,以 表示原问题最短计划长度, 表示松弛最短长度;相应目标不可达时用 。
定理 18.1.7
(删除松弛从不高估)
对每个状态 与正目标 ,都有 ,其中 大于任何数。特别地,如果松弛问题没有计划,原问题也没有计划。
证明
(在松弛模型中模拟原计划)
从同一状态开始,在原模型及松弛模型执行相同动作序列。起初两状态相同。如果原当前状态包含于松弛状态,原可用的正前提在松弛状态仍真。原后继删去部分事实再加入效果,松弛后继只加入同样的效果,所以包含关系保持。
归纳可知原计划也是同长度的松弛计划。因此原解存在时 ;用 的扩展次序,也涵盖不可达情况。如果连松弛问题都无解,原问题必无解。
证明透视
正性用在哪里
归纳中唯一传递的不变量是包含关系:原状态是松弛状态的子集。正前提具有单调性,更大的状态仍满足它们;正目标同样单调,所以更大的最终松弛状态仍包含 。在本模型中,删除从不有利,删除松弛利用的正是这一点。离开本模型,这一步就失效。设 、、目标 ,动作 的前提为 并删除 ,动作 有否定前提“ 为假”并加入 。计划 解决原问题,但松弛后 永远不会被移除, 永远不可用,于是 。
送货例子中,pickup, driveAB, deliver 是三步松弛计划,因为 driveAB 不再删除 atA。三步也必需:携带、在 B 及交付要由三个不同动作取得。因此 ,原最优则是 4。精确松弛最优值本身也可能难算;定义松弛不自动使其最短距离容易计算。
松弛事实层给出较简单的可采纳估计
从当前状态开始,建立递增事实集合:
每轮全部前提只读旧层 ,不读本轮刚加入的事实。以 表示首个满足 的层数 ;如果到不动点仍无目标,则为 。每个严格增长轮至少加一个原本缺席事实,所以至多有 个增长轮;需要时,再一轮无增长即可检测不动点。
命题 18.1.8
(松弛事实层给出下界)
对每个状态 与正目标 ,
如果各层到达不动点仍不含 ,则松弛问题没有计划,原问题也没有计划。
证明
(松弛计划不会越出事实层)
设 是从 出发的松弛计划, 为执行 个动作后的松弛状态。对 归纳证明 。 时 。如果 ,则 的前提在 之内,其加入效果因此属于 ;由 得 。长度为 的松弛计划结束时 ,所以 。
如果各层在不动点 停止增长而仍不含 ,则每个 ,没有松弛计划能达到 ;于是 。第二个不等式就是上一条定理。
一层可以同时加入数个动作的效果,它不是顺序动作数,也不是考虑删除冲突的可执行并行调度。
本例 含 atA, atB, parcelA, carrying, 再含 delivered,三个界为 。 同时有两个地点,刻意违反原不变量:这些集合是求界用的过度近似,不是真实可达状态。
例题 18.1.9
(计划中途的估计)
设 ,目标 。此时只有 driveBA 与 deliver 可用,所以 ,。没有单个动作同时加入两个目标事实,而 driveBA, deliver 不论次序都是松弛计划,所以 。在原模型中,先做 driveBA 会删去 atB,使 deliver 不可用;deliver, driveBA 则可行,所以 。三个界为 :松弛丢掉的是次序限制,而不是长度;层估计偏低,则是因为一层里装着两个动作的效果。
常见错误
常见错误
(前提不会自动被删除,除非它是删除效果)
把初始状态上执行 pickup 的后继写成只有 carrying,理由是 atA 与 parcelA 已经“用掉”。只有 的成员才会被移除。后继是 atA, carrying:atA 由持续不变规则保留,只有 parcelA 被删去。只有当领域把资源列为删除效果时,它才被消耗。
常见错误
(松弛层不是状态)
把 当作智能体可以处于的状态,再对它执行 driveBA 或从它回归。它同时含两个地点和两个包裹阶段,而不变量禁止任何可达状态如此。事实层收集的是 个松弛动作之后可能为真的事实;它们唯一的作用是给出界 。
有解练习
快速检查
(1. 检查可用性与持续不变规则)
在初始送货状态施 pickup。atA 会否因为是前提而被删?取件能否立即再做一次?
解答 · 解答 1
后继是 atA, carrying,只删 parcelA。前提不会只因曾被要求就消失,atA 由持续不变规则保留。再取件失败,因为 parcelA 已假。每次尝试动作,都先在当前状态检查前提。
快速检查
(2. 回归被动作破坏的目标)
把单一目标 carrying 经 deliver 回归。为什么并集公式本身不足?给一个可用前状态,说明不完整规则会受骗。
解答 · 解答 2
交付删除 carrying,删除冲突检查已排除它作最后动作。只用并集公式会得到 atB, carrying;该状态允许交付,但后继是 atB, delivered,携带已假,直接反驳省略冲突检查的规则。
快速检查
(3. 计算松弛层并解读结果)
列出送货初始状态的 ,给出层估计、最短松弛顺序长度及真正最短长度。 是原问题可达状态吗?
解答 · 解答 3
为 atA, parcelA。第一层由取件加 carrying、由开车加 atB,得到 atA, atB, parcelA, carrying。第二层加 delivered,所以 。松弛顺序最优为 3,原最优为 4。 不是原可达状态,因为同时含两地点,也同时含 parcelA 与 carrying。它用于可靠下界,不是执行跟踪。
快速检查
(4. 同一动作可以服务两个目标)
从没有事实开始,目标为 。一动作无前提、无删除,同时加入 。比较计划长度与两个单独目标距离之和。再改用两动作,一个只加 ,一个只加 ,比较顺序距离与松弛层估计。
解答 · 解答 4
联合动作下,原及松弛计划长度都是 1,层估计也是 1。单独每目标都花 1,相加成 2,就高估;逐目标相加可重复计算共用动作,不一定可采纳。改成两个独立动作,顺序最优为 2,但两效果都在第一松弛层出现,层估计为 1,仍是下界。这说明不能把层数报告为可执行顺序计划长度。