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