Model-Based Diagnosis

SCIENTIFIC CONTEXT:

Artificial Intelligence,

Diagnostic Problem Solving,

Model-Based Reasoning,

Time-varying Systems

PARTICIPANTS:

Luca Console

Andrea Panati

Luigi Portinale

Paolo Terenziani

Daniele Theseider Dupre'

Pietro Torasso

MAIN GOALS:

Automated diagnosis of physical systems starting from a possibly incomplete description of the behavior of the system

Solutions of complex diagnostic problems involving multiple faults and symptom masking

Integration of diagnostic problem solving with monitoring, analysis of time-varying and dynamic aspects in diagnosis

Application of model-based diagnosis to software: automatic debugging of logic programs

METHODOLOGY:

Use of:

• causal or behavioral models in logical form
• Petri nets

to describe the behavior (correct and/or faulty behavior) of the system to be diagnosed; possibility of dealing with incomplete descriptions (models)

Characterization of diagnosis as abductive reasoning (for logical models)

Characterization of diagnosis in terms of Petri Net analysis (for Petri Net models)

Use of Case-based Reasoning (CBR) to improve the efficiency of inference by adapting solutions of past cases already solved

Use of compiled knowledge to focus on part of the search space and to discriminate among alternative diagnoses in a way integrated with the generation of such diagnoses

Use of probabilistic information to both model uncertainty in the behavior of the modeled system and guide the reasoning process

Decomposition of atemporal and temporal aspects of a problem in order to obtain a flexible framework for the integration of diagnosis and monitoring of time-varying systems

Integration with temporal constraint propagation

MAIN RESULTS

An abductive logical characterization of diagnosis (see also work on abduction )

Unification of the different logical definitions of diagnosis: a spectrum of definitions with comparisons and guidelines to chose the right definition for a given application

An efficient algorithm for computing diagnoses based on the use of compiled knowledge

A characterization of diagnosis in terms of reachability in a Petri net model

Definition of diagnostic algorithms based on analysis techniques of Petri nets and in particular definition of :

• a parallel approach to backward reachability analysis
• an approach computing diagnoses through the computation of the invariants of the net model

Definition of algorithmic debugging of logic programs via model- based diagnosis: several advantages with respect to the original definition

An extension of abductive diagnosis to deal with time-varying systems and observations gathered across time

PROTOTYPES AND SYSTEMS:

AID a tool for abductive model-based diagnosis:

• graphical interface for building models
• automatic compilation of focusing conditions
• menu-based interface for the dialogue with the user (e.g., for data acquisition)
• graphical interface for explanation

ADAPtER, a prototypical systems integrating the AID abductive algorithm with the use of solved cases

• simple menu-based interface
• batch or interactive training phase on the case memory
• possibility of guiding the retrieval and storing of new cases into memory

APPLICATIONS

medical domains: causal pathophysiological models

simple mechanical systems

debugging of logic programs

RELATIONS WITH OTHER INTERNAL PROJECTS

LaTeR for temporal reasoning

Abduction

COOPERATIONS

For medical applications: School of Medicine, University of Torino (1980-1994) and CIME, Ospedale San Giovanni, Torino (after 1994)

Technical University of Vienna for the diagnosis of logic programs (1992-1993)

CISE for monitoring applications (1992-1993)

IRISA, Rennes (France) (after 1994)

Other Italian Universities in MURST 40% project "Sistemi Intelligenti" (Intelligent Systems)

Other Italian Universities and research institutions for CNR project "Progetto Finalizzato Informatica" (1990-1994)

For car diagnosis: BRITE-EURAM project "Vehicle Model-Based Diagnosis" (VMBD), with european car manufacturers, electronic component suppliers and universities (after 1996)

MAIN REFERENCES

W. Hamscher , L. Console and J. de Kleer (eds.), Readings in Model-based Diagnosis, Morgan Kaufmann,1992.

L. Console and G. Friedrich (eds.), Special Issue on Model- Based Diagnosis, Annals of Mathematics and Artificial Intelligence,11 (1-4), 1994.

L. Console, D. Theseider Dupré, P. Torasso, A Theory of Diagnosis for Incomplete Causal Models, Proc. 11th IJCAI, pages 1311-1317,1989.

L. Console, P. Torasso, A Spectrum of Logical Definitions of Model-based Diagnosis, Computational Intelligence, 7 (3):133- 141, 1991.

L. Portinale, Exploiting T-invariant analysis in Diagnostic reasoning on a Petri net model, Proc. 14th Int. Conf. on Application and Theory of Petri Nets, LNCS 691, pages 339- 356, Springer Verlag,1993.

C. Anglano and L. Portinale, B-W analysis: a backward reachability analysis for diagnostic problem solving suitable to parallel implementation, Proc. 15th Int. Conf. on Application and Theory of Petri Nets, LNCS 815, pages 39-58, Springer Verlag, 1994.

L. Console and P. Torasso, On the co-operation between abductive and temporal reasoning in medical diagnosis, Artificial Intelligence in Medicine, 3(6):291-311,1991.

L. Console, L. Portinale, D. Theseider Dupré and P. Torasso, Diagnosing Time-Varying Misbehavior: an Approach Based on Model Decomposition, Annals of Mathematics and Artificial Intelligence, 11(1-4):381-398, 1994.

L. Console and P. Torasso, An Approach to the Compilation of Operational Knowledge from Causal Models, IEEE Trans. on Systems, Man and Cybernetics, 22(4):772-789, 1992.

L. Console, L. Portinale and D. Theseider Dupré, Using Compiled knowledge to guide and focus abductive diagnosis, IEEE Transactions on Knowledge and Data Engineering (to appear).

L. Portinale, P. Torasso, C. Ortalda and A. Giardino, Using Case-Based Reasoning to Focus Model-Based Diagnostic Problem Solving, in Lecture Notes in Artificial Intelligence 837, S. Wess, K.D. Althoff, M.M. Richter (eds.), pages 325- 337, Springer Verlag, 1994.

L. Console, G. Friedrich and D. Theseider Dupré, Model-Based Diagnosis Meets Error Diagnosis in Logic Programs, Proc. 13th IJCAI, pages 1494-1499, 1993.