Accelerating Partial-Order Planners: Some Techniques for Effective Search Control and Pruning
Accelerating Partial-Order Planners: Some Techniques for Effective Search Control and Pruning
复制标题
加速偏序规划器：有效搜索控制和修剪的一些技术
DOI：
--
复制
发表时间：
1996
影响因子：
5
通讯作者：
Lenhart K. Schubert
中科院分区：
文献类型：
--
作者：
A. Gerevini;Lenhart K. Schubert
我们提出了一些领域独立的技术，使有理有据的偏序规划更接近实用。前两种技术旨在提高搜索控制，同时保持低开销成本。一种是基于对ucpop用于选择细化计划的默认A* 启发式的简单调整。另一种是基于尽可能地选择“零承诺”（强制）计划细化，否则使用LIFO优先级。一种更激进的技术是使用算子参数域来修剪搜索。这些域最初是从运算符的定义以及初始和目标条件计算的，使用多项式时间算法，该算法从初始条件开始通过运算符图传播常数集。在规划期间，参数域可用于修剪不可行的运算符实例并删除虚假的重击威胁。在实验的基础上修改的ucpop，我们改进的计划和目标选择策略的加速系数从5到1000多的各种问题，是不平凡的未修改的版本。关键是，最难的问题带来了最大的改进。基于参数域的修剪技术通常会为困难的问题提供一个数量级或更多的加速，无论是默认的ucpop搜索策略还是我们改进的策略。在线附录中提供了我们的技术和测试问题的Lisp代码。
We propose some domain-independent techniques for bringing well-founded partial-order planners closer to practicality. The first two techniques are aimed at improving search control while keeping overhead costs low. One is based on a simple adjustment to the default A* heuristic used by ucpop to select plans for refinement. The other is based on preferring "zero commitment" (forced) plan refinements whenever possible, and using LIFO prioritization otherwise. A more radical technique is the use of operator parameter domains to prune search. These domains are initially computed from the definitions of the operators and the initial and goal conditions, using a polynomial-time algorithm that propagates sets of constants through the operator graph, starting in the initial conditions. During planning, parameter domains can be used to prune nonviable operator instances and to remove spurious clobbering threats. In experiments based on modifications of ucpop, our improved plan and goal selection strategies gave speedups by factors ranging from 5 to more than 1000 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems gave the greatest improvements. The pruning technique based on parameter domains often gave speedups by an order of magnitude or more for difficult problems, both with the default ucpop search strategy and with our improved strategy. The Lisp code for our techniques and for the test problems is provided in on-line appendices.