SINTESI E USO DI MODELLI ASTRATTI NELLA DIAGNOSI MODEL-BASED

SINTESI E USO DI MODELLI ASTRATTI NELLA DIAGNOSI MODEL-BASED

Gianluca Torta Dipartimento di Informatica

Università di Torino

Outline

¾ Model Based Diagnosis

¾ astrazione di modelli

¾ astrazione nella MBD o uso dei modelli astratti

o proprietà dei modelli astratti

¾ astrazione automatica

¾ problemi aperti

Model Based Diagnosis (I)

Nella MBD il modello del sistema sotto diagnosi (System Description) è rappresentato da una tripla:

SD = <A, P = <I,S,O>, ∆>

dove:

• A è un set di variabili discrete dette assumables; ogni variabile C ∈ A rappresenta un componente del sistema e DOM(C) elenca i behavioral mode del componente (OK e uno o più modi di fault)

• P è il set di variabili discrete dette non-assumables e si partiziona in I (input), S (stati interni) e O (output)

•∆ è la Domain Theory ovvero il mapping da I ∪ A ad S ∪ O che rappresenta il behavior (formule logiche, relazioni, Reti Bayesiane ecc.)

Model Based Diagnosis (II)

Un problema diagnostico è dato da:

DP = <SD, I, OBS>

dove:

• SD è il modello del sistema

• I è una istanziazione dell’insieme di variabili I

• OBS è una istanziazione dell’insieme di variabili OBS ⊆ S ∪ O dette osservabili

Una soluzione consistente di un problema diagnostico (diagnosi consistency based) è una istanziazione D delle variabili A tale che:

Model Based Diagnosis (III)

Esempio:

V out

in

cmd

A = {V}

P = {in, cmd, out}

DOM(V) = {OK, SO, SC}

DOM(in) = DOM(out) = {f, nf}

DOM(cmd) = {open, close}

in(f) & cmd(open) & V(OK) ⇒ out(f) in(f) & cmd(open) & V(SO) ⇒ out(f) in(f) & cmd(open) & V(SC) ⇒ out(nf) in(f) & cmd(close) & V(OK) ⇒ out(nf) in(f) & cmd(close) & V(SO) ⇒ out(f) in(f) & cmd(close) & V(SO) ⇒ out(nf) in(nf) & cmd(*) & V(*) ⇒ out(nf)

∆ =

Definizione di Astrazione

La astrazione di un modello SDD = <A, P, ∆> è costituita da due elementi:

• un modello (astratto) SDA = <A’, P’, ∆’>

• un mapping AM che mappa A in A’, P in P’ e ∆ in ∆’

Tipi di Astrazione (I)

Astrazione strutturale:

Livello 0 Livello 1 Livello 2

Tipi di Astrazione (II)

Astrazione funzionale/causale:

Livello 0 Livello 1

Tipi di Astrazione (III)

Astrazione is-a:

Astrazione di Valori

Per ogni variabile x in SDD c’è una variabile X in SDA

I valori di DOM(x) sono mappati molti-a-uno sui valori di DOM(X)

Esempio

DOM(VALVE-x) = {OK, LEAK, STUCK}

DOM(VALVE-X) = {OK, STUCK}

con:

AM(VALVE-x(OK)) = AM(VALVE-x(LEAK)) = VALVE-X(OK) AM(VALVE-x(STUCK)) = VALVE-X(STUCK)

Astrazione di Variabili

Le variabili x1…xk in SDD sono mappate sulla variabile X in SDA I valori di DOM(x1) × … × DOM(xk) sono mappati molti-a-uno su valori di DOM(X)

Esempio

AM(PIPE-x1) = AM(PIPE-x2) = PIPE-X con:

AM(PIPE-x1(OK), PIPE-x2(OK)) = PIPE-X(OK)

AM(PIPE-x1(OK), PIPE-x2(BROKEN)) = PIPE-X(BROKEN) AM(PIPE-x1(BROKEN), PIPE-x2(OK)) = PIPE-X(BROKEN) AM(PIPE-x1(BROKEN), PIPE-x2(BROKEN)) = PIPE-X(BROKEN)

