前向状态空间搜索

前向状态空间搜索规划与第三章中的问题求解方法相似。有时也被称为前进（progression）规划，因为它沿向前的方向移动。我们从问题的初始状态出发，考虑行动序列，直到我们找到一个得到目标状态的序列。把规划问题形式化为状态空间搜索问题如下：

• 搜索的初始状态来自规划问题的初始状态。通常，每个状态会有一个正的基文字的集合；没有出现的文字为假。

• 可用于一个状态的行动是那些前提都得到满足的。行动产生的后继状态通过增加正效果文字和删除负效果文字生成。（在一阶情况下，我们必须应用从前提到效果文字的合一者）。注意一个单一的后继函数对所有规划问题都可行——使用明确的行动表示的结果。

• 检验状态是否满足规划问题的目标。

• 单步耗散通常是1。虽然允许不同的行动具有不同的耗散是很容易的，但是STRIPS规划器很少这么做。

回顾一下，不出现函数符号的情况下，规划问题的状态空间是有限的。因此，任何完备的图搜索算法——例如，A*——都将是一个完备的规划算法。

从规划搜索的初期（约1961年）直到最近（约1998年），人们认为前向状态空间搜索太低效而不能实际应用。这也不难找到原因——只要查阅一下第11.1节的开头部分。首先，前向搜索不能解决无关行动问题——所有可用行动都是从各个状态出发考虑的。其次，如果没有一个好的启发式的话，该方法会迅速陷入困境。考虑一个有10个机场，每个机场有5架飞机和20件货物的航空货物问题。目标是将所有的货物从机场A运送到机场B。这个问题有一个简单的解：将20件货物装载到机场A的一架飞机上，飞机飞到机场 B，卸载所有货物。但是找到解可能是困难的，因为平均分支因子是巨大的：50架飞机中的任何一架可以飞到9个其它的机场，200件包裹中的每一件也能一样被卸载（如果已经装载了）或者装载到机场的任何一架飞机上（如果还没装载）。平均而言，我们说存在大约 1000个可能的行动，所以达到明显解的深度的搜索树大约有100041个节点。显然需要一个非常精确的启发式，才能使这类的搜索变得有效率。在考察后向搜索之后，我们将讨论一些可能的启发式。