Controlling search is a central concern for AI. Overcoming combinatorial search in realistic planning, design, and reasoning problems requires large doses of domain specific search control knowledge. Explanation Based Learning (EBL) has emerged as a standard technique for acquiring search control knowledge. Previous EBL work has produced impressive demonstrations but has also uncovered a fundamental problem EBL frequently constructs overlycomplex explanations that yield ineffective control knowledge. This research describes a solution: integrating EBL with partial evaluation to improve EBL's explanations. In standard EBL systems, the problem solver's behavior on a training example determines what EBL explains and how. Partial evaluation, in contrast, performs a global analysis that often yields simpler and more general explanations. In previous work, STATIC (a partial evaluator written by the PI) was pitted against PRODIGY/EBL, a state of the art EBL system. When tested in PRODIGY/EBL's benchmark problem spaces, STATIC generated search control knowledge that was up to three times a effective as PRODIGY/EBL's, and did so twenty six to seventy seven times faster. Since STATIC's analysis in not focused by training examples, however, it may flounder when confronted with large and complex problem spaces. The PI intends to design and build a hybrid system , called DYNAMIC, that will overcome the weaknesses of both approaches. DYNAMIC will identify learning opportunities a la PRODIGY/EBL, BUT GENERATE EXPLANATIONS a la STATIC. The detailed studies of the two systems suggest that DYNAMIC will significantly out perform both, and yield insights in two fundamental questions: how to improve machine generated explanations, and what is the appropriate role of training examples in explanation based learning? //
