Constraint-based qualitative simulation and its application to diagnosis Juan J. Alba, Jose Villar, Antonio Munoz Instituto de Investigacion Tecnologica Universidad Pontificia Comillas Alberto Aguilera, 23. 28015 Madrid (alba@iit.upco.es) phone +34 1 544 90 88 fax +34 1 549 87 31 Abstract This paper describes SIMCC, a constraint-based qualitative simulation system. SIMCC is based on Benjamin Kuipers' QSIM algorithm, but it includes new constraints, improvements in the representation of dynamic-structure systems, qualitative and quantitative information management, explicit treatment of time and a better filtering mechanism. SIMCC application in diagnosis and monitoring of industrial equipment and processes is also discussed. 1 Introduction Qualitative simulation intends to provide an approximate or abstract description of a system behaviour, that can be useful whenever an accurate and complete mathematical description is not required or possible. Qualitative models describe the structure of a system in terms of qualitative variables, (for instance, A is greater than 0, B is less than 5.7), and qualitative constraints (for instance, A increases when B decreases). Qualitative models can be applied, for instance, in medicine, when a mathematical description of the human organs is not available. It can be also applied in engineering: a qualitative model can be used to guide the initial stages of a design process, when the equipment under design is not well defined and no mathematical tools can be applied. This kind of models can be also useful in diagnosis tasks, in order to provide an efficient way of validating failure hypothesis or filtering measurements. Qualitative modelling and simulation is based on the following steps: - description of the system structure through a set of qualitative constraints and variables, - prediction of the system behaviour from the initial state and the constraints, - interpretation of the obtained qualitative evolution, and application of the result to design refinement, fault detection or other application. Different researchers have followed three main approaches to qualitative modelling: [1] presents the description of a physical system in terms of components and connections. The approach presented in [2] is based on the modelling of a system as a set of interacting processes that act on shared variables. [3] is based on the previously existing mathematical description of the system, that is treated in a qualitative way. This paper presents an introduction to QSIM as presented in [3], and describes SIMCC, a qualitative simulation system based on the Kuipers approach, including several improvements concerning filters, constraints and the management of quantitative information. The description of SIMCC will be used to present the main elements of a qualitative simulation system. The last part of the paper will discuss the application of these ideas to diagnosis problems. 2 Constraint-based qualitative simulation This section briefly describes the main ideas of constraint-based qualitative simulation, presenting the QSIM algorithm as described in [3] and [4]. Constraint-based qualitative simulation is based on: - Variables describing the system state. - A description of the system structure in terms of constraints linking variables. - The initial qualitative state of the system. The qualitative simulation process expands the initial state in order to generate all possible states for the next time point. Each of the obtained states will be further expanded in order to generate all the possible system evolutions through time. This simulation process has the following steps: - A set of possible transitions are applied to each variable, in order to determine the possible values for each variable in the next time point. - The obtained possible values are filtered, in order to discard those that do not verify the constraints. - Each set of possible values for every variable is used to generate a global interpretation, that will define a possible system state. - The global filtering is applied on global interpretations, in order to determine which of them should be further expanded. The result of this process will be an oriented tree (see figure 1) where each node represents a global qualitative state. Each path from the tree root up to a leaf will represent a feasible system evolution. The number of different feasible system evolutions will depend on the amount of information contained in the qualitative formulation of the system description. Qualitative descriptions are usually less informative than their quantitative counterparts, therefore several possible behaviours can be generated. [Picture] Figure 1. The system states tree. The terms used in this figure will be explained in the following sections 2.1 Qualitative variables Physical systems will be modelled using time dependent real variables such as f: f: [a,b] -> R* being R*=[-inf, +inf] . Both the domain ([a,b]) and the range of f will be closed intervals. Kuipers' algorithm is able to manage functions with the following features: - f is continuous in [a, b]. - f is continuously differentiable in ]a, b[. - f has a finite number of critical points (where the derivative is zero) in any bounded interval. - Derivative values in the endpoints of the domain interval are defined as: f'(a) = lim(t->a+) f'(t) f'(b) = lim(t->b-) f'(t) Qualitative simulation is based on the qualitative description of variables, i.e., on the discretization of their values. Each variable can have a finite number of qualitative values and has an ordered set of landmarks, being each qualitative value represented by an ordered couple of consecutive or equal landmarks, as in x = (xi, xi+1) <-> xi is in ]xi, xi+1[ x = (xi, xi) <-> x = xi Any variable will always be between two consecutive landmarks or will be equal to one landmark. Landmarks represent notorious values, therefore the landmarks set will contain: - 0 if it is in the function range. - f(a) and f(b). - The value of f(t) for each critical point. - Any other additional distinguished value.. 2.2 Time as an independent discrete variable The goal of qualitative simulation is the description of the system behaviour through time. Therefore, time will be the independent variable, will also be treated as a discrete variable and will be divided into time intervals. The system description is constant while in a time interval, and can only change when a time point (the limit between two intervals) is reached. The system evolution will be described as a sequence of transitions from a time interval (where the system stays in the same qualitative state) to a distinguished time point (when a variable reaches a landmark, something changes in the qualitative state), then to the next time interval and so. Both time intervals and distinguished time points will be referred to as qualitative time points, and will be represented by a couple of consecutive or equal distinguished time points. t = (ti, ti+1) <-> t is in ]ti, ti+1[ t = (ti, ti) <-> t = ti. Note that this management of time can be used to order the obtained system states, but does not provide information concerning time intervals duration, because distinguished time points are only ordered symbolic values not representing numerical values. However, landmarks are actual numerical values that can be reached by functions. 2.3 Qualitative states The qualitative state of a function fi: fi: [a,b] -> R* with landmarks c0 < c1 < ... < ck in the qualitative time point (tj, tk) being k=j or k=j+1 is defined as: QS(fi, (tj, tk)) = fi(cm, cn, dir) where k=j or k=j+1, n=m or n=m+1, being dir the qualitative derivative: dir = DEC if f'(tj,tk) < 0 dir = CTE if f'(tj,tk) = 0 dir = CRE if f'(tj,tk) > 0 The qualitative state of a system is defined as the set of the qualitative states of all its functions. Note that the qualitative derivative is also discretized, but the number of its possible values is always three. On the other hand, the number of possible qualitative values of i can change as new landmarks are added. Whenever a variable is between two landmarks, it will be monotonous (i.e., its qualitative derivative will be constant in the interval defined by those landmarks). If the variable is between two landmarks and its qualitative derivative is CTE, then it will be equal to a symbolic value between both landmarks. 2.4 Qualitative constraints The structure of the system being modelled will be represented by means of a set of qualitative constraints among the previously defined variables. The simulation process will assign behaviours to the variables, and the constraints will be used to detect and delete the unfeasible combinations of behaviours. Constraints are the qualitative counterpart of differential equations. The complete set of constraints proposed in [3] is the following: ADD(f, g, h) <-> f(t) = g(t) + h(t) MULT(f, g, h) <-> f(t) = g(t) * h(t) MINUS(f, g) <-> f(t) = -g(t) DERIV(f,g) <-> f(t) = d(g(t))/dt M+(f, g) <-> f(t) is an increasing function of g(t) M-(f,g) <-> f(t) is a decreasing function of g(t) (note that the order of arguments is not the same as in [3]). Constraints can have associated sets of corresponding values: M+(f, g); VCOR( (0, 0) (2, 1) ) <-> <-> f is an increasing function of g and for all t, g(t) = 0 -> f(t) = 0, g(t) = 1 -> f(t) = 2 2.5 Transitions Transitions are used to obtain the set of possible qualitative states of a variable in a qualitative time point, given its qualitative state in the previous time point. They are base in the hypothesis stated in 2.1. There are two kinds of transitions: - P transitions: a P transition is an ordered couple of consecutive qualitative states, QS(f, (ti, ti)) -> QS(f, (ti, ti+1)) where the first state corresponds to a distinguished time point, and the second state corresponds to a time interval. P transitions QS(f, (ti, ti)) QS(f, (ti, ti + 1)) P1 (cj, cj, CTE) (cj, cj, CTE) P2 (cj, cj, CTE) (cj, cj+1, CRE) P3 (cj, cj, CTE) (cj-1, cj, DEC) P4 (cj, cj, CRE) (cj, cj+1, CRE) P5 (cj, cj+1, CRE) (cj, cj+1, CRE) P6 (cj, cj, DEC) (cj-1, cj, DEC) P7 (cj, cj+1, DEC) (cj, cj+1, CRE) - I transitions: an I transition is an ordered couple of qualitative sates QS(f, (ti, ti+1)) -> QS(f, (ti+1, ti+1)) where the first state corresponds to a time interval, and the second one corresponds to a distinguished time point I transitions QS(f, (ti, ti+1)) QS(f, (ti+1, ti+1)) I1 (cj, cj, CTE) (cj, cj, CTE) I2 (cj, cj+1, CRE) (cj+1, cj+1, CTE) I3 (cj, cj+1, CRE) (cj+1, cj+1, CRE) I4 (cj, cj+1, CRE) (cJ, cJ+1, CRE) I8 (cj, cj+1, CRE) (c*, c*, CTE) I5 (cj, cj+1, DEC) (cj, cj, CTE) I6 (cj, cj+1, DEC) (cj, cj, DEC) I7 (cj, cj+1, DEC) (cj, cj+1, DEC) I9 (cj, cj+1, DEC) (c*, c*, CTE) Note that in transitions I8 and I9 the function f reaches c* with its derivative equal to 0, being c* a new landmark such that cj < c* < cj+1 2.6 Qualitative differential equations If a system can be described through a set of ordinary differential equations (with no partial derivatives), then it can be expressed as a set of qualitative constraints, as in the following example: Given the equation: f(dny/dtn) + ... + a1f(dy/dt) + a0y = f(t) being ai = ai(t) and y = y(t) , the equation can be transformed into a system by doing x0 = y, x1 = f(dy/dt), ... , xn-1 = f(dn-1y/dtn-1), f(dx0/dt) = x1 f(dx1/dt) = x2 ... f(dxn-1/dt) = -a0x0 - a1x1 - ... - an-1xn-1 + f(t) and the qualitative formulation of this system is the following: DER(x1, x0) DER(x2, x1) ... DER(xn-1, xn-2) MUL(p0, a0, x0) MUL(p1, a1, x1) ... MUL(pn-1, an-1, xn-1) ADD(s0, p0, p1) ADD(s1, s0, p2) ... ADD(sn-2, sn-3, pn-1) SUB(sn-1, f, sn-2) DER(xn, xn-1) SUB(ZERO, xn, sn-1) where: x0 is y(t). pi are auxiliary functions for the qualitative products. si are auxiliary functions for the qualitative additions. Zero is a function equal to 0. 2.7 Consistency filtering After obtaining the possible transitions for each variable, consistency filtering aims at generating, for each constraint, the set of consistent transitions lists for all the argument variables in the constraint. Let REST(f1 , f2) be a constraint and y (T1, T2) a transitions list associated to REST, T1(f1): (cinf1, csup1, dir1) -> (cinf1*, csup1*, dir1*) T2(f2): (cinf2,csup2,dir2) -> (cinf2*,csup2*,dir2*) Transitions list (T1,T2) is consistent with constraint REST if and only if the successor qualitative states generated by (T1,T2) agree with REST. For instance, given - variables f(0, 2, +ě), g(0, 1, +ě) - constraint M+(f, g); VCOR((0, 0) (2, 1)) - initial state in a time interval ptc, ptc = (0, 1): f(0, 2, CRE), g(0, 1, CRE) - and transitions list (I8, I2) being I8: (cj, cj+1, CRE) -> (cj, cj+1, CTE) I2:(cj, cj+1, CRE) -> (cj+1, cj+1, CTE) successor qualitative states in time point (1, 1) are: f(0, 2, CTE) (after applying I8) g(1, 1, CTE) (after applying I2) and the consistency filtering will provide the following results: - qualitative derivatives are consistent: both variables are constant in the successor state, and that is consistent with M+. - qualitative values: g reaches the value 1 in the qualitative time point (1, 1), while f does not reach the corresponding value 2, therefore both transitions are inconsistent. 2.8 Global filtering and interpretation (Note that the terminology in this section is not completely equal to the one used in [3]. Some changes have been introduced in order to ensure the consistency with the description of SIMCC in the next section). A global interpretation is the assignment of a transition to every variable in the system. Consistency filtering provides lists of transitions that are consistent with each individual constraint. Global filtering obtains sequences of transitions lists making sure that the different transitions lists associated to different constraints assign the same transitions to the same variables when they appear in different constraints. If this is not the case for any of the transitions list, it will be discarded. For instance, let S be a system with three variables, X, Y y Z, and three constraints R0, R1, R2, where the following lists of transitions have been selected by the consistency filtering procedure: R0(X, Y) R1(Y, Z) R2(X, Z) (P1, P2) (P1, P1) (P1, P3) (P2, P3) (P2, P3) (P2, P1) The first transitions list of R0 will assign P2 to variable Y. The first transitions list of R1 will assign P1 to the same variable. Therefore, these two transitions lists are not compatible. In this case, the only global interpretation will be (P1,P2,P3) (corresponding to (X ,Y ,Z)). After obtaining global interpretations that will correspond to feasible qualitative states, the algorithm has to select those that should not be further expanded. A state will be discarded if it corresponds to a no change situation, a periodical behaviour or a divergent behaviour (see section 3.9). 3 The SIMCC algorithm The QSIM algorithm presented in section 2 and described in detail in [3] has some significant problems: - Quantitative information, usually useful even in qualitative problems, is not paid sufficient attention. - Dynamic structures (systems whose structure can change through time) are not easily represented. - Time is not explicitly treated. - Lack of certain interesting constraints. The algorithm that will be described in section 3, named SIMCC (the name stands for the Spanish initials of Qualitative Simulation in C) is intended to provide solutions to the limitations mentioned above. This algorithm basically uses the QSIM approach, with some additional elements and improvements. A detailed description of SIMCC may be found in [5] and [6] or [7]. SIMCC has been written in the C programming language on a personal computer (QSIM was written in Lisp). It has 6800 lines of code. There are to auxiliary applications: SCMENU (2200 lines) is a menu-based environment for using SIMCC, SCGRAF (1400 lines) can generate qualitative graphical outputs similar to the ones presented in [3]. 3.1 The management of time Quantitative time information can be obtained by defining time as a new system variable such that T=T(t), with its associated list of landmarks that will store interesting numerical values of time. Therefore, T will be a function of time t, being the former the "actual" time, including relevant quantitative information, and the latter the "Kuipers" time, purely symbolic and corresponding to the sequence of qualitative time points. Therefore, let (0,5,+ě) be the landmarks of T, a possible evolution of T could be the following: qualitative T time point (t0, t0) (0, 0) (t0, t1) (0, 5) (t1, t1) (0, 5) (t1, t2) (0, 5) (t2, t2) (5, 5) (t2, t3) (5, +inf) (t3, t3) (+inf, +inf) where the following quantitative information about qualitative time points is encapsulated: t0 = 0 t1 _ ]0, 5[ t2 = 5 t3 = +inf 3.2 Elements of a constraint A constraint must have the following elements: - A predicate, that is the constraint name. - A list of argument variables, that are linked by the predicate. - The constraint validity domain, a list of intervals (delimited by landmarks) corresponding to each of the argument variables that indicate when the constraint can be applied (a constraint can be applied if and only if each of the argument variables is inside its corresponding domain). This makes possible to enable or disable constraints as the system evolves, and to model systems with varying structures. A constraint can also have additional attributes: - A set of corresponding values,(vc0, vc1,..., vcn-1) for a n argument variables constraint (f0, f1,..., fn-1) is a list of n landmarks vci, (one for each fi) such that if all the n-1 independent variables (f1,..., fn-1) reach their associated landmarks (vc1,..., vcn-1) then the dependent variable f0 will also reach vc0. Note that not all the constraints can have an associated list of corresponding values. - A parameters list, that can modify the constraint 3.3 SIMCC constraints Arithmetic constraints mainly link values, while qualitative constraints are mainly used to link qualitative derivatives. SIMCC arithmetic constraints are the following: Name Meaning Parameters Corresp. val. ADD(F0, F1, F2) F0 = F1 + F2 none accepted SUB(F0, F1, F2) F0 = F1 - F2 none accepted MUL(F0, F1, F2) F0 = F1F2 none accepted OPP(F0, F1) F0 = -F1 none accepted EXP(F0, F1) F0 = (eP0F1) + P1 P0, P1 accepted LN(F0, F1) F0 = Ln (P0F1 + P1) P0, P1 accepted SIN(F0, F1) F0 = sin(P0F1 + P1) P0, P1 accepted COS(F0, F1) F0 = cos(P0F1 + P1) P0, P1 accepted POL(F0, F1) F0= P0 + P1F1 +...+ Pn*F1n P0,P1,...,Pn accepted All the landmarks in the initial state must be numerical values. Therefore, arithmetic constraints do not need corresponding values in the initial state, since SIMCC will automatically relate the involved landmarks. However, during SIMCC execution, symbolic landmarks can appear because of transitions I8 and I9. Therefore SIMCC will create and maintain lists of corresponding values associated to symbolic landmarks. The qualitative constraints are the following: Name Meaning Parameters Corr. val. MPL(F0, F1) sign (f(dF1;dt)) = sign (f(dF0;dt)) none accepted MNG(F0, F1) sign (f(dF1;dt)) = sign (-f(dF0;dt)) none accepted CTE(F0) f(dF0;dt) = 0 none not accepted TIM(F0) F0 is the qualitative expression of t none not accepted DER(F0, F1) F0 = f(dF1;dt) none not accepted A known constant will be a function with only one value in its landmarks list. An unknown constant will be defined as: - a variable with (0, +inf) as landmarks list and (0, +inf, CTE) as initial state, - the CTE constraint with no constraint validity domain (i.e., the constraint will be applicable for all t). 3.4 Modelling a system using SIMCC A SIMCC model of a system must have the following components: - Variables declarations: VARIABLE_NAME (c1, c2,..., cn) being (c1, c2,..., cn) the initial ordered landmarks list. All the landmarks will be numerical in the current SIMCC version. The variable range will be [c1,cn]. The landmarks list may have as many landmarks as desired. This will increase results accuracy, but will make slower the simulation process. On the other hand, the bigger the number of landmarks, the bigger the number of alternative system behaviours that can be generated. A landmark may be any numerical value, + inf, - inf, or aPI/b. - Constraints declarations: The most general declaration will be as follows, CONSTRAINT_TYPE(farg0, farg1,..., fargm) PARM (P0, P1,..., Pt), the parameters list, DOMI (f0[dominf0, domsupf0],...), the constraint validity domain, VCOR ((vcor00, vcor01,..., vcor0m), ...), the corresponding values list. - Initial state of each variable: fi (cinffi, csupfi, dir) cinffi and csupfi must be consecutive or equal members of the fi landmarks list. The initial state may correspond to a distinguished time point or a time interval. This must be clearly stated, since this fact will determine the appropriate transitions (I or P). 3.5 Initial state filtering The initial state will be consistent if and only if all the active constraints hold for the initial values of the argument variables. A constraint will be active if its argument variables are inside the constraint validity domain. The consistency filtering mechanism (that will be described later) will be also used for this purpose. Since consistency filtering is based on transitions, initial state filtering will be implemented through the use of a new type of transitions (type O), that generate a successor state that is equal to the initial state. If the initial state is consistent, new values must be added to each of the landmarks lists, in order to gather all the information that may be needed for successor states. The landmark 0 will always be added, and for each constraint, the appropriate values will be included. For instance, if the constraint ADD(f0, f1, f2) is present, the opposites of f2 landmarks will be added to f1 landmarks list and the opposites of f1 landmarks will be added to f2 landmarks list. More details on this can be found in [7]. 3.6 Selection of possible transitions After the initial state filtering, SIMCC will carry out the following tasks: - To determine which are the applicable transitions. I transitions will be selected if the current qualitative time point is an interval, P transitions will be selected otherwise. - To apply to each variable state the appropriate transitions, in order to generate its possible successor states. The application of transitions must take into account the variables ranges (for instance, P2, P3, P4 and P6 could take a variable out of its range if applied close to the endpoints of the range interval). A successor state of the system is generated through the application of n transitions to the n variables in the system. Since the maximum number of transitions per variable is 4, the maximum number of possible successor states is n4. Filtering is intended to limit this number. Filtering will be carried out in three steps: - Consistency filtering: It will filter the applicable transitions for each variable taking into account the constraints (disregarding their validity domains). It is similar to Kuipers' filtering but the individual treatment of constraints has been modified. For each constraint, it will generate all the lists of transitions that can be applied to its argument variables. - Global filtering: The transitions lists corresponding to all the constraints must be merged, in order to obtain the possible successor states. If several constraints (that are active taking into account their domains) share an argument variable, all of them should assign the same transition to that variable. Kuipers' global filtering has been modified in order to consider the constraints domain. - Global interpretation: It corresponds to Kuipers' global filtering, introducing some modifications in divergences treatment. 3.7 Consistency filtering The starting point is the set of possible transitions for each variable. The filtering process has the following stages: - For each constraint, all possible transitions for its argument variables are combined, and a set of transitions lists is obtained. - For each transitions list and for each list of constraint arguments, a set of variables successor states is generated. - Each list of possible successor states is checked again its corresponding constraint. If it is not compatible, the list is discarded. Arithmetic constraints filtering is based on the generation of a theoretical interval (]vi0infc, vi0supc[) derived from the successor states of the independent variables. This theoretical interval must be overlapped with successor state of the dependent variable, otherwise the transitions list can be considered inconsistent. Given a three argument arithmetic constraint, f0 = f1 # f2 being "#" any arithmetic operator, and being the successor states for a given transitions list the following: f0(vi0inf, vi0sup, dir0) f1(vi1inf, vi1sup, dir1) f2(vi2inf, vi2sup, dir2) the theoretical interval will be obtained as follows, ]vi1inf, vi1sup[ # ]vi2inf, vi2sup[ = ]vi0infc, vi0supc[ and the transitions list will be consistent with the constraint if: ]vi0inf, vi0sup[ intersecton ]vi0infc, vi0supc[ /= {} The interval defined by vi0infc and vi0supc is obtained by the retvi algorithm (see [7]), given given vi1inf, vi1sup, dir1, vi2inf, vi2sup and dir2. vi0infc and vi0supc will be obtained by operating f1 and f2 landmarks in the appropriate direction up to obtain vi0infc and vi0supc such that are members of f0 landmarks list. This operation is obvious if the landmarks in f1 and f2 are numeric, and makes use of corresponding values if symbolic landmarks are involved. The enclosed table presents a complete description of the consistency filtering of constraint ADD(f0, f1, f2), being f0(vi0inf, vi0sup, dir0) f1(vi1inf,vi1sup,dir1) f2(vi2inf,vi2sup,dir2) the candidate successor states for each argument variable. Name Qualitative derivatives Inconsistent if.... ADD(f0,f1,f2) (dir1=CRE,dir2=CRE and dir0/=CRE) or (dir1=DEC, dir2=DEC and dir0/=DEC) or (dir1=CTE and dir2/=dir0) or (dir2=CTE and dir1/=dir0) Theoretical interval vi0supc = retvi(vi1sup,cre,vi2sup,cre) vi0infc = retvi(vi1inf,dec,vi2inf,dec) Always consistent if... (f1=-inf or f2=+inf) or (f1=+inf or f2=-inf) More details can be found in [6] or [7]. The following table presents the filtering related to qualitative constraints. Name Qualitative derivatives. Inconsistent if... DER(f0, f1) (dir1=CTE and (vi0inf/=0 or vi0sup/=0)) or (dir1=CRE and (vi0inf=vi0sup=0 or vi0inf<0)) or (dir1=DEC and (vi0inf=vi0sup=0 or vi0sup>0)) MNG(f0, f1) (dir1=CTE and dir0/=CTE) or (dir1=CRE and dir0/=DEC) or (dir1=DEC and dir0/=CRE) Intervals inconsistency vi0infc: f0 landmark corresponding to the f1 landmark closer and greater or equal to v1sup or the smallest f0 landmark vi0supc: f0 landmark corresponding to the f1 landmark closer and lesser or equal to v1inf or the greatest f0 landmark MPL(f0, f1) dir1/=dir0 Intervals inconsistency vi0infc: f0 landmark corresponding to the f1 landmark closer and lesser or equal to v1inf or the smallest f0 landmark vi0supc: f0 landmark corresponding to the f1 landmark closer and greater or equal to v1sup or the greatest f0 landmark CTE(f0) dir0/=CTE TIM(f0) dir0/= CRE 3.8 Global filtering Global filtering provides a complete assignment of transitions for all the variables in the system, by adequately merging the transitions lists corresponding to each constraint. Each complete assignment will generate a possible successor state. Global filtering must take into account all the constraints and all the variables, since the domain of a given constraint may depend on variables that are not among its arguments. The algorithm proposed by Kuipers in [3] does not take into account the constraints domains. The global filtering process is based on a depth first search procedure that is described in [7]. 3.9 Global interpretation A complete transitions assignment after global filtering represents a mathematically feasible state. However, global interpretation intends to select states that deserve further expansion or have some interesting feature. The possible global interpretations are the following: - No change situation: all the transitions in the assignment are I1, I4 or I7, and the generated successor state is equal to the initial one and may be discarded (note that this does not correspond to periodical behaviour). - Periodical behaviour: when all the variable states are repeated in one path in the states tree and no changes are expected in the system structure. - Divergent behaviour: a simulated behaviour is divergent whenever any of the system variables (excluded time) reaches +ě or -ě. Three interpretations are possible: - assume that no variable can reach ě and discard that interpretation. - assume that ě corresponds to a system anomaly (such as a component fatal failure). Therefore, this interpretation could be accepted but no further expanded (since the system structure will be different because of the failure). - accept the divergence and continue simulation up to a second divergence. After that, consistency filtering is not possible. This would correspond to the study of a limit. Global interpretation must take into account that, if TIM constraint is being used, any acceptable branch in the states tree must lead to the end of the time range. 4 SIMCC contributions The SIMCC algorithm included several improvements over the QSIM system as described in [3]. Most of QSIM drawbacks addressed by SIMCC have been described in [8]. - Initial state filtering, introduced in SIMCC, is the basis of qualitative supervision, that will be described later. This filtering is based in the same filtering algorithms that are used in state expansion, no additional procedures are required. - New constraints have been added to the initial set proposed by Kuipers. New arithmetic constraints and the use of parameters lists permit to take advantage of the available quantitative information, and make the qualitative models more compact. However, the consistency filtering have been improved in order to deal with these new requirements. - Explicit time management was not considered by QSIM. Generated states were ordered, but variables were not explicitly related to time. The use of time in global filtering can also help to prune the states tree (see section 3.9). - Quantitative information management: QSIM could lead to results like "2 + 2 = a positive quantity greater than 2". SIMCC is able to take advantage of quantitative information through the use of the hybrid arithmetic described in section 3.7, that is able to deal with numerical and symbolic intervals. - The lack of dynamic structures in QSIM (reported, for instance, in [9]) has been solved through the use of validity domains for constraints. Examples of the interest of this possibility can be found in [5]. - A new filtering procedure has been required by the improvements mentioned above. The new interval algebra described in 3.7 was not present in [3], and the use of validity domains for constraints require a new structure for the global filtering mechanism. 5 Qualitative simulation and fault diagnosis Current technology in artificial intelligence applications in monitoring and diagnosis of industrial systems is usually based in the following elements: (see, for instance, [9], [10] or [11]): - Mathematical models of the system being supervised, corresponding to normal or failure situations, that can be used to predict its behaviour given input data. - Statistical tools that are required in order to analyze differences between measures and model predictions. - Knowledge based systems that can interpret the detected differences and provide appropriate diagnosis. Nevertheless, this approach usually presents significant drawbacks: - Mathematical models are usually difficult to develop and test, and their parameters can be difficult to estimate. - There is a significant gap between the knowledge used in failure detection (that is in the basis of the models) and the diagnosis knowledge, that can be encoded using well known knowledge representation techniques. - Mathematical models and diagnosis knowledge bases are usually system-specific, very difficult to apply in other systems. - The knowledge acquisition task required for this approach is quite time consuming and difficult to systematize. The use of qualitative models has been suggested as an answer to these problems. Sometimes (see [12] or [13]) qualitative models have been proposed as sources of examples that can be treated by learning algorithms such ID3. Other authors ([14], [15] or [16]) propose the direct usage of qualitative models in the monitoring or troubleshooting process. This section presents two possible approaches to diagnosis based on qualitative models. The first approach is based on the use of a failure library, storing qualitative models of failures. The second approach is based on the normal state qualitative model, and makes use of the initial state filtering to analyze measures. 5.1 Diagnosis based on a failure library Figure 2 shows an outline of this approach. Qualitative simulation is used to generate a failure library that will store qualitative descriptions of the system behaviour under the most frequent failure conditions. This is the main drawback of this approach, since it requires the development of a qualitative model for each failure. Nevertheless, some authors ([17]) have proposed the automatic generation of failure models through the modification of a basic model (however, this is only valid if failures do not significantly modify the structure of the system). The diagnosis process will be based on the discretization of system measures (conversion of actual values into qualitative information) and its comparison to the information in the failure library. This comparison is easier if it is carried out using qualitative information, since the same failure can have different quantitative descriptions that correspond to the same qualitative situation. However, unaccuracies inherent to qualitative modelling must be taken into account. [Picture] Figure 2. Diagnosis based on a failure library If the observed system behaviour corresponds to one of the failure models in the library, the identification will be immediate. If the comparison is not clear enough, new measures will be requested in order to make the situation clearer. An important task in this process is the so-called qualitative conversion. 5.2 Qualitative conversion of measures This conversion requires a list of numeric landmarks for each monitored variable. The qualitative state of a variable F, with associated landmarks (vi1, vi2,..., vin), in the qualitative time point (ptdinf, ptdsup), will be represented as: QS(F, (ptdinf, ptdsup)) = F(viinf, visup, dir) The qualitative conversion is the determination of viinf, visup and dir. The values viinf and visup will be the landmarks that are the closest to the observed value, MED. If MED < vi1 or MED > vin, there is a failure situation or an error in the model. The qualitative derivative of F, dir, will be determined through the numerical computation of the derivative of MED after several consecutive samples. On the other hand, any variable that is in the qualitative model and is not being monitored will be estimated from measured data. 5.3 Qualitative supervision This approach is represented in figure 3. There is only one qualitative model, that corresponds to normal behaviour. This approach is based in the following hypothesis: every system behaviour that is not consistent with the model constraints is caused by a failure. Qualitative supervision is also based on qualitative conversion. This operation will provide a qualitative state for the system, that can be filtered as the initial state of the simulation was filtered. If any of the active constraints is violated, there is a failure. Failure identification is based on the violated constraints. The most appropriate model should have one set of constraints for each component in the system, therefore violations can be associated to malfunctions. If the failure identification is not clear, new measures will be requested. [Picture] Figure 3. Qualitative supervision. A mixed approach can be also envisaged. It could make use of qualitative supervision for failure detection and initial failure hypothesis and could carry out failure identification by means of the failure library, if the information derived from the violated constraints is not enough. 6 Conclusions and further development Expert systems are usually based on expert knowledge, frequently intuitive and derived from experience. The knowledge acquisition process is a time consuming task, where inconsistencies and errors can be frequently found. Qualitative simulation, on the other hand, is based on a model that can be derived from the detailed study of the system and the application of its constituent physical laws. Its application to diagnosis tasks seems to be more systematic. This technique can be also used to model systems that are only partially known. 6.1 Qualitative simulation advantages Qualitative simulation provides qualitative information, that is usually easier to understand and use than lists of numbers. It can be also useful to obtain a first analysis of problems that will be later approached using numeric techniques, therefore reducing the search space and the computational load. On the other hand, qualitative simulation makes possible to study the evolution of a partially known system. Mathematical models are not always possible or satisfactory. Sometimes, they do not exist (like in certain medical applications). The involved parameters can be extremely difficult to estimate, or the mathematical structure of the model can be too complex. In these cases, qualitative simulation can be a solution. The qualitative model can provide information about variables that cannot be observed, because of technical or economical reasons. Diagnosis based on qualitative models of failures can take into account the future failure evolution. This can be used to provide a more useful information on the failure, and to assess the different maintenance strategies. On the other hand, qualitative models are flexible enough to be modified through the addition of new constraints. Last but not least, qualitative simulation intends to be a step further in the formalization of common sense reasoning that can be implemented in a computer, and therefore a step further in the development of intelligent systems. 6.2 Qualitative simulation drawbacks The most important disadvantage of this approach is the generation of a tree of possible behaviours, instead of one single description of the system evolution. This is caused by the lack of information in the qualitative formulation of a problem, and can lead to computational unefficiencies. This problem can be addressed through the use of additional equations, that would be redundant in a quantitative model but are useful in a qualitative formulation. An alternative solution is the use of domain specific knowledge, useful to prune the states tree. 6.3 Further development Efficient filtering methods are the most important goal of SIMCC improvement. Constraint-guided search algorithms, such as relaxation labelling ([18], [19]) could be used for this purpose. The basic problem in SIMCC the assignment of transitions to functions, and this could be formulated as the assignment of values to discrete variables, as in the relaxation labelling problem. SIMCC could be also improved through the addition of discrete functions (such as the ones used in electronic circuits). These new functions do not verify the hypothesis in section 2.1, therefore they would require their own transitions. No new landmarks would be added, state changes would only correspond to distinguished time points (I transitions) and new constraints could be required (such as AND, OR, etc). New constraints like "greater than" or "less than" could make easier to model certain systems. Last but not least, constraints involving only corresponding values could be also useful. References [12] I. Bratko et al., Automatic synthesis and compression of cardiological knowledge. Machine Intelligence 11, 1988. [9] B. Bredeweg, B. Wielinga. Integrating qualitative reasoning approaches. ECAI-88 [1] J. De Kleer, J. S. Brown, A qualitative physics based on confluences. Artificial Intelligence, 24, 1984. [2] K. D. Forbus, Qualitative process theory. Artificial Intelligence, 24, 1984. [18] R.A. Hummel, S.W. Zucker, On the foundations of relaxation labeling processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-5, No. 3, mayo 1983. [8] R. Janowsky. An introduction to QSIM and qualitative simulation. Artificial Intelligence in Engineering, 1987, Vol. 2, No. 2. [3] B. Kuipers. Qualitative simulation. Artificial Intelligence, 24. 1986. [4] B. Kuipers. Qualitative simulation as causal explanation. IEEE Transactions on Systems, Man and Cybernetics, vol SMC-1.7, n§ 3, may-june 1987. [14] J.T. Malin et al., Use of qualitative models in discrete event simulation to analyze malfunctions in processing systems. in Artificial Intelligence in Process Engineering, [11] [11] M.L. Mavrovouniotis, editor. Artificial Intelligence in process engineering. Academic Press, 1990 [5] A. Munoz. Desarrollo informatico de un simulador cualitativo basado en restricciones. Estudio de su aplicaci˘n al diagn˘stico. Proyecto Fin de Carrera, ETSII Universidad Pontificia Comillas, 1991 [13] D.A. Pearce, The induction of fault diagnosis systems from qualitative models, Workshop on artificial intelligence intelligence applications for space projects, ESA/ESTEC, 1988. [15] S.H. Rich, V. Venkatasubramanian, Model-based reasoning in diagnostic expert systems for chemical process plants, Computers in Chemical Engineering, Vol. 11, No. 2, 1987 [9] G. Saucier, A. Ambler, M.A. Breuer, editors. Knowledge based systems for test and diagnosis. North-Holland, 1989. [16] T.F. Thompson, W.J. Clancey, A qualitative modeling shell for process diagnosis, IEEE Software, march 1986. [19] C. Torras, Relaxation and neural learning: points of convergence and divergence. Journal of Parallel and distributed computing, april 1988. [10] S.G. Tzafestas, editor. Knowledge-based system diagnosis, supervision and control. Plenum Press, 1989. [6] J. Villar. Desarrollo te˘rico de un simulador cualitativo basado en restricciones. Aplicacion informatica al diagnostico. Proyecto Fin de Carrera, ETSII Universidad Pontificia Comillas, 1991 [7] A. Munoz, J. Villar, J.J. Alba. SIMCC: Simulador Cualitative basado en restricciones. Informe Interno IIT-91-013, 1991. [17] Q. Shen, R. Leitch. Qualitative model based diagnosis of continuous dynamic systems. Submitted to the First International Conference on Intelligent Systems Engineering. 1992.