Diagnosis is the reasoning leading to the identification of the cause of a problem. Given a system instrumented with a set of sensors, diagnosis can be performed thanks to diagnosis tests that are designed from the system model. The tests only involve measured variables and can be checked with the measured values. The configuration of tests that pass and tests that do not pass provides a way to isolate the faults. However the fact that all faults are discriminable, i.e. the system is fully diagnosable, depends on the set of tests and hence of the sensors that are placed on the system. The number of tests that can be designed is generally huge and more than sufficient to achieve full or maximal diagnosability. This paper addresses several variants of the problem of selecting the set of tests/sensors so that diagnosability is maximal and a cost criterion is minimized. The variant problems are formalized in the integer programming framework.
Since the end of the last century, the industrial world has continued to evolve and with this evolution, the systems and industrial processes are more complex and efficient. The growing complexity of industrial systems that have become increasingly demanding in terms of reliability, backup contact performance and availability has given rise to increasing interest of diagnosis.
As a result, companies are trying to develop and implement diagnosis and maintenance systems to ensure the reliability and availability of installations.
The effectiveness of the diagnosis system depends on the relevance of the information received on the system to be diagnosed through sensors. The efficiency of sensors can be evaluated with the level of diagnosability that can achieved, i.e. which faults are discriminable (or isolable) and which are not. In this paper, we consider that the system is composed by a set of interconnected components and that faults are associated to components. Diagnosis is generally achieved thanks to a set of diagnosis tests that are checked against the measures. Diagnosability refers to two properties: detectability, that means that a fault can be detected by at least one test; and isolability, that means that each fault has its own way to answer the tests.
Which diagnosis tests and how many of them are achievable depends on the sensors and their locations. In practice, diagnosis systems are forced by the cost of sensors and by the computational cost related to the number of diagnosis tests to be checked that can be prohibitive for on-line applications. Hence, optimizing the cost of sensors and/or tests while still guarantying a good level of diagnosability is essential in many application domains.
To achieve this, optimization methods can be put in place. In this paper, we consider five increasingly complex optimization problems. Problem I simply addresses the selection of a minimal number of tests guarantying full diagnosability. By full diagnosability, we mean that any fault in any component can be distinguished from any fault in another component. Problem II addresses the selection of a set of minimal cost sensors, selected among a set of possible sensors, that guaranty full diagnosability. This latter problem is obviously more difficult because sensors do not influence diagnosability directly but through the tests that can be actually implemented. Problem III considers that full diagnosability may not be achievable with the possible sensors but minimal cost selection must achieve maximal diagnosability. Problem IV maximizes components diagnosability when sensors themselves can undergo faults. Finally, Problem V requires that sensor faults are also diagnosable in addition to component faults. It maximizes diagnosability in this context. The two later problems hence provide solutions to robust optimal sensor selection problems. The five problems are formalized in an integer programming framework.
The paper is structured as follows. Section 2 provides an overview of the state of the art and positions the contribution. In Section 3, the notations and definitions used in the paper are presented. Section 4 formalizes the five optimization problems in an integer programming framework. Section 5 proposes an evaluation on an academic example, then on two real examples, a LEO satellite case study and a water desalinator. Finally, section 6 discusses the results and concludes the paper. 2
The objective of this paper is to propose a formalization of five increasingly complex optimization problems related to diagnosability. The optimization targets the cost of sensors and/or the number of diagnosis tests.
The optimal test selection problem, as known in the literature, aims at minimizing the cost of the tests while satisfying some isolability constraints. This problem is obviously related to the sensor placement problem, which searches the minimum cost sensor configuration that satisfies a given set of fault diagnosis specifications. However sensor selection is a more difficult problem because sensors do not influence diagnosability directly but through the tests that can be actually implemented.
In the literature, optimal test selection is often associated to the problem of test prioritization that corresponds to choosing the next best test or measurement to disambiguate a faulty situation. In practice, this is an integral part of the troubleshooting task. This domain has received a lot of attention [13; 14; 4].
Solutions have been proposed through heuristic optimization techniques [12; 15], focusing on diagnosis ambiguity reduction as the main optimization criterion, which leads to adopt heuristics based on information theory [8]. The methods known as diagnosis Test Prioritization Techniques are based on the Information Gain heuristic. They maximize the diagnosis information gain per test and increase the rate at which diagnosis quality improves [7] but they are often limited by their complexity. Nevertheless, we can mention the gReedy diagnosis Prioritization by ambiguiTy Reduction (RAPTOR) method [6] as a instance that achieves to restrain this issue.
Some authors address the sensor selection problem [18]. Several papers adopt the structural analysis framework [2; 5; 10], which is in line with this paper. In particular, [9] uses a structural model of the system to compute all minimal sensor sets that make faults isolable from each others. [19] uses an alternative structural model decomposition, based on gathering equations that can not be isolable. [11] presents an approach for diagnosability analysis and sensor placement based on genetic algorithms.
The problem of optimal test selection can also be formulated as a combinatorial optimization problem. Such formulation has already been proposed using binary integer programming [1; 17; 16], which is in line with the approach adopted in this paper. However, this approach has not been applied to maximize the robust optimal selection problem, when sensors themselves can be faulty and sensor faults must be diagnosable. In other words, Problems I and II find solutions in the litterature. For these problems we contribute with a new compact binary integer programming formulation. Problems III, IV, and V solve variants of the diagnosability maximization problem. 3
Let us consider a system composed of a set C of nc components and instrumented with a set of sensors S. Assume that a set T of N binary diagnosis tests is available for this system. The output of a test is either 0 when the test passes or 1 when it does not pass.
Every test Ti; i = 1; : : : ; N , covers a subset of components of 2T that form the component test support denoted by SuppC (Ti) and it is supported by a subset of sensors of 2S that form the sensor test support denoted by SuppS (Ti). This means that: all the sensors of SuppS (Ti) must be installed on the system for the test Ti to be available, when the test Ti does not pass, one of the components of SuppC (Ti), or SuppS (Ti) if sensors are assumed to undergo faults, is faulty.
The matrix that crosses tests on lines and components and sensors on columns is called the covering matrix and is denoted by M . M is the concatenation of two matrices: MC is the submatrix that covers the set of components C,
MS is the submatrix that covers the set of sensors.
Let us denote by M(i;j), i = 1; : : : ; N , j = 1; : : : ; nC + nS , the entry of M at the ith line and jth column. The entries of MC and MS are defined similarly as MC(i;j), i = 1; : : : ; N , j = 1; : : : ; nC , and MS(i;j), i = 1; : : : ; N , j = 1; : : : ; nS , respectively. cj denotes the column corresponding to component Cj and sk denotes the column corresponding to sensor Sk.
In the matrix M an entry at "1" on line i means that the corresponding component / sensor belongs to SuppC (Ti) / SuppS (Ti). This is illustrated in Table 1. Definition 3.1 (Instrumented test). A test is said to be instrumented for a submatrix M if all the sensors required for the test are available in M and free of faults. nC is the number of instrumented tests for the submatrix M . Definition 3.2 (Detectability). The fault fj of component cj is said to be detectable if the column j of MC has at least one ’1’.
Definition 3.3 (Isolability). A component cj is said to be isolable from a component ci if the columns i and j of MC are different.
Let us focuse on component faults and leave aside sensor faults for now.
Definition 3.4 (Admissible matrix M ). A matrix M said to be admissible if the set of instrumented tests for M provides the isolability for all pairs of components. is Property 3.5. M is admissible if and only if MC has nC different columns and all tests required for this are instrumented.
Since the entries of the covering matrix M are binary, this property can be formalized by: special case of 0-1 integer linear programming, which is an integer linear program in which unknowns are binary. MC (k; j)j 1; (1) Example Let us consider the covering matrix given in Table 2 and assume that the sthree sensors are available, hence all the tests T1 to T6 are instrumented.
We can notice that all the columns refering to components are different, which means that all components are isolable. In other words, the available tests guarantee full diagnosability to the system. Now assume that sensor S3 is not selected, then columns c1 and c4 are identical, hence components C1 and C4 are not isolable anymore.
Our goal is to find a submatrix M whose structure guaranties full or maximal diagnosability to the system while minimize some cost criterion. 4
There are several variants to formulate an optimal test/sensor selection problem. We are interested in investigating integer programming formulations. In this section, we hence provide the mathematical formulation of five variant problems that can be solved in the integer programming framework. We consider the following hypotheses: Problems I and II assume that full diagnosability is achievable and that sensors are not faulty, Problems III, IV, and V assume that full diagnosability may not be achievable. In addition, Problems IV and V relax the assumption that sensors cannot be faulty, targeting a robust solution with respect to components only and with respect to components and sensors, respectively.
In all the problems, we do assume that all the tests are instrumented in M .
In this section, we briefly introduce Integer Programming (IP) that we use to solve all different formulations of our problem.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to Integer Linear Programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. However, we have the
In this section, the goal is to minimize the number of tests that guarantee full component diagnosability under the assumption that sensors do not fail. In other words, the solution must provide an admissible matrix M .
Let us define the following variables:
zi is a boolean variable associated to each test i 2 T
such that:
zi =
and
(
8j 2 S zi 2 f0; 1g;
Objective (
Let us notice that, for efficiency purposes1, the y′ s are
j
coded as continuous variables in the program. In practice,
the r.h.s of inequality (
Note that Problem II is similar to the maximal covering location problem [3], which is also NP-hard. In this section, we assume the general case in which there may not be a solution to ensure full isolability. In this case, the solution provided by the solver must ensure maximal isolability. We still have the concern of minimizing the sensor cost. Thus, the problem becomes a bi-objective optimization problem.
Problem III can be formalized as follows: max(∑ ekl k;l ∑ pj yj ); 8(k; l) 2 C2 j2S Subject to: yj
In this formulation, variables ekl are used to obtain partial
isolability: ekl = 1 means that the fault of component k is
isolable from the fault of component l. Their sum is
maximized by the objective function and variables ekl are
introduced as the r.h.s of constraints (
In the objective function (
In Problem IV, we consider another variant of the problem where sensors may fail. We want however the output solution to achieve maximal isolability for component faults with minimum cost even when a single sensor fails.
We add a new element to our integer linear program: Ts is a parameter that denotes the set of tests instrumented by sensor s.
The optimization Problem IV becomes: max(∑ ekl k;l ∑ piyi); j2S
k 2 C; l 2 C zi for i 2 T;
In Problem IV, a covering constraint (
In Problem V, we yet consider another variant of the problem. Like in Problem IV, one sensor may fail. However, we want the solution to achieve maximal isolability for component and sensor faults with minimum cost. Consequently, the index l now refers to components and sensors (l 2 (C [ S)) in constraints (24) and not only to components like in Problem IV.
Problem V can be formalized as follows: ∑ piyi); j2S
k 2 C; l 2 (C [ S) (22) yj 0;
8j 2 S 0 ekl 1; 8l 2 S;
8k 2 C
zi 2 f0; 1g; i 2 T
(
After implementing Problem IV (Maximization of robust isolability w.r.t. component faults) with the Gurobi Optimizer, the solution provided by its execution consisted in a subset of 7 sensors fS1; S2; S3; S5; S6; S7; S9g. These sensors can indeed be used to instrument 6 tests T2; T4; T5; T6; T8; T9, achieving maximal robust diagnosability w.r.t. component faults. The corresponding matrix M is given in Table 6 where we can check that all component columns are different leading to 25 pairs of isolable components but c6 and c7 even when one of the sensors is faulty and cannot be used to instrument any test. maximize diagnosability. The corresponding solution matrix M is given in Table 5 where we can check which component columns are different leading to 34 pairs of isolable components.
T2 T5 T6 T7 T8 T2 T4 T5 T6 T8 T9
In the implementation of our mathematically formalized problems, we used the Gurobi Optimizer with the Python API. In what follows, we provide illustrative solutions to an academic example and the solutions to two industrial problems. Let us consider a simple example where the number of components nC , the number of sensors nS , and the number of tests nT are all fixed at 9.
The covering matrix we consider is given in Table 3 (w.r.t. components) and Table 4 (w.r.t. sensors).
Problem I (Optimal test selection with fault free sensors) and Problem 2 (Optimal sensor selection with fault free sensors) were implemented in the Gurobi Optimizer. Their execution did provide no solution. This means that full diagnosability is not possible given the covering matrices MC and MS . This could be anticipated because in MC , we can notice that C2 = C6 and C5 = C7. These components are hence not isolable.
After implementing Problem 3 (Maximization of isolability with fault free sensors) with the Gurobi Optimizer, the solution provided by its execution consisted in a subset of 7 sensors fS1; S2; S3; S4; S6; S7; S8g. These sensors can indeed be used to instrument 5 tests T2; T5; T6; T7; T8 that
Interestingly, it can be noticed that the number of required sensors is the same as for Problem III. Nevertheless, the sensors are different and they can be used to instrument 6 tests instead of 5, achieving this way robust diagnosability.
After implementing Problem V (Maximization of robust isolability w.r.t. component faults and sensor faults) with the Gurobi Optimizer, the solution provided by its execution consisted in all the sensors fS1; S2; S3; S4; S5; S6; S7; S8; S9g. However not all the tests are necessary. 8 instrumented tests T1; T2; T4; T5; T6; T7; T8; T9 are enough to achieve maximal robust diagnosability w.r.t. component faults and sensor faults. The corresponding solution matrices MC and MS are given in Table 7 and Table 8 where we can check which component and sensor columns are different even when one of the sensors is faulty and cannot be used to instrument any test. We obtain 96 pairs of isolable components/sensors.
A LEO satellite (Low Earth Orbit) [20], also known as the OTB orbit, is a satellite in the zone up to 2,000 kilometers in altitude, located between the atmosphere and the Van Allen outer belt. It is generally used in remote sensing and telecommunication applications.
LEO satellites are equipped with many radars and antennas that must be oriented in a precise and specific direction. In this case study, we are interested in the Attitude Determination and Control System (ADCS). This system is composed of two subsystems: the Attitude Determination Subsystem (ADS) and the Attitude Control Subsystem (ACS).
The Attitude Determination Subsystem is composed of sensors that detect the angular position of the satellite. If we take the example of Spot 7 LEO satellite [20], its Attitude Determination Subsystem has two types of sensors: speed sensors and gyroscopes. These sensors excite in triplicate for the three axes.
The Attitude Control Subsystem is the one responsible for controlling the movement to the desired position. The ACS Spot 7 LEO satellite [20] is equipped with three reaction wheels for three-axis control. The sensor suite of the satellite is composed of rate gyros for each of the three axes, and vector sensors which are used to periodically clear the accumulated attitude drift error from the rate gyroscopes.
As a result, we consider faults on rate and vector sensors as well as faults on the reaction wheels. This sums up to 9 faults f1 to f9 for the ADCS. The covering matrix that we considered has faults as columns instead of components. An entry at "1" on line i means that the test Ti does not pass when the corresponding fault is present.
An analysis of the ADCS and its model has provided 2448 tests for this system [20]. In this case study, we have considered Problem I and implemented the corresponding program in the Gurobi Optimizer. We found that only 4 of the 2448 tests are necessary to achieve full diagnosability and discriminate all the faults. These tests are: T315, T346, T503 and T2100.
T315 T346 T503 T2100
The solution matrix M shows that the tests found ensure the isolability of all faults and their number is minimal. Optimality can be confirmed from the theoretical minimal number of tests. It is obtained by considering that a set of tests exists such that every test iteratively partitions the fault set in two sets of non discriminable faults. So if we have nc components, then log2(nc) is the greatest lower bound of the theoretical minimal number of tests. In this case study, nc = 9 and the theoretical minimal number of tests is hence 4, which is in accordance with the result provided by Problem I. 5.3
The desalination system [20] is a system that removes salt from the water. It uses several chemical, electrical and even thermal procedures (cf. Figure 2). Given the complexity of this system, there is a need for properly instrumenting the system and providing relevant information that helps diagnosing the chemical desalination process.
If we take the desalinator case study presented in [20], it has 7 possible faults: f1 is the fault of the conductivity sensor, f 2 is the fault of the flow sensor, f 3 is a high pressure pump fault, f 4 is the fault of the temperature sensor, f 5 is the fault of scaling of the membrane, f 6 is the defect of the membrane, f 7 is the failure of the pump acid pump pH.
nof is used to refer to the fault free operating mode. 5 sensors can be considered for this system. An analysis of the desalinator benchmark and its model has provided 5173 tests for this system [20].
Problem I has been considered and the corresponding program has been implemented in the Gurobi Optimizer. We found that only 3 of the tests are necessary to guaranty full diagnosability. The subset of tests is fT129, T738; T833g as shown in Table 10.
We can notice that the tests found ensure detectability and isolability of all faults and that their number is minimized. Indeed, like in the LEO satelite case study, their number corresponds to the theoretical optimal number.
The solution of Problem II provided by Gurobi indicates that 3 sensors are necessary to guaranty full diagnosability. These sensors are S1, S2 and S5. Interestingly, 283 tests can be instrumented with these sensors.
The solution of Problem III provided by Gurobi is the same as the solution of Problem II, which is obviously correct. Indeed, when full diagnosability is achievable, maximal diagnosability is just full diagnosability. We obtain 28 pairs of isolable components.
The solution of Problem IV provided by Gurobi indicates that 3 sensors are necessary to guaranty maximal diagnosability w.r.t. components eventhough one sensor may be faulty. These sensors are S1, S2 and S4. 333 tests can then be instrumented and we obtain 27 pairs of isolable components independently of the failure of one sensor.
The solution of Problem IV provided by Gurobi indicates that the same 3 sensors as for Problem IV are necessary to guaranty maximal diagnosability w.r.t. components and sensors eventhough one sensor may be faulty. These sensors are S1, S2 and S4. 333 tests can then be instrumented and we obtain 59 pairs of isolable components/sensors independently of the failure of one sensor. 6
This paper shows the potential of integer linear programming for modeling five increasingly complex optimization problems related to diagnosability. The optimization targets the cost/number of sensors and/or the number of diagnosis tests under different assumptions. Although Problems I and II find solutions in the litterature, we have contributed with a new compact binary integer programming formulation. Problems III, IV, and V solve variants of the diagnosability maximization problem. Maximizing diagnosability when full diagnosability is not achievable is an interesting problem addressed in this paper. The five problems have been programmed using the Python language accompanied by the Gurobi solver library in order to find an optimal solution to the problems.
Our programs have been validated with the application to two real case studies, a LEO satellite and a water desalinator benchmark [20].
Future work will consider additionnal constraints refering to the practical implementation of the tests. On the other hand, solving the five problems in a decentralized or distributed framework will also be considered.