Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
复制标题
不运行任何搜索即可分析搜索拓扑：论因果图与 h 之间的联系
DOI：
--
复制
发表时间：
2011
影响因子：
5
通讯作者：
J. Hoffmann
中科院分区：
文献类型：
--
作者：
J. Hoffmann
忽略删除列表松弛对于满意规划和最优规划都是至关重要的。在早期的工作中，人们观察到，最佳松弛启发式h+在许多经典的规划基准中具有惊人的品质，特别是与完全不存在局部极小值有关。证明这是手工制作的，提出了这样的证明是否可以自动域分析技术的问题。与早期令人失望的结果相反-分析方法具有指数运行时间，并且仅在两个非常简单的基准领域中成功-我们在此以肯定的方式回答这个问题。我们建立因果图结构和h+拓扑之间的联系。这导致了低阶多项式时间分析方法，在我们称为TorchLight的工具中实现。在已经证明不存在局部最小值的12个域中，TorchLight在8个域中给出了强有力的成功保证。从经验上讲，它的分析表现出强大的性能，在进一步的2个这些领域，再加上4个领域，局部极小值可能存在，但很少。通过这种方式，TorchLight可以区分“容易”域和“困难”域。通过总结分析失败的结构原因，TorchLight还提供诊断输出，指示可能导致局部最小值的域方面。
The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results - the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains - we herein answer this question in the afirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish "easy" domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.