Diagnostica di sistemi dinamici mediante modelli ad eventi...

CASY - DEIS, University of Bologna Politecnico di Milano

1

Diagnostica di sistemi dinamici

mediante modelli ad eventi discreti

Luca Ferrarini Politecnico di Milano, [email protected]

Andrea PaoliUniversity of Bologna, [email protected]


2

Parte 1: Il problema della diagnostica nei DES, modellistica ed approccio a diagnoser;Parte 2: Come rendere un sistema diagnosticabile; Approcci decentralizzati e modulari alla diagnostica;Parte 3: Il problema della safety; Il problema della complessità; il problema della tolleranza ai guasti.

Tratto dai lavori di:Stéphane Lafortune (Univ. of Michigan)Demosthenis Teneketzis (Univ. of Michigan)Kasim Sinnamohideen (retired from Johnson Controls, Inc.)Meera Sampath (Wilson Center for R & T, Xerox Corp.)Raja Sengupta (CE Dept., Univ. of California at Berkeley)Rami Debouk (GM Research Lab.)Tae-Sic Yoo (Argonne National Lab.)Andrea Paoli (Univ. of Bologna)Olivier Contant (Univ. of Michigan) Sahika Genc (Univ. of Michigan)David Thorsley (Univ. of Michigan)


3

Diagnostica in ambito industriale• Un sistema automatico industriale deve garantire:

Performance, Sicurezza, Rispetto di norme ambientali• E’ progettato su sistema nominale: malfunzionamenti

non sono considerati a priori • Deve essere equipaggiato da un sistema automatico

in grado di rilevare mancato rispetto dei vincoli sopra: sistema di diagnostica• Semplice da sviluppare• Semplice da implementare• Semplice da validare• Economico (minimo sforzo e minimo

equipaggiamento)


4

Diagnostica in ambito industriale

• Sistemi industriali:• Perdite funzionali su

componenti (es. blocco di una valvola)

• Perdita di performance e sicurezza

• Numero di sensori limitati

• Componenti difficilmente accessibili

Sistema di condizionamento e ventilazione


5


• Controllo di qualità:• Deterioramento di

componenti (es. deterioramento tamburo)

• Perdita di performance• Numero di sensori

limitati• Processi molto

complessiSistemi di stampa e document processing (Xerox Corp.)


6


• Sistemi di comunicazione:• Perdita di informazioni (es.

guasti su un host)• Perdita di sicurezza• Guasti a volte intermittenti• Processi distribuiti

(processo di diagnosi deve comunicare)

Sistemi di guida automatica (flotte di veicoli autoguidati)


7


IMA C95 - Produzione: 700 blister/minutoDimensioni [cm]: lunghezza 1715, altezza 222, profondità 133

Sistema di elaborazione: 1 PC (gestione interfaccia uomo-macchina), 2 μC (controllo macchina, gestione encoders e I/O veloce), 1 DSP

(gestione assi elettrici e generazione camme elettroniche)I/O: ~ 350 segnali digitali e 25 segnali analogici


8



9



10

Architettura dei sistemi automatici

SISTEMA

SENSORICONTROLLO

INTERFACCIA

DIAGNOSTICA RICONFIGURAZIONI

SISTEMA DI SUPERVISIONE

SUPERVISION


11

Diagnostica in ambito accademico• Rilevazione di dinamiche anomale mediante

l’osservazione delle misure a disposizione.• Non model based: signal processing, reti neurali,

tecniche di intelligenza artificiale (più vicino a telecomunicazionisti e informatici)

• Model based: confronto dell’evoluzione attuale del sistema con un modello• Osservatori• Filtri di Kalman• Ridondanze analitiche e analisi strutturale

N.B. Occorre un modello del malfunzionamento!!!


12

Diagnostica e DES• Sistemi complessi: occorre una modellistica intuitiva

e potente (valvola aperta, valvola chiusa).• Gran parte dei malfunzionamenti sono meglio descritti

ad un livello alto di astrazione (valvola bloccata chiusa).

• L’effetto dei malfunzionamenti è più facilmente rilevabile ad un livello alto di astrazione (apro valvola e non osservo flusso).

• Sviluppo di tecniche di diagnostica model based su modelli ad eventi discreti• Varie metodologie• Un obiettivo: rilevare occorrenza di eventi

(stringhe) non osservabili usando le osservazioni sulle stringhe


13

Diagnostica e DES

SISTEMA

SENSORICONTROLLO

GENERATORE EVENTI

SUPERVISION DIAGNOSTICA DES RICONFIGURAZIONI

SISTEMA DI SUPERVISIONE


14

Richiami DES• Spazio degli stati discreto:

• {on, off, faulty}, {0,1,2,…}• Dinamiche pilotate da eventi:

• {start, stop, fault, repair}• Eventi osservabili (start, stop, repair) e non

osservabili (fault)• Traiettorie sono stringhe di eventi

• start,stop,start,stop,fault…• Modello è un linguaggio• Vari formalismi per descrivere il modello

• Automi, Reti di Petri, algebra di processo


15

Richiami DES: automi• Grafi orientati:

• Nodi -> Stati Archi -> Transizioni Etichette -> eventi• Traiettorie -> cammini ammissibili dallo stato iniziale• Linguaggio -> insieme dei cammini ammissibili

OV

OV

CV

CV V1 V2

VALVOLA

V3

V4

CV, OV

CV, OV

SO1

SC1

S02

SC2


16

Richiami DES: automi

OV

OV

CV

CV V1 V2

VALVOLA

V3

V4

CV, OV

CV, OV

SO1

SC1

S02

SC2

G=(X,E,δ,x0,M,X)X= insieme degli statiE= insieme degli eventiEo= eventi osservabiliEuo= eventi non osservabiliEo∩Euo=∅ Eo∪Euo=Eδ= funzione di transizione (XxE*->X)x0= stato inizialeM= stati marcatiX=stati proibitiL(G)={s∈E* tali che δ(x0,s) è definita}


17

Approccio a diagnoser

• Modello del sistema mediante automa• Guasti modellati con eventi non osservabili• Guasti persistenti!!!• Motore di inferenza (diagnoser) basato su

• dinamica del sistema• stati raggiunti.

• Utilizzo offline e online del diagnoser• Offline -> il sistema è diagnosticabile?• Online -> diagnosi vera e propria


18


Modello dei sensori

Modello DES dei componenti

DiagnoserModello del sistema

Diagnoser

Specifica didiagnostica

Supervisore

Step 1: Costruire il modello ad eventi Step 1: Costruire il modello ad eventi Step 2: Costruire il diagnoser

Analisi: Diagnosi possibile?

Sintesi: Come diagnosticare?


19

Step 1: Costruire il modello

VC

OPEN_VALVE, CLOSE_VALVE

CLOSE_VALVE

STOP_PUMP

SC

C1 C3

C4

C2

POFF PON

VO

SO


OPEN_VALVE

OPEN_VALVE

OPEN_VALVE

CLOSE_VALVE

CLOSE_VALVE

START_PUMP

START_PUMP

START_PUMP

STOP_PUMP

STOP_PUMP

STUCK_OPEN

STUCK_CLOSED

C1

VALVOLA

POMPA

SUPERVISORE


20


<OPEN_VALVE>

4

1 2 3

STUCK_CLOSED

• Composizione parallela:• Combinazione dei modelli che esprime la

concorrenza dei componenti• Eventi comuni tra componenti necessitano di

sincronizzazione• Eventi privati possono avvenire sempre• Spazio degli stati risultante: prodotto cartesiano

(VC,POFF,C1)

(VO,POFF,C2)

(SO,POFF,C1)(SC,POFF,C1)

STUCK_OPEN


21


3

6

SC

SC

<OPEN_VALVE>

<CLOSE_VALVE> <CLOSE_VALVE>

<STOP_PUMP>

9

12

SC

SC

<START_PUMP>

1 2

4 5

S0

S0

<OPEN_VALVE>

<OPEN_VALVE>

<CLOSE_VALVE>

7 8

10 11

S0

S0

<START_PUMP>

<START_PUMP>

<STOP_PUMP>

<STOP_PUMP>


22


3

6

SC

SC

<OPEN_VALVE>


<STOP_PUMP>

9

12

SC

SC

<START_PUMP>

1 2

4 5

S0

S0

<OPEN_VALVE>

<OPEN_VALVE>

<CLOSE_VALVE>

7 8

10 11

S0

S0

<START_PUMP>

<START_PUMP>

<STOP_PUMP>

<STOP_PUMP>

Dinamica

nominale


23


3

6

SC

SC

<OPEN_VALVE>


<STOP_PUMP>

9

12

SC

SC

<START_PUMP>

1 2

4 5

S0

S0

<OPEN_VALVE>

<OPEN_VALVE>

<CLOSE_VALVE>

7 8

10 11

S0

S0

<START_PUMP>

<START_PUMP>

<STOP_PUMP>

<STOP_PUMP> Dinamiche

faulty


24


3

6

SC

SC

<OPEN_VALVE>


<STOP_PUMP>

9

12

SC

SC

<START_PUMP>

1 2

4 5

S0

S0

<OPEN_VALVE>

<OPEN_VALVE>

<CLOSE_VALVE>

7 8

10 11

S0

S0

<START_PUMP>

<START_PUMP>

<STOP_PUMP>

<STOP_PUMP> Dinamiche

faulty

Eventi legali

diventano unsafe


25

Step 1: Costruire il modello• Tabella dei sensori

• Sensore di flusso (F, NF)• Sensore di pressione (P,NP)

STATES SENS OR MAP 1- 6, 10- 12: (POFF, - , - ) NP, NF 7: (PON, VO,C3) PP, F

8: (PON, SO,C3) PP, F 9: (PON, SC,C3) PP, NF


26





Anche se il guasto è sulla valvola il

componente chiave è la pompa


27





Ambiguità


28





Non ambiguo


29


3

6

SC

SC

<OPEN_VALVE, NP,NF>

<CLOSE_VALVE, NP,NF><CLOSE_VALVE, NP,NF>

<STOP_PUMP,NP,NF>

9

12

SC

SC

<START_PUMP,PP,NF>

1 2

4 5

S0

S0

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>

<CLOSE_VALVE, NP,NF>

7 8

10 11

S0

S0

<START_PUMP,PP,F>

<START_PUMP,PP,F>

<STOP_PUMP,NP,NF>

<STOP_PUMP,NP,NF>

< F -> NF >


30

Step 1: Costruire il modello• Eventi osservabili

• Comandi dal supervisore e lettura dei sensori• Cambiamento di stato dei sensori

• Eventi non osservabili• Cambiamenti nel sistema non registrati dai sensori• Guasti

• Obiettivo della metodologia• Identificare nel sistema i sintomi dei guasti• Rilevare tali sintomi per diagnosticare l’occorrenza

degli eventi “guasto”


