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