A Probabilistic ATMS

Reference: Srinivas, S. A Probabilistic ATMS. Knowledge Systems Laboratory, February, 1994.

Abstract: Truth maintenance systems (TMS) provide a method of improving the efficiency of search during problem solving. The problem solver uses the TMS to record the reasons that facts are derivable so that facts need not be rederived during the course of the search. De Kleer's Assumption Based Truth Maintenance system (ATMS) overcomes the limitations of many earlier systems, such as not being able to switch states swiftly and not being able to consider multiple solutions to a problem at once. We describe a probabilistic extension to the ATMS -- An ATMS structure is augmented with a probability distribution over the set of assumptions. A probabilistic model is then constructed in the form of a Bayesian network from the ATMS structure. The probabilistic ATMS provides significant new functionality such as the derivation of the probability of a fact being derivable, the posterior probability over the assumptions given that a fact is derivable and the most probable context in which a fact is derivable. Our technique does not require the probability distribution of an assumption to be independent of the distributions of other assumptions. As an example of the use of the probabilistic ATMS, we show that it can be applied to construct probabilistic models to do multiple fault diagnosis. This generalizes some aspects of de Kleer and Williams' work on model based diagnosis. The probabilistic ATMS has been implemented in IDEAL, a Bayesian network solver.

Full paper available as ps.

Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.