Préservation de l’observabilité en présence de défauts de capteurs

23/09/2017
Auteurs : Do Hieu Trinh
Publication e-STA e-STA 2007-3
OAI : oai:www.see.asso.fr:545:2007-3:19892
DOI :

Résumé

Préservation de l’observabilité en présence de défauts de capteurs

Métriques

17
8
913.15 Ko
 application/pdf
bitcache://c7930ababa02866e2133efd84ae4b1d77f0e592a

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2007-3/19892</identifier><creators><creator><creatorName>Do Hieu Trinh</creatorName></creator></creators><titles>
            <title>Préservation de l’observabilité en présence de défauts de capteurs</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 23 Sep 2017</date>
	    <date dateType="Updated">Sat 23 Sep 2017</date>
            <date dateType="Submitted">Fri 10 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">c7930ababa02866e2133efd84ae4b1d77f0e592a</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33806</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Préservation de l’observabilité en présence de défauts de capteurs Do Hieu Trinh1 1 Laboratoire d’Automatique de Grenoble LAG-CNRS, ENSIEG-INPG, BP 46, 38402 Saint Martin d’Hères, France Do-Hieu.Trinh@inpg.fr http://www.lag.ensieg.inpg.fr/ Résumé— Dans cet article, on s’intéresse à l’analyse de l’ob- servabilité dans le cadre des systèmes structurés. Il s’avère que le système est structurellement observable si et seule- ment si le système est connecté à la sortie et ne contient aucune contraction. Nous nous concentrons sur la préserva- tion de l’observabilité en présence de défauts de capteurs. Nous considérons les systèmes linéaires observables et nous nous demandons si un système donné restera observable en présence de défaut de capteur. Plus précisément, nous ca- ractériserons parmi les capteurs ceux qui sont critiques c’est à dire ceux dont les défauts mènent à la perte d’observabi- lité, ceux qui sont inutiles pour l’observabilité et l’ensemble de ceux qui sont utiles sans être critiques. En utilisant une approche basée sur la théorie des graphes, nous classons les capteurs en fonction de leur importance successivement pour la préservation de la connexion à la sortie, l’absence de contraction et puis la préservation de l’observabilité. Mots-clés— Systèmes linéaires structurés, observabilité, dé- fauts de capteurs. I. Introduction Les systèmes physiques sont souvent représentés par des modèles d’état dont les paramètres des matrices sont en général mal connus. Dans ce travail, on considérera les sys- tèmes structurés qui dépendent des paramètres non nuls dont les positions sont connues. Ce type de système repré- sente une classe importante de systèmes linéaires dépen- dants de paramètres qui peuvent modéliser efficacement un système non linéaire autour de différents points de fonction- nement, voir l’exemple d’une colonne de distillation dans [1]. Pour de tels systèmes on peut étudier des propriétés dites génériques, c’est à dire des propriétés qui sont vraies pour presque toutes valeurs des paramètres libres. A ces systèmes structurés, on associe des graphes qui sont un ou- til très efficace pour l’étude des propriétés génériques [2]. Il a été montré en particulier que l’étude d’ensembles de chemins entrée-sortie sur le graphe permettait de résoudre de façon élégante des problèmes tels que le découplage et le rejet de perturbations [3]. La commandabilité des systèmes linéaires structurés a été étudiée par un certain nombre d’auteurs dans les années 70 [2], [4], [5]. Ces résul- tats peuvent être dualisés pour avoir les conditions d’ob- servabilité générique. L’étude de l’observabilité sous l’aspect de localisation des capteurs ou en présence de défauts de capteurs a été abor- dée en particulier en génie chimique mais la plupart des modèles sont des modèles statiques. L’observabilité a été également étudiée dans le cadre des modèles qualitatifs (contraintes/variables) de manière structurelle, voir [6]. Dans cet article, nous considérons les modèles dynamiques et nous étudions la préservation de l’observabilité en pré- sence de défauts de capteurs dans le cadre structurel. Il s’avère que le système est structurellement observable si et seulement si le graphe du système est connecté à la sor- tie et ne contient aucune contraction. La contraction est une condition graphique qui qui exprime que la matrice [CT ; AT ]T du système ˙x = Ax, y = Cx n’est pas de rang plein donc que [CT , CT AT , . . . , CT AT n−1 ]T n’est pas non plus de rang plein. Si le graphe associé n’est pas connecté à la sortie, un état au moins n’aura d’influence sur aucune sortie et ne sera donc pas observable. En cas de défauts de capteurs, nous étudierons la préservation de la connexion à la sortie aussi bien que l’absence de contraction. À partir de ces analyses, nous étudierons la préservation de l’observabi- lité en cas de défauts de capteurs. Nous déterminerons les capteurs critiques, qui s’appelleront essentiels, aussi bien que les capteurs inutiles. Nous illustrerons les résultats sur des exemples académiques simples et nous nous donnerons les algorithmes de combinatoire classiques pour obtenir les solutions. Les résultats présentés ont été démontrés dans [7]. Dans cet article, nous essayons de présenter de manière pédagogique les phénomènes qui conduisent à la perte de l’observabilité et à sa préservation en présence de défauts de capteurs. Le sommaire de cet article est le suivant. Les systèmes linéaires structurés sont présentés dans le paragraphe II. Nous revisitons des conditions structurelles d’observabilité dans le paragraphe III. Nous formulons le problème de la préservation de l’observabilité en présence de défauts de capteurs dans le paragraphe IV. Dans le paragraphe V nous étudions la préservation de la connexion à la sortie et dans le paragraphe VI l’absence de contraction. Le problème de la préservation de l’observabilité en présence de défauts de capteurs est finalement considéré dans le paragraphe VII. Quelques remarques en guise de conclusion finissent l’ar- ticle. e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24 II. Systèmes linéaires structurés Dans ce paragraphe, nous rappelons quelques définitions et résultats sur les systèmes linéaires structurés. Plus de détails peuvent être trouvés dans [3]. Considérons un système linéaire décrit par ΣΛ. Dans ce travail, nous serons seulement concernés par l’observabilité et nous ne tiendrons pas compte des variables d’entrée. Nous avons donc : ΣΛ ˙x(t) = Ax(t) y(t) = Cx(t) , (1) où x(t) ∈ Rn est le vecteur d’état et y(t) ∈ Rp est le vecteur de sortie. A et C sont des matrices de dimensions appro- priées. Ce système est appelé système linéaire structuré si les éléments de la matrice composite J = A C sont soit fixés à zéro soit des paramètres libres. On note Λ = {λ1, λ2, . . . , λk} l’ensemble des paramètres libres de la ma- trice J. La structure du système est donnée par les posi- tions des paramètres fixés à zéro et des paramètres libres. Un système linéaire structuré représente une classe impor- tante de systèmes linéaires dépendants de paramètres. Pour de tels systèmes, on étudie les propriétés génériques c’est à dire les propriétés qui sont vraies pour presque toutes les valeurs des paramètres λi [8]. Un graphe orienté G(ΣΛ) = (Z, W) peut être facilement associé au système structuré ΣΛ du type (1) où la matrice A C est structurée : – L’ensemble de sommets Z = X∪Y où X est l’ensemble de sommets d’état {x1, x2, . . . , xn} et Y est l’ensemble de sommets de sortie {y1, y2, . . . , yp}. – L’ensemble d’arcs W = {(xi, xj)|Aji = 0} ∪ {(xi, yj)|Cji = 0}, où Aji (resp. Cji) est l’élément (j, i) de la matrice A (resp. C). Dans un graphe G(ΣΛ), on définit un chemin de iµ0 à iµq comme une série d’arcs consécutifs (iµ0, iµ1), (iµ1, iµ2), . . . , (iµq−1, iµq) tels que iµt ∈ Z pour t = 0, 1, . . . , q et (iµt−1, iµt) ∈ W pour t = 1, 2, . . . , q. Si iµ0 ∈ X et iµq ∈ Y , le chemin est dit chemin état-sortie. Le système ΣΛ est dit connecté à la sortie si pour n’importe quel sommet d’état xi, il existe un chemin état-sortie avec sommet initial xi. Nous utilisons également les graphes non orientés composés de sommets et d’arcs non orientés. Dans de tels graphes, les chemins non orientés sont appelés les chaînes. Nous donnons maintenant un exemple très simple afin d’illustrer les notions précédentes et ensuite, l’observabi- lité structurelle. Exemple 1: Considérons ΣΛ le système linéaire structuré défini par ses matrices structurées : A =   0 0 0 λ1 λ2 λ3 0 0 0   , C = λ4 λ5 λ6 , (2) Son graphe associé G(ΣΛ) est donné Figure 1. III. Observabilité structurelle La commandabilité structurelle ou la notion duale d’ob- servabilité structurelle ont été étudiées dans le passé [2], Fig. 1. G(ΣΛ) et la contraction de l’Exemple 1 [8]. Rappelons qu’un système est structurellement obser- vable s’il est observable pour presque toutes les valeurs des paramètres. On définit le concept de contraction qui est la notion duale de la dilatation définie par Lin dans l’étude de la commandabilité. Définition 1: On considère ΣΛ un système linéaire struc- turé défini par (1) et son graphe associé G(ΣΛ) où l’en- semble des sommets est Z et l’ensemble des arcs est W. On considère un ensemble S de kS sommets d’état. Notons E(S) l’ensemble des sommets wi pour i = 1, . . . , lS de Z tels qu’il existe un arc (xj, wi) de W où xj ∈ S. S est une contraction si kS − lS = dS > 0 (3) Reconsidérons le système structuré ΣΛ de l’Exemple 1. Dans cet Exemple 1, on a une contraction S = {x1, x2, x3} parce que E(S) = {x2, y} et kS − lS = 1 comme le montre la Figure 1. Rappelons la caractérisation graphique de l’observabilité structurelle, qui sera utilisée dans la suite [2], [8] : Théorème 1: On considère ΣΛ un système linéaire struc- turé défini par (1) avec son graphe associé G(ΣΛ). Ce sys- tème est structurellement observable si et seulement si : 1. ΣΛ est connecté à la sortie, 2. G(ΣΛ) ne contient pas de contraction. Revenons sur le système ΣΛ de l’Exemple 1. Ce système a une contraction, il n’est donc pas observable bien que tous ses sommets d’état soient connectés à la sortie. Nous pouvons vérifier la matrice d’observabilité : O =   C CA CA2   =   λ4 λ5 λ6 λ1λ5 λ2λ5 λ3λ5 λ1λ2λ5 λ2 2λ5 λ2λ3λ5   , (4) qui a un rang générique de 2. Ce système est génériquement non observable, ce qui implique qu’il n’est pas observable quelle que soit la valeur des paramètres. La cause de la non observabilité dans ce cas est liée à la structure du système. Présentons un deuxième exemple pour illustrer l’observa- bilité générique. Exemple 2: Considérons le système structuré ΣΛ sui- vant : A = λ1 0 0 0 , C = λ2 λ3 , (5) Son graphe associé G(ΣΛ) est donné Figure 2. Fig. 2. G(ΣΛ) pour l’Exemple 2 e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24 Ce système n’a pas de contraction et il est connecté à la sortie donc il est génériquement observable. Vérifions la matrice d’observabilité : O = C CA = λ2 λ3 λ1λ2 0 , (6) Cette matrice a un rang générique 2. Ce rang est inférieur à 2 quand λ1 = 0 ou λ2 = 0 ou λ3 = 0. Dans la littérature, nous pouvons trouver d’autres condi- tions d’observabilité équivalentes à celles du Théorème 1. Par exemple dans [2], [8], [3], l’observabilité peut être carac- térisée par le fait que l’ensemble des sommets d’état peut être recouvert par une forme graphique particulière appe- lée cactus qui rassemble les deux conditions du Théorème 1. IV. Formulation du problème Dans cet article, nous abordons le problème de la pré- servation de l’observabilité en présence de défauts de cap- teurs. Nous nous concentrerons ici sur l’analyse de l’obser- vabilité, qui est fortement sensible aux défauts de capteurs. Nous étudierons la préservation de la connexion à la sortie et l’absence de contraction en présence de défauts de cap- teurs. Nous classerons les capteurs en trois catégories : les cap- teurs essentiels, qui sont nécessaires pour préserver la pro- priété ; les capteurs inutiles, qui ne jouent aucun rôle pour le problème et les capteurs utiles. Définition 2: On considère ΣΛ un système linéaire struc- turé défini par (1) et une propriété P vraie pour ce système. Nous appelons solution du problème de défauts de capteurs un ensemble de capteurs sans défauts V ⊂ {y1, y2, . . . yp} tels que P reste vraie avec l’ensemble V . Pour cette pro- priété P, un capteur y∗ peut être classé dans une de trois catégories suivantes : 1. y∗ est dit capteur inutile si pour toute solution V qui contient y∗ , {V \y∗ } est encore une solution pour P. 2. y∗ est dit capteur utile si y∗ n’est pas inutile . 3. y∗ est dit capteur essentiel si y∗ appartient à toute so- lution V . Dans cet article, nous considérerons successivement trois propriétés différentes : la connexion à la sortie, l’absence de contraction, l’observabilité et leur préservation en présence de défauts de capteurs. V. Préservation de la connexion à la sortie A. Composantes fortement connexes et graphe de connexion Considérons ΣΛ un système linéaire structuré défini par (1) avec son graphe associé G(ΣΛ). Deux sommets vi et vj dans G(ΣΛ) sont dits équivalents s’il existe un chemin de vi à vj et un chemin de vj à vi. Dans ce contexte on suppose que vi est équivalent à lui-même. Les classes d’équivalences correspondant à cette relation d’équivalence s’appellent les composantes fortement connexes de G(ΣΛ). Il existe des algorithmes standards de type optimisation combinatoire pour trouver la décomposition canonique du graphe en composantes fortement connexes. Les sommets de sortie yi sont des composantes fortement connexes com- posées d’un sommet unique. Les composantes fortement connexes peuvent être dotées d’un ordre partiel naturel. Les composantes fortement connexes Ci et Cj sont telles que Ci Cj s’il existe un arc (vj, vi) où vi ∈ Ci et vj ∈ Cj. Les éléments infimaux avec cet ordre sont les composantes fortement connexes sans arcs sortants. Notons que les som- mets de sortie sont de tels éléments infimaux. Les compo- santes fortement connexes qui n’ont que des arcs sortants vers les sorties sont appelées les composantes pré-infimales. Le résultat suivant est simple à prouver. Proposition 1: Considérons ΣΛ un système linéaire structuré défini par (1) avec son graphe associé G(ΣΛ). ΣΛ est connecté à la sortie si et seulement si toutes les compo- santes infimales de G(ΣΛ) sont des sommets de sortie. Pour étudier la connexion à la sortie, nous présentons main- tenant un nouveau graphe non orienté. Définition 3: Le graphe C(ΣΛ) = (Zc, Wc) dit graphe de connexion est construit à partir de G(ΣΛ) comme suit : – l’ensemble des sommets est Zc = V ∪ V ∪ Y ∪ z avec V = {v1, v2, . . . , vk} où chaque vi corres- pond à une composante pré-infimale de G(ΣΛ), V = {v1, v2, . . . , vl} où chaque vi correspond à une compo- sante infimale de G(ΣΛ) qui n’est pas une sortie, Y est l’ensemble des sommets de sortie {y1, y2, . . . , yp} et z est un sommet additionnel, – l’ensemble d’arêtes est Wc = {(vi, yj)| s’il existe un chemin de la composante pré-infimale correspondante à vi, à yj} ∪ {(yj, z) ∀j}. Notons que par la définition de C(ΣΛ), on relie tous les sommets de sortie yj au sommet additionnel z. Exemple 3: Considérons ΣΛ un système linéaire struc- turé avec son graphe associé G(ΣΛ) présenté Figure 3. Fig. 3. G(ΣΛ) pour l’Exemple 3 Fig. 4. C(ΣΛ) pour l’Exemple 3 e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24 Dans cet exemple, toutes les composantes infimales {y1}, {y2},. . . {y6} sont des sorties donc V = ∅. On a quatre composantes pre-infimales dans G(ΣΛ) donc les sommets correspondants de V sont v1 ≈ {x1}, v2 ≈ {x2}, v3 ≈ {x5} et v4 ≈ {x7}. On relie chaque vi aux sommets de sortie correspondants : v1 à y1, y2 et y3 ; v2 à y2 et y3 . . . Ensuite, on relie chaque sortie yj à z par une arête. Le graphe de connexion C(ΣΛ) est donné Figure 4. Un graphe non orienté est dit connexe s’il existe une chaîne entre deux sommets quelconques. Un graphe non orienté peut être décomposé en composantes connexes disjointes. C(ΣΛ) nous permet d’analyser de manière simple la connexion à la sortie du système ΣΛ. Proposition 2: Le graphe G(ΣΛ) est connecté à la sor- tie si et seulement si le graphe de connexion C(ΣΛ) est connexe. Revenons sur l’Exemple 3, comme le graphe de connexion C(ΣΛ) est connexe, ainsi G(ΣΛ) est connecté à la sortie. B. Séparateurs irréductibles Définition 4: Considérons H(Z, W) un graphe non orienté connexe. Pour S ⊆ Z : – S est dit un séparateur si en enlevant à H(Z, W), S et les arêtes qui partent de S, le reste n’est plus connexe. – S est dit un séparateur irréductible s’il n’existe pas un sous-ensemble propre de S qui est un séparateur de H. Remarque 1: Si S, de cardinalité plus grande que 1, est un séparateur irréductible d’un graphe de connexion H, pour n’importe quel sommet s ∈ S, {S\s} n’est pas un séparateur, donc la suppression de {S\s} ne déconnecte pas H. Le graphe de connexion C(ΣΛ) capture toute l’information concernant la connexion à la sortie du système. Nous uti- liserons les séparateurs irréductibles composés seulement des sommets de sortie sur ce graphe pour analyser la pré- servation de la connexion à la sortie en cas de défauts de capteurs. C. Préservation de la connexion à la sortie en présence de défauts de capteurs Dans cette sous-section nous nous concentrerons sur les séparateurs composés seulement de sommets de sortie. Proposition 3: Considérons ΣΛ un système linéaire structuré défini par (1) avec son graphe associé G(ΣΛ) et son graphe de connexion C(ΣΛ). La connexion à la sortie de ΣΛ est préservée si et seulement s’il existe au moins un capteur sans défaut dans chaque séparateur irréductible de C(ΣΛ) inclus dans Y . Pour construire l’ensemble des séparateurs irréductibles dans Y d’un graphe de connexion C(ΣΛ), nous pouvons utiliser l’algorithme suivant : Algorithme 1: Énumération de tous les séparateurs irré- ductibles 1. Pour tout vi : – S(vi) := {yj|(vi, yj) ∈ Wc} 2. Pour tout S(vi) : – S’il n’existe pas k tel que S(vk) ⊂ S(vi), alors S(vi) est un séparateur irréductible. La construction de l’algorithme vient du fait que S(vi) est l’ensemble des sommets voisins de vi, ainsi c’est un sépa- rateur pour vi. De plus, si S(vi) ne contient aucun autre séparateur, il est irréductible. Théorème 2: Considérons ΣΛ un système linéaire struc- turé défini par (1) avec son graphe associé G(ΣΛ) et son graphe de connexion C(ΣΛ). Supposons que la propriété de la connexion à la sortie soit vraie pour G(ΣΛ). 1. Les capteurs inutiles ¯L pour la propriété de connexion à la sortie sont ceux qui n’appartiennent à aucun séparateur irréductible de C(ΣΛ) inclus dans Y . 2. Les capteurs essentiels ¯E pour la propriété de connexion à la sortie sont les séparateurs irréductibles de C(ΣΛ) inclus dans Y de cardinalité 1. Reconsidérons l’Exemple 3. En appliquant l’Algorithme 1, on trouve deux séparateurs irréductibles inclus dans l’ensemble Y : S1 = {y2, y3} et S2 = {y4}. On a donc ¯L = {y1, y5, y6} l’ensemble des capteurs inutiles parce que ces capteurs n’appartiennent à aucun séparateur irréduc- tible. L’ensemble des capteurs utiles est ¯F = {y2, y3, y4} et l’ensemble des capteurs essentiels ¯E = {y4}. Pour préser- ver la connexion à la sortie de ce système, on doit assurer au moins {y2, y4} ou {y3, y4} sans défauts. On peut vérifier aisément ces résultats sur les graphes C(ΣΛ) et G(ΣΛ) des figures 4 et 3. VI. Absence de contraction A. Graphe biparti Dans cette sous-section, nous caractériserons les contrac- tions. Ceci sera réalisé en utilisant un graphe biparti associé au système ΣΛ. Le graphe biparti est un outil qui est bien adapté aux calculs de rang générique des matrices. Il est connu [2] que l’absence de contraction est équivalente au fait que la matrice A C est génériquement de rang plein. Nous considérons un système linéaire structuré ΣΛ du type (1) comme précédemment. Nous présentons maintenant le graphe biparti B(ΣΛ) comme suit. Le graphe biparti de ce système est B(ΣΛ) = (B+ , B− ; W ) où les ensembles B+ et B− sont deux ensembles disjoints de sommets et W est l’ensemble d’arcs. L’ensemble de som- mets B+ est donné par X+ , l’ensemble de sommets B− est donné par X− ∪ Y , où X+ = {x+ 1 , . . . , x+ n } est le premier ensemble de sommets d’état, X− = {x− 1 , . . . , x− n } est le deuxième ensemble de sommets d’état et Y = {y1, . . . , yp} est l’ensemble de sommets de sortie. Notons que nous avons dédoublé chaque sommet d’état xi de G(ΣΛ) en deux sommets x+ i et x− i . L’ensemble d’arcs W est dé- fini par WA ∪ WC où WA = {(x+ j , x− i )|Aij = 0} et WC = {(x+ j , yi)|Cij = 0}. Un élément de la matrice Aij = 0 (resp. Cij = 0) signifie que l’élément (i, j) de la matrice A (resp. C) est un paramètre libre (structurellement différent de zéro). Un couplage dans un graphe biparti B = (B+ , B− ; W ) est un ensemble d’arcs M ⊆ W tels que les arcs dans M n’ont aucun sommet en commun. Le cardinalité d’un couplage, (le nombre des arcs) s’appelle également sa taille. Un cou- plage M est dit maximum s’il a une cardinalité maximum. Le problème du couplage maximum est de trouver un cou- plage de cardinalité maximale. Ce problème peut être ré- solu en utilisant des algorithmes très efficaces basés sur les chaînes alternées augmentantes ou les idées de la théorie e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24 du flot maximal [9]. Avec un couplage M, un sommet sur B est dit saturé par M s’il appartient à ce couplage La notion de couplage permet une caractérisation simple de l’absence de contraction en terme de graphe biparti du système [10], ce qui dans notre cas peut être énoncé comme suit. Proposition 4: Considérons ΣΛ un système linéaire structuré défini par (1) avec son graphe associé G(ΣΛ) et avec son graphe biparti associé B(ΣΛ). Il n’existe pas de contraction dans G(ΣΛ) si et seulement s’il existe un cou- plage de taille n dans B(ΣΛ). B. Décomposition de Dulmage-Mendelsohn (DM) [8] La DM-Décomposition permet de décomposer de fa- çon unique un graphe biparti B en sous-graphes bipartis irréductibles partiellement ordonnés Bi = (B+ i , B− i ; Wi ) (i = 0, 1, . . . , r, ∞) dits les composantes de la DM. Ces composantes ont les propriétés suivantes : Proposition 5: Considérons B = (B+ , B− ; W ) un graphe biparti et Bi = (B+ i , B− i ; Wi ) (i = 0, 1, . . . , r, ∞) ses DM-Composantes. 1. Un couplage maximum sur B est une union de couplages maximaux sur les DM-Composantes Bi (i = 0, 1, . . . , r, ∞). 2. Un sommet v ∈ B− 0 (ou B+ i , B− i (i = 1, . . . , r) ou B+ ∞) est saturé par n’importe quel couplage maximum sur B. 3. Un sommet v ∈ B+ appartient à B0 si et seulement s’il existe un couplage maximum sur B qui ne sature pas v. 4. Un sommet v ∈ B− appartient à B∞ si et seulement s’il existe un couplage maximum sur B qui ne sature pas v. Fig. 5. DM-Décomposition En effet, la DM-Décomposition est équivalente à une per- mutation des lignes et des colonnes de la matrice A C pour obtenir la forme bloc diagonale présentée Figure 5. Nous avons rΣ = rang A C ≤ n. Le fait que rΣ < n c’est à dire que la matrice AT ; CT T n’a pas le rang plein implique qu’il y a des colonnes de AT ; CT T qui sont la combinaison linéaire des autres colonnes. Par cette permutation, nous pouvons faire apparaître une bloc qui correspond avec la partie B0 de la DM-Décomposition. On a r − rΣ = |B+ 0 | - |B− 0 | où |.| est la cardinalité d’un ensemble. Fig. 6. B(ΣΛ) pour l’Exemple 3 Exemple 4: Considérons le système ΣΛ dont le graphe associé G(ΣΛ) est donné Figure 3 et considérons le graphe biparti B(ΣΛ). Nous construisons la DM-Décomposition de B(Σλ) comme dans [8]. Alors B0 = ∅ et B∞ = {x− 4 , x− 6 , x− 7 , y5, x+ 4 , x− 2 , x− 5 , y1, x+ 1 , y2, x+ 3 , x− 1 , x+ 2 , y3}. Fi- nalement, B1 = {x+ 5 ; y4}, B2 = {x+ 6 ; x− 3 } et B3 = {x+ 7 ; y6} comme montré Figure 6. C. Absence de contraction Proposition 6: Considérons ΣΛ un système linéaire structuré défini par (1) avec son graphe associé G(ΣΛ) et son graphe biparti associé B(ΣΛ). G(ΣΛ) ne contient pas de contraction si et seulement si la DM-Décomposition de B(ΣΛ) est telle que B0 = ∅. Nous cherchons maintenant les sorties qui peuvent être sup- primées sans créer des contractions. Théorème 3: Considérons ΣΛ un système linéaire struc- turé défini par (1) avec son graphe associé G(ΣΛ) et son graphe biparti associé B(ΣΛ). L’ensemble de capteurs essentiels ˆE pour l’absence de contraction est l’ensemble de sommets de sortie qui ap- partiennent aux composantes Bi, (i = 1, . . . r) dans la DM- Décomposition de B(ΣΛ). Par les propriétés de la DM-Décomposition, le nombre de sommets de B+ i est égal au nombre de sommets de B− i , (i = 1, . . . , r). Si nous supprimons un sommet de sortie qui appartient à B− i , ceci créera une contraction. Donc, tous les capteurs dans les composantes Bi, (i = 1, . . . , r) appar- tiennent à n’importe quelle solution du problème d’absence de contraction et sont donc essentiels. En outre, la suppression d’un seul sommet de sortie dans B∞ ne change pas la taille du couplage maximum sur B. Donc, aucun sommet de sortie dans B∞ n’est essentiel. Pour déterminer le nombre minimal de sommets de sor- tie dans toute solution pour l’absence de contraction, nous pouvons ramener l’analyse à B∞ comme suit : Algorithme 2: 1. Pour tout arc (v+ , v− ) de B∞, lui assi- gner un poids 0 si v− est un sommet d’état, un poids 1 si v− est un sommet de sortie. e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24 2. Trouver un couplage maximum de poids minimal dans B∞. Noter Wm le poids de ce couplage c’est à dire la somme des poids d’arcs qui le composent. 3. Le nombre minimal de sommets de sortie dans une solu- tion est Wm + card( ˆE). Théorème 4: Considérons ΣΛ un système linéaire struc- turé défini par (1) avec son graphe associé G(ΣΛ) et son graphe biparti associé B(ΣΛ). Considérons la partie B∞ de la DM-Décomposition de B(ΣΛ). L’ensemble des capteurs inutiles ˆL pour l’absence de contraction est l’ensemble des sommets de sortie qui n’ap- partiennent à aucun couplage maximum de poids minimal sur B∞. Remarque 2: Nous pouvons montrer que l’utilisation de l’Algorithme 2 sur B(Σλ) nous fournira un ensemble mini- mal de capteurs non défaillants qui assurent l’absence de contraction c’est à dire les capteurs qui appartiennent à un couplage maximum de poids minimal. Reconsidérons le système structuré ΣΛ de l’Exemple 3 avec son graphe associé dans la Figure 3. La DM-Décomposition de ce système est illustrée dans la Figure 6. Dans ce cas sur B∞, il existe au moins un couplage maxi- mum de poids minimal qui ne sature pas y5, par l’exemple le couplage composé par {(x+ 4 , x− 2 ); (x+ 3 , x− 1 ); (x+ 2 , y); (x+ 1 , y1)}. Par contre, n’importe quel couplage maximum de poids mi- nimal sature deux sommets de l’ensemble {y1, y2, y3}. Nous avons donc ˆL = {y5} l’ensemble des capteurs inutiles et ˆF = {y1, y2, y3, y4, y6} est l’ensemble des capteurs utiles. Nous avons deux capteurs essentiels ˆE = {y4, y6} (parce que y4 ∈ B1 et y6 ∈ B3) pour l’absence de contraction. VII. Préservation de l’observabilité Par les analyses des paragraphes V et VI, nous avons le Théorème suivant : Théorème 5: Considérons ΣΛ un système linéaire struc- turé défini par (1) et pour le problème de préservation de l’observabilité, en utilisant les notations des Théorème 2, Théorème 3 et Théorème 4 : – L’ensemble des capteurs essentiels est E = ¯E ∪ ˆE. – L’ensemble des capteurs inutiles est L = ¯L ∩ ˆL. – L’ensemble des capteurs utiles est F = Y \L. En effet, pour assurer que le système reste observable tout en supprimant des capteurs, le système avec les capteurs restants doit satisfaire la propriété de la connexion à la sor- tie et l’absence de contraction. Le Théorème 2 donne l’en- semble des capteurs qui peuvent être supprimés en conser- vant la propriété de connexion à la sortie. Les Théorème 3 et 4 donnent l’ensemble des capteurs qui peuvent être supprimés sans créer de contraction. Il est clair qu’un capteur qui est essentiel pour la connexion à la sortie ou essentiel pour l’absence de contraction est es- sentiel pour la préservation de l’observabilité du système. Un capteur qui est inutile pour la connexion à la sortie et inutile pour l’absence de contraction est inutile pour la pré- servation de l’observabilité du système. Reconsidérons le système décrit dans l’Exemple 3. Par l’analyse de la connexion à la sortie de ce système, on a ¯L = {y1, y5, y6}, ¯E = {y4} et ¯F = {y2, y3, y4}. Pour l’absence de contraction, on a ˆL = {y5}, ˆE = {y4, y6} et ˆF = {y1, y2, y3, y4, y6}. En utilisant le Théorème 5 avec ces ensembles de capteurs, on obtient : – L’ensemble des capteurs essentiels E = ¯E ∪ ˆE = {y4, y6} – L’ensemble des capteurs inutiles L = ¯L ∩ ˆL = {y5} – L’ensemble des capteurs utiles F = Y \L = {y1, y2, y3, y4, y6} Dans cet exemple, en gardant l’ensemble des capteurs es- sentiels E = {y4, y6} et deux des trois capteurs de l’en- semble des capteurs utiles et non essentiels {y1, y2, y3} sans défaut, l’observabilité est préservée. Les ensembles mi- nimaux des capteurs non défaillants permettant de pré- server l’observabilité du système sont {y4, y6, y1, y2} ou {y4, y6, y1, y3} ou {y4, y6, y2, y3}. VIII. Conclusions et perspectives Dans cet article, nous avons revisité l’observabilité des systèmes structurés. En utilisant l’approche des graphes, nous avons focalisé notre attention sur le problème de pré- servation de l’observabilité en présence de défauts de cap- teurs. Nous avons classé les capteurs par rapport à leur na- ture critique concernant l’observabilité du système. L’uti- lisation des algorithmes standards ou des décompositions pour réduire la complexité de problème permet d’obtenir des algorithmes qui sont polynômiaux en temps de calcul et donc facilement mis en oeuvre. L’approche proposée est bien adaptée pour l’analyse structurelle. Elle permet de dé- terminer les capteurs qui sont essentiels c’est à dire dont un défaut mène à la perte de l’observabilité, les capteurs qui sont inutiles pour la préservation de l’observabilité et ceux qui sont utiles. Cette approche peut également être utilisée pour résoudre des problèmes de détection et de diagnostic de défauts en présence de défauts de capteurs. Références [1] J. M. Dion and C. Commault. Approche structurelle du diag- nostic, application à un modèle de colonne à distiller. In Confé- rence Internationale Francophone d’Automatique,CIFA, Bor- deaux, France, 2006. [2] C.T. Lin. Structural controllability. IEEE Trans. Automat. Control, 19(3) :201–208, June 1974. [3] J. M. Dion, C. Commault, and J. van der Woude. Generic pro- perties and control of linear structured systems : a survey. Au- tomatica, 39(7) :1125–1144, 2003. [4] R.W. Shields and J.B. Pearson. Structural controllability of mul- tiinput linear systems. IEEE Trans. Automat. Contr., 21 :203– 212, 1976. [5] K. Glover and L.M. Silverman. Characterization of structu- ral controllability. IEEE Trans. Automat. Contr., 21 :534–537, 1976. [6] M. Blanke, M. Kinnaert, J. Lunze, and M. Staroswiecki. Diag- nosis and fault-tolerant control. Springer-Verlag, 2003. [7] C. Commault, J. M. Dion, and D. H. Trinh. Observability pre- servation under sensor failure. In IEEE CDC Conf., San Diego, USA, 2006. [8] K. Murota. Systems Analysis by Graphs and Matroids, volume 3 of Algorithms and Combinatorics. Springer-Verlag New-York, Inc., 1987. [9] J.E. Hopcroft and R.M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. on Comp., 2 :225–231, 1973. [10] C. Commault, J. M. Dion, and J. van der Woude. Characteriza- tion of generic properties of linear structured systems for efficient computations. Kybernetika, 38(5) :503–520, 2002. e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 19-24