40
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, Génie Informatique et Signal

Aspects algorithmiques de l ’analyse structurelle pour la surveillance

Embed Size (px)

DESCRIPTION

Aspects algorithmiques de l ’analyse structurelle pour la surveillance. D. Düstegör, V. Cocquempot, M. Staroswiecki. LAGIS UMR 8146 : Laboratoire d'Automatique, de Génie Informatique et Signal. Université de Lille 1. Contact : [email protected]. - PowerPoint PPT Presentation

Citation preview

Page 1: 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 : [email protected]

Université de Lille 1

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

Page 2: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 3: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 4: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 5: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 6: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 7: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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)

Page 8: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 9: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 10: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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é

Page 11: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

11/40

Application Vanne (Damadics)

Page 12: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

12/40

Application vanne

Page 13: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

13/40

Application vanne

Page 14: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 15: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 16: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 17: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 18: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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 à

Page 19: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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)

Page 20: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 21: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 22: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

22/40

Application Vanne

Page 23: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

23/40

Application Vanne

Découplage possible

Page 24: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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)

Page 25: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 26: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 27: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 28: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 29: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 30: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 31: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 32: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

32/40

Application Vanne

Page 33: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 34: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 35: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

35/40

Application Vanne

Meilleur couplage obtenu

Page 36: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 37: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

37/40

Application Vanne

Page 38: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 39: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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

Page 40: Aspects algorithmiques de l ’analyse structurelle pour la surveillance

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