Introduction to Formal Methods Chapter 11: Timed and Hybrid Systems

(1)

Introduction to Formal Methods Chapter 11: Timed and Hybrid Systems

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2020/

Teaching assistant:Enrico Magnago– enrico.magnago@unitn.it

CDLM in Informatica, academic year 2019-2020

last update: Sunday 24^thMay, 2020, 20:10

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M.

Di Natale, P. Pandya, M. Pistore, M. Roveri, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be displayed in public

without containing this copyright notice.

Roberto Sebastiani Ch. 11: Timed and Hybrid Systems Sunday 24^thMay, 2020 1 / 100

(2)

Outline

1

Motivations

2

Timed systems: Modeling and Semantics Timed automata

3

Symbolic Reachability for Timed Systems Making the state space finite

Region automata Zone automata

4

Hybrid Systems: Modeling and Semantics Hybrid automata

5

Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata Linear Hybrid Automata

6

Exercises

(3)

Motivations

Acknowledgments

Thanks for providing material to:

Rajeev Alur & colleagues (Penn University) Paritosh Pandya (IIT Bombay)

Andrea Mattioli, Yusi Ramadian (Univ. Trento) Marco Di Natale (Scuola Superiore S.Anna, Italy)

Disclaimer

very introductory very-partial coverage

mostly computer-science centric

(4)

Motivations

Hybrid Modeling

Hybrid machines = State machines + Dynamic Systems

(5)

Motivations

Hybrid Modeling: Examples

Automotive Applications Vehicle Coordination Protocols Interacting Autonomous Robots

Bio-molecular Regulatory Networks

(6)

Timed systems: Modeling and Semantics Timed automata

Timed Automata

(7)

Example: Simple light control

Requirement:

if Off and press is issued once, then the light switches on;

if Off and press is issued twice quickly, then the light gets brighter;

if Light/Bright and press is issued once, then the light switches off;

=⇒ cannot be achieved with standard automata Solution: add real-valued clock x

x reset at first press

if next press before x reaches 3 time units, then the light will get brighter;

otherwise the light is turned off

(8)

Modeling: timing constraints

Finite graph + finite set of (real-valued) clocks

Vertexes are locations Time can elapse there Constraints (invariants) Edges are switches

Subject to constraints Reset clocks

Meaning of clock value: time elapsed since the last time it was reset.

(9)

Timed Automata

Locations l

₁

, l

₂

, ... (like in standard automata) discrete part of the state

may be implemented by discrete variables

Switches (discrete transitions like in standard aut.) Labels, aka events, actions,... (like in standard aut.)

used for synchronization Clocks : x, y,... ∈ Q

⁺

value: time elapsed since the last time it was reset Guards : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N

set of clock comparisons against integers bounds constrain the execution of the switch

Resets (x := 0)

set of clock assignments to 0

Invariants : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

a l1

l2

(x ≥ 4) (y ≤ 2) a

y := 0 l1

l2

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

(10)

Timed Automata: States and Transitions

State: hl

_i

, x

₁

, x

₂

i hl

₁

, 4, 7i: OK!

hl

₂

, 2, 4i: not OK! (violates invariant in l

2

) Switch: hl

_i

, x , y i −→ hl

^a _j

, x

⁰

, y

⁰

i

hl

₁

, 4.5, 2i −→ hl

^a ₂

, 4.5, 0i: OK!

hl

₁

, 6, 2i −→ hl

^a ₂

, 6, 0i: not OK! (violates invar. in l

1

) hl

₁

, 3, 2i −→ hl

^a ₂

, 3, 0i: not OK! (violates guard) hl

₁

, 4.5, 2i −→ hl

^a ₂

, 4.5, 2i: not OK! (violates reset) hl

₁

, 4, 2i −→ hl

^a ₂

, 4, 0i: not OK! (violates invar. in l

₂

) Wait (time elapse): hl

_i

, x , y i −→ hl

^δ _i

, x + δ, y + δi

hl

₁

, 3, 0i −→ hl

² ₁

, 5, 2i: OK!

hl

₁

, 3, 0i −→ hl

³ ₁

, 6, 3i: not OK! (violates invar. in l

1

)

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(11)

Timed Automata: Formal Syntax

Timed Automaton hL, L

⁰

, Σ, X , Φ(X ), E i L: Set of locations

L

⁰

⊆ L: Set of initial locations Σ: Set of labels

X : Set of clocks Φ(X ): Set of invariants

E ⊆ L × Σ × Φ(X ) × 2

^X

× L: Set of switches A switch hl, a, ϕ, λ, l

⁰

i s.t.

l: source location a: label

ϕ: clock constraints λ ⊆ X : clocks to be reset l

⁰

: target location

(x1≥ 4) (x2≤ 2) a

y := 0

L1

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(12)

Clock constraints and clock interpretations

Grammar of clock constraints:

ϕ ::= x ≤ C | x < C | x ≥ C | x > C | ϕ ∧ ϕ s.t. C positive integer values.

=⇒ allow only comparison of a clock with a constant clock interpretation: ν

X = hx , y , zi, ν = h1.0, 1.5, 0i clock interpretation ν after δ time: ν + δ

δ = 0.2, ν + δ = h1.2, 1.7, 0.2i clock interpretation ν after reset λ: ν[λ]

λ = {y }, ν[y := 0] = h1.0, 0, 0i

A state for a timed automaton is a pair hl, νi, where l is a location and ν is a clock interpretation

(x1≥ 4) (x2≤ 2) a

y := 0

L₁

(x1≤ 5)

L2

(x1>4) (x2≤ 3)

(13)

Remark: why integer constants in clock constraints?

The constant in clock constraints are assumed to be integer w.l.o.g.:

if rationals, multiply them for their greatest common denominator, and change the time unit accordingly

in practice, multiply by 10

^k

(resp 2

^k

), k being the number of precision digits (resp. bits), and change the time unit accordingly Ex: 1.345, 0.78, 102.32 seconds

=⇒ 1, 345, 780, 102, 320 milliseconds

(14)

Example

clocks {x , y } can be set/reset independently x is reset to 0 from s

₀

to s

₁

on a

switches b and c happen within 1 time-unit from a because of constraints in s

₁

and s

₂

delay between b and the following d is > 2

no explicit bounds on time difference between event c − d

(15)

Timed Automata: Semantics

Semantics of A defined in terms of a (infinite) transition system S

_A ^def

= hQ, Q

⁰

, →, Σi

Q: {hl, νi} s.t. l location and ν clock evaluation Q

⁰

: {hl, νi} s.t. l ∈ L

⁰

location and ν(X ) = 0

→:

state change due to location switch state change due to time elapse Σ : set of labels of Σ ∪ Q

⁺

(16)

State change in transition system

Initial State hq, 0i Initial state

Time elapse

hq, 0i −→ hq, 1.2i

^1.2

state change due to elapse of time

Time Elapse, Switch and their Concatenation hq, 0i −→ hq, 1.2i

^1.2

−→ hq

^a ⁰

, 1.2i ”wait δ; switch;”

=⇒ hq, 0i

^1.2+a

−→ hq

⁰

, 1.2i ”wait δ and switch;”

(17)

Example

push push

click

Switch may be turned on whenever at least 2 time units has elapsed since last “turn off”

Light automatically switches off after 9 time units.

Example execution

hoff , 0, 0i −→ hoff , 3.5, 3.5i

^3.5

−→ hon, 0, 0i

^push

−→ hon, 3.14, 3.14i

^3.14 ^push

−→

hon, 0, 3.14i −→ hon, 3, 6.14i

³

−→ hon, 5.86, 9i

^2.86

−→ hon, 0, 9i

^click

(18)

Remark: Non-Zenoness

Beware of Zeno! (paradox)

When the invariant is violated some edge must be enabled

Automata should admit the

possibility of time to diverge

(19)

Combination of Timed Automata

Complex system = product of interacting systems Let A

₁^def

= hL

₁

, L

⁰₁

, Σ

₁

, X

₁

, Φ

₁

(X

₁

), E

₁

i,

A

₂^def

= hL

₂

, L

⁰₂

, Σ

2

, X

₂

, Φ

2

(X

₂

), E

₂

i Product: A

₁

||A

2

def

=

hL

₁

× L

₂

, L

⁰₁

× L

⁰₂

, Σ

₁

∪ Σ

₂

, X

₁

∪ X

₂

, Φ

₁

(X

₁

) ∪ Φ

₂

(X

₂

), E

₁

||E

₂

i Transition iff:

Label a belongs to both alphabets =⇒ synchronized

blocking synchronization: a-labeled switches cannot be shot alone Label a only in the alphabet of A

1

=⇒ asynchronized

Label a only in the alphabet of A

2

=⇒ asynchronized

(20)

Transition Product

Σ

1

def

= {a, b}

Σ

₂^def

= {a, c}

(21)

Transition Product: Example

(22)

Example: Train-gate controller [Alur CAV’99]

Desired property: G(s

₂

→ t

₂

)

(23)

Train-gate controller: Product

(24)

Symbolic Reachability for Timed Systems Making the state space finite

