Christian Commault

Jean-Michel Dion

Hieu Trinh

Observability preservation under sensor failure

This paper is concerned with the study of observability in a structured framework. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. We focus our attention on the observability preservation under sensor failure. We consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely we will characterize among the sensors those which are critical and which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. Using a graph approach we classify the sensors with respect to their importance for output connection preservation, contraction avoidance and then observability preservation under sensor failure.

I. INTRODUCTION

In this paper, we consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely we will characterize among the sensors those which are critical and which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. We study the problem using a graph approach which can be used easily for usual linear systems but will focus our attention on linear structured systems which represent a large class of parameter dependent linear systems. This approach was pioneered by Lin [START_REF] Lin | Structural controllability[END_REF]. Generic properties for such systems can be obtained from a graph associated to the system. The dualization of the results given by Lin allows to characterize the generic observability of structured systems. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. Starting from these conditions for observability we will here determine the critical sensors, which will be called essential, as well as the useless ones for both conditions. For each condition we will provide with a structural analysis of the admissible conditions and give global results for observability preservation. We will illustrate the results on simple academic examples and point out classical combinatorial algorithms for getting the solutions. The outline of this paper is as follows. The linear structured systems are presented in section 2. We revisit structural observability conditions in section 3. In section 4 we study the output connection preservation and in section 5 the contraction avoidance. The problem of observability preservation under sensor failure is finally considered in section 6. Some concluding remarks end the paper. In this part, we recall some definitions and results on linear structured systems. More details can be found in [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. We consider linear systems with parameterized entries and denoted by Σ Λ . In this paper, we will only be concerned with observability and we will not take into account input variables.

Σ Λ ẋ(t) = Ax(t) y(t) = Cx(t) , (1)
where x(t) ∈ R n is the state vector and y(t) ∈ R p the measured output vector. A and C are matrices of appropriate dimensions.

This system is called a linear structured system if the entries of the composite matrix J = A C are either fixed zeros or independent parameters (not related by algebraic equations). Λ = {λ 1 , λ 2 , . . . , λ k } denotes the set of independent parameters of the composite matrix J.

For the sake of simplicity the dependence of the system matrices on Λ will not be made explicit in the notation.

A structured system represents a large class of parameter dependent linear systems. The structure is given by the location of the fixed zero entries of J.

For such systems, one can study generic properties i.e. properties which are true for almost all values of the parameters collected in Λ [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF], [START_REF] Reinschke | Multivariable control : A graph-theoretic approach[END_REF]. More precisely a property is said to be generic (or structural) if it is true for all values of the parameters (i.e. any Λ ∈ R k ) outside a proper algebraic variety of the parameter space. A directed graph G(Σ Λ ) = (Z, W ) can be easily associated to the structured system Σ Λ of type [START_REF] Lin | Structural controllability[END_REF] where the matrix A C is structured:

• the vertex set is Z = X ∪ Y where X and Y are the state and output sets given by {x 1 , x 2 , . . . , x n } and {y 1 , y 2 , . . . , y p } respectively,

• the edge set is W = {(x i , x j )|A ji = 0} ∪ {(x i , y j )|C ji = 0}
, where A ji (resp. C ji ) denotes the entry (j, i) of the matrix A (resp. C).

Moreover, recall that a path in G(Σ Λ ) from a vertex i µ0 to a vertex i µq is a sequence of edges (i µ0 , i µ1 ), (i µ1 , i µ2 ), . . . , (i µq-1 , i µq ) such that i µt ∈ Z for t = 0, 1, . . . , q and (i µt-1 , i µt ) ∈ W for t = 1, 2, . . . , q. If i µ0 ∈ X and, i µq ∈ Y , the path is called a state-output path. The system Σ Λ is said to be output-connected if for any state vertex x i there exists a state-output path with initial vertex x i . A set of paths with no common vertex is said to be vertex disjoint. We will also use undirected graphs composed of vertices and undirected edges. In such graphs the undirected paths will be called walks.

Example 1: Let Σ Λ be the linear structured system defined by its structured matrices.

A =   0 0 0 0 0 0 λ 1 0 0   , C = 0 0 λ 2 0 λ 3 λ 4 , (2)
Its associated graph G(Σ Λ ) is given in Figure 1.

III. OBSERVABILITY OF LINEAR STRUCTURED SYSTEMS

The structural controllability or the dual notion of observability has been studied in several papers [START_REF] Lin | Structural controllability[END_REF], [START_REF] Shields | Structural controllability of multiinput linear systems[END_REF], [START_REF] Glover | Characterization of structural controllability[END_REF].

Define the concept of contraction which is the dual notion of the dilation defined by Lin in the study of controllability.

Definition 1: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with associated graph G(Σ Λ ) with vertex set Z and edge set W . Consider a set S made of k S state vertices. Denote E(S) the set of vertices w i for i = 1, . . . , l S of Z, such that there exists an edge (x j , w i ) of W where x j ∈ S. S is said to be a contraction if k Sl S > 0.

(3) Recall the graph characterization of the structural observability, which will be useful later [START_REF] Lin | Structural controllability[END_REF], [START_REF] Murota | Systems Analysis by Graphs and Matroids, ser. Algorithms and Combinatorics[END_REF].

Proposition 1: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with its associated graph G(Σ Λ ). The system is structurally observable if and only if:

1) The system Σ Λ is output-connected, 2) G(Σ Λ ) contains no contraction.

Consider again the system Σ Λ of Example 1. All the state vertices are output connected and its associated graph G(Σ Λ ) does not have any contraction so Σ Λ is structurally observable. If the output sensor y 1 fails, the set S = {x 2 , x 3 } is a contraction since E(S) = {y 2 } and k Sl S = 1. If the output sensor y 2 fails, x 2 is not any more output connected and {x 2 } is a contraction.

In the following sections, we will focus our interest on structurally observable systems. We look for the the maximal number of sensors which can be suppressed while preserving the structural observability of the system. We will tackle this problem in two stages. In a first step, we will study the preservation of the output connection property and give the set of sensors which can or cannot be suppressed to keep this property. In a second step, we will study the contraction avoidance when removing sensors and give the set of sensors which can or cannot be suppressed without creating a contraction.

IV. OUTPUT CONNECTION PRESERVATION

A. Strongly connected components and reduced connection graph

Let Σ Λ be the linear structured system defined by ( 1) with its associated graph G(Σ Λ ). Two vertices v i and v j of G(Σ Λ ) are said to be equivalent if there exists a path from v i to v j and a path from v j to v i . In this context v i is assumed to be equivalent to itself. The equivalent classes corresponding to this equivalence relation are called the strongly connected components of G(Σ Λ ). Standard combinatorial optimization algorithms exist to get the canonical decomposition of the graph into strongly connected components. The output vertices y i are strongly connected components composed of a unique vertex. The strongly connected components can be endowed with a natural partial order. The strongly connected components C i and C j are such that C i C j if there exists an edge (v j , v i ) where v i ∈ C i and v j ∈ C j . The infimal elements with this order are the strongly connected components with no outgoing edges. Notice that the output vertices are such infimal elements.

Proposition 2: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with its associated graph G(Σ Λ ). Σ Λ is output connected if and only if all of the infimal components of G(Σ Λ ) are output vertices. Proof: Any state vertex of Σ Λ is connected to one or more infimal components of G(Σ Λ ). When all of infimal components of G(Σ Λ ) are output vertices, all state vertices are output connected. Conversely if an infimal component is not an output vertex, the vertices of this component are not output connected.

We define pre-infimal components as the strongly connected components which have no path to others components except output vertices. To study output connection let us now introduce a new undirected graph.

Definition 2: The graph C(Σ Λ ) = (Z c , W c ) called reduced connection graph is derived from G(Σ Λ ) as follows:

• the vertex set is Z c = V ∪ V ′ ∪ Y ∪ z with V = {v 1 , v 2 , . . . , v k } where v i corresponds to the pre-infimal component I i of G(Σ Λ ), V ′ = {v ′ 1 , v ′ 2 , . . . , v ′ l } where v ′ i corresponds to an infimal component of G(Σ Λ )
which is not an output vertex, Y is the output set {y 1 , y 2 , . . . , y p } and z is an additional vertex ,

• the edge set is W c = {(v i , y j )| when there exists a path from I i to y j } ∪ {(y j , z) for any j}.

C(Σ Λ ) is a simple way to analyze the output connection of the system Σ Λ .

Proposition 3: The graph G(Σ Λ ) is output connected if and only if the reduced connection graph C(Σ Λ ) is connected. Proof: If C(Σ Λ ) is connected there is a walk from each v i to z in C(Σ Λ ) and this walk passes through an output y j . Then in G(Σ Λ ) all the vertices of a pre-infimal component are output connected, other state vertices being connected to a pre-infimal component will also be output connected. Conversely if G(Σ Λ ) is not output connected there exists at least one infimal component which is not an output vertex and then the corresponding vertex

v ′ i is isolated in C(Σ Λ ), therefore C(Σ Λ ) is not connected.
Example 2: Let Σ Λ be the linear observable structured system which associated graph G(Σ Λ ) is given in Figure 2.

C. Connection preservation under sensor failure

In this subsection we will focus our attention on separators which are only made of output vertices.

Proposition 4: Let Σ Λ be the linear observable structured system defined by ( 1 Algorithm 1: Listing all minimal separators 1) For all v i :

• S(v i ) := {y j |(v i , y j ) ∈ W c } 2) For all S(v i ): • If there is no k such that S(v k ) ⊂ S(v i ), then S(v i
) is a minimal separator. The construction of the algorithm comes from the fact that S(v i ) is the set of neighbor vertices of v i , so it is a separator for v i . Moreover, if S(v i ) does not contain any other separator, it is minimal.

Remark 2: With the set of minimal separators SM , we can classify the sensors with respect to their importance for the output connection of the system:

• The essential sensors Ē coincide with the minimal separators of cardinality one. If we loose one of these sensors, the output connection is lost.

• The sensors L which are not in any minimal separator are called useless sensors. These sensors do not play any role for the output connection of the system. • The useful sensors F are those which belong to at least one minimal separator. Each one individually may fail without loosing output connection but they may contribute to output connection in case of failure of the other sensors. Consider again Example 2. In the set of output vertices Y , we found two minimal separators S 1 = {y 2 , y 3 } and S 2 = {y 4 }. So L = {y 1 , y 5 } are useless sensors because they do not belong to any minimal separator. The useful sensors are F = {y 2 , y 3 , y 4 } and Ē = {y 4 } is an essential sensor. To keep this system output connected, we have to ensure at least that {y 2 , y 4 } or {y 3 , y 4 } have no failure.

When we have many minimal separators in Y , to keep the system output connected, we have to keep at least one sensor in each minimal separator -see Proposition 4. To minimize the number of sensor to conserve is a NP-complete problem. This problem is well know as the "hitting set" problem [START_REF] Garey | Computers and intractability: A guide to the theory of NP-Completeness[END_REF]. But we the size of this problem is strongly reduced with respect to the size of Σ Λ .

V. CONTRACTION AVOIDANCE

A. The bipartite graph

