Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational Approach

Abstract

We present an implemented model for discovering a class of state-space search heuristics. First, ab&traction& of a state-space problem are generated by dropping information from the problem definition. An optimal solution path for any such 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. Moreover, 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 used 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. ABSOLVER appears to be the first mechanical generator of heuristics guaranteed to find optimal solution paths. We have used it to derive known and novel heuristics for various state space problems, including Rubik's Cube.