Quantitatively relating abstractness to the accuracy of admissible heuristics

摘要

Admissible (lower-bound) heuristics are worth discovering because they have desirable properties in various search algorithms. One well-known source of admissible heuristics is from abstractions of a problem. Using standard definitions of heuristic accuracy and abstractness, we prove that heuristic accuracy decreases inversely with abstractness. This is the first quantitative result linking abstractness to the heuristic accuracy. Using this result, it may be possible to predict the accuracy of an abstraction-derived heuristic without testing it on a sample set of problems. It may also be possible for a heuristic discovery system to use the theory to predict the accuracy of a heuristic, thereby better focusing its search.