In this subsection, we will analyse in a finer way contractions. This will be performed using a bipartite graph associated with the system Σ Λ . We consider a linear structured system Σ Λ of type (1) as previously. Let us now introduce the bipartite graph B(Σ Λ ) as follows. The bipartite graph of this system is B(Σ Λ ) = (B + , B -; W ′ ) where the sets B + and B -are two disjoint vertex sets and W ′ is the edge set. The vertex set B + is given by X + , the vertex set B -is given by X -∪ Y , with X + = {x + 1 , . . . , x + n } the first set of state vertices, X -= {x - 1 , . . . , x - n } the second set of state vertices and Y = {y 1 , . . . , y p } the set of output vertices. Notice that here we have split each state vertex x i of G(Σ Λ ) into two vertices x + i and x - i . The edge set W ′ is described by

W A ∪ W C with W A = {(x + j , x - i )|A ij = 0} and W C = {(x + j , y i )|C ij = 0}.
In the latter, for instance A ij = 0 means that the (i, j)th entry of the matrix A is a parameter (structurally nonzero).

A matching in a bipartite graph B = (B + , B -; W ′ ) is an edge set M ⊆ W ′ such that the edges in M have no common vertex. We denote by ∂ + M (resp. ∂ -M ) the set of vertices in B + (resp. B -) incident to the edges in M . A matching M is called maximal if it has a maximum cardinality. The cardinality of a matching, i.e. the number of edges it consists of, is also called its size. The maximal matching problem is the problem of finding a matching of maximal cardinality. This problem can be solved using very efficient algorithms based on alternate augmenting chains or ideas of maximum flow theory [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF]. This notion allows a simple characterization of the generic rank of a structured matrix in terms of its bipartite graph [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF] which in our problem can be stated as follows.

Proposition 5: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF]

with its associated bipartite graph B(Σ Λ ).

There is no contraction in G(Σ Λ ) if and only if there exists a size n matching in B(Σ Λ ). With a matching M we associate a graph

B M = (B + ∪ B -; W ′ ) so that: (v, w) ∈ W ′ ⇔ (v, w) ∈ W ′ or (w, v) ∈ M . Denote S + = B + \∂ + M and S -= B -\∂ -M . Denote v w for {v; w} ∈ W ′ if there is a path from v to w in B M .

B. The Dulmage-Mendelsohn (DM) decomposition

The DM-Decomposition allows to decompose a bipartite graph B into unique partially ordered irreducible bipartite subgraphs

B i = (B + i , B - i ; W ′ i ) called the DM-components: Algorithm 2: DM-Decomposition [3] 1. Find a maximum matching M on B = (B + , B -; W ′ ). 2. Let B 0 = {B + 0 ∪ B - 0 } = {v ∈ B + ∪ B -|w v on B M for some w in S + } where B + 0 = {B + ∩ B 0 } and B - 0 = {B -∩ B 0 }. B 0 is called the minimal inconsistent part or horizontal tail of B. 3. Let B ∞ = {B + ∞ ∪ B - ∞ } = {v ∈ B + ∪ B -|v w on B M for some w in S -} where B + ∞ = {B + ∩ B ∞ } and B - ∞ = {B -∩ B ∞ }.
4. Let V i (i=1,...r) be the strong components of the graph obtained from B M by deleting the vertices of B 0 ∪ V ∞ and the edges incident thereto. 5. Define the partial order ≺ on {B i |i = 0, 1, ...r, ∞} as follows: Example 3: Consider the system Σ Λ which associated graph G(Σ Λ ) is depicted in Figure 2 and consider the associated bipartite graph B(Σ Λ ). We will find the DM-Decomposition of B(Σ Λ ). First of all, a maximum matching is defined by {x

B i ≺ B j ⇔ v j v i on B M for some v i ∈ B i and v j ∈ B j .
+ 6 → x - 3 ; x + 5 → y 4 ; x + 4 → x - 2 ; x + 3 → x - 1 ;
x + 1 → y 2 ; x + 2 → y 3 }, so that we have S + = ∅ and S -= {y 5 ; x - 5 ; y 1 ; x - 4 ; x - 6 }. Then B 0 = ∅ and B ∞ = {x - 4 ; x - 6 ; y 5 ; x + 4 ; x - 2 ; x - 5 ; y 1 ; x + 1 ; y 2 ; x + 3 ; x - 1 ; x + 2 ; y 3 }; Finally, B 1 = {x + 6 ; x - 3 } and B 2 = {x + 5 ; y 4 } as shown in the Figure 4.