Reachability Analysis

Verification of safety requirement: reachability problem

Input: a timed automaton A and a set of target locations L

^F

⊆ L Problem: Determining whether L

^F

is reachable in a timed automaton A

A location l of A is reachable if some state q with location

component l is a reachable state of the transition system S

_A

(25)

Timed/hybrid Systems: problem

Problem

The system S

_A

associated to A has infinitely-many states & symbols.

Is finite state analysis possible?

Is reachability problem decidable?

(26)

Idea: Finite Partitioning

Goal

Partition the state space into finitely-many equivalence classes, so that

equivalent states exhibit (bi)similar behaviors

(27)

Reachability analysis

(28)

Timed Vs Time-Abstract Relations

Idea

Infinite transition system associated with a timed/hybrid automaton A:

S

_A

: Labels on continuous steps are delays in Q

⁺

U

_A

(time-abstract): actual delays are suppressed

=⇒ all continuous steps have same label

from ”wait δ and switch” to ”wait (sometime) and switch”

(29)

Time-abstract transition system U A

U

_A

(time-abstract): actual delays are suppressed Only change due to location switch stated explicitly Cut system to finitely many labels

U

_A

(instead of S

_A

) allows for capturing untimed properties (e.g., reachability, safety)

A: (“wait δ; switch;”)

hl

₀

, 0, 0i −→ hl

^1.2 ₀

, 1.2, 1.2i −→ hl

^a ₁

, 0, 1.2i −→ hl

^0.7 ₁

, 0.7, 1.9i −→ hl

^b ₂

, 0.7, 0i S

_A

: (“wait δ and switch;”)

hl

₀

, 0, 0i

^1.2+a

−→ hl

₁

, 0, 1.2i

^0.7+b

−→ hl

₂

, 0.7, 0i U

_A

: (“wait (sometime) and switch;”) hl

0

, 0, 0i −→ hl

^a 1

, 0, 1.2i −→ hl

^b 2

, 0.7, 0i

(30)

Stable quotients

Idea: Collapse states which are equivalent modulo “wait & switch”

Cut to finitely many states Stable equivalence relation

Quotient of U

_A

= transition system [U

_A

]

(31)

L ^F -sensitive equivalence relation

All equivalent states in a class belong to either L

^F

or not L

^F

E.g.: states with different labels cannot be equivalent

(32)

Stable Quotient: Intuitive example

Task: plan trip from DISI to VR train station

“take the next #5 bus to TN train station and then the 6pm train to VR”

Constraints:

It is 5.18pm

Train to VR leaves at TN train station at 6.00pm it takes 3 minutes to walk from DISI to BUS stop Bus #5 passes 5.20pm or at 5.40pm

Bus #5 takes 15 minutes to TN train station

it takes 2 minutes to walk from BUS stop to TN train station Time-Abstract plan (U

A

):

“walk to bus stop; take 5.40 #5 bus to TN train-station stop;

walk to train station; take the 6pm train to VR”

Actual (implicit) plan (A):

“wait δ

1

; walk to bus stop; wait δ

2

; take 5.40 #5 bus to TN train-station stop;

wait δ

3

at bus stop; walk to train station; wait δ

4

; take the 6pm train to VR”

where δ

1

+ δ

2

= 19min and δ

3

+ δ

4

= 3min

all executions with distinct values of δiare bisimilar

(33)

Symbolic Reachability for Timed Systems Region automata

Region Equivalence over clock interpretation

Preliminary definitions & terminology Given a clock x :

bxc is the integral part of x (ex: b3.7c = 3) fr(x) is the fractional part of x (ex: fr(3.7) = 0.7)

C

x

is the maximum constant occurring in clock constraints x ./ C

x

Region Equivalence: ν ∼ = ν

⁰

Given a timed automaton A, two clock interpretations ν, ν

⁰

are region equivalent (ν ∼ = ν

⁰

) iff all the following conditions hold:

C1: For every clock x , either bν(x)c = bν

⁰

(x )c or bν(x)c, bν

⁰

(x )c ≥ C

_x

C2: For every clock pair x , y s.t. ν(x ), ν

⁰

(x ) ≤ C

x

and ν(y ), ν

⁰

(y ) ≤ C

y

,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν

⁰

(x)) ≤ fr(ν

⁰

(y)) C3: For every clock x s.t. ν(x ), ν

⁰

(x ) ≤ C

x

fr(ν(x)) = 0 iff fr(ν

⁰

(x)) = 0

(34)

Conditions: C1 + C2 + C3

Cx

x y

Cy

1 2 3 4

1 2 3

0

C_x

x y

C_y

1 2 3 4

1 2 3

0

C_x

x y

C_y

1 2 3 4

1 2 3

0

Cx

x y

Cy

1 2 3 4

1 2 3

0

C1:

For every clock x , either

bν(x)c = bν⁰(x )c

or

bν(x)c, bν⁰(x )c ≥ Cx

C2:

For every clock pair x , y s.t. ν(x ), ν

⁰

(x ) ≤ C

x

and ν(y ), ν

⁰

(y ) ≤ C

y

,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν⁰(x)) ≤ fr(ν⁰(y))

C3:

For every clock x s.t. ν(x ), ν

⁰

(x ) ≤ C ,

fr(ν(x)) = 0 iff fr(ν⁰(x)) = 0

(35)

Regions, intuitive idea:

C_x

x y

C_y

1 2 3 4

1 2 3

0

Intuition: ν ∼ = ν

⁰

iff they satisfy the same set of constraints in the form x

_i

< c, x

_i

> c, x

_i

= c, x

_i

− x

j

< c, x

_i

− x

j

> c, x

_i

− x

j

= c s.t. c ≤ C

_x_i

(36)

Region Operations

(37)

Properties of Regions

The region equivalence relation ∼ = is a time-abstract bisimulation:

Action transitions: if ν ∼ = µ and hl, νi −→ hl

^a ⁰

, ν

⁰

i for some l

⁰

, ν

⁰

, then there exists µ

⁰

s.t. ν

⁰

∼ = µ

⁰

and hl, µi −→ hl

^a ⁰

, µ

⁰

i

Wait transitions: if ν ∼ = µ,

then for every δ ∈ Q

⁺

there exists δ

⁰

∈ Q

⁺

s.t. ν + δ ∼ = µ + δ

⁰

=⇒ If ν ∼ = µ, then hl, νi and hl, µi satisfy the same temporal-logic formulas

(38)

Time-abstract Bisimulation in Regions

C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

_x

x y

C

_y

1 2 3 4

1 2 3

0 C

x y

C

_y

1 2 3 4

1 2 3

0

(39)

Number of Clock Regions

Clock region: equivalence class of clock interpretations Number of clock regions upper-bounded by

k ! · 2

^k

· Π

_{x ∈X}

(2 · C

_x

+ 2), s.t. k

^def

= ||X ||

finite!

exponential in the number of clocks grows with the values of C

_x

Example

2 clocks x,y, C

x

= 2, C

y

= 1 8 open regions

14 open line segments 6 corner points

=⇒ 28 regions

< 2 · 2

²

· (2 · 2 + 2) · (2 · 1 + 2) = 192

(40)

Region automaton

Equivalent states = identical location + ∼ =-equivalent evaluations Equivalent Classes (regions): finite, stable, L

^F

-sensitive

R(A): Region automaton of A

States: hl, r (A)i s.t. r (A) regions of A

=⇒ Finite state automaton!

Reachability problem hA, L

^F

i =⇒ Reachability problem hR(A), L

^F

i

=⇒ Reachability in timed automata reduced to that in finite automata!

(41)

Example: Region graph of a simple timed automata

May be further reduced (e.g., collapsing B, C, D into one state)

(42)

Complexity of Reasoning with Timed Automata

Reachability in Timed Automata Decidable!

Linear with number of locations Exponential in the number of clocks Grows with the values of C

x

Overall, PSPACE-Complete

Language-containment with Timed Automata

Undecidable!

(43)

Symbolic Reachability for Timed Systems Zone automata

Zone Automata

Collapse regions by convex unions of clock regions

Clock Zone ϕ: set/conjunction of clock constraints in the form (x

_i

./ c), (x

_i

− x

_j

./ c) , ./ ∈ {>, <, =, ≥, ≤}, c ∈ Z

ϕ is a convex set in the k-dimensional euclidean space possibly unbounded

=⇒ Contains all possible relationship for all clock value in a set Symbolic state: hl, ϕi

l: location ϕ: clock zone

x y

(44)

Zone Automata

Definition: Zone Automaton

Given a Timed Automaton A

^def

= hL, L

⁰

, Σ, X , Φ(X ), E i,

the Zone Automaton Z(A) is a transition system hQ, Q

⁰

, Σ, →i s.t.

Q: set of all zones of A (a zone is hl, ϕi) Q

⁰^def

= {hl, [X := 0]i | l ∈ L

⁰

}

Σ: set of labels/events in A

→: set of “wait&switch” symbolic transitions, in the form:

hl, ϕi −→ hl

^a ⁰

