Determination of Possible Minimal Conflict Sets Using Constraint Databases Technology and Clustering

Determination of Possible Minimal Conflict Sets Using Constraint Databases Technology and Clustering M.T. G´omez-L´opez, R. Ceballos, R. M. Gasca, and S. Pozo Computer Engineering Superior Technical School of Seville, Spain {mayte, ceballos, gasca, sergio}@lsi.us.es Abstract. Model-based Diagnosis allows the identification of the parts which fail in a system. The models are based on the knowledge of the system to diagnose, and can be represented by constraints associated to components. Inputs and outputs of components are represented as variables of those constraints, and they can be observable and non-observable depending on the situation of sensors. In order to obtain the minimal diagnosis in a system, an important issue is to find out the possible minimal conflicts in an efficient way. In this work, we propose a new approach to automate and to improve the determination of possible minimal conflict sets. This approach has two phases. In the first phase, we determine components clusters in the system in order to reduce drastically the number of contexts to consider. In the second phase, we construct a reduced context network with the possible minimal conflicts. In this phase we use Gr¨obner bases reduction.A novel logical architecture of Constraint Databases is used to store the model, the components clusters and possible minimal conflict sets. The necessary information in each phase is obtained by using a standard query language. 1 Introduction Diagnosis allows to determine why a system correctly designed does not work as it was expected. It is based on the monitorization of a system. The diagnosis aim is to detect and to identify the reason of an unexpected behavior, or in other words, to identify the parts which fail in a system. Our proposal is based on DX [1] approaches and in other works as [2,3]. These works were proposed to find out the discrepancies between the observed and correct behaviors of the system. In engineering applications it is often overlooked the storage of these data and query processing. The key idea in this paper is to combine the power of Constraint Databases (CDBs) [4,5] with the data treatment of diagnosis. We are able to improve the efficiency in some phases of the model-based diagnosis with CDBs. To improve the detection of possible minimal context conflicts, we use a program implemented in JavaTM and SQL (Standard Query Language). With CDBs technology [6] we are able to make the informationandmodels persistent.MostDXapproachesforcomponentscharacterizethe diagnosis of a system as a collection of minimal sets of failing components which explain the observed behaviors (symptoms). A conflict is a set of assumptions where, at least, one must be false. The assumptions are about behavioral modes of components. GDE [7] coupled with an ATMS [8] as inference engine uses previously discovered conflicts C. Lemaˆıtre, C.A. Reyes, and J.A. Gonzalez (Eds.): IBERAMIA 2004, LNAI 3315, pp. 942–952, 2004. c Springer-Verlag Berlin Heidelberg 2004 Determination of Possible Minimal Conflict Sets 943 to constrain the search in the candidate space. The most important disadvantage of using this approach is the large number of possible conflicts (2n−1), nbeing the number of components. In this work, we propose a new approach to automate and to improve the determination of possible conflicts, it is based on: –Astructuralpretreatmentinordertoreducedrasticallythecomputationalcomplexity. –The Reduction of the number of possible contexts to treat by means of symbolic techniques in order to obtain the possible conflicts. This technique for elimination is Gr¨obner bases [9] that is our projection operator to manipulate multiple polynomial variables. It eliminates the non-observable variables of the constraints of the different contexts of a previous step. Finding all minimal conflict has been a problem active enough at last years using CS- Tree [10]. Symbolic processing algorithms (Gr¨obner bases) of the initial model are used by model-based diagnosis communities [11,12]. Another proposition [13] presents the concept of a possible conflict as an alternative to the use of pre-compiled dependencyrecording. Our paper has been organized as follows: Section 2 reviews definitions and notation to allowing to formalize the subsequence operations. Section 3 shows an example to prove our solution. Section 4 describes the improvements to detect the possible minimal conflicts using CDBs and components clusters. Finally we present our conclusions and the future works in this research line. 2 Definitions and Notation The definitions and notation used are based on the concepts proposed in the diagnosis community (DX). To introduce our work it is necessary the use of the following definitions and notation: Definition 1. The System Polynomial Model (SPM): It can be defined as a finite set of polynomial equality constraints (P) which determine the system behavior. This is done by means of the relations between the non-observable variables (Vnob) and the observable variables (Vob) which are directly obtained from sensors that are supposed to work correctly. Therefore, the tuple SPM (P,Vob,Vnob)is obtained for a system. Definition 2. Context Set (CS): A context set of a SPM is a collection of components which compose the system. The possible context set will be 2comp −1, where comp is the number of components of the system. Definition 3. Context Network (CN): A graph formed by all the elements of the context set of the system according to the way proposed by ATMS [8]. 3 System Example: A System of Heat Exchangers In order to explain our methodology, we will apply it to the system shown in Figure 1. It was presented in [14]. This system consists of six heat exchangers, three flows ficoming 944 M.T. G´omez-L´opez et al. in at different temperatures ti. The functions of the system are described by polynomial constraints, coming from three kinds of balance: ifi=0: mass balance at each node, ifi∗ti=0: thermal balance at each node, in fi∗ti−out fj∗tj=0: enthalpic balance for each heat exchanger. Fig.1. System of Heat Exchangers The system has 34 polynomial equations and 54 variables, from which 28 are observable: t11,t12,t13,t16,t17,t18,t19,t112,t21,t26,t27,t212,t31,t 33,f11,f12,f13,f16, f17,f18,f19,f112,f21,f26,f27,f212,f31 and f33. There is no direct measure of the rest of the variables. This defines three different subsystems, each one formed by two exchangers: {E1,E 2},{E3,E 4}and {E5,E 6}. Each of the six exchangers and each of the eight nodes of the system are considered as components whose correct functioning must be verified. 4 Computing All Possible Minimal Conflicts The model which reflects the system structure and behavior is presented by a set of polynomial constraints. All this information is stored in a CDB. The key idea is to generate an equivalent constraints model which has the same solution as the original one, but only with observable variables. In order to produce this model we will use Gr¨obner bases as symbolic technique. 4.1 Gr¨obner Bases Gr¨obner bases theory is the origin of many symbolic algorithms used to manipulate multiple variable polynomials. It is a generalization of Gauss’ elimination of multivariable linear equations and of Euclides’algorithm for one-variable polynomial equations. Gr¨obner bases has better computational properties than the original system. We can determine if a system can be solved or not. Determination of Possible Minimal Conflict Sets 945 The main idea is to transform the polynomial constraint set into a standard form for the resolution of problems. Having the set of equality polynomial constraints of the form P=0,Gr¨obner bases produce an equivalent system G=0which has the same solution as the original one, but generally easier to be solved. For our work, we have a function called Gr¨obnerBasis, which calculates Gr¨obner bases by means of a finite set of polynomial equations (SPM) and a set of observable and non-observable variables. This function allows building the context network. The signature of Gr¨obnerBasis function looks like this: Gr¨obnerBasis({Polynomials},{Observable Variables}, {Non-observable Variables}) Let us consider, for instance, the context represented by {N12E1E2}.Gr¨obner Basis function takes the parameters: Gr¨obnerBasis({polynomialsOf(N12,E 1,E 2)},{f16,f 12,f 13,t 16,t 12,t 13}, {f14,f 15,f 22,f 23,f 24,t 14,t 15,t 22,t 23,t 24}) The result would be the system of polynomial constraints: {f12 +f13 −f16 =0}. 4.2 Constraint Database Architecture One of the difficulties in diagnosing a system is handling the information, therefore we have important reasons to use CDBs in model-based diagnosis: 1. By using CDBs, it is possible to add or delete some components when our system changes. In this way, rebuilding the full problem is not necessary. 2. If we do not use a CDB and the execution of the algorithm diagnosis fails, while being executed, we must reexecute the full problem because there is not partial information stored. 3. CDBs allow using the power of SQL in order to query the database and obtain the necessary information. Fig.2. Constraint Database Architecture (k: Primary Key) 946 M.T. G´omez-L´opez et al. Firstof all, wearegoing to explainthe databasearchitecture,andhowthe information is stored: 1. Components:Thistablecontainsthenamesand identifiers ofthecomponentswhich make up the system. In this table, the cluster identification of each component is also stored. 2. Polynomials: This table contains the different behaviors of the components. The components can have more than one polynomial associated. 3. ContextNetwork: This table represents all the relations that the process must study to obtain the minimal possible conflict context. 4. Variables: This table contains all the variables which participate in the system, observable and non-observable. 5. VariablePolynomials: This table represents the variables in each polynomial. This table is important because in order to obtain Gr¨obner bases we need to send the observable and non-observable variables of the polynomials. 6. Constraints:All the constraints are stored in this table. We will fill in this table with the Gr¨obnerBasis function results. 7. ConstraintNet: This table relates each context to constraints. 8. Clusters: This table contains the relations between components and clusters. 4.3 First Improvement: Identification of Components Clusters In our methodology, the first step is to isolate independent subsystems. This structural pretreatmentwillallowustodividethesystemintoindependentsubsystems.Thepossible minimal conflict sets of the system can be obtained by the conflicts of all independent subsystems. The subsystems obtained are smaller than the whole system. Therefore the computational complexity to detect conflicts from each subsystem is lower or equal than the whole system. In order to clarify the following steps we need the following definition: Definition 4. Components cluster (CC):A set of components Cis a components cluster, if the following predicates are true: –All non-observable inputs and outputs of each component of Care always linked only to components of C. –It does not exist another set C’ with less elements than C, which validates the first predicate and it is included in C. With the first predicate we look for the independence among conflicts of different components clusters. This predicate guarantees that it is possible to detect a conflict in a components cluster without information about other components clusters. This is possible because, in a components cluster, all the non-observable inputs and outputs are among components of the same cluster. Therefore, there is not any connection with another components cluster which is not monitored. We look for the division of our system into the biggest possible number of clusters in order to obtain a smaller computational cost. The second predicate guarantees that the components clusters will be as small as possible. Determination of Possible Minimal Conflict Sets 947 Example: For example, component E3is not completely monitored because we are not able to know the value of outputs f32 and t32. Likewise, E4is not completely monitored because we are not able to know the value of inputs f32 and t32. But we can monitor these two components together like they were only one component. In this case, all the inputs and outputs of this component are observable. Algorithm: The following pseudo-code (see Figure 3) stores the set of components clusters of a system. At first, the set Chas all the components. The algorithm extracts each time one component of Cto create an instance (CP) of a components cluster.All the components from Cwhich have, at least, one non-observable variable in common with one component of CP are added to CP. If it is impossible to find another component with non-observable variable in common, the components cluster is completed. The process continues with another component from Cwhich has not been assigned to any components cluster. The process is finished when the set Cis empty, and all components are assigned to one components cluster. Set c = ObtainSystemComponents() while (NotEmpty(c)) Component x = GetComponent(c) Cluster cp = CreateCluster(x) boolean change = true while(change) Set cno = GetCommonComp(cp,c) deleteComponents(c,cno) AddComponents(cp,cno) Change=NotEmpty(cno) endwhile AddClusterToDB(cp) endwhile Fig.3. Pseudocode of the components clusters algorithm Methods to Select the Components Clusters: –ObtainSystemComponents(): This method returns all the system components stored in the CDB. –GetComponent(Set c): It returns one component and delete it from the set C. –CreateCluster(Component x): Here it is created a cluster with the component x. –GetCommonComp(Cluster cp, Set c): This method returns and deletes (from the set C) all the components from cwhich have, at least, one non-observable variable in common with some of the components of cp. –AddComponents(Cluster cp, Set cno): It adds all cno components to cp cluster. –AddClusterToDB(Cluster cp): This method stores cp Cluster in the CDB. 948 M.T. G´omez-L´opez et al. For the example presented in Section 3, we obtain five components clusters, which are A={{N11},{N13},{N12,N21,N22,E 1,E2},{N14,N23,N24,E5,E6},{E3,E4}}.For all the components clusters obtained we will build a different and independent context network. With the structural pretreatment the number of nodes is 67. Without this structural pretreatment, the number of nodes of the context network (as it appears in [12]) is 214-1. 4.4 Second Improvement: Reduction Algorithm In order to improve the computational time in the calculation of the possible minimal set conflicts, we propose the algorithm of Figure 4. Previously we need two new definitions to understand the algorithm better. Definition 5. Observable Context: It is a context with only one component and, at least, one polynomial without non-observable variables. It means that is not necessary to call Gr¨obnerBasis function. For example {N11}and {E3}are observable contexts. Definition 6. Relevant Context: It is a context whose components have, at least, one polynomial whose non-observable variables are also in other polynomial of the context. If we call Gr¨obnerBasis function in other cases, we will not obtain any important results, because it is not possible to eliminate all non-observable variables from, at least, one polynomial of all the context’s components: C is a relevant context if C≡i{ci}|∀ci∈C·∃pi∈ci |∀x∈NonObsVar(pi)·x∈C where ciis a component, pia polynomial and NonObsVar(pi) the set of non-observable variable of pi foreach (cluster in clusters) Set contexts=ObtainContexts(cluster) foreach(context in contexts) if(IsAnObservableContext(context)) AddContext(context) UpdateTables(context) else if (RelevantContext(context)) AddContext(context) CallGr¨obner(context) endif endif endforeach endfor Fig.4. Pseudocode of the reduction algorithm for Relevant Contexts Determination of Possible Minimal Conflict Sets 949 Methods of the Reduction Algorithm: –ObtainContexts(Cluster cluster): This function returns all the contexts of cluster –IsAnObservableContext(Context c): This function returns true if the context is an observable context. –AddContext(Context c): This function adds the context cto table ContextNetwork . –UpdateTables(Context c): This function stores all the polynomial constraints of the context c, in the tables ConstraintNet and Constraint. Here it is not necessary to call Gr¨obnerBasis because the polynomials do not have any non-observable variables. Table 1. CARCs Index CC Constraints 1 1 f11 - f12 - f13 2 1 -f11 t11 + f12 t12 + f11 t13 - f12 t13 3 2 f17 - f18 - f19 4 2 -f17 t17 + f18 t18 + f17 t19 - f18 t19 5 3 f12 + f13 - f16 6 3 f21 - f26 7 3 f12 t12 + f13 t13 - f12 t16 - f13 t16 + f21 t21 - f21 t26 8 4 f18 + f19 - f112 9 4 f27 - f212 10 4 f18 t18 + f19 t19 - f18 t112 - f19 t112 + f27 t27 - f27 t212 11 5 f26 - f27 12 5 f16 - f17 13 5 f31 - f33 14 5 f16 t16 - f17 t17 + f26 t26 - f27 t27 + f31 t31 - f31 t33 –RelevantContext(Context c): This function returns true if the context cis a relevant context. Example: Context: N22,E 1and E2 In this case the component E1do not have any polynomial with all non-observable variable couple with other component To implement this idea, we propose a query to know what are the non-observable variables of a polynomial pwhich are also in the same context cbut in different polynomial. SELECT DISTINCT v.VARNAME FROM VARIABLES v, VARIABLES v2, VARIABLEPOLYNOMIALS cv, POLYNOMIALS c, VARIABLEPOLYNOMIALS cv2, POLYNOMIALS c2, CONTEXTNETWORK rc, CONTEXTNETWORK rc2, WHERE c.ID=pAND c.IDCOMPONENT=rc.IDCOMPONENT AND rc.ID=cAND c.ID=cv.ID AND cv.VARIABLE=v.IDVARIABLE AND v.OBSERVABLE=false AND c.ID<>c2.ID AND rc2.ID=rc.ID AND c2.ID=cv2.ID AND c2.IDCOMPONENT=rc2.IDCOMPONENT AND cv.VARIABLE=cv2.VARIABLE 950 M.T. G´omez-L´opez et al. Comparing the query result and the non-observable variable of the polynomial, we will know if all the non-observable variables of a polynomial are in another polynomial, and therefore if it is a relevant context. –CallGr¨obner(): We build Gr¨obnerBasis function call with information from the tables ContextNetwork, Polynomials,VariablePolinomial and Components. The results will be stored, if they are not in the table Constraints. Finally, the constraint and the corresponding context will be stored in the table CostraintNet. Table 2. Improvement using components cluster and relevant context No reduction Using CC Using CC and RC Number of Contexts 214-1 67 67 Calls to GB. function 214-1 67 7 Obtained Constraints 64 14 14 Elapsed time 4’2 days 7 Seconds 1 Second (This test have been carried out in a Pentium IV-2Ghz with 512 MB) With our solution, we only create 11 contexts and we only call Gr¨obnerBasis function 7 times, because the contexts {N11},{N13},{E3}and {E4}are observable contexts. The reduced algorithm obtains 14 constraints which are shown on Table 1.Table 2 shows the differences among using all contexts (as in [12]) and using our approach. 4.5 Determination of Possible Minimal Conflict Contexts In order to determinate the possible minimal conflicts we apply a constraint-driven algorithm. The following definition is necessary in this process: Definition 7. Context Analytical Redundancy Constraint (CARC): It is a constraint derived from SPM, in such a way that only the observable variables are related. In our approach, the set of CARCs of the system (Table 1) is the union of all the constraints. These constraints were obtained in each components cluster in two ways, directlyfromobservablecontextor usingGr¨obnerBasisfunctiontoeachrelevantcontext. All the relevant context are shown in Figure 5 for the Heat Exchangers example. 5 Conclusions and Future Works This paper proposes a new approach to automate and to improve the determination of possible minimal conflict sets. The determination of components clusters of the system reducesthenumberof contextstoconsider.Onlytherelevantcontextsarestudiedinorder to reduce the computational complexity. In this paper we propose a CDB architecture to store polynomial constraints using standard SQL and JavaTM language to obtain and handle the constraint information. Another advantage is the power of SQL storing and getting information in CDBs.