C. Contraction avoidance

Proposition 6: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with its associated graph G(Σ Λ ) and associated bipartite graph B(Σ Λ ). G(Σ Λ ) has not any contraction if and only if the DM-Decomposition of B(Σ Λ ) has no minimal inconsistent part B 0 . Proof: Follows directly from the DM-Decomposition properties and from the definition of a contraction We will look for the outputs which can be suppressed without creating contractions, i.e. the DM-Decomposition of B(Σ Λ ) has no minimal inconsistent part B 0 o there exists a matching of size n in B(Σ Λ ). So all output vertices which are not covered by the matching of size n can fail.

Proposition 7: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with associated graph G(Σ Λ ) and associated bipartite graph B(Σ Λ ). All output vertices belonging to strong components B i , (i = 1, ...r) in the DM-Decomposition of B(Σ Λ ) are essential to avoid contraction. Proof: Follows the DM-Decomposition properties, the number of vertices of B + i equals to the number of vertices of B - i . If we suppress one vertex of B - i , it will create a contraction.

Proposition 8: Consider Σ Λ the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF] with associated graph G(Σ Λ ) and associated bipartite graph B(Σ Λ ). Let B ∞ be the minimal inconsistent part of the DM-Decomposition of B(Σ Λ ). Decompose B ∞ in connected bipartite subgraphs. In a connected bipartite subgraph, if there exists a maximal matching which does not cover any output vertex, these output vertices are useless to avoid contraction. Otherwise, these output vertices are useful. Proof: A completer Remark 3: With the help of the DM-decomposition we can classify the sensors with respect to their importance for the contraction avoidance:

• The essential sensors Ê coincide with the set of outputs which belong to strong components B i . If we loose one of these sensors, we create a contraction. • The set of useless sensors of Proposition 8 is denoted by L. These sensors do not play any role for the contraction avoidance of the system. • The set of useful sensors of Proposition 8 is denoted by F . Each one individually may fail without creating a contraction but they may contribute to avoid contraction in case of failure of other sensors.

To check in such a connected bipartite subgraph B * = (B + , B -; W ′ ), if there exists a maximal matching which does not cover any output vertex, we can use the following algorithm: Algorithm 3: 1. For any arc (v + , v -) ∈ W ′ , assign it a weight 0 if v -is a state vertex, a weight 1 if v -is an output vertex. 2. Find a maximal matching of minimal weight in B * . Note W m the weight of this matching i.e. the sum of all the arc weights it consists of. 3. If W m = 0 the maximal matching does not cover any output vertex. Otherwise, W m > 0, any maximal matching covers at least one output vertex. To find a maximal matching of minimal weight in a bipartite graph, we can use the algorithm developed in [START_REF] Gabow | Data structures for weighted matching and nearest common ancestors with linking[END_REF] with running time O(n * (m + nlogn)).

Consider again Example 2 which associated graph G(Σ Λ ) is depicted in Figure 2. The DM-Decomposition of associated bipartite graph B(Σ Λ ) is depicted in Figure 4. The essential sensor is Ê = y 4 because y 4 ∈ B 2 . In B ∞ , we have two connected bipartite subgraphs composed of {y 5 ; x + 4 ; x - 2 ; x - 5 } and {y 1 ; x + 1 ; y 2 ; x + 3 ; x - 1 ; x + 2 ; y 3 }. In the first one, we have a maximal matching {x + 4 ; x - 2 } which does not cover the output y 5 so L = {y 5 } is a useless sensor for contraction avoidance. In the second one, any maximal matching covers at least two of three outputs {y 1 , y 2 , y 3 } so the set of useful sensors for contraction avoidance is F = {y 1 , y 2 , y 3 }.

