Discovering admissible heuristics by abstracting and optimizing: a transformational approach

August 1989

Discovering admissible heuristics by abstracting and optimizing: a transformational approach

Authors:

Jack Mostow and Armand E. Prieditis

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. 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 t o 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.
@conference{Mostow-1989-122056,
author = {Jack Mostow And Armand E. Prieditis},
title = {Discovering admissible heuristics by abstracting and optimizing: a transformational approach},
booktitle = {Proceedings of 11th International Joint Conference on Artificial intelligence (IJCAI '89)},
year = {1989},
month = {August},
pages = {701 - 707},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.