Automi Ibridi

Automi Ibridi

Carla Piazza¹

1Dipartimento di Matematica ed Informatica Universit `a di Udine

carla.piazza@dimi.uniud.it

Indice del Corso (Dis)Ordinato

Automi Ibridi: Sintassi e Semantica Sistemi a stati finiti(breve ripasso) Il problema dellaRaggiungibilit `a Risultati diIndecidibilit `a

Classinotevoli di Automi Ibridi: timed, rectangular, o-minimal, . . . Tecniche diDecisione:(Bi)Simulazione,Cylindric Algebraic Decomposition, Teoremi diSelezione, Semanticheapprossimate . . . e tanto altro:

Logiche temporali Composizione di Automi Il caso Stocastico

Stabilit `a, Osservabilit `a, Controllabilit `a Strumenti Software

Applicazioni

Un po’ di Storia

C’erano una volta . . .

Logiche Temporalie (Finite)Model Checking erano gli inizi degli ’80 . . .

ma ne parleremo la prossima volta

Gi `a da tempo ingegneri, matematici e fisici si occupavano diTeoria del Controllo

Agli inizi degli anni ’90 prendendo spunto dalle due discipline (forse)Henzinger,Alur,Courcobetis,Dill introdussero gliAutomi Ibridi

Un po’ di Storia

C’erano una volta . . .

Logiche Temporalie (Finite)Model Checking erano gli inizi degli ’80 . . .

ma ne parleremo la prossima volta

Gi `a da tempo ingegneri, matematici e fisici si occupavano diTeoria del Controllo

Agli inizi degli anni ’90 prendendo spunto dalle due discipline (forse)Henzinger,Alur,Courcobetis,Dill introdussero gliAutomi Ibridi

Un po’ di Storia

C’erano una volta . . .

Logiche Temporalie (Finite)Model Checking erano gli inizi degli ’80 . . .

ma ne parleremo la prossima volta

Gi `a da tempo ingegneri, matematici e fisici si occupavano diTeoria del Controllo

Agli inizi degli anni ’90 prendendo spunto dalle due discipline (forse)Henzinger,Alur,Courcobetis,Dill introdussero gliAutomi Ibridi

Un po’ di Storia

C’erano una volta . . .

Logiche Temporalie (Finite)Model Checking erano gli inizi degli ’80 . . .

ma ne parleremo la prossima volta

Gi `a da tempo ingegneri, matematici e fisici si occupavano diTeoria del Controllo

Agli inizi degli anni ’90 prendendo spunto dalle due discipline (forse)Henzinger,Alur,Courcobetis,Dill introdussero gliAutomi Ibridi

Hybrid Automata - Intuitivamente

