ON THE RELATIONS BETWEEN INTELLIGENT BACKTRACKING AND FAILURE-DRIVEN EXPLANATION-BASED LEARNING IN CONSTRAINT SATISFACTION AND PLANNING

The ideas of intelligent backtracking (IB) and explanation-based learn ing (EBL) have developed independently in the constraint satisfaction, planning, machine learning and problem solving communities. The varie ty of approaches developed for IB and EEL in the various communities h ave hither-to been incomparable. In this paper, I formalize and unify these ideas under the task-independent framework of refinement search, which can model the search strategies used in both planning and const raint satisfaction problems (CSPs). I show that both IB and EEL depend upon the common theory of explanation analysis-which involves explain ing search failures, and regressing them to higher levels of the searc h tree. My comprehensive analysis shows that most of the differences b etween the CSP and planning approaches to EEL and TB revolve around di fferent solutions to: (a) how the failure explanations are computed; ( b) how they are contextualized (contextualization involves deciding wh ether or not to keep the flaw description and the description of the v iolated problem constraints); and (c) how the storage of explanations is managed. The differences themselves can be understood in terms of t he differences between planning and CSP problems as instantiations of refinement search. This unified understanding is expected to support a greater cross-fertilization of ideas among CSP, planning and EEL comm unities. (C) 1998 Elsevier Science B,V. All rights reserved.