Learning While Searching in Constraint-Satisfaction-Problems

Abstract

The popular use of backtracking as a control strategy for theorem proving in PROLOG and in Truth-Maintenance-Systems (TMS) led to increased interest in various schemes for enhancing the efficiency of backtrack search. Researchers have referred to these enhancement schemes by the names ‘ ‘Intelligent Backtracking ’ ’ (in PROLOG), ‘ ‘Dependency-directed-backtracking ” (in TMS) and others. Those improve-ments center on the issue of “jumping-back ” to the source of the problem in front of dead-end situations. This paper examines another issue (much less explored) which arises in dead-ends. Specifically, we concen-trate on the idea of constraint recording, namely, analyzing and storing the reasons for the dead-ends, and using them to guide future decisions, so that the same conflicts will not arise again. We view constraint recording as a process of learning, and examine several possible learning schemes studying the tradeoffs between the amount of learning and the improve-ment in search efficiency. I.