Optimal Sensor Placement Problem for an Electro–pneumatic Actuator Kornel Rostek1 1 Warsaw University of Technology, Poland e-mail: rostek@mchtr.pw.edu.pl Abstract method was further improved in [7] and [8]. There, FDI re- quirements were specified as linear constraints. As the cost In this paper, a method for formulating and solv- function is linear, the problem falls into Binary Integer Lin- ing the optimal sensor placement problem for an ear Programming (BILP). It can be efficiently solved with a electro–pneumatic actuator is presented. The ap- branch-and-bound algorithm with standard Linear Program- proach minimizes the number of additional sen- ming (LP) solver. Those methods were thoroughly com- sors while maintaining maximum possible diag- pared in [9]. Budgetary constraints were analyzed in [10]. nosability and isolability. The proposed strategy The branch-and-bound algorithm is used to obtain the opti- is based on a Binary Diagnostic Matrix. Proposed mal solution. Regardless of chosen method, simple, qualita- isolability measure distinguish weak and strong tive methods of analysis of fault isolability are insufficient. isolability. It uses the branch-and-cut algorithm Generalized, quantitative method of fault isolability analysis to find a solution. is required. This paper presents the method of an optimal sensor 1 Introduction placement for diagnostic purposes using linear constraints and a linear objective function. The method uses a new The quality of diagnosis is often characterized using the measure of isolability proposed by the author. The main fault isolability. Different methods of Fault Detection and contribution of this metric is that both weak and unidirec- Isolation (FDI) can be compared with it. tionally strong isolability properties are considered and dis- Available measurements strongly affect the performance tinguished. Various additional optimization constraints are of an FDI system for a given industrial process. Additional analyzed. The model of an electro–pneumatic actuator was sensors providing additional information about a process used as an example illustrating the procedure. can improve the performance of an FDI system. From a The paper is organized as follows. In Section 2, the pre- practical point of view, it is vital to achieving the best possi- liminary definitions used in this work are given. Section 3 ble FDI system performance with minimal additional costs. defines the measure of fault isolability. Section 4 presents The problem of optimal sensor selection can be understood the proposed optimization procedure. Section 5 describes as a combinatorial problem of selecting the optimal set of the example of an electro–pneumatic actuator. Conclusions measurements. and final remarks section finalizes this paper. In recent years, numerous papers discussed different problems of the optimal sensor placement. The required minimum fault isolability of the diagnostic system is usu- 2 Preliminaries ally considered [1; 2] . Some of the proposed methods also A signal sensitive to faults is considered as a diagnostic sig- maximize designed fault isolability using heuristic methods, nal in FDI. A symptom is a value of a diagnostic signal e.g., genetic algorithms [3]. which indicates fault or faults. In the case of multi-valued The model-based FDI considers faults as deviations from diagnostic signals, one fault type may generate different val- nominal values of process parameters or as unknown pro- ues of each diagnostic signal. A fault signature is a vector cess inputs. If system model and measurements behave of diagnostic signal values associated with a particular fault differently, then faults are detected. In [4], a method for [11]. In case of multi-valued diagnostic signals, multiple searching for the optimal sensor set based on Analytical Re- values of a single diagnostic signal can be associated with dundancy Relations (ARRs) is proposed. First, all ARRs a fault. The specific vector of values of diagnostic signals are found under the assumption that all sensor candidates is called an alternative signature [11]. In the case of bi- are installed. Then, a sensor set is selected that minimizes nary diagnostic signals, each fault has exclusively one alter- the cost while satisfying detectability and isolability require- native signature, while for multi-valued diagnostic signals ments. However, this solution is computationally expensive. there might be multiple alternative signatures. A modified, incremental approach, using Minimal Struc- There are different definitions of fault isolability. Gen- turally Overdetermined (MSO) sets, was proposed in [5]. In erally, faults are considered isolable when at least some of [6] the Binary Integer Programming is used to find the opti- their signatures are different [12]. mal sensor set using the set of all possible MSO sets. FDI re- Binary Diagnostic Matrix (BDM) or Incidence Matrix is a quirements were ensured using non-linear constraints. The form of notation of a relationship specified by the Cartesian resulting problem is computationally difficult to solve. This product of diagnostic signals sets S = {sj : j = 1, 2, ..., J} the fault fm , and each alternative fault signature φ(fm ) ex- Table 1: The Binary Diagnostic Matrix example. 1 in j th cludes the fault fk . row and ith column means that fi is detectable with signal sj . In Table 1 signature V2 is excluding f1 . Opposite is not true so they are not strongly isolable. f1 f2 f3 f4 f5 f6 f7 f8 Commonly, in FDI an exoneration assumption is ac- s1 1 1 1 1 cepted. It states that a lack of symptoms exonerates a fault. s2 1 1 1 1 It means that all symptoms must appear for a fault isolation. s3 1 1 1 1 This assumption is not always valid. Due to dynamics of s4 1 1 1 symptoms and different sensitivity to faults, they may not s5 1 1 appear simultaneously or may even not appear at all. and faults F = {fi : i = 1, 2, ..., n}. Each row displays 3 Measure of isolability sensitivity of a given diagnostic signal to each fault. Each An implementation of the measure of isolability for a Binary column Vi = [v1,i , v2,i , , vJ,i ]T of binary diagnostic matrix Diagnostic Matrix was proposed in [14]. The value of this V can be associated with a fault fi . Often column Vi is measure is calculated in two steps: called signature of fault fi . An example of binary diagnostic 1. Calculate the value of the following discrete function matrix is shown in Table 1. for all possible ordered pairs of faults: The basic definition of isolability can be formulated in the context of BDM in the following way [13]: D: F ×F → {0, 1}, (1) Definition 1. where: F is the set of faults and fk ∈ F, k = 1 . . . K Faults fk , fm ∈ F are weakly isolable if their signatures are particular faults. It is assumed that the value are different. D (fk , fm ) = 1 when the appearance of all symptoms In the example from Table 1 all faults with exception of of the fault fk excludes the fault fm . If this is not true, a pair (f2 , f3 ) are weakly isolable. A weak isolability in then D (fk , fm ) = 0. some applications is not sufficient. It is possible that due to 2. Calculate the value of the measure as: a different sensitivity of diagnostic tests or process dynam- K K ics some signals appear earlier and match a signature of a 1 XX ψ= D (fk , fm ). (2) different, weakly isolated fault. In the above example, the (K − 1) K m=1 k=1 appearance of only the signal s1 may be insufficient to indi- m6=k cate the fault f1 reliably. Later signals s2 or s3 may appear indicating faults f2 , f3 or f5 . Therefore a stronger isolabil- In the case of multi-valued diagnostic signals, the condi- ity property is required [13]. tional isolability metric was proposed in [15]. The first step of calculation of the value of the proposed metric (1) needs Definition 2. to be slightly modified in order to take into account condi- A structure is unidirectionally strongly isolating if it is tional isolability. Instead of assigning exclusively values 0 weakly isolating and if no column in the structure matrix or 1 to each ordered pair of faults, the D (fk , fm ) can take can be obtained from any other column by turning an arbi- any value from the range [0, 1]. Let D (fk , fm ): trary number of “1”s into “0”s or by turning an arbitrary number of “0”s into “1”s. card ({φ : φ ∈ Φ(fk ) ∧ φ excludes fm }) D (fk , fm ) = , In a unidirectionally strongly isolating structure, each pair card (Φ(fk )) of faults differs in at least two entries. Firstly, where “1” is (3) in the first column and “0” in the other one and secondly, where: Φ(fk ) is the set of all alternative signatures of the where “0” is in the first column and “1” in the other one. A fault fk . weak isolability is a necessary condition for a strong isola- The formula (3) generalizes the first step of calculation bility. of the proposed measure. It can be understood as a fraction In Table 1 faults f5 and f6 are unidirectionally strongly of all alternative signatures of fk that excludes fm . In the isolable. case of binary diagnostic signals, there is always only one From Definition 2 following statement can be extrapo- alternative signature φ(fk ). The value of D (fk , fm ) is then lated: equal to 0 or 1. Consequently, in the case of binary diag- nostic signals, the formula (3) is equivalent to formulation Definition 3. below the formula (1). The signature Vi is excluding a fault fk if Vi is different than The proposed metric of isolability makes it possible Vk and Vi cannot be obtained from Vk by turning “1”s into to distinguish unidirectional strong isolability from weak “0”s. isolability. If D (fk , fm ) = 1 ∨ D (fm , fk ) = 1, then the Opposite does not have to be true. signature of the fault fk excludes the fault fm or the signa- Definition 4. Faults fk , fm ∈ F are weakly isolated iff each ture of the fault fm excludes the fault fk . Therefore, accord- alternative fault signature φ(fk ) excludes the fault fm , or ing to Definition 4, the faults are weakly isolable. Moreover, each alternative fault signature φ(fm ) excludes the fault fk . if D (fk , fm ) = 1 ∧ D (fm , fk ) = 1, then the signature of the fault fk excludes the fault fm and the signature of the If faults are mutually excluding each other, then they are fault fm excludes the fault fk . Thus, faults fk and fm are strongly isolable. unidirectionally strongly isolable as defined in Definition 5. Definition 5. Faults fk , fm ∈ F are unidirectional strongly The value of the presented measure of isolability can be isolable iff each alternative fault signature φ(fk ) excludes interpreted as a mean fraction of all diagnoses that can be PK PK excluded, after the occurrence of a single fault. The measure The objective function maximize 16 k=1 m=1 xDk,m x m6=k of isolability takes the maximal value when all pairs of faults with constraints (6) is a difficult, constrained, non-linear are unidirectionally strongly isolable. In such a case, each optimisation problem. single fault signature excludes (K −1) other faults (the fault PK PK does not exclude itself). Then k=1 m=1 D (fk , fm ) = 4.1 Additional constraints m6=k (K − 1) K and the value of the measure of isolability is Fault detectability equal to (K−1)K (K−1)K = 1. Generally, it is not possible to determine which faults will be detectable before solving the basic optimal sensor place- 4 Problem formulation for BDM ment problem. In practice, detectability of the most impor- In this section, only binary diagnostic signals are analyzed. tant faults is often required. In a special case, this require- If a fault fk is unisolable from fm , then D(fk , fm ) is equal ment can refer to all faults. to 0. Otherwise, it is equal to 1. The value of D(fk , fm ) can The detectability of a given fault can be interpreted as the be calculated in the following way: possibility to distinguish this fault from the state without  faults. To satisfy detectability requirements, an additional xDk,m = D(fk , fm ) = max xsj : vj,k 6= 0 ∧ vj,m = 0 , constraint can be added in the following way: x sj (4)  D(fk , faultless state) = max xsj : vj,k 6= 0 = 1. (7) where: xsj is the decision variable, which indicates that x sj j th diagnostic signal is available. This formula states that This ensures that there is at least one signal sensitive to fault D(fk , fm ) is equal to 1 if at least one diagnostic signal sj is fk . sensitive to the fault fk and not sensitive to the fault fm . The If the problem with this additional constraint becomes in- shorthand notation xDk,m will be used instead of D(fk , fm ) feasible, then it is impossible to meet the detectability re- as a variable in the description of an optimal sensor place- quirements. ment problem. Similarly, the variable xsj can be expressed as: Example 2. The detectability requirements for the problem introduced in 0 ≤ xsj ≤ min {xi : xi is necessary to calculate sj } , Example 1 can be formulated in the following way: xi (5) f1 : max{xs1 } = xs1 = 1, where: xi is the decision variable, which indicates that ith f2 : max{xs1 , xs2 } = 1, (8) sensor is available. If even one of the sensors necessary for the diagnostic signal sj is unavailable, then this signal f3 : max{xs1 , xs2 , xs3 } = 1. cannot be used. The inequality relation ≤ is used, because, Isolability constraints even if all required sensors are available, the diagnostic sig- nal may be not of interest, e.g., due to a too high cost of For some critical subset of faults, it may be beneficial to re- development of necessary models. quire the solution of the optimal sensor placement problem Example 1. to isolate these faults. These requirements can be fulfilled In Tab. 2 an example of a simple BDM is presented. There by introducing additional equality constraints. For example, are three faults and three diagnostic signals. Each diagnos- if it is important that a fault fk is isolable from a fault fm , tic signal requires two sensors to be available. then the following constraint should be added: xDk,m = 1. (9) Table 2: Simple BDM and sensor requirements for diagnos- If unidirectional strong isolability is desired, then two tic signals. constraints should be added: f1 f2 f3 xDk,m = 1, s1 (x1 , x2 ) 1 1 1 (10) s2 (x1 , x3 ) 1 1 xDm,k = 1. s3 (x2 , x3 ) 1 If the isolability requirements cannot be satisfied, then the constrained problem will be infeasible. The following equations can be constructed: Example 3. For the diagnostic system introduced in Example 1, if it is xs1 ≤ min{x1 , x2 }, required that the fault f3 is isolable from both f1 and f2 , xs2 ≤ min{x1 , x3 }, then the following constraints should be added: xs3 ≤ min{x2 , x3 }, xD3,1 = 1, xD2,1 = D(f2 , f1 ) = max{xs2 } = xs2 , (11) (6) xD3,2 = 1. xD3,1 = D(f3 , f1 ) = max{xs2 , xs3 }, xD3,2 = D(f3 , f2 ) = max{xs3 } = xs3 , 5 Optimal sensor placement problem for an xs1 , xs2 , xs3 ≥ 0, electro–pneumatic actuator xi , ssj ∈ {0, 1}, i, j = 1 . . . 3. To demonstrate an example of the optimal sensor placement formulation, an electro–pneumatic valve actuator will be The pairs of faults for which D(fk , fm ) = 0 were omitted. discussed. Fig. 1 illustrates the actuator [16]. It consists Air pressure sensor PVP minimize xCV + xCV I + xP s + xX f4 x E/P K K f1 f5 1 XX s.t. xDk,m = 0.3, SP CV CVI Ps Pz 30 m=1 k=1 Electronic controller Air supply system m6=k f3 f2 f6 xs1 ≤ xX , PVX X F xs1 ≤ xCV , Positioner feedback Pneumatic servo-motor Control valve xs2 ≤ xX , xs2 ≤ xCV I , Figure 1: Causal graph of the electro–pneumatic actuator xs3 ≤ xX , [16]. SP – set point, CV – control value, CVI – control value xs3 ≤ xP s , of the electro–pneumatic transducer, PVP – pressure mea- surement in servo–motor chamber, PVX – stem displace- xs4 ≤ xP s , ment, F – flow rate. xs4 ≤ xCV , xs5 ≤ xP s , xs5 ≤ xCV I , (13) of an electronic controller, an electro–pneumatic converter, xD2,1 ≤ xs3 , a servo–motor, a control valve, and an electro–mechanical xD3,1 ≤ xs3 , stem position feedback. The list of available measure- ments includes the control value CV, the control value of xD5,1 ≤ xs3 , the electro–pneumatic transducer CVI, the stem displace- xD6,1 ≤ xs3 , ment measurement X, and the pressure in the chamber of the servo–motor. Tab. 3 lists the considered faults. Tab. 4 xD1,4 ≤ xs1 + xs2 , xD2,4 ≤ xs1 + xs2 + xs3 , xD3,4 ≤ xs1 + xs2 + xs3 , Table 3: List of actuator faults. xD5,4 ≤ xs1 + xs2 + xs3 , Fault Faulty component f1 E/P transducer xD6,4 ≤ xs1 + xs2 + xs3 , f2 Pneumatic servomotor xCV , xCV I , xX , xP s , xsj ,xDk,m ∈ {0, 1}, f3 Position feedback f4 Pressure sensor fault k, m = 1 . . . 6, j = 1 . . . 5. f5 Supply air pressure f6 Control valve To ensure that all faults are detectable the following con- straints should be added: f1 : xs1 + xs2 + xs4 + xs5 ≥ 1, specifies the considered binary diagnostic matrix. f2 : xs1 + xs2 + xs3 + xs4 + xs5 ≥ 1, f3 : xs1 + xs2 + xs3 + xs4 + xs5 ≥ 1, (14) Table 4: List of considered diagnostic signals for the f4 : xs4 + xs5 ≥ 1, electro–pneumatic actuator. f5 : xs1 + xs2 + xs3 + xs4 + xs5 ≥ 1, Signal Residual f1 f2 f3 f4 f5 f6 f6 : xs1 + xs2 + xs3 + xs4 + xs5 ≥ 1. s1 X − f (CV ) 1 1 1 1 1 s2 X − f (CV I) 1 1 1 1 1 The problem (13) with (14) was solved using a Coin– s3 X − f (Ps ) 1 1 1 1 or branch–and–cut (Cbc) solver and a PuLP modeler. The s4 Ps − f (CV ) 1 1 1 1 1 1 following solution was returned by the solver: xCV = s5 Ps − f (CV I) 1 1 1 1 1 1 1.0, xCV I = 0.0, xP s = 1.0, xX = 1.0. Consequently, the optimal sensor set for given constraints is {CV, P s, X} and the resulting BDM is presented in Tab. 5. All of the con- Using Tab. 4, the maximum value of the metric of isola- bility ψ can be calculated as: Table 5: Optimal BDM for the electro–pneumatic actuator. f1 f2 f3 f4 f5 f6 1 XK XK 9 s1 1 1 1 1 1 ψ= m=1 D (fk , fm ) = = 0.3. s3 1 1 1 1 (K − 1) K k=1 m6=k 30 (12) s4 1 1 1 1 1 1 To find the diagnostic structure with ψ = 0.3 and the min- imum number of required sensors the optimal sensor place- sidered faults are detectable and the value of the isolability ment problem should be formulated as (13). measure is ψ = 0.3. 6 Conclusion [10] Ramon Sarrate, Fatiha Nejjari, and Albert Rosich. In this paper, the sensor placement problem was addressed Sensor placement for fault diagnosis performance for an electro–pneumatic actuator. A key contribution of this maximization under budgetary constraints. In 2nd In- work is the introduction of a new measure of fault isolabil- ternational Conference on Systems and Control, 2012. ity as an objective function or constraint to Linear Program- [11] Michał Bartyś. Generalized reasoning about faults ming problem. It distinguishes weak and unidirectionally based on the diagnostic matrix. International Jour- strong isolability. A strategy of introducing new variables nal of Applied Mathematics and Computer Science, which allow obtaining BILP problem was presented. This 23(2):407–417, 2013. strategy makes it possible to use efficient tools to find opti- [12] Janos Gertler. Fault detection and isolation using par- mal sensors sets. ity relations. Control Engineering Practice, 5(5):653 In this paper, the method was applied to a Binary Diag- – 661, 1997. nostic Matrix, but the proposed measure of fault isolability can describe multi-valued systems such as Fault Information [13] Janos Gertler. Fault detection and diagnosis in engi- Systems (FIS). neering systems. CRC press, 1998. [14] Kornel Rostek. Measure of fault isolability of diagnos- References tic system. In 25th International Workshop on Princi- [1] Abed Yassine, Stéphane Ploix, and Jean-Marie Flaus. ples of Diagnosis, 2014. A method for sensor placement taking into account di- [15] Kornel Rostek. Optimal Sensor Placement for Fault agnosability criteria. International Journal of Applied Information System, pages 67–72. Springer Interna- Mathematics and Computer Science, 18(4):497–512, tional Publishing, Cham, 2016. 2008. [16] Michał Bartyś. Single fault isolability metrics of the [2] Mattias Krysander, J. Aslund, and Mattias Nyberg. binary isolating structures. In Advanced and Intelli- An efficient algorithm for finding minimal overcon- gent Computations in Diagnosis and Control, pages strained subsystems for model-based diagnosis. Sys- 61–75. Springer, 2016. tems, Man and Cybernetics, Part A: Systems and Hu- mans, IEEE Transactions on, 38(1):197–206, 2008. [3] Stefan Spanache, Teresa Escobet, and Louise Trave- Massuyes. Sensor placement optimisation using ge- netic algorithms. In Proceedings of the 15th Interna- tional Workshop on Principles of Diagnosis, DX-04, 2004. [4] Louise Travé-Massuyès, Teresa Escobet, and Xavier Olive. Diagnosability analysis based on component- supported analytical redundancy relations. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 36(6):1146–1160, 2006. [5] Albert Rosich, Ramon Sarrate, Vicenç Puig, and Teresa Escobet. Efficient optimal sensor placement for model-based fdi using an incremental algorithm. In Decision and Control, 2007 46th IEEE Conference on, pages 2590–2595. IEEE, 2007. [6] Ramon Sarrate, Vicenç Puig, Teresa Escobet, and Al- bert Rosich. Optimal sensor placement for model- based fault detection and isolation. In Decision and Control, 2007 46th IEEE Conference on, pages 2584– 2589. IEEE, 2007. [7] Fatiha Nejjari, Ramon Sarrate, and Albert Rosich. Op- timal sensor placement for fuel cell system diagno- sis using bilp formulation. In Control & Automa- tion (MED), 2010 18th Mediterranean Conference on, pages 1296–1301. IEEE, 2010. [8] Albert Rosich, Ramon Sarrate, and Fatiha Nejjari. Op- timal sensor placement for fdi using binary integer lin- ear programming. In 20th International Workshop on Principles of Diagnosis, 2009. [9] Ramon Sarrate, Fatiha Nejjari, and Albert Rosich. Model-based optimal sensor placement approaches to fuel cell stack system fault diagnosis. Fault Detec- tion, Supervision and Safety of Technical Processes, Volume# 8| Part# 1, 2012.