Scaling up Logic-Based Truth Maintenance Systems via Fact Garbage Collection

AAAI 1996

TL;DR

This paper introduces "fact garbage collection" for truth maintenance systems (TMS), a technique that significantly reduces memory usage and improves performance in applications with many assumption/retraction cycles. By identifying and discarding "collectible" facts that are unlikely to be needed again and are cheap to rederive, this method prevents the monotonic growth of the TMS dependency network, making large-scale TMS applications more practical.

What Problem Does This Paper Address?

Truth maintenance systems (TMS) are crucial for AI applications that require explanations and reasoning about beliefs. They maintain a dependency network of facts and inferences. However, a significant drawback of traditional TMS is the monotonic growth of this network as new assumptions are added. This leads to increasing memory consumption and slower performance, potentially causing crashes in long-running applications. The authors encountered this issue in an intelligent learning environment (ILE) called CyclePad, where frequent assumption changes caused performance degradation and system instability, hindering its practical deployment. This paper aims to solve this scalability problem by introducing a mechanism to actively reduce the size of the TMS dependency network.

Methods

The core contribution is the Fact Garbage Collection (Fact-GC) algorithm. The authors treat the TMS as a cache of inferences and apply cache-like update strategies. The algorithm identifies "collectible" facts based on a user-defined predicate GCable?. These facts are then removed from the dependency network when they become unknown. To ensure that the system can still generate explanations and re-derive necessary information, the algorithm caches "restoring thunks." These thunks store information about the rules that generated the deleted clauses, allowing those rules to be re-executed if a non-collectible antecedent becomes known again.

The Fact-GC algorithm is integrated into the TMS retraction process. When an assumption is retracted, the system first attempts to find alternative support. If the assumption remains unknown, the Fact-GC algorithm is invoked. It iterates through the retracted nodes, and if a node is marked as GCable? and is unknown, it triggers Collect-Node. Collect-Node then:

  1. Caches clause information: Creates a "restoring thunk" for each clause involving the collectible node, storing information about the rule that created it and any non-collectible antecedents.
  2. Deletes rules: Removes any unexecuted rule instantiations that were triggered by the collectible node.
  3. Deletes the node: Removes the node itself from the TMS.

This process ensures that collectible facts and their associated dependencies are removed, while preserving the ability to reconstruct necessary information when needed.

Datasets

Not discussed in the paper. The evaluation uses a simulated scenario within the CyclePad system.

Key Insights and Ideas

  • TMS as a Cache: The paper's central insight is to view TMS not just as a persistent record but as a cache of inferences. Like any cache, it benefits from strategies to prune stale or unlikely-to-be-used entries.
  • Fact Garbage Collection: Actively removing facts that are unlikely to be needed again and are cheap to rederive is a practical way to combat the monotonic growth of TMS dependency networks.
  • Restoring Thunks: The mechanism for caching information to re-execute rules when non-collectible antecedents become known is crucial for maintaining the explanatory power of the TMS after garbage collection.
  • Trade-off Management: The algorithm balances the need to reclaim storage with the cost of rederiving facts, making it suitable for applications where facts are frequently assumed and retracted but rarely needed again once retracted.

Key Results

The paper demonstrates significant performance improvements using the Fact-GC algorithm in the CyclePad system.

  • Memory Reduction: The conventional LTRE (the inference engine with a standard TMS) exhausted 32MB of memory after 48 assumption/retraction cycles. In contrast, the GC-LTRE showed virtually no growth in data structures (nodes, clauses, rules) over the same number of cycles.
  • Performance Improvement: The average time per assumption/retraction cycle in CyclePad with the conventional LTRE increased to 46 seconds by the 48th cycle. With Fact-GC, the average time remained around 3.1 seconds for 1000 cycles, with the LTRE size remaining constant.
  • Scalability: The GC-LTRE enabled the system to handle a much larger number of assumption/retraction cycles without performance degradation, making it practical for real-world applications.

Limitations and Future Work

  • Applicability: The authors acknowledge that Fact-GC is most beneficial for applications where:
  • A class of facts constitutes a significant portion of the TMS database.
  • These facts are unlikely to be needed again once unknown.
  • These facts are inexpensive to rederive. They suggest that applications creating large caches of "nogoods" or frequently switching between a small set of assumptions might not benefit as much.

  • Future Work: The authors plan to test the GC-LTRE on other types of TMS-based applications, such as coaches for ILEs and qualitative simulators. They also mention an ongoing educational simulator project using the LTRE as a basis. The empirical question of when Fact-GC is beneficial remains open.

Summary updated

BibTeX
@inproceedings{1996scaling,
  title = {{Scaling up Logic-Based Truth Maintenance Systems via Fact Garbage Collection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure