• MONET 05

Testo completo

(1)MONET•05 2nd MONET Workshop on Model-Based Systems @IJCAI-05 Edinburgh, 30 July 2005. Notes edited by. Claudia Picardi Paulo Bretas Salles Franz Wotawa.

(2) Edinburgh, July 30th 2005. 2nd Workshop on Model-Based Systems. Foreword Model-Based Reasoning (MBR) is a methodology adopted to describe various kinds of systems (e.g. biological and medical systems, engineered artifacts in technical domains, cognitive processes and capabilities, software, environment) for many different tasks (e.g. simulation, diagnosis, planning, training, control, debugging). However, experiences are not often exchanged across different areas, because existing workshops are mainly system- and/or task-oriented. This workshop is thus first of all aimed at sharing modeling problems, experiences and solutions, needs and use-cases, across different areas of research and application. Moreover, standardization of modeling languages and methodologies is still an open issue within the model-based community. The lack of a standardization is the bottleneck that prevents a wide use of MBSs. In this sense the workshop hopes to stand as a starting point of discussion on the exchange, reuse and easier development of models. Between 1997 and 2005 the MONET Excellence Network, funded by the European Union, has brought together researchers to discuss on these topics in order to find common frameworks and solutions. It has fostered sharing and exchange of both practical and theoretical knowledge, creating a community of people. The goals of MONET are still of the utmost importance; the 2nd MONET Workshop aims thus at being a "live" edition of MONET by allowing the sharing of modeling problems, experiences and solutions across different areas. MONET-05 is also a chance at enlarging the community, by gathering it in a renowned intercontinental context such as IJCAI. We first of all want to thank all the authors that provided the material for this workshop, paving the way for what we hope will be a successful discussion. We thank all the members of the Program Committee for the efforts spent in making this workshop possible. We also sincerely thank all the people in the MONET Network that offered support in organizing the workshop. Last but not least, we thank Carlos Guestrin, the IJCAI workshop chair, for taking care of the organization details and for always providing help when we needed it.. The Workshop Program Chairs: Claudia Picardi Paulo Bretas Salles Franz Wotawa. 2.

(3) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005. Workshop Program Chairs Claudia Picardi Paulo Bretas Salles Franz Wotawa. Università di Torino Universidade de Brasilia Technische Universität Graz. Italy Brasil Austria. Workshop Program Committee Bert Bredeweg Irène Grosclaude Honghai Liu Michael Neumann Yannick Pencolé Chris J. Price Peter Struss Gianluca Torta Yuhong Yan Cecilia Zanni. Universiteit van Amsterdam France Telecom University of Aberdeen Justus-Liebig Universität Giessen Australian National University University of Wales Technische Universität München Università di Torino National Research Council of Canada LSIS-CNRS. The Netherlands France United Kingdom Germany Australia United Kingdom Germany Italy Canada France. 3.

(4) Edinburgh, July 30th 2005. 2nd Workshop on Model-Based Systems. List of Papers G. Calderon-Espinoza, J. Armengol. Dynamical Diagnosis with Interval Analytical Redundancy Relations.. pp. 5-10. R. Ceballos, M.T. Gomez-Lopez, R.M. Gasca, C. Del Valle. An efficient model integration of DX and FDI techniques to improve the automatic determination of minimal diagnosis.. pp. 11-16. M. Domingo, N. Agell, X. Parra, M. Sánchez. A System for Predicting Citizens' Satisfaction Using Qualitative Information.. pp. 17-22. M. Esser, P. Struss. Model-based Test Generation for Embedded Software.. pp. 23-29. G. Friedrich, K. Shchekotykhin. Diagnosis of Description Logic Knowledge Bases.. pp. 30-35. B. Guerraz, C. Dousson. From a Timed Fault Model to Temporal Fault Signatures.. pp. 36-41. G. Lamperti, M. Zanella. On Processing Temporal Observations in Model-Based Reasoning.. pp. 42-47. I. Lopez-Arevalo, A. Rodriguez-Martinez, A. Aldea, R. Banares-Alcantara, L. Jimenez. Redesign Support Framework based on Hierarchical Multiple Models.. pp. 48-53. B. Peischl, S. Soomro, Franz Wotawa. Lightweight Debugging Techniques.. pp. 54-59. C.J. Price, L. Travé-Massuyès, R. Milne, L. Ironi, B. Bredeweg, M.H. Lee, P. Struss, N. Snooke, P. Lucas, M. Cavazza. Visions for Model-based Reasoning. pp. 60-65. P. Salles, B. Bredeweg, T. Nuttle. Qualitative Models of Indicators of Environmental Sustainability of the Millennium Development Goals.. pp. 66-72. G. Steinbauer, F. Wotawa. Challenges in runtime detecting and locating faults in autonomous mobile robots.. pp. 73-77. B. Versiani dos Anjos, P. Salles. Qualitative models about degradation of riparian forests and its consequences for the soil.. pp. 78-82. T. Zrimec, S. Busayarat. A Model of the Human Lung Using a 3D High Resolution CT Atlas.. pp. 83-87. 4.

(5) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005. Dynamical Diagnosis with Interval Analytical Redundancy Relations Gabriela Calderón-Espinoza, Joaquim Armengol, Josep Veh´ı Institut d’Informàtica i Aplicacions. University of Girona, Spain E-17071 Girona, Catalonia, Spain gcalder,armengol,vehi@eia.udg.es. Abstract This paper focuses on diagnostic reasoning from uncertain and dynamical systems. Considering results from interval model-based detection, diagnostic reasoning is proposed by using aspects from approaches from FDI and DX communities. The reasoning is based on checking consistency from Interval Analytical Redundancy Relations (ARRs) by applying a modal interval tool which eliminates false alarms. An incremental reasoning after fault detection is proposed in order to never exonerate a diagnosis incorrectly. Aditional information about signs has been explored to reduce the diagnosis space. An example is presented in a water tanks system.. 1. Introduction. One approach to diagnosis is the called model-based diagnosis (MBD). MBD is based on comparing observations about behavior and the predictions from a process model. The better models are, the better results in MBD are. One approach from control community (FDI) is the use of structural analysis to make a complete analysis from the model. This approach identifies subsystems called Analytical Redundancy Relations (ARR). ARRs are obtained from combinations of constraints by eliminating unknown variables. After this, FDI approach just makes an on-line comparison between known variables and ARRs. Another consideration to simplify tasks in FDI is the assumption of single faults. On the other hand DX community from Computer Science and Artificial Intelligence (AI) makes the analysis after the presence of fault symptoms. In recent years DX community is making efforts in order to reduce the on-line tasks by taking the point of view from FDI about pre-compilation of the model. Moreover DX is successfully working to extend the methods for dynamical models. In this paper model precompilation and single fault assumption from FDI are used, on-line analysis with qualitative models and rows point of view from DX after the presence of fault symptoms [Cordier et al., 2004] are combined to improve diagnosis and to adapt reasoning to the used fault detection system. First step from model-based FDI is to generate signals called residuals which reflect the consistency between current. data and the model. In fault diagnosis systems based on consistency relations, the use of subsets that are sensitive to different faults is pursued and thereby isolation can be achieved. An important task is to find these submodels in order to find the minimal relations which give the highest diagnosis capability. These submodels called conflicts, can be achieved by using precomputed consistency relations, also called ARRs [Cordier et al., 2004]. The starting point of approaches are the elementary analytical relations (EAR) for a dynamical system, in this paper structural analysis [Blanke et al., 2003] is applied to generate ARRs with the aim of having useful models for diagnosis. In FDI the structural information is organized in form of incidence matrix. In DX the information is represented by transformed constraints. The goal of both approaches is to obtain analytical relations without unknown variables. Staroswiecky [Blanke et al., 2003] proposes an ARR generation technique based on the simultaneous elimination of a set of variables in a subset of analytical relations. On this paper a diagnostic reasoning with dynamical and interval ARRs is proposed according to the properties from the coherency test tool based on an extension of Interval Analysis called Modal Interval Analysis [Sainz et al., 2002]. Considering these results which are dedicated to uncertain system, enlightens the diagnostic reasoning with new aspects. Combination of points of view from communities and obtaining information based on the signs of partial derivatives is proposed. Several works had been explored in this direction [Calderón-Espinoza et al., 2003; Console et al., 2003; Olive et al., 2003]. Section 2 explains the properties from the detection system used to test the coherency of ARRs. Section 3 describes briefly the generation of ARRs with structural analysis to guaranty completes. In Section 4 the proposed diagnosis reasoning is described and in Section 5 we propose to add information to the fault detection in order to improve diagnosis. The additional information consists on information from partial derivatives and it is explained with an example of a water tanks system.. 2. Interval dynamic models. As it was said in the introduction one way to detect faults is by comparing the real system behavior with the predicted one obtained from a model. Continuous-time systems are usually. 5.

(6) Edinburgh, July 30th 2005. 2nd Workshop on Model-Based Systems. described by differential equations. Usually the input, state and output variables are sampled time-signals defined over a time variable k, which belongs to a discrete set. All signals are assumed to be sampled synchronously at a fixed sampling period. It is for this reason that discrete models are used. Then a fault is detected when the predicted behavior from the model is different from the corresponding measurement: y(t) = yˆ(t) (1) Most of the times this equation will be true and consequently the constant detection of faults happens. One reason is because of in industrial monitoring of processes, the uncertainty is often present due to sensors and signal noises, imprecise knowledge about model parameters or because the parameters may vary with time. With Intervals it is possible to have uncertain and less precise models but more accurate. These models are used to determine, for the measured sequence U , the sequence of the model output Yˆ (t). The consistency of the system with the model can be checked at every time t by determining the difference: r(t) = y(t) − yˆ(t). (2). detected. However if there is not a fault and the simulator never stops this drawback can be overcome by using an internal estimation Yrin (t). If the measurement is inside this envelope the fault, if it exists, will never be detected so the algorithm must stop. The simultaneous use of internal and external estimations obtain the same fault detection results than Yr (t) but with a much lower computation effort. Both estimations form an error-bounded estimation because although Yr (t) is not known, it is known that Yrin (t) ⊆ Yr (t) ⊆ Yrex (t). Three zones are defined by error bounded estimations depicted in Figure 1. The simulator guarantees that a fault exits when the measurement is out of the overbounded envelope (outer zone) by eliminating in this way false alarms. However if the measurement is in the intermediate zone there can be a fault and not be detected (missed alarm). This is due to that overbounded envelope includes values that do not belong to the values space of the system represented by interval models. Another reason is the dynamics of the system so more time may be needed for detecting a fault. If the measurement is in the inner zone, the algorithm stops because it is not possible to detect faults.. which is called residual. When there is no fault the value is close to zero. The reference behavior proposed for fault detection in the present work is obtained by simulation of interval models which consider uncertainty in model parameters and sensor measurements. One example of this kind of models is equation 3. The equation is a n-th order SISO (Single Input, Single Output) system represented by a difference equation where u are inputs, T the sampling time, and a or b are parameters of the system, in this case they are intervals: yt =. m+1 i=1. ai yt−iT +. p+1 . bj ut−jT. (4). Modal interval simulator. To compute the band limits is necessary to compute the range of a function in a parameter space at each simulation step, which is a task related to global optimization and usually needs an important computation effort. With SQualTrack [Sainz et al., 2002; Armengol et al., 2003] similar results can be obtained at a lower cost by calculating external estimations Yrex (t) to the range of the function at each iteration. After infinite iterations it would calculate the exact range, but it stops when the estimation is sufficiently close to detect the fault, thus saving much computational effort when a fault is. 6. output. intermediate zone outer zone. time. Figure 1: Three zones defined by error-bounded envelopes. Equation 3 is the starting point of this work. It defines an imprecise model of the supervised system with uncertain parameters that are independent. The simulation of a real-valued model produces a trajectory for each output variable which is a curve representing the evolution of the variable of the system across time: yr (t). In the case of an interval model, there is a set of models indeed where a set of curves (a band) represents the evolution of each variable [Armengol, 1999]. The limits of the band are:. 2.1. inner zone. (3). j=1. Yr (t) = [min(yr (t)), max(yr (t))]. outer zone intermediate zone. To computed the error bounded-estimations in a time instant, the simulator uses the values of the interval measurement from the past instant t-window. In case of multiincidences in the function and using algorithms based on Interval Arithmetic, overbounded results are obtained. However these multi-incidences are taken into account by using an extension of Interval Analysis called Modal Interval Analysis [SIGLA/X, 1999]. In this way spurious solutions are reduced which can be important depending on the problem. For example if detection is critical and need to be the most early possible or such as this paper were elimination of false alarms are valued. Sometimes simulation can not be required if results in prediction are satisfactory but in dynamical system the use of simulation has been shown that detection can be improved in terms of time and reliability [Sainz et al., 2002].. 3. Structural analysis. Structural model describes which variables are connected by which constraints. Different kind of variables can be represented: known variables, e.g. sensor signals and actuators.

