Performance Issues in Unimodal and Multimodal Reasoning Approaches to Diagnosis

In the paper we report experiments in two domains showing that the theoretical worst case intractability of diagnostic problem solving using MBR does occur in practice and that some diagnostic problems can't be solved in a reasonable time. The pape addresses the problem of estimating the computational effort needed to solve the problem via an abductive approach to MBR. We show experimentally that this effort is much strongly related to the number of coverings actually computed for the set of observed data than to the number of minimal diagnoses. We introduce a heuristic function able to (qualitatively) estimate the CPU time taken by MBR for solving the problem at hand. Given a classification of the diagnostic problems into 3 classes (easy, medium, hard) according to the time needed to solve them by MBR, we show the suitability of the heuristic function for predicting the class of each problem. This capability of predicting the class of each problem allows the definition of a flexible diagnostic problem solver which makes use of MBR, CBR or of a combination of both for solving it. We compare such a flexible problem solver both with the pure MBR problem solver and with ADAPtER, a hybrid MBR-CBR problem solver with a rigid architecture. The advantages of the flexible architecture problem solver both in terms of computational effort and competence are shown experimentally.