Unautoma ibridoH `e

unautoma a stati finiticonvariabili continueZ

Dyn(v)[Z, Z⁰, T ] Inv (v)[Z]

Dyn(v⁰)[Z, Z⁰, T ] Inv (v⁰)[Z]

Reset (e)[Z, Z⁰]; Act (e)[Z]

Reset (e⁰)[Z, Z⁰]; Act (e⁰)[Z]

v v⁰

Unostato `e una coppiahv , r idover `e una valutazione perZ

Hybrid Automata - Syntax

Definition (Hybrid Automata (Piazza et al.))

Ak-hybrid automatonH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti consists of the following components:

1 Z = Z₁, . . . ,Z_k

andZ⁰ = Z₁⁰, . . . ,Z_k⁰

are two vectors of variables ranging over the reals;

2 hV, Eiis a finite directed graph;

3 Eachv ∈ V is labeled by the two formulæInv (v )[Z ]and Dyn(v )[Z , Z⁰,T ]such that ifInv (v )[p]holds then

Dyn(v )[p, p, 0]holds as well;

4 Eache ∈ E is labeled by the formulæAct(e)[Z ]and Reset(e)[Z , Z⁰].

Hybrid Automata - Syntax

Definition (Hybrid Automata (Piazza et al.))

Ak-hybrid automatonH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti consists of the following components:

1 Z = Z₁, . . . ,Z_k

andZ⁰ = Z₁⁰, . . . ,Z_k⁰

are two vectors of variables ranging over the reals;

2 hV, Eiis a finite directed graph;

3 Eachv ∈ V is labeled by the two formulæInv (v )[Z ]and Dyn(v )[Z , Z⁰,T ]such that ifInv (v )[p]holds then

Dyn(v )[p, p, 0]holds as well;

4 Eache ∈ E is labeled by the formulæAct(e)[Z ]and Reset(e)[Z , Z⁰].

Hybrid Automata - Syntax

Definition (Hybrid Automata (Piazza et al.))

Ak-hybrid automatonH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti consists of the following components:

1 Z = Z₁, . . . ,Z_k

andZ⁰ = Z₁⁰, . . . ,Z_k⁰

are two vectors of variables ranging over the reals;

2 hV, Eiis a finite directed graph;

3 Eachv ∈ V is labeled by the two formulæInv (v )[Z ]and Dyn(v )[Z , Z⁰,T ]such that ifInv (v )[p]holds then

Dyn(v )[p, p, 0]holds as well;

4 Eache ∈ E is labeled by the formulæAct(e)[Z ]and Reset(e)[Z , Z⁰].

Hybrid Automata - Syntax

Definition (Hybrid Automata (Piazza et al.))

Ak-hybrid automatonH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti consists of the following components:

1 Z = Z₁, . . . ,Z_k

andZ⁰ = Z₁⁰, . . . ,Z_k⁰

are two vectors of variables ranging over the reals;

2 hV, Eiis a finite directed graph;

3 Eachv ∈ V is labeled by the two formulæInv (v )[Z ]and Dyn(v )[Z , Z⁰,T ]such that ifInv (v )[p]holds then

Dyn(v )[p, p, 0]holds as well;

4 Eache ∈ E is labeled by the formulæAct(e)[Z ]and Reset(e)[Z , Z⁰].

Hybrid Automata - Syntax

Definition (Hybrid Automata (Piazza et al.))

Ak-hybrid automatonH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti consists of the following components:

1 Z = Z₁, . . . ,Z_k

andZ⁰ = Z₁⁰, . . . ,Z_k⁰

are two vectors of variables ranging over the reals;

2 hV, Eiis a finite directed graph;

3 Eachv ∈ V is labeled by the two formulæInv (v )[Z ]and Dyn(v )[Z , Z⁰,T ]such that ifInv (v )[p]holds then

Dyn(v )[p, p, 0]holds as well;

4 Eache ∈ E is labeled by the formulæAct(e)[Z ]and Reset(e)[Z , Z⁰].

Note alla Definizione

Inv,Dyn,Act,Reset sono insiemi di formule in un linguaggio (al primo ordine)L

Ad esempioL = (+, ∗, <, 0, 1)

le formule vengono valutate su un modelloMdiLsul dominioR

Ad esempioM = (R, +, ∗, <, 0, 1)

i nodiV sono dettelocazioni(o control modes), gli archiE sono detticontrol switches

la variabileT rappresenta iltempo p ∈ R^k

Note alla Definizione

Inv,Dyn,Act,Reset sono insiemi di formule in un linguaggio (al primo ordine)L

Ad esempioL = (+, ∗, <, 0, 1)

le formule vengono valutate su un modelloMdiLsul dominioR

Ad esempioM = (R, +, ∗, <, 0, 1)

i nodiV sono dettelocazioni(o control modes), gli archiE sono detticontrol switches

la variabileT rappresenta iltempo p ∈ R^k

Note alla Definizione

Inv,Dyn,Act,Reset sono insiemi di formule in un linguaggio (al primo ordine)L

Ad esempioL = (+, ∗, <, 0, 1)

le formule vengono valutate su un modelloMdiLsul dominioR

Ad esempioM = (R, +, ∗, <, 0, 1)

i nodiV sono dettelocazioni(o control modes), gli archiE sono detticontrol switches

la variabileT rappresenta iltempo p ∈ R^k

Note alla Definizione

Inv,Dyn,Act,Reset sono insiemi di formule in un linguaggio (al primo ordine)L

Ad esempioL = (+, ∗, <, 0, 1)

le formule vengono valutate su un modelloMdiLsul dominioR

Ad esempioM = (R, +, ∗, <, 0, 1)

i nodiV sono dettelocazioni(o control modes), gli archiE sono detticontrol switches

la variabileT rappresenta iltempo p ∈ R^k

Note alla Definizione

Inv,Dyn,Act,Reset sono insiemi di formule in un linguaggio (al primo ordine)L

Ad esempioL = (+, ∗, <, 0, 1)

le formule vengono valutate su un modelloMdiLsul dominioR

Ad esempioM = (R, +, ∗, <, 0, 1)

i nodiV sono dettelocazioni(o control modes), gli archiE sono detticontrol switches

la variabileT rappresenta iltempo p ∈ R^k

Esempio: Termostato

Example (Termostato)

Consideriamo una stanzariscaldatada untermosifone controllato da untermostato

Quando il termosifone `eaccesolatemperatura cresce esponenzialmentenel tempo

Qualdo il termosifone `espentolatemperatura decresce esponenzialmentenel tempo

Iltermostato accendeil termosifone quando latemperatura scendeal di sotto dei19C

Iltermostato spegneil termosifone quando latemperatura saleal di sopra dei 21C

Esempio: Termostato

Modelliamo l’andamento dellatemperaturanel tempo con un automa ibridoH avente:

2 locazioniONeOFF

2 archi che collegano le due locazioni

1 variabile continuaZ che rappresenta la temperatura

Esempio: Termostato

H = hZ,Z⁰,V,E,Inv,Dyn,Act,Resetitale che:

Z eZ⁰ sono due variabili

V = {ON, OFF }eE = {(ON, OFF ), (OFF , ON)}

Inv (ON)[Z ] := Z ≤ 22eDyn(ON)[Z , Z⁰,T ] := Z⁰ =Z ∗ e^T Inv (OFF )[Z ] := Z ≥ 18e

Dyn(OFF )[Z , Z⁰,T ] := Z⁰ =Z /e^T Act((ON, OFF ))[Z ] := Z ≥ 21e Reset((ON, OFF ))[Z , Z⁰] :=Z⁰ =Z Act((OFF , ON))[Z ] := Z ≤ 19e Reset((OFF , ON))[Z , Z⁰] :=Z⁰ =Z

. . . meglio disegnarlo alla lavagna

Hybrid Automata - Sintassi in Letteratura

T. A. Henzinger

Hybrid Automata - Sintassi in Letteratura

J. Lygeros et al.

Perch ´e . . .

. . . nella nostra definizione non ci sono leequazioni differenziali?

perch `e fanno tanta paura

perch `e non vogliamo incolparle dell’indecidibilit `ae complessit `a

perch `e ci vorrebbero altre 200 ore di lezione per parlarne perch `e ci servirebbero deglianalistiper parlarne

perch `e vogliamorisultati/tecniche generaliche funzionino per tutte le equazionirisolvibili/approssimabili

Perch ´e . . .

. . . nella nostra definizione non ci sono leequazioni differenziali?

perch `e fanno tanta paura

perch `e non vogliamo incolparle dell’indecidibilit `ae complessit `a

perch `e ci vorrebbero altre 200 ore di lezione per parlarne perch `e ci servirebbero deglianalistiper parlarne

perch `e vogliamorisultati/tecniche generaliche funzionino per tutte le equazionirisolvibili/approssimabili

Hybrid Automata - Semantics

` = hv , r iisadmissibleifInv (v )[r ]holds

v v⁰

r

s f (t⁰)

Definition (Continuous Transitions)

hv , r i−→^t _Chv , si ⇐⇒

There exists a continuous function f : R⁺ 7→ R^k such that r = f (0), s = f (t) and for each t⁰ ∈ [0, t] the formulæInv (v )[f (t⁰)] and Dyn(v )[r , f (t⁰),t⁰]hold

Hybrid Automata - Semantics

` = hv , r iisadmissibleifInv (v )[r ]holds

v v⁰

r s

Definition (Discrete Transitions)

hv , r i ^{hv ,v}

0i

−−−→_Dhv⁰,si ⇐⇒

hv , v⁰i ∈ E, Inv (v )[r ], Act(hv , v⁰i)[r ],

Reset(hv , v⁰i)[r , s] and Inv (v⁰)[s]hold

Note alla Definizione

Abbiamo definito un grafoinfinitocon due tipi principali di archi

(V × R^k,−−→^{h , i} _D,−→_C)

Potevo essere pi `u precisa?

