Computing Multiple Minimal Diagnoses



Published Mar 26, 2021
Alexander Feldman Gregory Provan Arjan van Gemund


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.

How to Cite

Feldman, A., Provan, G., & van Gemund, A. (2021). Computing Multiple Minimal Diagnoses. Annual Conference of the PHM Society, 1(1). Retrieved from
Abstract 5 | PDF Downloads 1



diagnostic algorithm, model based diagnostics

(Brglez and Fujiwara, 1985) Franc Brglez and Hideo Fujiwara. A neutral netlist of 10 combinational benchmark circuits and a target translator in For- tran. In Proc. ISCAS’85, pages 695–698, 1985.
(Bunus et al., 2009) Peter Bunus, Olle Isaksson, Beate Frey, and Burkhard Mu ̈nker. RODON - a model-based diagnosis approach for the DX diagnostic competition. In Proc. DX’09, pages 423–430, 2009.
(Davis et al., 1962) Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving. Communications of the ACM, 5(7):394–397, 1962.
(de Kleer and Williams, 1987) Johan de Kleer and Brian Williams. Diagnosing multiple faults. Artificial Intelligence, 32(1):97–130, 1987.
(de Kleer et al., 1992) Johan de Kleer, Alan Mack- worth, and Raymond Reiter. Characterizing diagnoses and systems. Artificial Intelligence, 56(2- 3):197–222, 1992.
(de Kleer, 1986) Johan de Kleer. Problem solving with the ATMS. Artificial Intelligence, 28(2):197– 224, 1986.
(de Kleer, 1990) Johan de Kleer. Using crude probability estimates to guide diagnosis. Artificial Intelligence, 45(3):381–291, 1990.
(de Kleer, 2009) Johan de Kleer. Minimum cardinality candidate generation. In Proc. DX’09, pages 397–402, 2009.
(Feldman and van Gemund, 2006) Alexander Feld- man and Arjan van Gemund. A two-step hierarchical algorithm for model-based diagnosis. In Proc. AAAI’06, pages 827–833, July 2006.
(Feldman et al., 2006) Alexander Feldman, Jurryt Pietersma, and Arjan van Gemund. All roads lead to fault diagnosis: Model-based reasoning with LYDIA. In Proc. BNAIC’06, October 2006.
(Feldman et al., 2008a) Alexander Feldman, Gregory Provan, and Arjan van Gemund. Computing minimal diagnoses by greedy stochastic search. In Proc. AAAI’08, pages 911–918, 2008.
(Feldman et al., 2008b) Alexander Feldman, Gregory Provan, and Arjan van Gemund. Computing observation vectors for max-fault min-cardinality diagnoses. In Proc. AAAI’08, July 2008.
(Forbus and de Kleer, 1993) Kenneth Forbus and Jo- han de Kleer. Building Problem Solvers. MIT Press, 1993.
(Hansen et al., 1999) Mark Hansen, Hakan Yalcin, and John Hayes. Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering. IEEE Design & Test, 16(3):72–80, 1999.
(Kurtoglu et al., 2009) Tolga Kurtoglu, Sriram Narasimhan, Scott Poll, David Garcia, Lukas Kuhn, Johan de Kleer, Arjan van Gemund, and Alexander Feldman. First international diagnosis competition - DXC’09. In Proc. DX’09, pages 383–396, 2009.
(McAllester, 1990) David McAllester. Truth maintenance. In Proc. AAAI’90, volume 2, pages 1109– 1116, 1990.
(Siddiqi and Huang, 2007) Sajjad Siddiqi and Jinbo Huang. Hierarchical diagnosis of multiple faults. In Proc. IJCAI’07, pages 581–586, 2007.
(Williams and Ragno, 2007) Brian Williams and Robert Ragno. Conflict-directed A* and its role in model-based embedded systems. Journal of Discrete Applied Mathematics, 155(12):1562–1595, 2007.
Technical Papers

Most read articles by the same author(s)