后向状态空间搜索

后向状态空间搜索在第三章中作为双向搜索的一部分进行了简要描述。我们注意到当目标状态用一个约束集来描述而不是明确地列出时，后向搜索难以实现。特别地，如何生成目标状态集的可能前辈的描述并不总是显而易见的。我们将看到STRIPS表示使这个问题变得相当容易，因为状态集能够被在这些状态中一定为真的文字所描述。

后向搜索的主要优点是允许我们只考虑相关的行动。如果一个行动获得目标的合取子句中的一个，我们就说这个行动同目标合取式是相关的。例如，在我们的10机场航空货物问题中的目标是B机场拥有20件货物，或者更确切地

At(C1,B)∧At(C2,B)∧ ... ∧At(C20,B)

现在考虑合取子句At(C1, B)。运转后向搜索，我们寻找以此合取子句为效果的行动。只有一个这样的行动：Upload(C1, p, B)，这里飞机p没有被指定。

注意有许多不相关的行动也能够导向目标状态。例如，我们可以让一架空飞机从JFK飞到SFO；这个行动从“飞机在JFK并且目标的所有合取子句都得到满足”的前辈状态达到一个目标状态。一个允许不相关行动的后向搜索仍然是完备的，但是它会十分低效。假如解存在，它能被只允许相关行动的后向搜索找到。相关行动的限制意味着后向搜索比前向搜索有少得多的分支因子。例如，我们的航空货物问题有约1000个从初始状态出发的前向行动，但是从目标出发的后向行动只有20个可行。

后向搜索有时候也称为回归规划。回归规划中的原则问题是这样的：对哪些状态应用行动会到达目标？计算这些状态的描述称为经过行动的目标回归。考虑航空货物例子，来看应该怎么做。我们有目标

At(C1,B)∧At(C2,B)∧ ... ∧At(C20,B)

和获得第一个合取子句的相关行动Upload(C1, p, B)。仅当其前提得到满足时行动才会起作用。因此，任何前辈状态必须包含这些前提：In(C1, p)∧At(p, B)。而且，子目标At(C1, B)在前辈状态中应该不为真[4]。因此，前辈的描述是

In(C1,p)∧At(p,B)∧At(C2,B)∧ ... ∧At(C20,B)。

除了坚持行动达到某个期望的文字外，我们还知道必须坚持行动不撤消任何期望的文字。一个满足这种约束的行动被称为一致的。例如，行动Load(C2, p)与当前的目标不是一致的，因为它会否定文字At(C2, B)。

在给定相关性和一致性的定义之后，我们能够描述后向搜索中构造前辈的一般过程。已知一个目标描述G，A是一个相关而且一致的行动。对应的前辈如下：

删除G中出现的A的任何正效果。

添加A的每一个前提文字，除非它已经出现了。

任何标准的搜索算法都能被用来执行这个搜索。当生成的前辈描述被规划问题的初始状态所满足时，发生终止。在一阶情况下，满足性可能需要前辈描述中的变量置换。例如，前一段落中的前辈描述，通过置换{p/P12}被初始状态

In(C1,P12)∧At(P12,B)∧At(C2,B)∧ ... ∧At(C20,B)

所满足。置换必须用于从状态引向目标的行动，产生解Upload(C1,P12,B)。