(7) 2nd Workshop on Model-Based Systems. and unknown variables, for example internal states of the system. The structural model can be represented by an incidence matriz where rows correspond to constraints and columns to variables. Structural analysis identifies the part of the system which is monitorable, that is to say the set of constraints that have to be used to generate residuals. The task is to find submodels that can be used to formed consistency relations. Definition: Analytical Redundancy (ARR): There exists analytical redundancy if there exists two or more different ways to determine a variable x by only using the observations z(t), i.e. x = f1 (z(t)) and x = f2 (z(t)), and f1 (z(t)) = f2 (z(t)). Thus,the existence of analytical redundancy makes it possible to check the validity of the assumptions made to ensure that f1 (z(t)) = f1 (z(t)) A constraint that applies only to known variables and parameters constitutes an ARR an it can be evaluated from only observed variables in order to be used in fault detection and diagnosis tasks. Models for fault isolation or system state recognition are necessary. To achieve isolation, in addition to fault detection, a set of ARRs needs to be designed where different ARRs are sensitive to different subsets of faults. The basic tool for structural analysis is the concept of matching [Blanke et al., 2003]. A matching is a causal assignment which associates some system variables with the system constraint from which they can be calculated. Variables which cannot be matched cannot be calculated. Variables which can be matched in several ways can be calculated by different redundant means, thus providing a means for fault diagnosis. The aim is to calculate unknown variables from known variables. Known variables are available in real time, while unknown variables are not directly measured. However, there might exist some way to compute their value from the values of known ones (past and present values will be considered in discrete time models in order to represent a dynamical system).. 4. Diagnosis reasoning with dynamical and interval ARRs. In this section we explain generation of ARRs and the interpretation for a scheme of violated dynamical ARRs by the detection interval system. The example is a linear time invariant (LTI) dynamic system given by the following equations: (f1 ) x˙1 = a11 x11 + a13 x3 + a14 x14 + a16 x6 x˙2 = a21 x1 + a22 x2 + a23 x3 + a27 x7 (f2 ) x˙3 = a31 x1 + a33 x3 + a36 x6 (f3 ) x˙4 = x2 (f4 ) x˙5 = x3 + a55 x5 (f5 ) x˙6 = a66 x6 + b61 u1 (f6 ) x˙7 = a77 x7 + b72 u2 (f7 ) y˙1 = x1 (f8 ) y˙2 = x4 (f9 ) y˙3 = x5 (f10 ) The system’s structural model is represented by the set of constraints F = {f1 , . . . , f10 }, the set of unknown variables X = {x1 , . . . , x7 } and K =. Edinburgh, July 30th 2005. U Y = {u1 , u2 } {y1 , y2 , y3 } is the set of known variables/parameters i.e. input/reference signals (U ), known constant/parameters (P ), and measured signals (Y ). An incidence matrix for unknown variables by taking into account the concept of calculability for differential constraints is obtained. The concept of calculability gives a causality and defines if a variable x is calculable if and only if its value can be determined through the constraint f under the condition that the values of the other variables are known:. 4.1. Analytical redundancy relations generation. Three variables x1 , x4 and x5 can be calculated directly from known variables, the rest of the variables can be calculated in two different possible matchings1 . The number of distinct over-determined subsystems (for each performed matching is given by |F | − |X|. In this case is 10 − 7 = 3 which is equal to the number of unmatched relations. Table 1 shows two different possible matchings and Table 2 presents the unmatched relations for each matching: Match 1 f8 ←→ x1 f4 ←→ x2 f5 ←→ x3 f9 ←→ x4 f10 ←→ x5 f3 ←→ x6 f2 ←→ x7. Match 2 f8 ←→ x1 f4 ←→ x2 f5 ←→ x3 f9 ←→ x4 f10 ←→ x5 f1 ←→ x6 f2 ←→ x7. Table 1: Matched pair for each possible matching Matching 1 2. Unmatched relations f1 , f6 , f7 f3 , f6 , f7. Table 2: Unmatched relations for each performed matching All over-determined subsystems can be identified via unmatched relations for all possible matchings. There are two sets of rows that are identical. Since they can be disregarded, four over-determined subsystems are obtained and presented in Table 3. ARR1 ARR2 ARR3 ARR4. f1 1. f2. 1. 1. f3 1 1. f4. 1. f5 1 1 1 1. f6. f7. 1. 1. 1. f8 1 1 1 1. f9 1. 1 1. f10 1 1 1 1. Table 3: Analytical Redundancy Relations Where each row represents a minimal over-determined subsystem and contains an analytical redundancy relation 1 The computation of a set of ARRs relies on elimination techniques which are left aside here. It is, in general, guided by structural analysis (problem of finding a complete matching in a bipartite graph).. 7.

(8) Edinburgh, July 30th 2005. that can be used for fault detection. ARR can be directly deduced from these minimal over-determined subsystems in a sequential manner. For instance ARR1 involves equations f1 , f3 , f5 , f8 , f9 , f10 . A residual is the result of an ARR calculation when the known variables are replaced by their values. By substitution one example or ARR is the following: a36 a13 a36 a13 y¨3 + ( − a33 − a55 ) y˙3 + a55 (a33 − ) y3 = a a 16 16 a36 a14 a36 a36 a11 − y˙2 + y˙1 + (a31 − ) y1 a a16 a 16 16 . Residual expression for subsystem 1-1 can hence be written as ARR1 = y¨3 + αy3 y˙3 + βy3 y3 − αy2 y˙2 − αy1 y˙1 − βy1 y1 Residual expressions for the other ARRs in Table 3 can be obtained in a similar manner. This is one form to obtain all possible ARRs to diagnose a system. We use this set of relations in order to applied the diagnosis reasoning.. 4.2 A new fault diagnosis reasoning After a complete set of ARRs has been obtained, dynamical ARRs have to be evaluated. The modal interval simulator explained in section 2 is used to check the consistency in the interval ARRs. Uncertainty in parameters and sensor noise is considered by the interval models. Diagnosis reasoning is based on the property from the tool which consists on the elimination of false alarms. This tool is limited with regard to complex ARRs and computational work but it presents properties that can be useful for fault diagnosis. MBD from DX does not employ the notion of exoneration used in FDI approaches which assume that in an ARR is satisfied (residual is 0), then the components in the structure are exonerate [Cordier et al., 2004]. In the proposed diagnosis reasoning the DX notion is considered. Exoneration is not considered if an ARR is satisfied. The diagnostic reasoning is just based on violated ARRs. Since missed alarms are possible in the interval detection tool, this property forces the diagnostic reasoning not to take any decision when the system is consistent with the normal behaviour. A consistent state does not necessary imply that the system is working correctly. Because of the dynamics from the system three situations could happen: the system is faulty and it has not been detected because is inside normal behaviour, more time is needed to detect abnormal situation or the detection system is not able to detect faulty behaviour. It is for these reasons that diagnostic reasoning is just based on violated ARRs. Two model-based approaches for fault isolation are used from the two perspectives. FDI is based on faults signatures with a column interpretation of the fault signature matrix linking faults and ARRs. DX based on conflicts, proceeds along a row interpretation [Cordier et al., 2004]. An example of diagnostic reasoning is explained with current fault detection of {1 0 1 1}. Fault signature is compared with Table 3 but ARRs had been violated at different time. Temporal diagnosis is present in this kind of systems due to the properties of. 8. 2nd Workshop on Model-Based Systems. detection. The diagnosis can change along time and consequently a diagnosis reasoning which never exonerates a diagnosis incorrectly should be considered. Moreover an incremental diagnosis should be considered. Firstly, fault detection appears on ARR3 . With the assumption of single faults from FDI the first diagnosis based on rows point of view from DX is: one or more component/support are faulty: {f2 , f4 , f5 , f7 , f8 , f9 , f10 }. Secondly, ARR4 has been also violated. The coherent diagnostic is the intersection from ARR3 and ARR4 based on the point of view of columns from FDI concluding that {f5 , f8 , f9 , f10 } are faulty and exonerating {f2 , f4 , f7 }. Due to the assumption of single faults this is possible and because of the properties from the detection system (avoiding false alarms), the reasoning concludes that these exonerated components are not enough to explain the violation of both ARRs. Thirdly ARR1 is violated. With this information it is not possible to reduce the diagnosis. More time could be needed in order to ARR2 were violated in case {f5 , f8 , f10 } were faulty. Meanwhile the same diagnosis is maintained until ARR2 is violated, that which exonerate {f9 }. This is one reason that additional information about the way an ARR has been violated can help to improve the diagnostic reasoning by reducing the diagnosis or deciding if more time is needed to give a diagnosis. Summarizing the example, the fault signature of given observations at each instant time is a binary vector r = [r1 , ..., rn ] where ri = 0 if and only if ARRi = 0 and ri = 1 otherwise. (r1 , r2 , r3 , r4 ) = (0, 0, 0, 0) : not detected (r1 , r2 , r3 , r4 ) = (0, 0, 1, 0) : f2 , f4 , f5 , f7 , f8 , f9 , f10 faulty (r1 , r2 , r3 , r4 ) = (0, 0, 1, 1) : f5 , f8 , f9 , f10 faulty (r1 , r2 , r3 , r4 ) = (1, 0, 1, 1) : f5 , f8 , f9 , f10 faulty An incremental diagnosis is proposed based on rows point of view from DX with the first violated ARR. Following diagnosis consist on columns point of view from FDI whose faulty components are the intersection from previous diagnosis. The diagnosis can change along time and consequently a diagnosis reasoning which never exonerates a diagnosis incorrectly should be considered. An incremental diagnosis is proposed.. 5. Additional information based on partial derivatives. A well-known dynamical example of a system based on two interconnected tanks [Ploix and Follot, 2001] will be used to explain the obtention of additional information (see Figure 2) from the model for diagnosis reasoning. The system is described by the elementary analytical relations (Table 4). From elementary models the structure of the model is derived in form of incidence matrix by indicating presence of a variable in a constraints. In the structural model u, qv , qs1 , qs2 , ˜, x˜1 and x˜1 are known x1 and x2 are unknown variables and u variables from sensors. k, ks1 , ks2 are constant parameter from the systems. All variables and parameter are consid-.

(9) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005. ered as intervals for the consistency test by the modal interval simulator. u k qv. x1. (a) (b) (c) (d) (e) (f) (g) (h). qv 1. u 1. qs1. qs2. x1. 1 . x2. 1 1. 1. 1 . . 1 1. . . Table 5: Matching A. qs1. x2. a 1. ARR1 ARR2. b 1. c 1 1. d. e. 1. 1. f 1. g 1 1. h. 1. qs2. Table 6: Analytical redundancy relations Figure 2: Two tanks system A matching is shown for the example where unknown variables are associated with a constraint for the one which they can be determined, this is indicated with a in Table 5. Elementary Relation. (a). qv = ku. Domain low frequency. (b). 1 S dx = qv − qs1 dt. 0 < x1 < h 1. (c). qs1 = ks1 x1. (d). 2 S dx = qs1 − qs2 dt. (e). qs2 = ks2 x2. (f). u ˜=u. (g). x˜1 = x1. (h). x˜2 = x2. Support valve. upper tank output pipe upper tank. 0 < x2 < h 2. low frequency low frequency low frequency. lower tank output pipe lower tank control input. and identification. In the example of the two tanks system we have two ARRs: S. dx1 = k˜ u − ks1 x˜1 dt. (5). dx2 (6) = ks2 x˜2 − ks1 x˜1 dt Qualitative models will be formed by rules relating two kind of knowledge a) deviation of ARRs when a fault occurs and b) influence of known variables (measures from sensor) in deviation from output ARRs: S. δARR1 = k > 0; monotonically increasing (⊕) δu. (7). δARR1 = −ks1 < 0; monotonically decreasing () (8) δx1. x1 sensor. x2 sensor. Table 4: EARs for the two tanks system Analytical redundancy relations are (b) and (d). The constraints used to calculate unknown variables of this ARRs are the supports which represent components due to models are oriented to components. Fault signature is shown in Table 6. The additional information consists on analyze the sign of partial derivatives in order to establish a relation between known variables and faulty components. This knowledge can be obtained from the quantitative model and the goal is to obtain qualitative models with regard to fault modes by a set of rules. Indeed, during the interval computation and the global optimization, the sign of partial derivatives is obtained and analyzed. Also information about deviation from normal behaviour is obtained from the detection tool. The proposal on this paper is to reuse this information to make fault isolation. δARR2 = ks2 > 0; monotonically increasing (⊕) δx2. (9). δARR2 − ks1 < 0 monotonically decreasing () δx1. (10). In this way we deduce in Equation 7 that deviation from ARR1 with regard to known variable u is also deviation from ARR1 with regard to (a). Equation 8 with regard to (c), Equation 9 with (e) and Equation 10 deviation from ARR2 with regard to (c). We arrange this information in Table 7 where we have not written sensor faults and control input. Where [r] = sign(r − rref ) is a qualitative deviation whose values can be +1 if resultant values from detection in residual from ARR are bigger than normal values, -1 if values are smaller than normal ones and 0 if they are constant. The symbol ⊕ indicates that the corresponding variable is monotonically increasing with regard to qualitative deviation [r] which means that variable and residual will vary in the same. 9.

