Planning as heuristic search
Planning as heuristic search
复制标题
DOI：
10.1016/s0004-3702(01)00108-4
复制
发表时间：
2001-06-01
影响因子：
14.4
通讯作者：
Geffner, H
中科院分区：
文献类型：
--
作者：
Bonet, B;Geffner, H
在 AIPS98 规划竞赛中，HSP 规划器表明启发式搜索规划器可以与最先进的 Graphplan 和 SAT 规划器竞争。像 HSP 这样的启发式搜索规划器通过自动从 Strips 编码中提取启发式，将规划问题转化为启发式搜索问题。它们与专门的问题解决器（例如为 24-Puzzle 和 Rubik's Cube 开发的问题解决器）不同，因为它们使用通用的声明性语言来陈述问题，并使用通用的机制从这些表示中提取启发式。在本文中，我们研究了一系列启发式搜索规划器，它们基于简单且通用的启发式，假设动作先决条件是独立的。然后，在最佳优先和爬山搜索算法的背景下使用启发式算法，并在大量领域中进行测试。然后，我们考虑变化和扩展，例如反转搜索方向以加速节点评估，以及提取有关命题不变量的信息以避免死胡同。我们分析最终的规划者，评估他们的表现，并解释他们何时做得最好。我们还将这些规划器的性能与两个最先进的规划器进行了比较，并表明基于纯粹的最佳优先搜索的最简单的规划器在大量问题上产生了最可靠的性能。我们还讨论了这种方法的优点和局限性，建立启发式搜索规划和 Graphplan 之间的对应关系，并简要调查了可以缩小通用启发式搜索规划器和专用求解器之间当前性能差距的最新想法。 (C) 2001 Elsevier Science B.V. 保留所有权利。
In the AIPS98 Planning Contest, the HSP planner showed that heuristic search planners can be competitive with state-of-the-art Graphplan and SAT planners. Heuristic search planners like HSP transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24-Puzzle and Rubik's Cube in that they use a general declarative language for stating problems and a general mechanism for extracting heuristics from these representations.In this paper, we study a family of heuristic search planners that are based on a simple and general heuristic that assumes that action preconditions are independent. The heuristic is then used in the context of best-first and hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers. (C) 2001 Elsevier Science B.V. All rights reserved.