Automi Ibridi

(1)

Automi Ibridi

Carla Piazza¹

1Dipartimento di Matematica ed Informatica Universit `a di Udine

carla.piazza@dimi.uniud.it

(2)

Indice del Corso (Dis)Ordinato

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

Classi notevoli di Automi Ibridi:timed, rectangular,o-minimal, . . . Tecniche di Decisione: (Bi)Simulazione,Cylindric Algebraic Decomposition, Teoremi di Selezione, Semantiche approssimate Equazioni Differenziali

. . . e tanto altro:

Logiche temporali Composizione di Automi Il caso Stocastico

Stabilit à, Osservabilit à, Controllabilit à Strumenti Software

Applicazioni

(3)

Eliminazione dei Quantificatori

Definition (Eliminazione dei Quantificatori)

Una teoria al primo-ordineT ammette l’eliminazione dei quantificatori se per ogni formulaψdiT esiste una formula QF (ψ)equivalente aψe priva di quantificatori

Example SuRla formula

∀x(yx²+zx + w > 0) E equivalente alla formula`

z²− 4yw < 0

(4)

Eliminazione dei Quantificatori

z²− 4yw < 0

(5)

Eliminazione dei Quantificatori

z²− 4yw < 0

(6)

Eliminazione dei Quantificatori e Decidibilit `a

Theorem

SeT ammette l’eliminazione dei quantificatori,QF (ψ) è calcolabile e la validit à/soddisfacibilit à delle formule senza quantificatori è decidibile, alloraT èdecidibile

Example (Aritmetica di Presburger)

SiaT = (+, 0, 1)la teoria al primo-ordine di(N, +, 0, 1)ovvero:

0 6= x + 1 x + 0 = x

x + 1 = y + 1 → x = y

(x + y ) + z = x + (y + z) ∧ x + y = y + x (P(0) ∧ P(x ) → P(x + 1)) → ∀y (P(y ))

T ammette l’eliminazione dei quantificatori ed `edecidibile

(7)

Eliminazione dei Quantificatori e Decidibilit `a

Theorem

SeT ammette l’eliminazione dei quantificatori,QF (ψ) è calcolabile e la validit à/soddisfacibilit à delle formule senza quantificatori è decidibile, alloraT èdecidibile

Example (Aritmetica di Presburger)

SiaT = (+, 0, 1)la teoria al primo-ordine di(N, +, 0, 1)ovvero:

0 6= x + 1 x + 0 = x

x + 1 = y + 1 → x = y

(x + y ) + z = x + (y + z) ∧ x + y = y + x (P(0) ∧ P(x ) → P(x + 1)) → ∀y (P(y ))

T ammette l’eliminazione dei quantificatori ed `edecidibile

(8)

O-minimalit `a

Definition (O-minimalit `a)

SiaM = (M, . . . , <)un modello su cui è definito un ordine totale <,M è o-minimale se ogni insiemeX ⊆ M definibile è un unione finita dipunti e intervalli

Una teoriaT `e o-minimale se ha solo modelli o-minimali Example

SiaR_sin= (R, +, sin(·), 0, 1, <) sin(x ) = 0

definisce un insieme infinito di punti, quindiR_sinnon `e o-minimale

(9)

O-minimalit `a

Definition (O-minimalit `a)

SiaM = (M, . . . , <)un modello su cui è definito un ordine totale <,M è o-minimale se ogni insiemeX ⊆ M definibile è un unione finita dipunti e intervalli

Una teoriaT `e o-minimale se ha solo modelli o-minimali Example

SiaR_sin= (R, +, sin(·), 0, 1, <) sin(x ) = 0

definisce un insieme infinito di punti, quindiR_sinnon `e o-minimale

(10)

O-minimalit `a

Example

SiaN = (N, +, 0, 1)l’aritmetica di Presburger

∃y (x = y + y )

E soddisfatta dall’insieme` P dei numeri pari, quindiN non `e o-minimale

Example

SiaR_exp= (R, +, ∗, e^·,0, 1, <) `e o-minimale

(11)

O-minimalit `a

Example

SiaN = (N, +, 0, 1)l’aritmetica di Presburger

∃y (x = y + y )

E soddisfatta dall’insieme` P dei numeri pari, quindiN non `e o-minimale

Example

SiaR_exp= (R, +, ∗, e^·,0, 1, <) `e o-minimale

(12)

O-minimalit `a e Decidibilit `a

Theorem

SeT `e o-minimale ed ammette l’eliminazione dei quantificatori, alloraT `edecidibile

Example

SiaR = (R, +, ∗, 0, 1, <) `e o-minimale ed ammette l’eliminazione dei quantificatori [Tarski]

E anche nota come “semi-algebraic` theory over the reals”

Gli algoritmi di decisione sono anche noti comeCylindrical Algebraic Decomposition (CAD)(si veda Mathematica, Matlab, . . . )

(13)

Un caso unidimensionale

Consideriamo un polinomio di gradonin una variabile p(X ) = anXⁿ+a_n−1Xⁿ⁻¹+ · · · +a₁X + a₀

Supponiamo chelim_{X →−∞}p(X ) = −∞elim_{X →+∞}p(X ) = +∞

