APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL
APPROACH

arXiv:1508.06496v2 [math.OC] 24 Apr 2016

MAJID ZAMANI1 , MATTHIAS RUNGGER1 , AND PEYMAN MOHAJERIN ESFAHANI2

Abstract. In this paper we propose a compositional framework for the construction of approximations of
the interconnection of a class of stochastic hybrid systems. As special cases, this class of systems includes
both jump linear stochastic systems and linear stochastic hybrid automata. In the proposed framework,
an approximation is itself a stochastic hybrid system, which can be used as a replacement of the original
stochastic hybrid system in a controller design process. We employ a notion of so-called stochastic simulation
function to quantify the error between the approximation and the original system. In the first part of the
paper, we derive sufficient conditions which facilitate the compositional quantification of the error between the
interconnection of stochastic hybrid subsystems and that of their approximations using the quantified error
between the stochastic hybrid subsystems and their corresponding approximations. In particular, we show how
to construct stochastic simulation functions for approximations of interconnected stochastic hybrid systems
using the stochastic simulation function for the approximation of each component. In the second part of the
paper, we focus on a specific class of stochastic hybrid systems, namely, jump linear stochastic systems, and
propose a constructive scheme to determine approximations together with their stochastic simulation functions
for this class of systems. Finally, we illustrate the effectiveness of the proposed results by constructing an
approximation of the interconnection of four jump linear stochastic subsystems in a compositional way.

1. Introduction
Stochastic hybrid systems are a general class of dynamical systems consisting of continuous and discrete
dynamics subject to probabilistic noise and events. In the past few years, this class of systems has become
ubiquitous in many different fields due to the need for a rigorous modeling framework for many safetycritical applications. Examples of those applications include air traffic control [GL04], biochemistry [SH10],
communication networks [Hes04], and systems biology [HWS04]. The design of controllers to enforce certain
given complex specifications, e.g. those expressed via formulae in linear temporal logic (LTL) [BK08], in a
reliable and cost effective way is a grand challenge in the study of many of those safety-critical applications.
One promising direction to achieve those objectives is the use of simpler (in)finite approximations of the given
systems as a replacement in the controller design process. Those approximations allow us to design controllers
for them and then refine the controllers to the ones for the concrete complex systems, while provide us with
the quantified errors in this detour controller synthesis scheme.
In the past few years there have been several results on the (in)finite approximations of continuous-time
stochastic (hybrid) systems. Existing results include the construction of finite approximations for stochastic
dynamical systems under contractivity assumptions [Aba09], restricted to models with no control inputs, a
finite Markov decision process approximation of a linear stochastic control system [LAB09], however without
a quantitative relationship between approximation and concrete model, and the construction of finite bisimilar
abstractions for stochastic control systems [ZMM+ 14, ZTA14], for stochastic switched systems [ZAG15], for
randomly switched stochastic systems [ZA14], and the construction of sound finite abstractions for stochastic
control systems without any stability property [ZMAL12]. Further, the results in [JP09] check the relationship
between infinite approximations and a given class of stochastic hybrid systems via a notion of stochastic
(bi)simulation functions. However, the results in [JP09] do not provide any approximations and moreover
appear to be computationally intractable in the case of systems with inputs because one requires to solve a game
in order to quantify the approximation error. Note that all the proposed results in [Aba09, LAB09, ZMM+ 14,
1

2

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

ZTA14, ZAG15, ZA14, ZMAL12, JP09] take a monolithic view of continuous-time stochastic (hybrid) systems,
where the entire system is approximated. This monolithic view interacts badly with the construction of
approximations, whose complexity grows (possibly exponentially) in the number of continuous state variables
in the model.
In this paper, we provide a compositional framework for the construction of infinite approximations of the
interconnection of a class of stochastic hybrid systems, in which the continuous dynamics are modeled by
stochastic differential equations and the switches are modeled as Poisson processes. As special cases, this
class of systems includes both jump linear stochastic systems (JLSS) and linear stochastic hybrid automata
[JP09]. Our approximation framework is based on a new notion of stochastic simulation functions. In this
framework, an approximation, which is itself a stochastic hybrid system (potentially with lower dimension
and simpler interconnection topology), acts as a substitute in the controller design process. The stochastic
simulation function is used to quantify the error in this detour controller synthesis scheme. Although an
approximation in our framework might not be directly amenable to algorithmic synthesis methods based
on automata-theoretic concepts [MPS95] which require finite approximations, our approach facilitates the
construction of potentially lower-dimensional less-interconnected stochastic hybrid systems as approximations
and, hence, can be interpreted as the first pre-processing step in the construction of a finite approximation.
In the first part of the paper, we derive sufficient small-gain type conditions, similar to the ones in [DIW11],
under which one can quantify the error between the interconnection of stochastic hybrid subsystems and that
of their approximations in a compositional way by using the errors between stochastic hybrid subsystems
and their approximations. In the second part of the paper, we focus on JLSS and propose a computational
scheme to construct infinite approximations of this class of systems, together with the corresponding stochastic
simulation functions. To show the effectiveness of the proposed results, we construct an approximation (two
disjoint 3 dimensional JLSS) of the interconnection of four JLSS (overall 10 dimensions) in a compositional
way and then use the approximation in order to design a safety controller for the original interconnected
system. Note that the controller synthesis would not have been possible without the use of the approximation.
The recent work in [RZ15] provides a compositional scheme for the construction of infinite approximations
of interconnected deterministic control systems without any hybrid dynamic. The results in this paper are
complementary to the ones in [RZ15] as we extend our focus to the class of stochastic hybrid systems. A
preliminary investigation of our results on the compositional construction of infinite approximations of interconnected stochastic hybrid systems appeared in [Zam14]. In this paper we present a detailed and mature
description of the results announced in [Zam14], including proposing a new notion of stochastic simulation
functions which is computationally more tractable in the case of systems with inputs and providing constructive
means to compute approximations of JLSS.
2. Stochastic Hybrid Systems
2.1. Notation. We denote by N the set of nonnegative integer numbers and by R the set of real numbers. We
annotate those symbols with subscripts to restrict them in the obvious way, e.g. R>0 denotes the positive real
numbers. The symbols In , 0n , and 0n×m denote the identity matrix, zero vector, and zero matrix in Rn×n ,
Rn , and Rn×m , respectively. For a, b ∈ R with a ≤ b, we denote the closed, open, and half-open intervals in
R by [a, b], ]a, b[, [a, b[, and ]a, b], respectively. For a, b ∈ N and a ≤ b, we use [a; b], ]a; b[, [a; b[, and ]a; b] to
denote the corresponding intervals in N. Given N ∈ N≥1 , vectors xi ∈ Rni , ni ∈ N≥1 and i ∈ [1; N ], we use
PN
x = [x1 ; . . . ; xN ] to denote the vector in Rn with n = i=1 ni . Similarly, we use X = [X1 ; . . . ; XN ] to denote
PN
the matrix in Rn×m with n = i=1 ni , given N ∈ N≥1 , matrices Xi ∈ Rni ×m , ni ∈ N≥1 , and i ∈ [1; N ]. Given
a vector x ∈ Rn , we denote by kxk the Euclidean norm of x. The distance of a point x ∈ Rn to aP
set D ⊆ Rn
n
n×n
is defined as kxkD = inf d∈D kx − dk. Given a matrix P = {pij } ∈ R
, we denote by Tr(P ) = i=1 pii the
trace of P .
Given a function f : Rn → Rm and x̄ ∈ Rm , we use f ≡ x̄ to denote that f (x) = x̄ for all x ∈ Rn . If x is the
zero vector, we simply write f ≡ 0. Given a function f : R≥0 → Rn , the (essential) supremum of f is denoted

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

3

by kf k∞ := (ess)sup{kf (t)k, t ≥ 0}. Measurability throughout this paper refers to Borel measurability. A
continuous function γ : R≥0 → R≥0 , is said to belong to class K if it is strictly increasing and γ(0) = 0; γ is
said to belong to class K∞ if γ ∈ K and γ(r) → ∞ as r → ∞. A continuous function β : R≥0 × R≥0 → R≥0
is said to belong to class KL if, for each fixed t, the map β(r, t) belongs to class K with respect to r and, for
each fixed nonzero r, the map β(r, t) is decreasing with respect to t and β(r, t) → 0 as t → ∞.
2.2. Stochastic hybrid systems. Let (Ω, F, P) be a probability space endowed with a filtration F = (Fs )s≥0
satisfying the usual conditions of completeness and right continuity [KS91, p. 48]. Let (Ws )s≥0 be a pedimensional F-Brownian motion and (Ps )s≥0 be a qe-dimensional F-Poisson process. We assume that
 the Pois-
son process and the Brownian motion are independent of each other. The Poisson process Ps := Ps1 ; . . . ; Psqe
model qe kinds of events whose occurrences are assumed to be independent of each other.
Definition 2.1. The class of stochastic hybrid systems with which we deal in this paper is the tuple Σ =
(Rn , Rm , Rp , U, W, f, σ, r, Rq , h), where Rn , Rm , Rp , and Rq are the state, external input, internal input, and
output spaces, respectively, and
• U is a subset of the set of all F-progressively measurable processes with values in Rm ; see [KS91, Def.
1.11];
• W is a subset of the set of all F-progressively measurable processes with values in Rp ;
• f : Rn × Rm × Rp → Rn is the drift term which is globally Lipschitz continuous: there exist constants
Lx , Lu , Lw ∈ R≥0 such that: kf (x, u, w) − f (x0 , u0 , w0 )k ≤ Lx kx − x0 k + Lu ku − u0 k + Lw kw − w0 k for all
x, x0 ∈ Rn , all u, u0 ∈ Rm , and all w, w0 ∈ Rp ;
• σ : Rn → Rn×ep is the diffusion term which is globally Lipschitz continuous;
• r : Rn → Rn×eq is the reset function which is globally Lipschitz continuous;
• h : Rn → Rq is the output map.
A stochastic hybrid system Σ satisfies

d ξ(t) = f (ξ(t), ν(t), ω(t)) d t + σ(ξ(t)) d Wt + r(ξ(t)) d Pt ,
Σ:
ζ(t) = h(ξ(t)),

(2.1)

P-almost surely (P-a.s.) for any ν ∈ U and any ω ∈ W, where stochastic process ξ : Ω × R≥0 → Rn is called
a solution process of Σ and stochastic process ζ : Ω × R≥0 → Rq is called an output trajectory of Σ. We call
the tuple (ξ, ζ, ν, ω) a trajectory of Σ, consisting of a solution process ξ, an output trajectory ζ, and input
trajectories ν and ω, that satisfies (2.1) P-a.s.. We also write ξaνω (t) to denote the value of the solution
process at time t ∈ R≥0 under the input trajectories ν and ω from initial condition ξaνω (0) = a P-a.s., in
which a is a random variable that is F0 -measurable. We denote by ζaνω the output trajectory corresponding
to the solution process ξaνω . Here, we assume that the Poisson processes Psi , for any i ∈ [1; qe], have the rates
of λi . We emphasize that the postulated assumptions on f , σ, and r ensure existence, uniqueness, and strong
Markov property of the solution processes [Bor89].
Remark 2.2. We refer the interested readers to Section IV in [JP09] showing how one can cast linear stochastic hybrid automata (LSHA) as jump linear stochastic systems (JLSS) (c.f. Section 5) which are a specific
class of the ones introduced in Definition 2.1.
3. Stochastic Simulation Function
Before introducing the notion of stochastic simulation functions, we first need to define the infinitesimal
generator of a stochastic process.
Definition 3.1. Let Σ = (Rn , Rm , Rp , U, W, f, σ, r, Rq , h) and Σ̂ = (Rn̂ , Rm̂ , Rp̂ , Û, Ŵ, fˆ, σ̂, r̂, Rq̂ , ĥ) be two
ˆ respectively. Consider a twice continuously differenstochastic hybrid systems with solution processes ξ and ξ,
n
n̂
ˆ denoted
tiable function V : R × R → R≥0 . The infinitesimal generator of the stochastic process Ξ = [ξ; ξ],

4

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

by L, acting on function V is defined in [ØS05, Section 1.3] as:





 ∂x,x V
1
f (x, u, w)
σ(x)  T
LV (x, x̂) := [∂x V ∂x̂ V ] ˆ
+ Tr
σ (x) σ̂ T (x̂)
σ̂ (x̂)
∂x̂,x V
f (x̂, û, ŵ)
2
+

qe
X
i=1

∂x,x̂ V
∂x̂,x̂ V


(3.1)

λi (V (x + r(x)ei , x̂ + r̂(x̂)ei ) − V (x, x̂)) ,

for every x ∈ Rn , x̂ ∈ Rn̂ , u ∈ Rm , û ∈ Rm̂ , w ∈ Rp , and ŵ ∈ Rp̂ .
Now, we introduce a notion of stochastic simulation functions, inspired by the notion of simulation function
in [RZ15], for deterministic control systems distinguishing the role of internal and external inputs.
Definition 3.2. Let Σ = (Rn , Rm , Rp , U, W, f, σ, r, Rq , h) and Σ̂ = (Rn̂ , Rm̂ , Rp , Û, W, fˆ, σ̂, r̂, Rq , ĥ) be two
stochastic hybrid systems with the same internal input and output space dimension. A twice continuously
differentiable function V : Rn × Rn̂ → R≥0 is called a stochastic simulation function from Σ̂ to Σ in the kth
moment (SSF-Mk ), where k ≥ 1, if it has polynomial growth rate and for any x ∈ Rn and x̂ ∈ Rn̂ one has
and ∀û ∈ R

m̂

p

α(kh(x) − ĥ(x̂)kk ) ≤ V (x, x̂),

(3.2)

LV (x, x̂) ≤ −η(V (x, x̂)) + ρext (kûkk ) + ρint (kw − ŵkk ),

(3.3)

∀ŵ ∈ R ∃u ∈ R

m

p

∀w ∈ R one obtains

for some K∞ functions α, η, ρext , ρint , where ei ∈ Rqe denotes the vector with 1 in the ith coordinate and 0’s
elsewhere, α, η are convex functions, and ρext , ρint are concave ones.
In the above definition, the symbols ∂x and ∂x,x̂ denote the first and the second order partial derivatives with
respect to x and x and x̂, respectively.
We say that a stochastic hybrid system Σ̂ is approximately alternatingly simulated in the kth moment by
a stochastic hybrid system Σ or Σ approximately alternatingly simulates in the kth moment Σ̂, denoted by
Σ̂ kAS Σ, if there exists a SSF-Mk function V from Σ̂ to Σ. We call Σ̂ an abstraction of Σ.
Remark 3.3. Note that the notion of SSF-Mk here is different from the notion of stochastic simulation
function in [JP09, Definition 2] requiring the existences of a supermartingale function [Oks02, Appendix C]
whose construction is computationally intractable in the case of (even linear) systems with inputs because one
requires to solve a game to compute this function. On the other hand, the notion of stochastic (bi)simulation
function in [JP09] is stronger than the notion of SSF-Mk as it provides a lower bound on the probability of
satisfaction of specifications for which satisfiability can be obtained at all time instances rather than for a
bounded time horizon (cf. Proposition 3.7) or at single time instances (cf. Proposition 3.8). We refer the
interested readers to Subsection V.B in [ZMM+ 14] for more detailed information about those differences in
satisfiability.
Remark 3.4. If the drift, diffusion, and reset terms in Σ and Σ̂ in Definition 3.2 are polynomial, one can
use some sum of squares based semidefinite programing tools, such as SOSTOOLS [PAV+ 13, Subsection 4.2],
in order to efficiently search for a (sum of squares) SSF-Mk function from Σ̂ to Σ which may not exist in
general.
The following theorem shows the importance of the existence of a SSF-Mk function by quantifying the error
between the behaviors of Σ and the ones of its abstraction Σ̂.
Theorem 3.5. Let Σ = (Rn , Rm , Rp , U, W, f, σ, r, Rq , h) and Σ̂ = (Rn̂ , Rm̂ , Rp , Û, W, fˆ, σ̂, r̂, Rq , ĥ). Suppose
V is an SSF-Mk function from Σ̂ to Σ. Then, there exist a KL function β and K∞ functions γext , γint such
that for any ν̂ ∈ Û, any ω̂ ∈ W, and any random variable a and â that are F0 -measurable1, there exists ν ∈ U
1Note that F may be the trivial sigma-algebra, i.e., a and â are deterministic initial conditions.
0

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

5

such that for all ω ∈ W the following inequality holds:

E[kζaνω (t) − ζ̂âν̂ ω̂ (t)kk ] ≤ β (E[V (a, â)], t) + γext (E[kν̂kk∞ ]) + γint (E[kω − ω̂kk∞ ]).

(3.4)

The proof of Theorem 3.5 requires the following preparatory lemma and is provided in the Appendix.
Lemma 3.6. Let g be a non-negative constant and η be a K∞ function. Suppose that the function y : R≥0 →

Rt
R≥0 is continuous and we have y(t) ≤ y(t0 ) + t0 [−η y(τ ) + g] d τ for all t ≥ t0 ≥ 0. Then, there exists a KL
function ϑ such that
n

o
y(t) ≤ max ϑ y(0), t , η −1 2g , ∀t ≥ 0.
The proof of Lemma 3.6 is provided in the Appendix.
Note that the importance of the result provided in Theorem 3.5 is that one can synthesize a controller for
the abstraction Σ̂, which is potentially easier (e.g., lower dimension and simpler interconnection topology) to
enforce some complex specification, for example given in LTL. Then there exists a controller for the concrete
stochastic hybrid system Σ satisfying the same complex specification. The error, introduced in the design
process by taking the detour through the abstraction, is quantified by inequality (3.4). In Section 5, we show
how one can actually refine a controller designed for the abstract JLSS to a controller for the original JLSS
via a so-called interface function.
The notion of stochastic simulation function in this work can also be used to lower bound the probability that
the Euclidean distance between any output trajectory of the abstract model and the corresponding one of the
concrete model remains close.
We make the above statement more precise with the following results.
Proposition 3.7. Let Σ and Σ̂ be two stochastic hybrid systems with the same internal input and output
space dimension. Suppose V is an SSF-Mk function from Σ̂ to Σ and the K∞ function η in (3.3) satisfies
η(r) ≥ θr for some θ ∈ R>0 and any r ∈ R≥0 . For any ν̂ ∈ Û, any ω̂ ∈ W, and any random variable a and â
that are F0 -measurable, there exists ν ∈ U such that for all ω ∈ W the following inequalities (3.5) and (3.6)
hold provided that there exists a constant  ≥ 0 satisfying  ≥ ρext (kν̂kk∞ ) + ρint (kω − ω̂kk∞ ):




 
V (a, â) − α(Tεk )
P sup kζaνω (t) − ζ̂âν̂ ω̂ (t)k ≥ ε | [a; â] ≤ 1 − 1 −
e
, if α εk ≥ ,
(3.5)
k
α (ε )
θ
0≤t≤T



 
θV (a, â) + eT θ − 1 
P sup kζaνω (t) − ζ̂âν̂ ω̂ (t)k ≥ ε | [a; â] ≤
, if α εk ≤ .
(3.6)
k ) eT θ
θα
(ε
θ
0≤t≤T
The proof of Proposition 3.7 is provided in the Appendix.
As an alternative to the previous result, we now use the notion of stochastic simulation function to lower
bound the probability of the Euclidean distance between any output trajectory of the abstract model and the
corresponding one of the concrete model point-wise in time: this error bound is sufficient to work with those
specifications for which satisfiability can be achieved at single time instances, such as next ( ) and eventually
(3) in LTL. Please look at the explanation after the proof of Proposition 5.11 in [ZMM+ 14] for more details.
Proposition 3.8. Let Σ and Σ̂ be two stochastic hybrid systems with the same internal input and output space
dimension. Suppose V is an SSF-Mk function from Σ̂ to Σ. For any ν̂ ∈ Û, any ω̂ ∈ W, and any random
variable a and â that are F0 -measurable, there exists ν ∈ U such that for all ω ∈ W the following inequality
holds for all t ∈ R≥0 :
1
n
o
β (E[V (a, â)], t) + γext (E[kν̂kk∞ ]) + γint (E[kω − ω̂kk∞ ]) k
,
(3.7)
P kζaνω (t) − ζ̂âν̂ ω̂ (t)k ≥ ε ≤
ε
where β, γext , and γint are the functions appearing in (3.4).

6

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

The proof of Proposition 3.8 is provided in the Appendix.
In the next section, we work with interconnected stochastic hybrid systems without internal inputs, resulting
from the interconnection of stochastic hybrid subsystems having both internal and external signals. In this
case, the interconnected stochastic hybrid systems reduce to the tuple Σ = (Rn , Rm , U, f, σ, r, Rq , h) and the
drift term becomes f : Rn × Rm → Rn . In this view, inequality (3.3) is not quantified over w, ŵ ∈ Rp , and,
hence, the term ρint (kw − ŵkk ) is omitted as well. Similarly, the results in Theorem 3.5 and Propositions 3.7
and 3.8 are modified accordingly, i.e., for systems without internal inputs the inequalities (3.4), (3.5), (3.6),
and (3.7) are not quantified over ω, ω̂ ∈ W and, hence, the term γint (E[kω − ω̂kk∞ ]) is omitted in inequalities
(3.4) and (3.7) and  is lower bounded as  ≥ ρext (kν̂kk∞ ) in Proposition 3.7 as well.
The next corollary provides a similar result as the one of Proposition 3.7 but by considering an infinite time
horizon and interconnected stochastic hybrid systems and assuming ν̂ ≡ 0, resulting in  = 0. The relation
proposed in this corollary recovers the one proposed in [JP09, Theorem 3].
Corollary 3.9. Let Σ and Σ̂ be two interconnected stochastic hybrid systems with the same output space
dimension. Suppose V is an SSF-Mk function from Σ̂ to Σ. For ν̂ ≡ 0 and any random variable a and â that
are F0 -measurable, there exists ν ∈ U such that the following inequality holds:


V (a, â)
.
P
sup kζaν (t) − ζ̂â0 (t)k > ε | [a; â] ≤
α (εk )
0≤t<∞
The proof of Corollary 3.9 is provided in the Appendix.
Note that under the assumptions of Corollary 3.9 any SSF-Mk function is also a stochastic simulation function
as in [JP09].
4. Compositionality Result
In this section, we analyze interconnected stochastic hybrid systems and show how to construct an abstraction
of an interconnected stochastic hybrid system together with the corresponding stochastic simulation function.
The definition of the interconnected stochastic hybrid system is based on the notion of interconnected systems
introduced in [TI08].
4.1. Interconnected stochastic hybrid systems. We consider N ∈ N≥1 stochastic hybrid subsystems
Σi = (Rni , Rmi , Rpi , Ui , Wi , fi , σi , ri , Rqi , hi ) ,

i ∈ [1; N ]

with partitioned internal inputs and outputs


wi = wi1 ; . . . ; wi(i−1) ; wi(i+1) ; . . . ; wiN , wij ∈ Rpij
and output function

yi = [yi1 ; . . . ; yiN ], yij ∈ Rqij

hi (xi ) = [hi1 (xi ); . . . ; hiN (xi )],
as depicted schematically in Figure 1.

ui
wi1
wiN

⌃i

yi1
yi2
yiN

Figure 1. Input/output configuration of stochastic hybrid subsystem Σi .

(4.1)
(4.2)

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

7

We interpret the outputs yii as external ones, whereas the outputs yij with i 6= j are internal ones which are
used to define the interconnected stochastic hybrid systems. In particular, we assume that the dimension of
wij is equal to the dimension of yji , i.e., the following interconnection constraints hold:
pij = qji , ∀i, j ∈ [1; N ], i 6= j.

(4.3)

If there is no connection from stochastic hybrid subsystem Σi to Σj , then we assume that the connecting
output function is identically zero for all arguments, i.e., hij ≡ 0. We define the interconnected stochastic
hybrid system as the following.
Definition 4.1. Consider N ∈ N≥1 stochastic hybrid subsystems Σi = (Rni , Rmi , Rpi , Ui , Wi , fi , σi , ri , Rqi , hi ),
i ∈ [1; N ], with the input-output configuration given by (4.1)-(4.3). The interconnected stochastic hybrid
PN
PN
system Σ = (Rn , Rm , U, f, σ, r, Rq , h), denoted by I(Σ1 , . . . , ΣN ), follows by n =
ni , m =
i=1
i=1 mi ,
PN
q = i=1 qii , and functions
f (x, u) := [f1 (x1 , u1 , w1 ); . . . ; fN (xN , uN , wN )],
σ(x) := [σ1 (x1 ); . . . ; σN (xn )],
r(x) := [r1 (x1 ); . . . ; rN (xn )],
h(x) := [h11 (x1 ); . . . ; hN N (xN )],
where u = [u1 ; . . . ; uN ] and x = [x1 ; . . . ; xN ] and with the interconnection variables constrained by wij = yji
for all i, j ∈ [1; N ], i 6= j.
The interconnection of two stochastic hybrid subsystems Σi and Σj from a group of N subsystems is illustrated
in Figure 2.
ui
wi1
wij
wiN

uj
wj1
wji

yi1
yii

⌃i

yij
yiN

yj1
yji

⌃j

yjj
yjN

wjN

Figure 2. Interconnection of two stochastic hybrid subsystems Σi and Σj .

4.2. Compositional construction of abstractions and simulation functions. We assume that we are
given N stochastic hybrid subsystems Σi = (Rni , Rmi , Rpi , Ui , Wi , fi , σi , ri , Rqi , hi ) , together with their corresponding abstractions Σ̂i = (Rn̂i , Rm̂i , Rpi , Ûi , Wi , fˆi , σ̂i , r̂i , Rqi , ĥi ) and with SSF-Mk functions Vi from Σ̂i to
Σi . In order to provide the main compositionality result, we require the following assumption:
ei ∈ R>0 and
Assumption 1. For any i, j ∈ [1; N ], i 6= j, there exist K∞ convex functions γi and constants λ
δij ∈ R≥0 such that for any s ∈ R≥0
ei γi (s)
ηi (s) ≥ λ

(4.4a)

hji ≡ 0 =⇒ δij = 0 and

(4.4b)
k

hji 6≡ 0 =⇒ ρiint ((N − 1)max{ 2 ,1} αj−1 (s)) ≤ δij γj (s),

(4.4c)

where ηi , αi , and ρiint represent the corresponding K∞ functions of subsystems Σi appearing in Definition 3.2.

8

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

For notational simplicity in the rest of the paper, we define matrices Λ and ∆ in RN ×N with their components
ei , ∆ii = 0 for i ∈ [1; N ] and Λij = 0, ∆ij = δij for i, j ∈ [1; N ], i 6= j. Moreover, we define
given by Λii = λ
→
→
Γ( s ) := [γ1 (s1 ); . . . ; γN (sN )], where s = [s1 ; . . . ; sN ].
The next theorem provides a compositional approach on the construction of abstractions of interconnected
stochastic hybrid systems and that of the corresponding SSF-Mk functions.
Theorem 4.2. Consider the interconnected stochastic hybrid system Σ = I(Σ1 , . . . , ΣN ) induced by N ∈ N≥1
stochastic hybrid subsystems Σi . Suppose that each stochastic hybrid subsystem Σi approximately alternatingly
simulates a stochastic hybrid subsystem Σ̂i with the corresponding SSF-Mk function Vi . If Assumption 1 holds
and there exists a vector µ ∈ RN
>0 such that the inequality
µT (−Λ + ∆) < 0

(4.5)

2

is satisfied , then
V (x, x̂) :=

N
X

µi Vi (xi , x̂i )

i=1

is an SSF-Mk function from Σ̂ = I(Σ̂1 , . . . , Σ̂N ) to Σ.
Proof. Note that for any x = [x1 ; . . . ; xN ], where xi ∈ Rni and i ∈ [1; N ], one obtains:
kxkk ≤

N
X
i=1

kxi kk ,

for any k ∈ [1, 2] due to triangle inequality and appropriate equivalency between different norms and
N
N
X
X
k
k
k
kxi k2 ) 2 ≤ N 2 −1
kxi kk ,
kxkk = (kxk2 ) 2 = (
i=1

i=1

for any k > 2 due to Jensen’s inequality [BV09] for convex functions. By combining the previous inequalities,
one gets
N
X
k
kxkk ≤ N max{ 2 ,1}−1
kxi kk ,
(4.6)
i=1

for any k ≥ 1 and any x = [x1 ; . . . ; xN ], where xi ∈ Rni and i ∈ [1; N ].
First we show that inequality (3.2) holds for some convex K∞ function α. Using (4.6), for any x = [x1 ; . . . ; xN ] ∈
Rn and x̂ = [x̂1 ; . . . ; x̂N ] ∈ Rn̂ , one gets:
k

N
X

k

N
X

kĥ(x̂) − h(x)kk ≤ N max{ 2 ,1}−1
≤ N max{ 2 ,1}−1
where α is a K∞ function defined as
α(s) :=

i=1

i=1

k

kĥii (x̂i ) − hii (xi )kk ≤ N max{ 2 ,1}−1

N
X
i=1

kĥi (x̂i ) − hi (xi )kk

αi−1 (Vi (xi , x̂i )) ≤ α(V (x, x̂)),


 max
→
s ≥0

 s.t.

k

N max{ 2 ,1}−1

PN

i=1

αi−1 (si )

→

µT s = s.

Now we show that α is a concave function. Let us recall that by assumptions αi are convex functions and,
hence, αi−1 are concave3. Thus, from an optimization point of view, the function α is a perturbation function
2We interpret the inequality component-wise, i.e., for x ∈ RN we have x < 0 iff every entry x < 0, i ∈ {1, . . . , N }.
i
3Note that the inverse of a strictly increasing convex (resp. concave) function is a strictly increasing concave (resp. convex)

one.

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

LV (x, x̂) =
≤
≤
≤
≤
≤

N
X
i=1
N
X
i=1
N
X
i=1
N
X
i=1
N
X
i=1
N
X
i=1

µi LVi (xi , x̂i ) ≤

N
X
i=1

9



k
µi −ηi (Vi (xi , x̂i )) + ρiint (kwi − ŵi k ) + ρiext (kûi kk )


µi −ηi (Vi (xi , x̂i )) +

N
X
j=1,j6=i


µi −ηi (Vi (xi , x̂i )) +

N
X
j=1,j6=i


µi −ηi (Vi (xi , x̂i )) +

N
X
j=1,j6=i


µi −ηi (Vi (xi , x̂i )) +

N
X
j=1,j6=i


ei γi (Vi (xi , x̂i )) +
µi −λ


ρiint ((N − 1)

max{ k
2 ,1}

ρiint ((N − 1)

max{ k
2 ,1}

k

kwij − ŵij k ) + ρiext (kûi kk )

k

kyji − ŷji k ) + ρiext (kûi kk )


max{ k
2 ,1}

ρiint ((N − 1)


max{ k
2 ,1}

ρiint (N − 1)

N
X
i6=j,j=1

khj (xj ) − ĥj (x̂j )kk ) + ρiext (kûi kk )


αj−1 (Vj (xj , x̂j )) + ρiext (kûi kk )


k
δij γj (Vj (xj , x̂j )) + ρiext (kûi k )

= µ> (−Λ + ∆) Γ ([V1 (x1 , x̂1 ) ; . . . ; VN (xN , x̂N )]) +

N
X
i=1

k

µi ρiext (kûi k ).

(4.7)

which is known to be a concave function; see [BV09, Section 5.6.1, p. 249] for further details. By defining the
convex3 K∞ function α(s) = α−1 (s), ∀s ∈ R≥0 , one obtains
α(kĥ(x̂) − h(x)kk ) ≤ V (x, x̂),
satisfying inequality (3.2). Now we show that inequality (3.3) holds as well. Consider any x = [x1 ; . . . ; xN ] ∈
Rn , x̂ = [x̂1 ; . . . ; x̂N ] ∈ Rn̂ , and û = [û1 ; . . . ; ûN ] ∈ Rm̂ . For any i ∈ [1; N ], there exists ui ∈ Rmi , consequently,
a vector u = [u1 ; . . . ; uN ] ∈ Rm , satisfying (3.3) for each pair of subsystems Σi and Σ̂i with the internal inputs
given by wij = hji (xj ) and ŵij = ĥji (x̂j ). We derive the chain of inequalities in (4.7), where we use the
inequalities (4.6) and:
ρiint (r1 + · · · + rN −1 ) ≤

N
−1
X
i=1

ρiint ((N − 1)ri ),

which are valid for any k ≥ 1, ρiint ∈ K∞ , xi ∈ Rni , and any ri ∈ R≥0 , i ∈ [1; N [. Note that if ρiint satisfies
the triangle inequality, one gets the less conservative inequality
ρiint (r1 + · · · + rN −1 ) ≤

N
−1
X

ρiint (ri ),

i=1

and it suffices that (4.9) holds instead of (4.4c). Define the functions

 min −µT (−Λ + ∆) Γ(→
s)
→
s ≥0
η(s) :=
→
 s.t.
µT s = s,

PN
 max
i=1 µi ρiext (si )
→
s ≥0
ρext (s) :=
→
 s.t.
k s k ≤ s.

(4.8a)

(4.8b)

10

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

ûi
ŵi1
ŵiN

ˆi
⌃

ŷi1
ŷi2
ŷiN

ûi
ŵi1
ŵiN

k
AS

ŷi1
ŷi2
ŷiN

ˆi
⌃

)

ˆ1
⌃

ˆ4
⌃

⌃1
k
AS

ˆ3
⌃

⌃3

ˆ5
⌃

ˆ2
⌃

⌃4

⌃2

⌃5

Figure 3. Compositionality results.
By construction, we readily have
k

V̇ (x, x̂) ≤ −η (V (x, x̂)) + ρext (kûk ),

where the functions η and ρext are K∞ functions. It remains to show that η is a convex function and ρext is
a concave one. Let us recall that by assumptions µT (−Λ + ∆) < 0 and γi , the i-th element of Γ, is convex.
Thus, the function η in (4.8a) is a perturbation function which is a convex one. Note that by assumption each
function ρiext is concave, and for the same reason as above, the function (4.8b) is also concave. Hence, we
conclude that V is an SSF-Mk function from Σ̂ to Σ.

T
Remark 4.3. As shown in [DIW11, Lemma 3.1], a vector µ ∈ RN
>0 satisfying µ (−Λ + ∆) < 0 exists if and
−1
only if the spectral radius of Λ ∆ is strictly less than one.

Remark 4.4. If the functions ρiint , i ∈ [1; N ], satisfy the triangle inequality, ρiint (a + b) ≤ ρiint (a) + ρiint (b)
for all non-negative values of a and b, then the condition (4.4c) reduces to
k

hji 6≡ 0 =⇒ ρiint ((N − 1)max{ 2 ,1}−1 αj−1 (s)) ≤ δij γj (s).

(4.9)

Figure 3 illustrates schematically the result of Theorem 4.2.
5. Jump Linear Stochastic Systems
In this section, we focus on a specific class of stochastic hybrid systems, namely, jump linear stochastic systems
(JLSS) [JP09] and quadratic SSF-M2 functions V . In the first part, we assume that we are given an abstraction
Σ̂ and provide conditions under which V is an SSF-M2 function. In the second part we show how to construct
the abstraction Σ̂ together with the SSF-M2 function V .
A JLSS is defined as a stochastic hybrid system with the drift, diffusion, reset, and output functions given by
d ξ(t) =(Aξ(t) + Bν(t) + Dω(t)) d t + Eξ(t) d Wt +

qe
X

Ri ξ(t) d Pti ,

i=1

ζ(t) =Cξ(t),

(5.1)

where
A ∈ Rn×n , B ∈ Rn×m , D ∈ Rn×p , E ∈ Rn×n , Ri ∈ Rn×n , ∀i ∈ [1; qe], C ∈ Rq×n .

The matrices Ri , ∀i ∈ [1; qe], parametrize the jump associated with event i. We use the tuple
Σ = (A, B, C, D, E, R),

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

11

where R = {R1 , . . . , Rqe}, to refer to a JLSS of the form (5.1). Note that in this section we consider JLSS
driven by a scalar Brownian motion for the sake of simple presentation, though the proposed results can be
readily generalized for the systems driven by multi-dimensional Brownian motions as well.
5.1. Quadratic SSF-M2 functions. In this section, we assume that for some constant κ
b ∈ R>0 there exist
a positive definite matrix M ∈ Rn×n and matrix K ∈ Rm×n such that the matrix inequalities

A + BK +

qe
X

C T C  M,

!T
λi Ri

M +M

A + BK +

i=1

qe
X

!
+ ET M E +

λi Ri

i=1

qe
X
i=1

λi RiT M Ri  −b
κM,

(5.2)
(5.3)

hold.
Note that condition (5.3) is sufficient and necessary for the asymptotic stability of Σ = (A, B, C, 0n×p , E, R)
equipped with a linear feedback control law u = Kx in the mean square sense (second moment)4 as showed
in the next lemma. Condition (5.2) is always satisfied for any positive definite matrix M up to multiplication
by some positive scalar which does not violate the satisfaction of (5.3).
Lemma 5.1. A JLSS Σ = (A, B, C, 0n×p , E, R) equipped with a linear feedback control law u = Kx is asymptotically stable in the mean square sense if and only if there exists a positive definite matrix M ∈ Rn×n such
that the matrix inequality (5.3) is satisfied for given feedback gain K and some positive constant κ
b.
The proof of Lemma 5.1 is provided in the Appendix.
The matrices K and M in (5.2) and (5.3) can be computed jointly using semidefinite programming as explained
in the following lemma.
Lemma 5.2. Denoting K = KM −1 and M = M −1 , matrix inequalities (5.2) and (5.3) are equivalent to the
following linear matrix inequalities:


M
M CT
0
(5.4)
CM
Iq


M
0
···
0
EM
1
..


..
 0
.
M
.
λqe2 RqeM 


 ..

..
..
..
(5.5)
 .
  0,
.
.
0
.


1


···
0
M
λ12 R1 M 
 0
M ET

1

λqe2 M RqTe

···

1

λ12 M R1T

Q

where 0’s denote zero matrices of appropriate dimensions and
qe
qe

T 

X
X
T
Q := − κ
bM − M A +
λi Ri − A +
λi Ri M − K B T − BK.
i=1

i=1

The proof is a simple consequence of using Schur complements [BV09] and is omitted here for the sake of
brevity.
Here, we consider a quadratic SSF-M2 function of the following form
V (x, x̂) = (x − P x̂)T M (x − P x̂),

(5.6)

4A stochastic hybrid system Σ is said to be asymptotically stable in the mean square sense if all F -measurable initial states
0
a yield limt→∞ E[kξ(t)k2 ] = 0.

12

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

where P is a matrix of appropriate dimension. Assume that the equalities
AP = P Â − BQ

(5.7a)

D = P D̂ − BS

(5.7b)

CP = Ĉ

(5.7c)

EP = P Ê

(5.7d)

Ri P = P R̂i , ∀i ∈ [1; qe],

(5.7e)

hold for some matrices Q and S of appropriate dimensions. In the following theorem, we show that those
conditions imply that (5.6) is an SSF-M2 function from Σ̂ to Σ.
Theorem 5.3. Consider two JLSS Σ = (A, B, C, D, E, R) and Σ̂ = (Â, B̂, Ĉ, D̂, Ê, R̂) with p = p̂ and q = q̂.
Suppose that there exist matrices M , K, P , Q, and S satisfying (5.2), (5.3), and (5.7), for some constant
κ
b ∈ R>0 . Then, V defined in (5.6) is an SSF-M2 function from Σ̂ to Σ.
Proof. Note that V is twice continuously differentiable. We show that for every x ∈ Rn , x̂ ∈ Rn̂ , û ∈ Rm̂ ,
ŵ ∈ Rp , there exists u ∈ Rm such that for all w ∈ Rp , V satisfies kCx − Ĉ x̂k2 ≤ V (x, x̂) and
∂V (x, x̂)
∂V (x, x̂)
(Ax + Bu + Dw) +
(Âx̂ + B̂ û + D̂ŵ)
∂x
∂ x̂
  h
qe
i ∂ V ∂ V  X
1
Ex
x,x
x,x̂
xT E T x̂T Ê T
+ Tr
+
λi (V (x + Ri x, x̂ + R̂i x̂) − V (x, x̂))
∂x̂,x V ∂x̂,x̂ V
Ê x̂
2
i=1
√
√
e − P B̂)k2
2k M Dk2
2k M (B R
2
≤ − (b
κ − π)V (x, x̂) +
kw − ŵk +
kûk2 ,
(5.8)
π
π
e of appropriate dimension.
for any positive constant π < κ
b and some matrix R
LV (x, x̂) :=

From (5.7c), we have kCx − Ĉ x̂k2 = (x − P x̂)T C T C(x − P x̂) and using M  C T C, it can be readily verified
that kCx − Ĉ x̂k2 ≤ V (x, x̂) holds for all x ∈ Rn , x̂ ∈ Rn̂ . We proceed with showing the inequality in (5.8).
Note that
∂x V (x, x̂) = 2(x − P x̂)T M, ∂x̂ V (x, x̂) = −2(x − P x̂)T M P, ∂x,x V (x, x̂) = 2M, and
T

∂x̂,x̂ V (x, x̂) = P T ∂x,x V (x, x̂)P, ∂x,x̂ V (x, x̂) = (∂x̂,x V (x, x̂)) = −∂x,x V (x, x̂)P

holds. Given any x ∈ Rn , x̂ ∈ Rn̂ , û ∈ Rm̂ , and ŵ ∈ Rp , we choose u ∈ Rm via the following linear interface
function:
e + S ŵ,
u = νν̂ (x, x̂, û, ŵ) := K(x − P x̂) + Qx̂ + Rû
(5.9)
e of appropriate dimension.
for some matrix R
By using the equations (5.7a) and (5.7b) and the definition of the interface function in (5.9), we simplify
Ax + Bνν̂ (x, x̂, û, ŵ) + Dw − P (Âx̂ + B̂ û + D̂ŵ)
e − P B̂)û and obtain the following expression for LV (x, x̂):
to (A + BK)(x − P x̂) + D(w − ŵ) + (B R


e − P B̂)û
LV (x, x̂) = 2(x − P x̂)T M (A + BK)(x − P x̂) + D(w − ŵ) + (B R
 T  T


    T X
 T

 
qe
E 0 x
E
0
Ri
0
M
−M P
M
−M P
x
x
x
+
+
λ
i
x̂
x̂
0 Ê x̂
0 Ê T −P T M P T M P
0 R̂iT −P T M P T M P x̂
i=1
 T 
X

 
qe
Ri 0
M
−M P
x
x
+
λi
T
T
x̂
−P M P M P
0 R̂i x̂
i=1
 T X
 T


 
qe
Ri 0
Ri
0
M
−M P
x
x
+
λi
,
x̂
0 R̂i x̂
0 R̂iT −P T M P T M P
i=1

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

13

where 0’s denote zero matrices of appropriate dimensions. We use (5.7d) and (5.7e) to obtain the following
expression for LV (x, x̂):
qe
qe
h
T


X
X
A + BK +
λi Ri M + M A + BK +
LV (x, x̂) =(x − P x̂)
λi Ri
T

i=1

+ ET M E +

qe
X
i=1

i=1

i


e − P B̂)û .
λi RiT M Ri (x − P x̂) + 2(x − P x̂)T M D(w − ŵ) + (B R

Using Young’s inequality [You12] as
 2
1
a + b2 ,
2
2
for any a, b ≥ 0 and any  > 0, and with the help of Cauchy-Schwarz inequality and (5.3) one gets the following
upper bound for LV (x, x̂):
√
√
e − P B̂)k2
2k M (B R
2k M Dk2
2
kw − ŵk +
kûk2 ,
LV (x, x̂) ≤ −b
κV (x, x̂) + πV (x, x̂) +
π
π
for any positive constant π < κ
b.
ab ≤

Using this computed upper bound, we obtain (5.8) which completes the proof. Note that the K∞ functions
α, η, ρext , and ρint , in Definition
3.2 associated with the SSF-M
function in (5.6) are given by α(s) := s,
√
√ 2

η(s) := (b
κ − π)s, ρext (s) :=

e
2k M (B R−P
B̂)k2
s
π

and ρint (s) :=

2k M Dk2
s,
π

∀s ∈ R≥0 .


Remark 5.4. Using the linear functions α and η, as computed in Theorem 5.3, the functions β, γext , and
1
γint , appearing in Theorem 3.5, are simplified as the following: β(r, t) := re−(bκ−π)t , γext (r) := κb−π
ρext (r),
1
and γint (r) := κb−π ρint (r) for any r, t ∈ R≥0 .
e Similar to the results
Remark 5.5. Note that Theorem 5.3 does not impose any condition on matrix R.
e which minimize function ρext
in [GP09, Proposition 1] for the deterministic case, we propose a choice of R
e minimizing ρext is given by
for V . The choice of R
e = (B T M B)−1 B T M P B̂.
R

(5.10)

Remark 5.6. Consider Σih = (Ai , Bii , Ci , Di , Ei , Ri ) and its abstraction Σ̂i = (Âi , B̂i , Ĉi , D̂i , Êi , R̂i ). Assume


Di = d1i · · · dpi and D̂i = dˆ1i · · · dˆpi . Using equation (5.7b), one can readily conclude that if dji ∈ im B, for
some j ∈ [1; p], then the corresponding dˆji can be chosen as dˆji = 0n̂ . This choice for columns of D̂ makes the
interconnection topology of abstract subsystems potentially simpler and, hence, their analysis easier. We refer
the interested readers to Section 6 for an example of such choice for D̂.
As of now, we derived various conditions on the original system Σ, the abstraction Σ̂, and the matrices
appearing in (5.6) and (5.9), to ensure that (5.6) is an SSF-M2 function from Σ̂ to Σ with the corresponding
interface function in (5.9) lifting any control policy designed for Σ̂ to the one for Σ. However, those conditions
do not impose any requirements on the abstract external input matrix B̂. As an example, one can choose
B̂ = In̂ which makes the abstract system Σ̂ fully actuated and, hence, the synthesis problem over Σ̂ much
easier. Similar to [GP09, Subsection 4.1] in the context of deterministic control systems, one can also choose
an external input matrix B̂ which preserves all the behaviors of the original JLSS Σ on the abstraction Σ̂: for
ˆ ζ̂, ν̂, ω̂) of Σ̂ such that ζ̂ = ζ P-a.s..
every trajectory (ξ, ζ, ν, ω) of Σ there exists a trajectory (ξ,
Note that using the following choice of external input matrix B̂, the results in [RZ15] for the linear deterministic
control system are fully recovered by the corresponding ones here providing that the JLSS is not affected by
any noise, implying that E, Ê, Ri , and R̂i , ∀i ∈ [1; qe], are identically zero.

14

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

Theorem 5.7. Consider two JLSS Σ = (A, B, C, D, E, R) and Σ̂ = (Â, B̂, Ĉ, D̂, Ê, R̂) with p = p̂ and q = q̂.
Suppose that there exist matrices P , Q, and S satisfying (5.7) and that the abstract external input matrix B̂
is given by
B̂ = [P̂ B P̂ AG],

(5.11)

where P̂ and G are assumed to satisfy
C = Ĉ P̂

(5.12a)

In = P P̂ + GF

(5.12b)

In̂ = P̂ P

(5.12c)

0n̂×n = P̂ EGF

(5.12d)

0n̂×n = P̂ Ri GF, ∀i ∈ [1; qe],

(5.12e)

ˆ ζ̂, ν̂, ω̂) of Σ̂ so that
for some matrix F . Then, for every trajectory (ξ, ζ, ν, ω) of Σ there exists a trajectory (ξ,
ζ = ζ̂ holds P-a.s..
ˆ ζ̂, ν̂, ω) with
Proof. Let (ξ, ζ, ν, ω) be a trajectory of Σ. We are going to show that (ξ,


ν − QP̂ ξ − Sω
ζ̂ = ζ, ξˆ = P̂ ξ, and ν̂ =
,
Fξ
P-a.s. is a trajectory of Σ̂. We use (5.7d), (5.7e), (5.12b), (5.12c), (5.12d), and (5.12e) and derive
d P̂ ξ = (P̂ Aξ + P̂ Bν + P̂ Dω) d t + P̂ Eξ d Wt +

qe
X

P̂ Ri ξ d Pti

i=1

= (P̂ AP P̂ ξ + P̂ A(In − P P̂ )ξ + P̂ Bν + P̂ Dω) d t + P̂ E(P P̂ + GF )ξ d Wt +
= (P̂ AP P̂ ξ + P̂ AGF ξ + P̂ Bν + P̂ Dω) d t + P̂ P Ê P̂ ξ d Wt +

qe
X

qe
X

P̂ Ri (P P̂ + GF )ξ d Pti

i=1

P̂ P R̂i P̂ ξ d Pti

i=1

= (P̂ AP P̂ ξ + P̂ AGF ξ + P̂ Bν + P̂ Dω) d t + Ê P̂ ξ d Wt +

qe
X

R̂i P̂ ξ d Pti .

i=1

Now we use the equations (5.7a) and (5.7b) and the definition of B̂ and ν̂ to derive
qe
X

d P̂ ξ = P̂ (P Â − BQ)P̂ ξ + P̂ AGF ξ + P̂ Bν + P̂ (P D̂ − BS)ω d t + Ê P̂ ξ d Wt +
R̂i P̂ ξ d Pti
i=1

=(ÂP̂ ξ + [P̂ B P̂ AG]ν̂ + D̂ω) d t + Ê P̂ ξ d Wt +

qe
X

R̂i P̂ ξ d Pti

i=1

=(ÂP̂ ξ + B̂ ν̂ + D̂ω) d t + Ê P̂ ξ d Wt +

qe
X

R̂i P̂ ξ d Pti

i=1

showing that (P̂ ξ, ζ̂, ν̂, ω) is a trajectory of Σ̂. From C = Ĉ P̂ in (5.12a), it follows that ζ̂ = ζ P-a.s. which
concludes the proof.


APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

15

5.2. Construction of abstractions. In this subsection, we provide constructive methods to compute the
abstraction Σ̂ along with the various matrices involved in the definition of the stochastic simulation function
and its corresponding interface function.
First, let us recall Lemma 2 in [GP09], showing that there exist matrices Â and Q satisfying (5.7a) if and only
if columns of P span an (A, B)-controlled invariant subspace, see e.g. [BM92, Definition 4.1.1].
Lemma 5.8. Consider matrices A, B, and P . There exist matrices Â and Q satisfying (5.7a) if and only if
im AP ⊆ im P + im B.

(5.13)

Given that P satisfies (5.13), it is straightforward to compute Â and Q such that (5.7a) holds, by solving n̂
linear equations.
Similar to Lemma 5.8, we give necessary and sufficient conditions for the existence of matrices D̂ and S
appearing in condition (5.7b).
Lemma 5.9. Given P and B, there exist matrices D̂ and S satisfying (5.7b) if and only if
im D ⊆ im P + im B.

(5.14)

The proof of Lemma 5.9 is provided in the Appendix.
Now we provide necessary and sufficient conditions for the existence of matrices Ê and R̂i , ∀i ∈ [1; qe], appearing
in conditions (5.7d) and (5.7e).
Lemma 5.10. Given P and E, there exists a matrix Ê satisfying (5.7d) if and only if
im EP ⊆ im P.

(5.15)

The proof is recovered from the one of Lemma 5.8 by substituting A, Â, and B with E, Ê, and 0n×m ,
respectively.
Lemma 5.11. Given P and Ri , ∀i ∈ [1; qe], there exists matrices R̂i , ∀i ∈ [1; qe], satisfying (5.7e) if and only
if
im Ri P ⊆ im P,

(5.16)

for any i ∈ [1; qe].
The proof is recovered from the one of Lemma 5.8 by substituting A, Â, and B with Ri , R̂i , ∀i ∈ [1; qe], and
0n×m , respectively.
Lemmas 5.8, 5.9, 5.10, and 5.11 provide necessary and sufficient conditions on P which lead to the construction
of matrices Â, D̂, Ê, and R̂i , ∀i ∈ [1; qe], together with the matrices Q, S appearing in the definition of the
interface function in (5.9). The output matrix Ĉ simply follows by Ĉ = CP . As we already discussed, the
abstract external input matrix can be chosen arbitrarily. For example one can choose B̂ = In̂ making the
abstract system Σ̂ fully actuated and, hence, the synthesis problem over it much simpler. One can also choose
B̂ as in (5.11) guaranteeing preservation of all behaviors of Σ on Σ̂ under extra conditions in (5.12). Lemma
3 in [GP09], as recalled next, provides necessary and sufficient conditions on P and C for the existence of P̂ ,
G, and F satisfying (5.12a), (5.12b), and (5.12c).
Lemma 5.12. Consider matrices C and P with P being injective and let Ĉ = CP . There exists matrix P̂
satisfying (5.12a), (5.12b), and (5.12c), for some matrices G and F of appropriate dimensions, if and only if
im P + ker C = Rn .

(5.17)

16

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

u1

Σ1

u2

Σ2

y14

y23

Σ3

y31
y33

Σ4

y44
y42

Figure 4. The interconnected system Σ = I(Σ1 , Σ2 , Σ3 , Σ4 ).
The conditions (5.13)-(5.16) (resp. (5.13)-(5.17)) complete the characterization of matrix P , together with the
system matrices {A, B, C, D} leading to the abstract matrices {Â, B̂, Ĉ, D̂}, where B̂ can be chosen arbitrarily
(resp. B̂ is computed as in (5.11) for the sake of preservation of all behaviors of Σ on Σ̂ as long as conditions
(5.12d) and (5.12e) are also satisfied). Note that there always exists an injective matrix P ∈ Rn×n̂ that
satisfies the conditions (5.13)-(5.17). In the worst-case scenario, we can pick the identity matrix with n̂ = n.
Of course, we would like to have the abstraction Σ̂ as simple as possible and, therefore, we should aim at a P
with n̂ as small as possible.
We summarize the construction of the abstraction Σ̂ in Table 1.
1. Compute matrices M and K satisfying (5.2) and (5.3).
2. Pick an injective P satisfying (5.13)-(5.16) (resp. (5.13)-(5.17) only
if the computed matrices P̂ , G, and F satisfy (5.12d) and (5.12e));
3. Compute Â and Q from (5.7a);
4. Compute D̂ and S from (5.7b);
5. Compute Ĉ = CP ;
6. Choose B̂ arbitrarily (resp. B̂ = [P̂ B P̂ AG]);
e appearing in (5.9), from (5.10);
7. Compute R,
8. Compute Ê from (5.7d) (resp. Ê = P̂ EP );
9. For any i ∈ [1; qe], compute R̂i from (5.7e) (resp. R̂i = P̂ Ri P ).
Table 1. Construction of an abstract JLSS Σ̂ for a given JLSS Σ.

6. An Example
Let us demonstrate the effectiveness of the proposed results by synthesizing a controller for an interconnected
system consisting of four JLSS Σ = I(Σ1 , Σ2 , Σ3 , Σ4 ). The interconnection scheme of Σ is illustrated in
Figure 4. The system has two outputs and we synthesize a controller to enforce them to stay approximately
(in the 2nd moment metric) within the safety constraint
S = [0 5] × [0 5].

We refer the interested readers to the explanation provided before [ZMM+ 14, Remark 5.5] or to [ZTA14,
Subsection 5.1] concerning the interpretation of the satisfaction of a safety constraint in the moment over the
concrete stochastic systems.
In designing a controller for Σ we proceed as follows. In the first step, we compute abstractions Σ̂i of the
individual subsystems to obtain an abstraction Σ̂ = I(Σ̂1 , Σ̂2 , Σ̂3 , Σ̂4 ) of the interconnected system Σ. The
interconnection scheme changes for Σ̂ (see Remark 5.6) and the abstract system is given by two identical independent interconnected systems Σ̂14 = I(Σ̂1 , Σ̂4 ) and Σ̂23 = I(Σ̂2 , Σ̂3 ). The abstract system Σ̂ is illustrated
in Figure 5. In the second step, we determinize the stochastic systems Σ̂14 and Σ̂23 by neglecting the diffusion

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

û1

û2

Σ̂1

Σ̂2

ŷ14

ŷ23

Σ̂3

Σ̂4

17

ŷ33
ŷ44

Figure 5. The abstract interconnected system Σ̂ = I(Σ̂1 , Σ̂2 , Σ̂3 , Σ̂4 ).
and reset terms. We obtain two identical deterministic control systems Σ̃14 and Σ̃23 . We show that Σ̃i is an
abstraction of Σ̂i , i ∈ {14, 23} by computing an SSF-M2 function from Σ̃i to Σ̂i . In the third step, we fix a
sampling time τ > 0 and use the MATLAB Toolbox MPT [HKJM13] to synthesize a safety controller that
enforces the safety constraints on Σ̃ = I(Σ̃14 , Σ̃23 ) at all sampling times kτ , k ∈ N. In the final step, we refine
the computed controller for Σ̃ to a controller for Σ. We use Theorem 3.5 to establish a bound on the distance
in the 2nd moment metric between the output trajectories of Σ and the safe set S.
6.1. The interconnected system. Let us consider the system illustrated in Figure 4. The subsystems Σ1
and Σ2 are double integrators and Σ3 and Σ4 are autonomous triple integrators. All systems are affected by
a scalar Brownian motion and a Poisson process. For j ∈ {1, 2} the system matrices are given by


 
 
0 1
0
1
Aj =
, Bj =
, CjT =
, Ej = 0.4I2 , Rj = 0.1I2 ,
2 0
1
0
and for i ∈ {3, 4} by



0
Ai =  0
−24

1
0
−26


 
0
1
1 , Bi = 0, CiT = 0 , Ei = 0.4I3 , Ri = 0.1I3 .
−9
0

The rate of the Poisson process Pt is λ = 4.2. The output of Σ1 (resp. Σ2 ) is connected to the internal input
of Σ4 (resp. Σ3 ) and the output of Σ3 (resp. Σ4 ) connects to the internal
input of Σ1 (resp. Σ2 ). The

 output

functions hij (xi ) = Cij xi are determined by Cii = Ci(i−2) = 1 0 0 for i ∈ {3, 4}, C23 = C14 = 1 0 and
hij ≡ 0 for the remaining i, j ∈ [1; 4]. Correspondingly, the internal input matrices are given by
 
 
0
0


D41 = D32 = −d , Dj(j+2) =
, d 6= 0, j ∈ {1, 2}.
d
5d
Subsequently, we use C1 = C14 , C2 = C23 , Ci = Cii , i ∈ {3, 4}, D1 = D13 , D2 = D24 , D3 = D32 , D4 = D41 ,
and denote the JLSS by Σi = (Ai , Bi , Ci , Di , Ei , Ri ).
6.2. The abstract subsystems. In order to construct an abstraction for I(Σ1 , Σ2 , Σ3 , Σ4 ) we construct an
abstraction Σ̂i of each individual subsystem Σi , i ∈ {1, 2, 3, 4}. We begin with i ∈ {1, 2} and follow the steps
outlined in Table 1. First, we fix κ
b = 3 and solve an appropriate LMI (see Lemma 5.2) to determine the
matrices Mi and Ki so that (5.2) and (5.3) hold. We obtain


 
1.68 0.4
−9
Mi =
, KiT =
.
0.4 0.23
−4
We continue with step 2. and determine


PiT = 1 −2 ,


so that (5.13)-(5.17)
hold.
The
matrices P̂i , Fi , and Gi that (5.12b)-(5.12e) hold, follow by P̂i = 1 0 ,



GTi = 0 2 , and Fi = 1 0 . We continue with steps 3.-8. and get the scalar abstract JLSS subsystems Σ̂i ,
i ∈ {1, 2} with
Âi = −2, B̂i = 1, D̂i = 0, Ĉi = 1, Êi = 0.4, R̂i = 0.1.

18

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

Simultaneously, we compute Qi = 2 and Si = −d. As already discussed in Remark 5.6, Di ∈ im Bi and we can
choose D̂i = 0. It follows that the subsystems Σ̂i , i ∈ {1, 2}, are not affected by internal inputs, which implies
that the interconnection between Σ3 (resp. Σ4 ) and Σ1 (resp. Σ2 ) is absent on the abstract interconnected
system Σ̂; compare also Figure 4 and Figure 5.
We continue with the construction of Σ̂i for i ∈ {3, 4}. We repeat the procedure and obtain


6.924 3.871 0.468
Mi = 3.871 2.534 0.315 , Ki = 0.
0.468 0.315 0.054
In step 2., we compute


1 −2 4
T
Pi =
,
1 −3 9

so that (5.13)-(5.17) hold. The equations (5.12b)-(5.12e) are satisfied by


1 0 −9 −3
,
P̂i = 6
0
4
2




GTi = 1 0 0 , and Fi = 61 6 5 1 . We follow steps 3.-8. and get the 2D abstract JLSS subsystems Σ̂i ,
i ∈ {3, 4}, where


 
 


−2 0
12
−1
Âi =
, B̂i =
, D̂i = d
, Ĉi = 1 1 ,
0 −3
−8
1
with the diffusion and reset terms again given by Êi = 0.4I2 and R̂i = 0.1I2 . Moreover, Qi = 0 and Si = 0.

For all i ∈ {1, 2, 3, 4}, equations (5.2), (5.3), and (5.7) hold. Hence, Theorem 5.3 applies and we see
that Vi (xi , x̂i ) = (xi − Pi x̂i )T Mi (xi − Pi x̂i ) is an SSF-M2 function from Σ̂i to Σi for all i ∈ [1; 4]. Moreover, (5.12) holds and Theorem 5.7 implies that all the behaviors of Σi are preserved on Σ̂i . Following the
proof of Theorem 5.3, we see that the interface function for i ∈ {1, 2} follows by (5.9) as
νiν̂i (xi , x̂i , ûi , ŵi ) = Ki (xi − Pi x̂i ) − 2x̂i − 2.5ûi − dŵi ,

(6.1)

ei = −2.5 for i ∈ {1, 2}. Although the internal
and νiν̂i ≡ 0 for i ∈ {3, 4}. Here we used (5.10) to compute R
input matrices for Σ1 and Σ2 are zero, the internal inputs ŵ1 = ŷ3 and ŵ2 = ŷ4 still appear in the interface
function. As provided in the proof of Theorem 5.3 and by fixing π = 1, the K∞ functions for i ∈ {1, 2} and
j ∈ {3, 4} are given by
αi (s) = s, ηi (s) = 2s, ρiext (s) = 0.16s, ρiint (s) = 1.3d2 s,

αj (s) = s, ηj (s) = 2s, ρjext (s) = 150s, ρjint (s) = 7.9d2 s,
for any s ∈ R≥0 .
6.3. The interconnected abstraction. We now proceed with Theorem 4.2 to construct a stochastic simulation function form Σ̂ to Σ. We start by checking the Assumption 1. Note that ρiint satisfies the triangle
ei = 2, and δij are given by
inequality and we use Remark 4.4 to see that Assumption 1 holds for γi (s) = s, λ


0
0 1.3 0

0
0 1.3
2 0
.
∆=d 
0 7.9 0
0
7.9 0
0
0
Additionally, we require the existence of a vector µ ∈ √
R4>0 satisfying (4.5), which is the case if and only if the
spectral radius of ∆ is strictly less than one, i.e., 1/2 1.3 × 7.9d2 < 1, which holds for example for d = 1/2.
One can choose the vector µ as µ = [2 2 1 1] and, hence, it follows that
V (x, x̂) =

2
X
i=1

2Vi (xi , x̂i ) +

4
X
i=3

Vi (xi , x̂i ),

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

19

is an SSF-M2 from I(Σ̂1 , Σ̂2 , Σ̂3 , Σ̂4 ) to I(Σ1 , Σ2 , Σ3 , Σ4 ) where the interface function follows from (6.1).
Following the proof of Theorem 4.2, we see that V satisfies (3.2) with α(s) = s and (3.3) with η(s) = 1.35s,
ρext (s) = 150s, and ρint ≡ 0. Here, we computed η and ρext according to (4.8a) and (4.8b). Subsequently, we
design a controller for Σ via the abstraction Σ̂. We restrict external inputs for Σ̂3 and Σ̂4 to zero, so that we
can set ρjext ≡ 0, j ∈ {3, 4}. As a result ρext reduces to ρext (s) = 0.16s, ∀s ∈ R≥0 , and we use Theorem 3.5
in combination with Remark 5.4 to derive the inequality
E[kζaν (t) − ζ̂âν̂ (t)k2 ] ≤ e−1.35t E[V (a, â)] + 0.12E[kν̂k2∞ ].

(6.2)

6.4. The deterministic system and the controller. The synthesis of the safety controller is based on
a deterministic system Σ̃ which results from Σ̂ by omitting the diffusion and reset terms. In particular, we
determinize the identical systems Σ̂14 = I(Σ̂1 , Σ̂4 ) and Σ̂23 = I(Σ̂2 , Σ̂3 ) and obtain for i ∈ {14, 23} the systems


 

−2
0 −d
0

 ˜˙

d ξ˜i (t) + 0 ν̃i (t),
ξi (t) =  0 −3
Σ̃i :
0
0 −2
1





˜
ζ̃i (t) = 1 1 0 ξi (t).
We compute an SSF-M2 function V̂ (x̂, x̃) = [x̂; x̃]T M̂ [x̂; x̃] from Σ̃ = I(Σ̃14 , Σ̃23 ) to Σ̂, by solving an appropriate LMI. The matrix M̂ results in


m1
0 −m2
0

0
m1
0 −m2 


M̂ = 

−mT2
0
m3
0
0

with

1.1400
m1 = 1.3072
0.0052

1.3072
1.6968
0.0228

−mT2

0

m3






0.0052
1.1437 1.3112 0.0060
1.1793 1.3649 0.0081
0.0228 , m2 = 1.3365 1.7181 0.0218 , m3 = 1.3649 1.7631 0.0224 .
0.0104
0.0089 0.0230 0.0085
0.0081 0.0224 0.0079

The associated K∞ functions for V̂ are given by α(r) = r, η(r) = 0.82r, ρext (r) = 0.32r, and ρint ≡ 0. Again
we use Theorem 3.5 and Remark 5.4 to establish
E[kζ̂âν̃ (t) − ζ̃ãν̃ (t)k2 ] ≤ e−0.82t E[V̂ (â, ã)] + 0.4kν̃k2∞ .

(6.3)

Next we design a safety controller to restrict the output ỹ ∈ R of Σ̃i , i ∈ {14, 23} to [0 5]. Additionally, to
2
control the mismatch between the trajectories of Σ and Σ̃, we limit the inputs to ũ ∈ [−1 1] . We fix the
sampling time to τ = 0.1 secs and use the MATLAB Toolbox MPT [HKJM13] to compute a safety controller
2
K : R6 → 2[−1 1] , which when applied in a sample-and-hold manner to Σ̃ enforces the constraints at the
sampling instances t = kτ , k ∈ N. A part of the domain of the controller, which restricts the initial states of
Σ̃ is illustrated in Figure 6. Note that K is a set-valued map that provides, for each state x̃ in the domain of
2
K, possibly a set of admissible inputs K(x) ⊆ [−1 1] .
6.5. Input trajectory generation and performance guarantees. We use the closed-loop system con˜ ζ̃, ν̃) be a trajectory of Σ̃ that satisfies K,
sisting of Σ̃ and K to generate input trajectories for Σ. Let (ξ,
˜ )) for all k ∈ N. We use
i.e., ν̃ is constant on the intervals τ [k, (k + 1)[, k ∈ N, and satisfies ν̃(kτ ) ∈ K(ξ(kτ
the interface (6.1) to compute the input trajectory ν for Σ. Using the bounds in (6.2) and (6.3), the overall
estimate between output trajectories of Σ̃ and Σ follows to

 12 
 12

 21
≤ E[kζaν (t) − ζ̂âν̃ (t)k2 ] + E[kζ̂âν̃ (t) − ζ̃ãν̃ (t)k2 ]
E[kζaν (t) − ζ̃ãν̃ (t)k2 ]
1

1

≤ e−0.67t E[V (a, â)] 2 + e−0.41t E[V̂ (â, ã)] 2 + kν̃k∞ .

(6.4)

20

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

Figure 6. Part of the domain of the safety controller. The left figure shows the projection
on x̃1 and x̃2 . The right figure shows the projection on x̃2 and x̃3 .
We show some simulation results of the controlled system in Figure 7. The initial state of Σ is fixed as
a = [1; −1; −5; 1; −1; −5; 1; −2; 1; −2]. We determine the initial state for Σ̂ as well as Σ̃ as the vector ã ∈ R6
lying in the domain of the controller and minimizing V (a, ã) which is ã = [1.44; −0.69; 1.44; −0.69; 1; 1]. We
˜ )). In the top two plots of the figure, we see a realization of the
randomly pick the input ν̃(kτ ) in K(ξ(kτ
observed process ζ1 (resp. ζ2 ) and ζ̂1 (resp. ζ̂2 ) of Σ and Σ̂, respectively. On the middle plot, we show
the corresponding evolutions of the refined input signals ν1 and ν2 for Σ. On the 2nd plot from bottom,
we show the square root of the average value (over 1000 experiments) of the squared distance in time of the
output trajectory of Σ to the one of Σ̂, namely, kζaν − ζ̂ãν̃ k2 . The solid black curve denotes the error bound
given by the right-hand-side of (6.2). On the bottom part, we show the square root of the average value
(over 1000 experiments) of the squared distance in time of the output trajectory of Σ to the set S, namely,
kζaν (t)kS . Notice that the square root of this empirical (averaged) squared distances is significantly lower
than the computed bound given by the right-hand-side of (6.4), as expected since the stochastic simulation
functions can lead to conservative bounds. (One can improve the bounds by seeking optimized stochastic
simulation functions.)
7. Summary
In this paper we proposed a compositional framework for the construction of infinite approximations of interconnected stochastic hybrid systems by leveraging some small-gain type conditions. We introduced a new
notion of stochastic simulation functions to quantify the error between the stochastic hybrid systems and their
approximations. In comparison with the similar notion in [JP09], our proposed notion of stochastic simulation functions is computationally more tractable for stochastic hybrid systems with inputs. Moreover, we
provided a constructive approach on the construction of those infinite approximations for a class of stochastic
hybrid systems, namely, jump linear stochastic systems. Finally, we illustrated the effectiveness of the results
by constructing an infinite approximation of an interconnection of four jump linear stochastic systems in a
compositional manner. We employed the constructed approximation as a substitute in the controller synthesis
scheme to enforce a safety constraint on the concrete interconnected system, would not have been possible to
enforce without the use of the approximation.

Appendix
Proof of Lemma 3.6. Lemma 3.6 is an extension of Lemma 4.4 in [LSW96] and the proof follows similar ideas.
The proof includes two steps. We first show that the set [0, s0 ], s0 := η −1 (2g), is forward invariant, i.e., if
y(t0 ) ∈ [0, s0 ], then y(t) ∈ [0, s0 ] for all t ≥ t0 . For the sake of contradiction, suppose the trajectory y visits
[0, s0 ] and then later leaves it. Due to the continuity of y, this implies that there exist a time instance t > t0
and positive value ε > 0 such that y(t0 ) = s0 and y(t) = s0 + ε, and y(τ ) ≥ s0 for all τ ∈ [t0 , t]. In view of the

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

ζ 1( t )
ζ̂ 1( t )

1
0.5
0
0

1

2

3
ζ 2( t )
ζ̂ 2( t )

1
0.5
0
0

1

2

3

q
E[kζ(t) − ζ̂(t)k2 ]

1.5
1
0.5
0
−0.5

ν 1( t )
ν 2( t )

0

1

2

3

4

5

0

1

2

3

4

5

0

1

2

3

4

5

1
0.5
0

0.02

p

E[kζ(t)k2S ]

0.04

0

t [sec]

Figure 7. Top two plots: One realization of ζ1 (resp. ζ2 ) ( ) and ζ̂1 (resp. ζ̂2 ) ( ). The
middle plot: the corresponding realization of external inputs ν1 ( ) and ν2 ( ) of Σ. The 2nd
plot from bottom: Square root of the average values (over 1000 experiments) of the squared
distance of the output trajectory of Σ to the one of Σ̂. The solid black line indicates the error
bound given by the right-hand-side of (6.2). Bottom plot: Square root of the average values
(over 1000 experiments) of the squared distance of the output trajectory of Σ to the safe set
S.

21

22

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

lemma hypothesis, we then have
0 < ε = y(t) − y(t0 ) ≤

t

Z

t0

[−η(y(τ )) + g] ≤ 0,

which concludes the first step. In the second step, we assume that y(0) > s0 . Consider the function κ : R>0 →
R defined as
Z s
−dr
κ(s) :=
.
min{η(r),
r}
1
Let ts be the first time that the process y reaches s0 , i.e., ts := inf{t ≥ 0 : y(t) ≤ s0 }.5 In the following we
show that the function

 −1
κ
κ(r) + t/2 , r > 0
ϑ(r, t) :=
(7.1)
0
r = 0,

is indeed the desired KL function for the lemma assertion. Note that for all t ∈ [0, ts ], we have η y(t) ≥ 2g,
and that we have


κ y(t) − κ y(0) =

y(t)
Z

− d(y(τ ))

≥
min{η y(τ ) , y(τ )}

y(0)

Zt
0



Zt 1
η y(τ ) − g
t
2 η y(τ )

dτ ≥
dτ ≥ .
2
min{η y(τ ) , y(τ )}
η y(τ )
0

The above observation together with the fact that the function κ is strictly decreasing on (0, ∞) imply that



y(t) ≤ κ−1 κ y(0) + t/2 ,
∀t ∈ [0, ts ].
Note that lims↓0 κ(s) = ∞, and since κ is strictly decreasing on (0, ∞), the function ϑ(r, t) defined in (7.1) is
a K∞ function in the first argument for each t, and decreasing with respect to the second argument for each
nonzero r. As such, the function ϑ(r, t) is a KL function. Combining the results of the two steps concerning
the intervals [0, ts ] and (ts , ∞) concludes the desired assertion.

Proof of Theorem 3.5. For any time instances t ≥ t0 ≥ 0, any ν̂(t) ∈ Rm̂ , any ω̂(t) ∈ Rp , and any random
variable a and â that are F0 -measurable, there exists ν(t) ∈ Rm such that for all ω(t) ∈ Rp , one obtains


Z t
h
i

E V (ξaνω (t), ξˆâν̂ ω̂ (t)) = E V ξaνω (t0 ), ξˆâν̂ ω̂ (t0 ) +
LV (ξaνω (s), ξˆâν̂ ω̂ (s)) d s
t0

Z t

h

i

≤ E V ξaνω (t0 ), ξˆâν̂ ω̂ (t0 ) + E
−η V ξaνω (s), ξˆâν̂ ω̂ (s) + ρext (kν̂(s)kk ) + ρint (kω(s) − ω̂(s)kk ) d s
t0

Z t
h
 h
h
i
i
i 
ˆ
≤ E V ξaνω (t0 ), ξâν̂ ω̂ (t0 ) +
−η E V ξaνω (s), ξˆâν̂ ω̂ (s)
+ E ρext (kν̂kk∞ ) + ρint (kω − ω̂kk∞ ) d s,
t0

where the first equality is an application of the Itô’s formula for jump diffusions thanks to the polynomial rate
of the function V [ØS05, Theorem 1.24], and the last inequality follows from Jensen’s inequality
due to the con

vexity assumption on the function η [Oks02, p. 310]. Let us define the process y(t) := E V (ξaνω (t), ξˆâν̂ ω̂ (t)) .
Note that in view of the Itô’s formula, the process y(·) is continuous provided that the solution processes ξaνω
and ξˆâν̂ ω̂ have finite moments. This is indeed the case under our model setting in Definition 2.1, in particular
due to the Lipschitz continuity of functions f, σ, r, fˆ, σ̂, r̂ [ØS05, 1.19]. Therefore, the process y(t) meets all
the required assumptions of Lemma 3.6, implying that there exists a KL function ϑ such that
 


E[V (ξaνω (t),ξˆâν̂ ω̂ (t))] ≤ ϑ E[V (a, â)], t + η −1 2E ρext (kν̂kk∞ ) + ρint (kω − ω̂kk∞ ) .
(7.2)
5By convention, inf ∅ = ∞.

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

23

In view of Jensen’s inequity and using equation (3.2), the convexity of α and the concavity of ρext , ρint , we
have
i
h
i
h 
 

α E kζaνω (t) − ζ̂âν̂ ω̂ (t)kk ≤ E α kζaνω (t) − ζ̂âν̂ ω̂ (t)kk ≤ E V (ξaνω (t), ξˆâν̂ ω̂ (t))




≤ ϑ E[V (a, â)], t + η −1 2ρext E[kν̂kk∞ ] + 2ρint E[kω − ω̂kk∞ ] ,
which in conjunction with the fact that α ∈ K∞ leads to


h
i




k
−1
−1
k
k
E kζaνω (t) − ζ̂âν̂ ω̂ (t)k ≤ α
2ρext E[kν̂k∞ ] + 2ρint E[kω − ω̂k∞ ]
ϑ E[V (a, â)], t + η







≤ α−1 2ϑ E[V (a, â)], t + α−1 2η −1 4ρext E[kν̂kk∞ ] + α−1 2η −1 4ρint E[kω − ω̂kk∞ ]
.
Therefore, by introducing functions β, γext , and γint as

β(r, t) := α−1 2ϑ(r, t) ,


γext (r) := α−1 2η −1 4ρext (r) ,


γint (r) := α−1 2η −1 4ρint (r) ,

(7.3)

inequality (3.4) is satisfied. Note that if α−1 and η −1 satisfies the triangle inequality (i.e., α−1 (a + b) ≤
α−1 (a) + α−1 (b) and η −1 (a + b) ≤ η −1 (a) + η −1 (b) for all a, b ∈ R≥0 ), one can divide all the coefficients by
factor 2 in the expressions of β, γext , and γint in (7.3) to get a less conservative upper bound in (3.4).

Proof of Proposition 3.7. Since V is an SSF-Mk function from Σ̂ to Σ and η(r) ≥ θr for some θ ∈ R>0 and
any r ∈ R≥0 , for any ν̂ ∈ Û, any ω̂ ∈ W, and any random variable a and â that are F0 -measurable, there
exists ν ∈ U such that for all ω ∈ W one obtains:




LV ξaνω (t), ξˆâν̂ ω̂ (t) ≤ − θV ξaνω (t), ξˆâν̂ ω̂ (t) + ρext (kν̂kk∞ ) + ρint (kω − ω̂kk∞ ).
Since there exists a constant  ≥ 0 such that  ≥ ρext (kν̂kk∞ ) + ρint (kω − ω̂kk∞ ), one obtains:




LV ξaνω (t), ξˆâν̂ ω̂ (t) ≤ − θV ξaνω (t), ξˆâν̂ ω̂ (t) + ,
and the following chain of inequalities hold:




P sup ζaνω (t) − ζ̂âν̂ ω̂ (t) ≥ ε | [a; â] =P sup α ζaνω (t) − ζ̂âν̂ ω̂ (t)
0≤t≤T

0≤t≤T


≤P

k



≥ α(εk ) | [a; â]




sup V ξaνω (t), ξˆâν̂ ω̂ (t) ≥ α(εk ) | [a; â] .

(7.4)



(7.5)

0≤t≤T

Using inequalities (7.4), (7.5), and Theorem 1 in [Kus67, Chapter III], one obtains the inequalities (3.5) and
(3.6).

Proof of Proposition 3.8. The proof is a simple consequence of Theorem 3.5 and Markov inequality [Oks02],
used as the following:
 h
i k1
n
o E[kζ (t) − ζ̂ (t)k]
E kζaνω (t) − ζ̂âν̂ ω̂ (t)kk
aνω
âν̂ ω̂
P kζaνω (t) − ζ̂âν̂ ω̂ (t)k ≥ ε ≤
≤
(7.6)
ε
ε
1
β (E[V (a, â)], t) + γext (E[kν̂kk∞ ]) + γint (E[kω − ω̂kk∞ ]) k
≤
.
ε


24

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

Proof of Corollary 3.9. Since V is an SSF-Mk function from Σ̂ to Σ, for ν̂ ≡ 0 and any random variable a and
â that are F0 -measurable, there exists ν ∈ U such that one obtains:


 

LV ξaν (t), ξˆâ0 (t) ≤ − η V ξaν (t), ξˆâ0 (t) ,


implying that V ξaν (t), ξˆâ0 (t) is a nonnegative supermartingale [Oks02, Appendix C]. As a result, we have
the following chain of inequalities:






k
> α(εk ) | [a; â]
sup α ζaν (t) − ζ̂â0 (t)
P
sup ζaν (t) − ζ̂â0 (t) > ε | [a; â] =P
0≤t<∞

0≤t<∞





V (a, â)
k
ˆ
≤P
sup V ξaν (t), ξâ0 (t) > α(ε ) | [a; â] ≤
,
α(εk )
0≤t<∞


where the last inequality is implied from V (ξaν (t), ξˆâ0 (t)) being a nonnegative supermartingale and [Kus67,
Lemma1].

Proof of Lemma 5.1. Consider the jump linear stochastic system Σ with a linear feedback control law u = Kx,
where K ∈ Rm×n , satisfying
d ξ(t) = (A + BK)ξ(t) d t + Eξ(t) d Wt +

qe
X

Ri ξ(t) d Pti .

i=1
T

Define the matrix-valued deterministic process Φ(t) := E[ξ(t)ξ (t)]. Applying the Itô’s formula for jump
diffusions [ØS05] leads to the following differential equations describing the time-evolution of the deterministic
process Φ(t):
Φ̇(t) = A + BK +

qe
X
i=1

qe
qe
X
X

T
λi Ri Φ(t) + Φ(t) A + BK +
λi Ri + EΦ(t)E T +
λi Ri Φ(t)RiT .
i=1

(7.7)

i=1

To see further details on how the above ODE is derived, one can view each element of the matrix Φ(t) as
an R-valued mapping and treat it in the same way as we considered the Lyapunov function in the proof
of Theorem 5.3, and consequently arrives at (7.7). From linear system theory, one can readily check that
the ODE in (7.7) is asymptotically stable (implying Σ is mean square asymptotically stable) if and only if
V (Φ(t)) = Tr(M Φ(t)) = E[ξ(t)T M ξ(t)] is a Lyapunov function for (7.7) for a positive definite matrix M
satisfying condition (5.3), which completes the proof.

Proof of Lemma 5.9. Suppose that im D 6⊆ im P +im B, then there exists w ∈ Rp so that Dw 6= P x̂−Bu holds
for all x̂ ∈ Rn̂ , u ∈ Rm . Hence (5.7b) cannot hold for any matrix D̂ and S. Now suppose im D ⊆ im P + im B.
Let ei denote the columns of Ip . Then there exist dˆi ∈ Rn̂ and si ∈ Rm so that Dei = P dˆi − Bsi holds for all
i ∈ {1, . . . , p} and the matrices D̂ = [dˆ1 . . . dˆp ] and S = [s1 . . . sp ] satisfy (5.7b).

References
[Aba09]
[BK08]
[BM92]
[Bor89]
[BV09]
[DIW11]

A. Abate. A contractivity approach for probabilistic bisimulations of diffusion processes. In Proceedings of 48th IEEE
Conference on Decision and Control, pages 2230–2235, December 2009.
C. Baier and J. P. Katoen. Principles of model checking. The MIT Press, April 2008.
G. Basile and G. Marro. Controlled and conditioned invariants in linear system theory. Prentice Hall Englewood
Cliffs, 1992.
V.S. Borkar. Optimal control of diffusion processes. Pitman research notes in mathematics series. Longman Scientific
& Technical, 1989.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2009.
S. Dashkovskiy, H. Ito, and F. Wirth. On a small gain theorem for iss networks in dissipative lyapunov form. European
Journal of Control, 17(4):357–365, 2011.

APPROXIMATIONS OF STOCHASTIC HYBRID SYSTEMS: A COMPOSITIONAL APPROACH

25

[GL04]

W. Glover and J. Lygeros. A stochastic hybrid model for air traffic control simulation. In R. Alur and G. J. Pappas,
editors, Hybrid Systems: Computation and Control, volume 2993 of Lecture Notes in Computer Science, pages
372–386. Springer Berlin Heidelberg, March 2004.
[GP09]
A. Girard and G. J. Pappas. Hierarchical control system design using approximate simulation. Automatica, 45(2):566–
571, 2009.
[Hes04]
J. P. Hespanha. Stochastic hybrid systems: Application to communication networks. In R. Alur and G. J. Pappas,
editors, Hybrid Systems: Computation and Control, volume 2993 of Lecture Notes in Computer Science, pages
387–401. Springer Berlin Heidelberg, March 2004.
[HKJM13] M. Herceg, M. Kvasnica, C. N. Jones, and M. Morari. Multi-Parametric Toolbox 3.0. In Proc. of the European Control
Conference, pages 502–510, 2013.
[HWS04] J. Hu, W. C. Wu, and S. Sastry. Modeling subtilin production in bacillus subtilis using stochastic hybrid systems.
In R. Alur and G. J. Pappas, editors, Hybrid Systems: Computation and Control, volume 2993 of Lecture Notes in
Computer Science, pages 417–431. Springer Berlin Heidelberg, March 2004.
[JP09]
A. A. Julius and G. J. Pappas. Approximations of stochastic hybrid systems. IEEE Transaction on Automatic Control,
54(6):1193–1203, 2009.
[KS91]
I. Karatzas and S. E. Shreve. Brownian Motion and Stochastic Calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2nd edition, 1991.
[Kus67]
H. J. Kushner. Stochastic stability and control. ser. Mathematics in Science and Engineering. New York: Academic
Press, 1967.
[LAB09]
M. Lahijanian, S. B. Andersson, and C. Belta. A probabilistic approach for control of a stochastic system from LTL
specifications. In Proceedings of 48th IEEE Conference on Decision and Control, pages 2236–2241, 2009.
[LSW96]
Y. Lin, E. D. Sontag, and Y. Wang. A smooth converse lyapunov theorem for robust stability. SIAM Journal on
Control and Optimization, 34:124–160, 1996.
[MPS95]
O. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for timed systems. In E. W. Mayr and
C. Puech, editors, Symposium on Theoretical Aspects of Computer Science, volume 900 of LNCS, pages 229–242.
Springer-Verlag, 1995.
[Oks02]
B. K. Oksendal. Stochastic differential equations: An introduction with applications. Springer, 5th edition, November
2002.
[ØS05]
Bernt Øksendal and Agnès Sulem. Applied Stochastic Control of Jump Diffusions. Universitext. Springer-Verlag,
Berlin, 2005.
[PAV+ 13] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler, and P. A. Parrilo. SOSTOOLS version 3.00
sum of squares optimization toolbox for MATLAB. arXiv: 1310.4716, October 2013.
[RZ15]
M. Rungger and M. Zamani. Compositional construction of approximate abstractions. In Proceedings of the 18th
International Conference on Hybrid Systems: Computation and Control, pages 68–77. ACM New York, NY, USA,
April 2015.
[SH10]
A. Singh and J. P. Hespanha. Stochastic hybrid systems for studying biochemical processes. Philosophical Transactions
of the Royal Society, 368(1930):4995–5011, November 2010.
[TI08]
Y. Tazaki and J. Imura. Bisimilar finite abstractions of interconnected systems. In Proc. of the 11th Int. Conf. on
Hybrid Systems: Computation and Control, pages 514–527. Springer, 2008.
[You12]
W. H. Young. On classes of summable functions and their fourier series. Proceedings of the Royal Society of London
A: Mathematical, Physical and Engineering Sciences, 87(594):225–229, 1912.
[ZA14]
M. Zamani and A. Abate. Approximately bisimilar symbolic models for randomly switched stochastic systems. Systems
and Control Letters, 69:38–46, July 2014.
[ZAG15]
M. Zamani, A. Abate, and A. Girard. Symbolic models for stochastic switched systems: A discretization and a
discretization-free approach. Automatica, 55:183–196, May 2015.
[Zam14]
M. Zamani. Compositional approximations of interconnected stochastic hybrid systems. In Proceedings of the 53rd
IEEE Conference on Decision and Control, pages 3395–3400, December 2014.
[ZMAL12] M. Zamani, P. Mohajerin Esfahani, A. Abate, and J. Lygeros. Symbolic models for stochastic control systems without
stability assumptions. Submitted for publication., 2012.
[ZMM+ 14] M. Zamani, P. Mohajerin Esfahani, R. Majumdar, A. Abate, and J. Lygeros. Symbolic control of stochastic systems
via approximately bisimilar finite abstractions. IEEE Transactions on Automatic Control, Special Issue on Control
of Cyber-Physical Systems, 59(12):3135–3150, December 2014.
[ZTA14]
M. Zamani, I. Tkachev, and A. Abate. Bisimilar symbolic models for stochastic control systems without state-space
discretization. In Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control,
pages 41–50. ACM New York, NY, USA, April 2014.

1 Department

of Electrical and Computer Engineering, Technische Universität München, D-80290 Munich, Germany.

E-mail address: {zamani,matthias.rungger}@tum.de
URL: http://www.hcs.ei.tum.de

26

M. ZAMANI, M. RUNGGER, AND P. MOHAJERIN ESFAHANI

2 Automatic

Control Laboratory at ETH Zürich and the Risk Analytics and Optimization Chair at ETH Lausanne,
Switzerland.
E-mail address: mohajerin@control.ee.ethz.ch
URL: http://control.ee.ethz.ch/∼peymanm

