Incremental acquisition of search knowledge

The development of highly effective heuristics for search problems is a difficult and time-consuming task. We present a knowledge acquisition approach to incrementally model expert search processes. Though, experts do not normally have complete introspective access to that knowledge, their explanations of actual search considerations seem very valuable in constructing a knowledge-level model of their search processes. Furthermore, for the basis of our knowledge acquisition approach, we substantially extend the work done on Ripple-down rules which allows knowledge acquisition and maintenance without analysis or a knowledge engineer. This extension allows the expert to enter his domain terms during the KA process; thus the expert provides a knowledge-level model of his search process. We call this framework nested ripple-down rules. Our approach targets the implicit representation of the less clearly definable quality criteria by allowing the expert to limit his input to the system to explanations of the steps in the expert search process. These explanations are expressed in our search knowledge interactive language. These explanations are used to construct a knowledge base representing search control knowledge. We are acquiring the knowledge in the context of its use, which substantially supports the knowledge acquisition process. Thus, in this paper, we will show that it is possible to build effective search heuristics efficiently at the knowledge level. We will discuss how our system SmS1.3 (SmS for Smart Searcher) operates at the knowledge level as originally described by Newell. We complement our discussion by employing SmS for the acquisition of expert chess knowledge for performing a highly pruned tree search. These experimental results in the chess domain are evidence for the practicality of our approach. (C) 2000 Academic Press.