SOLVING DIAGNOSTIC PROBLEMS USING EXTENDED ASSUMPTION-BASED TRUTH MAINTENANCE SYSTEMS: FOUNDATIONS

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.