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, (Sleeman, D.; Brown, J. S., Intelligent Tutoring Systems (1982), Academic Press: Academic Press New York), 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, (SNeRG Tech. Note No. 15 (1986), Department of Computer Science: Department of Computer Science SUNY at Buffalo, NY)
[7] Cantone, R. R.; Lander, W. B.; Marrone, M. P.; Gaynor, M. W., IN-ATE: Fault diagnosis as expert system guided search, (Bolc, L.; Coombs, M. J., Computer Expert Systems (1986), Springer: Springer New York)
[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, (Artificial Intelligence Laboratory, AI Memo 394 (1976), MIT: MIT Cambridge, MA)
[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, (Proceedings AAAI-84. Proceedings AAAI-84, Austin, TX (1984)), 142-147
[16] Hamscher, W.; Davis, R., Issues in diagnosis from first principles, (Artificial Intelligence Laboratory, AI Memo 394 (1986), MIT: MIT Cambridge, MA)
[17] Martins, J. P.; Shapiro, S. C., Reasoning in multiple belief spaces, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, F.R.G. (1983))
[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, (Computer Science Department, STAN-CA-78-711 (1970), Stanford University: Stanford University Palo Alto, CA)
[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, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 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: 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: 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, (Proceedings IJCAI-77. Proceedings IJCAI-77, Cambridge, MA (1977)), 1030-1037
[26] Quinlan, J. R., Learning efficient classification procedures and their application to chess end games, (Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M., Machine Learning (1983), Tioga: Tioga Palo Alto, CA), 463-482
[27] Reggia, J. A.; Nau, D. S., An abductive non-monotonic logic, (Workshop on Nonmonotonic Reasoning. Workshop on Nonmonotonic Reasoning, New Paltz, NY (1984))
[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, (Proceedings IEEE International Conference on Computer Design. Proceedings IEEE International Conference on Computer Design, Rye, NY (1983))
[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, (AI Tech. Rept. 595 (1979), MIT: MIT Cambridge, MA)
[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, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.