Computing Multiple Minimal Diagnoses
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Abstract
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
##plugins.themes.bootstrap3.article.details##
diagnostic algorithm, model based diagnostics
(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.
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
The Prognostic and Health Management Society advocates open-access to scientific data and uses a Creative Commons license for publishing and distributing any papers. A Creative Commons license does not relinquish the author’s copyright; rather it allows them to share some of their rights with any member of the public under certain conditions whilst enjoying full legal protection. By submitting an article to the International Conference of the Prognostics and Health Management Society, the authors agree to be bound by the associated terms and conditions including the following:
As the author, you retain the copyright to your Work. By submitting your Work, you are granting anybody the right to copy, distribute and transmit your Work and to adapt your Work with proper attribution under the terms of the Creative Commons Attribution 3.0 United States license. You assign rights to the Prognostics and Health Management Society to publish and disseminate your Work through electronic and print media if it is accepted for publication. A license note citing the Creative Commons Attribution 3.0 United States License as shown below needs to be placed in the footnote on the first page of the article.
First Author et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.