Domain-independent planning is a notoriously hard search problem. Several systematic search techniques have been proposed in the context of various formalisms. However, despite their theoretical completeness, in practice these algorithms are incomplete because for many problems the search space is too large to be (even partially) explored. In this paper we propose a new search method in the context of Blum and Furst's planning graph approach, which is based on local search. Local search techniques are incomplete, but in practice they can efficiently solve problems that are unsolvable for current systematic search methods. We introduce three heuristics to guide the local search (Walkplan, Tabuplan and T-Walkplan), and we propose two methods for combining local and systematic search. Our techniques are implemented in a system called GPG, which can be used for both plan-generation and plan-adaptation tasks. Experimental results show that GPG can efficiently solve problems that are very hard for current planners based on planning graphs.
展开▼
机译：与领域无关的计划是一个非常困难的搜索问题。在各种形式主义的背景下，已经提出了几种系统的搜索技术。但是，尽管它们具有理论上的完整性，但在实践中这些算法还是不完整的，因为对于许多问题，搜索空间太大而无法（甚至部分地）探索。在本文中，我们在Blum and Furst的规划图方法的背景下提出了一种基于局部搜索的新搜索方法。本地搜索技术是不完整的，但实际上，它们可以有效解决当前系统搜索方法无法解决的问题。我们介绍了三种启发式方法来指导本地搜索（Walkplan，Tabuplan和T-Walkplan），并提出了两种结合本地搜索和系统搜索的方法。我们的技术在称为GPG的系统中实施，该系统可用于计划生成和计划调整任务。实验结果表明，GPG可以有效地解决基于规划图的当前规划者很难解决的问题。
展开▼