, succ(ϕ, e)i

succ(ϕ, e): successor of ϕ after (waiting and) executing the switch e

succ(hl, ϕi, e)

^def

= hl

⁰

, succ(ϕ, e)i

(45)

Zone Automata: Symbolic Transitions

Definition: succ(ϕ, e)

Let e

^def

= hl, a, ψ, λ, l

⁰

i, and φ, φ

⁰

the invariants in l, l

⁰

Then

succ(ϕ, e)

^def

= (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

∧: standard conjunction/intersection

⇑: projection to infinity: ψ⇑

^def

= {ν + δ | ν ∈ ψ, δ ∈ [0, +∞)}

[λ := 0]: reset projection: ψ[λ := 0]

^def

= {ν[λ := 0] | ν ∈ ψ}

note: ϕ is considered “immediately before entering l”

(46)

Zone Automata: Symbolic Transitions (cont.)

Initial zone: values before entering the location

Intersection with invariant φ: values allowed to

enter the location

Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed to

enter the location, after waiting a legal amount of time

Intersection with guard ψ: values allowed to

enter the location, after waiting a legal amount of time, from which the switch can be shot

Reset projection λ: values ..., after reset

=⇒ Final!

ϕ

ϕ φ

φ

ψ

succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ) ⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]succ(ϕ, e) =

^def

