无约束变量的偏序规划

11.3.2 无约束变量的偏序规划

在这一节中，我们考虑当POP和包含变量的一阶行动表示一起使用时，可能出现的复杂因素。假设我们有一个积木世界问题（图11.4），它具有开放前提On(A,B)和行动

Action ( Move(b, x, y)，

PRECOND：On(b,x)∧Clear(b)∧Clear(y),

EFFECT：On(b,y)∧Clear(x)∧¬On(b,x)∧¬Clear(y))

这个行动获得On(A, B)，因为效果On(b, y)在置换{b/A, y/B}下与On(A, B)合一。然后我们将这个置换应用到行动中，产生

Action ( Move(A, x, B)，

PRECOND：On(A,x)∧Clear(A)∧Clear(B),

EFFECT：On(A,B)∧Clear(x)∧¬On(A,x)∧¬Clear(B))

这里留下变量x是无约束的。也就是，行动说从某处移动积木A，而不说出从何处。这是最少承诺原则的另一个例子：我们可以推迟进行选择，直到规划中的某个其它步骤为我们做出选择。例如，假设我们在初始状态中有On(A, D)。那么Start行动可以用来获得On(A, x)，把x与D绑定。这种在选择x之前等待更多信息的策略通常比尝试x的所有可能值并对每个失败结果进行回溯的方法更加有效。

前提和行动中变量的出现使得发现和解决冲突的过程复杂化。例如，当Move(A, x, B)被添加到规划中时，我们将需要一个因果连接

如果存在另一个具有效果¬On(A, z)的行动M2，那么只有当z是B时M2才发生冲突。为了容纳这种可能性，我们扩展规划的表示，以包含一组形如z ≠ X——其中z是变量，X是另一个变量或一个常量符号——的不等式约束。在这种情况下，我们通过添加z ≠ B来解决冲突，意味着未来对规划的扩展可以把z实例化为除了B以外的任何值。任何时候我们把一个置换用于规划时，必须检验不等式与置换不冲突。例如，包含x / y的置换与不等式约束x ≠ y冲突。这样的冲突无法解决，所以规划器必须回溯。

在积木世界中含有变量的POP规划的更详尽例子将在第12.6节中给出。