Generating Effective Admissible Heuristics by Abstraction and Reconstitution

Abstract

Admissible heuristics are worth discovering because they have desirable properties in various search algorithms. Unfortunately, effective ones--ones that are accurate and efficiently computable--are difficult for humans to discover. One source of admissible heuristics is from abstractions of a problem: the length of a shortest path solution to an abstracted problem is an admissible heuristic for the original problem because the abstraction has certain details removed. However, often too many details have to be abstracted to yield an efficiently computable heuristic, resulting in inaccurate heuristics. This paper describes a method to reconstitute the abstracted details back into the solution to the abstracted problem, thereby boosting accuracy while maintaining admissibility. Our empirical results of applying this paradigm to project scheduling suggest that reconstitution can make a good admissible heuristic even better.