In this paper we present an extension of the spectrum of logical de nitions of model-based diagnosis introduced in (Console &Torasso 1991b). The extended spectrum considers the case of temporal model-based diagnosis and generalizes the logical characteriza

A spectrum of de nitions for temporal model-based diagnosisV. Brusoniand

L. Console

Dipartimento di Informatica, Universita di Torino Corso Svizzera 185, 10149 Torino, Italy Phone:+39 11 7429111| Fax:+39 11 751603 E-mail: fbrusoni,lconsole,terenz,dtdg@di.unito.it

and

P. Terenziani

and

D. Theseider Dupre

In this paper we present an extension of the spectrum of logical de nitions of model-based diagnosis introduced in (Console& Torasso 1991b). The extended spectrum considers the case of temporal model-based diagnosis and generalizes the logical characterization of abductive temporal diagnosis presented in (Brusoni et al. 1996). We distinguish between di erent temporal phenomena that can be taken into account in diagnosis and we introduce a modeling language which can capture all such phenomena. We then introduce a general characterization of the notions of diagnostic problem and explanation, showing that in the temporal case the spectrum of alternative de nitions has two dimensions: the notion of logical explanation being adopted (i.e., consistency vs. entailment, as in consistency-based and abductive approaches to atemporal diagnosis) and the notion of temporal explanation (i.e., requiring that the temporal information on the observations is consistent with or entailed by that in the part of the model used for explaining the observations). In the paper we analyse the various alternatives in the spectrum and we show how various approaches in the literature can be classi ed within our framework.

Abstract

Time is an important dimension of model-based diagnosis, as pointed out by many researchers (see, e.g., (Hamscher, Console,& de Kleer 1992), chapters 5 and 6). In fact, the assumption that the system to be diagnosed is static and that all the observations are given at a single time point is restrictive in many domains. Various aspects concerning time have been considered in the approaches in the literature in particular, each approach focused on one or more of the following three aspects, where the rst one is related to the observations and the other two ones to the model of the system1: Time-varying context. The behavior of the system is observed in di erent contexts (which necessarily1 The authors are indebted to Roy Leitch and other people from his group for the following classi cation.

Introduction

imply di erent times): for example, di erent inputs (test vectors) are provided to a combinatorial circuit, in order to collect more evidence on its behavior. The system and its components could be assumed to maintain their\working" or\faulty" mode across the times of observation or could be allowed to change behavior (see time-varying behavior below). Actually, the issue of time-varying contexts is more interesting when it is coupled with one of the two cases below. Temporal behavior. Given a model of the behavior of a system, the consequences of the fact that the system is in a speci c (normal or faulty) mode manifest themselve

s after some time and for some time. A diagnosis should account for both the observations and their temporal location. These types of phenomena have been rst considered in\causal" approaches to diagnosis (e.g. (Console& Torasso 1991a Long 1983)) and then in model-based diagnosis (Guckenbiehl& Schafer-Richter 1990 Hamscher 1991 Nejdl& Gamper 1994 Nokel 1989). A temporal behavior can be a dynamic one, in case the behavior of the system depends on its internal state (memory), as in sequential circuits in such cases diagnosis is typically very underconstrained (Hamscher& Davis 1984). Time-varying behavior. A system (or its components) may have di erent faults across time (Console et al. 1994 Downing 1992 Friedrich& Lackinger 1991). This is particularly interesting when diagnosis is coupled with monitoring (Lackinger& Nejdl 1991). Unlike dynamic models above, in this case there is typically only a weak model for transitions from one fault to the other or from normality to faults (e.g., the model distinguishes possible and impossible transitions or attaches probabilities to transitions, but it does not know about preconditions of transitions). Each one of the approaches in the literature focused on some of the aspects above (the references in the items above corresponds to approaches that focused either on temporal or on time-varying behavior). Furthermore, di erent models (ontologies) for time have