Comparison of Two Distributed Fault Diagnosis Approaches based on Binary Integer Linear Programming (BILP) Optimization ErdalTaskent1and Vicenç Puig2 1 Reliability, Risk, and Safety Engineering Specialist, Izmir, Turkey e-mail: etaskent@hotmail.com 2 Advanced Control System Research Group, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain e-mail: vicenc.puig@upc.edu Abstract constrained, i.e., structural redundancy 1. Therefore, each MSO set will consists of in any case one constraint that can Two distributed fault diagnosis approaches were be used as an ARR. compared, by analogy, to determine which is The global FMSO sets are obtained from the set of local more efficient regarding computational FMSO sets, and the union of locally computed shared sets complexity. The first approach considered all which forms a compound FMSO set that includes at least “locally computed” global and compound sets one shared FMSO set whose fault support is not empty, with minimal cardinality using a heuristic contains equations from at least two subsystems. optimization method while minimizing subsystems interactions (communication). The In this paper, two distributed fault diagnosis approaches second approach aimed at obtaining minimal were compared, by analogy, to determine which is more coupled MSOs for minimizing the number of efficient regarding computational complexity. The first common links between MSOs by adding approach [1] considered generates all “locally computed” constraints in already existing optimal sensor global and compound sets with minimal cardinality using a placement algorithm, which uses BILP, but not in heuristic optimization method while minimizing a distributed context. As a result of comparison, subsystems interactions (communication). The second complexity of both approaches is characterized. approach [4] aimed at obtaining minimal coupled MSOs, for minimizing the number of common links between 1. Introduction MSOs by adding constraints in already existing optimal For complex systems with large-scale distribution and sensor placement algorithm [3] which uses BILP, but not communication constraints, it is appropriate to use in a distributed context. distributed approaches [1]. Distributed approaches are more reliable than centralized approaches in case of the The two considered approaches deal with the problem of failure of the centralized diagnoser (also in decentralized distributed fault diagnosis (local diagnosis with minimum schemes). Moreover, distributed approaches are preferred global diagnosis) that aims to obtain a set of optimal local because of lack of scalability and efficiency of centralized diagnosers that guarantee the same properties as a global solutions during online analysis for large-scale systems diagnoser. Both approaches target to provide the maximum since that can be dealt with complexity by partitioning the possible detectability and isolability that can be achieved system into subsystems [11]. Failures in communication for a system given a set of measurements. links and nodes, and degraded diffusion through the affected nodes by propagation of overloads can lead to In the first approach [1], the Fault-Driven Minimal cascading failures. Moreover, transmission delays Structurally Overdetermined (FMSO) Set concept is increasing the detection time can affect diagnostic introduced, which can be directly used to construct an accuracy [2]. Reducing communication costs in distributed ARR (or residual generator). A heuristic optimization contexts requires minimizing data transfer between local method to obtain the minimal cardinality set of compound subsystems [1]. Therefore, distributed algorithms should FMSO sets is used in [1]. This optimization procedure can consider the requirements of computational and be improved by using BILP optimization as proposed in communication efficiency. To deal with computational [2] utilizing MSOs (each is sensitive to a set of faults) and complexity in distributed algorithms, efficient approaches the structurally equivalence to the compound FMSO sets for the sensor placement analysis and to compute feasible formation shown. MSO sets need to be developed. In the second approach [4], after applying sensor The Minimal Structurally Over-determined (MSO) set placement algorithm proposed in [3], a set of minimum approach offers an alternate way to find all ARRs. coupled set of MSOs are obtained. The adaptation According to [9], a minimal structurally over-determined presented in [4] aims at placing the sensors not only to subsystem (MSO subsystem) is a part of the over- guarantee detectability and isolability properties but also to constrained part of a system graph from which removal of facilitate the partition of a system into various subsystems one constraint will make the subsystem to become just by reducing number of links (communication) within a system. This algorithm also minimizes the number of sensors to be installed thus reducing overall cost. 1 𝑒17 : 𝑣̇4 = (𝑞34 − 𝑞4 ) 𝑒19 : 𝑣4 = ∫ 𝑣̇4 𝑑𝑡 For solving the BILP optimization without the need of 𝐶𝑇4 + 𝑓6 previous computation of the complete MSOs set, which is a computationally complex task, some methods have been 𝑣4 𝑒18 : 𝑞4 = 𝑒20 : 𝑣4 = 𝑦6 developed [7]. In [12], an efficient method to finding all 𝑅𝑣4 the minimal sensors set for maximum fault detectability and isolability from a structural model is proposed. 3. First Approach: Fault-Driven Minimal The structure of the paper is as follows: Section 2 Structurally Overdetermined Sets presents a four tank system used as case study along the paper. Sections 3 and 4 present the two distributed fault 3.1 Background concepts diagnosis approaches. Section 5 presents the comparison of the two approaches using the case study presented in This approach [1], [6] establishes a structure connecting Section 2. Finally, Section 6 draws the main conclusions. FMSOs with minimum number of shared measurements (communication) from neighboring subsystems by an 2. Case Study iterative matching procedure. The global FMSO sets, Ф, are obtained from the set of The case study used to compare both approaches is based local FMSO sets Φ𝑙 , and locally computed shared FMSO on four tank system, proposed in [2], and is shown in Fig. sets Φ 𝑠 and shared CMSO sets Ψ 𝑠 (different subsystems) 1. V1, V2, V3, V4 are the volumes of water in each tank, q12, which forms a compound FMSO set [1], [6]. q23, q34, q4 represents the flows of water through each pipe (P1, P2, P3, P4), u1 and u2 represents the water sources. The shared CMSO (Clear Minimal Structurally Overdetermined) set, whose fault support is empty, u1 u2 corresponds to the measurements (internal (subsystem i) and from neighboring subsystems (shared variables)). S1 S2 The FMSO sets including equations with shared variables are called shared FMSO sets [1], [6]. v2 v3 v4 The shared variables 𝑋𝑖𝑠 = {𝑞12 , 𝑣2 , 𝑞23 , 𝑣3, 𝑞34 , 𝑣4 }, which 𝑋𝑖𝑙 don’t include, are considered as known variables [1], v1 T1 p1 T2 p2 T3 p3 T4 p4 [6]. Compound FMSO set (𝜑 ′ ): A global FMSO set that includes at least one shared FMSO set whose fault support q12 q23 q34 q4 is not empty, contains equations from at least two subsystems [1], [6]. Figure1: Four Tank System [2], [4]. The optimal compound FMSO set selection is performed by a heuristic method. The four tank system is modeled through the following A local FMSO set for any subsystem Σi is also an FMSO equations [4]: set of Σ, hence a global FMSO set [1], [6]. 1 A local FMSO set (𝜑 ∈ Φ𝑖𝑙 )'s equations include local and 𝑒1 : 𝑣̇1 = 𝐶𝑇1 + 𝑓1 (𝑞𝑖𝑛1 − 𝑞12 ) 𝑒4 : 𝑞𝑖𝑛1 = 𝑢1 shared variables of Σi and only involve the fault fi. To achieve detectability of fault fi, only the equations included 𝑣1 − 𝑣2 in 𝜑 required [1], [6]. 𝑒2 : 𝑞12 = 𝑒5 : 𝑣1 = 𝑦1 𝑅𝑣12 + 𝑓2 The concept of compound FMSO set allow us to establish the relation between FMSO sets for the subsystems and 𝑒3 : 𝑣1 = ∫ 𝑣̇1 𝑑𝑡 𝑒6 : 𝑞12 = 𝑦2 FMSO sets for the global system [1], [6]. 1 To illustrate the previous concepts the example used in 𝑒7 : 𝑣̇ 2 = (𝑞12 − 𝑞23 ) 𝑒10 : 𝑣2 = 𝑦3 𝐶𝑇2 + 𝑓3 [1], [2], [6] is used that considers the first tank of the proposed case study 𝑣2 − 𝑣3 𝑒8 : 𝑞23 = 𝑒11 : 𝑞23 = 𝑦4 𝑅𝑣23 + 𝑓4 1 𝑒1 : 𝑣̇1 = (𝑞𝑖𝑛1 − 𝑞12 ) 𝐶𝑇1 + 𝑓1 𝑒9 : 𝑣2 = ∫ 𝑣̇ 2 𝑑𝑡 𝑣1 − 𝑣2 𝑒2 : 𝑞12 = 𝑅𝑣12 + 𝑓2 1 𝑒12 : 𝑣̇ 3 = (𝑞𝑖𝑛2 + 𝑞23 − 𝑞34 ) 𝑒15 : 𝑞𝑖𝑛2 = 𝑢2 𝑒3 : 𝑣1 = ∫ 𝑣̇1 𝑑𝑡 𝐶𝑇3 𝑒4 : 𝑞𝑖𝑛1 = 𝑢1 𝑒5 : 𝑣1 = 𝑦1 𝑣3 − 𝑣4 𝑒13 : 𝑞34 = 𝑒16 : 𝑞34 = 𝑦5 𝑒6 : 𝑞12 = 𝑦2 (1) 𝑅𝑣34 + 𝑓5 Then, the set of shared FMSO sets Φ𝑖𝑠 is {𝜑1 , 𝜑2 , 𝜑3 }: 𝑒14 : 𝑣3 = ∫ 𝑣̇ 3 𝑑𝑡 𝜑1 = {𝑒2 , 𝑒5 }, 𝑤ℎ𝑒𝑟𝑒 : 4. Second Approach: Minimal Coupled MSOs 𝑋𝜑1 = {𝑣1 }, 𝑍𝜑1 = {𝑞1 , 𝑣2 , 𝑦1 , 𝑦2 }, 𝐹𝜑1 = {𝑓2 } 𝜑2 = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 }, 𝑤ℎ𝑒𝑟𝑒 : 𝑋𝜑1 = {𝑣̇1 , 𝑣1 , 𝑞𝑖𝑛1 }, 𝑍𝜑2 = {𝑞1 , 𝑣2 , 𝑢1 }, 𝐹𝜑2 = {𝑓1 , 𝑓2 } 4.1 Background concepts 𝜑3 = {𝑒1 , 𝑒3 , 𝑒4 , 𝑒5 }, 𝑤ℎ𝑒𝑟𝑒 : In the second approach [4], the graph G(V, E) representing 𝑋𝜑1 = {𝑣̇1 , 𝑣1 , 𝑞𝑖𝑛1 }, 𝑍𝜑2 = {𝑞1 , 𝑢1 , 𝑦1 }, 𝐹𝜑2 = {𝑓1 } (2) the set of MSOs is obtained considering that 𝜑 ⊆ Σ𝑖 , 𝑋𝜑 ⊆ 𝑋𝑖𝑙 , 𝑍𝜑 ∩ 𝑋𝑖𝑠 ≠ ∅, and 𝑍𝜑 ⊆ (𝑍𝑖 ∪ 𝑋𝑖𝑠 ) (3)  the MSOs are the graph vertices collected in a set V,  the measured input/output variables are the graph The procedure to compute a global FMSO set 𝜑 𝑐 , starts edges collected in a set E. by searching in the bipartite graph G(X, Г) for a matching that covers each shared variable of 𝑋𝜑𝑠 (𝜑𝑟 is the root Each MSO set will consists of in any case one constraint 𝑟 that can be used as an ARR. MSOs represent the FMSO set) given by Figure 4 in [1], [6]. According to the operational procedure of Algorithm 1 in redundancies in the system and can form the basis for fault [6], [1], it is possible to get the set of all global FMSO sets detection and isolation. As given in [2], for the running Ф from the set of local FMSO sets Φ𝑙 shared FMSO sets example, there were 165 MSOs generated using the Φ 𝑠 and shared CMSO sets Ψ 𝑠 . algorithm proposed in [12]. For example for the first tank, Considering all the possible root FMSO sets, 164 the only MSO = {𝑒1 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 } as 𝑒5 is the redundant compound FMSO sets are computed for this system. equation. The number of ARRs generated in this way will Added to 𝜑4 = {𝑒1 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 } ∈ Φ1𝑙 , which is a local be larger than the set of ARRs found from a single FMSO set for subsystem Σ1, the 165 global FMSO sets are complete matchings (ranking algorithm), and get a set of found for Ф [1], [5]. ARRs for each of these matchings (the number of ARRs was 16 (C1, …, C16) as obtained in [4]). 3.2 Distributed diagnosis The second approach by ARRs in original [4] performs Given a set of faults, measurements and local models for better concerning computational complexity, without the every subsystem, we now construct local diagnosers that need of previous computation of the complete MSOs set. together make the entire system completely diagnosable. For the comparison on a common basis, in this work we Using the Algorithm 2 and definitions of Chapter 2 in [1], used MSOs instead of ARRs in the second approach. The [6], we can develop a local full diagnosis for every analysis is to be shown with MSOs as the same carried out subsystem. by ARRs, judging that the inference will be equivalent. These results demonstrate that all considered faults can After obtaining the model from the sets of equations or set be detected and isolated, e.g. in the considered example, of all MSOs, sensor placement algorithm [3] is applied. detectability is achieved for f1 using 𝜑4 ∈ Φ𝑖𝑙 (local FMSO) of Table 4 in [1], [6] (no additional measurement A binary matrix W = [wij] of size n× k containing the set is needed). For f2, detectability is achieved obtaining a of MSOs (the row set) and sensors (the column set) is compound FMSO set 𝜑9 ∈ Φ1𝑐 lumping 𝜑1 ∈ Φ1𝑠 (as root formed. Matrix W refers to the set of sensor faults an MSO FMSO set) with 𝜓1 ∈ Ψ1𝑠 and 𝜓2 ∈ Ψ2𝑠 . Optimal is sensitive to. In the same way, the binary matrix V = [vij] compound FMSO sets from 164 compound FMSO sets are of size n× l relates the set of MSOs (the row set) and obtained by heuristic method as presented in Table 1. process faults (the column set). These relations are known as fault signature matrix (FSM) [9]. After obtaining W and Φ1𝑐 = {𝜑9 } 𝐹𝜙1 V (the process faults not shown here) according to [4], the 𝜑9 = {𝑒2 , 𝑒5 , 𝑒6 , 𝑒10 } 𝐹𝜑9 = {𝑓2 } values of W and V are used to find various constraints in ---------------------------------------------------------------------- (6) [4], [13]. Φ2𝑐 = {𝜑10 , 𝜑11 } 𝐹𝜙2 𝜑10 = {𝑒6 , 𝑒7 , 𝑒9 , 𝑒10 , 𝑒11 } 𝐹𝜑10 = {𝑓3 } 4.2 Minimizing the coupling between MSOs 𝜑11 = {𝑒8 , 𝑒10 , 𝑒11 , 𝑒13 , 𝑒16 , 𝑒20 } 𝐹𝜑11 = {𝑓4 } In order to facilitate the distributed implementation of the ---------------------------------------------------------------------- fault diagnosis systems, the sensors should be placed such Φ3𝑐 = {𝜑12 } 𝐹𝜙3 that the coupling between MSOs is minimized. This is 𝜑12 = {𝑒11 , 𝑒12 , 𝑒13 , 𝑒14 , 𝑒15 , 𝑒16 , 𝑒20 } 𝐹𝜑12 = {𝑓5 } achieved by adding additional constraints that minimizes ---------------------------------------------------------------------- the number of common links between MSOs [4], [13]. Φ4𝑐 = {𝜑13 } 𝐹𝜙4 First, a constraint that reduces the number of row links 𝜑13 = {𝑒16 , 𝑒17 , 𝑒18 , 𝑒19 , 𝑒20 } 𝐹𝜑14 = {𝑓6 } coupling is written in compact form as Table 1: Optimal compound FMSO sets Φ𝑖𝑐 (i = 1..4) Wi j (0)i p  I ii  0 iu   r i1  0i1 (4) obtained by heuristic method for distributed diagnosis [1], An analog constraint could be added to minimize the row [6]. links coupling as follows Algorithm 2, using a heuristic optimization method, W i j T  0  j y  I j j   c  j1  0 j1 (5) produces a minimal cardinality set of compound (global) The MSOs (the row set (vertices)) are added. FMSO sets while minimizing subsystems interactions. Additional constraints were added in the existing optimal sensor placement algorithm using Binary Integer Linear Programming [4]. Finally, the sensor placement and The algorithm chooses MSOs also in such manner that MSOs optimization problem is solved. these MSOs form a system with minimum coupling by choosing MSOs with minimum number of 1’s in rows and min (c T 01  n)  q  columns (the ideal solution by algorithm for this case is q ,   diagonal matrix, with diagonal elements are 1’s and rest of   other element are 0) but such solution is not possible in this case. A minimum coupled or decoupled system can be subject to: divided into various subsystems in much better way as compared to a highly coupled system. In this case, the  W kI n     system can be divided into two subsystems using the      0 l k V T    1l 1  approach presented in [8]. The first subsystem is formed  Ik W T  q  0  by MSOs, MSOi-1, MSOi (Tank 1 and Tank 2) and the     k 1  (6) second subsystem is formed by MSOs, MSOi+1, MSOi+2  0 C2l k  V fTf      1C 2l 1  (Tank 3 and Tank 4). After dividing the system into two   r  0   V fTs subsystems, the fault signature matrices are created  G2    l .k 1    c   1C k 1  following the decentralized fault diagnosis algorithm in [8]  G3  VssT    2  (summarized in Section II) and after creating fault  W 0 I 0  0i1  signature matrices, fault detection and isolation can be W T I   0  carried out. The proposed algorithm in this chapter allows  0   j 1  obtaining a minimum coupled system by which partitioning of the system into various subsystems become The values of q, λ, rows (r), columns (c) obtained are easy as compared to the subsystems obtained by shown in Table 5.3 in [13]. The result shows that only 4 decentralized fault diagnosis algorithm described in [8] sensors are needed (minimization of sensor) which where we get a highly coupled system using ranking measures the volume variable V1, V2, V3, V4 and only four algorithm [9]. Tank 1 and Tank 4 have no coupling with MSOs will be required to satisfy the detectability and each other and the only coupling between two subsystems isolability of faults in these sensors, minimizing at the is single coupling between MSOi and MSOi+1 (Tank 2 and same time the degree of coupling among the obtained Tank 3), the system obtained is one of the least coupled MSOs according to (4) and (5) [4]. The algorithm chooses system, can be seen in Fig 5.2 in [4]. The other system can these four MSOs since it fulfills the necessary conditions, also be MSOi+3, MSOi+4, MSOi+5 and MSOi+6 shown in Fig 5 firstly the solution obtained allows to isolate the fault in [4] since this system has the same type of coupling which is shown in Table 2 [4] how the solution fulfills the when compared with chosen system but the cost or weight necessary conditions of isolability (since each column is of sensor used for MSOi-1, MSOi, MSOi+1, MSOi+2 is lower different so it is isolable, shown in Table 2 [4]), secondly than the cost of the sensors used for MSOi+3, MSOi+4, the solution obtain is detectable since a unique solution is MSOi+5 and MSOi+6 thus it can be seen that the algorithm obtained, thirdly the solution obtained gives equal number chooses the best system according to least coupling and of 1’s in respective rows and columns shown in Table 3 [4] cost. which is a necessary condition for formation of a system. … , MSOi-3, MSOi-2 V1 V2 V3 V4 MSOi-1, MSOi, MSOi+1, MSOi+2 MSO i-1 1 1 0 0 MSOi+3, … MSO i 1 1 1 0 If we cannot obtain the "best" matching property with all the possible MSOs, the system is not structurally MSO i+1 0 1 1 1 monitorable and we have to place some additional sensors. MSO i+2 0 0 1 1 5. Comparison of Two Approaches Table 2: Fault Isolability [4]. The matrix sizes regarding efficiency in computational complexity for each approach are demonstrated. As the It is seen from the Table 2 that the analysis results in 4 vertices and 6 edges, whereas the ideal solution should comparison objective, the approaches are assessed under produce 4 edges as 1’s are only on the diagonal elements the case of using, for both, a Binary Integer Linear Programming (BILP) for optimization. on FSM. The first approach [1] considered Fault-Driven Minimal Structurally Overdetermined Sets, used a heuristic V1 V2 V3 V4 optimization method to obtain the minimal cardinality set MSO i-1 1 1 0 0 =2 of compound FMSO sets. MSO i 1 1 1 0 =3 To be able to apply a BILP optimization in the first approach, the structurally equivalence of the model of MSO i+1 0 1 1 1 =3 Khorasgani’s approach [2], which uses BILP, to the MSO i+2 0 0 1 1 =2 compound FMSO sets formation and its obtaining the =2 =3 =3 =2 equivalent results with the first approach were shown. Hence, we can use this approach for the first approach [1] Table 3: Equal number of ones in rows and columns [4]. for that to be comparable with the second approach [4] in from each nearest neighbor), the blue colored equation terms of matrix sizes. relates to the shared CMSO set from subsystem i (Si), the Then, the matrix size increase for the second approach black colored equation to the shared FMSO set from Si to obtain minimal coupled MSOs, by adding constraints in (the root), and the yellow colored equation to the shared already existing optimal sensor placement algorithm FMSO set from a neighboring subsystem. (BILP) [3], was demonstrated to see which approach is more efficient. 5.2 Applying Khorasgani’s BILP Approach [2] to the First Approach in Optimizing the 5.1 First approach: Fault-Driven Minimal Compound FMSO Sets by Analogy Structurally Overdetermined Sets [1] Khorasgani [2] used in this approach the Binary Integer This approach [1] used a heuristic method (Algorithm 2) in Linear Programming (BILP) for optimization. optimizing the compound FMSO sets, after generating all The optimization problem takes into account the “locally computed” global and compound sets using relationship between measurements and MSOs (each MSO Algorithm 1 [1], a structure connecting FMSOs with is sensitive to a set of faults). minimum number of shared measurements A distributed MSO selection is to design an algorithm that (communication) from neighboring subsystems: selects MSOi (locally) in a way that we add a minimum number of measurements to develop a local diagnoser 164 compound FMSO sets (agent)for each subsystem. 165 global FMSO sets (1 local FMSO set) The optimal shared variables selection is performed by the Binary Integer Linear Programming (BILP). Using the definitions given in Section 3.1, we can demonstrate a sketch for the optimal compound FMSO set selection, the shared FMSO /CMSO sets, e.g., for MSOk-l = MSOi (measurements) + measurements subsystem 1 (Si): Mi Mo (the part of CMSO set) subsystem 1(Si) from neighboring subsystems for subsystem 1(Si) shared FMSO sets (as root FMSO set) (9) optimal a compound FMSO set 𝜑9 ∈ Φ1𝑐 lumping 𝜑1 ∈ Φ1𝑠 where Mo represents the set of measurements (not belonging to subsystem i) we need to communicate to the with 𝜓1 ∈ Ψ1𝑠 and 𝜓2 ∈ Ψ2𝑠 . subsystem Si along with the set of measurements, Mi associated with the subsystem Si. subsystem 1(Si) subsystem 2 (S2) MSOi corresponds, in the optimal compound FMSO set, to shared CMSO set (neighboring susbsystems) the shared FMSO set and the part of the shared CMSO set shared (variable) CMSO set as the internal measurements in subsystem i (Si). (also shared FMSO sets) from neighboring subsystems Mo corresponds, in the optimal compound FMSO set, to the part of the shared CMSO set as the measurements from (7) the neighboring subsystems of Si. The shared CMSO set, whose fault support is empty, According to [2], using a MSO is equivalent to using the corresponds to the internal measurements (Si) and measurements (Mi) that are included in the MSO, and we measurements from neighboring subsystems (shared need to include this in the optimization problem. For variables). example, consider MSO11, it has three measurements M11 = {u1, y1, y2}. Using MSO11 in a local diagnosis subsystem From the Table 1, Φ𝑖𝑐 (i = 1..4) by a heuristic method, 5 means we need to communicate these measurement optimal compound FMSO sets for the 4 subsystems are streams to that subsystem to achieve global diagnosability obtained from 164 compound FMSO sets as given below: for the faults that belong to that subsystem. Φ1𝑐 = {𝜑9 }, Φ2𝑐 = {𝜑10 , 𝜑11 }, Φ3𝑐 = {𝜑12 }, Φ4𝑐 = {𝜑13 }. We need to demonstrate that this model can be considered as structurally equivalent to the compound 𝜑9 = {𝑒2 , 𝑒5 , 𝑒6 , 𝑒10 } FMSO set model of the first approach, and hence, we can 𝜑10 = {𝑒6 , 𝑒7 , 𝑒9 , 𝑒10 , 𝑒11 } use this approach, which uses BILP, in the first approach 𝜑11 = {𝑒8 , 𝑒10 , 𝑒11 , 𝑒13 , 𝑒16 , 𝑒20 } for that to be comparable with the second approach: 𝜑12 = {𝑒11 , 𝑒12 , 𝑒13 , 𝑒14 , 𝑒15 , 𝑒16 , 𝑒20 } As given in [2], for the running example there were 165 𝜑13 = {𝑒16 , 𝑒17 , 𝑒18 , 𝑒19 , 𝑒20 } (8) MSOs generated, 3 measurements in the subsystem 1, and 8 measurements for the entire system. The red colored equation relates to the shared CMSO set (variable) from neighboring subsystems, corresponding minimal subsystems interactions (one or possibly more Subsystem 1 has two faults of interest, and the goal is to be measurements from the other subsystems, as given in the able to isolate them from any of the 6 faults in the cost function in Eq. 9 [2], the cost will incur only the complete system. external measurements from the neighboring subsystems Therefore, to solve the optimization problem in [2] for and not the measurements as internal in Si and as the use subsystem 1 (S1), matrix A has of shared FMSO set from a neighboring subsystem with the root shared set (Si). 177 rows (equal to the number of constraints): - 2 constraints to guarantee the local detectability Therefore, we could decide that both application lays on of f1 and f2, the same basis and Khorasgani’s approach using BILP - 10 constraints to guarantee the local isolability of (i.e., the optimization stage) obtains the optimal f1 and f2 from the other faults, and equivalent results so as to be used in the first approach for - 165 constraints to capture the relationship comparison. between the MSOs and the measurements and The above case is that the shared FMSO set’s fault support 173 columns (equal to the number of binary variables): is not empty and then there are two faults (f4, f5) included - 8 constraints for the measurements in 𝜑11 corresponding two shared FMSO sets, but, since the - 165 constraints for the MSOs and local diagnoser 𝜑12 will respond to its subsystem’s (S3) fault (f5), in achieving global diagnosability, 𝜑11 can act b is a vector with 177 elements (equal to the number of for only the fault (f4) of the root shared set (S2) not the one constraints). (f5) of the shared set in the neighbor (S3). Table 5 shows, in the MSOk-l form, the minimum number Alternatively by another algorithm, a different compound of shared measurements (from neighboring subsystems FMSO set for S2 can also optimally select the same and possibly one from each neighbor) obtained with the measurements from the neighbors in Table 5 (possibly BILP Optimization. more than one from each first order (nearest) neighbor) which provides a practical advantage by not needing to Table 5: Set of augmented measurements to each transfer data over long distances, which can be costly and subsystem model [2]. error-prone [2]. Subsystem Set of augmented measurements This approach [2] now establishes a structure S1 MSOk - l y3 (S2) connecting FMSOs, in compound, with minimum number S2 MSOk - l y2, u2, y6 (S3, S1, S4) of shared measurements from neighboring subsystems. S3 MSOk - l y4, y6 (S2, S4) S4 MSOk - l y5 (S3) If we apply Binary Integer Linear Programming (BILP) instead of a heuristic method in the first approach, for the From the Table 6, the solution obtained in the first four tanks (S1, S2, S3, S4), similar to the analysis in [2]: approach by heuristic method the measurements from neighboring subsystems as the CMSO sets (𝜓𝑖 ∈ Ψ𝑖𝑠 ) of subsystem 1 (S1), matrix A has 𝜑9,10,11,12,13 (5 optimal compound FMSO sets Φ𝑖𝑐 , (i = 1..4) for the 4 subsystems) is shown. 176 rows (equal to the number of constraints): - 164 constraints to capture the relationship Table 6: Set of augmented measurements to each between the FMSOs and the measurements subsystem model – first approach solution by heuristic In this case, 164 constraints are used for the relationship method [1]. corresponding to the number of all compound FMSO sets computed in the first approach except for the one local S1 𝝋𝟗 y1, y2 y3 (S2) FMSO set. S2 𝝋𝟏𝟎 y3, y4 y2 (S1) Since we have 165 global FMSOs (165 constraints) in this 𝝋𝟏𝟏 y3, y4 y5, y6 (S3, S4) approach as given in [1], the total number of columns (c) S3 𝝋𝟏𝟐 u2, y5 y4, y6 (S2, S4) for each subsystem is 173. S4 𝝋𝟏𝟑 y6 y5 (S3) for all the subsystems, the matrix A: As seen from the Table 5 and Table 6, all the measurements (one from each neighbor) from the total (r) total (c) neighboring subsystems are the same except for S2, u2 in subsystem 1 (S1) [2] is selected instead of y5 in [1] from the same subsystem (S3). This difference comes from the use of shared FMSO 2 faults 2 10 164 176 (r) 173 (c) set from a neighboring subsystem (𝑒13 used in 𝜑11 ) in this 3 measurements approach [1] (see equation (8) and Table 5). For both subsystem 2 (S2) application ([2], Table 5 and [1], Table 6), subsystem 2 is 2 faults 2 10 164 176 173 the only subsystem that shares a variable with a second 2 measurements order connected subsystem, all the other subsystems only need to communicate with their first order (nearest) subsystem 3 (S3) connected subsystems. To minimize the number of 1 fault 1 5 164 170 173 2 measurements subsystem 4 (S4) (165 + 10 + 45) = 220 rows 1 fault 1 5 164 170 173 1measurement n (λ) + k (q) = 165 + 8 = 173 columns (10) The analysis results in as (220, 173) element matrix. This is the matrix size for the four tank example, before for the system (S1, S2, S3, S4): adding constraints (the rows) in the following, as obtained with the existing optimal sensor placement algorithm. 176 + 176 + 170 + 170 = 692 (r) The matrix size by adding additional constraints, the row The analysis results in (692, 173) element matrix. This set, to choose MSOs that form a system with minimum matrix size is to be processed if we apply BILP to the first coupling (communication) was shown below: approach for optimizing the compound FMSO sets, which is to be compared with the one to be obtained in Section From Section 4.2, using equations (4) and (5) [4], we 5.3. checked how these additional constraints act. 5.3 Second Approach: Minimal Coupled MSOs (W165× 8 0165 × 165- I165× 165 0 165 × 2) (r)165 × 1≤ 0165× 1 The analysis is performed for the four tank example: (W8× 165 08 × 6 - I8× 8) (c)8 × 1≤ 08× 1 As obtained in the second approach in Section 4.1, using the methodology in [3] as the first step: (13) n number of MSOs = 165 = λ, For each constraint, with the values as the numbers of MSOs (n (λ) = 165) and (candidate) sensors (q = 8) in columns, a simple validation performed first to see that the k number of candidate sensors = 8 =q, corresponding number of columns does not change by this approach as 173 in total as a joint effect of the constraints, q = 8, λ= 165, and thus maintaining the number of columns obtained with using [3]: l number of process faults =2 (11) The rows added for each constraint as 165 and 8 are given in equation (13). W kI n  165 × 8 0lk  V T  1l1 8 × 165 Ik W T q 0 k 1 ≤ (12) 0C l k  V ffT   1C l 1 If we add the number of rows obtained with two additional 2 ( ) 2 constraints: G2  V fsT 0l .k 1 165 + 8 =173 rows G3 V T 1C k 1 ss ) 2 ( ( ) And totally, 173 rows are added. The number of rows (i.e., constraints) As many as the column number before adding constraints the rows are added. • The MSO selector constraints (11) in [3] involve If we add the additional number (173) of rows (constraints) n (λ) = 165 rows obtained in this section after adding constraints (the rows) in eq. (13), to the number of rows in (220, 173) matrix. • The detectability constraints (14) and (17) in [3] involve (220 + 173) = 393 rows l + k (q) = 10 rows We obtain the resulting (393, 173) element matrix. • The isolability constraints (20), (24), and (30) in [3] In comparison, it is shown that for optimization the involve second work [4] performs better as (393, 173) element matrix than the first approach [1] processing a (692, 173) 𝐶2𝑙 + 𝑙. 𝑘 + 𝐶2𝑘 = 1 + 16 + 28 = 45 rows matrix in terms of computational complexity. 6. Discussion and Conclusions R) and SCAV (ref. DPI2017-88403-R), the FPI grant (ref. BES- 2014-068319). Two distributed fault diagnosis approaches were compared, by analogy (i.e., the matrix sizes) to determine their efficiency in the case of using, for both, a Binary References Integer Linear Programming (BILP) for optimization using [1] Pérez, C.G., Chanthery, E., Travé-Massuyès, L. and a four-tank system example. Sotomayor, J. Fault-Driven Minimal Structurally Though, as demonstrated in the first approach [1], the Overdetermined Set in a Distributed Context. 27th Fault-Driven Minimal Structurally Overdetermined International Workshop on Principles of Diagnosis: DX- (FMSO) Sets can be directly used to construct an ARR or 2016, Denver, United States. 2016 residual generator, the matrix sizes to be processed for [2] Khorasgani, H., Biswas, G. and Jung, D. Minimal computing the optimal sets (apart from the computation of Structurally Overdetermined Sets Selection for Distributed all global (compound) sets) were assessed. Fault Detection. 26th International Workshop on Principles Since the first approach used a heuristic optimization of Diagnosis: DX-2015, Paris, France, 2015 method to obtain the minimal cardinality set of compound [3] Rosich, A., Sarrate, R., Nejjari, F. Optimal Sensor FMSO sets, we applied Khorasgani's BILP optimization Placement for FDI using Binary Integer Linear method, utilizing a structurally equivalent model to the Programming. 20th International Workshop on Principles of compound FMSO sets formation, to the first approach to Diagnosis: DX-2009, Stockholm, Sweden. decide that Khorasgani’s approach using BILP obtains the [4] Gupta, V., Puig, V., Blesa, J.A methodology for distributed equivalent results so as to be used in the first approach for fault diagnosis, Journal of Physics: Conference Series, the purpose of comparison. Volume 783, 2017. Then, we applied Binary Integer Linear Programming [5] Rosich, A. Sensor placement for fault diagnosis based on (BILP) instead of a heuristic method for the four tanks to structural models: Application to a fuel cell stack system, find the matrix size to be processed in this case. PhD Thesis, UPC, Barcelona, Spain, 2011. In the second approach [4], minimum coupled MSOs for [6] Pérez, C.G., Carlos Gustavo Pérez Zuniga, Structural minimizing the number of common links (communication) analysis for the diagnosis of distributed systems, PhD between MSOs are obtained by adding constraints (the row Thesis, LAAS-CNRS, Toulouse, France, 2017. set/MSOs) in already existing optimal sensor placement [7] Sarrate, R., Nejjari, F., Rosich, A. Model-based Optimal algorithm [3], which uses BILP, but not in a distributed Sensor Placement Approaches to Fuel Cell Stack System context and thus uses the complete set of MSOs. Fault Diagnosis, 8th IFAC International Symposium on For the comparison on a common basis, in this work we Fault Detection, Supervision and Safety for Technical used MSOs instead of ARRs in performing the analysis of Processes. Mexico City, 2012 the second approach. [8] Gupta, V., Puig, V. Decentralized Fault Diagnosis using In the original second approach [4], in applying sensor Analytical Redundancy Relations: Application to a Water placement algorithm, for solving the BILP optimization Distribution Network. European Control Conference (ECC), without the need of previous computation of the complete 2016 MSOs which requires a high computation time, the ARRs (the model) were generated using ranking algorithm and [9] M.Blanke, M. Kinnaert, J. Lunze, M.Staroswiecki. Diagnosis and Fault-Tolerant Control. Springer. 3rd Edition, all the possible ARRs in addition to the primary ARRs 2016. obtained from the set of system model equations. After solving the sensor placement problem, the [10] Puig, V., Ocampo-Martinez, C. Decentralised Fault algorithm ensures a set of minimum coupled (minimal Diagnosis of Large-scale Systems: Application to Water sensors) set of MSOs for maximum fault detectability and Transport Networks, 26th International Workshop on principles of Diagnosis, Paris, France, 2015. isolability. In comparison, it is shown that the second work [11] Roychoudhury I, Daigle M, Bregon A. A Structural Model performs better in terms of the matrix sizes to handle. Then Decomposition Framework for Systems Health again, it is preferential to use the second approach with Management, IEEE Aerospace Conference, Big Sky, MT, ARRs in original [4] concerning computational USA, 2013. complexity, in that case resulting as (95, 24) matrix. [12] M. Krysander, J. Aslund and M. Nyberg. An efficient In addition to this work, adding redundant sensors (the algorithm for finding minimal over-constrained sub-systems column set) to obtain the ideal solution (best matching) in for model-based diagnosis. IEEE Transactions on Systems, the fault signature matrix can be shown. Man and Cybernetics, Part A: Systems and Humans, vol. As the most efficient approach from the required MSO 38(1), pp. 197-206, 2008. sets point of view causal computation approach can be [13] Gupta, V., Distributed Fault Diagnosis in Large Scale studied which needs no MSO sets. Industrial Process, PhD Thesis, Universitat Politècnica de Catalunya UPC, Barcelona, Spain, 2016 The uncertainty in the system could be studied by using statistical and stochastic methods for robust distributed fault detection and isolation. Acknowledgements This work was partially funded by the Spanish State Research Agency (AEI) and the European Regional Development Fund (ERFD) through the projects DEOCS (ref. DPI2016-76493-C3-3-