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.//