Astrazione di Modelli e MBD

1. astrazione da modello quantitativo a modello qualitativo (discretizzazione, mapping): dato un modello numerico del sistema sintetizzare un modello qualitativo corrispondente che permetta di usare la MBD (Console & al DX 03, Struss DX 03)

2. astrazione da modello qualitativo a modello qualitativo

Astrazione Qualitativo-Qualitativo

Vantaggi:

1. la complessità del reasoning diagnostico dipende in modo esponenziale dalla dimensione del sistema

2. il numero massimo di diagnosi dipende in modo esponenziale dalla dimensione del sistema

3. un numero troppo elevato di diagnosi dettagliate alternative puo’ rendere difficile per un supervisore umano e/o

automatico la loro interpretazione (e il conseguente decision- making in base ad esse)

Modelli Astratti e Processo Diagnostico (I)

MD MA’

MA’’

MA’’’

modelli separati

MD MA’

MA’’

MA’’’

modello unico +

+

+

Modelli Astratti e Processo Diagnostico (II)

Proprietà della Astrazione (I)

CORRETTEZZA

se una istanziazione DD non è una diagnosi a livello dettagliato allora DA = AM(DD) non è una diagnosi a livello astratto

COMPLETEZZA

se una istanziazione DD è una diagnosi a livello dettagliato allora DA = AM(DD) è una diagnosi a livello astratto ID = CORRETTEZZA + COMPLETEZZA

Proprietà della Astrazione (II)

corretta completa

Proprietà della Astrazione (III)

ID

Astrazione e Diagnosticabilità (I)

indiscriminabilità (Travè-Massuyès et al. IJCAI 01)

Due fault C1(F1) e C2(F2) sono discriminabili sse esiste un DP dove F1 appare in una diagnosi (minimale) ma non F2 e viceversa

grado di diagnosticabilità (Travè-Massuyès et al. IJCAI 01) Il grado di diagnosticabilità di SD è dato dal rapporto tra il numero di classi di indiscriminabilità e il numero di possibili fault

diagnosticabilità forte (Console at el., DX 00) Grado di diagnosticabilità uguale a 1

Astrazione e Diagnosticabilità (II)

Nella astrazione di valori, se C1(F1) e C1(F2) sono

indiscriminabili si puo’ pensare di astrarli in un fault C1(AF) Nella astrazione di variabili, per astrarre C1 e C2 in AC occorre mappare tutte le coppie in DOM(C1) × DOM(C2) in valori di DOM(AC)

indiscriminabilità tra coppie (Torta & Torasso IJCAI 03) Data la coppia {C1(F1), C2(F2)} essa è indiscriminabile da {C1(F1’), C2(F2’)} sse per ogni DP, se la prima appartiene a una diagnosi anche la seconda appartiene a una diagnosi e viceversa

Data una partizione di DOM(C1) × DOM(C2) in classi di indiscriminabilità è possibile pensare di astrarre C1, C2 in un

Discriminabilità e Osservabilità

La (in)discriminabilità è legata alla osservabilità del sistema.

F1 F2

X Y

Z

F1 F2

X ?

discriminabili indiscriminabili

Astrazione Automatica (I)

Astrazione automatica per:

• produrre velocemente modelli astratti a diversi livelli anche per grandi sistemi

• produrre modelli astratti che soddisfano proprietà formali

• produrre modelli astratti “ottimali”

Astrazione Automatica (II)

1. input: osservabilità, discriminabilità desiderata, informazioni domain-dependent, tipo di modello 2. prodotto: nuovo modello, modello aumentato 3. scope: di valori e/o di variabili

4. proprietà formali richieste: correttezza, completezza, ID 5. qualità richieste: efficienza, compattezza e intuitività del

modello/diagnosi astratti e del mapping di astrazione 6. proprietà dell’algoritmo di astrazione automatica:

ottimalità, efficienza

Astrazione di Variabili

multi-valore

2. prodotto: nuovo modello 3. scope: di valori e di variabili 4. proprietà formali richieste: ID

5. qualità richieste: maggiore efficienza, maggiore compattezza del modello e delle diagnosi astratti, compattezza e intuitività del mapping

6. proprietà dell’algoritmo di astrazione automatica:

efficienza garantita da tecnica greedy e da reasoning ogni volta localizzato a una parte del modello

Function Abstract(SD, CL_k ,Π_i) While (Oracle(SD) = <C_i, C_j>)

LocalDT = CutDT(DT, C_i, C_j)

If (MergeComps(LocalDT, C_i, C_j) = <AC, defAC>) Comps = Comps \ {C_i, C_j} ∪ {AC}

DT = ReviseDT(<AC, defAC>, C_i, C_j) EndIf

EndWhile Return SD EndFunction

Algoritmo di Astrazione

out’’P2 out in P1 out’ V1

cmd

Esempio (I)

out’’ e out osservabili

Esempio (II)

P1 in

out’ cmd V1

out’’

P2

out

Rete Causale

Esempio (III)

P1 in

out’ cmd V1

out’’

P2

out

P2 e V1 sono vicini, ma tra loro c’è il nodo out’’ osservabile

Oracle()

Esempio (IV)

P1 in

out’ cmd V1

out’’

P2

out

P1 e V1 sono vicini e tra loro non ci sono nodi osservabili

Oracle()

Esempio (V)

P1 in

out’ cmd V1

out’’

Porzione della Causal Net rilevante

CutDT()

Esempio (VI)

C1: {<V1(ok),P1(ok)>} def_ABM1=V1(ok) & P1(ok) C2: {<V1(ok),P1(lk)>, def_ABM2= V1(ok) & P1(lk) |

<V1(lk),P1(ok)>, V1(lk) & P1(ok) |

<V1(lk),P1(lk)>} V1(lk) & P1(lk) C3: {<V1(ok),P1(sc)>, def_ABM3=V1(sc) | P1(sc)

<V1(lk),P1(sc)>,

<V1(hb),P1(sc)>,

<V1(so),P1(sc)>,

<V1(sc),P1(ok)>,

<V1(sc),P1(lk)>,

<V1(sc),P1(sc)>}

C5: {<V1(so),P1(ok)>} def_ABM5=V1(so) & P1(ok) C4: {<V1(hb),P1(ok)>, def_ABM4= V1(hb) & P1(ok) |

<V1(hb),P1(lk)>, V1(hb) & P1(lk) |

<V1(so),P1(lk)>} V1(so) & P1(lk)

Esempio (VII)

in cmd AV1

out’’

P2

out

Rete Causale dopo astrazione

out’’P2 out

in AV1

cmd

Esempio (VIII)

Sistema dopo astrazione

Astrazione di Valori

modello relazionale 2. prodotto: nuovo modello 3. scope: di valori

4. proprietà formali richieste: ID

5. qualità richieste: maggiore efficienza e compattezza del modello e delle diagnosi astratti

6. proprietà dell’algoritmo di astrazione automatica:

garantisce che l’astrazione trovata τIND contiene tute e sole le distinzioni sufficienti a soddisfare τTARGdato τOBS

Efficienza garantita da tecniche di tree-clustering per modelli relazionali con topologia ciclica

Problemi Aperti (I)

• qualità della astrazione

definizione di una misura della qualità della astrazione compattezza del mapping (tecniche di inductive learning?) euristiche per ottenere un mapping di buona qualità globale

• diagnosi automatica flessibile

computazione del modello astratto on-line costosa riutilizzo di informazione calcolata off-line?

Problemi Aperti (II)

• astrazioni non-ID

richiedere solo completezza bontà modello astratto come guida

bontà modello astratto come approssimazione

• diagnosi temporale

modelli cambiano (automi, QDE...) concetto di discriminabilità cambia

diversi livelli di astrazione in diversi istanti di tempo?

END