AN APPROACH TO DEPENDENCY DIRECTED BACKTRACKING USING DOMAIN SPECIFIC KNOWLEDGE

Abstract

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