Scaling up logic-based truth maintenance systems via fact garbage collection

John O. Everett*, Kenneth D Forbus

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Truth maintenance systems provide caches of beliefs and inferences that support explanations and search. Traditionally, the cost of using a TMS is monotonic growth in the size of this cache. In some applications this cost is too high; for example, intelligent learning environments may require students to explore many alternatives, which leads to unacceptable performance. This paper describes an algorithm for fact garbage collection that retains the explanation-generating capabilities of a TMS while eliminating the increased storage overhead. We describe the application context that motivated this work and the properties of applications that benefit from this technique. We present the algorithm, showing how to balance the tradeoff between maintaining a useful cache and reclaiming storage, and analyze its complexity. We demonstrate that this algorithm can eliminate monotonic storage growth, thus making it more practical to field large-scale TMS-based systems.

Original languageEnglish (US)
Title of host publicationProceedings of the National Conference on Artificial Intelligence
Editors Anon
PublisherAAAI
Pages614-620
Number of pages7
Volume1
StatePublished - Dec 1 1996
EventProceedings of the 1996 13th National Conference on Artificial Intelligence, AAAI 96. Part 1 (of 2) - Portland, OR, USA
Duration: Aug 4 1996Aug 8 1996

Other

OtherProceedings of the 1996 13th National Conference on Artificial Intelligence, AAAI 96. Part 1 (of 2)
CityPortland, OR, USA
Period8/4/968/8/96

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Scaling up logic-based truth maintenance systems via fact garbage collection'. Together they form a unique fingerprint.

  • Cite this

    Everett, J. O., & Forbus, K. D. (1996). Scaling up logic-based truth maintenance systems via fact garbage collection. In Anon (Ed.), Proceedings of the National Conference on Artificial Intelligence (Vol. 1, pp. 614-620). AAAI.