A spectrum of de nitions for temporal model-based diagnosis. Arti cial Intelligence (to app

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

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

been adopted, e.g., some approaches use metric time (e.g., (Guckenbiehl& Schafer-Richter 1990 Long 1983 Console& Torasso 1991a)), other approaches use only some qualitative notion of temporal ordering (e.g., (Nejdl& Gamper 1994), which deals with qualitative temporal relations expressed in Allen's interval algebra (Allen 1983)), other approaches use ad-hoc abstract temporal primitives (e.g., (Hamscher 1991)). Finally, di erent logical notions of diagnosis have been adopted: some approaches refer to the consistency-based notion of explanation (de Kleer, Mackworth,& Reiter 1992 Reiter 1987), others to the abductive notion of explanation (Console& Torasso 1991b Poole 1989). A reader looking at the various approaches tends to get confused about the actual nature of the problem in some cases (s)he is forced to analyse many technical and/or domain-dependent aspects concerning the various approaches and these details may be not very important to understand the merits of the proposed solutions and to compare one approach with the others. We believe that a general framework, providing a general and domain-independent characterization of temporal model-based diagnosis would be very important. Such a framework should provide a reference definition for the problem and, what is most important, a general characterization of the space of the alternative approaches to the solution of the problem. Thus, if the approaches in the literature can be cast into the framework, one can have a common ground to compare them at a knowledge level. Formal frameworks that c

apture the various approaches and allow to compare them have been proposed as regards the case of atemporal model-based diagnosis (consider, e.g., the logical spectrum of de nitions of diagnosis introduced in (Console& Torasso 1991b) and then discussed and extended in (Besnard& Cordier 1994 Preist, Eshghi,& Bertolino 1994 ten Teije& van Harmelen 1994)). In this paper we propose a formal framework for temporal diagnosis that generalizes the characterization in (Brusoni et al. 1996). The framework is very general as regards both the modeling language and the notion of diagnosis. The modeling language we propose can capture both temporal behavior (including dynamic behavior) and time varying behavior and is completely independent of the model of time being adopted (i.e., the approach makes no assumption on the language for representing temporal information and temporal constraints). As regards the notion of diagnosis, the framework extends the spectrum of de nitions of diagnosis proposed in (Console& Torasso 1991b) showing that in the temporal case there are at least two (partially interacting) issues to be de ned: the notion of logical explanation being adopted (consistency-based vs. abductive) this is the dimen-

sion considered in (Console& Torasso 1991b) the notion of temporal explanation being adopted. We show that also in the latter case one can consider a spectrum of alternatives ranging from a consistencybased to an abductive notion of temporal explanation. This leads to a two-dimension lattice of alternative definitions of the notion of temporal diagnosis which generalizes the one-dimension lattice presented in (Console& Torasso 1991b). As in (Console& Torasso 1991b), we show that different approaches in the literature correspond to different alternatives in the lattice and this provides a knowledge-level framework for comparing the alternative approaches. Moreover, as in (Console& Torasso 1991b), we give some guidelines to select among the alternative de nitions in the spectrum, given the available model of the system to be diagnosed. The paper is organised as follows: in the following section we sketch a language for modeling the temporal, dynamic and time-varying behavior of a system (which extends the language in (Brusoni et al. 1996)) then we sketch the de nition of the extended spectrum nally, we analyse how di erent approaches to temporal diagnosis can be cast into our framework in particular, we provide a (partial) list classifying the various approaches by taking into account both the type of temporal phenomena they can deal with and the notion of diagnosis in the spectrum they adopt. In this section we rst sketch a language for modeling temporal and time-varying behavior of a physical system. We then show, through a set of examples, that the language is general enough to capture both temporal and time-varying behavior. Let us consider a system (device) D and let COMP= fc1::: cn g be the set of components of D. Each co

mponent of D is characterized by a set of behavioral modes: the behavior of the device D can be represented as the consequence of the behavioral modes of its components. In particular, the behavior of a system is described using two sets of formulae: a set TBM of behavior formulae and a set TC of temporal integrity constraints. A behavior formula has the form: a1 (X1 T1 )::: an (Xn Tn ) explains b1 (Y1 T1)::: bm (Ym Tm ) fC (T1::: Tn T1::: Tm )g where: the symbols ai may denote a mode of behavior of a component ck or some input to the component or a state in which the component can be or some contextual condition on which the behavior of the component may depend the symbols bj may denote the output of a component or some state in which the component can be.0 0 0 0

Temporal behavioral models

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

straints associated with the formula it expresses constraints between the entities in the formula. More speci cally, C is a constraint between maximal episodes for a1 (X1 ),::: an (Xn ) and episodes for each bi (Yi ) episodes of each bi (Yi ) are not necessarily maximal since other overlapping episodes of bi (Yi ) may be derived due to other causes, giving rise to a single maximal episode for bi (Yi ). However, some local form of maximality is assumed also for the episodes of bi (Yi ): one such episode would be maximal in the absence of any other reason for having bi (Yi ), i.e., in the absence of episodes of other entities implying bi (Yi ) or of other episodes for a1 (X1 ),:::, an (Xn ) (in fact, it would also be conceivable that two di erent sets of maximal episodes of the causes led to two overlapping episodes of bi (Yi ), and then to a single maximal episode of bi (Yi )). C may contain constraints that relate the episodes for the explained entities b1 (Y1 )::: bm (Ym ) to the maximal episodes for the explaining entities a1 (Xi )::: an (Xn ), as well as constraints on the maximal episodes of explaining entities only (e.g. on their duration or their relative location) and on episodes of the explained entities only (the use of the last type of constraints has been advocated, e.g., in (Nokel 1989)). We interpret the constraint C as a necessary condition in order for a1 (X1 T1 ),:::, an (Xn Tn ) to be an explanation for b1 (Y1 T1),:::, bm (Ym Tm) i.e. using a1 (X1 T1),:::, an (Xn Tn ) as an explanation for b1 (Y1 T1 ),:::, bm (Ym Tm) requires that C holds (or imposing that it holds, if it is not known). Moreover, we consider the restriction of C to the explaining entities only (i.e. to the premises ai ) as a su cient condition for a1 (X1 T1),:::, an (Xn Tn ) to have as a consequence episodes of b1 (Y1 ),:::, bm(Ym ) (satisfying the rest of the constraints in C). A more exible alternative could be to provide an explicit su cient condition. The temporal integrity constraints in TC are expressed as a logical formula of temporal constraints involving maximal episodes for some entities in the model. For example, a cons

traint like: a(X T1)^ b(Y T2) ! T1 disjoint T2 can be used for imposing that a(X ) and b(Y ) are mutually exclusive (their episodes must be temporally disjoint). All the discussion above and in the following is completely independent of the language for expressing the temporal constraints (in the examples in the paper we will use the language of LaTeR, a general purpose temporal reasoning system that we developed over the0 0 0 0

Ti denotes a time interval in which ai (Xi ) is true (an episode for ai (Xi )) similarly for the bj . Xi (resp., Yj ) represent a generic tuple of arguments of ai (resp., bj ). C (T1::: Tn T1::: Tm ) is a set of temporal con0 0

last few years (Brusoni et al. February 1997)). The only requirement is the language must provide the notion of consistency of a set of constraints and the notion of entailment of some temporal constraints from a set of temporal constraints. The language sketched above allows us to express both temporal (non-dynamic and dynamic) and timevarying behavior. The forms of temporal behavior used in many diagnostic systems based on causal models (e.g. (Long 1983 Console& Torasso 1991a Pan 1984)) can be captured using behavior formulae. In this case the atoms correspond to states of part of the modeled system, behavior formulae correspond to causal relations and the constraints express the temporal relations between the states involved in a causal relation. For example, the following formula: engine(on T1) friction(T2 ) explains engine temp(high T3) fT4= intersection(T1 T2 ) T4 lasting at least 2 hours start(T3 ) 3 hours after start(T4 )g is a causal relation specifying that friction causes a high engine temperature if the engine is on the temporal constraint speci es that there must be a minimal persistence of the cause (better, of the intersection between the cause and the contextual condition) to produce an e ect and that the start of the e ect is delayed with respect to the start of the cause. In a similar way, behavior formulae can be used to express the component-oriented behavioral models typical of the model-based tradition (since dart (Genesereth 1984), ht (Davis 1984), gde (de Kleer& Williams 1987)). In this case some selected atoms in the behavior formulae denote a mode of behavior of the components being modeled and each formula describes a rule of behavior (usually input-output behavior) of a component. In this case the temporal constraints express delays in such a behavior (e.g., delays between input and outputs). Models of temporal behavior of this form have been used, e.g., in (Hamscher 1991 Guckenbiehl& Schafer-Richter 1990). The following is an example taken from (Guckenbiehl& Schafer-Richter 1990): and gate(X ) inp1(X I1 T1 ) inp2 (X I2 T2 ) explains out(X and(I1 I2 ) T3 ) fT1 equal T2 start(T3 ) 30 after start(T1 )g describing the temporal behavior of a gate in a combinatorial circuit. In case the behavior to be modeled is dynamic (i.e., the system or component being mode

led has an internal memory and its behavior depends on such a memory) it is su cient to use some atoms in the formulae to denote the internal memory. For example, suppose that the behavior of a device (component) d depends on its internal state s. This can be expressed with a formula of the form:

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

constraints may be associated with such a behavior, e.g.: T2 during T1 T3 during T1 T3 meets T5, start(T4 ) n after start(T2 ) start(T5 ) m after start(T2 ) specifying that there is a delay of n units of time between the input and output, that the change of state starts m units of time after the input and that the interval for the new state meets the interval for the old state (i.e., that the component must always be in some state). Temporal integrity constraints can be used to impose that d cannot be in two di erent states at the same time. These types of models have been used, e.g., in (Hamscher& Davis 1984 Hamscher 1991). Let us consider now the case of time-varying behavior. The behavior of a device (component) is timevarying if the device (component) can assume di erent modes of behavior across time (Friedrich& Lackinger 1991). This type of information can be expressed in our language using temporal integrity constraints. A powerful formalism used in time-varying systems for expressing how modes can evolve across time is that of Mode Transition Graphs (Console et al. 1994 Nejdl& Gamper 1994), to impose that a set of mutually exclusive behavioral modes could or must follow each other only in a constrained way: e.g. m1 must be directly followed by m2 or m3, but not by other modes. Also these types of constraints can be expressed as temporal integrity constraints between the atoms denoting modes of behavior. The example above can be expressed by the following formula: m1 (T ) ! 9T (T meets T^ (m2 (T ) _ m3 (T ))) (in addition to the constraints that specify that the modes are mutually exclusive). Thus both temporal (non-dynamic and dynamic) and time-varying behavior can be expressed in our formalism with appropriate modeling. In order to provide a formal characterization of temporal diagnosis, a model expressed in terms of a set TBM of temporal behavior formulae and a set TC of temporal integrity constraints can be transformed into a set of logical formulae. These logical formulae thus provide a semantics for our modeling formalism. The transformation involves some technicalities (in particular for expressing in logical terms the meaning of the temporal constraints associated with temporal behavior formulae) and is presented elsewhere (Brusoni et al. 1996). The output of the transformation is formed by the following sets:0 0 0 0

modei (d T1 ) inp(d X T2) s(d Y T3 ) explains out(d f (X Y ) T4 ) s(d g(X Y ) T5 ) fC (T1::: T5 )g which says that if d is in mode modei and in state Y and it receives the input X, it produces the output f (X Y ) and its state changes to g(X Y ). Temporal

TBML: the logical correspondent of the temporal behavioral

model TBM and of the set TC of tem-

poral integrity constraints Abd: the set of abducible symbols, i.e. symbols that can be part of the solution to a diagnostic problem (see next section). These correspond to the assumptions that can be made during the diagnostic process and include at least the symbols denoting modes of behavior of the device (or of the components) being modeled and to be diagnosed. In this section we show how the spectrum of logical definitions of diagnosis introduced in (Console& Torasso 1991b) for the atemporal case can be extended to the temporal case, starting from the modeling formalism introduced in the previous section. A diagnostic problem is characterized by a set of observations to be explained. In particular, diagnosis is relevant when there is a discrepancy between the expected behavior of a system and the observed behavior, so that observations correspond to symptoms gathered during the abnormal behavior of the system. The goal of diagnostic problem solving is to determine which faults of the system (or, in particular, of one or more of its components) can explain the abnormal behavior. From a general point of view, observations can be characterized by four sets: CXT= fa1 a2::: am g: a set of contextual data OBSpos= fo1 o2::: on g: a set of positive atoms corresponding to data that have been observed OBSneg= f:b1:b2::::bk g: a set of negative observations, corresponding to data that are known to be absent (false), at least in some period of time (as speci ed by the item below). TOBSTC (ta1::: tam to1::: ton tnot b1::: tnot ok ) a set of temporal constraints on contextual and observed data. In particular, the set TOBSTC can be partitioned into two subsets: CCXT containing constraints that involve contextual data only and COBS containing all the other constraints. The distinction between contextual data and observations is the same one introduced in (Console& Torasso 1991b): contextual data correspond to data that have not to be accounted for by a diagnosis, unlike observations that have to be accounted for. Typical examples of contextual data are the inputs to the device to be analysed while the outputs from the device are examples of observations to be explained. TOBSTC is a set of temporal constraints (expressed in some language for temporal constraints) and provides temporal information on contextual data and observations. It may contain information on the absolute temporal location (with respect to a reference time point) or duration of observed events, which may be precise, as in

An extended spectrum for diagnosis

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

inp(a 1 t1) out(a 0 t2 ) t1= 20 t2= 40 in which the input and output of a component a are located precisely in time, or imprecise, as in engine temp(high t) t lasting at least 20 start(t) between 30 and 60 This constraint speci es that the temperature of the engine has been high during an interval t starting between time 30 and 60 and whose duration is at least 20 units

of time. Qualitative information on the relative position of events can also be the only temporal information available, as in out(a 1 t1) out(b 0 t2 ) t1 overlaps t2 This constraint speci es that the interval t1 and t2 overlap (\overlap" is one of the relations in Allen's interval algebra (Allen 1983)). Given the model of the system to be diagnosed and the observations, we can introduce the notion of temporal diagnostic problem: De nition 1 Given the observations CXT, OBSpos, OBSneg, COBS and CCXT, a temporal diagnostic problem is a six-tuple hTBML CXT CCXT TOBSE, TOBSTE TOBSTC i where: TBML is the logical representation of the model of the system to be diagnosed (TBM and TC details are given in (Brusoni et al. 1996)). TOBSE is a subset of the observations OBSpos . TOBSTE is a subset of the temporal constraints COBS associated with the observations. TOBSTC is the set of all the temporal constraints on the observations. TOBSE and TOBSTE can be any subsets of the observations and on the temporal constraints on the observations, respectively. Following (Console& Torasso 1991b), TOBSE isolates a subset of the observations that must be explained abductively. As in (Console& Torasso 1991b) and as we shall see, di erent de nitions for TOBSE lead to di erent notions of explaining the observations. De nition 1 introduces a similar distinction also as regards the temporal constraints: TOBSTC is the whole set of temporal constraints while TOBSTE can be any subset of the temporal constraints on the observations. We impose that a solution must be consistent with the constraints in TOBSTC and entail those in TOBSTE so that di erent de nitions for TOBSTE lead to di erent notions of temporally explaining the observations. We can introduce the following de nition of explanation to a temporal diagnostic problem: De nition 2 An explanation for a temporal diagnostic problem TDP= hTBML CXT CCXT TOBSE, TOBSTE TOBSTC i is a set E of abducible symbols such that: (i) E TBML CXT j= TOBSE

(ii) If TC (E ) is the set of ground temporal constraints derivable from E TBML CXT CCXT, i.e., the temporal constraints associated with the part of the model involved in the explanation E, then: (ii.1) TC (E ) TOBSTC is temporally consistent. (ii.2) TOBSTE is temporally entailed by TC (E ) The notions of temporal consistency and temporal entailment depend on the actual temporal constraint language being used2 . De nition 2, which generalizes the abductive de nition in (Console& Torasso 1991b) (see below for more comments), captures the following intuitive idea: (i) The set of assumptions E in conjunction with the model and the contextual data CXT must entail TOBSE, i.e, (a subset of) the observations this is the strong notion of explaining the observations adopted in abductive approaches to diagnosis (Console& Torasso 1991b Poole 1989). (ii) given the set TC (E ) of constraints associated with the part of model used to explain TOBSE, then (ii.1) all the temporal constra

ints on the observations (logically represented in TOBSC ) must be consistent with TC (E ) and (ii.2) the subset of temporal constraints in TOBSTE must be entailed by TC (E ). Temporal constraints on the set E of assumptions can be obtained given the constraints in the part of the model involved in the explanation and those on the observations. As regards the generalization of the atemporal definition in (Console& Torasso 1991b), the atemporal consistency requirement with respect to the observations (i.e. not predicting something which is inconsistent with what has been observed) is completely replaced by temporal consistency, including consistency with respect to negative observations: if, for example, an observable condition o is observed to be false until t, then any explanation that predicts it to be necessarily true before t can be rejected. Thus (ii.1) already includes the weak notion of explaining the observations adopted in consistency-based approaches to model-based diagnosis (Reiter 1987 de Kleer, Mackworth,& Reiter 1992). Notice that, as in (Console& Torasso 1991b), di erent choices for TOBSE lead to di erent logical de nitions of diagnosis. In particular, a lattice of de nitions can be singled out, where purely consistency-based diagnosis is one of the extremes (and corresponds to the case where TOBSE= ) and purely abductive diagnosis is the other extreme (and corresponds to the case2 Temporal consistency and entailment could be reduced to logical consistency and entailment with an appropriate axiomatization of the temporal constraint language, which is not a goal of this paper.

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

where TOBSE is the whole set of observations) moreover also all the intermediate cases (corresponding to all the other de nitions of TOBSE ) can be considered. The spectrum is extended in this paper also to the temporal dimension in the sense that di erent de nitions of TOBSTE lead to di erent notions of explaining the temporal constraints on the observations. Also in this case a lattice can be singled out: at one extreme case, where TOBSTE=, it is only required that the temporal constraints on the observations are consistent with those in the part of the model involved in the explanation. At the other extreme, where TOBSTE contains all the constraints on the observations, then all the temporal information on the observations must follow from the explanation. Thus de nition 2 points out that there are two orthogonal dimensions in the characterization of the notion of temporal diagnosis: selecting the notion of\explaining" the observations selecting the notion of\temporally explaining" the observations Actually, the two notions are not completely independent in the sense that the choice of TOBSTE depends in some sense of the choice of TOBSE . In fact, suppose that a 62 TOBSE, i.e., the explanation must only be consistent with the observation a and it is not required that a is explained abductively. In this case it is not reasonable to include tempor

al constraints on a in TOBSTE . In fact, it would be strange to impose that although the explanation must not entail (predict) the presence of a it must entail (predict) the temporal location of a, i.e., that a must be true on some interval T respecting some constraints. Thus in this sense the temporal notion of explanation depends on the logical notion of explanation being adopted. The analysis in (Console& Torasso 1991b) shows that the completeness of the model is the criterion to choose abductive over consistency-based diagnosis. In particular, since abduction can be regarded as deduction on a completed theory (Console, Theseider Dupre,& Torasso 1991), its use is recommended when the model of the system to be diagnosed is\complete" (i.e., when all the causes of the observations are included in the model). In particular, it is reasonable (and recommended) to include an observation a in the set of observations to be explained abductively in case all the causes of a are in the model. In other cases, the requirement that the explanation must entail an observation may be too restrictive and may lead to loosing relevant solutions. Similar considerations apply also for the temporal dimension: requiring that the temporal constraints on the observations are entailed is reasonable only in case the temporal constraints in the model are precise (or, better, at least as precise as those that may occur in the observations) if this is not the case, the requirement may be too restrictive and may lead to loosing relevant

solutions. Let us consider, as an example, the explanatory formula a explains b fta overlaps tb g (1) Suppose that the observation to be explained is: tb Since 10 Until 20 (2) Assuming a with the constraint ta Since 5 Until 15 (3) is intuitively a reasonable explanation, but note that (1) and (3) do not entail (2), since it would not be reasonable to predict (2) given (1) and (3) since the constraints in the model are not very precise (with respect to those in the observations). Speci cally, there is no set of assumptions that entails b( 10 20]), and then there is no abductive explanation for it. In case the temporal constraints in the model are precise enough (that is, they are such that assumptions entail information on observable states that is at least as precise as the constraints that may be available on the observations), it may make sense to require that the constraints on the observations are entailed by those in the explanation. For example, consider the following explanatory formula: a explains b fta contains tb g (4) and the observation tb Lasting AtMost 10 (5) Given (4), the assumption ta Lasting AtMost 10 is the weakest assumption that entails (5) notice that, on the other hand, the assumption ta Lasting 20 is consistent with (5) but does not entail it. Precise observations (such as tb Lasting 10) cannot be explained also in this case. In this section we analyse some of the approaches to temporal model-based diagnosis showing

how they can be cast into the spectrum of de nition introduced in the previous section. The analysis, summarized in gure 1, is not exhaustive and only aims at showing that there are approaches that t into the various alternative possibilities showed by our general characterization. Notice, moreover, that each one of the approaches in the literature deals only with some of the aspects mentioned in the introduction (i.e., temporal, dynamic, time-varying behavior). Most of the temporal extensions of consistencybased atemporal diagnosis make use of a notion of temporal explanation which is also based on consistency. This is the case, for example, of the xde system (Hamscher 1991), which deals (even if using abstract forms of

Towards a classi cation of the approaches in the literature

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

Consistency-basedLogical notion

of explanationAbduction

Temporal

ConsistencyTemporalEntailment

Notion of Temporal Explanation

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 few remarks are worth in conclusion on the computation of temporal diagnoses, which is a very complex problem (an underconstrained problem, as already noticed in (Hamscher& Davis 1984)). In (Brusoni et al. 1995) we presented an algorithm for computing diagnoses in a restricted case of our general framework, namely in the case where only one episode for each ground atom is allowed this allows us to deal only with limited forms of dynamic and time-varying behavior and thus the attention is focused on temporal non-dynamic behavior. Allen, J. 1983. Maintaining knowledge about temporal intervals. Communications of the ACM 26:832{ 843. Besnard, P., and Cordier, M. 1994. Explanatory diagnoses and their characterization by circumscription. Annals of Mathematics and Arti cial Intelligence 11(1-4):75{96. Brusoni, V. Console, L. Terenziani, P. and Theseider Dupre, D. 1995. An e cient algorithm for computing temporal abductive diagnoses. In Proc. DX 95, Sixth Int. Workshop on Principles of Diagnosis. Brusoni, V. Console, L. Terenziani, P. and Theseider Dupre, D. 1996. Characterizing temporal abductive diagnosis. Technical report, Dip. Informatica, Universita' di Torino. A short version appeared in Proc. DX 95, Sixth Int. Workshop on Principles of Diagnosis. Brusoni, V. Console, L. Pernici, B. and Terenziani, P. February 1997. Later: an e cient, general purpose manager of temporal information. IEEE Expert (to appear). Console, L., and Torasso, P. 1991a. On the cooperation between abductive and temporal reasoning in medical diagnosis. Arti cial Intelligence in Medicine 3(6):291{311. Console, L., and Torasso, P. 1991b. A spectrum of logical de nitions of model-based diagnosis. Computational Intelligence 7(3):133{141. Console, L. Portinale, L. Theseider Dupre, D. and Torasso, P. 1994. Diagnosing time-varying misbehavior: an approach based on model decomposition. Annals of Mathematics and Arti cial Intelligence 11(14):381{398. Console, L. Theseider Dupre, D. and Torasso, P. 1991. On the relationship between abduction and deduction. Journal of Logic and Computation 1(5):661{ 69

0. Davis, R. 1984. Diagnostic reasoning based on structure and behavior. Arti cial Intelligence 24(1-3):347{ 410. de Kleer, J., and Williams, B. 1987. Diagnosing multiple faults. Arti cial Intelligence 32(1):97{130.

References

de Kleer, J. Mackworth, A. and Reiter, R. 1992. Characterizing diagnoses and systems. Arti cial Intelligence 56(2{3):197{222. DeCoste, D. 1991. Dynamic across-time measurement interpretation. Arti cial Intelligence 51(1-3):273{341. Downing, K. 1992. Consistency-based diagnosis in physiological domains. In Proc. AAAI-92, 558{563. Dvorak, D., and Kuipers, B. 1989. Model-based monitoring of dynamic systems. In Proc. 11th IJCAI, 1238{1243. Friedrich, G., and Lackinger, F. 1991. Diagnosing temporal misbehaviour. In Proc. 12th IJCAI, 1116{ 1122. Genesereth, M. 1984. The use of design descriptions in automated diagnosis. Arti cial Intelligence 24(13):411{436. Guckenbiehl, T., and Schafer-Richter, G. 1990. SIDIA: Extending prediction based diagnosis to dynamic models. In Gottlob, G., and Nejdl, W., eds., Proc. Int. Workshop on Expert Systems in Engineering. Springer Verlag LNCS 462. 53{68. Hamscher, W., and Davis, R. 1984. Diagnosing circuit with state: an inherently underconstrained problem. In Proc. AAAI 84, 142{147. Hamscher, W. Console, L. and de Kleer, J., eds. 1992. Readings in Model-Based Diagnosis. Morgan Kaufmann. Hamscher, W. 1991. Modeling digital circuits for troubleshooting. Arti cial Intelligence 51(1-3):223{ 271. Lackinger, F., and Nejdl, W. 1991. Integrating modelbased monitoring and diagnosis of complex dynamic systems. In Proc. 12th IJCAI, 1123{1128. Long, W. 1983. Reasoning about state from causation and time in a medical domain. In Proc AAAI 83, 251{ 254. Nejdl, W., and Gamper, J. 1994. Harnessing the power of temporal abstractions in model-based diagnosis of dynamic systems. In Proc. 11th ECAI, 667{ 671. Ng, H. 1991. Model-based, multiple fault diagnosis of dynamic, continuous physical devices. IEEE Expert 6(6):38{43. Nokel, K. 1989. Temporal matching: Recognizing dynamic situations from discrete measurements. In Proc. 11th IJCAI, 1255{1260. Pan, J. 1984. Qualitative reasoning with deep-level mechanism models for diagnoses of mechanisms failures. In Proc. 1st IEEE Conference on AI Applications (CAIA), 295{301. Poole, D. 1989. Normality and faults in logic-based diagnosis. In Proc. 11th IJCAI, 1304{1310. Preist, C. Eshghi, K. and Bertolino, B. 1994. Consistency-based and abductive diagnoses as gen-

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

eralized stable models. Annals of Mathematics and Arti cial Intelligence 11(1-4):51{74. Reiter, R. 1987. A theory of diagnosis from rst principles. Arti cial Intelligence 32(1):57{96. ten Teije, A., and van Harmelen, F. 1994. An extended spectrum of logical de nitions of diagnosis. In Proc. 5th Int. Work. on Principles of Diagnosis, 334{ 342.

本文来源：https://www.bwwdw.com/article/j4t1.html