Compositional Abstractions of Interconnected Discrete-Time
Stochastic Control Systems

arXiv:1709.10312v1 [] 29 Sep 2017

Abolfazl Lavaei, Sadegh Esmaeil Zadeh Soudjani, Rupak Majumdar, and Majid Zamani
Abstract— This paper is concerned with a compositional approach for constructing abstractions of interconnected discretetime stochastic control systems. The abstraction framework
is based on new notions of so-called stochastic simulation
functions, using which one can quantify the distance between
original interconnected stochastic control systems and their
abstractions in the probabilistic setting. Accordingly, one can
leverage the proposed results to perform analysis and synthesis
over abstract interconnected systems, and then carry the
results over concrete ones. In the first part of the paper, we
derive sufficient small-gain type conditions for the compositional quantification of the distance in probability between
the interconnection of stochastic control subsystems and that
of their abstractions. In the second part of the paper, we
focus on the class of discrete-time linear stochastic control
systems with independent noises in the abstract and concrete
subsystems. For this class of systems, we propose a computational scheme to construct abstractions together with their
corresponding stochastic simulation functions. We demonstrate
the effectiveness of the proposed results by constructing an
abstraction (totally 4 dimensions) of the interconnection of four
discrete-time linear stochastic control subsystems (together 100
dimensions) in a compositional fashion.

I. I NTRODUCTION
Large-scale interconnected systems have received significant attentions in the last few years due to their presence in
real life systems including power networks, air traffic control,
and so on. Each complex real-world system can be regarded
as an interconnected system composed of several subsystems.
Since these large-scale network of systems are inherently difficult to analyze and control, one can develop compositional
schemes to employ the abstractions of the given systems as a
replacement in the controller design process. In other words,
in order to overcome the computational complexity in largescale interconnected systems, one can abstract the original
concrete system by a simpler one with lower dimension.
Those abstractions 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 controller synthesis detour.
In the past few years, there have been several results on the
construction of (in)finite abstractions for stochastic systems.
Existing results include infinite approximations for a class of
stochastic hybrid systems [1] and finite approximations for
discrete-time stochastic models with continuous state spaces
[2], [3], [4]. Construction of finite bisimilar abstractions for
stochastic control systems is proposed in [5], [6]. Recent
results address stochastic switched systems [7], [8] and
This work was supported in part by the German Research Foundation
(DFG) through the grant ZA 873/1-1.
A. Lavaei and M. Zamani are with the Department of Electrical and Computer Engineering, Technical University of Munich, D-80290 Munich, Germany. S. Esmaeil Zadeh Soudjani and R. Majumdar are with the Max Planck
Institute for Software Systems, Kaiserslautern 67663, Germany. Email:
{lavaei,zamani}@tum.de, {sadegh,rupak}@mpi-sws.org.

propose compositional construction of infinite abstractions
of continuous-time stochastic control systems [9], [10] using
small-gain type compositional reasoning.
In this paper, we provide a compositional approach for
the construction of infinite abstractions of interconnected
discrete-time stochastic control systems. Our abstraction
framework is based on a new notion of so-called stochastic
simulation functions under which an abstraction, which is
itself a discrete-time stochastic control system with lower
dimension, performs as a substitute in the controller design
process. The stochastic simulation function is leveraged to
quantify the error in probability in this controller synthesis
scheme. As a consequence, one can use the proposed results here to solve particularly safety/reachability problems
over the abstract interconnected systems and then carry the
results over the concrete interconnected ones. It should be
noted that the existing compositional results in [9], [10] are
for continuous-time stochastic systems and assume that the
noises in the concrete and abstract systems are the same,
which means the abstraction has access to the noise of the
concrete system, which is a strong assumption. In this paper,
we do not have such an assumption meaning that the noises
of the abstraction can be completely independent of that of
the concrete system.
II. D ISCRETE -T IME S TOCHASTIC C ONTROL S YSTEMS
A. Preliminaries
We consider a probability space (Ω, FΩ , PΩ ), where Ω is
the sample space, FΩ is a sigma-algebra on Ω comprising
subsets of Ω as events, and PΩ is a probability measure
that assigns probabilities to events. We assume that random
variables introduced in this article are measurable functions
of the form X : (Ω, FΩ ) → (SX , FX ). Any random variable
X induces a probability measure on its space (SX , FX ) as
P rob{A} = PΩ {X −1 (A)} for any A ∈ FX . We often directly discuss the probability measure on (SX , FX ) without
explicitly mentioning the underlying probability space and
the function X itself.
A topological space S is called a Borel space if it is
homeomorphic to a Borel subset of a Polish space (i.e., a
separable and completely metrizable space). Examples of a
Borel space are the Euclidean spaces Rn , its Borel subsets
endowed with a subspace topology, as well as hybrid spaces.
Any Borel space S is assumed to be endowed with a Borel
sigma-algebra, which is denoted by B(S). We say that a map
f : S → Y is measurable whenever it is Borel measurable.
B. Notation
The following notation is used throughout the paper. We
denote the set of nonnegative integers by N := {0, 1, 2, . . .}
and the set of positive integers by Z+ := {1, 2, 3, . . .}. The
symbols R, R>0 , and R≥0 denote the set of real, positive, and

