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

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