Focusing the ATMS

Kenneth D. Forbus, Johan de KleerAAAI 1988

Introduction

In the late 1980s, the Assumption-based Truth Maintenance System (ATMS) emerged as a powerful architecture for AI, enabling programs to maintain multiple, often conflicting, "contexts" or sets of beliefs simultaneously. However, standard ATMS implementations suffered from an "eagerness" problem. In infinite domains—such as natural deduction in logic or complex engineering design—the system would execute every possible consistent inference, leading to a combinatorial explosion. This paper introduces the "implied-by" strategy to give inference engines tight control over ATMS activity, ensuring the system only performs work relevant to the current task.

The Implied-By Strategy

The authors propose a novel approach implemented in the ATMoSphere language. This strategy shifts control from the ATMS back to the inference engine through three primary mechanisms:

  1. Focus Environments: The inference engine explicitly designates a "center of attention"—a specific set of assumptions defining the current task.
  2. Implied-by Consumers: Unlike standard "IN" consumers that fire if a premise is merely consistent with a context, implied-by consumers only trigger if their requirements are logically implied by the current focus environment. This stricter requirement prevents the system from wandering into irrelevant branches of a search tree.
  3. Contradiction Consumers: These act as logical interrupts. If a focus environment becomes inconsistent (a "nogood"), the ATMS immediately signals the engine to pivot, preventing wasted cycles on dead-end branches.

By requiring logical implication by the focus environment, the ATMS avoids exploring branches that, while consistent, do not contribute to the current line of reasoning. This effectively turns the ATMS from an eager, autonomous inference generator into a high-performance tool that strictly respects the boundaries set by the inference engine.

Experimental Evaluation

The strategy was evaluated using two classic AI benchmarks:

  • Natural Deduction: A set of six logic problems from introductory textbooks, representing "infinite" domains where formulas can grow in size and number without bound.
  • Cryptarithmetic: The classic "SEND + MORE = MONEY" puzzle, where letters must be mapped to unique digits to satisfy an addition equation.

To test "distraction" resistance, the authors created a modified version of the logic problems where they injected a large amount of irrelevant premise data.

Results and Discussion

Efficiency and Resistance to Distraction

The results from the natural deduction benchmarks highlight the difference between consistency-based and implication-based triggers. In clean environments, the implied-by strategy already shows efficiency gains, executing fewer rules than the standard "INTERN" strategy (e.g., 54 rules vs. 64 in Example 2).

However, the strategy's most striking advantage is its immunity to noise. When irrelevant data was added to the logic problems, the rule counts for standard "IN" and "INTERN" strategies jumped significantly, sometimes tripling. In contrast, the implied-by strategy's rule count remained identical to the baseline, as the irrelevant data was never implied by the focus environment.

Rule execution counts with irrelevant data injected, demonstrating the focus of the implied-by strategy.

Outperforming ADDB

In the Cryptarithmetic puzzle, the implied-by strategy outperformed Dependency-Directed Backtracking (ADDB). By only creating assumptions as they became relevant to the search, it required significantly fewer assumptions and rule executions compared to both standard consumers and the ADDB strategy.

Comparison of assumptions and rules for the Cryptarithmetic puzzle.

Conclusion

The implied-by strategy effectively focuses the ATMS, preventing it from being distracted by irrelevant data or infinite search paths. While global label updating remains a potential overhead, the strategy represents a significant step toward making truth maintenance systems practical for large-scale, complex reasoning tasks. Future work includes exploring multiple foci for parallel processing and further optimizing bookkeeping costs to balance global updates with local focus requirements.

Summary updated

BibTeX
@inproceedings{forbus1988focusing,
  author = {Kenneth D. Forbus and Johan de Kleer},
  title = {{Focusing the ATMS}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure