Abstract
Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not extend trivially to Generalized Planning (GP). GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in the number of objects, the number of state variables, their domain size, or their initial and goal configuration. The generalization requirements of GP make it impractical to perform the state-space search that is usually implemented by heuristic planners. This paper adapts the planning as heuristic search paradigm to the generalization requirements of GP, and presents the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines a set of evaluation and heuristic functions for guiding a combinatorial search in our new GP solution space. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g.~integers. Lastly, the paper defines an upgraded version of our novel algorithm for GP called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space, and that is guided by our evaluation/heuristic functions for GP.
Abstract (translated)
规划作为启发搜索是古典规划中最成功的一种方法,但不幸的是,它并不直接延伸到通用规划(GP)。GP的目标是计算适用于给定域中的一组经典规划实例的算法解决方案,即使这些实例在数量对象、状态变量的数量、域大小或初始和目标配置方面有所不同。GP的泛化要求使其无法通常由启发规划师执行的状态空间搜索。本文将GP的泛化要求适应为GP的启发搜索范式,并提出了GP的本地启发搜索方法。首先,本文介绍了一种新的指针方案空间,它是GP问题中经典规划实例的数量和实例大小独立的,即对象、状态变量和域大小的数量。其次,本文定义了一套评价和启发函数,以指导我们新的GP解决方案空间中的组合搜索。这些评价和启发函数的计算不需要预先建立状态或行动基础。因此,我们的GP作为启发搜索方法可以处理大型集合具有大型数值域的状态变量,例如~整数。最后,本文定义了GP的新型算法版本,称为最佳先决通用规划(BFGP),它在我们指针方案空间中实施最佳先决搜索,并受GP的评价/启发函数指导。
URL
https://arxiv.org/abs/2301.11087