La formulap(X ) > 0ha almeno una soluzione inR

(14)

Un caso unidimensionale

(15)

Un caso unidimensionale

(16)

Un caso unidimensionale

esiste un intervallo in cuip(X )cresce esiste un intervallo in cuip⁰(X ) > 0 p⁰(X )`e di gradon − 1

studiop⁰(X ) > 0 studiop⁰⁰(X ) > 0 . . .

doponpassi arrivo ad una costante

(17)

Un caso unidimensionale

(18)

Un caso unidimensionale

(19)

Un caso unidimensionale

(20)

Un caso unidimensionale

(21)

Un caso unidimensionale

(22)

Un caso unidimensionale

(23)

Radici reali di un polinomio

Theorem (Sturm)

Siap(X )un polinomio suR, sianoa, b ∈ R `e possibile

determinare quante radici dip(X )cadono nell’intervallo(a, b)

Per arrivare al risultato di Tarski suR^k occorre sfruttare le proiezioni

(24)

O-minimal Hybrid Automata

Definition (Lafferriere, Pappas, Sastry 2000)

Un automaH = hZ,Z⁰,V,E,Inv,Dyn,Act,Reseti `e detto o-minimalese

le formuleInv,Act,Reset sono definite su una teoria o-minimale

Dynsono campi vettoriali le cui soluzioni sono o-minimali Reset non dipendono daZ

(25)

O-minimal Hybrid Automata

Theorem

Gli automi o-minimali hanno il quoziente perbisimulazione finito

Se costruiti su una teoria o-minimaledecidibile, gli automi o-minimali hanno una quoziente per bisimulazionecalcolabile

(26)

O-minimal Hybrid Automata

Theorem

Gli automi o-minimali hanno il quoziente perbisimulazione finito

Se costruiti su una teoria o-minimaledecidibile, gli automi o-minimali hanno una quoziente per bisimulazionecalcolabile

come possiamoestenderli? (FOCoRe, IDA, Prodotto Cartesiano)

come altro possiamosfruttareil risultato di Tarski? (Tiwari, Ratschan)

(27)

Inclusion Dynamics

Passiamo da funzioni adinclusioniper definire il flusso

r = f (r, 0) f (r, δ)

f (r, 2δ)

f (r, 3δ)

f (r, 4δ)

r F (r, δ) F (r, 2δ)

F (r, 3δ) F (r, 4δ)

Dyn[Z , Z⁰,T ] ≡ Z⁰=f (Z , T ) Dyn[Z , Z⁰,T ] ≡ Z⁰ ∈ F (Z , T )

(28)

Inclusion Dynamics

Passiamo da funzioni adinclusioniper definire il flusso

r = f (r, 0) f (r, δ)

f (r, 2δ)

f (r, 3δ)

f (r, 4δ)

r F (r, δ) F (r, 2δ)

F (r, 3δ) F (r, 4δ)

Dyn[Z , Z⁰,T ] ≡ Z⁰=f (Z , T ) Dyn[Z , Z⁰,T ] ≡ Z⁰ ∈ F (Z , T )

(29)

Perch ´e Inclusion Dynamics?

Possiamo usarle per:

approssimaresoluzioni di equazioni differenziali stimareparametri non noti coinvolti nelle dinamiche

(30)

Problemi

Dobbiamo garantire che seDyn(v )[Z , Z⁰,T ]vale, allora esiste un flussocontinuoche soddisfa la dinamica

SeDyn(v )[Z , Z⁰,T ] ≡ Z⁰=f_v(Z , T ), `e sufficiente richiedere chefv sia continua

SeDyn(v )[Z , Z⁰,T ] ≡ Z⁰∈ Fv(Z , T ), la Hausdorff continuit `a di Fv non basta

(31)

Esempio

F_v(X , t) =

ht cos θ, sin θi | θ ∈ [¹_t,¹_t +2π − |t|]

if t 6= 0 {hx, y i | y ∈ [−1, 1] ∧ x = 0} otherwise

+1

−1 Fv(X, 0)

Fv(X, t0)

Fv(X, t1)

t0 t1

1 t1

1 t₁− |t|

(32)

Hybrid Automata with Inclusion Dynamics

Definition (Michael’s Form)

SiaF_Z^v(T )^def= {Z⁰| Dyn(v )[Z , Z⁰,T ] ∧ Inv (v )[Z⁰]}. Un automa `e inMichael’s formse

1 F_Z^v `e lower semi-continua

2 per ognit ∈ I_Z^v l’insiemeF_Z^v(t) è chiuso e convesso doveI_Z^v è il pi ù grande intervallo[0, t⁰)tale cheF_Z^v(t) 6= ∅per ognit ∈ [0, t⁰)

Theorem

SeH `e in Michael’s form, alloras ∈ F_r^v(t)ssehv , r i−→^t _Chv , si.

(33)

Hybrid Automata with Inclusion Dynamics

Definition (Michael’s Form)

SiaF_Z^v(T )^def= {Z⁰| Dyn(v )[Z , Z⁰,T ] ∧ Inv (v )[Z⁰]}. Un automa `e inMichael’s formse

1 F_Z^v `e lower semi-continua