(10) Edinburgh, July 30th 2005. [r1 ]. [r2 ]. a +1 ⊕u 0. a -1 ⊕u 0. b ±1. 0. 2nd Workshop on Model-Based Systems c +1 x1 +1 x1. c -1 x1 -1 ⊕x1. d 0. e 0. e 0. ±1. +1 ⊕x2. -1 x2. Table 7: ARRs with signal information direction. Symbol indicates that the variable is monotonically decreasing indicating the opposite deviation direction. (b) and (d) are the ARRs such as the union of qualitative deviations and information about included variables form aditional information.. 5.1. Diagnostic reasoning with additional signs. Firstly an inconsistency is present in ARR2 ; the first diagnosis based on rows point of view and compared with Table 6 is: the set of possible faulty components are {c, d, e}. Additional information is used to check if this violated ARR is consistent with conditions in fault modes in order to consider the possibility or not than ARR1 can be not satisfied after a time. [r2 ] is increasing (+1) and it has been violated in the same direction. On one hand if variable x1 is decreasing, the possibility that in more time ARR1 can be violated it exists and {c} can be the faulty component, so the set of candidates is maintained. On the other hand if condition x1 is increasing, component {c} can be exonerated from the suspect fault candidates because this component were not be able to explain the violated ARR concluding that {d, e} are suspect of being faulty components and no more time is needed (sensor fault has not been considered in this case). In this way the set of diagnosis can be reduced or can help to decide if more time is needed to give a diagnosis.. 6. Discussion. In this paper a fault diagnosis reasoning has been proposed and it has been adapted for fault detection systems where false alarms are avoided. A fault detection system based on interval models has been proposed for fault diagnosis by using ARRs generated by structural analysis. From FDI model pre-compilation, single faults and exoneration assumption in some cases were used. No-exoneration notion when an ARR is satisfied and on-line analysis with qualitative models were combined to improve diagnosis and to adapt reasoning to the used fault detection system. The diagnostic reasoning is just based on violated ARRs. Rows and columns points of view at different level of the diagnosis task. The problem about fault isolation in dynamical systems has been explored and the decision problem before wait for another violated ARR has been studied. Additional knowledge obtained from partial derivative signs from the model was proposed in order to improve diagnosis task by taking advantage from interval systems. Another kind of additional knowledge to the future is the order of ARRs violation from a system. This information can. 10. contribute to improve the diagnostic reasoning for uncertain dynamical systems.. Acknowledgments This work was supported by Mexican National Council for Science and Technology (CONACyT), the European Union (European Regional Development Fund) and the Spanish government (Plan Nacional de Investigación Cient´ıfica, Desarrollo e Innovación Tecnológica, MCyT) through the co-ordinated research projects DPI2003-07146-C02-02 and DPI2004-07167-C02-02.. References ´ Sainz, [Armengol et al., 2003] J. Armengol, J. Veh´ı, M.A. and P. Herrero. Fault detection in a pilot plant using interval models and multiple sliding time windows. In SAFEPROCESS’03, Washington D.C., 2003. [Armengol, 1999] J. Armengol. Application of Modal Interval Analysis to the simulation of the behavior of dynamic systems with uncertain parameters. PhD, Universitat de Girona, 1999. [Blanke et al., 2003] M. Blanke, M. Kinnaert, J. Lunze, and M. Staroswiecki. Diagnosis and Fault-Tolerant Control. Springer-Verlag, Berlin, Germany, 2003. [Calderón-Espinoza et al., 2003] Gabriela CalderónEspinoza, Joaquim Armengol, and Arantza Aldea. Applying modal intervals to fault diagnosis. In International Conference on Artificial Intelligence and Applications, pages 505 – 510, Spain, 2003. [Console et al., 2003] Luca Console, Gianluca Correndo, and Claudia Picardi. Deriving qualitative deviations from matlab models. In 14th International workshop on principles of diagnosis (DX03), 2003. [Cordier et al., 2004] Marie-Odile Cordier, Philippe Dague, François Lévy, Jacky Montmain, Marcel Staroswiecki, and Louse Travé-Massuyès. Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives. IEEE Transactions on systems, Man, and Cybernetics-Part B: Cybernetics, 34(5):2163–2177, 2004. [Olive et al., 2003] Xavier Olive, Travé-Massuyès Louise, and Jérome Thomas. Complementing an interval based diagnosis method with sign reasoning in the automotive domain. In SAFEPROCESS’03, Washington D.C., 2003. [Ploix and Follot, 2001] Stéphane Ploix and Cyril Follot. Fault diagnosis reasoning for set-membership approaches and application. In CCA/ISIC’01, Mexico, 2001. ´ [Sainz et al., 2002] Miguel Angel Sainz, Joaquim Armengol, and Josep Veh´ı. Fault detection and isolation of the three-tank system using the modal interval analysis. Journal of Process Control, 12(2):325–338, 2002. [SIGLA/X, 1999] SIGLA/X. Modal intervals. Basic tutorial. In MISC99, pages 157–227, Universitat de Girona. Spain, 1999..

(11) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005. A model integration of DX an FDI techniques for automatic determination of minimal diagnosis R. Ceballos, M.T. Gómez-López, R. M. Gasca and C. Del Valle Computer Engineering Superior Technical School of Seville, Spain. Abstract Two communities work in parallel in model-based diagnosis: FDI and DX. In this work an integration of the FDI and the DX communities is proposed. Only relevant information for the identification of the minimal diagnosis is used. In the first step, the system is divided into clusters of components, and each cluster is separated into nodes. The minimal and necessary set of contexts is then obtained for each cluster. These two steps automatically reduce the computational complexity since only the essential contexts are generated. In the last step, a signature matrix and a set of rules are used in order to obtain the minimal diagnosis. The evaluation of the signature matrix is on-line, the rest of the process is totally off-line.. 1. Introduction. Diagnosis allows us to determine why a correctly designed system does not work as expected. Diagnosis is based on a set of integrated sensors which obtain a set of observations. The aim of diagnosis is to detect and identify the reason for any unexpected behaviour, and to isolate the parts which fail in a system. The behaviour of components is stored by using constraints. Inputs and outputs of components are represented as variables of the component constraints. These variables can be observable and non-observable depending on the sensors allocation of the sensors. Two communities work in parallel, although separately, in model-based diagnosis: FDI (from Automatic Control) and DX (from Artificial Intelligence). Nevertheless, the integration of FDI with DX theories has been shown in recent work [Cordier et al., 2000],[Ceballos et al., 2004]. In the DX community, [Reiter, 1987], [de Kleer et al., 1992] presented the diagnosis formalization. A general theory was proposed to explain the discrepancies between the observed and the correct behaviour by using a logical-based diagnosis process. In the FDI community, [Staroswiecki and Declerk, 1989] and [Cassar and Staroswiecki, 1997] presented the formalization of structural analysis, the process to obtain the ARRs (Analytical Redundancy Relation) of the system. In this work an integration of FDI theories with the DX community is proposed, in order to improve the minimal di-. agnosis determination. This integration has three phases. The structural pre-treatment in the first phase and the reduction of the model in the second phase enables the improvement of the computational complexity. The minimal diagnosis is obtained by applying an observational model to a signature matrix together with a set of precompiled rules. The evaluation of the signature matrix is on-line, however the rest of the process is totally off-line. Our paper has been organized as follows. First, definitions and notations are established in order to clarify concepts. Section 3 shows two examples of the validation of this approach. Section 4 describes the advantages of the structural pretreatment. After that, in section 5, the process for the definition of the context network is explained. Section 6 describes the determination of the minimal diagnosis. Finally, conclusions are drawn and future work is outlined.. 2. Definitions and notation. In order to clarify the diagnosis process some definitions must be established. Definition 2.1 System Model: A finite set of polynomial equality constraints (P) which determine the system behaviour. This is done by means of the relations between nonobservable (Vi ) and observable variables (sensors) of the system (Oj ). Definition 2.2 Observational Model: A tuple of values for the observable variables. Definition 2.3 Context: A collection of components of the system, and their associated constraints. The number of possible contexts is 2nComp - 1, where nComp is the number of components of the system. Definition 2.4 Context Network: A graph formed by all the contexts of the system in accordance with to the way proposed by ATMS[de Kleer, 1986]. The context network has a natural structure of a directed graph for set inclusion. Definition 2.5 Diagnosis Problem: A tuple formed by a system model and an observational model. The solution of this problem is a set of possible failed components.. 3. Examples. The following examples are used in order to explain our methodology.. 11.

