Diagnosing multiple faults. (English) Zbl 0642.94045

Summary: The diagnostic procedure presented in this paper is model-based, inferring the behavior of the composite device from knowledge of the structure and function of the individual components comprising the device. The system (GDE-general diagnostic engine) has been implemented and tested on many examples in the domain of troubleshooting digital circuits. This research makes several novel contributions: First, the system diagnoses failures due to multiple faults. Second, failure candidates are represented and manipulated in terms of minimal sets of violated assumptions, resulting in an efficient diagnostic procedure. Third, the diagnostic procedure is incremental, exploiting the iterative nature of diagnosis. Fourth, a clear separation is drawn between diagnosis and behavior prediction, resulting in a domain (and inference procedure) independent diagnostic procedure. Fifth, GDE combines model- based prediction with sequential diagnosis to propose measurments to localize the faults. The normally required conditional probabilities are computed from the structure of the device and models of its components. This capability results from a novel way of incorporating probabilities and information theory into the context mechanism provided by assumption- based truth maintenance.


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68T99 Artificial intelligence
92C50 Medical applications (general)
Full Text: DOI


[1] Ben-Bassat, M., Myopic policies in sequential classification, IEEE trans. comput., 27, 170-178, (1978)
[2] Ben-Bassat, M., Multimembership and multiperspective classification: introduction, applications, and a Bayesian model, IEEE trans. syst. man cybern., 6, 331-336, (1980)
[3] Ben-Bassat, M.; Campbell, D.B.; Macneil, A.R.; Weil, M.H., Pattern-based interactive diagnosis of multiple disorders: the MEDAS system, IEEE trans. pattern anal. Mach. intell., 2, 148-160, (1980)
[4] Brown, J.S.; Burton, R.R.; de Kleer, J., Pedagogical, natural language and knowledge engineering techniques in SOPHIE I, II and III, (), 227-282
[5] Davis, R., Diagnostic reasoning based on structure and behavior, Artifical intelligence, 24, 347-410, (1984)
[6] Campbell, S.S.; Shapiro, S.C., Using belief revision to detect faults in circuits, ()
[7] Cantone, R.R.; Lander, W.B.; Marrone, M.P.; Gaynor, M.W., IN-ATE: fault diagnosis as expert system guided search, ()
[8] de Kleer, J., An assumption-based TMS, Artifical intelligence, 28, 127-162, (1986)
[9] de Kleer, J., Problem solving with the ATMS, Artifical intelligence, 28, 197-224, (1986)
[10] de Kleer, J., Local methods of localizing faults in electronic circuits, ()
[11] Doyle, J., A truth maintenance system, Artificial intelligence, 12, 231-272, (1979)
[12] Genesereth, M.R., The use of design descriptions in automated diagnosis, Artificial intelligence, 24, 411-436, (1984)
[13] Ginsberg, M.L., Counterfactuals, Artificial intelligence, 30, 35-79, (1986) · Zbl 0655.03011
[14] Gorry, G.A.; Barnett, G.O., Experience with a model of sequential diagnosis, Comput. biomedical res., 1, 490-507, (1968)
[15] Hamscher, W.; Davis, R., Diagnosing circuits with state: an inherently underconstrained problem, (), 142-147
[16] Hamscher, W.; Davis, R., Issues in diagnosis from first principles, ()
[17] Martins, J.P.; Shapiro, S.C., Reasoning in multiple belief spaces, ()
[18] McCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artificial intelligence, 28, 89-116, (1986)
[19] Mitchell, T., Version spaces: an approach to concept learning, ()
[20] Pearl, J., Entropy, information and rational decision, Policy anal. inf. syst., 3, 93-109, (1979)
[21] Peng, Y.P.; Reggia, J.A., Plausibility of diagnostic hypotheses: the nature of simplicity, (), 140-145
[22] Peng, Y.P.; Reggia, J.A., A probabilistic causal model for diagnostic problem-solving; part 1: integrating symbolic causal inference with numeric probabilistic inference, (1986), Department of Computer Science, University of Maryland College Park, MD
[23] Peng, Y.P.; Reggia, J.A., A probabilistic causal model for diagnostic problem-solving; part 2: diagnostic strategy, (1986), Department of Computer Science, University of Maryland College Park, MD
[24] Pipitone, F., The FIS electronics troubleshooting system, IEEE computer, 68-75, (1986)
[25] Pople, H., The formation of composite hypotheses in diagnostic problem solving: an exercise in synthetic reasoning, (), 1030-1037
[26] Quinlan, J.R., Learning efficient classification procedures and their application to chess end games, (), 463-482
[27] Reggia, J.A.; Nau, D.S., An abductive non-monotonic logic, ()
[28] Reggia, J.A.; Nau, D.S.; Wang, P.Y., Diagnostic expert systems based on a set covering model, Int. J. man-Mach. stud., 19, 437-460, (1983)
[29] Reiter, R., A theory of diagnosis from first principles, Artificial intelligence, 32, 57-95, (1987), (this issue) · Zbl 0643.68122
[30] Shannon, C.E., A mathematical theory of communication, Bell syst. tech. J., 27, 379-623, (1948) · Zbl 1154.94303
[31] Shirley, M.H.; Davis, R., Generating distinguishing tests based on hierarchical models and symptom information, ()
[32] Slagle, J.R.; Lee, R.C.T., Application of game tree searching techniques to sequential pattern recognition, Commun. ACM, 14, 103-110, (1971) · Zbl 0213.18205
[33] Steele, G.L., The definition and implementation of a computer programming language based on constraints, ()
[34] Sussman, G.J.; Steele, G.L., CONSTRAINTS: A language for expressing almost-hierarchical descriptions, Artificial intelligence, 14, 1-39, (1980)
[35] Szolovitz, P.; Pauker, S.G., Categorical and probabilistic reasoning in medical diagnosis, Artificial intelligence, 11, 115-144, (1978)
[36] Williams, B.C., Doing time: putting qualitative reasoning on firmer ground, (), 105-112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.