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

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: