CATMS: An ATMS Which Avoids Label Explosions

John W. Collins, Dennis DeCosteAAAI 1991

Introduction

Assumption-based Truth Maintenance Systems (ATMS) are fundamental to automated reasoning, allowing systems to explore multiple contexts or scenarios simultaneously. By maintaining "labels"—minimal sets of assumptions required for a fact to be true—an ATMS enables a problem solver to navigate complex logical dependencies efficiently. However, traditional ATMS implementations suffer from a critical bottleneck known as "label explosion." As problem complexity increases, the exponential growth of assumption combinations leads to massive cross-product operations that can overwhelm computational resources. This paper introduces CATMS (Compressed ATMS), a system designed to mitigate label explosion through compression techniques and assumption closures.

The CATMS Architecture

CATMS addresses the inefficiencies of standard ATMS by modifying how subsumption and label propagation are handled. The system introduces several key innovations:

Assumption Closures and Label Compression

Unlike standard systems that track raw assumptions, CATMS utilizes "assumption closures"—the set of all assumptions logically implied within a given context. This allows the system to treat assumption nodes as barriers. Instead of propagating complex labels forward indefinitely, CATMS "compresses" these labels into a single assumption at strategic points, preventing the exponential growth of label sets.

Auto-Assuming and Lazy Updating

A novel "auto-assuming" mechanism serves as a safety valve. When CATMS detects that a label is likely to explode during computation, it can automatically convert a regular node into an "auto-assumption." This resets the label size to one, maintaining tractability. To further optimize performance, CATMS employs "lazy updating," deferring the expansion of closures and consistency checks until a specific query is made or essential propagation is required. This hybrid approach balances the benefits of pre-calculated "compiled" reasoning with on-the-fly "interpreted" logic.

Experimental Evaluation

The efficacy of CATMS was evaluated using the Qualitative Process Engine (QPE), a framework for qualitative physics. Two primary scenarios were tested:

  1. Two Containers: A standard liquid flow problem.
  2. Mechanical Linkage: A complex domain involving physical part movement, which previously served as a benchmark for triggering label explosions.

Results and Analysis

The experimental results demonstrate significant performance improvements, particularly in the more complex Mechanical Linkage domain.

Performance comparison of CATMS vs. ATMS in QPE examples.

As shown in the table above, CATMS dramatically reduced the computational overhead for the Mechanical Linkage task. The number of unique environments tracked by the system dropped from 4,270 in the standard ATMS to just 810 in CATMS. Furthermore, the average label size was reduced from 9.91 to 1.46. These efficiencies translated into a nearly 2x speedup in total QPE runtime, decreasing from 479.9 seconds to 244.4 seconds. CATMS also identified fewer "minimal nogoods," further reducing the overhead required to maintain logical consistency.

Conclusion and Future Work

CATMS provides a flexible framework that allows for a trade-off between compilation-time effort and query-time computation. By using assumptions as barriers to propagation, the system successfully avoids the exponential costs of label explosion in complex engineering and physics simulations.

Future research will focus on developing more sophisticated heuristics for the auto-assuming mechanism, such as "look-ahead" strategies to optimize when a node should be compressed. Additionally, the authors plan to investigate how CATMS integrates with other ATMS optimizations, including focusing and parallel processing, and how to efficiently "decompress" labels for specialized algorithms like the General Diagnostic Engine (GDE).

Summary updated

BibTeX
@inproceedings{collins1991catms,
  author = {John W. Collins and Dennis DeCoste},
  title = {{CATMS: An ATMS Which Avoids Label Explosions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure