Steven Bradtke, Wendy G. Lehnert
Knowedge-based problem solvers traditionally merge knowledge about a domain with more general heuristics in an effort to confront novel problem situations intelligently. While domain knowledge is usually represented in terms of a domain model, the case-based reasoning (CBR) approach to problem solving utilizes domain knowledge in the form of past problem solving experience. In this paper we show how the CBR approach to problem solving forms the basis for a class of heuristic search techniques. Given a search space and operators for moving about the space, we can use a case-base of known problem solutions to guide us through the search. In this way, the case-base operates as a type of evaluation function used to prune the space and facilitate search. We will illustrate these ideas by presenting a CBR search algorithm as applied to the 8-puzzle, along with results from a set of experiments. The experiments evaluate 8-puzzle performance while manipulating different case-bases and case-base encoding techniques as independent variables. Our results indicate that there are general principles operating here which may be of use in a variety of applications where the domain model is weak but experience is strong.