A Topological-Based Method for Allocating Sensors by Using CSP Techniques

A Topological-Based Method for Allocating Sensors by Using CSP Techniques R. Ceballos, V. Cejudo, R. M. Gasca, and C. Del Valle Departamento de Lenguajes y Sistemas Inform´aticos, Universidad de Sevilla (Spain) {ceballos, cejudo, gasca, carmelo}@lsi.us.es Abstract. Model-based diagnosis enables isolation of faults of a system. The diagnosis process uses a set of sensors (observations) and a model of the system in order to explain a wrong behaviour. In this work, a new approach is proposed with the aim of improving the computational complexity for isolating faults in a system. The key idea is the addition of a set of new sensors which allows the improvement of the diagnosability of the system. The methodology is based on constraint programming and a greedy method for improving the computational complexity of the CSP resolution. Our approach maintains the requirements of the user (detectability, diagnosability,...). 1 Introduction Model-based diagnosis (MBD)[1][2] allows to determine why a correctly designed system does not work as expected. In MBD, the behaviour of components is simulated by using constraints. Inputs and outputs of components are represented as variables of constraints. These variables can be observable and non-observable depending on the sensors allocation. The objective of the diagnosis process is to detect and identify the reason for any unexpected behaviour, and to isolate the parts which fail in a system. The diagnosability of systems is a very active research area in the diagnosis community. A toolbox integrating model-based diagnosability analysis and automated generation of diagnostics is proposed in [3]. The proposed toolbox supports the automated selection of sensors based on the analysis of detectability and discriminability of faults. In this line, a methodology to obtain the diagnosability analysis using the analytical redundancy relations (ARR) was proposed in [4]. This approach is based on an exhaustive analysis of the structural information. The objective is the addition of new sensors to increase the diagnosability. In a previous work [5] a methodology to analyze the diagnosability of a system based in a process algebras was proposed. A framework for testing the diagnosability of a system is defined by using the available sensors, a model abstraction, and some snapshots of sensor readings. In this work, a new approach is proposed in order to improve the computational complexity for isolating faults in a system. Our approach is based on the addition of new sensors. A constraint satisfaction problem (CSP) is obtained in order to select the necessary sensors to guarantee the problem specification. We propose an algorithm for determining the bottleneck sensors of the system in order to improve the computational complexity of the CSP. A CSP is a framework for modeling and solving real problems as a set of constraints among variables. A CSP is defined by a set of variables X={X1,X2,..., Xn}associated with a set of discrete-valued, D={D1,D2,..., Dn}(where every element of Diis represented by set of vi), and a set of constraints C={C1,C2,..., Cm}. Each constraint Ci is a pair (Wi,Ri), where Riis a relation Ri⊆Di1·...·Dik defined in a subset of variables Wi⊆X. The remainder of the paper is organized as follows. Section 2 provides the definitions and notation in order to clarify MBD concepts. Section 3 introduces the basis of our approach. Section 4 describes the CSP generation. Sections 5 shows the greedy method for improving the CSP resolution. Finally, conclusions are drawn and future work is outlined. 2 Notation and Definitions In order to explain our methodology, it is necessary to establish some concepts and definitions from the model-based diagnosis theories. Definition 1. ASystem Model is a finite set of equality constraints which determine the system behaviour. This is done by means of the relations between the non-observable and observable variables (sensors) of the system. Definition 2. ADiagnosis is a particular hypothesis that shows the system differs from its model. Any component could be working or faulty, thus the diagnosis space for the system initially consists of 2nComp - 1 diagnoses [2], where nComp is the number of components of the system. The goal of diagnosis is to identify and refine the set of diagnoses. Definition 3. The Discriminability Analysis [3] determines whether and under which circumstances the considered (classes of) faults can be distinguished. Definition 4. The Diagnosability level is the quotient of the number of the (classes of) faults which can be distinguished each other, and the number of all the possible faults. The size of the possible faults is initially 2comp -1. Definition 5. A set of components Tis a Cluster of components [6], (i) if it does not exist a common non-observable variable of any component of the cluster with any component outside the cluster, and (ii) if for all Q⊂Tthen Qis not a cluster of components. All common non-observable variables between components of the same cluster belong to the cluster, therefore, all the connections with components which are outside the cluster are monitored. A cluster of components is completely monitored, and for this reason the detection of faults inside the cluster is possible without any information from other components which do not belong to the cluster. A more detailed explanation and the cluster detection algorithm appears in [6]. 3 The Basis of the Algorithm Our approach is based on the generation of new clusters of components by allocating sensors in some of the non-observable variables. These new clusters reduce 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. Let Cbe a set of ncomponents of a system, and C1and C2be clusters of n-mandmcomponents such as C1∪C2=C; then the computational complexity for detecting conflicts in C1and C2separately is lower than in the whole system C, since the number of possible diagnoses of the two clusters is (2n-m)+(2 m)-2≤2n-m ·2m-2whichislessthan2 n-1. The clustering process enables isolating the faults of the original system, since the multiple faults which include components of different clusters are eliminated. These kind of faults are transformed into single or multiple faults which belong to only one cluster. The computational complexity for detecting conflicts and discriminating faults in a system is always higher than for an equivalent system divided into clusters. 4 The CSP Problem Specification The objective is to obtain the best allocation of sensors in order to generate new clusters. The allocation of the sensors will be formulated as a Constraint Satisfaction Problem (CSP). A CSP is a way of modeling and solving real problems as a set of constraints among variables. The methodology was applied to the 74181 4-Bit ALU. It is one of the ISCAS85 benchmarks [7]. It includes 61 components, 14 inputs and 8 outputs. Table 1 shows the set of variables and constraints for determining the number and location of sensors for this example. The following variables are included: –nNonObsVar: This constant-variable holds the number of non-observable variables. Table 1. CSP for the 74181 ALU sensors allocation Variable (= initial value) Domain (1) nSensors = {free}D={1, . . . , nNonObsVar} (2) clusterOfCompi={free}D={1, . . . , nComp} (3) clusterDistt={free}D={1, . . . , nComp} (4) sensork={free}D={true, false} Constraints (5) if (sensorE01 =false)⇒clusterOfCompM11 = clusterOfCompM32 (6) if (sensorE02 =false)⇒clusterOfCompM19 = clusterOfCompM32 ... Fig. 1. 74181 ALU –nSensors: This variable holds the number of new sensors. It must be smaller than the number of non-observable variables. –sensork: This set of variables represents the possible new sensors of the system. They hold a boolean value in the interval {true, false},wheretrue implies that there must be a sensor, and false the opposite. –clusterOfCompi: This set of variables represents the cluster associated to each component i. –clusterDistt: This set of variables holds the number of components included in each cluster t. For each common non-observable variable between two components a constraint is generated which guaranties that if there is not a sensor, the two components must belong to the same cluster. Table 1 shows the constraints (5),(6),... that hold this kind of information, and it is based on Figure 1. The final sensors allocation is stored in sensork, and the distribution of the clusters is stored in clusterDisti. The optimization problem can have different objectives, depending on the user and the problem requirements. Two typical goals can be: –To minimize the number of sensors (if the number of clusters is fixed). –To minimize the maximal number of components in each cluster (if the maximal number of sensors is fixed). It is possible to add other constraints in order to guarantee some properties of the solution. For example, in order to guarantee prices, to respect requirements of the customers, to store incompatibilities, to specify problems, ... We have applied the limited discrepancy search (LDS) [8] algorithm in order to search the solution. This algorithm is based on the limitation of the number of discrepancies. 5 Improving the Algorithm: A Greedy Method The computational complexity of a CSP is exponential in general. We propose a method to obtain the most important allocation of the new sensors in order to generate more clusters; that is, the bottlenecks of the system. Our method has two phases: 1. The calculation of the minimal paths: A graph where the nodes represent the components of the system, and the edges represent the connections between each two components (non-observable variables). Each edge has a weight calculated as the number of common non-observable variables between two components. By applying the Floyd’s algorithm (dynamic programming), all the shortest paths between all pairs of nodes is stored. 2. In order to determine which are bottlenecks of the system, each minimal path will vote which sensors are more important. Figure 2 shows this algorithm. sensorsOrder(P) componentVotes[nComp][nNonObsVar] sensorVotes[nNonObsVar] // All the components (1..nComp) votes the variables (sensors) // associated to the minimal paths forEach jbetween 1to nComp forEach Pkfrom component i to component j forEach qbetween 1to length(Pk) = (voteValue / (length(Pk,i,j)·length(Pk)) forEach vincludes in path[q] componentVotes[i][Pk,i,j,q]+= endForEach endForEach endForEach endForEach // Recounting of votes for each sensor forEach sensorjbetween 1to nSensors sensorVotes[j] = 0 forEach ibetween 1to nComp sensorVotes[j] += componentVotes[i][j] / ( ·nComp ) endForEach endForEach return sort(sensorVotes) Fig. 2. Algorithm for obtaining the bottleneck sensors of the system ( O(n2·m2), where nis the number of components and mis the number of non observable variables) Each minimal path will vote for the included non-observable variables of the minimal path. The number of votes are scaled in order to guarantee that each component generates the same total number of votes. These votes allow to generate a sorted list of non-observable variables. This list is composed of the most relevant sensors with the aim of generating new clusters. The bottlenecks of the system represent the best sensors in order to isolate components and faults. The sorted list of sensors enables creating a CSP with less variables to find the solution of the problem in a limited time. Only the solutions included in the combinations of the mbottleneck sensors will be tested, and therefore, the number of possible solutions will be lower than 2m.Theoptimal solution is not guaranteed, but the reduction of computational complexity enables finding a solution in a limited time. Example: In the Alu74181 example the most important sensors are (based on the number of votes): E02(930), E03(878), X28(773), E01(737), E00(583), D00(514), D01(463), D02(326), D03(301),... The other sensors have less than 166 votes. The first 9 sensors are represented by shaded circles in Figure 1. The possible diagnoses in the system are 261 - 1. By using the first 9 selected sensors, the number of clusters is 17 (all with less than 6 components) and the computational complexity is reduced because of the reduction of possible diagnosis to less than 29. 6 Conclusions and Future Work The objective of our approach is the allocation of a set of new sensors in order to improve the computational complexity and diagnosability of a system. The methodology was applied to an standard example, and the results are very promising. It is based only on topological properties. This enables applying this approach to different kinds of systems. As a future work, we are working on new greedy methods to improve the votes counting. Acknowledgements This work has been funded by the Spanish Ministry of Science and Technology (DPI2003-07146-C02-01) and the European Regional Development Fund. References 1. Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence 32 1 (1987) 57–96 2. de Kleer, J., Mackworth, A., Reiter, R.: Characterizing diagnoses and systems. Artificial Intelligence 2-3(56) (1992) 197–222 3. Dressler, O., Struss, P.: A toolbox integrating model-based diagnosability analysis and automated generation of diagnostics. In: DX03, 14th International Workshop on Principles of Diagnosis, Washington, D.C., USA (2003) 99–104 4. Trav´e-Massuy´es, L., Escobet, T., Spanache, S.: Diagnosability analysis based on component supported analytical redundancy relations. In: 5th IFAC Symposium on Fault Detection, EEUU (2003) 5. Console, L., Picardi, C., Ribaudo, M.: Diagnosis and diagnosability analysis using PEPA. In: ECAI 2000, Proceedings of the 14th European Conference on Artificial Intelligence, Berlin, Germany, IOS Press (2000) 20–25 6. Ceballos, R., G´omez-L´opez, M.T., Gasca, R., Pozo, S.: Determination of Possible Minimal Conflict Sets using Components Clusters and Grobner Bases. In: DX04, 15th International Workshop on Principles of Diagnosis, Carcassonne, France (2004) 21–26 7. Hansen, M.C., Yalcin, H., Hayes, J.P.: Unveiling the ISCAS-85 Benchmarks: A Case Study in Reverse Engineering. IEEE Design and Test of Computers 16(3) (1999) 72–80 8. Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Fourteenth IJCAI, Montreal, Canada, IOS Press (1995)