Avrei potuto tenere traccia anche della funzione continuaf Potevo essere meno precisa?

Avrei potuto considerare un solo tipo di archi

→=−−→^{h , i} _D ∪ −→_C untimed semantics

Note alla Definizione

Abbiamo definito un grafoinfinitocon due tipi principali di archi

(V × R^k,−−→^{h , i} _D,−→_C)

Potevo essere pi `u precisa?

Avrei potuto tenere traccia anche della funzione continuaf Potevo essere meno precisa?

Avrei potuto considerare un solo tipo di archi

→=−−→^{h , i} _D ∪ −→_C untimed semantics

Note alla Definizione

Abbiamo definito un grafoinfinitocon due tipi principali di archi

(V × R^k,−−→^{h , i} _D,−→_C)

Potevo essere pi `u precisa?

Avrei potuto tenere traccia anche della funzione continuaf Potevo essere meno precisa?

Avrei potuto considerare un solo tipo di archi

→=−−→^{h , i} _D ∪ −→_C untimed semantics

Note alla Definizione

Abbiamo definito un grafoinfinitocon due tipi principali di archi

(V × R^k,−−→^{h , i} _D,−→_C)

Potevo essere pi `u precisa?

Avrei potuto tenere traccia anche della funzione continuaf Potevo essere meno precisa?

Avrei potuto considerare un solo tipo di archi

→=−−→^{h , i} _D ∪ −→_C untimed semantics

Note alla Definizione

Abbiamo definito un grafoinfinitocon due tipi principali di archi

(V × R^k,−−→^{h , i} _D,−→_C)

Potevo essere pi `u precisa?

Avrei potuto tenere traccia anche della funzione continuaf Potevo essere meno precisa?

Avrei potuto considerare un solo tipo di archi

→=−−→^{h , i} _D ∪ −→_C

untimed semantics

Hybrid Automata - Reachability

Hybrid Automata - Reachability

Hybrid Automata - Reachability

Hybrid Automata - Reachability

Hybrid Automata - Reachability

Hybrid Automata - Reachability

Hybrid Automata - Reachability

LetI, F ∈ R^k. Can we reachF fromI?

Trace and Reachability

AtraceofH is a sequence of admissible states

[`<sub>0</sub>, `₁, . . . , `<sub>i</sub>, . . . , `n]such that`<sub>i−1</sub> → `_i holds∀i ∈ [1, n]

Definition (Reachability)

The automatonH reachess ∈ R^k fromr ∈ R^k if there exists a tracetr = [`<sub>0</sub>, . . . , `n]ofH such that`0= hv , r iand`n= hu, si, for somev , u ∈ V

Definition (Reachability Problem)

Given an automatonH, a set of starting pointsI ⊆ R^k, and a set of ending pointsF ⊆ R^k we wish to decide whether there exists a point inIfrom which a point inF is reachable

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Mille fonti di Non Determinismo

Gli Hybrid Automata sono non-deterministici in quanto:

Locazionidistinte possono parzialmente condividere gli invarianti

Da ogni stato ammissibile possono partire diverse traiettoriecontinue

Ci possono essere archi che portano in locazioni distinte ma che condividono parzialmente leactivation

Leattivazioninon sono necessariamente sulle frontiere degli invarianti

Iresetnon sono necessariamente deterministici

Esempio: Termostato

Z ≥ 21 Z⁰=Z

Z ≤ 19 Z⁰=Z

Z ≥18 Z⁰=Z ∗e^−T Z ≤22

Z⁰=Z ∗e^T

hON, 15i−^0.1−→C hON, 16.57i−−→^0.25 C hON, 21.28i−−−−−−→^{hON,OFF i}D

hOFF , 21.28i . . .

hON, 15i−−→^0.35C hON, 21.28i−−−−−−→^{hON,OFF i}D hOFF , 21.28i . . . hOFF , 18.5i−−−−−−→^{hOFF ,ONi}D hON, 18.5i . . .

hOFF , 18.5i−−→^0.01 C hOFF , 18.31i−−−−−−→^{hOFF ,ONi}D hON, 18.31i . . .

Esempio: Termostato

Osserviamo che:

Da ogni punto partono infinite traiettorie Alcune sono sostanzialmente “equivalenti”

Altre no!

Automi Ibridi: Sintassi e Semantica

Esempio: Termostato

Che modello avrei potuto costruire con meno informazioni?

Z ≤ 19 Z⁰=Z

Z ≥18 Z ≤22

Z0 >Z Z0 <Z

Questo hapi `u tracce del precedente!

Esempio: Termostato

Che modello avrei potuto costruire con meno informazioni?

Z ≥ 21 Z⁰=Z

Z ≤ 19 Z⁰=Z

Z ≥18 Z ≤22

Z0 >Z Z0 <Z

Questo hapi `u tracce del precedente!

Hybrid Automata - Semantica in Letteratura

Henzinger:

Introduce unatimeded unaun-timedsemantics Etichetta le transizioni discrete con glieventi Scarta lezeno-traces

Parla di machine-closed systems e nonzeno automata

Hybrid Automata - Semantica in Letteratura

Lygeros et al. pag. 39

Introducono la nozione dihybrid time set(sequenza di intervalli temporali)

Su questa nozione basano la definizione ditransizioni discrete e continue

Distinguono traexecutions:Finite,Infinite,Zeno,Maximal Studiano condizioni al contorno

Altri Problemi

Henzingerintroduce altri due problemi:

emptiness problem: l’automa ha almeno una traccia divergente inizializzata

(finitary) {timed} trace inclusion problem: dati due automi ibridi determinare se ogni traccia {temporizzata} (finita) del primo `e anche una traccia del secondo.

Sono problemi legati all’analisi di propriet `a disafetyeliveness Henzinger dice:

ilreachabilityproblem pu `o essere ridotto altrace inclusion problem

l’emptinessproblem pu `o essere ridotto altimed trace inclusionproblem

Altri Problemi

Henzingerintroduce altri due problemi:

emptiness problem: l’automa ha almeno una traccia divergente inizializzata

(finitary) {timed} trace inclusion problem: dati due automi ibridi determinare se ogni traccia {temporizzata} (finita) del primo `e anche una traccia del secondo.

Sono problemi legati all’analisi di propriet `a disafetyeliveness Henzinger dice:

ilreachabilityproblem pu `o essere ridotto altrace inclusion problem

l’emptinessproblem pu `o essere ridotto altimed trace inclusionproblem

Altri Problemi

Henzingerintroduce altri due problemi:

emptiness problem: l’automa ha almeno una traccia divergente inizializzata

(finitary) {timed} trace inclusion problem: dati due automi ibridi determinare se ogni traccia {temporizzata} (finita) del primo `e anche una traccia del secondo.

Sono problemi legati all’analisi di propriet `a disafetyeliveness Henzinger dice:

ilreachabilityproblem pu `o essere ridotto altrace inclusion problem

l’emptinessproblem pu `o essere ridotto altimed trace inclusionproblem

I nostri autori

Thomas A. Henzingeris Professor of Computer and

Communication Sciences at EPFL in Lausanne, Switzerland, and Adjunct Professor of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He holds a Dipl. Ing. degree in Computer Science from Kepler University in Linz, Austria, an M.S. degree in Computer and Information Sciences from the University of Delaware, and a Ph.D. degree in Computer Science from Stanford University (1991) with Manna.

I nostri autori

Rajeev Aluris Professor of Computer and Information Science at University of Pennsylvania. He obtained his bachelor’s degree in computer science from Indian Institute of Technology at Kanpur in 1987, and PhD in computer science from Stanford University in 1991 with Dill.

I nostri autori

David Dillis a Professor of Computer Science and, by courtesy, Electrical Engineering at Stanford University. He has been on the faculty at Stanford since 1987. He has an S.B. in Electrical Engineering and Computer Science from Massachusetts Institute of Technology (1979), and an M.S and Ph.D. from Carnegie-Mellon University (1982 and 1987) with Clarke.

I nostri autori

John Lygeroshas been a Professor of Computation and Control at the Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, since July 2006 and the Head of the Automatic Control Laboratory since January 2009. He completed a B.Eng. degree in electrical engineering in 1990 and an M.Sc. degree in Systems Control in 1991, both at Imperial College of Science Technology and Medicine, London, U.K.. In 1996 he obtained a Ph.D. degree from the Electrical Engineering and Computer Sciences Department, University of California, Berkeley with Sastry.