一个偏序规划的例子

11.3.1 一个偏序规划的例子

现在我们看一下POP是怎样解决第11.1节的备用轮胎问题的。图11.7重复了问题的描述。

图11.7 简单漏气轮胎问题描述

对解的搜索从初始规划开始，初始规划包含一个具有效果At(Spare, Trunk)∧At(Flat, Axle)的Start行动和具有唯一前提At(Spare, Axle)的Finish行动。接着通过挑选一个开放前提来继续工作（不能取消的）和从可能得到后继的行动中进行选择，从而生成后继规划。目前，我们不再担心帮助决策的启发式函数；我们将做表面上任意的选择。事件序列如下：

（1）选择 Finish 状态的唯一开放前提 At(Spare, Axle)。选择唯一的可用行动 PutOn(Spare, Axle)。

（2）选择PutOn(Spare, Axle)的前提At(Spare, Ground)。选择唯一的可用行动Remove(Spare, Trunk)来获得它。结果规划如图11.8所示。

图11.8 轮胎问题中，在对前两个开放前提选择行动后的不完全偏序规划。线框表示行动，左边是前提，右边是效果。（效果被忽略，除了Start行动之外。）黑箭头表示保护箭头头部的命题的因果连接

（3）选择PutOn(Spare, Axle)的前提¬At(Flat, Axle)。正好相反，选择行动LeaveOvernight，而不是行动Remove(Flat, Axle)。注意行动LeaveOvernight同时还有效果¬At(Spare, Ground)，这意味着它同因果连接

相冲突。为了解决冲突，添加一个定序约束，把LeaveOvernight放在Remove(Spare, Trunk)之前。结果规划如图11.9所示。（为什么这能解决冲突，为什么没有其它方法解决？）

图11.9 在选择LeaveOvernight作为行动以获得¬At(Flat,Axle)之后的规划。为了避免同保护At(Spare,Ground)的来自Remove(Spare,Trunk)的因果连接冲突，LeaveOvernight被约束为在Remove(Spare,Trunk)之前发生，如虚线箭头所示

（4）现在剩下的唯一开放前提是行动Remove(Spare, Trunk)的前提At(Spare, Trunk)。唯一能够获得它的行动是已经存在的 Start行动，但是从 Start到 Remove(Spare, Trunk)的因果连接与LeaveOvernight的效果¬At(Spare, Trunk)相冲突。这次无法解决与LeaveOvernight的冲突了：我们不能将它排在 Start 之前（因为没有东西能出现在 Start 之前），我们也不能把它排在Remove(Spare, Trunk)之后（因为已经有一个约束把它排在Remove(Spare, Trunk)之前了）。所以我们只能被迫后退，删除Remove(Spare, Trunk)行动和最后两个因果连接，返回图 11.8 所示的状态。本质上，规划器证明了 LeaveOvernight 对于换轮胎不起作用。

（5）再次考虑PutOn(Spare, Axle)的前提¬At(Flat, Axle)。这次我们选择Remove(Flat, Axle)。

（6）再一次，选择行动Remove(Spare, Trunk)的前提At(Spare, Tire)，并选择Start来获得它。这一次没有冲突。

（7）选择行动Remove(Flat, Axle)的前提At(Flat, Axle)，并选择Start来获得它。这给我们提供了一个完整的、一致的规划——换句话说，一个解——如图11.10所示。

图11.10 轮胎问题的最后解。注意Remove(Spare,Trunk)和Remove(Flat,Axle)可以在任一顺序下进行，只要它们在行动PutOn(Spare,Axle)之前完成

虽然这个例子很简单，但是它说明了偏序规划的某种实力。首先，因果连接导致了早期对因不能解决的冲突而不包含解的搜索空间部分进行剪枝。其次，图11.10中的解是一个偏序规划。在这种情况下，其优点是规模小，因为只有两个可能的线性化；虽然如此，智能体还是可能欢迎灵活性的——例如，在繁忙的交通中不得不更换轮胎。

这个例子也指出可以进行某些可能的改进。例如，有重复的尝试：在冲突引起回溯之前，Start连接到Remove(Spare, Trunk)，然后由于回溯而断开连接，尽管它不涉及该冲突。当搜索继续时它又被重新连接。这是一个典型的历时回溯，可能被由依赖关系所指导的回溯减轻。