VI. OBSERVABILITY PRESERVATION

To keep the system observable while suppressing sensors, the system with remaining sensors must satisfy output connectivity property and absence of contraction. Proposition 4 and Remark 2 give the set of sensors which can be suppressed or can not be suppressed to keep the output connectivity property. Proposition 7 and Proposition 8 give the set of sensors which can be suppressed without creating a contraction. It is clear that a sensor which is essential for output connection or contraction avoidance is essential for observability preservation of the system. A sensor which is useless for output connection and contraction avoidance is useless for observability preservation of the system. Finally, we have the following Theorem: Theorem 1: Let Σ Λ be the linear structured system defined by [START_REF] Lin | Structural controllability[END_REF]. Using the notations of Remarks 2 and 3, to preserve the observability of the system:

• The set of essential sensors, i.e. the sensors which cannot fail, is given by E = Ē ∪ Ê

• The set of useless sensors, i.e. the sensors which do not play any role for observability, is given by L = L ∩ L

• The set of useful sensors, i.e. which may fail individually without observability loss but may contribute to observability in case of sensor failures, is given by F = (Y \L)\E.

Reconsider the observable system in Example 2. In this Example, we have L = {y 1 , y 5 }, F = {y 2 , y 3 , y 4 } and Ē = {y 4 }. By Example ??, we found Ê = y 4 , L = {y 5 } and F = {y 1 , y 2 , y 3 }. Finally, we have: In this paper, we revisited the observability analysis for structured systems. Using a graph approach we focused our attention on observability preservation under sensor failure and classified the sensors with respect to their criticity concerning observability. The use of standard algorithms or decompositions for reducing the problem complexity allows to get easily tractable algorithms. The proposed approach is well suited for structural analysis prior to observer design and the numerical implementation is simple. It allows to determine the sensors which are essential i.e. those whose failure will lead to observability loss, the sensors which are useless for observability preservation and those which are useful without being essential. The output connection analysis is valid for standard linear systems and is potentially interesting for nonlinear systems when considering linearized models of fixed structure and varying parameters around a set point. We think that this approach can also be useful for solving fault detection and diagnosis problem in case of sensor failure.

Fig. 1 .

 1 Fig. 1. G(Σ Λ ) for Example 1

Fig. 2 .

 2 Fig. 2. G(Σ Λ ) for Example 2

Fig. 3 .

 3 Fig. 3. C(Σ Λ ) for Example 2

  ) with its associated graph G(Σ Λ ) and its reduced connection graph C(Σ Λ ). Output connection of Σ Λ is preserved if and only if there exists at least one non failing sensor in each minimal separator of C(Σ Λ ) included in Y . Proof: Disconnecting C(Σ Λ ) is equivalent to suppress completely at least one minimal separator. When we do not suppress completely any minimal separator (i.e. we keep at least one non failing sensor in each separator), C(Σ Λ ) remains connected so G(Σ Λ ) from Proposition 3 is still output connected To find out the set of minimal separators SM ⊆ Y in a C(Σ Λ ), we can follow the following algorithm:

Fig. 4 .

 4 Fig. 4. B(Σ Λ ) for Example 2

•

  The essential sensors E = Ē ∪ Ê = {y 4 } • The useless sensors L = L ∩ L = {y 5 } • The useful sensors F = Y \E\L = {y 1 , y 2 , y 3 } VII. CONCLUDING REMARKS

  Christian Commault, Jean-Michel Dion and Do Hieu Trinh Laboratoire d'Automatique de Grenoble. LAG-CNRS, ENSIEG-INPG BP 46, 38402 Saint Martin d'Hères, France.

Email:{Christian.Commault,Jean-Michel.Dion}@inpg.fr Do-Hieu.Trinh@lag.ensieg.inpg.fr

II. LINEAR STRUCTURED SYSTEMS