Aspects algorithmiques de l ’analyse structurelle pour la surveillance

Aspects algorithmiques de l ’analyse structurelle pour la surveillance

D. Düstegör, V. Cocquempot, M. Staroswiecki

Contact : vincent.cocquempot@univ-lille1.fr

Université de Lille 1

LAGIS UMR 8146 : Laboratoire d'Automatique, deGénie Informatique et Signal

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

2/40

Plan de la présentation

• Conclusions/Perspectives

• Contexte de nos travaux

• Principes généraux de l'approche structurelle.

• Aspects algorithmiques de la méthode

• Adaptativité de la méthode (chgt de structure)

Illustration sur un modèle de vanne, projet européen DAMADICS

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

3/40

Contexte des travaux

• Début des travaux aux LAIL (ex LAGIS) en 1990 (Thèse de Ph. Declerck)

..... depuis, nombreux articles, plusieurs thèses : formalisation de la méthode

• Plusieurs applications : projets européens : COSY, DAMADICS, CHEM, collabo. indust. : EDF, IRSyD, Renault Trucks

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

4/40

Contexte des travaux

• Thèse de Dilek Düstegör "Aspects algorithmiques de l'analyse structurelle pour la surveillance", soutenance prévue avant Déc. 2005

• Objectifs : étude de nouvelles propriétés, implantation de la méthode, amélioration des algorithmes

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

5/40

RRA

RRA : Relation de redondance analytique

expriment des liens entre variables connues du système

problème général d’élimination de variables inconnues

calcul des variables inconnues (en fonction des variables connues) puis substitution dans relations redondantes

Méthode possible de génération

Résidu0)u,y(r RRA

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

6/40

Motivations de l’AS• Systèmes complexes : nombreuses variables et contraintes

• Co-existence de différents types de modèles : qualitatifs, quantitatifs, statiques, dynamiques, règles, tables, …

• Description du système sous forme de multiples sous-systèmes interconnectés

Nécessité d’une modélisation et de méthodes d’analyse adaptées

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

7/40

Objectifs de l’AS

• Déterminer des propriétés du système

• Déterminer les chemins de calculs des variables inconnues (observabilité)

• Déterminer les chemins de calcul des résidus

Analyse et aide à la conception (placement de capteurs)

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

8/40

Modélisation structurelle

Système = (C,X,K)

C : ensemble de contraintes

X : ensemble de variables inconnues

K : ensemble de variables connues

Description structurelle

- graphe bi-partie

- matrice d’incidence

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

9/40

Défaillances

Défaillance composant = contraintes non vérifiées

ajout de variables de défaillances dans modèle structurel

permet d ’analyser la sensibilité (structurelle) des Résidus

plusieurs niveaux de connaissance des défaillances

indication des contraintes affectées

hypothèse (dynamique) sur la défaillance

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

10/40

Modèle structurel

S : C XK

(fi,zj) S(fi,zj) = 1

{0,1}ssi fi contraint l’évolution de zj

S(fi,zj) = 0 sinon

Matrice d’incidence

Graphe bi-partie

z1

c1

z2 z3

c2

z1 z2 z3

c1

c2

1 1 0

0 1 1

Graphe contraintes/variables non orienté

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

11/40

Application Vanne (Damadics)

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

12/40

Application vanne

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

13/40

Application vanne

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

14/40

Couplage

Couplage (Matching)

= « Sélection » de couples (ci, xi)

indique que xi est calculée à partir de ci

(en supposant les autres variables connues)

Compléments : Couplage maximal, Couplage complet

couplage orientation du graphe

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

15/40

DM Décomposition• Décomposition de Dulmage Mendehlson...

– permutation de lignes et colonnes.– 3 sous-systèmes caractérisés

• S+ : système sur-contraint : plus de contraintes que de variables

Plusieurs possibilités pour résoudre le système, existence de redondance

•S0 : système juste contraint : autant de contraintes que de variables

1 solution (observabilité), pas de redondance

•S- : système sous-contraint : moins d’équation que de variable

pas de solution

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

16/40

Application vanne

Sous-système sur-contraint

Syst. sur-contraint : 18x15 Syst. juste contraint : 4x4

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

17/40

Cycles

• cycles algébriques

Détermination des cycles différentiels ??

Pas de problème (structurel)

problème d’observabilité

donc de surveillabilité !

• cycles différentiels

couplage causal = pas de cycle différentiel

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

18/40

Détectabilité

Condition nécessaire

Une défaillance est détectable si elle appartient à la partie sur-contrainte du système et qu ’il existe un couplage causal complet sur les variables

Existence d ’un résidu sensible à

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

19/40

Application Vanne

Parmi les 19 défaillances du cahier des charges seules 2 défaillances (f16 et f9) ne sont pas détectables

Proposition d’implantation de capteurs supplémentaires (ajout de redondance, suppression de cycles différentiels)

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

20/40

Localisabilité

Table de signature de défaillance

Permet d ’indiquer toutes les structures de résidus possibles et donc toutes les défaillances détectables et localisables

Table de localisabilité

1 2

r1

r2

1 0

0 1

Permet d ’indiquer les possibilités de localisation des défaillances

1 2

1

2

1 0

0 1

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

21/40

Localisabilité

DM-décomposition de la table de localisabilité

Améliorations : ajout de capteurs

modèle de défaillances (hypothèse de défauts)

sous ensembles de défaillances non localisables entre elles

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

22/40

Application Vanne

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

23/40

Application Vanne

Découplage possible

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

24/40

Algorithmes

• DM Décomposition

• Construction table (complète) de signatures

• Générer les séquences de calcul des RRA

• Adaptativité en cas de chgt de structure

Nécessité d’algorithmes performants dans le cas de systèmes complexes (grd nbre de contraintes et de variables)

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

25/40

Algo : Table de signature

• algo 1 : exhaustif

Toutes les signatures

possibles sont obtenues

Algo très lourd!!

MAIS

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

26/40

Algo : Table de signature

Utilisation des

Blocs de Koenig-Hall

composantes connectées

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

27/40

Algo : Table de signature

• Algo 2 : choisir 1 couplage (quelconque) par bloc de Koenig-Hall et non tous les couplages

• Tous les couplages sur les blocs de KH sont équivalents vis à vis de la structure du résidu

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

28/40

Comparaison complexité

Algo 2 : cas le + favorable

Algo 1

Au pire : même complexité que algo 1

)!mn(!n

TM

!m

T

)!mn(!m!n

T MKH

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

29/40

Application vanne

Sous-système sur-contraint

17 couplages possibles

qui conduisent à la même structure de résidu

Nbre total de couplages possibles (algo1 : méthode exhaustive): 532

Algo 2 : 205 couplages permettant d’obtenir les 10 structures de résidus

bloc de KH

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

30/40

Choix du couplage sur les blocs de KH

• complexité des calculs

• robustesse des calculs

• sensibilité aux défaillances

Choix du couplage sur les blocs de Hall pas anodin

Couplage = séquence de calcul des résidus

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

31/40

Ordres de partiels de préférence

• par rapport aux variables:

kxj cci

préférable de coupler xi à cj plutôt qu’à ck

• par rapport aux contraintes:

kcj xxi

préférable de coupler ci à xj plutôt qu’à xk

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

32/40

Application Vanne

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

33/40

Choix du couplageChoix du « meilleur »

couplage

2 démarches :

• utilisation directe des ordres partiels : algo SMP

• pondération du graphe structurel fonction des ordres partiels, puis fonction de coût

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

34/40

Utilisation directe des ordres partiels

Problème classique de combinatoire : « stable Marriage Problem »

algorithmes existants Gale-Shapley

Liste incomplète

Existence de couplage sans préférenceIci

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

35/40

Application Vanne

Meilleur couplage obtenu

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

36/40

Pondération du graphe

Quantification de la préférence Pondération du graphe

Soit (xi,cj) un arc du graphe

cj placé en kième position dans la liste de préférence de xi

Matrice de pondération (de coût)

Pb: trouver le couplage maximal de poids minimum

S(i,j) = k

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

37/40

Application Vanne

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

38/40

Application Vanne

• Meilleur couplage obtenu identique au précédent.

• Meilleur couplage, poids total minimum : 12

• Poids du couplage directement sous-optimal : 13

• Moins bon couplage, poids total maximum : 17

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

39/40

Changement de structure

• Ajout de composants (évolution , contraintes d’exploitation)

• Perte de composants (défaillance, évolution )

• Adaptativité des algorithmes : ne pas reprendre au début

• Algorithme spécifique suivant le bloc dans lequel la contrainte est ajoutée

6/09/05 V. Cocquempot, Aspects algo. de l'AS pour la surveillance"

40/40

Conclusion

• AS : outil performant pour analyse et conception de systèmes complexes

• des algorithmes performants, simples et constructifs

Nécessite

• des concepts et outils de représentation simples, efficaces