An Efficient First-Order Horn-Clause Abduction System Based on the ATMS

Hwee Tou Ng, Raymond J. MooneyAAAI 1991 · OpenReview

Introduction

Abduction, defined as the "inference to the best explanation," is a cornerstone of automated reasoning in fields such as diagnosis, plan recognition, and natural language processing. Formally, given a domain theory ($T$) and observations ($O$), the goal is to find a minimal set of assumptions ($A$) such that $A \cup T \models O$.

Despite its utility, abduction is computationally expensive. Traditional systems often struggle with two main issues: the "factoring" problem in first-order logic (unifying distinct assumptions to create coherent explanations) and massive redundancy in search. This paper introduces the AAA (ATMS-based Abduction Algorithm), a system that successfully integrates first-order Horn-clause logic with an Assumption-based Truth Maintenance System (ATMS) to overcome these hurdles.

Methodology

The AAA algorithm and its heuristic variant, AAA/H, employ several key strategies to manage complexity:

  • ATMS-based Caching: By adopting the "consumer architecture" of an ATMS, AAA caches justifications for sub-goals. When the system encounters a previously solved sub-goal in a different branch of the search tree, it reuses the cached result instead of re-computing it.
  • First-Order Factoring: The system allows the ATMS to handle the unification of assumptions. It identifies pairs of assumptions within an environment that can be unified, creating new, simplified environments that lead to more elegant explanations.
  • Heuristic Beam Search (AAA/H): Since finding all minimal explanations is NP-complete, AAA/H uses a beam search to focus on the most promising candidates. Explanations are ranked using a simplicity metric ($E/A$, where $E$ is the number of explained atoms and $A$ is the number of assumptions), keeping only the top $N$ explanations at each step.

Evaluation and Results

The researchers evaluated AAA/H against a non-ATMS baseline (Stickel’s SAA/H) using a substantial knowledge base (46 KB of facts and 163 KB of rules). The test suite covered diverse domains, including animal coloration narratives, UNIX plan recognition, and logic circuit diagnosis.

Performance comparison between SAA/H (S/H) and AAA/H (A/H) across various problem domains.

As shown in the table above, AAA/H demonstrated significant performance improvements:

  • Speedup: AAA/H was consistently at least an order of magnitude faster than the baseline. The mean speedup ratio across all tasks was 17.55x, reaching nearly 40x in the complex "full adder" circuit diagnosis problem.
  • Reduced Redundancy: The number of justifications (a proxy for rule invocations) was significantly lower in AAA/H, with a mean reduction ratio of 3.38x. This confirms that the performance gains are primarily due to the ATMS's ability to eliminate redundant computational work.

Key Insights and Discussion

The primary advantage of AAA lies in its ability to "remember" partial proofs. In complex domain theories where the same sub-problems recur frequently, caching results in the ATMS prevents the system from re-traversing the same search space. Furthermore, the system's ability to perform factoring within the ATMS framework allows it to find more coherent first-order explanations than propositional systems.

While highly effective, the authors acknowledge certain limitations. AAA is technically "incomplete" in specific scenarios involving variable instantiation in goal clauses. Additionally, consistency checking is performed via a depth-limited forward-chaining heuristic, which is necessary for decidability but may occasionally accept inconsistent explanations. Future work will focus on achieving full completeness and establishing a formal proof of equivalence between AAA and traditional methods.

Conclusion

The AAA system represents a major milestone in automated reasoning, proving that an ATMS can be made practical for large-scale heuristic search. By effectively combining first-order logic with efficient truth maintenance, it offers a scalable solution for complex abductive tasks.

Summary updated

BibTeX
@inproceedings{ng1991efficient,
  author = {Hwee Tou Ng and Raymond J. Mooney},
  title = {{An Efficient First-Order Horn-Clause Abduction System Based on the ATMS}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
  url = {https://openreview.net/forum?id=JB0I2OMfs3u},
}
Figure