Discovering Admissible Search Heuristics by Abstracting and Optimizing

Abstract

We present an implemented model for discovering a class of state-space search heuristics. First, abstractions of a state-space problem are generated by dropping information from the problem definition. Each resulting abstracted problem gives a lower bound on the true distance to the goal. This bound can be used as an admissible evaluation function for guiding the base-level search. If the abstracted goal is unreachable from an abstracted state, the original state can safely be pruned. However, using exhaustive search to evaluate the abstracted problem is generally too slow. Therefore, optimization is needed to speed up the computation of the lower bound (or solvability test), for example by factoring the abstracted problem into independent subproblems. We analyze the conditions under which the resulting heuristic is faster than brute force search. Our implementation, named ABSOLVER, has several general transformations for abstracting and simplifying state-space problems, including a novel method for problem factoring. We tested their generality by using them to derive known and novel heuristics for various state space problems. ABSOLVER appears to be the first mechanical generator of heuristics guaranteed to find optimal solution paths.