Choices Without Backtracking

Johan de KleerAAAI 1984

Abstract

In traditional AI problem-solving, backtracking serves as a significant computational bottleneck, forcing systems to erase and re-derive logical states when encountering contradictions. This paper discusses the Assumption-based Truth Maintenance System (ATMS), a framework that eliminates backtracking by labeling every inference with the specific assumptions required for its validity. By allowing the simultaneous exploration of multiple contradictory hypotheses, the ATMS transforms truth maintenance from a process of state-switching into a persistent database of context-dependent facts.

1. Introduction: The Backtracking Bottleneck

In the early 1980s, AI problem solvers—particularly those designed for qualitative reasoning and circuit analysis—faced a fundamental efficiency wall. When a program encountered a choice between multiple plausible alternatives, it typically employed a Truth Maintenance System (TMS) to track current assertions. However, traditional TMS designs, such as Doyle’s justification-based system, were inherently limited by the "Single-State Problem." They could only represent one consistent "world" at a time. To compare two different solutions, the system had to backtrack, erase its current state, and rebuild the alternative state from scratch.

This approach was inefficient for two reasons: first, it wasted time re-deriving the same inferences every time the search returned to a previous branch; second, it suffered from an "overzealous" contradiction problem, where the discovery of a contradiction forced an immediate stop, preventing the system from using that contradiction to localize faults.

2. The Assumption-Based Paradigm

Johan de Kleer proposed a shift from justification-based systems to assumption-based systems. In an ATMS, the binary state of an assertion (being either "IN" or "OUT") is replaced by a label. This label consists of a set of assumptions—primitive choices—under which the assertion is valid.

For example, rather than simply asserting a value for a variable, the ATMS stores the value alongside its dependency: <y = -1, {A, B}>. This indicates that y = -1 is true if and only if assumptions A and B are both held. This labeling mechanism allows the database to store contradictory information simultaneously (e.g., x=1 under {A} and x=0 under {B}) without logical collapse. The system treats these as belonging to different "contexts" rather than a single conflicting state.

3. Mechanisms of Efficiency

3.1 Simultaneous Exploration and Contexts

A "context" in the ATMS is defined simply as a subset of the database characterized by a specific set of assumptions. Because assertions are tied to these sets, the system never has to "undo" work. It simply shifts its focus to a different set of assumptions. All previous inferences remain in the database, ready to be reused if their underlying assumptions are ever met again.

3.2 Nogoods and Contradiction Handling

When the system discovers that a specific combination of assumptions leads to a contradiction, that set is designated as a nogood. The ATMS then automatically ignores any future potential inference that depends on a superset of a nogood. This allows the system to prune the search space effectively without the need for chronological backtracking.

3.3 The Internal Frame Problem

De Kleer identifies backtracking as an internal manifestation of the classic AI "frame problem"—the difficulty of determining what remains true when a single choice changes. By making dependencies explicit and persistent through labels, the ATMS sidesteps this issue. It operates on the principle that memory is cheaper than computation; by storing every inference and its "pedigree," the system ensures that no logical work is performed twice.

4. Applications and Results

The ATMS was validated through integration into several state-of-the-art systems of the era, including:

  • LOCAL: A program for troubleshooting electronic circuits within the SOPHIE III framework.
  • QUAL / ENVISION: Systems designed for qualitative reasoning about physical device behavior.

Performance benchmarks on Symbolics Lisp machines (L-M-2 and 3600) demonstrated that the time spent handling assumptions, which previously dominated runtimes, became negligible. Furthermore, the ATMS avoided the memory exhaustion issues common in older backtracking algorithms, proving that assumption-based reasoning could handle the ambiguity inherent in qualitative physics.

5. Limitations and Conclusion

Despite its advantages, the ATMS introduces its own complexities. The process of "interpretation construction"—finding the maximal sets of consistent assumptions that describe a complete global state—remains a potentially NP-hard task performed at the end of the inference process. Additionally, the system assumes logical independence among rules; redundant rules can lead to incoherent derivations that require extra filtering.

Nevertheless, the ATMS represents a landmark shift in symbolic AI. By treating context as a first-class citizen and replacing backtracking with persistent, labeled justifications, it provided a robust foundation for complex reasoning tasks that require the simultaneous consideration of multiple competing hypotheses.

Summary updated

BibTeX
@inproceedings{kleer1984choices,
  author = {Johan de Kleer},
  title = {{Choices Without Backtracking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure