ECOLE GDMACS 09 1 Diagnostic décentralisé des Systèmes à Evénements Discrets Moamar SAYED MOUCHAWEH Maître de Conférences HDR Centre de Recherche en STIC

ECOLE GDMACS 09 1

Diagnostic décentralisé des Systèmes à Evénements Discrets

Moamar SAYED MOUCHAWEH

Maître de Conférences HDR

Centre de Recherche en STIC (CReSTIC)

Université de Reims

[email protected]

ECOLE GDMACS 09 2

Table des matières

1. Classification des méthodes de diagnostic des SED selon la structure de prise de décision

2. Diagnostic centralisé

3. Diagnostic décentralisé sans coordinateur

4. Diagnostic décentralisé avec coordinateur (conditionnel)

5. Notions de co-diagnosticabilité

ECOLE GDMACS 09 3

1. Classification des méthodes de diagnostic des SED selon la structure de

prise de décision

Centralisée [Sampath 95]

Décentralisée sans coordinateur [Lafortune 05]

Décentralisée avec coordinateur [Debouk 00, Wang 05]

Distribuée [Fabre 02, Pencolé 05,Qiu 05, Su 04]

ECOLE GDMACS 09 4


- Un seul modèle avec un seul diagnostiqueur

Modèle Global du Système

Diagnostiqueur Global

Décision finale du diagnostic

- Inconvénients : Explosion combinatoire, faible robustesse,

faible maintainabilité, …

Structure centralisée

ECOLE GDMACS 09 5

- Un seul modèle avec plusieurs

diagnostiqueurs locaux

- Pas de besoin de coordinateur pour les

décisions de diagnostiqueurs locaux

architecture non conditionnelle

Agrégation booléenne

Modèle Globale G

P1 P2 Pn

Gd1 Gd2 Gdn

Fusion des décisions

Projection


Structure décentralisée sans coordinateur

ECOLE GDMACS 09 6

Modèle Global du Système

Diagnostiqueur local 1


Coordinateur

Communication

Observateur local 1

Observateur local 2

Décision 1 Décision 2

Décision finale

- Une communication limitée est

nécessaire pour résoudre le problème

d’ambiguïté entre les différents

diagnostiqueurs => Coordinateur

- Architecture conditionnelle :

«Défaut si la décision de tous les

autres

diagnostiqueurs est ‘pas de défaut’ »


Structure décentralisée avec coordinateur

ECOLE GDMACS 09 7

- Plusieurs sous modèles chacun a son

diagnostiqueur local

- Communication entre diagnostiqueurs

pour affiner le diagnostic

- Inconvénients : complexité du

protocole de communication, délai de

communication, ..



Modèle local 1 Modèle local 2

Communication

Observateur local 1 Observateur local 2

Décision 1 Décision 2


Structure distribuée

ECOLE GDMACS 09 8

2. Structure centralisée

C5 C1 noconso

C6 FV C7 AP

C2 conso C3 DP C4

OV

conso

noconso

VFC VOC

VF VO

OV

FV

FC OC

OVFV

Poff Pon DP

AP

AP DP

OV

FV

FV OV

a) Modèle de la vanne

b) Modèle de la pompe

FV – Fermeture Vanne

OV – Ouverture Vanne

FC- Fermeture Collée

OC – Ouverture Collée

AP – Arrêter Pompe

DP – Démarrer Pompe

VF – Vanne Fermée

VO- Vanne Ouverte

VFC – Vanne Fermée Collée

VOC – Vanne Ouverte Collée

Poff – Pompe arrêtée

Pon – Pompe en marche

conso – Demande de consommation

noconso - aucun demande de consommation

c) Modèle de la commande

ECOLE GDMACS 09 9

- H(Vanne,Pompe,•) = indique la sortie du capteur mesurant le flux : NF = Non flux, F = Flux

- Le • précise que la sortie du capteur est totalement indépendante de la commande

- Le modèle global représentant le fonctionnement normal et défaillant est obtenu par une composition synchrone des modèles locaux

H(VF, Poff, ●) = NF

H(VFC, Poff, ●) = NF

H(VOC, Poff, ●) = NF

H(VF, Pon, ●) = NF

H(VO, Pon, ●) = F

H(VFC, Pon, ●) = NF

H(VOC, Pon, ●) = F

2. Structure centralisée

ECOLE GDMACS 09 10

OV , F

FV , NF

VF VO VOC VFC

FV , NF FV , F

DP , NF

AP , NF AP , F

DP , F

1

noconso, NF

2 FC

conso, NF

conso, NF

noconso, NF

3 5 FC

7 9 FC

13

17

19 20 FC

12 14 FC

4 6 FC

8 10 FC

23

24

16

18

21

22

11 OC

15 OC

FV , NF

DP , NF

AP , NF

conso, NF

OV , NF

FV , NF

noconso, F

OV , F

conso, NF

noconso, NF

conso, F

noconso, F

Poff

Pon

Poff

Poff

Poff

Poff

Pon

Pon

Pon

C1

C3

C2

C7

C5

C6

C4

C6

C5

AP , NF AP , NF

Etats de la commande

Etats de la pompe

Etats de la vanne

ECOLE GDMACS 09 11

1N

3N, 5F1

7N, 9F1

11N

15N, 18F2

21F2

22F2

23F2

24F2

noconso, F

conso, NF

FV, F

OV, F

DP, NF

AP, NF

conso, NF

Noconso, NF 8N, 10F1

FV, NF

conso, NF

DP, F FV, F

12N, 14F1 AP, NF

16F2

18F2

noconso, F

OV, F

FV, NF 19N

AP, NF 13F1

17F1

20F1

14F1

5F1

9F1

noconso, NF

FV, NF

AP, NF

conso, NF

DP, NF

OV, NF

OV, NF

4N, 6F1

ECOLE GDMACS 09 12

2. Structure centralisée [Genc 03]

uo

uo

f1

e

a

a a

P1 P2 P3

P4 P5 P6

P7 P8 P9 P10

t1 t2 t3

t4 t5 t6 t7

1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0

0 0 0 0 1 0 0 0

Xd0 =

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 f1 f2

a) Modèle du procédé b) Modèle du diagnostiqueur

c) Matrice d’états du diagnostiqueur

uo

uo

f1

e

a

a a

P1 P2 P3

P4 P5 P6

P7 P8 P9 P10

t1 t2 t3

t4 t5 t6 t7

ECOLE GDMACS 09 13

1

2 3 6

4 5

7 8

c1 c1

c1

c2 c2 c2

b2 a2 f2 f1

f1

a1 b1

1N, 2F1, 3F1, 6F2

4F1 5F1 6F2

a1 a2 c2

c1

c1 c1

c2

7N 8N

b1 b2

c2 c2 Procédé G Diagnostiqueur global Gd

3. Structure décentralisée sans coordinateur

- Σo = {a1, a2, b1, b2, c1, c2}, ПF1 = {f1} et ПF2 = {f2}

- Σo1 = {a1, a2, c1, c2} pour diagnostiqueur local Gd1

- Σo2 = {b1, b2, c1, c2} pour diagnostiqueur local Gd2

ECOLE GDMACS 09 14

Diagnostiqueur G

1N, 2F1, 3F1, 5F1, 6F2, 8N

4F1 7N 6F2, 8N

a1 a2 c2

c1

c1 c2

c2

d1

1N, 2F1, 3F1, 4F1, 6F2, 7N

5F1 8N 6F2, 7N

b1 b2 c2

c1

c1 c2

c2

Diagnostiqueur d2G

3. Structure décentralisée sans coordinateur

ECOLE GDMACS 09 15

Décision locale 1 Décision locale 2Décision

Globale

Défaut Ambiguïté Défaut

Sans défaut Ambiguïté Sans défaut

En défaut si aucun site "Sans défaut" Ambiguïté Défaut

En défaut si aucun site "Sans défaut" Défaut Défaut

En défaut si aucun site "Sans défaut" Sans défaut Sans défaut

Sans défaut si aucun site en "Défaut" Ambiguïté Sans défaut

Sans défaut si aucun site en "Défaut" Défaut Défaut

Sans défaut si aucun site en "Défaut" Sans défaut Sans défaut

Ambiguïté Ambiguïté Ambiguïté

Défaut Sans défaut Conflit

En défaut si aucun site "Sans défaut" Sans défaut si aucun site en "Défaut" Conflit

4. Structure décentralisée avec coordinateur

ECOLE GDMACS 09 16

Règle : Décision de Gd1 Décision de Gd2 Décision Globale

1 N, F1, F2 N, F1, F2 Ambiguïté

2 F1 N, F1, F2 F1

3 N N, F1, F2 N

4 N, F1, F2 F1 F1

5 N, F1, F2 N N

6 F2, N N N

7 N F2, N N

8 F2, N F2, N F2

4. Structure décentralisée avec coordinateur

ECOLE GDMACS 09 17

- Notion de diagnosticabilité détermine l’ensemble des défauts qu’un

diagnostiqueur est capable de diagnostiquer, dans un délai fini après

l’occurrence d’un défaut, en se basant sur le modèle et l’ensemble

d’événements observables

- Selon la structure de prise de décision :

- Notion de diagnosticabilité [Sampath 95] (structure centralisée)

- Notion de co-diagnosticabilité [Wang 05, Qiu 05] (structure décentralisée)

- Notion de co-diagnosticabilité communicative [Su 04] (structure distribuée)

- Elle est formalisée de deux manières différentes :

- A base d’événements [Sampath 95]

- A base d’états [Lin 94, Zad 03]


ECOLE GDMACS 09 18

5. Notions de co-diagnosticabilitéDiagnosticabilité à base d’événements

- Formalisation de la notion de diagnosticabilité à base

d’événements :

• -L/s : le langage de toutes les continuations des séquences

d’événements après s : L/s = {t Σ* | st L}

• -(ПFi) : l’ensemble de toutes les traces qui se terminent par

un événement de défaut appartenant à ПFi

• - PL-1(PL(st)) : l’ensemble de toutes les traces qui ont une

projection, équivalente à celle de st.

ECOLE GDMACS 09 19

- Un langage L préfixe clos et vivant est dit diagnosticable par

rapport à une fonction de projection PL et un ensemble de

partitions de défaut ΣП ssi :

f ПFi, i {1, 2, …, r}, ni , s (ПFi), t L/s : |t| ≥

ni,w PL-1(PL(st)) f w

- Toute séquence w ayant un comportement observable, P(w),

équivalent à celui de st, P(st), doit contenir un défaut

appartenant à Пfi. Autrement dit, chaque défaut de l’ensemble

des défauts Σf doit avoir une signature distincte et observable

pour inférer l’occurrence de ce défaut et déterminer son type

après l’occurrence d’un nombre fini d’événement ni = |t|


ECOLE GDMACS 09 20

- Après la construction du diagnostiqueur Gd , et pour que le

langage L soit diagnosticable, il suffit que ce diagnostiqueur

satisfasse les deux conditions suivantes:

1) Il existe au moins un état du diagnostiqueur pour lequel le

diagnostiqueur décide avec certitude l’occurrence d’un défaut

appartenant à une partition ПFi ,

2) Il ne doit pas y avoir de cycles dits " indéterminés" pour

lesquels le diagnostiqueur est incapable de décider avec

certitude l’occurrence d’un défaut appartenant à une partition

ПFi.


ECOLE GDMACS 09 21

1N 3F1 7N 4F1 9F1 11N a b

c

6F1

5F1 10F1 12N

d

e

e


ECOLE GDMACS 09 22

SN : ensemble des états normaux correspondant à un fonctionnement désiré,

Sf : ensemble des états défaillants qui sont atteints après l’occurrence d’un défaut f ∑f,

SFi Sf : ensemble des états défaillants qui sont atteints après l’occurrence d’un défaut f ПFi

Hf : ensemble des sorties des états de SF,

HFi Hf : ensemble des sorties des états de SFi.

- Un système est diagnosticable pour un ensemble d’événements observables et un ensemble de partition de défaut ssi : i {1, 2, …, r}, x X, x’ = (st, x), x” = (w, x),w PL-1PL(st), h’

= h(x’), h” = h(x”) h’, h” HFi

5. Notions de co-diagnosticabilitéDiagnosticabilité à base d’états

ECOLE GDMACS 09 23

5. Notions de co-diagnosticabilitéDiagnosticabilité à base d’états

20

21

22

19

10

7

8

9

18

23

24

17

12

5

6

11

16

13

14

15

2

3

4

1

Etat

Radiateur

Température Load

Mode Normal N Mode défaillant F

off on on off

a

n

a

n

a

n

H

C

B

Sorties observées

Etats correspondants

Mode de fonctionnement

Y

X

N, F

Bon

15, 16

F

Con

5, 6, 17, 18

N, F

Con

5, 6

N

Bon

3, 4, 15, 16

N, F

Boff

1, 2, 13, 14

N, F

Coff

11,12,23,24

N, F

Hon

7

N

Hoff

9, 10, 21,22

N, F

Hon

7, 8, 19, 20

N, F

a) Modèle du procédé à base d’états b) Diagnostiqueur à base d’états

ECOLE GDMACS 09 24

- Notion de co-diagnosticabilité permet d’assurer que tout défaut appartenant à l’ensemble de défauts prédéfini est diagnostiqué dans un

délai borné par au moins un diagnostiqueur local

- Co-diagnosticabilité indépendente [Sengupta 98] : Un système est co-diagnosticable d’une façon indépendente si chaque diagnostiqueur local est capable de diagnostiquer un défaut en utilisant ses propres observations

- Co-diagnosticabilité locale [Pencolé 04]: Un système est co-diagnosticable localement si tous les défauts qui peuvent avoir lieu au sous-système est diagnosticable par son diagnostiqueur local


ECOLE GDMACS 09 25

- Co-diagnosticabilité collobarative [Sengupta 98, Qiu 05, Wang 05]

Un procédé composé de m diagnostiqueurs locaux avec un langage L préfixe clos et un langage de spécification K contenu dans L (K L) est dit co-diagnosticable d’une façon collaborative par rapport aux fonctions de projections PLi (i {1, …, m}) ssi :

( n ) (s L-pr(K)) (st L-pr(K), |t| ≥ n)

i {1, 2, …, m}, w P-1Li PLi(st) L, w L-pr(K)

où pr(K) est le préfixe clos du langage K et représente le comportement désiré du procédé.


ECOLE GDMACS 09 26


- Co-diagnosticabilité communicative [Sengupta 98] : Un système

est co-diagnosticable si chaque diagnostiqueur local est capable de

diagnostiquer un défaut en utilisant ses propres observations et un

ensemble des événements communiqués par d’autres diagnostiqueurs

ECOLE GDMACS 09 27

C1 C1

C1

O2

f1

O1

O2 C1

C1 C2

C1

C1

O3

O3O3

C2

f2

C1, C2 : des événements de communication

f1 et f2 deux types de défaut différents

O1, O2 et O3 des événements observables

Modèle local 1 Modèle local 2

f1 est co-diagnosticable locallement, d’une façon indépendente et colaborative

f2 est co-diagnosticable d’une façon communicative


ECOLE GDMACS 09 28

Références

Debouk R., Lafortune S., Teneketzis D., “Coordinated decentralized protocols for failure diagnosis of discrete event systems”, Discrete Event Dynamic Systems: Theory and Applications, Vol. 10, N° 1-2, pp. 33-86, 2000.

Genc S., Lafortune S., “Distributed diagnosis of discrete-event systems using Petri nets”, International Conference on Application and Theory of Petri Nets, Eindhoven, Netherlands, pp. 316-336, 2003.

Lafortune S., Wang Y., Yoo T. S., “Diagnostic Decentralise Des Systemes A Evenements Discrets”, Journal Europeen des Systemes Automatises, Vol. 99, No. 99, pp. 95-110, 2005.

Lin F., “Diagnosability of Discrete Event Systems and its Applications”, In Discrete Event Dynamic Systems, Kluwer Academic Publishers, Boston, USA, pp.197-212, 1994.

ECOLE GDMACS 09 29

Fabre E., Benveniste A., Jard C., “Distributed diagnosis for large discrete event dynamic systems”, 15th IFAC World Congress, Barcelona, Spain, 2002.

Pencolé Y., Cordier M. O., A formal framework for the decentralised diagnosis of large scale discrete event systems and its application to telecommunication networks , Artificial Intelligence Journal , Elsevier , Vol. 164 , No. 1-2 , pp. 121-170 , 2005.

Pencolé Y., Diagnosability analysis of distributed discrete event systems, In: Proc. 16th European Conference on Artificial Intelligence, Valencia, Spain, 2004

Qiu W., “Decentralized / distributed failure diagnosis and supervisory control of discrete event systems”, Thesis, Iowa State University, 2005.

Références

ECOLE GDMACS 09 30

Références

Sengupta R., Diagnosis and communication in distributed systems, In: Proc. 4th International Workshop of Discrete Event Systems, Cagliari, Italy, 1998

Su R., “Distributed Diagnosis for Discrete-Event System”, Thesis of PhD, University of Toronto, Canada, 2004.

Wang Y., Yoo T. S., Lafortune S., Decentralized diagnosis of discrete event systems using conditional and unconditional decisions. In Proceedings of the 44th IEEE Conference on Decision and Control, 2005.

Zad S. H., Kwong R. H., Wonham W. M., Fault Diagnosis in Discrete Event Systems: Framework and model reduction, IEEE Transactions On Automatic Control, Vol. 48, N° 7, pp. 1199-1212, 2003.

Documents

ECOLE GDMACS 09 1 Diagnostic décentralisé des Systèmes à Evénements Discrets Moamar SAYED MOUCHAWEH Maître de Conférences HDR Centre de Recherche en STIC