Computing multiple minimal diagnoses

Existing research in Model-Based Diagnosis (MBD) primarily concerns computation of a single (possibly multiple-fault) diagnostic candidate. This is unrealistic, as often multiple candidates cannot be discerned given a system description and an observation vector. It is also computationally more difficult to compute multiple minimal-cardinality diagnoses, as opposed to a single diagnosis. In this paper we analyze the theoretical and practical aspects of computing multiple minimal-cardinality diagnoses. We propose an algorithm, named SAFARI, which solves the computational complexity problem by trading-off completeness for efficiency. Our algorithm has the desirable property of computing multiple-cardinality diagnoses with probability which is negatively exponential to the cardinality of the minimal-cardinality diagnoses. We also empirically confirm the theoretical results with experiments on a benchmark of 74XXX/ISCAS85 combinational circuits. The efficiency of the algorithm is evaluated in terms of metrics, and the results are compared to other MBD algorithms participating in the First International Diagnostic Competition (DXC'09). The results from the competition support our theoretical prediction that computing all minimal-cardinality diagnoses maximizes the DXC'09 utility metric. The results also show at least an order-of-magnitude speedup and an order-of-magnitude decrease in memory consumption while computing multiple minimal diagnoses of optimality similar to competing algorithms.