An Approach to Dependency Directed Backtracking Using Domain Specific Knowledge

Abstract

The idea of dependency directed backtracking proposed by Stallman and Sussman (1977)\noffers significant advantages over heuristic starch schemes with chronological\nbacktracking which waste much effort by discarding many "good" choices when\nbacktracking situations arise. However, we have found that existing non-chronological\nbacktracking machinery is not suitable for certain types of problems, namely, those\nwhere choices do not follow logically from previous choices, but are based on a heuristic\nevaluation of a constrained set of alternatives. This is because a choice is not justified by\na âset of supportâ (of previous choices), but because its advantages outweigh its\ndrawbacks in comparison to its competitors. What is needed for these types of problems\nis a scheme where the advantages and disadvantages of choices are explicitly recorded\nduring problem solving. Then, if an unacceptable situation arises, information about the\nnature of the unacceptability and the tradeoffs can be used to determine the most\nappropriate backtracking point. Further, this requires the problem solver to use its\nhindsight to preserve those "good" intervening choices that were made chronologically\nafter the "bad" choice, and to resume its subsequent reasoning in fight of the modified\nset of constraints. In this paper, we describe a problem solver for non-chronological\nbacktracking in situations involving tradeoffs. By endowing the backtracker with access\nto domain-specific knowledge, a highly contextual approach to reasoning in dependency\ndirected backtracking situations can be achieved.