Some Experiments with Case-Based Search

Abstract

Abstract and multiple solutions are typically generated with an as-sessment of their respective strengths. If external feedback is provided to the system, newly solved problems can be added to the case base to strengthen it, thereby realiz-ing a form of knowledge acquisition that is qualitatively distinct from the knowledge engineering techniques tradi-tionally associated with rule-based systems. Knowedge-based problem solvers traditionally merge knowledge about a domain with more gen-eral heuristics in an effort to confront novel prob-lem situations intelligently. While domain knowl-edge 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 present-ing a CBR search algorithm as applied to the 8-puzzle, along with results from a set of exper-iments. The experiments evaluate 8-puzzle per-formance while manipulating different case-bases and case-base encoding techniques as indepen-dent 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. P