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:
- The Reasoner: A domain-dependent module that discovers facts and passes them to the CMS as propositional clauses.
- The CMS: A domain-independent system that records these clauses and answers queries regarding "minimal supports" for specific facts.
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.
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