2 per ognit ∈ I_Z^v l’insiemeF_Z^v(t) è chiuso e convesso doveI_Z^v è il pi ù grande intervallo[0, t⁰)tale cheF_Z^v(t) 6= ∅per ognit ∈ [0, t⁰)

Theorem

SeH `e in Michael’s form, alloras ∈ F_r^v(t)ssehv , r i−→^t _Chv , si.

(34)

Michael’s Form e Raggiungibilit `a

Per ogni automa in Michael’s form, possiamo scrivere una formulaReach(H, ph)[Z , Z⁰,T ], doveph = v₀, . . . ,v_n `e un cammino inhV, Ei, tale che

Reach(H, ph)[Z , Z⁰,T ]

vale ⇐⇒

H raggiungehvn,Z⁰i dahv₀,Z icon una

traiettoria corrispondente aph

Problema

Sfortunatamente, esistono automi con cammini discreti di lunghezza infinita

(35)

Michael’s Form e Raggiungibilit `a

Per ogni automa in Michael’s form, possiamo scrivere una formulaReach(H, ph)[Z , Z⁰,T ], doveph = v₀, . . . ,v_n `e un cammino inhV, Ei, tale che

Reach(H, ph)[Z , Z⁰,T ]

vale ⇐⇒

H raggiungehvn,Z⁰i dahv₀,Z icon una

traiettoria corrispondente aph

Problema

Sfortunatamente, esistono automi con cammini discreti di lunghezza infinita

(36)

FOCoRe e IDA

FOCoRe(FirstOrderConstantReset hybrid automata) sono first-order hybrid automata:

in Michael’s form

conconstant resets(i.e.,Reset(e)[Z , Z⁰]non dipende da Z)

IDA(IndependentDynamics hybridAutomata) consentono identity resetstra locazioni che hanno la stessa dinamica

Possiamo ridurre il problema della raggiungibilit `a per FOCoRe e IDAT-automata al problema della soddifacibilit `a di formule in T

(37)

FOCoRe e IDA

FOCoRe(FirstOrderConstantReset hybrid automata) sono first-order hybrid automata:

in Michael’s form

conconstant resets(i.e.,Reset(e)[Z , Z⁰]non dipende da Z)

IDA(IndependentDynamics hybridAutomata) consentono identity resetstra locazioni che hanno la stessa dinamica Possiamo ridurre il problema della raggiungibilit `a per FOCoRe e IDAT-automata al problema della soddifacibilit `a di formule in T

(38)

Raggiungibilit `a e Bisimulazione

Theorem

SiaT una teoria al primo-ordine decidibile. Il problema della raggiungibilit `a per FOCoRe e IDAT-automata `e decidibile

Theorem

Esistono FOCoRe e IDA con quozienti per (bi)simulazione infiniti

(39)

Predicate Abstraction

A. Tiwari and G. Khanna Series of Abstractions for Hybrid Automata, HSCC 2002

Consideriamo un’automaH in cui:

ledinamichesono definite conequazioni differenzialidella forma

Z = p(Z )˙ conppolinomio

invarianti, activation e resetsonodisequazioni tra polinomi In generale, su questi automi la raggiungibilit `a `eindecidibile

(40)

Prediacate Abstraction - Intuitivamente

Consideriamo il caso di una sola locazione in cui Z = p(Z )˙

Divido lo spazio in un numero finito di regioni a seconda che p(Z ) > 0

p(Z ) = 0 p(Z ) < 0

(41)

Predicate Abstraction - Intuitivamente

p(Z ) `e continua, quindi per passare dap(Z ) > 0ap(Z ) < 0 occorre passare attraversop(Z ) = 0

inoltre per passare dap(Z ) > 0ap(Z ) = 0deve essereZ⁰⁰<0

calcoloZ⁰⁰=p⁰(Z ) ∗ Z⁰ =p⁰(Z ) ∗ p(Z ) risuddivido lo spazio . . .

itero il ragionamento

(42)

Predicate Abstraction - Intuitivamente

(43)

Predicate Abstraction - Intuitivamente

(44)

Predicate Abstraction - Intuitivamente

(45)

Predicate Abstraction - Stati e Transizioni

Intendo astrarreH con(Q, →)

Come costruiscoQ?

considero l’insiemeP₀dei polinomi che occorrono inH saturoP₀chiudendolo per ‘‘derivazione”(ottengoP) per ogni polinomiop ∈ P considero una variabilex_p che varia in{−, +, 0}

considero l’insiemeQ = {−, +, 0}^|P|delle possibili combinazioni di valori assunti dalle varibili

(46)

Predicate Abstraction - Stati e Transizioni

Intendo astrarreH con(Q, →)

Come costruisco →? seq1→ q2, allora devono valere le seguenti condizioni:

sex_p = +inq₁ex_p =0inq₂, allora deve esserex_p⁰ = − inq₁

. . .

(47)

Constraint Interval Arithmetics

S. Ratschan and Z. She Safety Verification of Hybrid Systems by Constraint Propagation Based Abstraction Refinement, HSCC 2005