Foundations of Assumption-based Truth Maintenance Systems: Preliminary Report

Raymond Reiter, Johan de KleerAAAI 1987

Introduction

Published in the 1987 AAAI proceedings, this seminal work by Raymond Reiter and Johan de Kleer provides the rigorous mathematical scaffolding for the Assumption-based Truth Maintenance System (ATMS). By formalizing the "Clause Management System" (CMS), the authors moved truth maintenance from an algorithmic "black box" to a well-defined problem in propositional logic, linking it to the classical theory of prime implicants.

The Clause Management System (CMS)

The paper's primary contribution is the introduction of the CMS, a domain-independent framework that separates reasoning from logical bookkeeping. In this architecture, a problem-solver is split into two distinct components:

  1. The Reasoner: A domain-dependent module that discovers facts and passes them to the CMS as propositional clauses.
  2. The CMS: A domain-independent system that records these clauses and answers queries regarding "minimal supports" for specific facts.
The interaction between the Reasoner and the Clause Management System (CMS).

This separation allows the CMS to act as an "intelligent cache." By recording why certain combinations of assumptions lead to contradictions (known as "nogoods"), the CMS enables the Reasoner to prune massive branches of a search tree before performing expensive domain-specific computations.

Logical Foundations: Prime Implicant Theory

Reiter and de Kleer bridge the gap between truth maintenance and Boolean logic by utilizing Prime Implicant Theory. A prime implicant is a minimal conjunction of literals that implies a formula. The authors prove that finding the "simplest explanation" (minimal support) for a fact is mathematically equivalent to finding the prime implicants of the set of clauses provided by the Reasoner.

This connection allowed the field to leverage decades of research in digital circuit design, specifically two-level Boolean minimization. The paper formalizes abductive reasoning—reasoning from effects to causes—by defining support as the smallest set of assumptions $S$ such that $S \implies g$.

Search Efficiency and Results

The authors demonstrate the practical utility of the CMS through search optimization. By using a CMS-guided search rather than standard chronological backtracking, the number of "expensive" function evaluations in a sample problem was reduced from 14 to 6.

An AND/OR search tree illustrating branching logic and potential pruning points.

A key result, Theorem 5, formally proves that the set of all minimal support clauses for a query is exactly the set of prime implicants satisfying specific subset conditions. Furthermore, the authors show that de Kleer’s original ATMS is a restricted version of the CMS, limited to Horn clauses and unit queries.

Limitations and Complexity

Despite its theoretical elegance, the CMS faces significant computational challenges. The problem of finding prime implicants is NP-hard, and in the worst case, the number of prime implicants can grow exponentially, leading to a "space explosion." Additionally, the framework is strictly propositional; while a Reasoner might use predicate calculus, the CMS treats those formulas as atomic symbols, potentially losing granularity.

As a preliminary report, the paper concludes by highlighting the need for more efficient algorithms to update the "compiled" database of prime implicants as new clauses are added.

Summary updated

BibTeX
@inproceedings{reiter1987foundations,
  author = {Raymond Reiter and Johan de Kleer},
  title = {{Foundations of Assumption-based Truth Maintenance Systems: Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure