Discovering Effective Admissible Heuristics by Abstraction: Developing a Quantitative Theory Relating Abstractness to Effectiveness

可容许概率是概率值的一个重要类别 发现：它们保证搜索中的最短路径解决方案 算法，如A*，它们保证更便宜 产生解路径有界增长的解 搜索算法中的长度，如动态加权。 几 研究人员已经描述了可接受的诊断是如何 从给定问题的抽象版本生成，从 某些细节被删除了 这项工作旨在 发展一种定量理论，将抽象性与 有效性所产生的经济学和他们的经验 验证这个理论。 这样的理论将使我们能够预测 通过使用，可以预期降低多少复杂性 抽象派生的语法学。 最终，这一理论将 更好地了解如何有效地受理 可以自动发现代理。//

Admissible heuristics are an important class of heuristics worth discovering: They guarantee shortest path solutions in search algorithms such as A* and they guarantee less expensively produced solutions with a bounded increase in solution path length in search algorithms such as dynamic weighing. Several researchers have described how admissible heuristics can be generated from abstracted versions of a given problem, ones from which certain details have been removed. This work aims to develop a quantitative theory that relates abstractness to the effectiveness of the resulting heuristics and them empirically validate that theory. Such a theory will enable us to predict how much complexity reduction can be expected from using abstraction-derived heuristics. Ultimately, this theory will result in a better understanding of how effective admissible heuristics can be automatically discovered.//