(12) Edinburgh, July 30th 2005. 2nd Workshop on Model-Based Systems k m. 31 26 24 12. N22. 27. E3 25. 28 14. E1. 11 N 11. 32. 18. N23. 29 110. E1. N12 16 E4 17 N13 E2. 13. 15. 19. 22 N21 23 21. N14 E2. 112. 111. 210 N24 211 33. 212. Figure 1: The example of heat exchangers • A system of heat exchangers: As proposed in [Guernez, 1997], this system consists of six heat exchangers which distribute three flows fi that come at different temperatures ti , in accordance with the sensor allocations. There are different subsystems, each one formed by two exchangers: {E1, E2}, {E3, E4} and {E5, E6}. Each one of the six exchangers and each one of the eight nodes of the system are considered as components. The observable variables (flows and temperatures) are represented by shaded circles in Figure 1. The normal behaviour of the system can be described by means of polynomial constraints based on three different kinds of balances: i fi = 0: mass balance at each node i ·ti =0: thermal balance at each node i f in fi ·ti out fj ·tj = 0: enthalpic balance for each heat exchanger • A polybox system: This polybox system is derived from the standard problem used in the diagnosis community [de Kleer et al., 1992]. The system consists of fifteen components: nine multipliers, and six adders. The observable variables are represented by shaded circles in Figure 2.. 4. Structural pretreatment. The first part of this section shows the way to divide the diagnosis problem into independent diagnosis subproblems. The second part of this section explains the way of grouping the components into nodes in order to reduce the number of nonobservable variables to be considered in the system.. 4.1 Identification of the clusters The objective of this section is the partition of the system into independent subsets of components. This partition reduces the computational complexity of the diagnosis process since it enables the generation of the diagnosis of the whole system based on the diagnosis of the subsystems. Definition 4.1 Cluster of components: A set of components T is a cluster, if it does not exist a common non-observable variable of any component of the cluster with any component outside the cluster, and if for all T’ ⊂ T, T’ is not a cluster of components. In a cluster, all common non-observable variables among the components belong to the same cluster, therefore all the. 12. a b. M1. c d e. M2 M3. f g. M4. h i j. M5 M6. M7. x07 A5. x01 x02. x03. A1. A2. x08 x09 M9. x04 x05. A3. x06. A4. M8. q. x10 x11 A6. n o. p. r. x12. Figure 2: The polybox example connections with components which are outside the cluster are monitored. A cluster of components is totally monitored, and for this reason the detection of faults inside the cluster is possible without information from other components which do not belong to the cluster. A more detailed explanation and the cluster detection algorithm appears in previous work [Ceballos et al., 2004]. The diagnosis space for a system initially consists of 2nComp diagnoses [de Kleer et al., 1992], where nComp is the number of components of the system. Therefore the computational complexity for the diagnosis process is always smaller for an equivalent system divided into clusters, due to the reduced number of possible diagnoses. Example: In the heat exchanger example, five clusters of components can be obtained [Ceballos et al., 2004]: {N11 }, {N13 }, {N12 , N21 , N22 , E1 , E2 }, {N14 , N23 , N24 , E5 , E6 }, and {E3 , E4 }. These clusters allow the generation of an independent diagnosis process for each cluster, therefore the number of possible diagnoses is reduced to: (21 -1)+(21 -1)+(25 1)+(25 -1)+(22 -1) = 67. If each constraint of the model is considered as a component, then it is possible to obtain more clusters to a total of 9 clusters, as shown in Section 4.3.. 4.2. Obtaining relations without non-observable variables. In the diagnosis process it is necessary to produce new relations without non-observable variables, in order to monitor the system behaviour by using only the observational model. Our approach uses a function named NewRelations (NR) which takes a set of constraints and obtains a set of new constraints without a set of non-observable variables. Example: NR({x-a·c, y-b·d, f-x-y}, {x ,y}) = {a·c + b·d - f = 0}. This function can be implemented using different techniques. The Gröbner Basis algorithm [Buchberger, 1985] is used here. Gröbner basis theory is the origin of many symbolic algorithms used to manipulate equality polynomials. It is a combination of Gaussian elimination (for linear systems) and the Euclidean algorithm (for univariate polynomials over a field). The Gröbner basis can be used to produce an equiv-.

(13) 2nd Workshop on Model-Based Systems NodesIdentification(T) return N , S Ev = List of components associated to the variable v Ni = List of components of the node i Si = List of dispensable variables of the node i // Generate all the possible nodes of components foreach x ∈ T Ni = {x} endforeach // Detect all the components associated to a variable foreach Ni ∈ N foreach vark ⊂ nonObsVar(Ni ) Ek = Ek ∪ {Ni } endforeach endforeach // Merging the nodes of components while ∃ Ek ∈ E where |Ek | = 2 ∧ Ek = {Ni ,Nj } ∧ i<j Ni = Ni ∪ Nj N = N \ Nj Si = Si ∪ Sj ∪ {k} foreach Eq ∈ E where Nj ∈ Eq E q = E q \ Nj if ¬ ( Ni ∈ Eq ) Eq = E q ∪ N i endif endforeach endwhile. Figure 3: The algorithm to select the nodes of components alent system which has the same solution as the original, and without having non-observable variables.. 4.3. Obtaining the nodes of each cluster. Main assumption in this paper is to suppose that only one constraint is associated to each component. If it is necessary to apply this methodology to components with n constraints (where n > 1), it is then possible decoupling the component x into n virtual components xi with one constraint each. Our approach provide the minimal set of constraints to detect all the possible diagnoses of a system. The introduction of new definitions is necessary in order to efficiently generate these set of constraints: Definition 4.2 Dispensable variable: A non-observable variable vi is dispensable if there exist only two components xi and xj which include this variable in their related constraints. In the polybox example the variable x04 and the variable x08 are dispensable variables. Definition 4.3 Node of components: A single component could be a node of components if none of its non-observable variables is a dispensable variable. Two components, or, a component and a node of components, belong to the same node of components if they have a common dispensable variable. Lemma 1. Let N be a node of components. Let C be a context. If C ∩ N = ∅ ∧ ¬(N ⊂ C), then, by using only the components of the set C - {C∩N} is possible to generate constraints without non-observable variables. Proof. In order to generate constraints without nonobservable variables by using the set of components S = N ∩ C, it is necessary to eliminate the dispensable variables of. Edinburgh, July 30th 2005. Table 1: Improvements obtained using structural pretreatment in the proposed examples Examples: Clusters: Nodes: Vars.: Ctxs.: Heat E. 9 14 26 → 0 214 -1 → 14 Polybox 1 5 12 → 2 215 -1 → 31 the set S. If the set S does not have all the components of N, then there exists v, a dispensable variable, which cannot be eliminated, since it only appears in one component of the set S. Therefore, by using the components of the set N ∩ C, it is not possible to generate constraints without non-observable variables. Corollary 1. The contexts are built by using nodes of components instead of components, since it is impossible to generate constraints without non-observable variables by using a subset of a node of components. The following algorithm obtains the set of nodes of a cluster T. Algorithm: Figure 3 shows the algorithm NodesIdentification(T) which takes T, the set of components of a cluster, and returns N, the list of nodes, and S the list of the dispensable variables of each node. The algorithm begins by creating n nodes, where n is the number of components of the cluster. All these nodes have one component. Each list Ek stores all the nodes which have a constraint which includes the non-observable variable k. The auxiliary function nonObsVar returns the set of non-observable variables of a set of components. The dispensable variables are detected when a list Ek (associated with the variable k) includes only two nodes. In this case, the two nodes, Ni and Nj , are merged into the node Ni . The lists Si and Sj are merged (they are the set of dispensable variables of the new node), and obviously, variable k must be included in set Si . After this step it is necessary to update all the elements of the list Eq , in order to guarantee that node Ni and not Nj appears in all the elements of list E. Our approach obtains the nodes of each cluster of the system. A new set of constraints without the dispensable variables is obtained by applying the NewRelations function to the set of constraints of each node. If the node of components have no dispensable variables it is not necessary to apply the NewRelations function. Example: Table 1 shows the results obtained in the two proposed examples. The column Nodes shows the addition of all the nodes included in the clusters of the system. The column Vars shows the initial number of non-observable variables, and the final number of non-observable variables that are not dispensable variables. The column Ctxs shows the total number of possible contexts of the system, and the final number of possible contexts by using the nodes of components. In the heat exchanger example 9 clusters are obtained (if each constraint of the model is considered as a component). The non-observable variables are reduced from 26 to 0, as it appears in Table 1, because all the variables are dispensable. Table 2 shows the list of nodes of the polybox example, and the constraint obtained in each node by eliminating the dispensable variables.. 13.