nonnegative real numbers, respectively. Given a vector x ∈
Rn , kxk denotes the Euclidean norm of x. The symbols In
and 1n denote the identity matrix in Rn×n , and the vector in
Rn with all its elements to be one, respectively. We denote by
diag(a1 , . . . , aN ) a diagonal matrix in RN ×N with diagonal
matrix entries a1 , . . . , aN starting from the upper left corner.
Given functions fi : XQ
. . . , N },
i → Yi , for
QNany i ∈ {1,
QN
N
their Cartesian product i=1 fi : i=1 Xi → i=1 Yi is
Q
defined as ( N
i=1 fi )(x1 , . . . , xN ) = [f1 (x1 ); . . . ; fN (xN )].
For any set A we denote by AN the Cartesian
product of a
Q∞
countable number of copies of A, i.e., AN = k=0 A. Given
a measurable function f : N → Rn , the (essential) supremum
of f is denoted by kf k∞ := (ess)sup{kf (k)k, k ≥ 0}. A
+
function γ : R+
0 → R0 , is said to be a class K function if
it is continuous, strictly increasing, and γ(0) = 0. A class
K function γ(·) is said to be a class K∞ if γ(r) → ∞ as
r → ∞.
C. Discrete-Time Stochastic Control Systems
We consider stochastic control systems in discrete time
(dt-SCS) defined over a general state space adopted from
[11] and characterized by the tuple
Σ = (X, W, U, {U (x, ω)|x ∈ X, ω ∈ W }, Y, Tx , h) ,

(1)

where X is a Borel space as the state space of the system.
We denote by (X, B(X)) the measurable space with B(X)
being the Borel sigma-algebra on the state space. Sets W
and U are Borel spaces as the internal and external input
spaces of the system. The set {U (x, ω)|x ∈ X, ω ∈ W }
is a family of non-empty measurable subsets of U with the
property that
K := {(x, ω, ν) : x ∈ X, ω ∈ W, ν ∈ U (x)}
is measurable in X × W × U . Intuitively, U (x, ω) is the set
of inputs that are feasible at state x ∈ X with the internal
input ω ∈ W . Set Y is a Borel space as the output space
of the system. Map Tx : B(X) × X × W × U → [0, 1], is
a conditional stochastic kernel that assigns to any x ∈ X,
ω ∈ W and ν ∈ U (x, ω) a probability measure Tx (·|x, ω, ν)
on the measurable space R(X, B(X)) so that for any set
A ∈ B(X), Px,ω,ν (A) = A Tx (dx̄|x, ω, ν), where Px,ω,ν
denotes the conditional probability P(·|x, ω, ν). Finally, h :
X → Y is a measurable function that maps a state x ∈ X
to its output y = h(x) ∈ Y .
Given the dt-SCS in (1), we are interested in Markov
policies to control the system.
Definition 2.1: A Markov policy for the dt-SCS Σ in (1)
is a sequence ρ = (ρ0 , ρ1 , ρ2 , . . .) of universally measurable
stochastic kernels ρn [12], each defined on the input space
U given X × W and such that for all (xn , ωn ) ∈ X ×
W , ρn (U (xn , ωn )|(xn , ωn )) = 1. The class of all Markov
policies is denoted by ΠM .
For given inputs ω(·), ν(·), the stochastic kernel Tx captures the evolution of the state of the system. This kernel
features an equivalent dynamical representation: there exists
a measurable function fa : X × W × U × Vς → X such that
the evolution of the state of the system can be written as
x(k + 1) = fa (x(k), ω(k), ν(k), ς(k)),
where {ς(k) : Ω → Vς , k ∈ N} is a sequence of independent
and identically distributed (i.i.d.) random variables on the set

Vς . In this paper we assume that the state space X is a subset
of Rn and are interested in the specific form of the function
fa (x, ω, ν, ς) = f (x, ω, ν) + g(x)ς.
Therefore, the dt-SCS Σ in (1) can be described as:

x(k + 1) = f (x(k), ω(k), ν(k)) + g(x(k))ς(k),
Σ:
y(k) = h(x(k)),
(2)
for any x(k) ∈ X, ω(k) ∈ W, and ν(k) ∈ U (x(k), ω(k)).
Note that Tx in (1) contains the information of functions f
and g and the distribution of noise ς(·) in the dynamical
representation (2).
For the sake of simplicity, we also assume that the set of
valid inputs is the whole input space: U (x, ω) = U for all
x ∈ X and ω ∈ W , but the obtained results are generally
applicable. We associate respectively to U and W the sets U
and W to be collections of sequences {ν(k) : Ω → U, k ∈
N} and {ω(k) : Ω → W, k ∈ N}, in which ν(k) and ω(k)
are independent of ς(t) for any k, t ∈ N and t ≥ k.
For any initial state a ∈ X, ν(·) ∈ U, and ω(·) ∈ W,
the random sequences xaων : Ω × N → X and yaων : Ω ×
N → Y that satisfy (2) are called respectively the solution
process and output trajectory of Σ under external input ν,
internal input ω and initial state a. We here call the tuple
(ω, ν, xaων , yaων ) a trajectory of Σ.
III. S TOCHASTIC P SEUDO -S IMULATION AND
S IMULATION F UNCTIONS
In this section we first introduce a notion of so-called
pseudo-simulation functions for the discrete-time stochastic
control systems with both internal and external inputs and
then define the stochastic simulation functions for systems
with only external input. These definitions can be used to
quantify closeness of two dt-SCS with the same internal input
and output spaces.
Definition 3.1: Consider dt-SCS Σ = (X, W, U, Y, Tx , h)
b = (X̂, W, Û , Y, T̂x , ĥ) with the same internal input
and Σ
and output spaces. A function V : X × X̂ → R≥0 is called
b to Σ
a stochastic pseudo-simulation function (SPSF) from Σ
if
• ∃α ∈ K∞ such that
∀x ∈ X, ∀x̂ ∈ X̂,
•

α(kh(x) − ĥ(x̂)k) ≤ V (x, x̂), (3)

∀x ∈ X, x̂ ∈ X̂, ν̂ ∈ Û , and ∀ω̂ ∈ Ŵ , ∃ν ∈ U such
that ∀ω ∈ W
h
E V (x(k + 1), x̂(k + 1)) x(k), x̂(k), ω(k) = ω,
i
, ω̂(k) = ω̂, ν(k) = ν, ν̂(k) = ν̂ − V (x(k), x̂(k)) ≤

−κ(V (x(k), x̂(k)))+ρint (kω − ω̂k)+ρext(kν̂k)+ψ,
(4)

for some κ ∈ K, ρint , ρext ∈ K∞ ∪ {0}, and ψ ∈ R≥0 .
b PS Σ if there exists a pseudoWe utilize notation Σ
b to Σ, in which control system
simulation function V from Σ
b
Σ is considered as an abstraction of concrete (original)
system Σ. The second condition above implies implicitly
existence of a function ν = νν̂ (x, x̂, ν̂, ω̂) for satisfaction
of (4). This function is called the interface function and can

b to a policy ν
be used to refine a synthesized policy ν̂ for Σ
for Σ.
In this paper we study interconnected discrete-time
stochastic control systems without internal inputs, resulting
from the interconnection of discrete-time stochastic control
subsystems having both internal and external signals. In
this case, the interconnected dt-SCS reduces to the tuple
(X, U, Y, Tx , h). Thus we modify the above notion for systems without internal inputs.
Definition 3.2: Consider two dt-SCS Σ = (X, U, Y, Tx , h)
b = (X̂, Û , Y, T̂x , ĥ) with the same output spaces. A
and Σ
function V : X × X̂ → R≥0 is called a stochastic simulation
b to Σ if
function (SSF) from Σ
• ∃α ∈ K∞ such that
∀x ∈ X, ∀x̂ ∈ X̂,

α(kh(x) − ĥ(x̂)k) ≤ V (x, x̂), (5)

∀x ∈ X, x̂ ∈ X̂, ν̂ ∈ Û , ∃ν ∈ U such that
h
i
E V (x(k+1), x̂(k+1)) x(k), x̂(k), ν(k)=ν, ν̂(k)=ν̂

•

−V (x(k), x̂(k)) ≤−κ(V (x(k), x̂(k)))+ρext (kν̂k)+ψ,
(6)

for some κ ∈ K, ρext ∈ K∞ ∪ {0}, and ψ ∈ R≥0 .
The next theorem shows usefulness of SSF in comparing
output trajectories of two dt-SCS in a probabilistic sense.
b be two dt-SCS with the same
Theorem 3.3: Let Σ and Σ
b to Σ, and
output spaces. Suppose V is an SSF from Σ
there exists a constant 0 < κ
b < 1 such that the function
κ ∈ K in (6) satisfies κ(r) ≥ κ
br ∀r ∈ R≥0 . For any
external input trajectory ν̂(·) ∈ Û that preserves Markov
b and for any random variables
property for the closed-loop Σ,
a and â as the initial states of the two dt-SCS, there exists
an input trajectory ν(·) ∈ U of Σ through the interface
function associated with V such that the following inequality
holds provided that there exists a constant ψb ≥ 0 satisfying
ψb ≥ ρext (kν̂k∞ ) + ψ:
P



sup kyaν (k) − ŷâν̂ (k)k ≥ ε | [a; â]

0≤k≤T



(7)




T
b
1 − 1 − V (a,â) 1 − ψb
if α (ε) ≥ ψbκ ,
α(ε)
α(ε)

 b 
≤ 
b
ψ
 V (a,â) (1−b
κ)T + κbα(ε)
(1−(1−b
κ)T ) if α (ε) < ψbκ .
α(ε)
b to Σ, we have
Proof: Since V is an SSF from Σ


P
sup kyaν (k) − ŷâν̂ (k)k ≥ ε | [a; â]
0≤k≤T


=P
sup α (kyaν (k) − ŷâν̂ (k)k) ≥ α(ε) | [a; â]
0≤k≤T


≤P
sup V (xaν (k), x̂âν̂ (k)) ≥ α(ε) | [a; â] . (8)
0≤k≤T

The equality holds due to α being a K∞ function. The
inequality is also true due to condition (5) on the SSF V .
The results follows by applying Theorem 3 in [13, pp. 81]
to (8) and utilizing inequality (6).
The results shown in Theorem 3.3 provide closeness of
output behaviours of two systems in finite-time horizon. We

can extend the result to infinite-time horizon provided that
constant ψ̂ = 0 as the following.
b be two dt-SCS with the same
Corollary 3.4: Let Σ and Σ
b to Σ such that
output spaces. Suppose V is an SSF from Σ
ρext (·) ≡ 0 and ψ = 0. For any external input trajectory
b
ν̂(·) ∈ Û preserving Markov property for the closed-loop Σ,
and for any random variables a and â as the initial states
of the two dt-SCS, there exists ν(·) ∈ U of Σ through the
interface function associated with V such that the following
inequality holds:


V (a, â)
.
P
sup kyaν (k) − ŷâ0 (k)k ≥ ε | [a; â] ≤
α (ε)
0≤k<∞
b to Σ with ρext (·) ≡ 0
Proof: Since V is an SSF from Σ
and ψ = 0, for any x(k) ∈ X and x̂(k) ∈ X̂ and any
ν̂(k) ∈ Û , there exists ν(k) ∈ U such that
h
i
E V (x(k + 1), x̂(k + 1)) | x(k), x̂(k), ν(k), ν̂(k)
− V ((x(k), x̂(k)) ≤ −κ(V (x(k), x̂(k)),

(9)

showing that V (xaν (k), x̂âν̂ (k)) is a nonnegative supermartingale [14]. Following the same reasoning as in the proof
of Theorem 3.3 we have


P
sup kyaν (k) − ŷâν̂ (k)k ≥ ε | [a; â]
0≤k<∞




=P
sup α kyaν (k) − ŷâν̂ (k)k ≥ α(ε) | [a; â]
0≤k<∞


V (a, â)
≤P
sup V (xaν (k), x̂âν̂ (k)) ≥ α(ε) | [a; â] ≤
,
α(ε)
0≤k<∞
where the last inequality is due to the nonnegative supermartingale property [13].
The stochastic simulation function defined before can be
used to guarantee an upper bound on the probability of the
maximum difference in output trajectories. This idea can
be used in conjunction with stochastic safety/reachability
analysis of the systems, which is discussed next.
Suppose that V is a stochastic simulation function from
b to Σ. Then for any input strategy ν̂ of the system Σ
b
Σ
there exists an input strategy ν of Σ, such that the following
probability is bounded


P sup kyaν (k) − ŷâν̂ (k)k ≥ ε | [a; â] ≤ δ,
0≤k≤T

with δ being defined in Theorem 3.3 based on ε and T . Given
the unsafe set A1 for Σ, we can construct another set A2 ,
which is the ε neighborhood of A1 , i.e.,
A2 = {y ′ |∃y ∈ A1 , ky ′ − yk ≤ ε}.
Now, we can provide the following corollary.
b to Σ. For any
Corollary 3.5: Suppose V is an SSF from Σ
input ν̂(·) there exists ν(·) such that the following inequality
holds:
P{∃k ≤ T, yaν (k) ∈ A1 } ≤ P{∃k ≤ T, ŷâν̂ (k) ∈ A2 }+δ.
Proof: Denote the events E1 := {∃k ≤ T, yaν (k) ∈
A1 } and E2 := {∃k ≤ T, ŷâν̂ (k) ∈ A2 }. Then we have

P{E1 } = P{E1 ∩ E2 } + P{E1 ∩ E¯2 } ≤ P{E2 } + P{E1 ∩ Ē2 },

where Ē2 is the complement of E2 . Notice that the term
P{E1 ∩ Ē2 } is bounded by δ due to the above results, which
concludes the proof.
IV. C OMPOSITIONAL A BSTRACTIONS
I NTERCONNECTED S YSTEMS

κi (s) ≥ λi γi (s)
hji ≡ 0 =⇒ δij = 0 and

FOR

Here, we first provide a formal definition of interconnection between discrete-time stochastic control systems.
A. Interconnected Stochastic Control Systems
Consider a complex stochastic control system Σ composed
of N ∈ N≥1 stochastic control subsystems Σi interconnected
with each other as follows:
Σi = (Xi , Wi , Ui , Yi , Txi , hi ), i ∈ [1; N ],
with partitioned internal inputs and outputs


ωi = ωi1 ; . . . ; ωi(i−1) ; ωi(i+1) ; . . . ; ωiN ,
yi = [yi1 ; . . . ; yiN ],

(10)

and also output space and function
hi (xi ) = [hi1 (xi ); . . . ; hiN (xi )],
Yi =

N
Y

Yij .

Assumption 1: For any i, j ∈ [1; N ], i 6= j, there exist
K∞ functions γi and constants λi ∈ R>0 and δij ∈ R≥0
such that for any s ∈ R≥0

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

µT (−Λ + ∆) < 0
(11)

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 control systems. In
particular, we assume that the dimension of ωij is equal
to the dimension of yji . If there is no connection from
stochastic control subsystem Σi to Σj , then we assume that
the connecting output function is identically zero for all
arguments, i.e., hij ≡ 0. Now, we define the interconnected
stochastic control systems as the following.
Definition 4.1: Consider N ∈ N≥1 stochastic control
subsystems Σi = (Xi , Wi , Ui , Yi , Txi , hi ), i ∈ [1; N ], with
the input-output configuration as in (10) and (11). The interconnection of Σi for any i ∈ [1, . . . , N ], is the interconnected
stochastic control system Σ = (X,
Y, Tx , h), denoted
QU,
QN by
N
I(Σ1 , . . . , ΣN ), such that X := i=1 Xi , U := i=1 Ui ,
QN
function fa := i=1 fai , characterizing the stochastic kernel
QN
Tx based on those of subsystems (i.e. fai ), Y := i=1 Yii ,
QN
and h = i=1 hii , subjected to the following constraint:
(12)

B. Compositional Abstractions of Interconnected Systems
This subsection contains one of the main contributions of
the paper. We assume that we are given N stochastic control
subsystems
Σi = (Xi , Wi , Ui , Yi , Txi , hi ),
bi =
together with their corresponding abstractions Σ
b i to Σi . For
(X̂i , Wi , Ûi , Yi , T̂xi , ĥi ) with SPSF Vi from Σ
providing the main compositionality result of the paper, we
raise the following assumption.

(15)

where κi , αj , and ρiint represent the corresponding K and
K∞ functions of Vi appearing in Definition 3.1. Prior to presenting the next theorem, we define Λ := diag(λ1 , . . . , λN ),
→
∆ := {δij }, where δii = 0 ∀i ∈ [1; N ], and Γ( s ) :=
→
[γ1 (s1 ); . . . ; γN (sN )], where s = [s1 ; . . . ; sN ]. In the next
theorem, we leverage a small-gain type condition to quantify
the error between the interconnection of stochastic control
subsystems and that of their abstractions in a compositional
way.
Theorem 4.2: Consider the interconnected stochastic control system Σ = I(Σ1 , . . . , ΣN ) induced by N ∈ N≥1
stochastic control subsystems Σi . Suppose that each stochasb i with the
tic control subsystem Σi admits an abstraction Σ
corresponding SPSF Vi . If Assumption 1 holds and there
exists a vector µ ∈ RN
>0 such that the inequality
(16)

is also met, then

j=1

ωij = yji ∀i, j ∈ [1; N ], i 6= j.

(13)
(14)

V (x, x̂) :=

N
X

µi Vi (xi , x̂i )

i=1

b = I(Σ
b 1, . . . , Σ
b N ) to Σ =
is an SSF function from Σ
I(Σ1 , . . . , ΣN ).
The proof is similar to that of Theorem 4.5 in [9], and is
omitted here due to lack of space.
V. D ISCRETE -T IME L INEAR S TOCHASTIC C ONTROL
S YSTEMS
In this section, we focus on a class of discrete-time linear
stochastic control systems, defined as follows:

x(k + 1) = Ax(k) + Bν(k) + Dω(k) + F ς(k),
Σ:
y(k) = Cx(k),
(17)
where the additive noise ς(k) is a sequence of independent
random vectors with multivariate standard normal distributions. We use the tuple Σ = (A, B, C, D, F ) to refer to the
class of systems in (17). Here, we provide conditions under
which a candidate V is an SPSF function facilitating the
construction of an abstraction Σ̂.
Let us assume that there exist matrix K and positive
definite matrix M such that the matrix inequalities
C T C  M,
(18)


(1 + π)(A + BK)T M (A + BK) − M  −b
κM, (19)
hold for some positive constants π and 0 < κ
b < 1. We
employ the following quadratic SPSF
V (x, x̂) = (x − P x̂)T M (x − P x̂),

(20)

where P ∈ Rn×n̂ is a matrix of appropriate dimension.
Assume that the equalities
AP
D
CP

=
=
=

P Â − BQ
P D̂ − BS
Ĉ,

(21)
(22)
(23)

hold for some matrices Q and S of appropriate dimensions
and possibly with the lowest possible n̂. In the next theorem,
we show that under the aforementioned conditions V in (20)
b to Σ.
is an SPSF from Σ
b =
Theorem 5.1: Let Σ = (A, B, C, D, F ) and Σ
(Â, B̂, Ĉ, D̂, F̂ ) be two discrete-time linear stochastic control subsystems with two independent additive noises. Suppose that there exist matrices M , K, P , Q, and S satisfying
(18), (19), (21), (22), and (23). Then, V defined in (20) is
b to Σ.
an SPSF from Σ
Proof: Here, we show that ∀x, ∀x̂, ∀ν̂, ∀ω̂, ∃ν, ∀ω,
such that V satisfies kCx − Ĉ x̂k2 ≤ V (x, x̂) and
h
E V (x(k + 1), x̂(k + 1)) | x(k), x̂(k), ω(k) = ω, ω̂(k) = ω̂,
i
, ν̂(k) = ν̂ − V (x(k), x̂(k))
π √
2
≤ −b
κ(V (x(k), x̂(k))) + (1 + + )k M Dk2 kω − ω̂k2
π
2
2
2 √
2
e − P B̂)k kν̂k2
+ (1 + + )k M (B R
π
π


+ Tr F T M F + F̂ T P T M P F̂ .
(24)
According to (23), we have kCx − Ĉ x̂k2 = (x −
P x̂)T C T C(x − P x̂). By applying (18), it can be easily
verified that kCx − Ĉ x̂k2 ≤ V (x, x̂) holds ∀x, ∀x̂. Now, we
show inequality (24). Given any x, x̂, ν̂, and ω̂, we choose
ν via the following linear interface function:
e + S ω̂, (25)
ν = νν̂ (x, x̂, ν̂, ŵ) := K(x − P x̂) + Qx̂ + Rν̂

e of appropriate dimension. By Employing
for some matrix R
equations (21), (22), and the definition of the interface
function in (25), we simplify
Ax + Bνν̂ (x, x̂, ν̂, ω̂) + Dω − P (Âx̂ + B̂ ν̂ + D̂ω̂)


+ F ς(k) − P F̂ ςˆ(k)

e
to (A+BK)(x−P x̂)+D(ω− ω̂)+(B R−P
B̂)ν̂ + F ς(k)−

P F̂ ςˆ(k) . One obtains:
h
E V (x(k + 1), x̂(k + 1)) | x(k), x̂(k), ω(k) = ω, ω̂(k) = ω̂,
i
, ν̂(k) = ν̂ − V (x(k), x̂(k))
h
i
= (x − P x̂)T (A + BK)T M (A + BK) − M (x − P x̂)
i h
i
h
+ 2(x − P x̂)T (A + BK)T M D(ω − ω̂)
h
i h
i
e − P B̂)ν̂
+ 2(x − P x̂)T (A + BK)T M (B R
i
i h
h
√
e − P B̂)ν̂ + k M D(ω − ω̂)k2
+ 2(ω − ω̂)T DT M (B R
√

e − P B̂)ν̂k2 + Tr F T M F + F̂ T P T M P F̂ .
+ k M (B R

1 2
b , for any
Using Young’s inequality [15] as ab ≤ π2 a2 + 2π
a, b ≥ 0 and any π > 0, and by employing Cauchy-Schwarz
inequality and (19), one obtains the following upper bound:
h
E V (x(k + 1), x̂(k + 1)) | x(k), x̂(k), ω(k) = ω, ω̂(k) = ω̂,
i
, ν̂(k) = ν̂ − V (x(k), x̂(k))
π √
2
≤ −b
κ(V (x, x̂)) + (1 + + )k M Dk2 kω − ω̂k2
π
2
2 √
2
e − P B̂)k2 kν̂k2
+ (1 + + )k M (B R
π
π


+ Tr F T M F + F̂ T P T M P F̂ .
(26)

b to
Hence, the proposed V in (20) is an SPSF from Σ
Σ, which completes the proof. Note that the K and K∞
functions κ, α, and ρext , in Definition 3.1 associated with
the SPSF in √
(20) are α(s) := s2 , κ(s) := b
κs, and√ρint (s) :=
2
π
e
(1+ π + 2 )k M Dk2 s2 , ρext (s) := (1+ π2 + π2 )k M (B R−
P B̂)k2 s2 , ∀s ∈ R≥0 . Moreover, positive
constant
ψ
in
(4)

is ψ = Tr F T M F + F̂ T P T M P F̂ .
Remark 5.2: One can readily verify from the result of
Theorem 5.1 that choosing F̂ equal to zero results in smaller
constant ψ and, hence, more closeness of linear subsystems
and their abstractions. Observe that this is not the case when
one assumes the noise of the concrete subsystem and its
abstraction are the same as in [9], [10].
Remark 5.3: Note that the results in Theorem 5.1 do not
impose any condition on matrix B̂ and, hence, it can be
chosen arbitrarily. As an example, one can choose B̂ = In̂
b fully actuated and, hence,
which makes the abstract system Σ
the synthesis problem over it much easier.
Remark 5.4: Since Theorem 5.1 does not impose any
e we choose R
e to minimize function
condition on matrix R,
e
ρext for V as suggested in [16]. The following choice for R
minimizes ρext .

e = (B T M B)−1 B T M P B̂.
R

(27)

VI. E XAMPLE
Here, we demonstrate the effectiveness of the proposed
results for an interconnected system consisting of four
discrete-time linear stochastic control subsystems, i.e. Σ =
I(Σ1 , Σ2 , Σ3 , Σ4 ). The interconnection scheme of Σ with
four inputs and two outputs is illustrated in Figure 1.
As seen, 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
system matrices are given by
Ai = I25 , Bi = I25 , CiT = 0.1125 , Fi = 0.01125 ,
for i ∈ {1, 2, 3, 4}. The internal input and output matrices
are also given by:
T
T
T
T
C14
= C23
= C31
= C42
= 0.1125 ,
D13 = D24 = D32 = D41 = 0.1125 .

In order to construct an abstraction for I(Σ1 , Σ2 , Σ3 , Σ4 ),
b i of each individual subsystem
we construct an abstraction Σ
Σi , i ∈ {1, 2, 3, 4}. We first fix κ
b and π for each subsystem,

Σ1

y14

ν1

ν3

ν2

ν4
Σ2

Fig. 1.

Σ3

y31
y33

y23

Σ4

y44
y42

The interconnected system Σ = I(Σ1 , Σ2 , Σ3 , Σ4 ).

and then determine the matrices M and K such that (18)
and (19) hold for i ∈ {1, 2, 3, 4}:
Mi = I25 , Ki = −0.95I25 , κ
bi = 0.98, πi = 0.99.

We continue with determining other matrices such that (21),
(22), and (23) hold:
Pi = 125 , Qi = 125 , Si = −0.003125,
for i ∈ {1, 2, 3, 4}. Accordingly, the matrices of abstract
subsystems are computed as:
Âi = 2, Ĉi = 2.5, D̂i = 0.096,
for i ∈ {1, 2, 3, 4}. Note that here F̂i , i ∈ {1, 2, 3, 4}, are
considered zero in order to reduce constants ψi for each
ei , i ∈
Vi . Moreover, B̂i are chosen 1 and we compute R
e
{1, 2, 3, 4}, using (27) as Ri = 125 . The interface function
for i ∈ {1, 2, 3, 4} follows by (25) as:
νi = −0.95I25 (xi − 125 x̂i )+125 x̂i +125 ν̂i −0.003125ω̂i .
Hence, Theorem 5.1 holds and Vi (xi , x̂i ) = (xi −
b i to Σi
125 x̂i )T Mi (xi − 125 x̂i ) is an SPSF function from Σ
2
satisfying conditions (3) and (4) with αi (s) = s , κi (s) =
0.98s, ρiext (s) = 0, ρiint (s) = 0.88s2, and ψi = 0.0025,
for i ∈ {1, 2, 3, 4}. We now proceed with Theorem 4.2
b to Σ.
to construct a stochastic simulation function form Σ
Assumption 1 holds with γi (s) = s and:



0.98
0
0
0
0
0
0.88
0
0.98
0
0 
0
0
0.88
 0
 0
.
, Λ=
∆=
0
0
0.98
0 
0
0.88
0
0 
0
0
0
0.98
0.88
0
0
0


Additionally, one can readily verify that a vector µ ∈ R4>0
exists here since the spectral radius of Λ−1 ∆ is strictly less
than one [17]. By choosing vector µ as µT = [1 1 1 1],
the function
V (x, x̂) = V1 (x1 , x̂1 )+V2 (x2 , x̂2 )+V3 (x3 , x̂3 )+V4 (x4 , x̂4 )
b 1, Σ
b 2, Σ
b 3, Σ
b 4 ) to I(Σ1 , Σ2 , Σ3 , Σ4 ) satis an SSF from I(Σ
isfying conditions (5) and (6) with α(s) = s2 , κ(s) = 0.1s,
ρext (s) = 0, ∀s ∈ R≥0 , and ψ = 0.01. If the initial states of
b are started from zero,
the interconnected systems Σ and Σ
one can readily verify that the norm of error between outputs
b will not exceed 1 with probability at least
of Σ and of Σ
90% computed by the stochastic simulation function V using
inequality (7) for T = 10.

VII. D ISCUSSION
In this paper, we provided a compositional approach
for abstractions of interconnected discrete-time stochastic
control systems, with independent noises in the abstract and
concrete subsystems. First, we introduced new notions of
stochastic pseudo-simulation and stochastic simulation functions in order to quantify the distance in a probability setting
between original stochastic control subsystems and their abstractions and their interconnections, respectively. Therefore,
one can employ the proposed results here to potentially solve
safety/reachability problems over the abstract interconnected
systems and then refine the results to the concrete interconnected ones. Furthermore, we provided a computational
scheme for the class of discrete-time linear stochastic control
systems to construct abstractions together with their corresponding stochastic pseudo-simulation functions. Finally, we
demonstrated the effectiveness of the results by constructing
an abstraction (totally 4 dimensions) of the interconnection
of four discrete-time linear stochastic control subsystems
(together 100 dimensions) in a compositional fashion.
R EFERENCES
[1] A. A. Julius and G. J. Pappas, “Approximations of stochastic hybrid
systems,” IEEE Transactions on Automatic Control, vol. 54, no. 6, pp.
1193–1203, 2009.
[2] I. Tkachev and A. Abate, “On infinite-horizon probabilistic properties
and stochastic bisimulation functions,” in Proceedings of the 50th
IEEE Conference on Decision and Control and European Control
Conference (CDC-ECC), 2011, pp. 526–531.
[3] S. Esmaeil Zadeh Soudjani and A. Abate, “Adaptive and sequential
gridding procedures for the abstraction and verification of stochastic
processes,” SIAM Journal on Applied Dynamical Systems, vol. 12,
no. 2, pp. 921–956, 2013.
[4] S. Esmaeil Zadeh Soudjani, “Formal abstractions for automated
verification and synthesis of stochastic systems,” Ph.D. dissertation,
Technische Universiteit Delft, The Netherlands, November 2014.
[5] 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,
vol. 59, no. 12, pp. 3135–3150, 2014.
[6] M. Zamani, I. Tkachev, and A. Abate, “Towards scalable synthesis of
stochastic control systems,” Discrete Event Dynamic Systems, vol. 27,
no. 2, pp. 341–369, July 2017.
[7] M. Zamani and A. Abate, “Approximately bisimilar symbolic models
for randomly switched stochastic systems,” Systems & Control Letters,
vol. 69, pp. 38–46, 2014.
[8] M. Zamani, A. Abate, and A. Girard, “Symbolic models for stochastic
switched systems: A discretization and a discretization-free approach,”
Automatica, vol. 55, pp. 183–196, 2015.
[9] M. Zamani, “Compositional approximations of interconnected stochastic hybrid systems,” in Proceedings of the 53rd IEEE Conference on
Decision and Control (CDC), 2014, pp. 3395–3400.
[10] M. Zamani, M. Rungger, and P. Mohajerin Esfahani, “Approximations
of stochastic hybrid systems: a compositional approach,” IEEE Transactions on Automatic Control, 2016.
[11] O. Hernández-Lerma and J. B. Lasserre, Discrete-time Markov control
processes, ser. Applications of Mathematics. Springer-Verlag, 1996,
vol. 30.
[12] D. P. Bertsekas and S. E. Shreve, Stochastic Optimal Control: The
Discrete-Time Case. Athena Scientific, 1996.
[13] H. J. Kushner, Stochastic Stability and Control, ser. Mathematics in
Science and Engineering. Elsevier Science, 1967.
[14] B. Oksendal, Stochastic differential equations: an introduction with
applications. Springer Science & Business Media, 2013.
[15] 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, vol. 87, no. 594, pp. 225–229,
1912.
[16] A. Girard and G. J. Pappas, “Hierarchical control system design using
approximate simulation,” Automatica, vol. 45, no. 2, pp. 566–571,
2009.
[17] S. Dashkovskiy, H. Ito, and F. Wirth, “On a small gain theorem for iss
networks in dissipative lyapunov form,” European Journal of Control,
vol. 17, no. 4, pp. 357–365, 2011.

