Technical Reports

The ICICS/CS Reading Room

UBC CS TR-88-10 Summary

Solving Diagnostic Problems using Extended Truth Maintenance Systems, July 1988 Gregory M. Provan

We describe the use of efficient, extended Truth Maintenance Systems (TMSs) for diagnosis. We show that for complicated diagnostic problems, existing ATMSs need some method of ranking competing explanations and pruning the search space in order to maintain computational efficiency. We describe a specific implementation of an ATMS for efficient problem solving that incorporates the full Dempster Shafer theory in a semantically clear and efficient manner. Such an extension allows the Problem Solver to rank competing solutions and explore only the ``most likely'' solutions. We also describe several efficient algorithms for computing both exact and approximate values for Dempster Shafer belief functions.

If you have any questions or comments regarding this page please send mail to