(14) Edinburgh, July 30th 2005. 5. Determination of the context network. In DX community the diagnosis is obtained by detecting conflicts. Many methodologies tries to use structural description of the system, those methods are known as compilation methods. In [Pulido and González, 2004] the Possible Conflicts (PCs) concept is proposed as a compilation technique. Each PC represent a subsystem within system description containing minimal analytical redundancy and being capable to become a conflict. Computing Analytical Redundancy Relations (ARRs)[Staroswiecki and Declerk, 1989] is the compilation technique of FDI methodology. Our approach provide the minimal set of contexts which include an over-determined system of constraints that can detect a conflict in a cluster. The minimality issue was not guaranteed in the original ARR approach, but its guaranteed in our approach. In [Pulido and González, 2004] approach the PCs are obtained directly by using components, but our approach use nodes instead of components, therefore the size of the problem is reduced from 2c , where c is the number of components, to 2n , where n is the number of nodes. A context network, in accordance with the way proposed by ATMS[de Kleer, 1986], is generated in order to obtain all the relevant contexts for the diagnosis process. In order to establish the smallest set of contexts it is necessary to introduce the following definitions. Definition 5.1 Structural context: This is a context where all the nodes are connected, that is, they compose a connected graph, and all the non-observable variables appear in at least two constraints. The function to determine which are structural contexts is named isAStructural and takes a context C and returns a true value if it is a structural context. Definition 5.2 Minimal completed context: A structural context C is completed context if the set of constraints of the nodes of the context is a over-determined system of constraints, and, if it is possible to generate new constraints without non-observable variables by using the set of constraints of the context. A completed context is minimal if no context C’ ⊂ C exists such that C’ is a completed context. Lemma 2. If C is a minimal completed context then no context C’ exists, where C ⊂ C’, which can generate relevant constraints in the diagnosis process. Proof. Let C be a completed context with n nodes. Let C’ be a context with m nodes such that C ∩ C’ = ∅, and let be D a context with n + m nodes such that C ∪ C’ = D. Therefore: a) If C’ is not a completed context, it is impossible to eliminate one of the non-observable variables of the context C’, and hence it is not possible to generate a new constraint with all the nodes of the context D. It is possible to obtain constraints with fewer nodes than n+m nodes of context D, however these constraints can be obtained in a context with less nodes, and hence D is not minimal. b) If C’ is a completed context, then context D can generate a new constraint with all the nodes of the context. However, with this new constraint, which uses all the nodes of context D, it is impossible to distinguish between faults of nodes included in C and those included in C’. Hence it is not relevant in the diagnosis process. Therefore, in these two possible cases, it is not possible to. 14. 2nd Workshop on Model-Based Systems. Nodes N1 N2 N3 N4 N5. Table 2: Nodes for the polybox example Components Constraints M6 M8 A4 A6 h·j + n·o - r + x05 M5 g·i - x05 M1 M7 A1 A5 a·c + k·m - p + x02 M2 b·d - x02 M3 M4 M9 A2 A3 q - (f·h + x05)·(x02 + c·e). generate new relevant constraints for the diagnosis process if new nodes are added. Corollary 2. If a context C is a minimal completed context it is not necessary to process contexts C’ such that C ⊂ C’, since it is not possible to generate new relevant constraints for the diagnosis process. The algorithm which generate the contexts of each cluster has n - 1 stages, first the context with 2 nodes are obtained, then the context with 3 nodes, until it reaches the context with n nodes, where n is the number of nodes. The function NewRelations is only applied to the contexts which are structural contexts. When a minimal completed context C is found, the new constraints without non-observable variables are stored, and no contexts C’, such that C ⊂ C’, are generated. These new constraints are named Context Analytical Redundancy Constraint. Definition 5.3 Context Analytical Redundancy Constraint (CARC): A constraint obtained from a minimal completed context in such a way that only the observed variables are related. Example: In order to clarify this section, Tables 2 and 3 shows the results obtained for the polybox example. This system includes only one cluster with 15 components. The number of possible contexts is reduced from 215 −1 to 25 −1. By applying the rules and the algorithm proposed in this section, 10 contexts of the possible 31 (25 −1) are generated, however only 6 are minimal completed contexts. These 6 contexts generate 6 CARCs. Figure 4 shows the context network of the polybox example. Only the treated contexts are circled. The minimal completed contexts are circled in bold.. 6. Determination of the minimal diagnosis. The last step is the determination of the minimal diagnosis using the set of CARCs. In order to clarify the methodology, we suppose that the sensor observations are correct. We propose using a signature matrix as in FDI, but in order to obtain the same minimal diagnosis as in DX approach, it is necessary to apply a set of rules which guarantee the no-exoneration case in the solution. Definition 6.1 Fault signature: Given a set of n CARCs, denoted CARC= { CARC1 , CARC2 , ..., CARCn }, and a set of m faults denoted F = {F1 ,...,Fm }, the signature of a fault Fj is given by FSj = [s1j ,..., snj ]T in which sij = 1 if the context which generated the CARCi involves the nodes included in the fault Fj , and sij = 0 otherwise. Definition 6.2 Signature matrix: All the signatures for the set of possible faults constituted the signature matrix. Definition 6.3 Signature of an observation: This is given by OS=[OS1 ,...,OSn ] where OSi =0 if the CARCi is satisfied,.