(((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

(47)

Example: Zone Automata, Symbolic Transitions

Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

(y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

=⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Reset projection λ

^def

= {y := 0}

=⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

ϕ

ϕ φ

φ

ψ

(48)

Remark on succ(ϕ, e)

In the above definition of succ(ϕ, e), ϕ is considered “immediately before entering l”:

succ(ϕ, e)

^def

= (((ϕ ∧ φ)⇑ ∧φ) ∧ ψ)[λ := 0]

Alternative definition of succ(ϕ, e), ϕ is considered “immediately after entering l”:

succ(ϕ, e)

^def

= (((ϕ⇑ ∧φ) ∧ ψ)[λ := 0] ∧ φ

⁰

)

no initial intersection with the invariant φ of source location l

(here ϕ is assumed to be already the result of such intersection)

final intersection with the invariant φ

⁰

of target location l

⁰

(49)

Symbolic Reachability Analysis

1: function Reachable (A, L

^F

) // A

^def

= hL, L

⁰

, Σ, X , Φ(X ), E i

2: Reachable = ∅

3: Frontier = {hl

_i

, {X = 0}i | l

_i

∈ L

⁰

}

4: while (Frontier 6= ∅) do

5: extract hl, ϕi from Frontier

6: if (l ∈ L

^F

and ϕ 6= ⊥) then

7: return True

8: end if

9: if (6 ∃ hl, ϕ

⁰

i ∈ Reachable s.t. ϕ ⊆ ϕ

⁰

) then

10: add hl, ϕi to Reachable

11: for e ∈ outcoming(l) do

12: add succ(ϕ, e) to Frontier

13: end for

14: end if

15: end while

16: return False

(50)

Canonical Data-structures for Zones: DBMs

Difference-bound Matrices (DBMs) Matrix representation of constraints

bounds on a single clock differences between 2 clocks

Reduced form computed by all-pairs shortest path algorithm (e.g. Floyd-Warshall)

Reduced DBM is canonical:

equivalent sets of constraints produce the same reduced DBM Operations s.a reset, time-successor, inclusion, intersection are efficient

=⇒ Popular choice in timed-automata-based tools

(51)

Difference-bound matrices, DBMs

DBM: matrix (k + 1) × (k + 1), k being the number of clocks added an implicit fake variable x

0

def

= 0 s.t. x

i

./ c =⇒ x

i

− x

₀

./ c each element is a pair (value,{0, 1}), s.t “{0, 1}” means “{<, ≤}”

Example:

(0 ≤ x

1

) ∧(0 < x

2

) ∧(x

1

< 2) ∧(x

2

< 1) ∧(x

1

− x

2

≥ 0) (x

0

− x

1

≤ 0) ∧(x

0

− x

2

< 0) ∧(x

1

− x

0

< 2) ∧(x

2

− x

0

< 1) ∧(x

2

− x

1

≤ 0)

(52)

Difference-bound matrices, DBMs (cont.)

Use all-pairs shortest paths, check DBM

idea: given x

_i

− x

_j

./ c, x

_i

− x

_k

./ c

₁

and x

_k

− x

_j

./ c

₂

s.t. ./∈ {≤, <}, then c is updated with c

₁

+ c

₂

if c

₁

+ c

₂

< c

Satisfiable (no negative loops) =⇒ a non-empty clock zone Canonical: Matrices with tightest possible constraints Canonical DBMs represent clock zones:

equivalent sets of constraints ⇐⇒ same reduced DBM

(53)

Canonical Data-structures for Zones: DBMs

(54)

Complexity Issues

In theory:

Zone automaton might be exponentially bigger than the region automaton

In practice:

Fewer reachable vertices =⇒ performances much improved

(55)

Timed Automata: summary

Only continuous variables are timers

Invariants and Guards: x ./ const, ./∈ {<, >, ≤, ≥}

Actions: x:=0

Reachability is decidable

Clustering of regions into zones desirable in practice Tools: Uppaal, Kronos, RED ...

Symbolic representation: matrices

(56)

Decidable Problems with Timed Automata

Model checking branching-time properties of timed automata Reachability in rectangular automata

Timed bisimilarity: are two given timed automata bisimilar?

Optimization: Compute shortest paths (e.g. minimum time

reachability) in timed automata with costs on locations and edges

Controller synthesis: Computing winning strategies in timed

automata with controllable and uncontrollable transitions

(57)

Hybrid Systems: Modeling and Semantics Hybrid automata

Hybrid Automata

(58)

Hybrid Automata

Locations, Switches, Labels (like in standard aut.) Continuous variables: X

^def

= {x

₁

, x

₂

, ..., x

_k

} ∈ R

value evolves with time

e.g., distance, speed, pressure, temperature, ...

Guards: g(X ) ≥ 0

sets of inequalities (equalities) on functions on X constrain the execution of the switch

Jump Transformations J(X , X

⁰

)

discrete transformation on the values of X Invariants: X ∈ Inv

_l

(X )

set of invariant constraints on X ensure progress

Continuous Flow:

^dX_dt

∈ flow

_l

(X )

set of degree-1 differential (in)equalities describe continuous dynamics

Initial: X ∈ Init

_l

(X )

initial conditions (X ∈ Init

_l

(X ) = ⊥ if l 6∈ L

⁰

)

a

l2

l1

a

l2

l1

g(X ) ≥ 0 a

l2

l1

g(X ) ≥ 0 a

J(X , X⁰) l2

l1

g(X ) ≥ 0 a

J(X , X⁰) l2

X ∈ Invl₂(X) l1

X ∈ Invl1(X)

g(X ) ≥ 0 a

J(X , X⁰)

l2

dX

dt∈flowl1(X ) X ∈ Invl2(X)

l1

dX

dt∈flowl₁(X ) X ∈ Invl₁(X)

g(X ) ≥ 0 a

J(X , X⁰)

l2

X ∈ Initl2(X )

dX

dt∈flowl₁(X ) X ∈ Inv (X)

l1

X ∈ Initl₁(X )

dX

dt∈flow_l₁(X ) X ∈ Invl1(X)

(59)

Hybrid Automata A = hL, L ⁰ , X , Σ, Φ(X ), E i

L: Set of locations,

L

⁰

∈ L: Set of initial locations X : Set of k continuous variables Φ(X ): Set of Constraints on X

Σ: Set of synchronization labels (alphabet) E: Set of edges

State space: L × R

^k

,

state : hl, ψi s.t. l ∈ L and ψ ∈ R

^k

region ψ : subset of R

^k

For each location l:

Initial states: region Init

_l

(X ) Invariant: region Inv

_l

( X)

Continuous dynamics:

^dX_dt

∈ flow

_l

(X ) For each edge e from location l to location l

⁰

Guard: region g(X ) ≥ 0

Update relation “Jump” J(X , X

⁰

) over R

^k

× R

^k

Synchronization label a ∈ Σ (communication information)

(60)

Remark: Degree of flow l (X )

Continuous dynamics described w.l.o.g. with sets of degree-1 differential (in)equalities flow

_l

(X )

Sets/conjunctions of higher-degree differential (in)equalities can be reduced to degree 1 by renaming

Ex:

(a

₁^d_dt²₂^s

+ a

₂^ds_dt

+ a

₃

s + a

₄

./ 0)

⇓

(v =

^ds_dt

) ∧ (a

₁^dv_dt

+ a

₂

v + a

₃

s + a

₄

./ 0)

(61)

(Finite) Executions of Hybrid Automata

State: pair hl, X i such that X ∈ Inv

_l

( X) Initialization: hl, X i such that X ∈ Init

_l

(X ) Two types of state updates (transitions)

Discrete switches: hl, X i −→ hl

^a ⁰

, X

⁰

i

if there there is an a-labeled edge e from l to l

⁰

s.t.

X , X

⁰

satisfy Inv

l

( X) and Inv

l⁰

( X) respectively X satisfies the guard of e (i.e.

g(X ) ≥ 0) and

hX , X

⁰

i satisfies the jump condition of e (i.e.,

hX , X⁰i ∈ J(X , X⁰))

Continuous flows: hl, X i −→ hl, X

^f ⁰

i

f is a continuous function in [0, δ] s.t.

f (0) = X f (δ) = X⁰

for every t ∈ [0, δ], f (t) ∈ Invl(X) for every t ∈ [0, δ], ^{df (t)}_dt ∈ flowl(X )

(62)

Example: Gate for a railroad controller

Notation: “dh” shortcut for “

^dh_dt

”

(63)

Example: Gate for a railroad controller

10 20 30

90 h

0 t

lowering

Open closed lowering raising Open

?lower ?lower ?raise?raise

raising Open

(64)

Symbolic Reachability for Hybrid Systems

General Symbolic-Reachability Schema

1: R = I(X)

2: while (True) do

3: if (R intersects F) then

4: return True

5: else

6: if (Image(R) ⊆ R) then

7: return False

8: else

9: R = R ∪ Image(R)

10: end if

11: end if

12: end while

I: initial; F: Final; R: Reachable; Image(R): successors of R need a data type to representt state sets (regions)

Termination may or may not be guaranteed

(65)

Symbolic Representations

Necessary operations on Regions Union

Intersection Negation Projection Renaming

Equality/containment test Emptiness test

Different choices for different classes of problems BDDs for Boolean variables in hardware verification DBMs in Timed automata

Polyhedra in Linear Hybrid Automata ...

(66)

Reachability for Hybrid Systems

Same algorithm works in principle

Problem: What is a suitable representation of regions?

Region: subset of R

^k

Main problem: handling continuous dynamics

Precise solutions available for restricted continuous dynamics Timed automata

Multi-rate & Rectangular Hybrid Automata (reduced to Timed aut.) Linear Hybrid Automata

Even for linear systems, over-approximations of reachable set

needed

(67)

Reachability Analysis for Dynamical Systems

Goal: Given an initial region, compute whether a bad state can be reached

Key step: compute Reach(X) for a given set X under

^dX_dt

= f (X )

Notation: (hereafter we often use “dX ” or “ ˙ X ” as a shortcut of “

^dX_dt

”

(68)

Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata

Simple Hybrid Automata: Multi-Rate and Rectangular

Two simple forms of Hybrid Automata Multi-Rate Automata

Rectangular Automata

Idea: can be reduced to Timed Automata

typically used as over-approximations of complex hybrid automata

(69)

Multi-rate Automata

Modest extension of timed automata Dynamics of the form

^dX_dt

= const

s.t. the rate of of each variable is the same in all locations Guards and invariants: x < const, x > const

Resets: x := const

Simple translation to timed automata by shifting and scaling:

if x

i

:= d

i

then rename it with a fresh var v

i

s.t. v

i

+ d

i

= x

i

if

^dx_dtⁱ

= c

i

, then rename it with a fresh var u

i

s.t. c

i

· u

_i

= x

i

shift & rescale constants in constraints accordingly

(70)

Rectangular Automata (simplified)

More interesting extension of timed automata Dynamics of the form

^dX_dt

∈ [const1, const2]

s.t. the rate of each variable is the same in all locations Guards and invariants: x < const, x > const

Jumps: x := const

Translation to multi-rate automata (hints). For each x :

Introduce x

_M

, x

_m

describing the greatest/least possible x values flow: substitute ˙x < c

_u

with ˙x

_M

= c

_u

and ˙x > c

_l

with ˙x

_m

= c

_l

invariants: substitute Inv

_l

(x ) with Inv

_l

(x

_M

), Inv

_l

(x

m

)

guards: substitute x > c with x

M

> c , add jump x

m

:= c (if none)

guards: substitute x < c with x

m

< c, add jump x

M

:= c (if none)

jump: if x := c, then both x

M

:= c and x

m

:= c

(71)

Symbolic Reachability for Hybrid Systems Linear Hybrid Automata

Linear Hybrid Automata

Polyhedron ϕ: set/conjunction of linear inequalities on X in the form (A · X ≥ B) , s.t. A ∈ R

^m

× R

^k

and B ∈ R

^m

for some m.

ϕ is a convex set in the k-dimensional euclidean space possibly unbounded

=⇒ Contains all possible values for all variables in a set Symbolic state: hl, ϕi

l: location ϕ: polyhedron

(generalization of zone automata)

x y

(72)

Linear Hybrid Automata A = hL, L ⁰ , X , Σ, Φ(X ), E i

State space: L × R

^k

,

state : hl, ψi s.t. l ∈ L and ψ ∈ R

^k

polyhedron ψ : subset of R

^k

in the form A · X ≥ B For each edge e from location l to location l

⁰

Guard: region (A · X ≥ B): polyhedron on X

Update relation “Jump” J(X , X

⁰

): X

⁰

:= T · X , T ∈ R

^k

× R

^k

Synchronization label a ∈ Σ (communication information) For each location l:

Initial states: region Init

l

(X ): polyhedron on X Invariant: region Inv

_l

( X): polyhedron on X

Continuous dynamics flow

_l

(X ): polyhedron on

^dX_dt

Continuous Dynamics

Time-invariant, state-independent dynamics specified by a convex polyhedron constraining first derivatives

Es:

^dx_dt

≥ 3,

^dx_dt

=

^dy_dt

, 2.1

^dx_dt

− 3.5

^dy_dt

+ 1.7

^dz_dt

≥ 3.1, ...

(73)

Example: Gate for a railroad controller

(74)

Reachability Computation: Key Steps

Compute “discrete” successors of hl, ψi Compute “continuous” successor of hl, ψi Check if ψ intersects with “bad” region

Check if newly found ψ is covered by already visited polyhedra

ψ

₁

, ..., ψ

n

(expensive!)

(75)

Computing Discrete Successors of hl, ψi

Intersect ψ with the guard φ

=⇒ result is a polyhedron

Apply linear transformation of J to the result

=⇒ result is a polyhedron

Intersect with the invariant of target location l

⁰

=⇒ result is a polyhedron

(76)

Computing Time Successor

Consider maximum and minimum rates between derivatives (external vertices in the flow polyhedron)

Apply these extremal rates for computing the projection to infinity (to be intersected with invariant)

Hint:

^dx_dy

=

^dx_dy^dt

dt

, s.t. max

_{x ,y}^dx_dy

= max

_{x ,y}^dxdy^dt dt

and min

_{x ,y}^dx_dy

= min

_{x ,y} ^dxdy^dt dt

dy/dt

dx/dt (1,4)

(3,2)

x y

min dy/dx = 2/3 max dy/dx = 4

x y

(77)

Linear Hybrid Automata: Symbolic Transitions

Definition: succ(ϕ, e)

Let e

^def

= hl, a, ψ, J, l

⁰

i, and φ, φ

⁰

the invariants in l, l

⁰

Then

succ(ϕ, e)

^def

= J(((ϕ∧φ)⇑ ∧φ) ∧ ψ) (ϕ immediately before entering the location)

succ(ϕ, e)

^def

= J((ϕ⇑ ∧φ) ∧ ψ) ∧ φ

⁰

(ϕ immediately after entering the location):

∧: standard conjunction/intersection

⇑: continuous successor ψ⇑

J: Jump transformation J(X )

^def

= T · X

note: ϕ is considered “immediately after entering l”

(78)

Linear Hybrid Automata: Symbolic Transitions (cont.)

Initial zone: values allowed to enter location l

Projection to infinity: ... after waiting unbounded time Intersection with invariant φ: ...

waiting a legal amount of time Intersection with guard ψ: ... from which the switch can be shot Jump J: ..., after jump

Intersection with invariant φ

⁰

: ...

values allowed to enter location l

⁰

=⇒ Final!

x y

φ

x y

ψ

x y

φ’

x y

succ(ϕ, e) =

^def

J((ϕ⇑ ∧φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J ((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J ((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰ succ(ϕ, e) =

^def

J((ϕ⇑ ∧ φ) ∧ ψ) ∧ φ ⁰

(79)

Symbolic Reachability Analysis

1: function Reachable (A, F ) // A

^def

= hL,L

⁰

,Σ,X ,Φ(X ),E i, F

^def

= {hl

_i

, φ

_i

i}

_i

2: Reachable = ∅

3: Frontier = {hl, Init

_l

(X )i | l ∈ L

⁰

}

4: while (Frontier 6= ∅) do

5: extract hl, ϕi from Frontier

6: if ((ϕ ∧ φ) 6= ⊥ for some hl, φi ∈ F ) then

7: return True

8: end if

9: if (6 ∃ hl, ϕ

⁰

i ∈ Reachable s.t. ϕ ⊆ ϕ

⁰

) then

10: add hl, ϕi to Reachable

11: for e ∈ outcoming(l) do

12: add succ(ϕ, e) to Frontier

13: end for

14: end if

15: end while

16: return False

(80)