A theory of diagnosis from first principles. (English) Zbl 0643.68122

Reiter, Raymond

Artif. Intell. 32, 57-95 (1987).

Suppose one is given a description of a system, together with an observation of the system’s behaviour which conflicts with the way the system is meant to behave. The diagnostic problem is to determine those components of the system which, when assumed to be functioning abnormally, will explain the discrepancy between the observed and correct system behaviour.
We propose a general theory for this problem. The theory requires only that the system be described in a suitable logic. Moreover, there are many such suitable logics, e.g. first-order, temporal, dynamic, etc. As a result, the theory accommodates diagnostic reasoning in a wide variety of practical settings, including digital and analogue circuits, medicine, and database updates. The theory leads to an algorithm for computing all diagnoses, and to various results concerning principles of measurement for discriminating among competing diagnoses. Finally, the theory reveals close connections between diagnostic reasoning and nonmonotonic reasoning.

MSC:

68T99	Artificial intelligence
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Keywords:

correct system behaviour; diagnostic reasoning; nonmonotonic reasoning

References:

[1]	(Bobrow, D. G., Special Issue on Non-Monotonic Logic. Special Issue on Non-Monotonic Logic, Artificial Intelligence, 13 (1, 2) (1980))
[2]	Brown, J. S.; Burton, D.; 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
[3]	(Buchanan, B. G.; Shortliffe, E. H., Rule-based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project (1984), Addison-Wesley: Addison-Wesley Reading, MA)
[4]	Davis, R., Diagnostic reasoning based on structure and behavior, Artificial Intelligence, 24, 347-410 (1984)
[5]	de Kleer, J., Local methods for localizing faults in electronic circuits, MIT AI Memo 394 (1976), Cambridge, MA
[6]	de Kleer, J.; Williams, B. C., Diagnosing multiple faults, Artificial Intelligence, 32, 97-130 (1987), (this issue) · Zbl 0642.94045
[7]	Genesereth, M. R., The use of design descriptions in automated diagnosis, Artificial Intelligence, 24, 411-436 (1984)
[8]	Ginsberg, M. L., Counterfactuals, Artificial Intelligence, 30, 35-79 (1986) · Zbl 0655.03011
[9]	Jacobs, B. E., On database logic, J. ACM, 29, 2, 310-332 (1982) · Zbl 0497.68061
[10]	Jones, M.; Poole, D., An expert system for educational diagnosis based on default logic, (Proceedings Fifth International Workshop on Expert Systems and their Applications, II (1985)), 673-683, Avignon, France
[11]	McCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, 28, 89-116 (1986)
[12]	Moszkowski, B., A temporal logic for multilevel reasoning about hardware, IEEE Computer, 18, 2, 10-19 (1985)
[13]	Poole, D.; Aleliunas, R.; Goebel, R., Theorist: A logical reasoning system for defaults and diagnosis, (Tech. Rept. (1985), Logic Programming and Artificial Intelligence Group, Department of Computer Science, University of Waterloo: Logic Programming and Artificial Intelligence Group, Department of Computer Science, University of Waterloo Waterloo, Ont)
[15]	Reggia, J. A.; Nau, D. S.; Wang, Y., Diagnostic expert systems based on a set covering model, Int. J. Man-Mach. Stud., 19, 437-460 (1983)
[16]	Reggia, J. A.; Nau, D. S.; Wang, Y., A formal model of diagnostic inference I. Problem formulation and decomposition, Inf. Sci., 37, 227-256 (1985) · Zbl 0583.68046
[17]	Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 1, 2, 81-132 (1980) · Zbl 0435.68069
[18]	Tsotsos, J. K., Knowledge organization and its role in representation and interpretation for time-varying data: The ALVEN system, Comput. Intell., 1, 16-32 (1985)