A spectrum of de nitions for temporal model-based diagnosis.(5)

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.