(15) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005 N1 N 2N 3N4 N5. Table 3: CARCs obtained in the polybox example Index Context CARC 1 N1 N2 h·j + n·o - r + g·i a·c + k·m - p + b·d 2 N3 N4 3 N1 N3 N5 q - (f·h - h·j - n·o + r)·(-a·c - k·m + p + c·e) 4 N1 N4 N5 q - (f·h - h·j - n·o + r)·(b·d + c·e) 5 N2 N3 N5 q - (f·h + g·i)·(-a·c - k·m + p + c·e) 6 N2 N4 N5 q - (f·h + g·i)·(b·d + c·e) and OSi =1 otherwise. Definition 6.4 Diagnosis set: The set of faults whose signatures are consistent with the signature of the observational model. Our approach supposed that an observation signature OS is consistent with another signature FSj if OSi = sij ∀ i. Definition 6.5 Minimal diagnosis: A fault Fj is a minimal diagnosis if Fk is not a diagnosis ∀ faults Fk ⊂ Fj . Table 4 shows the signature matrix for the polybox example in order to clarify these definitions and the process to obtain the minimal diagnosis. The signature OK = [0, ..., 0]T represents the no-fault case. The signature matrix is very similar to the corresponding matrix in the FDI methodology. However in our approach, the faults involve nodes instead of components. In this example it is necessary to expand the number of columns of the signature matrix in order to obtain the multiple faults. Each fault Fj , which involves n nodes, is obtained using a fault Fk , which involves n−1 nodes, and a simple fault Fs which is not involved in Fk . The multiple fault signature Fj is given by FSj = [s1j ,..., snj ]T in which sij = 0 if sik =sis , and sij = 1 otherwise. The multiple fault signature Fj is not added to the signature matrix if ∀ sij : sij = 1 → sij = sik , due to the implication that the new multiple fault is a superset of a previously obtained fault which involves fewer nodes, and therefore cannot be part of a minimal diagnosis. The generation of the signature matrix stops when it is impossible to generate new signatures of faults which involve n nodes, with the faults which involve n−1 nodes. In FDI, the exoneration assumption [Cordier et al., 2000] is implied, that is, given an observational model, each component of the support of a satisfied CARC is considered as functioning correctly, that is, it is exonerated. In the DX approach, the exoneration is not considered by default. In order to obtain the same results as in the DX approach by using a signature matrix, it is necessary to apply a new definition of consistency. In the no-exoneration case an observation signature OS is consistent with another signature FSj if ∀ OSi = 1 then sij = 1. That is, only the non-satisfied CARCs are used, and Fj must have the value 1 in each nonsatisfied CARC. When the diagnosis set is obtained by using the new definition of consistency, we propose the application of a set of rules in order to detect which of the faults are minimal diagnoses, since many faults will be consistent with the observational model although they are not a minimal diagnosis. The following algorithm generates the rules to obtain the minimal diagnosis. Algorithm: Let CS(OS,FS) be a function which evaluates. N1 N 2N 3N4. N 1N 2 N3 N5. N 1 N2 N4 N5. N 1 N3 N4N5. N 2 N3 N4N5. N 1 N2 N 3 N 1N 2N4 N 1 N3 N5 N1 N 2N5 N 1N 3 N4 N 2 N3 N4 N 2N 3 N5 N 1 N4 N5 N2 N4N5 N 3N4N5. N1 N 2. N1 N 3 N 2N 3 N1 N4 N1 N 5 N 2N 4 N 2 N5 N 3 N4 N3 N5. N1. N2. N3. N4. N4 N5. N5. Figure 4: Context network of the polybox example whether the signature OS is consistent with signature FS. For each possible fault Fj in the signature matrix, let MDF j be a Boolean variable which holds information on whether a fault Fj is a minimal diagnosis, and let VCF j be a Boolean variable which holds information on whether a fault Fj is a valid candidate for the generation of new faults that could be a minimal diagnosis. For each possible fault Fj it is initially supposed that VCF j = true. The first step is to validate if the OK (no fault case) is a minimal diagnosis: MDOK = CS(OS,OKS), and, for any simple fault Fj , the equality VCF j = ¬ MDOK must be satisfied. If OK is not a minimal diagnosis, the following rules must be evaluated for all the possible faults (except OK) in the same sequential order as they appear in the signature matrix. These rules guarantee the correct detection of the minimal diagnosis for an observational model: • For each fault Fj with the signature FSj , the equality MDF j = VCF j ∧ CS(OS,FSj ) must be satisfied. • For each fault Fk which involves n + 1 nodes, where n ≥ 0, and which can be obtained using the fault Fj (that involves n nodes) and a simple fault Fs (which is not involved in Fj ) then MDF j ⇒ VCF k = false. Table 5: A subset of the rules for the polybox example MDOK = CS(OS,OKS). MDF 2 = VCF 2 ∧ CS(OS,FS2 ). VCF 1 = ¬ MDOK. .... .... MDF 13 = VCF 13 ∧ CS(OS,FS13 ). VCF 5 = ¬ MDOK. MDF 13 ⇒ VCF 123 = false. MDF 1 = VCF 1 ∧ CS(OS,FS1 ). MDF 13 ⇒ VCF 134 = false. MDF 1 ⇒ VCF 12 = false. MDF 13 ⇒ VCF 135 = false. .... MDF 14 = VCF 14 ∧ CS(OS,FS14 ). MDF 1 ⇒ VCF 14 = false. .... MDF 1 ⇒ VCF 15 = false. MDF 245 = VCF 245 ∧ CS(OS,FS245 ). Example: Table 5 shows a subset of the rules for the polybox example. The generation of the rules for the verification of whether a fault is a minimal diagnosis can be done offline, because these rules are the same for all the observational models. The bottom of Table 4 shows the VC and MD evaluation results for the observation signature OS = [0, 0, 1, 1, 1, 1]T . Only the evaluation of the rules must be done on-line. This part of the process is a simple propagation of Boolean values.. 15.

(16) Edinburgh, July 30th 2005. CARC 1 2 3 4 5 6. VC MD. OK 0 0 0 0 0 0. OK 1 0. 2nd Workshop on Model-Based Systems. F1 1 0 1 1 0 0. F1 1 0. F2 1 0 0 0 1 1. Table 4: The signature matrix of the polybox example F3 F4 F5 F12 F13 F14 F15 F23 F24 F25 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 Fxxx ⊂ {F123 , F124 , F134 , F135 , F145 , F234 , F235 , F245 }. F2 F3 F4 F5 F12 F13 F14 F15 F23 F24 F25 F34 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 VC and MD values for the observation signature OS = [0, 0, 1, 1, 1, 1]T. The evaluation of the signature matrix is very similar to the FDI methodology. However in our approach, the faults involve nodes instead of components. Hence, the last step is the substitution of each node with one of its components. In the polybox example, fault F3 is equivalent to the faults in {{M1 }, {M7 }, {A1 }, {A5 }}; fault F12 is equivalent to faults {{M6 M5 }, {M8 M5 }, {A4 M5 }, {A6 M5 }}; and so on. The information of all the possible minimal diagnoses is stored in a matrix and as a set of rules. Therefore, it is only necessary to calculate this diagnosis once. As happens in FDI methodology, this work can be done off-line, only the evaluation of the signature matrix is on-line.. 7. Conclusions and future work. This paper proposes a new approach to automation of and improvement in the determination of minimal diagnosis. The approach is based on FDI and DX theories. The structural pre-treatment in the first phase and the reduction of the model in the second phase enable improvement in the computational complexity. All the possible minimal diagnoses are represented in a signature matrix. The minimal diagnosis is obtained by using an observational model and a set of precompiled rules. Only the evaluation of the signature matrix is on-line, the rest of the process can be done off-line. The methodology was applied to two different examples, and the results were very promising. As future work we suggest extending the methodology to include dynamic systems and to include more complex and real problems, where the application of the methodology could be more complicated.. 8. Acknowledgment. The authors wish to thank two anonymous reviewers for their valuable comments. This work has been funded by the M. de Ciencia y Tecnolog´ıa of Spanish (DPI2003-07146-C02-01) and the European Regional Development Fund.. References [Buchberger, 1985] B. Buchberger. Gröbner bases: An algorithmic method in polynomial ideal theory. Multidimen-. 16. F34 0 1 1 1 1 1. F35 0 1 1 1 1 1. F35 0 0. F45 0 1 1 1 1 1. F45 0 0. Fxxx 1 1 1 1 1 1. Fxxx 0 0. sional Systems Theory, N. K. Bose, ed., pages 184–232, 1985. [Cassar and Staroswiecki, 1997] J. Cassar and M. Staroswiecki. A structural approach for the design of failure detection and identification systems. In IFAC-IFIP-IMACS Conf. on Control of Industrial Processes, Belfort, France, 1997. [Ceballos et al., 2004] R. Ceballos, M.T. Gomez, R.M. Gasca, and S. Pozo. Determination of possible minimal conflict sets using components clusters and grobner bases. In DX04, pages 21–26, Carcassonne, France, June 2004. [Cordier et al., 2000] M. Cordier, F. Lévy, J. Montmain, L. Travémassuyés, M. Dumas, M. Staroswiecki, and P. Dague. A comparative analysis of ai and control theory approaches to model-based diagnosis. In 14th European Conference on Artificial Intelligence, pages 136–140, 2000. [de Kleer et al., 1992] J. de Kleer, A. Mackworth, and R. Reiter. Characterizing diagnoses and systems. Artificial Intelligence, 2-3(56):197–222, 1992. [de Kleer, 1986] J. de Kleer. An assumption-based truth maintenance system. Artificial Intelligence, 2(28):127– 161, 1986. [Guernez, 1997] C. Guernez. Fault detection and isolation on non linear polynomial systems. In 15th IMACS World Congress on Scientific, Computation, Modelling and Applied Mathematics, 1997. [Pulido and González, 2004] B. Pulido and C. Alonso González. Possible conflicts: A compilation technique for consistency-based diagnosis. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 34(5):2192–2206, October 2004. [Reiter, 1987] R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence 32, 1:57–96, 1987. [Staroswiecki and Declerk, 1989] M. Staroswiecki and P. Declerk. Analytical redundancy in non linear interconnected systems by means of structural analysis. In IFAC Advanced Information Processing in Automatic Control (AIPAC-89), pages 51–55, Nacy, France, June 1989..

