规划方法分析

11.6 规划方法分析

规划是当前人工智能中一个引起巨大兴趣的领域。一个原因是规划结合了我们迄今为止已经讨论过的 AI 的两个主要领域：搜索和逻辑。也就是，规划器既能被视为搜索解的程序，也能被视为（构造性地）证明解存在的程序。这两个领域的思想杂交致使过去10年中性能提高了好几个数量级，并且增加了规划器在工业应用中的使用。不幸的是，我们还没有了解得很清楚，哪些技术在哪类问题上能够最好地工作。很有可能的是，新的技术将会出现，并且超越已有的方法。

规划是最先经历控制组合爆炸的。如果域内有p个原始命题，那么就有2p个状态。对于复杂的域， p可以变得相当大。考虑域内的对象具有属性（Location, Color，等等）和关系（At, On, Between等）。如果域内有d个对象具有三元关系，则有个状态。我们也许可以得出这样的结论：在最坏情况下，规划是毫无希望的。

相对于这种悲观主义，分治方法是一种强有力的武器。在最佳情况下——问题完全可分解——分治策略提供指数级的加速。然而，可分解性被行动之间的负相互作用所破坏。偏序规划器用因果连接——一种强大的表示方法——来处理这种情况，但是不幸的是每个冲突必须用一个选择（将冲突行动放在连接之前还是之后）来解决，而这样的选择会指数级增长。GRAPHPLAN在图的构造阶段避免了这些选择，这是通过运用记录冲突的互斥连接来实现的，并不真正做出一个选择来解决它们。SATPLAN表示了与互斥关系类似的范围，不过它是利用通用的CNF形式而不是特定的数据结构来完成这个的。工作的性能依赖于所用的SAT求解器。

有时候通过识别那些可以排除的负相互作用而有效地求解问题是可能的。如果一个问题中的子目标存在一个顺序，以致规划器能够按这个顺序获得它们，而不需要撤消任何先前获得的子目标，那么我们说该问题具有可串行化子目标。例如，在积木世界中，如果目标是要建造一个塔（例如，A 在 B上，B在C上，C在Table（桌子）上），那么子目标是可以自底向上地可串行化的：如果我们首先得到C在Table上这个子目标，在获得别的子目标时，我们将永远不必撤消它。使用自底向上技巧的规划器在积木世界域内可以不需要回溯就能求解任何问题（虽然它并不总能找到最短规划）。

作为一个更复杂的例子，对于指挥NASA的深空一号宇宙飞船的远程智能体规划器，已经确定的是涉及指挥航空器的命题可串行化。这可能并不令人感到惊奇，因为工程师设计的航天器要尽可能地容易控制（服从其它约束）。利用目标的串行化排序，远程智能体规划器能够消除大部分搜索。这意味着它能足够快地实时控制航天器，这是在以前被认为是不可能的。

有不止一种方法能够控制组合爆炸。我们在第五章中看到约束满足问题（CSP）中，有许多控制回溯的技术，诸如由依赖关系所指导的回溯技术。所有这些技术都能用于规划。例如，从规划图中抽取一个解的过程可以被形式化描述为一个布尔CSP，这个布尔CSP的变量说明了给定行动是否应该在给定时间发生。CSP可以用第五章中的任何算法求解，诸如最小冲突。BLACKBOX系统中使用的与CSP技术关系密切的方法是将规划图转化为CNF表达式，然后用SAT求解器抽取一个规划。这个方法看起来比 SATPLAN 要更可行，大概是因为规划图已经消除了问题的许多不可能的状态和行动。它也比GRAPHPLAN要好，大概是因为诸如WALKSAT的可满足性搜索比GRAPHPLAN使用的严格回溯搜索具有强得多的灵活性。

勿庸置疑，诸如GRAPHPLAN，SATPLAN和BLACKBOX这样的规划器，通过提升规划系统性能水准和澄清涉及的表示和组合问题，已经使规划领域向前推进。然而，这些方法本质上是命题的，因此限制了它们能够表示的领域。（例如，具有数十个物体和地点的后勤学问题，对应的CNF表达式可能需要上千兆字节的存储量。）如果要产生进一步的进展，那么一阶表示和算法是必需的，尽管像规划图这样的结构作为启发式的来源仍然是有用的。