1.前向状态空间搜索<br> 前向规划器（progression planner）主要进行正向规划，即从初始状态到目标状态，考虑在一个给定状态中的所有可能动作的所有效果。<br> 当一个操作的前提条件在当前状态中都得到满足，则该操作适用于当前状态。然后，我们利用当前状态与该操作生成后继状态，并且添加它的正效果（添加效果列表），删除它的负效果（删除效果列表）。<br> 直到20世纪90年代初期，前向规划器一直被认为是低效的，因为如果在一个状态上有多个操作适用，那么它的分枝数量将是庞大的。而这些适用的操作中，又有相当大的一部分是与达到目标无关的。而且不幸的是，启发式也无能为力，因为启发式选取的是状态，而不是操作，而在启发式对状态进行选择之前，必须得算出所有的后继状态。同时，很难设计出针对逻辑表示的好的启发式。虽然存在表示在当前状态中还有多少个目标的合取项未被满足的启发式，以及它的更精确的变体，但是它们本身的计算代价也是很大的。<br> 2.后向状态空间搜索<br> 与前向规划器相反，后向规划器（regression planner）进行的是反向规划，即由目标状态到初始状态，反向应用操作，考虑为了达到一个状态，在前一状态中什么必须为真。如果一个动作的一个正效果（添加效果）在当前子目标中，则称该操作适用于当前目标。然后，我们通过删除该操作的负效果（删除效果列表）并添加该操作的所有前提条件来计算当前状态的前驱状态，并将该前驱状态作为下一步的子目标。具体过程将在本章的第3.3节中详细介绍。后向规划器有一个明显的优点，就是它只考虑相关的操作，即只将对实现目标有作用的操作添加到搜索树中。但是，对于一个相对复杂的问题，它的分枝依然是庞大的。所以，启发式对于它的集中搜索来说，仍然是很重要的。<br> 图3.1阐释了前向状态空间和后向状态空间规划过程的区别。二者的主要区别是由以下事实导致的：可能存在多个目标状态（甚至一个目标状态就一个操作来说，可能有多个前驱状态），但只有一个初始状态。在这种情况下，正向遍历需要重复计算当前状态的后继状态；而在后向遍历中，必须计算很大数目的目标状态的前驱状态。因此，很难说哪一种方法更好。后向规划虽然实现起来比较复杂，但是当目标状态数目较多时，它允许同时考虑多个规划前缀，每个引向一个目标状态。
展开
