Automi Ibridi

(1)

Automi Ibridi

Carla Piazza¹

1Dipartimento di Matematica ed Informatica Universit `a di Udine

carla.piazza@dimi.uniud.it

(2)

Conclusions

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)

Nella lezione precedente . . .

. . . abbiamo visto che:

SeH `e definito con formule su(R, +, ∗, <, 0, 1), allora Path Reachability ⇔ Formula Satisfiability

Reachability ⇔ Infinite Formula Satisfiability Inoltre si possono usare le formule per definiremodelli astratti

Casagrande et al. Inclusion dynamics hybrid automata. I.&C., 2008 Tiwari et al. Series of Abstractions for Hybrid Automata. HSCC, 2002

(4)

Conclusions

Warning!

i risultati relativi allaPath Reachabilitypresuppongono almeno latransitivit `adelle dinamiche

con le formule siamo passati da semanticaoperazionalea denotazionale

anche nei modelliastrattiabbiamo mantenutoprecisione infinita

Proviamo a passare aprecisione finita

(5)

Warning!

(6)

Conclusions

Warning!

(7)

Warning!

(8)

Conclusions

Which is Your Point of View?

The world isdense

(R, +, ∗, <, 0, 1) first-order theory isdecidable

The world isdiscrete

Diophantine equations areundecidable

What about theirinterplay?

(9)

Which is Your Point of View?

The world isdense

(R, +, ∗, <, 0, 1) first-order theory isdecidable

The world isdiscrete

Diophantine equations areundecidable

What about theirinterplay?

(10)

Conclusions

Example

Bouncing Ball

X = V ˙ V = −g ˙

X ≥ 0 X

⁰

= X

V

⁰

= −γV

(11)

Example

Zeno Behavior The automaton avoids time elapsing by crossing edges infinitely often

(12)

Conclusions

Example

Zeno Point The limit point of a Zeno behavior

(13)

Delta-Notch

DeltaandNotchare proteins involved in cell differentiation (see, e.g., Collier et al., Ghosh et al.)

Notch production is triggered by high Delta levels in neighboring cells

Delta production is triggered by low Notch concentrations in thesame cell

High Delta levels lead todifferentiation

(14)

Conclusions

Delta-Notch: Single Cell Automaton

q₁ q₂

q₃ q₄

X_D⁰ = fD(XD, T ) X_N⁰ = fN(XN, T )

X_D⁰ = gD(XD, T ) X_N⁰ = fN(XN, T )

X_D⁰ = fD(XD, T ) X_N⁰ = gN(XN, T )

X_D⁰ = gD(XD, T ) X_N⁰ = gN(XN, T )

f_Dandf_N increaseDelta and Notch,g_Dandg_N decreaseDelta and Notch, respectively

(15)

Delta-Notch: Two Cells Automaton

It is the Cartesian product of two “single cell” automata

TheZenostate can occur only in the case of

two cells withidenticalinitial concentrations

(16)

Conclusions

Verification

Question

Can we automaticallyverifyhybrid automata?

Let us start from the basic case ofReachability

Naive Reachability (H, Initial set) Old ← ∅

New ← Initial set while New 6= Old do

Old ← New

New ← Discrete Reach(H, Continuous Reach(H, Old )) return Old

(17)

Verification

Question

Can we automaticallyverifyhybrid automata?

Let us start from the basic case ofReachability

Naive Reachability (H, Initial set) Old ← ∅

New ← Initial set while New 6= Old do

Old ← New

New ← Discrete Reach(H, Continuous Reach(H, Old )) return Old

(18)

Conclusions

Bounded Sets and Undecidability

Even if the invariants arebounded,reachabilityisundecidable

Proof sketch

Encode two-counter machine by exploiting density:

each counter value,n, is represented in a continuous variable by the value2⁻ⁿ

each control function is mimed by a particular location

(19)

Where is the Problem?

Keeping in mind our examples:

Question “Meaning”

What is the meaning of these undecidability results?

Question “Decidability”

Can we avoid undecidability by adding some natural hypothesis to the semantics?

(20)

Conclusions

Undecidability in Real Systems

Undecidabilityin our models comes from . . . infinitedomains: unbounded invariants densedomains: the “trick”nas2⁻ⁿ

But whichreal systemdoes involve . . . unbounded quantities?

infinite precision?

Unboundednessanddensityabstractdiscrete largequantities

(21)

Undecidability in Real Systems

Undecidabilityin our models comes from . . . infinitedomains: unbounded invariants densedomains: the “trick”nas2⁻ⁿ

But whichreal systemdoes involve . . . unbounded quantities?

infinite precision?

Unboundednessanddensityabstractdiscrete largequantities

(22)

Conclusions

Dense vs Discrete - Intuition

We do not really want to completely abandondensedomains

We need to introduce afinitelevel ofprecisioninbounded densedomains, we can distinguish two sets only if they differ of

“at least ”

Intuitively, we can see thatsomething newhas been reached only if areasonable largeset of new points has been

discovered, i.e., we aremyope

(23)

Dense vs Discrete

Lemma (Convergence)

Let S ⊆ R^k be a bounded set such that S = ∪_i∈ND_i, with either D_i =D_j or D_i∩ D_j = ∅

If there exists > 0 such that for each i ∈ N there exists ai such that B({a_i}, ) ⊆ Di, then there exists j ∈ N such that

S = ∪_i≤jD_i

This is a trivialcompactness-likeresult

(24)

Conclusions

Finite Precision Semantics

Definition (-Semantics) Let > 0. For each formula ψ:

() either {|ψ|}= ∅or {|ψ|}contains an -ball (∩) {|ψ₁∧ ψ₂|}⊆ {|ψ₁|}∩ {|ψ₂|}

(∪) {|ψ₁∨ ψ₂|}= {|ψ₁|}∪ {|ψ₂|} (¬) {|ψ|}∩ {|¬ψ|}= ∅

It is a general framework: there exist many different -semantics

(25)

Reachability

Eps-Reachability(H, ψ[Z ], {| · |}) R[Z ] ← ψ[Z ]

May New R[Z⁰] ← ∃Z ( \Reach¹(Z , Z⁰) ∧R[Z ]) New R[Z ] ← May New R[Z ] ∧ ¬R[Z ]

while({|New R[Z ]|}6= ∅) R[Z ] ← R[Z ] ∨ New R[Z ]

May New R[Z⁰] ← ∃Z ( \Reach¹(Z , Z⁰) ∧R[Z ]) New R[Z ] ← May New R[Z ] ∧ ¬R[Z ]

return R[Z ]

(26)

Conclusions

A Decidability Result

Theorem (Reachability Problem)

Using-semanticsand assuming bothboundedinvariants and decidability for specification language, we havedecidability of reachabilityproblem for hybrid automata

Proof Sketch

Because of condition () of -semantics, continuous steps can either:

increase the reached set by at least do not increase the reach set

(∩), (∪), and (¬) ensure that the sets New R are disjoint

(27)

A Decidability Result

Theorem (Reachability Problem)

Using-semanticsand assuming bothboundedinvariants and decidability for specification language, we havedecidability of reachabilityproblem for hybrid automata

Proof Sketch

Because of condition () of -semantics, continuous steps can either:

increase the reached set by at least do not increase the reach set

(∩), (∪), and (¬) ensure that the sets New R are disjoint

(28)

Conclusions

An Instance of -semantics

Definition

Let > 0. We define [|ψ|]by structural induction on ψ as follows:

[|t₁◦ t₂|]=B([|t₁◦ t₂|], ), for ◦ ∈ {=, <}

[|ψ₁∨ ψ₂|]= [|ψ₁|]∪ [|ψ₂|]

[|ψ1∧ ψ₂|]= ∪B({p},)⊆[|ψ1|]∩[|ψ2|]B({p}, ) [|∃Z ψ[Z , X ]|]= ∪_p∈R[|ψ[p, X ]|]

[|∀Z ψ[Z , X ]|]= ∪_{B({p},)⊆∩}

Z ∈R[|ψ[Z ,X ]|]B({p}, ) [|¬ψ|] = ∪B({p},)∩[|ψ|]=∅B({p}, )

(29)

Conclusions

Hybrid automata are bothpowerfulandnaturalin the modeling of hybrid systems

May be a little bittoo expressive. . . Real systems always havefinite precision

-semanticsintroduce a finite precision ingredient in hybrid automata

Using -semantics wedo not have Zeno behaviors

(30)

Conclusions

Why not. . .

. . . modeling systems over discrete latices?

00 0000 00 11 1111 11

0000 0000 1111 1111

000000 000000 111111 111111

0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000

1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111

0000 00000000 0000 00000000 00000000 00000000 0000 00000000 00000000 0000

1111 11111111 1111 11111111 11111111 11111111 1111 11111111 11111111 1111

0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000

1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111

000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000

111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111

00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000

11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111

00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000

11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111

000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000

111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111

0000 00000000 0000 00000000 00000000 00000000 0000 00000000 00000000 0000

1111 11111111 1111 11111111 11111111 11111111 1111 11111111 11111111 1111

0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000

1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111

No, because three main reasons:

modeling would became harder

we would increase computational complexity we would still assume infinite precision!!! (e.g., 0, 999 . . . 9 6= 1)

. . . using only < and > instead of =?

No, because reachability is still undecidable.

(31)

Under, Over and Demorgan

Example

Consider the formula 1 < X < 5 and = 0.1

We have that [|1 < X < 5|] = [|1 < X ∧ X < 5|]= (0.9, 5.1),

Consider the formula ¬(1 < X < 5)

We get that [|¬(1 < X < 5)|]= (−∞,0.9) ∪ (5.1, +∞)

Notice that this last formula is not equivalent to X ≤ 1 ∨ X ≥ 5 whose semantics is [|X ≤ 1 ∨ X ≥ 5|]= (−∞,1.1) ∪ (4.9, +∞)

(32)

Conclusions

References

Casagrande et al., “Discrete Semantics for Hybrid Automata” Discrete Event Dynamic Systems 2009

A. Girard and G. J. Pappas, “Approximation metrics for discrete and continuous systems”, IEEE TAC 2007

M. Fr ¨anzle, “Analysis of hybrid systems: An ounce of realism can save an infinity of states”, CSL 99

Automi Ibridi

Automi Ibridi

Indice del Corso (Dis)Ordinato

Nella lezione precedente . . .

Warning!

Warning!

Warning!

Warning!

Which is Your Point of View?

Which is Your Point of View?

Example

X = V ˙ V = −g ˙

X ≥ 0 X

= X

V

= −γV

Example

Example

Delta-Notch

Delta-Notch: Single Cell Automaton

Delta-Notch: Two Cells Automaton

Verification

Verification

Bounded Sets and Undecidability

Where is the Problem?

Undecidability in Real Systems

Undecidability in Real Systems

Dense vs Discrete - Intuition

Dense vs Discrete

Finite Precision Semantics

Reachability

A Decidability Result

A Decidability Result

An Instance of -semantics

Conclusions

Why not. . .

Under, Over and Demorgan

References

An Instance of -semantics