31


3

6

SC

SC

<OPEN_VALVE, NP,NF>


<STOP_PUMP,NP,NF>

9

12

SC

SC

<START_PUMP,PP,NF>

1 2

4 5

S0

S0

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>


7 8

10 11

S0

S0

<START_PUMP,PP,F>

<START_PUMP,PP,F>

<STOP_PUMP,NP,NF>

<STOP_PUMP,NP,NF>

< F -> NF >

sintomo


32


3

6

SC

SC

<OPEN_VALVE, NP,NF>


<STOP_PUMP,NP,NF>

9

12

SC

SC

<START_PUMP,PP,NF>

1 2

4 5

S0

S0

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>


7 8

10 11

S0

S0

<START_PUMP,PP,F>

<START_PUMP,PP,F>

<STOP_PUMP,NP,NF>

<STOP_PUMP,NP,NF>

< F -> NF >

Nessun sintomo


33


Modello dei sensori



Diagnoser


Supervisore

Step 1: Costruire il modello ad eventi Step 2: Costruire il diagnoser


Sintesi: Come diagnosticare?


34

Step 2: Costruire il diagnoser• Problema: rilevare l’evento “f” (non osservabile)

osservando solo gli eventi “a” e “b”.

1

2

3

4 5

a abb

a a

f

uo


35

Step 2: Costruire il diagnoser

• Finchè osservo “abab…ab” non so se sono nella zona P1 (f non è avvenuto) o P2 (f è avvenuto)

1

2

3

4 5

a abb

a a

f

uo

P1 P2


36


• Appena osservo “aa” so che sono nella zona P3 (f èavvenuto)

• “aa” è sintomo di “f”

1

2

3

4 5

a abb

a a

f

uo

P3


37


• Problema: “aa” potrebbe non essere mai eseguito (non diagnostico mai “f”)…

• … esistono due stringhe arbitrariamente lunghe (s1, s2), con stessa osservazione, una contiene “f”, l’altra no.

1

2

3

4 5

a abb

a a

f

uo

s1s2


38


• Obiettivo: costruire un DES che esegua in automatico questo tipo di inferenza -> DIAGNOSER

• DIAGNOSER = osservatore diagnostico

1

2

3

4 5

a abb

a a

f

uo


39

Step 2.1: Osservare lo stato• Presenza di eventi non osservabili: alcune transizioni

non sono visibili dall’esterno• Transizioni ε• L’automa è detto non-deterministico

• Primo problema è quello di stimare lo stato attuale del sistema (Transizioni ε creano incertezza)

• Esiste una procedura per costruire, partendo da un automa non deterministico, un automa deterministico “equivalente”

• Tale automa è un osservatore:• Le transizioni sono dovute solo ad eventi

osservabili• Lo stato contiene una stima dello stato originale


40

Step 2.1: Osservare lo stato• Per costruire l’osservatore:

• Costruisco la funzione di transizione partendo da quella del sistema originale restringendola ai soli eventi osservabili

• Ad ogni nuovo step associo allo stato raggiunto l’insieme raggiungibile non osservabile…

• … stati raggiungibili mediante stringhe non osservabili

• Insieme degli stati dell’osservatore Xo⊆2X

• Caso peggiore #Xo = #2X


41

Step 2.1: Osservare lo stato0 1 2

9 53 4

6 7 8

a1

a1

a1

b1

b1

b1

b2b2b2

a2a2a2

Evento a2 non è osservabile !!!!

{1,4,9} {2,5}

{6} {7} {8}

{0,3}

Finchè non osservo un evento il sistema

è in 0 o in 3

a1

a1

b1

b1

b2 b2 b2

Stima dello stato.

3 è nell’insieme raggiungibile non osservabile di 0.


42

Step 2.1: Osservare lo stato0 1 2

9 53 4

6 7 8

a1

a1

a1

b1

b1

b1

b2b2b2

a2a2a2

{1,4,9} {2,5}

{6} {7} {8}

{0,3} a1

a1

b1

b1

b2 b2 b2

Natural Projection


43

Proiezione naturaleProiezione

Proiezione inversa


44

Proiezione naturale

Stringhe in L che assomigliano a “s”

(hanno la stessa osservazione)


45

Step 2.2: Rilevare il guasto• Idea: arricchire lo stato dell’osservatore con

informazioni sull’occorrenza del guasto (evento di interesse “f”)

• Man mano che la procedura di costruzione dell’osservatore continua l’incertezza su stato e occorrenza del guasto tende a diminuire

• Si affiancano ai nomi degli stati delle label:• “N” -> il guasto non è avvenuto• “Y” -> il guasto è avvenuto

• Quando costruisco l’insieme raggiungibile non osservabile aggiorno le label: N->Y solo se per raggiungere lo stato la stringa non osservabile contiene il guasto


46

Step 2.2: Rilevare il guasto• Dato che il guasto è considerato persistente la label Y

si propaga inalterata

X1-N X2-N

X1-Y X2-Y

No failures

No failures

X1-Nf

X2-Y


47

Step 2.2: Rilevare il guasto

1

2

3

4 5

a abb

a a

f

uo

aab b

a

{1N,3Y}

{2N,4Y,5Y}

{4Y,5Y}

{3Y}

a


48


1

2

3

4 5

a abb

a a

f

uo

Stati incerti Stati certiaab b

a

{1N,3Y}

{2N,4Y,5Y}

{4Y,5Y}

{3Y}

a


49


1

2

3

4 5

a abb

a a

f

uo

Ciclo di stati incerti: problema!!!

aab b

a

{1N,3Y}

{2N,4Y,5Y}

{4Y,5Y}

{3Y}

a


50


1

2

3

4 5

a abb

a a

f

uo

Ciclo di stati incerti: se a tale ciclo corrispondono due cicli (s1 e s2) connessi nell’automa originale di cui uno contiene il guasto e l’altro no il ciclo si dice indeterminato e il guasto non èdiagnosticabile

s1s2

aab b

a

{1N,3Y}

{2N,4Y,5Y}

{4Y,5Y}

{3Y}

a


51

Step 2.2: Rilevare il guasto1

2

a b

3

4

b

6

8

c

d

5

7

9

c

f

a

10

de

11

12

ed

d {2N,5N,4N}

{1N,3N}a

{6N,7N,9Y} {11N}

c d

{8N,10Y}

{6N,9Y}

{12N}

e

d

d

e

d

“b” e “f” non osservabili !!Voglio rilevare “f” !!

e


52

Step 2.2: Rilevare il guasto1

2

a b

3

4

b

6

8

c

d

5

7

9

c

f

a

10

de

11

12

ed

d {2N,5N,4N}

{1N,3N}a

{6N,7N,9Y} {11N}

c d

{8N,10Y}

{6N,9Y}

{12N}

e

d

d

e

d

Ciclo di stati incerti!!

“b” e “f” non osservabili !!Voglio rilevare “f” !!


53

Ciclo di stati incerti!!

1

2

a b

3

4

b

6

8

c

de

5

7

9

c

f

a

10

de

11

12

ed

d {2N,5N,4N}

{1N,3N}a

{6N,7N,9Y} {11N}

c d

{8N,10Y}

{6N,9Y}

{12N}

e

d

d

e

d

1 No f 6 6 8d e

d

1 f 9 10 9d

d

e

Cicli connessi nella macchina originale:f non è diagnosticabile !!!


54

Evento da rilevare: f !!!!

1

2a

f 5b

3 4

6

7 11 12

8 9 10a

b

bf

d

d

g

g

t

t

{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}

{6Y}

a b g

td

tE’ un ciclo indeterminato?

g

Ciclo N

No !! Il ciclo Y non è connesso!!

Rilevo “f” entrando nello stato 6Y:

Sintomo “t”


55

Step 2.3: Rilevare più guasti• Partizionare gli eventi da rilevare in più classi: non

siamo interessati a distunguere tra eventi nella stessa classe.

b fa

fc

fb

uo c

d

• Se F1 = {fa}, F2 = {fb}, F3 = {fc}, non è diagnosticabile

• Se F1 = {fa, fb}, F2 = {fc}, è diagnosticabile


56

Step 2.3: Rilevare più guasti• Costruiamo il diagnoser come sopra ma utilizzando la

label “N” per indicare che nessun evento guasto èoccorso, la label “Fi” per indicare che un evento dell’i-esima classe è occorso.

X1- N

X1- F1

σf1 σf2

σf3

X1- F1,F2

X1- F1,F3


57

3

6

SC

SC

<OPEN_VALVE, NP,NF>



<STOP_PUMP,NP,NF>

9

12

SC

SC

<START_PUMP,PP,NF>

1 2

4 5

S0

S0

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>


7 8

10 11

S0

S0

<START_PUMP,PP,F>

<START_PUMP,PP,F>

<STOP_PUMP,NP,NF>

<STOP_PUMP,NP,NF>

< F -> NF >


58

1 N

4 N 5 F2 6 F1

7 N 8 F2

10 N 11 F2

1 N 2 F2 3 F1

9 F1

12 F1

3 F1

6 F1

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>

<CLOSE_VALVE, NP,NF> <CLOSE_VALVE, NP,NF>

<START_PUMP,PP,F>

<START_PUMP,PP,NF>

<START_PUMP,PP,NF>

<STOP_PUMP,NP,NF> <STOP_PUMP,NP,NF>

< F -> NF >

F1: Valvola SC

F2: Valvola SO


59

1 N

4 N 5 F2 6 F1

7 N 8 F2

10 N 11 F2

1 N 2 F2 3 F1

9 F1

12 F1

3 F1

6 F1

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>

<CLOSE_VALVE, NP,NF> <CLOSE_VALVE, NP,NF>

<START_PUMP,PP,F>

<START_PUMP,PP,NF>

<START_PUMP,PP,NF>

<STOP_PUMP,NP,NF> <STOP_PUMP,NP,NF>

< F -> NF >

F1: Valvola SC

F2: Valvola SO

Ciclo indeterminato


60

Formalizziamo i risultati• Consideriamo un linguaggio vivo e con osservazioni

regolari. • Dato un set di eventi non osservabili da rilevare e una

partizione su di essi, il linguaggio è diagnosticabile se per ogni “guasto” fi:

• per ogni stringa “s” che termina con fi…• … data una continuazione “t” suffic. lunga..• … ogni stringa che assomiglia a “st” contiene un

evento nella stessa partizione di fi

s

fi

t


61

Formalizziamo i risultati• Consideriamo un linguaggio L vivo e con osservazioni

regolari. L è diagnosticabile se

• Si dimostra che condizione necessaria e sufficiente affinchè L sia diagnosticabile è che il diagnoser di un qualunque generatore di L non contenga cicli indeterminati

• Tale test è di complessità polinomiale nella cardinalitàdell’insieme di stato del diagnoser…

• … che può essere molto grande!


62

Step 3: Utilizzo on-line• Se il linguaggio è diagnosticabile, il diagnoser è in

grado di rilevare in un numero finito di passi l’occorrenza di ogni tipo di guasti entrando uno stato certo.

• Per l’implementazione due possibili strade• Costruzione off-line del diagnoser e

memorizzazione delle sue transizioni (molta memoria, poco calcolo)

• Costruzione del diagnoser “on-the-fly” (poca memoria, molto calcolo)


63


Modello dei sensori



Diagnoser


Supervisore

Step 1: Costruire il modello ad eventi Step 2: Costruire il diagnoser


Sintesi: Come rendere

diagnosticabile?

NO


64

Come rendere diagnosticabile?• Approccio passivo: aggiungere sensori al sistema…• …ovvero aggiungere eventi osservabili• Approccio iterativo finché il diagnoser non ha più cicli

indeterminati!!!• Problema: ottimizzare la scelta dell’equipaggiamento

sensoriale• Set di sensori da cui scegliere, ognuno con un costo.

• Hp: sistema diagnosticabile usando tutti i sensori.• Problema NP completo!!!• Esistono soluzioni sub-ottime


65

Come rendere diagnosticabile?• Approccio attivo: modificare la strategia di

supervisione per rendere il sistma diagnosticabile• I cicli indeterminati possono nascere a causa delle

azioni imposte dal supervisore• Idea: introdurre i vincoli di diagnosticabilità nel

progetto del supervisore.


66

Il supervisore influenza la diagnosi

VC


CLOSE_VALVE

STOP_PUMP

SC

C1 C3

C4

C2

POFF PON

VO

SO


OPEN_VALVE

OPEN_VALVE

OPEN_VALVE

CLOSE_VALVE

CLOSE_VALVE

START_PUMP

START_PUMP

START_PUMP

STOP_PUMP

STOP_PUMP

STUCK_OPEN

STUCK_CLOSED

C1

VALVOLA

POMPA

NUOVO SUPERVISORE


67

Il supervisore influenza la diagnosi

No. State Sensor Reading

1 ( POFF, VC, C1 ) NP, NF2 ( POFF, SO, C1 ) NP, NF3 ( POFF, SC, C1 ) NP, NF4 ( PON, VC, C2 ) PP, NF5 ( PON, SO, C2 ) PP, F6 ( PON, SC, C2 ) PP, NF7 ( PON, VO, C3 ) PP, F8 ( PON, SO, C3 ) PP, F9 ( PON, SC, C3 ) PP, NF10 ( PON, VC, C4 ) PP, NF11 ( PON, SO, C4 ) PP, F12 ( PON, SC, C4 ) PP, NF


68

3

6

SC1

SC1

<CLOSE_VALVE, PP,NF>

9

12

SC2

SC2

1 2

4 5

S01

S01

<STOP_PUMP, NP, NF>

7 8

10 11

S02

S02

<START_PUMP,PP,NF>

< F -> NF >

< NF -> F >

< NF -> F >

<START_PUMP,PP, F> <START_PUMP,PP,NF>

<OPEN_VALVE, PP, F>

<OPEN_VALVE, PP, F> <OPEN_VALVE, PP, NF>

<CLOSE_VALVE, PP,NF>

<CLOSE_VALVE, PP, F>

<STOP_PUMP, NP, NF>

<STOP_PUMP, NP, NF>


69

1 N

4 N 6 F1

7 N

10 N

1 N 3 F1

5 F2

8 F2

11 F2

2 F2

9 F1

12 F1

3 F1

6 F1

<START_PUMP, PP, NF><START_PUMP, PP, F>

< NF -> F >

< NF -> F >

<OPEN_VALVE, PP, F>


<STOP_PUMP, NP, NF>

<START_PUMP, PP, F>

<OPEN_VALVE, PP, F>


<STOP_PUMP, NP, NF>

<START_PUMP, PP, NF>


<STOP_PUMP, NP, NF>

<START_PUMP, PP, NF>

<OPEN_VALVE, PP, NF>

<OPEN_VALVE, PP, NF>

<START_PUMP, PP, F>

< F -> NF >

F1 : SC

F2 : SO

DIAGNOSTICABILE!

Nuovo diagnoser


70

Diagnostica attiva• Integrare risultati della teoria del controllo supervisivo

con il problema della diagnostica.• Si parte da un linguaggio di specifica ammissibile K• Si desidera limitare il comportamento del sistema

all’interno di K mediante un supervisore DES…• …rendendo diagnostcabile il sistema ottenuto• Risultato: Ka massimo linguaggio controllabile,

osservabile e diagnosticabile contenuto in K• Si giunge a Ka eliminando stringhe da K in maniera

iterativa• Caso peggiore: insieme vuoto!!!• Il supervisore risulta essere anche diagnoser per il

sistema.


71

Come rendere diagnosticabile?• Utilizzare elaborazioni sulle informazioni di basso

livello per arricchire il set di eventi osservabili:sensori virtuali

DIGITAL DATA STREAM

EVENT GENERATOR

ANALOG DATA STREAM

FEATURE EXTRACTION

DISCRIMINANT ANALYSIS

DIAGNOSER LOCAL UI REMOTE UI

Cluster 2

Event 1: Feed_Motor_OnEvent 5: Stack Ht. Counter Low

Broken Feed Roll Cartridge

FAILURE

Failure 2


72

Architetture decentralizzate• Per sistemi distribuiti: diagnoser locali e

coordinamento centralizzato• Esempio: sistema di trasmissione con tre nodi…• …ogni nodo trasmette periodicamente dati agli altri

nodi• Obiettivo: rilevare guasti ai trasmettitori/ricevitori dei

nodi• Il ricevitore del nodo 2 è guasto

Nodo 3

Nodo 1 Nodo 2


73

Architetture decentralizzate• Modello di comunicazione nodo 1-3 al nodo 1

m_transmitted

ack_transmitted

time_out

m_received

ack3_1

send1_3

ack_received

T1_faulty R3_faulty

R1_faulty T3_faulty

Obs. by node 1

Obs. by node 3

Faults


74

Architetture decentralizzate

• Se i nodi 1 e 3 coordinano le loro informazioni, il sistema è certo che il ricevitore del nodo 2 è guasto

Source Destination Ack. Rec. by Source1 2 No1 3 Yes3 2 No2 3 No

Nodo 1 Nodo 2 Nodo 3 Globale

Sospetto T2 T2, T3 T3 -

guasto R2 R2, R3 R2 -

Normal T1, T3 - T1, T2 T1, T2, T3

Operation R1, R3 - R3 R1, R3

Faulty - - - R2

Scenario

Conoscenza

∪

∩


75

Architetture decentralizzate

SITE 2SITE 1

INTERFACE 1

DIAGNOSTICS

SUPERVISORY CONTROLLER 1

INTERFACE 2

DIAGNOSTICS

SUPERVISORY CONTROLLER 2

COORDINATOR FAILURE RECOVERY

Local Observations

Communications


76

Architetture decentralizzate• Hp1: sistema diagnosticabile se centralizzato• Hp2: sistema di comunicazione affidabile• Coordinatore è l’elemento chiave!!• Protocollo 1: i diagnoser locali si comunicano solo i

guasti rilevati (stati certi), il protocollo è banale• Protocollo 2: i diagnoser comunicano lo stato attuale,

il protocollo esegue intersezioni


77

Strumenti software• DesUMA: scaricabile da www.eecs.umich.edu/umdes


78

Diagnosticabilità con vincoli di safety• Simple Pump-Valve-Controller Example:

• Don’t ``START_PUMP’’ if valve is ``STUCK_CLOSED’’


79

Diagnosticabilità con vincoli di safety• Se il sistema è diagnosticabile, il diagnoser entra uno

stato certo in un numero limitato di “passi” dopo il guasto.

• In DES “passi”= eventi!!!• Abbiamo visto che in seguito ad un guasto azioni

legali potrebbero diventare illegali• Diagnostica con vincoli di safety: diagnosticare il

guasto prima che tali azioni illegali vengano eseguite• Esempio:

start_pump quando la valvola è chiusa!!!

STOP_PUMP

C1 C3

C4

C2OPEN_VALVE

CLOSE_VALVE

START_PUMP

C1

SUPERVISORE


80

3

6

SC

SC

<OPEN_VALVE, NP,NF>


<STOP_PUMP,NP,NF>

9

12

SC

SC

<START_PUMP,PP,NF>

1 2

4 5

S0

S0

<OPEN_VALVE, NP,NF>

<OPEN_VALVE, NP,NF>


7 8

10 11

S0

S0

<START_PUMP,PP,F>

<START_PUMP,PP,F>

<STOP_PUMP,NP,NF>

<STOP_PUMP,NP,NF>

< F -> NF >

Eventi legali

diventano unsafe


81

La nozione di “safe-diagnosability”

s2 f t2 : safe

s1 f t1 : unsafe!

s1

s2

ff

t1

t2

Detection Unsafe

Ingresso stato certoLinguaggio del sistema

diagnosticabile per Hp

Azioni illegali se

eseguite dopo guasto


82

La nozione di “safe-diagnosability”• Si definisce per ogni tipo di guasto l’insieme delle

continuazioni illegali • Safe-diagnosbility: sistema disgnosticabile tale che,

dopo un guasto, la continuazione più breve che assicura la rilevazione del guasto non contiene alcuna azione illegale

• Per testare: il modello (automa) viene raffinato mediante operazioni di marking e splitting degli stati per evidenziare stati raggiungibili da stringhe unsafe…

• …su questo modello si costruisce il diagnoser…• …sul diagnoser sono definite un insieme di condizioni

necessarie e sufficienti.


83

La nozione di “safe-diagnosability”

f

f

f

Safe diagnoser

CertoIncerto

Zona Illegale

| Certo ->

t12

P(t12)

t2 P(t2)

t3 P(t3)

t11P(t11)

Modello


84

Esempio di “safe-diagnosability”


85

Esempio di “safe-diagnosability”

Sensore di flusso: NO Sensore di pressione: SI

Unsafe Unsafe

Take action


86

“Safe-diagnosability” e riconfigurazione• Sistema safe diagnosable: dopo un guasto esiste

sempre un sintomo osservabile prima di un’azione illegale.

• IDEA: usare il sintomo per forzare una riconfigurazione

• Se dopo tale sintomo e prima dell’azione illegale esiste un evento controllabile il sistema è detto riconfigurabile

Usare σ per disabilitare nri

e abilitare ri impedendo v


87

Supervisory Control of DES with faults

• Start from uncontrolled system• Restrict the uncontrolled language to

meet nominal specifications • Supervisor:• Potential fault f is considered at this

point• New model • Actual controlled behavior

Gnom

K nom

Gsupnom :=Gnom ||Snom L Gsup

nom( )⊆ K nom

Gn+ f

Gsupn+ f :=Gn+ f ||Snom L Gsup

n+ f( )⊇ K nom


88

Fault Tolerant Specifications1. Diagnose the

occurrence of f beforeexecuting string in the forbidden post-language

2. Force the system to stop its evolution before executing string in the forbidden post-language

3. Steer the faulty system to meet post-faults specifications

Kf

Kf

K deg


89

FT Specification 1: safe-diagnosability• A language is safe-diagnosable if it is diagnosable

and after a fault, the shortest continuation that assures the detection does not contain any illegal substring in

Kf

| Detection ->

Safe diagnoser

Model


90

FT Specification 2: safe controllability• A language is safe-controllable if for any string that contains a

fault and a forbidden string, there exists:– An observable event that assure the detection before the

forbidden sequence (safe diagnosability);– A controllable event z after the observable event and before

the forbidden sequence.

i-th post-detection model

Testing:

Compute

verify that none substring

is forbidden

{ ε }↓C

Gdeg,i∀i


91

FT Specification 3: active FTC• Language is active fault tolerant if for all i

exists a sublanguage of the post-fault specification which is controllable and observable with respect to

• Testing active fault tolerance possibilities:

– Test if

– Compute

• If is active fault tolerant, there exists a set of post-fault supervisor

L Gsupn+ f( )

K deg,i

Gdeg,i

ε{}↓C

Gdeg,i⊆ K deg,i

K deg,i{ }↑CN

Gdeg,i

L Gsupn+ f( )

Sdeg,i


92

FT supervision architecture


93

Problemi dell’approccio a diagnoser• Modellistica fisica del sistema (composizione

parallela): modello con un numero di stati elevato (#X)• Diagnoser: osservatore diagnostico, numero di stati

molto elevato (>#2X) • Per ovviare al problema:

• Approcci distribuiti• Approcci modulari per sfruttare la simmetria del

sistema• Applicazione a nuove classi di modelli

• Reti di Petri• Statecharts


94

Statecharts• Sono automi gerarchici:

• Clustering degli stati• Gerarchia verticale• Ortogonalità per non espandere parti in

concorrenza

A B C

D E F

1

2

G2.1

a1 b1

c1

a2 b2

c2

e1


95

Statecharts• Operazione di “flat”

1

A,D B,D C,Da1 b1

c1

A,E B,E C,Ea1b1

c1

A,F B,F C,Fa1 b1

c1

a2

b2

c2

a2 a2

b2b2

c2 c2

e1

e2

Flat automaton


96

Statecharts e diagnostica• IDEA: “proiettare” lo statechart ad un livello k

approssimandolo con un automa semplificato e testare la diagnosticabilità sul relativo diagnoser (LK-diagnosability)

• Attenzione è una proiezione che allarga il linguaggio, i risultati sono solo sufficienti

A B

C D

1

2

G2.1

G2.2

a1

b1

a2

b2

e1

e2

3e2

e1

GH

1

2

3e1

e1

e2

e2 GL1H


97

Statecharts e diagnostica

Statechart

wait op stop

disc nor F

off1

on

Gon.1

Gon.2

exec

err

off2

f-off

done

con

dis

f2 dis

con

on

offoff

on

f1

on


98

Statecharts e diagnosticaoff1 f-off

on

f1

on

onoff

off2off

on

GL1H

[(off1,N);(off1,N)]

[(off1,N);(on,N)]

[(off1,N);(foff,F1)]

[(on,N);(off1,N)]

[(on,N);(off2,N)]

[(off1,N);(on,N)]

[(off1,N);(foff,F1)]

[(off2,N);(on,N)]

[(foff,F1);(foff,F1)]

on

on

on on

on

off

off

Nessun ciclo indeterminato

f1 è L1-diagnosable!!!

La flat machine ha 16 states

# Flat diagnoser >100 states


99

Statecharts e diagnosticaProiezione a livello 1 con lift di informazioni

wait op

disc nor F

off1

on

Gon.1

Gon.2

exec

err

off2

con

dis

f2 dis

con

on

offoff

off1

on

on

onoff

off2off

GH

GL1H

on

off1

on

on

onoff

off2offGL1

H (f2) onIf2


100

Statecharts e diagnosticaProiezione a livello 1 con lift di informazioni

[(off1,N);(off1,N)]

[(on,N);(off1,N)]

[(on,N);(off2,F2)]

[(off2,F2);(off2,F2)]

onon

[(off1,N);(on,N)][(off1,N);(on,N)]

[(off2,F2);(off2,F2)]

off1on

on

onoff

off2off

GL1H (f2)

onIf2

off

offononNessun ciclo indeterminato:

f2 è L1-diagnosable!!!


101

Statecharts e diagnosticaSe non si riesce a provare la diagnosticabilità (cicli indeterminati nel diagnoser), si cerca di fare l’”unfolding” di tali cicli liftando informazioni dai livelli inferiori

wait op

disc nor

off1

on

Gon.1

Gon.2

exec

err

off2

con

dis con

off

GH

on

stop alrtrg

fofff1on

offon

off1

on off2

fofff1

on on

on

off

off

GL1H


102


off1

on off2

fofff1

on on

on

off

off

GL1H

[(off1,N);(off1,N)]

[(off1,N);(on,N)]

[(off1,N);(on,F1)]

[(on,N);(off1,N)] ; [(on,N);(off2,N)]

[(on,F1);(off1,F1)] ; [(on,F1);(off1,F1)]

[(off1,N);(on,N)] ; [(off1,N);(on,F1)]

[(off1,F1);(on,F1)] ; [(off2,N);(on,N)]

[(off2,N);(on,F1)] ; [(off2,F1);(on,F1)]

on

on

off

offIndeterminate cycle!!


103


[(off1,N);(on,N)]

[(off1,N);(on,F1)]

on

off

[(off1,N);(wait,N)||disc]

[(off1,N);(stop,F1)||err]

on

trgexec

[(wait,N);(op,N)]||disc [(stop,F1);(alr,F1)]||err

off off

Da: Usando la componente Gon.1

A:


104

Statecharts e diagnostica[(off1,N);(off1,N)]

on[(off1,N);(wait,N)||disc]

[(off1,N);(stop,F1)||err]

trgexec

[(wait,N);(op,N)]||disc [(stop,F1);(alr,F1)]||err

off off

[(op,N)||disc;(off1,N)]

on

[(alr,F1)||err;(off2,F1)]

off

[(off2,F1);(stop,F1)||err]

trg

No indeterminate cycle:

f1 is diagnosable!!!


105

Conclusioni• Introduzione al problema della diagnostica• Un possibile approccio in ambito DES: il diagnoser• Diagnosability: definizioni e test• Rendere un sistema diagnosable• Diagnosability e safety• Architetture decentralizzate• Statecharts e diagnostica• Controllo tollerante ai guasti• Possibili in questo ambito lavori di tesi in

collaborazione PoliMi e UniBo• Teorici• Applicativi


106

Biblografia Essenziale[Sampath et al., TCST 1996] “Failure Diagnosis Using Discrete Event Models” by M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, IEEE Trans. on Control Systems Technology, Vol. 4, No. 2, March, 1996 pp. 105-124.

[Yoo et al., 2002] “Polynomial-time Verification of Diagnosability of Partially-observed Discrete-Event Systems” by T. Yoo and S. Lafortune, IEEE Trans. on Automatic Control, Vol. 47, No. 9, September, 2002 pp. 1491-1495.

[Sampath et al., TAC 1995] “Diagnosability of Discrete Event Systems” by M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, and D. Teneketzis, IEEE Trans. on Automatic Control, Vol. 40, No. 9, September, 1995 pp. 1555-1575.

[Paoli and Lafortune, Automatica 2005] “Safe diagnosability for fault-tolerant supervision of disecrete-events systems” by A. Paoli and S. Lafortune, Automatica, Vol. 41, No. 8, August, 2005.

[Paoli and Lafortune, JDEDS 2008] “Diagnosability analysis of a class of hierarchical state machines” by A. Paoli and S. Lafortune, Journal on Discrete Event DynamicSystems, 2008 (on line first).


107

Biblografia Estesa[Sampath et al., TCST 1996] “Failure Diagnosis Using Discrete Event Models” by M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, IEEE Trans. on Control Systems Technology, Vol. 4, No. 2, March, 1996 pp. 105-124.[Yoo et al., 2002] “Polynomial-time Verification of Diagnosability of Partially-observed Discrete-Event Systems” by T. Yoo and S. Lafortune, IEEE Trans. on Automatic Control, Vol. 47, No. 9, September, 2002 pp. 1491-1495.[Sampath et al., TAC 1995] “Diagnosability of Discrete Event Systems” by M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, and D. Teneketzis, IEEE Trans. on Automatic Control, Vol. 40, No. 9, September, 1995 pp. 1555-1575.[Paoli and Lafortune, Automatica 2005] “Safe diagnosability for fault-tolerant supervision of disecrete-events systems” by A. Paoli and S. Lafortune, Automatica, Vol. 41, No. 8, August, 2005.[Yoo et al., TAC 2002] “NP-Completeness of Sensor Selection Problems Arising In Partially-observed Discrete-Event Systems”, by T. Yoo and S. Lafortune, IEEE Trans. on Automatic Control, Vol. 47, No. 9, September, 2002 pp. 1495-149.[Debouk et al., DEDSJ 2000] ”Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems”, by R. Debouk, S. Lafortune, and D. Teneketzis, Discrete Event Dynamic Systems: Theory and Applications, Vol. 10, No. 1, January, 2002 pp. 33-86.[Sampath et al., TAC 98] “Active Diagnosis of Discrete Event Systems” by M. Sampath, S. Lafortune, and D. Teneketzis, IEEE Trans. on Automatic Control, Vol. 43, No. 7, July, 1998 pp. 908-929[Sampath et al., SafeProcess 2000] “Combining Qualitative & Quantitative Reasoning - A Hybrid Approach to Failure Diagnosis of Industrial Systems” by M. Sampath, A. Godambe, E. Jackson and E. Mallow, IFAC Safeprocess 2000, Budapest, 2000.[Genc et al., ATPN 2003] “Distributed Diagnosis Of Discrete-Event Systems Using Petri Nets” by S. Genc and S. Lafortune, ATPN 2003, The Netherlands, 2003.[Paoli and Lafortune, SafeProcess 2005] “On the diagnosability of a class of hierarchical state machines” by A. Paoli and S. Lafortune, IFAC SafeProcess 2006, Beijing, China, 2006.[Paoli and Lafortune, IFAC 2008] “Fault Tolerant Control of Discrete Event Systems” by A. Paoli and S. Lafortune, IFAC World Congress 2008, Seul, South Korea, 2008.

Diagnostica di sistemi dinamici mediante modelli ad eventi...

Documents

Transcript of Diagnostica di sistemi dinamici mediante modelli ad eventi...