(17) 2nd Workshop on Model-Based Systems. Edinburgh, July 30th 2005. A System for Predicting Citizens’ Satisfaction Using Qualitative Information Marta Domingo1, Núria Agell2, Xavier Parra3 and Mónica Sánchez4 GREC Group. Av. Víctor Balaguer s/n. 08800 Vilanova i la Geltrú, Spain 2 GREC Group and ESADE-URL. Av. Pedralbes, 60. 08034 Barcelona. Spain 3 GREC Group and MA2-UPC. Jordi Girona, 1,3. 08034 Barcelona. Spain 4 GREC Group and ESAII-UPC. Av. Víctor Balaguer s/n. 08800 Vilanova i la Geltrú, Spain llorensdomingo@yahoo.es, nuria.agell@esade.edu, xavier.parra@upc.edu, monica.sanchez@upc.edu 1. Abstract In studies concerned with sustainability the underlying models are not numerical since they depend on many conditions that can be regarded as qualitative. In this paper, a model to evaluate citizens’ satisfaction learnt from data collected from a survey is presented. The model, which involves the use of RBF neural networks, will provide local councillors with useful information, enabling them to evaluate trends and improve strategies focused on enhancing sustainability. In this paper a contribution describing a practical experience with a model-based system applied to a study commissioned by the town council of Vilanova i la Geltrú (Catalonia, Spain) is presented.. 1 Introduction Sustainability can be described as a new development model, based on the improvement of population welfare and the preservation of natural resources as a means to achieve long-term advantages. Initiatives are based on the use of sets of indicators, each indicator reflecting the interactions between environmental, economic and social aspects. In the European context, a definition of sustainability indicators was addressed at the meeting: ‘Towards a Local Sustainability Profile - European Common Indicators’, during the ‘3rd European Conference on Sustainable Cities and Towns’ (9-12 February 2000, Hanover, Germany). At this meeting, local authorities of many European cities agreed to integrate the European Common Indicators into their existing municipal management systems. This initiative is a step towards a new generation of monitoring practices. A set of environmental sustainability indicators and methodologies for collecting the data for each indicator was developed in conjunction with stakeholders. The European Common Indicators are a self-contained set of indicators. The support of the Town Council of Vilanova i la Geltrú and MCyT (Spanish Ministry of Science and Technology) MERITO project (TIC2002-04371-C02/01) is acknowledged.. focused on helping towns and cities interested in the quality of their urban environment to begin to monitor progress. An initial listing of existing indicators was reduced to a final list of 10 integrated indicators through a process of analysis and elimination. The resulting 10 European Common Indicators were: • Citizen satisfaction with the local community • Local contribution to global climatic change • Local mobility and passenger transportation • Availability of local public open areas and services • Quality of local ambient air • Journeys by children to and from school • Sustainable management of the local authority and local business • Noise pollution • Sustainable land use • Products promoting sustainability The monitoring initiative is intended to support local authorities in their work towards sustainability and to provide objective and comparable information on progress towards sustainability across Europe. Based on the above set of integrated indicators, it is designed to measure movement towards or away from sustainability, focusing on the extent of change over time and the identification of trends and directions, rather than on absolute measures. The definition and calculation of some indicators is direct, because they are quantitatively measurable (in terms of CO2 emissions, passenger transport (km/capita), percentage of population with access to green spaces, number of days with good air quality, etc.). Other indicators, such as the degree of satisfaction of citizens with their locality, involve a qualitative perception of reality and have to be managed differently. In other words, the economic, social and environmental systems that make up the community are partial issues that may give an idea of the quality of life in that community, which is the central concern of sustainability. However, the satisfaction of citizens with their local community is about more than just numerical accordance of their locality with permitted ratings. In many works, quantitative indicators are taken into account as a central concern of urban sustainability, while other subjective perceptions of people related to global welfare are not properly dealt with.. 17.

(18) Edinburgh, July 30th 2005. The challenge is to model this kind of qualitative knowledge and to look for adequate tools to analyze it and identify trends and change over time. Afterwards, town hall managers would be able to experiment with the effect of a given action on the trend. This paper presents a contribution describing a practical experience with a model-based system applied to a study commissioned by the town council of Vilanova i la Geltrú (Catalonia, Spain), a town with over 55,000 inhabitants. Some of the authors of this paper were involved in the study of the first indicator: ‘degree of satisfaction of citizens with their locality’ in Vilanova i la Geltrú. The degree of satisfaction of citizens with their locality was chosen as the first European Common Indicator at the Hanover meeting [3], [4], [6]. Initially, a descriptive study was performed on the basis of a representative collection of data [Ferrer et al., 2002]. This information was based on a frame questionnaire concerning different aspects of the town. The questionnaire provided a number of qualitative questions, with some linguistic labels as answers. Moreover, qualitative information related to the reasons for satisfaction or dissatisfaction of citizens was also collected. In Section 2 the problem being treated in this study is presented. Section 3 gives the basic concepts of the methodology and its performance when working with qualitative data. In Section 4, the experiments being performed and their results are described. Finally, the paper draws some conclusions and offers proposals for future research.. 2 Problem definition Predicting evolution of citizens’ satisfaction with a specific proposed strategy is a key issue for town hall management. To this end, a methodology involving the use of RBF neural networks is implemented. This allows a view of the changes in citizens’ satisfaction, analyzing the system’s. 2nd Workshop on Model-Based Systems. sensibility with respect to variations in input variables. In the near future, it is planned to monitor this system in order to provide local councillors with a friendly tool to support decision-making. The study on the global subjective indicator ‘citizens’ satisfaction’ in Vilanova i la Geltrú was carried out from December 2001 to November 2002. The study was divided into four main parts: design, fieldwork, information extraction and exposition of results. At the design stage it was decided to conduct stratified sampling by controlling the representativeness of people living in the town. Parts one and two were performed in three phases. The first phase entailed random sampling on phone numbers, and surveys were administered to people answering the phone. When the first round of answers had been stored, the representativeness of the sample was analyzed. The second round of phone surveys had an adapted schedule and specific people search. Finally, the third phase was performed on the street looking for specific individuals.. 2.1 Description of framework and variables The methodology proposed to study the first indicator was based on a frame questionnaire using a standard form provided by the town council of Vilanova i la Geltrú, a reference document for all European cities signing the Hanover Agreement. The questionnaire was composed of 11 questions about several aspects of the urban environment. There were 10 variables concerning the basic urban services, and an 11th variable was a more synthetic and subjective issue, dealing with the convenience of the city for everyone as a good place to live and work in (see Table 1). Only minor changes and additions to the questionnaire were allowed to let the council achieve some qualitative subjective information. Changes in the order of questions were also allowed.. QUESTIONS 1) Are you satisfied about the protection of natural resources (urban environment, beach, mountains)? 2) Are you satisfied about the streets, public spaces, façades, pedestrian-only zones? 3) Are you satisfied about the employment opportunities in Vilanova i la Geltrú? 4) Are you satisfied about the level of cultural, sports, and leisure services in Vilanova i la Geltrú? 5) Are you satisfied about the level of public health and social services in Vilanova i la Geltrú? 6) Are you satisfied about the education services in Vilanova i la Geltrú? 7) Are you satisfied about the public transport services in Vilanova i la Geltrú? 8) Are you satisfied about the opportunities for participation in the decision-making processes of the town (municipal elections, forums, attention to citizen’ problems, etc.)? 9) Are you satisfied about the level of security in Vilanova i la Geltrú? 10) Are you satisfied about accommodation opportunities in Vilanova i la Geltrú (easiness, quality, prices…)? 11) Are you satisfied about Vilanova i la Geltrú as a globally good place to live and work in?. 18.