DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS
UNDER COUPLED CONSTRAINTS

arXiv:1506.05297v3 [cs.SY] 22 Aug 2016

D. BOSKOS AND D. V. DIMAROGONAS

Abstract. The goal of this report is to define abstractions for multi-agent systems with
feedback interconnection in their dynamics. In the proposed decentralized framework, we
specify a finite or countable transition system for each agent which only takes into account
the discrete positions of its neighbors. The dynamics of the considered systems consist
of two components. An appropriate feedback law which guarantees that certain system
and network requirements are fulfilled and induces coupled constraints, and additional free
inputs which we exploit in order to accomplish high level tasks. In this work, we provide
sufficient conditions on the space and time discretization for the abstraction of the system’s
behaviour which ensure that we can extract a well posed and hence meaningful transition
system. Furthermore, these conditions include design parameters whose tuning provides the
possibility for multiple transitions, and hence, enable the construction of transition systems
with motion planning capabilities.

1. Introduction
High level task planning for multi-agent systems constitutes an active area of research which
lies in the interface between computer science and modern control theory. A challenge in this
new interdisciplinary direction constitutes of the problem of defining appropriate abstractions
for continuous time multi-agent control systems, which can be used as a tool for the analysis
and control of large scale systems and the synthesis of high level plans [11], [21]. Robot motion
planning and control constitutes a central field where this line of work is applied [10], [9]. In
particular, the use of a suitable discrete system’s model allows the automatic synthesis of discrete plans that guarantee satisfaction of the high level specifications. Then, under appropriate
relations between the continuous system and its discrete analogue, these plans can be converted
to low level primitives such as sequences of feedback controllers, and hence, enable the continuous system to implement the corresponding tasks. Such tasks in the case of multiple mobile
robots in an industrial workspace could include for example the following scenario. Robot 1
should periodically visit regions A, B, while avoiding C and after collecting an item of type X
from robot 2 at location D, store it at location E.
In order to synthesize high level plans, it is required to specify an abstraction of the original
system, namely a system that preserves some properties of interest of the initial system, while
ignoring detail. Results in this direction for the nonlinear single plant case have been obtained
in the papers [23] and [32], where the notions of approximate bisimulation and simulation are
exploited for certain classes of nonlinear systems, under appropriate stability, and completeness
assumptions, respectively. The notion of bisimulation, has its origin in computer science [4],
and guarantees that if the initial system and its abstraction are bisimilar, then the task of
checking feasibility of high level plans for the original system reduces to the same task for its
abstraction and vice versa. Bisimulation relations between transition system models of discrete
Key words and phrases. hybrid systems, multi-agent systems, abstractions, transition systems.
1

2

D. BOSKOS AND D. V. DIMAROGONAS

or continuous time linear control systems with finite affine observation maps were explicitly
characterized and constructed in [22], providing also a generalization of the notion of state
space equivalence between continuous time systems [30].
Another abstraction tool for a general class of systems is the hybridization approach [3], where
the behaviour of a nonlinear system is captured by means of a piecewise affine hybrid system on
simplices. Motion planing techniques for the latter case have been developed in the recent works
[12], [13], which are also based on the abstraction and controller synthesis framework provided
in [18], [17], and further studied in [7]. Other abstraction techniques for nonlinear systems
include [25], where discrete time systems are studied in a behavioral framework, the sign based
abstraction methodology introduced in [29], which is based on Lie-algebraic type conditions
and [1], where box abstractions are studied for polynomial and other classes of systems (for a
literature survey on the subject see also the monograph [27]). It is also noted that certain of
the aforementioned approaches have been extended to switched [14], [15] and networked control
systems [31]. Furthermore, abstractions for the case of discrete time interconnected systems
that are described by coupled difference equations, can be found in [28] and [24], for stabilizable
linear systems, and incrementally input-to-state stable nonlinear systems, respectively. Finally,
we note that the control design which we adopt for the construction of the symbolic models is
in part related to the notion of In-Block Controllability [8], [19].
In particular, we focus on multi-agent systems and assume that the agents’ dynamics consist
of feedback interconnection terms, which ensure that certain system properties as for instance
connectivity or (and) invariance are preserved, and free input terms, which provide the ability
for motion planning under coupled constraints. In this report, we generalize the corresponding
results of our recent work [5], where sufficient conditions for well posed abstractions of the
multi-agent system are provided for the case where the agents’ workspace is Rn . A well posed
abstraction refers to the property that the discrete state transition system which serves as
an abstract model of the multi-agent system has at least one outgoing transition from each
state. The extension in this work is twofold. First, the results on admissible space and time
discretizations in [5] which ensure well posed abstractions, are now valid when the agents’
workspace is a general domain D of Rn , provided that D is invariant for the dynamics of the
system. Also, the corresponding framework is extended for motion planning, and sufficient
conditions are provided which guarantee that each agent can perform multiple transitions from
each initial discrete state.
The rest of the report is organized as follows. Basic notation and preliminaries are introduced
in Section 2. Section 3 is devoted to the formulation of the problem and motivates the control
design that will be utilized for the derivation of the symbolic models. In Section 4, we define
well posed abstractions for single integrator multi-agent systems by means of hybrid feedback
controllers and prove that the latter provide solutions consistent with the design requirement
on the systems’ free inputs. Section 5 is devoted to specific properties of the control laws
that realize the transitions of the proposed discrete system’s model. In Section 6 we quantify
space and time discretizations which guarantee well posed transitions with motion planning
capabilities. The framework is illustrated through an example in Section 7 including simulation
results. Finally, we conclude and indicate directions of further research in Section 8.
2. Preliminaries and Notation
We use the notation |x| for the Euclidean norm of a vector x ∈ Rn . For a subset S of
R , we denote by cl(S), int(S) and ∂S its closure, interior and boundary, respectively, where
∂S := cl(S) \ int(S). Given R > 0 and x ∈ Rn , we denote by B(R) the closed ball with
n

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS 3

center 0 ∈ Rn and radius R, namely B(R) := {x ∈ Rn : |x| ≤ R} and B(x; R) := {y ∈
Rn : |x − y| ≤ R}. For two nonempty sets A, B ⊂ Rn their Minkowski sum is given as
A + B := {x + y ∈ Rn : x ∈ A, y ∈ B}. Also, for a nonempty set A ⊂ Rn its diameter is defined
as diam(A) := sup{|x − y| : x, y ∈ A}. Given a real number a ∈ R≥0 we denote by bac the
integer part of a (bac := max{n ∈ N ∪ {0} : n ≤ a}). Finally, given a function f : X → Y and
a subset W of X, the notation f |W is used for the restriction of f to W .
Consider a multi-agent system with N agents. For each agent i ∈ N := {1, . . . , N } we use
the notation Ni for the set of its neighbors and Ni := |Ni | for its cardinality. We also consider
an ordering of the agent’s neighbors which is denoted by j1 , . . . , jNi , and define the Ni -tuple
j(i) = (j1 , . . . , jNi ). Whenever it is clear from the context, the argument i in the latter notation
will be omitted. Given an index set I and an agent i ∈ N with neighbors j1 , . . . , jNi ∈ N ,
define the mapping pri : I N → I Ni +1 which assigns to each N -tuple (l1 , . . . , lN ) ∈ I N the
Ni + 1-tuple (li , lj1 , . . . , ljNi ) ∈ I Ni +1 , i.e., the indices of agent i and its neighbors.
We proceed by providing a formal definition for the notion of a transition system (see for
instance [4], [22], [23]).
Definition 2.1. A transition system is a tuple T S := (Q, Act, −→), where:
• Q is a set of states.
• Act is a set of actions.
• −→ is a transition relation with −→⊂ Q × Act × Q.
The transition system is said to be finite, if Q and Act are finite sets. We also use the (standard)
a
notation q −→ q 0 to denote an element (q, a, q 0 ) ∈−→. For every q ∈ Q and a ∈ Act we use the
notation Post(q; a) := {q 0 ∈ Q : (q, a, q 0 ) ∈−→}. The transition system is called deterministic
a
a
if for each q ∈ Q and a ∈ Act, q −→ q 0 and q −→ q 00 implies that q 0 = q 00 .
3. Problem Formulation
We focus on multi-agent systems with single integrator dynamics
ẋi = ui , xi ∈ Rn , i ∈ N

(3.1)

and consider as inputs decentralized control laws of the form
ui = fi (xi , xj ) + vi , i ∈ N ,

(3.2)

with xj (= xj(i) ) := (xj1 , . . . , xjNi ) ∈ RNi n (see Section 2 for the Notation j(i)), consisting of
two terms: a feedback term fi (·) which depends on the states of i and its neighbors, and an
extra input term vi , which we call free input. We assume that for each i ∈ N it holds xi ∈ D
where D is a domain of Rn and that each fi (·) is locally Lipschitz. We also assume that the
feedback terms fi (·) are globally bounded, namely, there exists a constant M > 0 such that
|fi (xi , xj )| ≤ M, ∀(xi , xj ) ∈ DNi +1 .

(3.3)

Furthermore, we consider piecewise continuous free inputs vi that satisfy the bound
|vi (t)| ≤ vmax , ∀t ≥ 0, i ∈ N .

(3.4)

In the subsequent analysis, it is assumed that the maximum magnitude of the feedback terms
is higher than that of the free inputs, namely, that
vmax < M.

(3.5)

4

D. BOSKOS AND D. V. DIMAROGONAS

This assumption is motivated by the fact that we are primarily interested in maintaining the
property that the feedback is designed for, and secondarily, in exploiting the free inputs in order to accomplish high level tasks. A class of multi-agent systems of the form (3.1)-(3.2) which
justifies this assumption has been studied in our companion work [6]. In particular, sufficient
conditions are provided, which guarantee both connectivity of the network and forward invariance of the system’s trajectories inside a given bounded domain, for an appropriate selection of
vmax in (3.4) which necessitates vmax to satisfy (3.5). The latter forward invariance property is
defined in the Invariance Assumption (IA) below, which we assume that the multi-agent system
(3.1)-(3.2) satisfies for the rest of the report.
(IA) For every initial condition x(0) ∈ DN and any piecewise continuous input v = (v1 , . . . , vn ) :
R≥0 → RN n satisfying (3.4), the (unique) solution of the system (3.1)-(3.2) is defined and remains in DN for all t ≥ 0. /
This assumption does not restrict the class of systems under consideration since it is satisfied
for any forward complete system when D = Rn . Recall that the system (3.1)-(3.2) is forward
complete (see e.g, [2]) if for each initial condition in Rn and each measurable locally essentially
bounded input v = (v1 , . . . , vn ) : R≥0 → RN n , its solution exists for all positive times. Also,
notice that due to the above bounds on the dynamics and the free input terms, the system
(3.1)-(3.2) is forward complete. Finally, when D is bounded, as is the case in [6], a finite
partition of the workspace by bounded sets can lead to a finite transition system which captures
the properties of interest of the multi-agent system and hence enables the investigation for
computable solutions with respect to high level specifications.
In what follows, we consider a cell decomposition of the state space D (which can be regarded
as a partition of D) and a time step δt > 0. We will refer to this selection as a space and
time discretization. For the definition of a cell decomposition we adopt a modification of the
corresponding definition from [16, p 129-called cell covering].
Definition 3.1. Let D be a domain of Rn . A cell decomposition S = {Sl }l∈I of D, where
I is a finite or countable index set, is a family of nonempty connected sets Sl , l ∈ I, such that
sup{diam(Sl ), l ∈ I} < ∞, cl(int(Sl )) = Sl for all l ∈ I, int(Sl ) ∩ int(Sl̂ ) = ∅ for all l 6= ˆl and
∪l∈I Sl = D. /
Given a cell decomposition S := {Sl }l∈I of D, we use the notation li = (li , lj1 , . . . , ljNi ) ∈ I Ni +1
to denote the indices of the cells where agent i and its neighbors belong at a certain time instant
and call it the cell configuration of agent i. Similarly, we use the notation l = (l1 , . . . , lN ) ∈ I N
to specify the indices of the cells where all the N agents belong at a given time instant and
call it the cell configuration (of all agents). Thus, given a cell configuration l, it is possible
to determine the cell configuration of agent i as li = pri (l) (see Section 2 for the definition of
pri (·)).
Through the space and time discretization we aim at capturing reachability properties of the
original continuous time system, by means of a discrete state transition system. Informally, we
would like to consider for each agent i, its individual transition system with state set the cells
of the state partition, actions defined to be all possible cells of its neighbors, and transition
relation specified as follows. Given the initial cells of agent i and its neighbors, it is possible
for i to perform a transition to a final cell, if for all states in its initial cell there exists a free
input, such that its trajectory will reach the final cell at time δt, for all possible initial states of
its neighbors in their cells, and their corresponding free inputs. Feasibility of high level plans
requires the corresponding system to be well posed (meaningful), which implies that for each
initial cell it is possible to transit to (at least) one final cell.

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS 5

We next illustrate the concept of a well posed space-time discretization, namely, a discretization which generates for each agent a meaningful transition system in accordance with the
discussion above. Consider a cell decomposition as depicted in Fig. 1 and a time step δt. The
tips of the arrows in the figure are the endpoints of agent’s i trajectories at time δt. In both
cases in the figure we focus on agent i and consider the same cell configuration for i and its
neighbors. However, we consider different dynamics for Cases (i) and (ii). In Case (i), we
observe that for the three distinct initial positions in cell Sli , it is possible to drive agent i to
cell Sli0 at time δt. We assume that this is possible for all initial conditions in this cell and
irrespectively of the initial conditions of i’s neighbors in their cells and the inputs they choose.
We also assume that this property holds for all possible cell configurations of i and for all the
agents of the system. Thus we have a well posed discretization for system (i). On the other
hand, for the same cell configuration and system (ii), we observe the following. For three distinct initial conditions of i the corresponding reachable sets at δt, which are enclosed in the
dashed circles, lie in different cells. Thus, it is not possible given this cell configuration of i to
find a cell in the decomposition which is reachable from every point in the initial cell and we
conclude that discretization is not well posed for system (ii).
xi (δt)

xi (δt)
xj2

Sli0

xj2

Slj2

xj1 Slj1
Sli

xi

Slj2

xj1 Slj1
Sli

xi

System (i):
System (ii):
ẋi =fi,(i) (xi ,xj1 ,xj2 ) + vi,(i) ẋi =fi,(ii) (xi ,xj1 ,xj2 ) + vi,(ii)
Figure 1. Illustration of a space-time discretization which is well posed for
system (i) but non-well posed for system (ii).

One main challenge in the attempt to provide meaningful decentralized abstractions for
system (3.1)-(3.2) is the interconnection between the agents through the fi (·) terms. The
latter in conjunction with the considerations above, motivates the design of appropriate hybrid
feedback laws in place of the vi ’s which will guarantee the desired well posed transitions.
We next define the particular feedback laws that are utilized for the construction of the
symbolic models in this report, which also motivate the notion of well posed discretizations
that will be formulated in the next section. Consider a cell decomposition S = {Sl }l∈I of D
and a time step δt. For each agent i ∈ N and cell configuration li = (li , lj1 , . . . , ljNi ) ∈ I Ni +1
of i let
(xi,G , xj,G ) ∈ Sli × (Slj1 × · · · × SljN )
(3.6)
i

be an arbitrary Ni + 1-tuple of reference points and define the family of feedback laws ki,li :
[0, T (xi0 , wi )) × DNi +1 → Rn parameterized by xi0 ∈ Sli and wi ∈ W as
ki,li (t, xi , xj ; xi0 , wi ) : = ki,li ,1 (xi , xj )
+ ki,li ,2 (xi0 ) + ki,li ,3 (t; xi0 , wi ),

(3.7)

6

D. BOSKOS AND D. V. DIMAROGONAS

where
W := B(λvmax ), λ ∈ (0, 1),

(3.8)

ki,li ,1 (xi , xj ) := fi (xi , xj,G ) − fi (xi , xj ),
1
ki,li ,2 (xi0 ) := (xi,G − xi0 ),
δt
ki,li ,3 (t; xi0 , wi ) := Fi,li (χi (t)) + wi − Fi,li (χi (t) + twi

(3.9)

and

+ (1 −

t
δt )(xi0

− xi,G )),

T (xi0 , wi ) := sup{t̄ ∈ [0, Tmax ) : χi (t) + twi

+ 1 − δtt (xi0 − xi,G ) ∈ D, ∀t ∈ [0, t̄]},
t ∈ [0, T (xi0 , wi )), (xi , xj ) ∈ D

Ni +1

(3.10)

(3.11)
(3.12)

, xi0 ∈ Sli , wi ∈ W.

The function Fi,li (·) in (3.11) is defined as
Fi,li (xi ) := fi (xi , xj,G ), xi ∈ D

(3.13)

and χi (·) in (3.11), (3.12) is the solution of the initial value problem
χ̇i = Fi,li (χi ), χi (0) = xi,G ,

(3.14)

which is defined and remains in D on the maximal right interval [0, Tmax ) (Tmax is the same
as in (3.12)). In particular, χi (·) constitutes a reference trajectory, whose endpoint agent i
should reach at time δt, when the agent’s initial condition lies in Sli and the feedback ki,li (·)
above is applied (plus some extra hypotheses for the rest of the agents). The time T (xi0 , wi )
in (3.12) stands for the right endpoint of the maximal right interval for which a modification of
the reference trajectory that depends on xi0 and wi is guaranteed to remain inside the domain
D. Also, the parameter λ in (3.8) stands for the portion of the free input that can be exploited
for motion planning. In particular, each vector wi from the set W in (3.8) provides a possible
“constant velocity” of a motion that we superpose to the reference trajectory χi (·) of agent i,
allowing thus the agent to reach all points inside a ball with center the position of the reference
trajectory at time δt. Note that the control laws ki,li (·) are decentralized, since they only use
information of agent i’s neighbors states. In addition, they depend on the cell configuration li
through the reference points (xi,G , xj,G ) which are involved in (3.9)-(3.11).
We proceed by providing some extra intuition for the selection of the control laws in (3.9),
(3.10) and (3.11), based on Fig. 2 below. Consider a cell decomposition of D, a time step
δt and select an agent i, a cell configuration of i and a tuple of reference points as in (3.6).
The reference trajectory of i is obtained from (3.14), by “freezing” agent i’s neighbors at their
corresponding reference points through the feedback term ki,li ,1 (·). Also, by selecting a vector
wi in W and informally assuming that we can superpose to the reference trajectory the motion
of i with constant speed wi , namely, move along the curve x̄i (·) defined as
x̄i (t) := χi (t) + twi , t ∈ [0, Tmax ),

(3.15)

we can reach the point x inside the dashed ball at time δt from the reference point xi,G , as
depicted in Fig. 2. In a similar way, it is possible to reach any point inside this ball by a
different selection of wi . This ball has radius
r := λvmax δt,

(3.16)

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS 7

namely, the distance that the agent can cross in time δt by exploiting the part of the free
input that is available for planning. Our abstraction requirement is that the transition to each
cell which has nonempty intersection with B(χi (δt); r) is well posed. This will be verified for
system (3.1)-(3.2) through the establishment of condition (6.23) in Theorem 6.3 (Section 6)
for appropriate space-time discretizations. For instance, in order for the transition to the cell
where the point x belongs to be well posed, we will require the following. That the feedback law
ki,li (·), which is selected in place of agent’s i free input, guarantees that for each initial condition
of i in cell Sli , the endpoint of i’s trajectory will coincide with the endpoint of the curve x̄i (·).
In order to compensate for the deviation of the initial state with respect to the reference point
and reach the point x, we use the extra terms ki,li ,2 (·) and ki,li ,3 (·). These enforce the agent
to move with the velocity of the reference trajectory plus two constant velocity terms, one
analogous to the displacement between the agents initial state and the reference point, and the
other analogous to the distance between x and the endpoint of χi (·).
x̄i (t)
xi (t)
χi (δt)

xi,G
Sli

B(χi (δt); r)

xi (δt) = x
xi0

Sli0

χi (δt) + twi

Figure 2. Consider any point x inside the ball with center χi (δt). Then, for
each initial condition xi0 in the cell Sli , the endpoint of agent’s i trajectory
xi (·) coincides with the endpoint of the curve x̄i (·), which is precisely x, and
lies in Sli0 , namely, xi (δt) = x̄i (δt) = x ∈ Sli0 .
4. Abstractions for Multi-Agent Systems
In this section we formalize the discussion in Section 3, by exploiting a class of hybrid feedback
laws containing the control laws introduced in (3.7). One reason for employing the subsequent
analysis in an abstract framework is that the selection in (3.9)-(3.11) is not the only possible.
For instance, it can be shown that selecting the control laws ki,li ,1 (xi , xj ) := fi (xi,G , xj,G ) −
fi (xi , xj ), ki,li ,2 (xi0 ) as before and ki,li ,3 (wi ) := wi , can also provide well posed discretizations
for system (3.1)-(3.2). However, the latter will necessitate finer admissible discretizations and
hence, increase the complexity of the symbolic model. In the sequel, given a time step δt and the
bounds M and vmax on the feedback and input terms provided by (3.3) and (3.4), respectively,
it is convenient to introduce the following lengthscale
Rmax := δt(M + vmax ).

(4.1)

It follows from (3.1), (3.2), (3.3), (3.4) and (4.1) that Rmax is the maximum distance an agent
can travel within time δt.
Before defining the notion of a well posed space-time discretization we define the class of
hybrid feedback laws which are assigned to the free inputs vi in order to obtain meaningful
discrete transitions. For each agent, these control laws are parameterized by the agent’s initial
conditions and a set of auxiliary parameters belonging to a nonempty subset W of Rn . These
parameters, as discussed in the previous section, are exploited for motion planning. In particular, for every agent i, each vector wi ∈ W is in a one-to-one correspondence with a point
inside a reachable ball for i, and the agent can reach this point by selecting the control law

8

D. BOSKOS AND D. V. DIMAROGONAS

corresponding to the specific parameter wi . The latter provides the possibility for the agent to
perform transitions to different cells, namely, all cells which have nonempty intersection with
that ball. Furthermore, we note that in accordance to the control laws introduced in (3.7) for
each agent i, the feedback laws in the following definition depend on the selection of the cells
where i and its neighbors belong. One basic requirement for this class of controllers consists
of conditions that guarantee well posed solutions for the system (condition (P1) in Definition
4.1, below). We also impose a consistency requirement (condition (P2) in Definition 4.1) that
their magnitude does not exceed the maximum bound on the free inputs (3.4), when the states
of the agent and its neighbors lie in an appropriate inflation of their corresponding cells (in
particular, an overapproximation of their reachable states over the time interval [0, δt]).
Definition 4.1. Given a cell decomposition S = {Sl }l∈I of D, a time step δt and a nonempty
subset W of Rn , consider an agent i ∈ N and an initial cell configuration li = (li , lj1 , . . . , ljNi )
of i. For each xi0 ∈ Sli and wi ∈ W , let T (xi0 , wi ) > 0 and consider a mapping ki,li (·; xi0 , wi ) :
[0, T (xi0 , wi )) × DNi +1 → Rn , parameterized by xi0 ∈ Sli and wi ∈ W . We say that ki,li (·)
satisfies Property (P), if the following conditions are satisfied.
(P1) For each xi0 ∈ Sli and wi ∈ W , the mapping ki,li (·; xi0 , wi ) is locally Lipschitz continuous.
(P2) It holds
|ki,li (t, xi , xj ; xi0 , wi )| ≤ vmax , ∀t ∈ [0, δt] ∩ [0, T (xi0 , wi )),
xi ∈ (Sli + B(Rmax )) ∩ D, xjm ∈ (Sljm + B(Rmax )) ∩ D,
m = 1, . . . , Ni , xi0 ∈ Sli , wi ∈ W,

(4.2)

with vmax as given in (3.4) and Rmax as in (4.1).
(P3) It holds T (xi0 , wi ) > δt, for all xi0 ∈ Sli , wi ∈ W . /
The motivation for considering the time interval [0, T (xi0 , wi )) in Definition 4.1 comes from
the maximal right interval on which the modification of agent’s i reference trajectory in (3.12)
remains inside the domain D. We next provide an extra Condition (C) for the feedback laws
provided in the above definition, which is needed in order to define well posed discretizations.
Definition 4.2. Consider a cell decomposition S = {Sl }l∈I of D, a time step δt and a nonempty
subset W of Rn . Given an agent i ∈ N , a cell configuration li = (li , lj1 , . . . , ljNi ) of i, a control
law
vi = ki,li (t, xi , xj ; xi0 , wi )
(4.3)
as in Definition 4.1 that satisfies Property (P), a vector wi ∈ W , and a cell index li0 ∈ I, we say
that Condition (C) is satisfied, or specifically, that li , ki,li (·), wi , li0 satisfy Condition (C), if
the following hold. For each initial cell configuration l with pri (l) = li , l = (l1 , . . . , lN ), and for
all ` ∈ N \ {i} and feedback laws
v` = k`,l` (t, x` , xj(`) ; x`0 , w` ),

(4.4)

that satisfy Property (P) (with l` = pr` (l)), the solution of the closed-loop system (3.1)-(3.2),
(4.3)-(4.4) is well defined on [0, δt] and satisfies xi (δt, x(0)) ∈ Sli0 , for all initial conditions
x(0) ∈ DN with xi (0) = xi0 ∈ Sli x` (0) = x`0 ∈ Sl` , ` ∈ N \ {i} and w` ∈ W , ` ∈ N \ {i}. /
Notice that when Condition (C) is satisfied, agent i is driven to cell Sli0 precisely in time
δt under the feedback law ki,li (·) corresponding to the given parameter wi in the definition.
In particular, Condition (C) ensures that the latter holds for any choice of feedback laws in
place of the other agents’ free inputs, as long as these control laws satisfy Property (P). We

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS 9

next provide the definition of a well posed space-time discretization. This definition formalizes
our discussion on the possibility to assign a feedback law to each agent, in order to enable a
meaningful transition from an initial to a final cell.
Definition 4.3. Consider a cell decomposition S = {Sl }l∈I of D, a time step δt and a nonempty
subset W of Rn .
(i) Given an agent i ∈ N , an initial cell configuration li = (li , lj1 , . . . , ljNi ) of i and a cell index
l

i
li0 is well posed with respect to the space-time
li0 ∈ I we say that the transition li −→
discretization S − δt, if there exist a feedback law vi = ki,li (·; xi0 , wi ) as in Definition 4.1
that satisfies Property (P), and a vector wi ∈ W , such that Condition (C) in Definition 4.2 is
fulfilled.

(ii) We say that the space-time discretization S − δt is well posed, if for each agent i ∈ N
and cell configuration li = (li , lj1 , . . . , ljNi ) of i, there exists a cell index li0 ∈ I such that the
l

i
transition li −→
li0 is well posed with respect to S − δt.

Given a space-time discretization S − δt and based on Definition 4.3(i), it is now possible to
provide an exact definition of the discrete transition system which serves as an abstract model
for the behaviour of each agent.
Definition 4.4. For each agent i, its individual transition system T Si := (Qi , Acti , −→i )
is defined as follows:
• Qi := I (the indices of the cell decomposition)
• Acti := I Ni +1 (the set of all cell configurations of i)
l

l

i
i
0
0
0
• li −→
i li iff li −→ li is well posed, for each li , li ∈ Qi and li = (li , lj1 , . . . , ljNi ) ∈ Acti . /

We have preferred to use the term actions instead of labels (as for instance in [23]) for the
elements of the set Acti , because the cell configuration of i indicates how the feedback term
fi (·) acts on and affects the possible transitions of agent i.
Remark 4.5. (i) Given a well posed space-time discretization S − δt and an initial cell configuration l = (l1 , . . . , lN ), it follows from Definitions 4.3 and 4.4 that for each agent i ∈ N it
holds Posti (li ; pri (l)) 6= ∅ (Posti (·) refers to the transition system T Si of each agent-see also
Section 2).
(ii) According to Definition 4.3, given a control law ki,li (·) it is possible to perform transitions
to different cells by an alternative selection of wi .
(iii) In addition, it is also possible to obtain different transitions by choosing an alternative
control law. In particular, it is possible for the control laws considered in (3.7) to obtain a
different reference trajectory in (3.14) by selecting another set of points (xi,G , xj,G ) and hence,
reach a ball which intersects different cells (see Fig. 2). /
Assume a well posed space-time discretization S − δt is given. Based on Definition 4.3
and Remark 4.5 we proceed by providing a modification of each transition system T Si that
captures additional information on the control actions that realize the individual transitions.
In particular, for each i ∈ N and cell configuration li = (li , lj1 , . . . , ljNi ) of i we pick a control law
ki,li (·) which generates at least one well posed transition, i.e., such that li , ki,li (·), wi , li0 satisfy
Condition (C) for certain wi ∈ W and li0 ∈ I (this is always possible since the discretization is
well posed) and define for all l ∈ I
[wi ](li ,l) := {w ∈ W : li , ki,li (·), w, l satisfy Condition(C)}.

(4.5)

10

D. BOSKOS AND D. V. DIMAROGONAS

Based on (4.5), we next provide for each agent the controlled version of its individual transitions
system.
Definition 4.6. Consider a well posed space-time discretization and select for each agent i
and cell configuration li a control law ki,li (·) which generates at least one well posed transition.
Then, the controlled individual transition system T Sic := (Qi , Actci , −→ci ) of each agent i
is defined as follows
• Qi := I
• Acti := I Ni +1 × 2W
(li ,[wi ])

l

i
0
0
• li −→ci li0 iff li −→
i li and [wi ] = [wi ](li ,li0 ) 6= ∅, for each li , li ∈ Qi , li = (li , lj1 , . . . , ljNi ) ∈
I Ni +1 and [wi ] ∈ 2W , with [wi ](li ,li0 ) as defined in (4.5). /

Remark 4.7. (i) Although the set 2W has uncountable cardinality, we have preferred this
representation for the control actions (instead of e.g., to select W ), because for each agent i
and cell configuration li the possible actions which generate a transition are bounded by the
successor states of the agent.
(ii) For each agent i and cell configuration li = (li , lj1 , . . . , ljNi ) it holds ∪[wi ]∈2W Postci (li ; (li , [wi ])) ⊂
Posti (li ; li ), since the transitions in T Sic are associated to the specific controller selection for
the cell configuration. /
Next, notice that according to Definition 4.3, a well posed space-time discretization requires
the existence of a well posed transition for each agent i. The latter reduces to the selection of an
appropriate feedback controller for i, which also satisfies Property (P), and the requirement that
the selected feedback controllers of the other agents also satisfy (P). Yet, it is not completely
evident, that given an initial cell configuration and a well posed transition for each agent, it
is possible to choose a feedback law for each agent, so that the resulting closed-loop system
will guarantee all these well posed transitions (for all possible initial conditions in the cell
configuration). The following proposition clarifies this point.
Proposition 4.8. Consider system (3.1)-(3.2), let l = (l1 , . . . , lN ) be an initial cell configuration and assume that the space-time discretization S − δt is well posed, which according to
Remark 4.5 implies that for all i ∈ N it holds that Posti (li ; pri (l)) 6= ∅. Then, for every final cell
0
) ∈ Post1 (l1 ; pr1 (l)) × · · · × PostN (lN ; prN (l)), there exist feedback
configuration l0 = (l10 , . . . , lN
laws
vi = ki,pri (l) (t, xi , xj ; xi0 , wi ), i ∈ N ,
(4.6)
satisfying Property (P), and w1 , . . . , wN ∈ W , such that for each i ∈ N , the solution of the
closed-loop system (3.1)-(3.2), (4.6) (with vm = km,prm (l) , m ∈ N ) is well defined on [0, δt],
and its i-th component satisfies
xi (δt, x(0)) ∈ Sli0 , ∀x(0) ∈ DN :
xm (0) = xm0 ∈ Slm , m ∈ N .
Proof. The proof is given in the Appendix.

(4.7)


The result of the following proposition guarantees that the selection of the controllers introduced in Definition 4.1 provides well posed solutions for the closed-loop system on the time
interval [0, δt]. We exploit this result in Theorem 6.3, where we derive sufficient conditions for
well posed space-time discretizations, which are also suitable for motion planning. Furthermore,
Proposition 4.9 guarantees that the magnitude of the hybrid feedback laws does not exceed the

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS11

maximum allowed magnitude vmax of the free inputs on [0, δt], and hence, establishes consistency with the initial design requirement. In particular, it follows that every solution of the
closed-loop system on [0, δt] is identical to a solution of the original system (3.1)-(3.2) with the
same initial condition and certain free input v(·) satisfying |vi (t)| ≤ vmax , for all t ≥ 0 and
i ∈ N . For certain technical reasons concerning the proofs in the next sections, it is convenient
to obtain the first results of the proposition for feedback laws that only satisfy Properties (P1)
and (P2) of Definition 4.1.
Proposition 4.9. Consider the space-time discretization S − δt corresponding to the cell decomposition S of D and the time step δt. Let l = (l1 , . . . , lN ) be an initial cell configuration
and consider any feedback laws of the form
vi = ki,pri (l) (t, xi , xj ; xi0 , wi ), i ∈ N

(4.8)

assigned to the agents that satisfy Properties (P1) and (P2). Then:
(i) For each wi ∈ W , i ∈ N and initial condition x(0) ∈ DN with xi (0) = xi0 ∈ Sli , i ∈ N , the
solution of the closed-loop system (3.1)-(3.2), (4.8) (with vi = ki,pri (l) , i ∈ N ) is defined and
remains in DN for all t ∈ [0, T̃ ), where
T̃ := min{δt, min{T (xi0 , wi ) : i ∈ N }}

(4.9)

and
lim x(t) ∈ DN .

(4.10)

t→T̃ −

Assume additionally that (P3) also holds, namely, that (P) is satisfied. Then:
(iia) The solution x(t) of (3.1)-(3.2), (4.8) above remains in DN for all t ∈ [0, δt] and satisfies
|ki,pri (l) (t, xi (t), xj (t); xi0 , wi )| ≤ vmax , ∀t ∈ [0, δt], i ∈ N ,

(4.11)

which provides the desired consistency with the design requirement (3.4) on the vi ’s.
(iib) There exists a piecewise continuous function v = (v1 , . . . , vN ) : [0, ∞) → RN n satisfying
|vi (t)| ≤ vmax , ∀t ≥ 0, i ∈ N , such that the solution x(·) above and the solution ξ(·) of (3.1)(3.2), with the same initial condition as x(·) and input v(·), coincide on [0, δt].
Proof. The proof is given in the Appendix.



Remark 4.10. Note, that the result of part (i) of Proposition 4.9 holds for any selection of
feedback laws vi = ki,pri (l) (·) that satisfy Properties (P1) and (P2). Respectively, the results of
parts (iia) and (iib) hold for all selections of feedback laws vi = ki,pri (l) (·) that satisfy Property
(P).
In the final result of this section, we merge the results of Propositions 4.8 and 4.9, and show
that each infinite discrete behaviour of the decentralized abstraction can be implemented by a
continuous controller, which is compatible with the restrictions on the free inputs, and produces
a continuous trajectory that satisfies the Invariance Assumption (IA). In particular, we prove
that for each possible discrete transition sequence of the overall system which is compatible with
the individual transition system of each agent, there exists a trajectory of the continuous time
system (3.1)-(3.2) which satisfies (IA) and generates the discrete trajectory when sampled at
time intervals of length δt. Before proceeding, we introduce the following notion of the product
transition system.

12

D. BOSKOS AND D. V. DIMAROGONAS

Definition 4.11. (i) Consider the space-time discretization S − δt, and for each agent i ∈ N ,
its individual transition system T Si as provided by Definition 4.4. The product transition
system T SP := (QP , ActP , −→P ) is defined as follows:
• QP := I N (all possible cell configurations)
• ActP := {∗}1
∗

0
• l −→P l0 , iff li0 ∈ Posti (li ; pri (l)), ∀i ∈ N , for all l = (l1 , . . . , lN ), l0 = (l10 , . . . , lN
).

(ii) Given an initial cell configuration l0 ∈ I N , a path originating from l0 in T SP , is an infinite
∗
sequence of states l0 l1 l2 . . . such that li −→ li+1 for all i ∈ N ∪ {0}. /
Remark 4.12. Given a well posed space-time discretization S − δt and an initial cell configuration l0 ∈ I N , it follows from Remark 4.5 and Definition 4.11 that there exists at least one
path l0 l1 l2 . . . in T SP originating from l0 . /
We are now in position to state the result providing the consistency between the discrete
plan level and the continuous controller implementation.
Proposition 4.13. Assume that the space-time discretization S −δt is well posed for the multi0
) and path
agent system (3.1)-(3.2). Then, for each initial cell configuration l0 = (l10 , . . . , lN
0 1 2
0
N
l l l . . . originating from l in T SP , and for each initial condition x(0) ∈ D of (3.1)-(3.2)
satisfying xi (0) ∈ Sli0 , i ∈ N , there exists a free input v̄(·) satisfying |v̄i (t)| ≤ vmax , ∀t ≥ 0,
i ∈ N , such that the solution x(t) of the system remains in DN for all t ≥ 0 and satisfies
xi (mδt) ∈ Slim for each m ∈ N and i ∈ N .
Proof. The proof is carried out by induction and is based on the results of Propositions 4.8 and
4.9 (iib). Before stating the induction hypothesis, we provide certain basic properties of the
deterministic control system (3.1)-(3.2) which can be found in [20, Chapter 1], or [26, Chapter
2].
Recall that according to our hypotheses, the input set U of the multi-agent system consists
of all piecewise continuous inputs v : R≥0 → RN n satisfying |vi (t)| ≤ vmax , ∀t ≥ 0, i ∈ N . Also,
for each r > 0 we define the shift operator Shr : U → U as
Shr (v)(t) := v(t + r), ∀t ≥ 0,
which implies that
v 0 = Shr (v) ⇐⇒ v 0 (t) = v(t + r), ∀t ≥ 0 ⇐⇒ v 0 (t − r) = v(t), ∀t ≥ r.

(4.12)

To the control system (3.1)-(3.2) we associate the transition map ϕ : Aϕ → DN with
Aϕ := {(t, t0 , x0 ; v) : t ≥ t0 ≥ 0, x0 ∈ DN , v ∈ U},
where ϕ(t, t0 , x0 ; v) denotes the value at time t of the unique solution of (3.1)-(3.2) with initial
condition x0 at time t0 and input v(·). Notice, that by virtue of the Invariance Assumption
(IA), ϕ(·) is well defined. The map ϕ(·) satisfies the following properties:
•Causality. For each t > t0 ≥ 0, x0 ∈ DN and v 1 , v 2 ∈ U with v 1 |[t0 ,t) = v 2 |[t0 ,t) it holds
ϕ(t, t0 , x0 ; v 1 ) = ϕ(t, t0 , x0 ; v 2 ),
where v 1 |[t0 ,t) denotes the restriction of v 1 (·) to [t0 , t) (see Section 2).
1Following notation [27, page 11]

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS13

•Semigroup Property. For each t2 ≥ t1 ≥ t0 ≥ 0, x0 ∈ DN and v ∈ U it holds
ϕ(t2 , t1 , ϕ(t1 , t0 , x0 ; v); v) = ϕ(t2 , t0 , x0 ; v).
•Time Invariance. For each r > 0, t ≥ t0 ≥ r, x0 ∈ DN and v ∈ U it holds
ϕ(t, t0 , x0 ; v) = ϕ(t − r, t0 − r, x0 ; Shr (v)).
0
Now consider an initial cell configuration l0 = (l10 , . . . , lN
), a path l0 l1 l2 . . . originating from
P
N
l in T S , and an initial condition x(0) ∈ D satisfying xi (0) ∈ Sli0 , i ∈ N . We will determine
a free input v̄(·) satisfying |v̄i (t)| ≤ vmax , ∀t ≥ 0, i ∈ N , such that the corresponding solution
x(t) := ϕ(t, 0, x(0); v̄) remains in DN for all t ≥ 0 and satisfies xi (mδt) ∈ lim for each m ∈ N
and i ∈ N . The construction of v̄(·) is based on the following Induction Hypothesis, which
constitutes the core of the proposition.
0

Induction Hypothesis (IH). For each m ∈ N there exists a piecewise continuous input
v m : R≥0 → RN n satisfying |vim (t)| ≤ vmax , ∀t ≥ 0, i ∈ N and such that
v m |[0,κδt) = v κ |[0,κδt) , ∀κ = 1, . . . , m − 1,
m

κ

ϕ(t, 0, x(0); v ) = ϕ(t, 0, x(0); v ), ∀κ = 1, . . . , m − 1, t ∈ [0, κδt],
m

ϕi (mδt, 0, x(0); v ) ∈ S , ∀i ∈ N .

(4.13)
(4.14)
(4.15)

lim

.Proof of (IH). In order to prove (IH) for m = 1, we need to show that (4.15) is fulfilled.
∗
From the fact that xi (0) ∈ Sli0 , i ∈ N and that l0 −→ l1 , we deduce from Definition 4.11 and
Proposition 4.8 that there exist feedback laws ki,pri (l) (·) as in (4.6) (with l = l0 ), which satisfy
Property (P), and w1 , . . . , wN ∈ W such that (4.7) holds with l0 = l1 . Hence, it follows from
Proposition 4.9(iib) that there exists a piecewise continuous input v 1 : R≥0 → RN n satisfying
|vi1 (t)| ≤ vmax , ∀t ≥ 0, i ∈ N and such that
ϕi (δt, 0, x(0); v 1 ) ∈ Sli1 , ∀i ∈ N
which establishes (4.15) for m = 1.
Now assume that (IH) holds for certain m ∈ N. We will show that it is also valid for m+1. By
∗
exploiting Property (4.15) of (IH) for m and that lm −→ lm+1 , we deduce from Definition 4.11
and Proposition 4.8 that there exist feedback laws ki,pri (l) (·) as in (4.6) (with l = lm ), which
satisfy Property (P), and w1 , . . . , wN ∈ W such that (4.7) holds with l0 = lm+1 . Hence, it
follows from Proposition 4.9(iib) that there exists a piecewise continuous input v : R≥0 → RN n
satisfying |vi (t)| ≤ vmax , ∀t ≥ 0, i ∈ N and such that
ϕi (δt, 0, ϕ(mδt, 0, x(0); v m ); v) ∈ Slm+1 , ∀i ∈ N .

(4.16)

i

We following define v m+1 : R≥0 → RN n as
 m
v (t),
t ∈ [0, mδt),
v m+1 (t) :=
v(t − mδt), t ∈ [mδt, ∞).

(4.17)

Then, it follows from (4.17) that v m+1 (·) satisfies (4.13) (with m := m + 1) and the latter
implies (4.14) (with m := m + 1) by causality. Hence, we get from (4.14) that
ϕ(mδt, 0, x(0); v m+1 ) = ϕ(mδt, 0, x(0); v m ).

(4.18)

14

D. BOSKOS AND D. V. DIMAROGONAS

From the semigroup property and (4.18) we deduce that
ϕ((m + 1)δt, 0, x(0); v m+1 ) = ϕ((m + 1)δt, mδt, ϕ(mδt, 0, x(0); v m+1 ); v m+1 )
= ϕ((m + 1)δt, mδt, ϕ(mδt, 0, x(0); v m ); v m+1 ).

(4.19)

Also, we get from (4.17) and (4.12) that
v = Shmδt (v m+1 ).

(4.20)

Thus, it follows from time invariance and (4.20) that
ϕ((m + 1)δt, mδt, ϕ(mδt, 0, x(0); v m ); v m+1 ) = ϕ(δt, 0, ϕ(mδt, 0, x(0); v m ); Shmδt (v m+1 ))
= ϕ(δt, 0, ϕ(mδt, 0, x(0); v m ); v).

(4.21)

Hence, we conclude from (4.16), (4.19) and (4.21) that (4.15) also holds (with m := m + 1) and
the proof of (IH) is complete. /
In order to finish the proof of the proposition, define v̄ : R≥0 → RN n by
v̄(t) := v m (t), m ∈ N, t ∈ [(m − 1)δt, mδt),

(4.22)

with v m (·) as given by (IH) for each m ∈ N. Then, it follows from (4.22) and (IH) that
|v̄i (t)| ≤ vmax , ∀t ≥ 0, i ∈ N and thus, by the Invariance Assumption (IA), the solution x(t) of
the system remains in DN for all t ≥ 0. Furthermore, it holds that
v̄|[0,mδt) = v m |[0,mδt) , ∀m ∈ N.

(4.23)

Indeed, for each t ∈ [0, mδt) there exists κ ∈ {1, . . . , m} such that t ∈ [(κ − 1)δt, κδt). If κ = m,
then it follows from (4.22) that v̄(t) = v m (t). If κ ∈ {1, . . . , m − 1}, then we get from (4.22)
that v̄(t) = v κ (t) and thus from (4.13) that v̄(t) = v m (t). Hence, (4.23) is valid. Finally, from
(4.23), (4.15) and causality we conclude that for each m ∈ N it holds
xi (mδt) = ϕi (mδt, 0, x(0); v̄) = ϕi (mδt, 0, x(0); v m ) ∈ Slim
and the proof is complete.



We note that the result of Proposition 4.13 remains valid if we consider the product of
the agents’ controlled transition systems as given by Definition 4.6, which will be determined
explicitly in Section 6 for the control laws ki,li in (3.7). This observation is summarized in the
following remark.
Remark 4.14. Instead of the product T SP formed by the agents’ individual transition systems
c
T Si , consider the controlled product transition system T SP
:= (QcP , ActcP , −→cP ) formed
c
by the controlled transition systems T Si , i ∈ N in Definition 4.6 as follows:
• QcP = I N ;
• ActcP = {∗};
∗

• l −→cP l0 , iff there exist [w1 ], . . . , [wN ] ∈ 2W such that li0 ∈ Postci (li ; (pri (l), [wi ])), ∀i ∈ N , for
0
all l = (l1 , . . . , lN ), l0 = (l10 , . . . , lN
).
Then, the result of Proposition 4.13 remains valid for any initial cell configuration l0 and path
c
l0 l1 l2 . . . originating from l0 in T SP
. /

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS15

5. Time Domain Properties of the Control Laws
In this section we use the results of Section 4 in order to prove certain useful properties of the
reference trajectory χi (·) and the time domain [0, Ti (xi0 , wi )) of the control laws (3.7) as specified by (3.12). We proceed by providing some extra details for the dynamics as determined by
the control law in (3.2). In particular, we assume that the fi ’s are globally Lipschitz functions.
Furthermore, if we want to achieve more accurate bounds for the dynamics of the feedback
controllers assigned to the free inputs vi (those will be clarified in the proof of Theorem 6.3 in
the next section), we can choose (possibly) different Lipschitz constants L1 , L2 > 0 such that
|fi (xi , xj ) − fi (xi , yj )| ≤L1 |(xi , xj ) − (xi , yj )|,

(5.1)

|fi (xi , xj ) − fi (yi , xj )| ≤L2 |(xi , xj ) − (yi , xj )|,

(5.2)

∀xi , yi ∈D, xj , yj ∈ D

Ni

,i ∈ N.

In order to provide some extra informal motivation on considering both constants L1 and L2 ,
we recall that in order to derive sufficient conditions for a well posed discretization, we design
for each agent i inside a cell Sli a feedback, in order to “track” a given reference trajectory (of
i) starting in the same cell. In particular, the constant L1 provides bounds on the feedback
term (3.9) which compensates for the deviation of agent’s i dynamics from its corresponding
dynamics along the reference trajectory, due to the time evolution of its neighbors’ states. On
the other hand, the constant L2 provides bounds on the feedback term (3.11) which compensates
for the deviation of the initial state with respect to the initial state of the reference trajectory.
Based on the global Lipschitz assumption, we establish uniqueness of the reference trajectory
χi (·) and provide a lower bound for the right endpoint Tmax of its maximal interval of existence,
which is independent of the selection of (xi,G , xj,G ) in (3.6).
Lemma 5.1. For each tuple of reference points (xi,G , xj,G ) as in (3.6), the initial value problem
(3.14) has a unique solution which is defined and remains in D on the right maximal interval
[0, Tmax ). Furthermore, it holds
vmax
√
.
(5.3)
Tmax >
2M L1 max{ Ni : i ∈ N }
Proof. For the proof of the lemma we exploit the result of Proposition 4.9. In particular,
we show that the solution χi (·) of (3.14) coincides on a suitable time interval with the i-th
component of the solution of the multi-agent system (3.1)-(3.2) under an appropriate selection
of the initial conditions and feedback controllers for the vi ’s. Hence, by implicitly exploiting
the Invariance Assumption (IA) that leads to the result of Proposition 4.9(iia), which is valid
for any choice of feedback laws that satisfy Property (P), we will verify that (5.3) is fulfilled.
In order to proceed with the proof, let (xi,G , xj,G ) be a tuple of reference points as in
(3.6), corresponding to a cell decomposition {Sl }l∈I of D and a cell configuration li of agent
i, and consider another cell decomposition {Sloo }lo ∈Io of D and an initial cell configuration
lo = (lo1 , . . . , loN ) ∈ IoN with pri (lo ) = (loi , loj1 , . . . , lojNi ), such that
xi,G ∈ Slooi and Sloojκ = xjκ ,G , κ = 1, . . . , Ni .

(5.4)

We have selected the auxiliary cell decomposition {Sloo }lo ∈Io with the sets Sloojκ consisting of a
single element, because this slightly simplifies the subsequent analysis and also allows obtaining
a greater (uniform) lower bound for the time Tmax . Next, define the time step
vmax
√
(5.5)
δto :=
2M L1 max{ Ni : i ∈ N }

16

D. BOSKOS AND D. V. DIMAROGONAS

and consider the feedback laws ki,pri (lo ) : DNi +1 → Rn given by
ki,pri (lo ) (xi , xj ) := fi (xi , xj,G ) − fi (xi , xj ) = Fi,li (xi ) − fi (xi , xj ),

(5.6)

with Fi,li (·) as in (3.13) and k`,pr` (lo ) : DN` +1 → Rn for ` ∈ N \ {i} given by
k`,pr` (lo ) (x` , xj(`) ) := 0.

(5.7)

Note that the feedback laws k`,pr` (lo ) (·) for ` ∈ N \ {i} satisfy Property (P) by default. Hence,
in order to invoke Proposition 4.9(iia), we show that ki,pri (lo ) (·) also satisfies (P). Property (P3)
is obvious, since ki,pri (lo ) (·) is independent of t. Property (P1) follows from the corresponding
Lipschitz property for fi (·) and Fi,li (·), since the latter satisfies the Lipschitz condition
|Fi,li (x) − Fi,li (y)| ≤ L2 |x − y|, ∀x, y ∈ D.

(5.8)

Indeed, due to (5.2) and (3.13), we have that for each x, y ∈ D it holds
|Fi,li (x) − Fi,li (y)| = |fi (x, xj,G ) − fi (y, xj,G )| ≤ L2 |(x, xj,G ) − (y, xj,G )| = L2 |x − y|.
In order to show (P2), notice that due to (5.5) we get
p
vmax ≥ 2M δto L1 Ni , for all i ∈ N .

(5.9)

Hence, we get from (4.1), (5.1), (3.5), (5.4) and (5.9) that for every xi ∈ (Slooi + B(Rmax )) ∩ D
and xjκ ∈ B(xjκ ,G , Rmax ) ∩ D, κ = 1, . . . , Ni , it holds
|ki,pri (lo ) (xi , xj )| =|fi (xi , xj ) − fi (xi , xj )| ≤ L1 |xj − xj,G | = L1

Ni
X

! 12
2

(xjκ − xjκ ,G )

κ=1

≤L1

p
p
p
Ni Rmax = L1 Ni δto (M + vmax ) < 2M δto L1 Ni ≤ vmax ,

and thus (P2) holds as well, since ki,pri (lo ) (·) is independent of t, xi0 and wi . Then, it follows
from Proposition 4.9(iia) that the solution x(t) of the closed-loop system (3.1)-(3.2), (5.6)-(5.7)
with initial condition x(0) ∈ DN satisfying xi (0) = xi,G , xj1 (0) = xj1 ,G , . . . , xjNi (0) = xjNi ,G
(and the initial state of each other agent ` belonging to Sloo` ) is defined and remains in DN for
all t ∈ [0, δto ]. Hence, the i-th component of the solution x(·) satisfies
xi (t) ∈ D, ∀t ∈ [0, δt0 ],

(5.10)

and by virtue of (3.1)-(3.2) and (5.6), it holds
ẋi = Fi,li (xi ), xi (0) = xi,G , t ∈ [0, δt0 ].

(5.11)

Hence, it follows from (5.11) that xi (·) coincides with the unique solution χi (·) of (3.14) on
[0, δto ] ∩ [0, Tmax ), which in conjunction with (5.10) implies that χi (t) remains in a compact
subset of D for t ∈ [0, δto ] ∩ [0, Tmax ). From the latter, we deduce that Tmax > δto . Indeed, otherwise χi (t) would remain in a compact subset of D for t ∈ [0, Tmax ), contradicting maximality
of [0, Tmax ). Thus, we conclude that (5.3) is satisfied.

By exploiting Lemma 5.1, it will be shown in the next section that Tmax is always greater
than the maximum possible selection of the time step δt for a well posed discretization. The
latter in conjunction with the result of Lemma 5.2 below enables us to prove that in this case
the control law ki,li ,3 (·) and hence also ki,li (·) are well defined on [0, δt].

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS17

Lemma 5.2. Consider a cell decomposition S of D, a time step δt and select an agent i ∈ N
and a cell configuration li = (li , lj1 , . . . , ljNi ) of i. Also, consider a tuple of reference points
(xi,G , xj,G ) as in (3.6) and the control law ki,li (·) in (3.7). We assume that ki,li (·) satisfies
Properties (P1) and (P2) of Definition 4.1, and that the right endpoint Tmax of the interval
where the reference trajectory (3.14) is defined, satisfies Tmax > δt. Then, for all xi0 ∈ Sli and
wi ∈ W , the time Ti (xi0 , wi ) satisfies Ti (xi0 , wi ) > δt, which implies that ki,li (·) also satisfies
Property (P3) of Definition 4.1.

Proof. Indeed, let xi0 ∈ Sli and wi ∈ W . By defining


t
(xi0 − xi,G ), t ∈ [0, Tmax ),
x̂i (t) := x̄i (t) + 1 −
δt

(5.12)

with x̄i (t) = χi (t) + twi as given in (3.15), and taking into account the definition of T (xi0 , wi )
in (3.12), we want to show that x̂i (·) remains in D for more than time δt. By virtue of our
assumption that Tmax > δt, the latter is meaningful to verify and implies that T (xi0 , wi ) > δt.
We next show that x̂i (·) coincides on a suitable time interval with the i-th component of the
solution of (3.1)-(3.2) by choosing appropriate initial conditions and feedback laws that satisfy
(P1) and (P2).
Let xi0 ∈ Sli , wi ∈ W , consider an arbitrary initial cell configuration l with pri (l) = li ,
l = (l1 , . . . , lN ), and assign the feedback law ki,pri (l) = ki,li (as the latter is given by (3.7)) to
i and the feedback laws k`,pr` (l) := 0 to the rest of the agents ` ∈ N \ {i}. It also follows from
the assumptions of the lemma for i, and trivially for the other agents, that the feedback laws
satisfy Properties (P1) and (P2). Thus, we can use the result of Proposition 4.9(i). By selecting
an initial condition x(0) ∈ DN with xi (0) = xi0 and xjm (0) ∈ Slm , m = 1, . . . , Ni , and recalling
that wi ∈ W , we get from Proposition 4.9(i) that the i-th component of the solution satisfies
xi (t) ∈ D, ∀t ∈ [0, T̃ ), T̃ := min{δt, T (xi0 , wi )}
lim xi (t) ∈ D.

(5.13)
(5.14)

t→T̃ −

We proceed by showing that xi (t) = x̂i (t), for all t ∈ [0, T̃ ), with T̃ as given in (5.13), or
equivalently, that


t
xi (t) = χi (t) + twi + 1 −
(xi0 − xi,G ), ∀t ∈ [0, T̃ )
δt

(5.15)

Indeed, from (3.15), (3.14), (3.1)-(3.2), (3.7), (3.9) and (3.13) we have that
x̄˙ i (t) = Fi,li (χi (t)) + wi ,
ẋi (t) = Fi,li (xi (t)) + ki,li ,2 (xi0 ) + ki,li ,3 (t; xi0 , wi ).
By recalling that x̄i (0) = xi,G , xi (0) = xi0 and that due to (3.12) and (5.13) it holds T̃ ≤
T (xi0 , wi ) ≤ Tmax , and thus χi (·), xi (·) and ki,li ,3 (·) are well defined on [0, T̃ ), it follows from

18

D. BOSKOS AND D. V. DIMAROGONAS

(3.10), (3.11) and (3.15) that
Z

t

[Fi,li (xi (s)) − Fi,li (χi (s))

xi (t) − x̄i (t) = xi0 − xi,G +
0

+ ki,li ,2 (xi0 ) + ki,li ,3 (s; xi0 , wi ) − wi ]ds


Z t
t
= 1−
[Fi,li (xi (s))
(xi0 − xi,G ) +
δt
0


i
s
− Fi,li x̄i (s) + 1 −
(xi0 − xi,G ) ds, ∀t ∈ [0, T̃ ).
δt

Hence, we get from (5.8) that for all t ∈ [0, T̃ ) it holds |xi (t) − x̄i (t) − 1 − δtt (xi0 − xi,G )| ≤

Rt
s
L xi (s) − x̄i (s) − 1 − δt
(xi0 − xi,G ) ds. Application of the Gronwall Lemma, (3.15), and
0 2
the fact that T̃ ≤ Tmax , imply that (5.15) holds.
We are now in position to prove that T (xi0 , wi ) > δt. Indeed, suppose on the contrary that
T (xi0 , wi ) ≤ δt, which by virtue of the assumption that Tmax > δt, and (5.13), implies that
T (xi0 , wi ) < Tmax and T̃ = T (xi0 , wi ). From the latter, together with (5.12), (5.13), (5.14) and
continuity of x̂i (·), we get that x̂i (T (xi0 , wi )) = limt→T (xi0 ,wi )− x̂i (t) = limt→T (xi0 ,wi )− xi (t) ∈
D. Hence, from (5.12), the deduction that T (xi0 , wi ) < Tmax and continuity of x̂i (·), it follows
that there exists ε > 0 such that x̂i (t) ∈ D for t ∈ [T (xi0 , wi ), T (xi0 , wi ) + ε), which contradicts
(3.12). Thus we conclude that T (xi0 , wi ) > δt, which establishes validity of (P3).

6. Well Posed Space-Time Discretizations with Motion Planning Capabilities
In this section, we exploit the controllers introduced in (3.7) to provide sufficient conditions
for well posed space-time discretizations. By exploiting the result of Proposition 4.8 this framework can be applied for motion planning, by specifying different possibilities for transitions
for each agent through modifying its controller. Consider again the system (3.1)-(3.2), a cell
decomposition S = {Sl }l∈I of D and a time step δt. In addition, consider the least upper
bound on the diameter of the cells in S, namely,
dmax := sup{diam(Sl ), l ∈ I},

(6.1)

which due to Definition 3.1 is well defined. We will call dmax the diameter of the cell decomposition. Our goal is to determine sufficient conditions relating the Lipschitz constants L1 , L2 ,
the bounds M , vmax for the system’s dynamics, as well as the space and time scales dmax and
δt of the space-time discretization S − δt, which guarantee that S − δt is well posed. According
to Definition 4.3, establishment of a well posed discretization is based on the selection of appropriate feedback laws which guarantee well posed transitions for all agents and their possible
cell configurations. For each agent i ∈ N and cell configuration li = (li , lj1 , . . . , ljNi ) of i let
(xi,G , xj,G ) be a reference point as in (3.6). We consider the family of feedback laws given
in (3.9), (3.10), (3.11), and parameterized by xi0 ∈ Sli and wi ∈ W . The function Fi,li (·) is
given in (3.13), and χi (·) is the reference solution of the initial value problem (3.14), defined
on [0, Tmax ). Recall that the parameter λ in (3.8) provides the portion of the free input that is
exploited for planning. Thus, it can be regarded as a measure for the degree of control freedom
that is chosen for the abstraction. In the following results, we also introduce an additional parameter µ which provides a lower bound on the minimum number (≥ 1) of discrete transitions
that are possible from each initial cell, as will be clarified in the corollary at the end of the
section. Before proceeding to the desired sufficient conditions for well posed discretizations and

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS19

their reachability properties, we prove the auxiliary Propositions 6.1 and 6.2. Proposition 6.1
below provides bounds on the hybrid control laws ki,li (·) in (3.7).
Proposition 6.1. Consider a cell decomposition S of D with diameter dmax and a time step
δt. Also, for each agent i ∈ N and cell configuration li = (li , lj1 , . . . , ljNi ) of i let (xi,G , xj,G ) be
a reference point as in (3.6) and consider the feedback law ki,li (·) in (3.7). Then its components
ki,li ,1 (·), ki,li ,2 (·) and ki,li ,3 (·) as given in (3.9), (3.10) and (3.11), respectively, satisfy the
bounds
p
|ki,li ,1 (xi , xj )| ≤ L1 Ni (Rmax + dmax ), ∀xi ∈ D,
xjm ∈ (Slm + B(Rmax )) ∩ D, m = 1, . . . , Ni ,
1
|ki,li ,2 (xi0 )| ≤ dmax , ∀xi0 ∈ Sli ,
δt
|ki,li ,3 (t; xi0 , wi )| ≤ L2 (δtλvmax + dmax ) + λvmax ,

(6.2)

∀t ∈ [0, δt] ∩ [0, T (xi0 , wi )), xi0 ∈ Sli , wi ∈ W.

(6.4)

(6.3)

with Rmax as given in (4.1).
Proof. Indeed, in order to show (6.2) let xj ∈ DNi satisfying xjm ∈ (Slm + B(Rmax )) ∩ D, m =
1, . . . , Ni . Then, for each m = 1, . . . , Ni there exists x̂jm with x̂jm ∈ Slm and |x̂jm −xjm | ≤ Rmax .
Hence, from the latter together with (3.9) and (5.1), we get
|ki,li ,1 (xi , xj )| ≤ L1 |(xj1 − xj1 ,G , . . . , xjNi − xjNi ,G )|
≤ L1

Ni
X

! 21
2

(|xjm − x̂jm | + |x̂jm − xjm ,G |)

m=1

≤ L1

Ni
X

! 12
(Rmax + dmax )2

= L1

p

Ni (Rmax + dmax ),

m=1

which establishes (6.2). Furthermore, by recalling that xi,G ∈ Sli , it follows directly from (3.10)
1
that |ki,li ,2 (xi0 )| = δt
|xi0 − xi,G | and hence, that (6.3) is satisfied. Finally, for ki,li ,3 (·) we get
from (3.11) and (5.8) that


|ki,li ,3 (t; xi0 , wi )| ≤ L2 χi (t) + twi + 1 − δtt (xi0 − xi,G ) − χi (t) + |wi |,
which due to (3.8) implies validity of (6.4).



Based on the result of Proposition 6.1 we next provide conditions on dmax and δt which
guarantee that the feedback laws ki,li (·) satisfy Property (P). Additionally it is shown that the
radius r introduced in (3.16) satisfies a design requirement which is related later in Corollary 6.7
to a lower bound on the number of possible transitions through the parameter µ.
Proposition 6.2. Consider a cell decomposition S of D with diameter dmax , a time step δt,
the parameters λ ∈ (0, 1), µ > 0 and define
p
(6.5)
L := max{3L2 + 4L1 Ni , i ∈ N },
with L1 and L2 as given in (5.1) and (5.2). We assume that λ, µ, dmax and δt satisfy the
following restrictions, as provided by the three cases below:

20

D. BOSKOS AND D. V. DIMAROGONAS

2λ
Case I. 0 ≤ µ ≤ 1−λ
.


2
(1 − λ)2 vmax
dmax ∈ 0,
,
(6.6)
4M L
#
"
p
p
2
2
− 4M Ldmax (1 − λ)vmax + (1 − λ)2 vmax
− 4M Ldmax
(1 − λ)vmax − (1 − λ)2 vmax
.
δt ∈
,
2M L
2M L
(6.7)

Case II.

2λ
1−λ

4λ
1−λ .

<µ<



2
2(λ(1 − λ)µ − 2λ2 )vmax
0,
,
µ2 M L
#
p
2
(1 − λ)vmax + (1 − λ)2 vmax
− 4M Ldmax
µ
dmax ,
,
δt ∈
2λvmax
2M L
dmax ∈
"

(6.8)
(6.9)

or

dmax ∈

2
2
2(λ(1 − λ)µ − 2λ2 )vmax
(1 − λ)2 vmax
,
µ2 M L
4M L


(6.10)

and δt satisfies (6.7).
Case III. µ ≥

4λ
1−λ .

dmax and δt satisfy (6.8) and (6.9), respectively.

Then, the intervals in Cases I, II, III are well defined, and for each agent i ∈ N , cell configuration li = (li , lj1 , . . . , ljNi ) of i and reference point (xi,G , xj,G ) as in (3.6) the solution χi (t) of
(3.14) is defined and remains in D for all t ∈ [0, δt]. In addition the feedback law ki,li (·) in (3.7)
satisfies property (P) and the distance r as defined in (3.16) satisfies the design requirement
µ
(6.11)
r ≥ dmax
2
Proof. The proof of the fact that the intervals in Cases I, II, III are well defined is provided in
the Appendix. Also, it follows from Lemma 5.1 that for any reference point (xi,G , xj,G ) as in
(3.6) the solution χi (t) of (3.14) is defined and remains in D for all t ∈ [0, Tmax ), and by virtue
of (5.3) and the assumed bounds on δt in Cases I, II, III, that
Tmax > δt,

(6.12)

establishing thus that χi (t) ∈ D for all t ∈ [0, δt]. We break the subsequent proof in the
following steps.
STEP 1: Verification of Properties (P1) and (P2) for the feedback law (3.7) for
dmax − δt as given by Cases I, II, III, in conjunction with the design requirement
(6.11). In this step we prove that the proposed feedback law (3.7) satisfies Properties (P1) and
(P2). Verification of (P1) is straightforward. Thus, we proceed to show that (4.2) holds, which
implies (P2), and simultaneously, that (6.11) is fulfilled. By taking into account (3.7) and the
result of Proposition 6.1, namely, (6.2), (6.3) and (6.4), we need to prove that
p
1
L1 Ni (Rmax + dmax ) + dmax
δt
+L2 (δtλvmax + dmax ) + λvmax ≤ vmax .
(6.13)
By recalling (4.1), (3.5) and the fact that λ ∈ (0, 1) we get that δtλvmax ≤ Rmax
2 . Also, from the
fact that dmax and δt are selected according to the Cases I, II, III, it follows from elementary

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS21

calculations which are provided in the Appendix that
dmax ≤ Rmax .
(6.14)
√
1
Hence, it suffices instead of (6.13) to show that (2L1 Ni + 23 L2 )Rmax + δt
dmax ≤ (1 − λ)vmax ,
which by virtue of (4.1) is equivalent to
p
3
(M + vmax )(2L1 Ni + L2 )δt2 − (1 − λ)vmax δt + dmax ≤ 0.
(6.15)
2
√
By taking into account (3.5), it suffices instead of (6.15) to show that M (3L2 + 4L1 Ni )δt2 −
(1 − λ)vmax δt + dmax ≤ 0 which by virtue of (6.5) follows from
M Lδt2 − (1 − λ)vmax δt + dmax ≤ 0.

(6.16)

In order for the above equation to have real roots, it is required that
2
(1 − λ)2 vmax
− 4M Ldmax ≥ 0 ⇐⇒ dmax ≤

2
(1 − λ)2 vmax
.
4M L

(6.17)

Hence, by collecting our requirements (6.17), (6.16), (6.14) and (6.11) together with the fact
that dmax > 0 we have
2
(1 − λ)2 vmax
,
(6.18)
p4M L
p
2
2
(1 − λ)vmax − (1 − λ)2 vmax
− 4M Ldmax
− 4M Ldmax
(1 − λ)vmax + (1 − λ)2 vmax
≤ δt ≤
,
2M L
2M L
(6.19)
1
dmax ≤ δt,
(6.20)
M + vmax
µ
dmax ≤ δt.
(6.21)
2λvmax

0 < dmax ≤

We can then show that for all Cases I, II and III as in the statement of the proposition the
above requirements are satisfied and hence, that (P2) holds. The proof of this fact can be found
in the Appendix.
STEP 2: Verification of Property (P3). In order to show (P3), it suffices to prove that
for the given selection of λ ∈ (0, 1), µ > 0, dmax and δt as provided by Cases I, II, III, the agent
i and the cell configuration li it holds T (xi0 , wi ) > δt, for all xi0 ∈ Sli and wi ∈ W . The latter
is a direct consequence of (6.12) and Lemma 5.2.

We are now in position to state our main result on sufficient conditions for well posed
abstractions.
Theorem 6.3. Consider a cell decomposition S of D with diameter dmax , a time step δt, the
parameters λ ∈ (0, 1), µ > 0 and assume that λ, µ, dmax and δt satisfy the restrictions of
Proposition 6.2. Then, for each agent i ∈ N and cell configuration li = (li , lj1 , . . . , ljNi ) of i
we have Posti (li ; li ) 6= ∅, namely, the space-time discretization is well posed for the multi-agent
system (3.1)-(3.2). In particular, for any tuple of reference points (xi,G , xj,G ) as in (3.6) and
corresponding reference trajectory χi (·) of i as given by (3.14) it holds
B(χi (δt); r) ⊂ D,
Posti (li ; li ) ⊃ {l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅},
where r is defined in (3.16).

(6.22)
(6.23)

22

D. BOSKOS AND D. V. DIMAROGONAS

Proof. For the proof, pick i ∈ N , li = (li , lj1 , . . . , ljNi ), (xi,G , xj,G ) as in (3.6) and notice that
by virtue of Proposition 6.2, the reference trajectory χi (·) is well defined on [0, δt]. In addition,
consider the control law ki,li (·) in (3.7). Then, it follows again from Proposition 6.2 that the
latter satisfies Property (P). Next, for each x ∈ B(χi (δt); r) define
wi (= wi (x)) :=
Then, we get from (3.16) that |wi | ≤

r
δt

x − χi (δt)
.
δt

(6.24)

= λvmax and hence, by virtue of (3.8) that

wi (= wi (x)) ∈ W, ∀x ∈ B(χi (δt); r).

(6.25)

In order to prove the theorem, we need to verify that (6.22) and (6.23) are fulfilled.
Proof of (6.22). In order to show (6.22), pick x ∈ B(χi (δt); r), wi as in (6.24) and recall
that the control law ki,li (·) satisfies Property (P). Then we have from (6.25) that wi ∈ W and
thus, we get from Property (P3) applied with xi0 = xi,G and the selected parameter wi that
T (xi,G , wi ) > δt. From the latter and (3.12) we obtain that χi (δt) + wi δt ∈ D, which by virtue
of (6.24) implies that x ∈ D and establishes validity of (6.22).
Proof of (6.23). For the verification of (6.23) it suffices to prove the following claim.
Claim II. Consider the control law ki,li (·) above and pick any wi ∈ W . Then, for any initial
cell configuration l with pri (l) = li , l = (l1 , . . . , lN ), ` ∈ N \ {i} and selection of feedback laws
in (4.4) which satisfy (P) the following hold. The solution of the closed-loop system (3.1)-(3.2),
(3.7), (4.3), (4.4), with the selected parameter wi for ki,li (·), is well defined on [0, δt] and satisfies
xi (δt)(:= xi (δt, x(0))) = χi (δt) + δtwi = x̄i (δt),

(6.26)

for all x(0) ∈ DN with xm0 ∈ Slm , m ∈ N and wm ∈ W , m ∈ N \ {i}, with the last equality
in (6.26) being a consequence of (3.15) (see also Fig. 2 in Section 3). /
Indeed, let any l ∈ I such that
Sl ∩ B(χi (δt); r) 6= ∅.

(6.27)
l

i
In order to show that l ∈ Posti (li ; li ), i.e., that the transition li −→
l is well posed, it suffices
according to Definition 4.3(i) to verify that there exists wi ∈ W such that Condition (C) holds
with the control law ki,li (·) above. By exploiting (6.27), we pick x ∈ Sl ∩ B(χi (δt); r) and wi in
(6.24) as the parameter for ki,li (·), which by virtue of (6.25) satisfies wi ∈ W . Thus, it follows
that the conclusion of Claim II is fulfilled with (6.24) and (6.26) implying that xi (δt) = x ∈ Sl .

l

i
Hence, Condition (C) is satisfied and we conclude that li −→
l is well posed. It thus remains
to verify Claim II.

Proof of Claim II. Let x, ki,li (·) and wi (= wi (x)) as in the statement of Claim II. We
first note that due to Proposition 4.9(iia), the solution of the closed-loop system is defined
and remains in DN on the whole interval [0, δt]. In order to show that xi (δt) = x̄i (δt), we
show that xi (·) is an appropriate
modification of the trajectory x̄i (·). In particular, it holds

xi (t) = x̄i (t) + 1 − δtt (xi0 − xi,G ), ∀t ∈ [0, δt], which implies the desired result. The proof of
the latter is based precisely on the same arguments used for the proof of (5.15) in Lemma 5.2
and is therefore omitted. Hence, we conclude that xi (δt) = x̄i (δt) and the proof is complete. 
Remark 6.4. Notice that the reachable cells provided by the left hand side of (6.23) are a subset
of the reachable cells from the specific cell configuration of i. In addition, these cells depend on
the reference points (xi,G , xj,G ), since a different selection will correspond to a different control

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS23

law ki,li and will lead in principle to another reference trajectory, thus, modifying the center of
the ball B(χi (δt); r). /
Based on the above remark, we next show that by selecting for each agent i and cell configuration li a tuple of reference points (xi,G , xj,G ) and the control law (3.7), the right hand side
of (6.23) provides the set ∪[wi ]∈2W Postci (li ; (li , [wi ])) of the controlled transition systems T Sic
in Definition 4.6.
Corollary 6.5. Consider a space-time discretization S −δt satisfying the hypotheses of Theorem
6.3. Also, select for each agent i and cell configuration li , a tuple of reference points (xi,G , xj,G )
as in (3.6), the control law ki,li (·) in (3.7) and consider the corresponding reference trajectory
χi (·) given by (3.14). Then, for each i, li = (li , lj1 , . . . , ljNi ) and l ∈ I the actions [wi ](li ,l) in
(4.5) for the specification of the controlled transition system T Sic are given as


x − χi (δt)
: x ∈ Sl ∩ B(χi (δt); r) ,
(6.28)
[wi ](li ,l) =
δt
with r as in (3.16), and it holds
∪[wi ]∈2W Postci (li ; (li , [wi ]))
= {l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅}.

(6.29)

Proof. Proof of (6.28). We first consider the case where Sl ∩ B(χi (δt); r) 6= ∅ and show that
[wi ](li ,l) ⊃ { x−χδti (δt) : x ∈ Sl ∩ B(χi (δt); r)}. Indeed, let x ∈ Sl ∩ B(χi (δt); r) and wi as given by
(6.24), which by virtue of (6.25) satisfies wi ∈ W . Thus, from Claim II in the proof of Theorem
6.3 we obtain that li , ki,li (·), wi and l satisfy Condition (C), since (6.24) and (6.26) imply that
xi (δt) = x ∈ Sl . Thus, we obtain from (4.5) that x−χδti (δt) ∈ [wi ](li ,l) . In order to prove the
reverse inclusion, let wi ∈ [wi ](li ,l) ⊂ W and assume on the contrary that


x − χi (δt)
: x ∈ Sl ∩ B(χi (δt); r) .
(6.30)
wi ∈
/
δt
Let x = χi (δt) + δtwi and notice that due to (3.8) and (3.16) it holds x ∈ B(χi (δt); r). In
addition, by exploiting Claim II applied with this selection of wi , we obtain from (6.26) that
xi (δt) = χi (δt) + δtwi = x. Also, since wi ∈ [wi ](li ,l) we get from (4.5), namely, the fact that
li , ki,li (·), wi , l satisfy Condition (C), that xi (δt) ∈ Sl . Thus, x ∈ Sl ∩ B(χi (δt); r) which
contradicts (6.30).
Finally, in order to verify (6.28) for the general case we need to show that [wi ](li ,l) = ∅ when
Sl ∩ B(χi (δt); r) = ∅. Notice that the latter is equivalently written as
|x − χi (δt)| > r, ∀x ∈ Sl .

(6.31)

Hence, suppose on the contrary that (6.31) holds and that [wi ](li ,l) 6= ∅. Then, by picking any
wi ∈ [wi ](li ,l) ⊂ W , we obtain from (6.26) in Claim II that xi (δt) = χi (δt) + δtwi . On the
other hand, since wi ∈ [wi ](li ,l) , we get from (4.5) that xi (δt) ∈ Sl . Hence, it follows that
r
χi (δt) + δtwi ∈ Sl which by virtue of (6.31) implies that |wi | > δt
. Thus, we obtain from (3.8)
and (3.16) that wi ∈
/ W , which is a contradiction.
Proof of (6.29). This follows directly from (6.28) and the definition of transitions in T Sic as
provided by Definition 4.6.

Remark 6.6. It is noted that if we select W in (3.8) as the open ball int(B(λvmax )) we will
obtain in (6.23) the cells which have nonempty intersection with the open ball int(B(χi (δt); r)).

24

D. BOSKOS AND D. V. DIMAROGONAS

In this case, it follows from the properties of a cell decomposition that each transition system
T Sic is deterministic. The latter relies on the requirement that the interiors of the cells in the
decomposition are disjoint and the fact that when the intersection of a cell with this ball is
nonempty, it will also have nonempty interior. /
The results of Theorem 6.3 and Corollary 6.5 can be utilized for motion planning tasks
through the following procedure:
Step 1. Given the Lipschitz constants L1 , L2 and the bounds M , vmax on the agents’ dynamics,
pick design parameters λ, µ and select a well posed space-time discretization S − δt for the
multi-agent system based on Theorem 6.3.
Step 2. Fix a reference point for each cell Sl of the decomposition {Sl }l∈I . Then, derive
the controlled transition system T Sic of each agent i as follows. For each cell configuration
li = (li , lj1 , . . . , ljNi ) compute the endpoint χi (δt) of the reference trajectory (3.14) at time δt,
corresponding to the reference points xi,G , xj1 ,G , . . . , xjNi ,G of the cells Sli , Slj1 , . . . , SljN , as
i
selected at the beginning of Step 2. Then, specify the cells which have nonempty intersection
(li ,[wi ])

with B(χi (δt); r), in order to obtain all the transitions li −→ci li0 to the cells in (6.29), with
[wi ] = [wi ](li ,li0 ) as given by (6.28). Also, note that the actions [wi ] do not need to be specified
until Step 4.
c
defined in
Step 3. Find a path l0 l1 l2 · · · in the controlled product transition system T SP
Remark 4.14 which satisfies the plan and project it for each agent i to a sequence of transitions

li0

(l0i ,[wi ]0 )
(l1i ,[wi ]1 )
c
1
−→i li −→ci li2

···.

Step 4. Select the control laws to implement the individual transitions by the continuous time
m
(lm
i ,[wi ] )

system as follows. For each transition lim −→ci lim+1 pick any parameter wi ∈ [wi ]m =
[wi ](lm ,lm+1 ) , with the latter as given in (6.28), and apply the control law (3.7) with the selected
i
i
wi .
The following corollary provides a lower bound for the minimum number of cells each agent
can reach in time δt, depending on the selection of the design parameter µ for the space-time
discretization.
Corollary 6.7. Consider a cell decomposition S of D with diameter dmax , a time step δt, and
parameters λ ∈ (0, 1), µ > 0 such that the hypotheses of Theorem 6.3 are fulfilled. Then for
each agent i ∈ N and each cell configuration of i, there exist at least bµn c + 1, if µn ∈
/ N, or
bµn c, if µn ∈ N possible discrete transitions.
Proof. In order to prove the result, we need by virtue of (6.23) to show that

bµn c + 1, if µn ∈
/ N,
#{l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅} ≥
bµn c,
if µn ∈ N,

(6.32)

where # denotes the cardinality of a set. By using the notation Vol(S) for the volume (Lebesgue
measure) of a measurable set S ⊂ Rn , it follows from (6.1) and the iso-diametric inequality
that for each l ∈ I it holds
 
n
 
dmax
dmax
=
β(n) := Smax ,
(6.33)
Vol(Sl ) ≤ Vol B
2
2
where
β(n) := Vol(B(1)),

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS25

namely, the volume of the ball with center 0 and radius 1 in Rn . It then follows from (6.22),
namely, that B(χi (δt); r) ⊂ D, (6.33) and the fact that due to Definition 3.1 it holds ∪l∈I Sl =
D, that
(
(δt);r))
i (δt);r))
b Vol(B(χ
c + 1, if (B(χSimax
∈
/ N,
Smax
(6.34)
#{l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅} ≥
(B(χi (δt);r))
(B(χi (δt);r))
c,
if
∈ N.
b
Smax
Smax
By taking into account (6.11) and (6.33), we get that
Vol (B(χi (δt); r))
≤
Smax

n
µ
β(n)
2 dmax

dmax n
β(n)
2

= µn

(6.35)

and thus, (6.32) is a direct consequence of (6.34) and (6.35). The proof is now complete.



Finally, we provide certain upper bounds on the complexity of the controlled transition
system of each agent as a function of λ, namely, the part of the input that is exploited for
reachability purposes. Therefore, given a finite cell decomposition S = {Sl }l∈I of a bounded
domain D, it is convenient to introduce the length
din = 2 sup{R > 0 : ∀l ∈ I, ∃ x ∈ Sl , B(x, R) ⊂ Sl }

(6.36)

corresponding to the maximum diameter of a ball that can be inscribed in all cells. The following
corollary provides the corresponding complexity result.
Corollary 6.8. Consider a bounded domain D admitting a finite cell decomposition S of diameter dmax , a time step δt and a parameter λ ∈ (0, 1), such that the hypotheses of Theorem 6.3
are fulfilled with µ = 0, implying that dmax and δt satisfy (6.6) and (6.7), respectively. If in
2
(1−λ)2 vmax
,
addition dmax is the maximum possible diameter that satisfies (6.6), i.e., dmax =
4M L
then the cardinalities of the state set Qci and transition relation −→ci of agent’s i individual con1
1
trolled transition system are upper bounded by C1 (1−λ)
, respectively,
2n and C2
(1−λ)(2(Ni +1)+1)n

n

Vol(D)
Ni +1 4 n
din
4M L
with C1 = Vol(B( 1 )) cv2
, C2 = C1
, c = dmax , din as given in (6.36) and Vol(D),
c
2

max

Vol(B( 12 )) being the volume of the domain D and the ball with radius 21 in Rn , respectively. Finally, the cardinality of the state set QcP and transition relation −→cP of the controlled product
1
1
0
0
N
transition system are upper bounded by C10 (1−λ)
2N n and C2 (1−λ)3N n , respectively, with C1 = C1

N
n
and C20 = C1N 4c
.
Proof. Notice first, that when dmax =

2
(1−λ)2 vmax
,
4M L

δt =

it follows from (6.7) that necessarily

(1 − λ)vmax
.
2M L

(6.37)

Next, based on the finiteness hypothesis of S which implies that the length din as defined in
(6.36) is positive, we provide an upper bound on the number of cells in S and the number of
cells that may intersect any reachable ball in D with radius r, as the latter is given by (3.16).
First, notice that due to (6.36) it holds
Vol(Sl ) ≤ Vol(B( d2in )), ∀l ∈ I.

(6.38)

In addition, in order to obtain a bound on the cardinality of I, we exploit the facts that the cells
of the decomposition cover D and have disjoint interiors, which implies that for any subset of

26

D. BOSKOS AND D. V. DIMAROGONAS

cells, the volume of their union equals the sum of their individual volumes. The latter properties
in conjunction with (6.38) imply that
X
X
Vol(∪i∈I Sl ) = Vol(D) =⇒
Vol(Sl ) = Vol(D) =⇒
Vol(B( d2in )) ≤ Vol(D) =⇒
l∈I

l∈I

Vol(D)
Vol(D)
Vol(D) 1
1
#I ≤
=
1
1
n =
din
n
d
(cd
Vol(B( 2 )) in
Vol(B( 2 ))
Vol(B( 2 ))
max )

n

n
Vol(D)
Vol(D)
4M L
4M L
1
=
=
2
2
(1 − λ)2n
Vol(B( 12 )) c(1 − λ)2 vmax
Vol(B( 12 )) cvmax
1
,
= C1
(1 − λ)2n

(6.39)

with c and C1 as given in the statement of the corollary. We next proceed to determine an
upper bound on the number of cells which intersect any reachable ball B(χi (δt); r). Note first,
that by the definition of dmax it follows that
{l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅} ⊂ {l ∈ I : Sl ⊂ B(χi (δt); r + dmax ) 6= ∅} =⇒
#{l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅} ≤ #{l ∈ I : Sl ⊂ B(χi (δt); r + dmax )}.

(6.40)

In addition, by taking into account as above that the cells of the decomposition have disjoint
interiors, we get that

[
{Sl ∈ S : Sl ⊂ B(χi (δt); r + dmax ) ⊂ Vol(B(χi (δt); r + dmax )) =⇒
Vol
X
Vol(Sl ) ≤ Vol(B(χi (δt); r + dmax )) =⇒
{l∈I:Sl ⊂B(χi (δt);r+dmax )}

Vol(B(χi (δt); r + dmax ))
Vol(B( d2in ))
!n
r + dmax
=
.
din

#{l ∈ I : Sl ⊂ B(χi (δt); r + dmax )} ≤

(6.41)

2

From the selection of dmax in the statement of the corollary, δt in (6.37) and the definition of
r we get that
!n
!n
!n
2
2
(1−λ)2 vmax
(1−λ)vmax
max
λvmax (1−λ)v
+
r + dmax
2M L
4M L
2M L
≤
=
din
cdmax
cdmax
2

2

=

2
(1−λ)vmax
ML
2
c(1−λ)vmax
4M L

!n

2

 n
4
1
=
.
c
(1 − λ)n

(6.42)

Due to (6.39) it follows directly that the cardinality of the state set of each agent’s individ1
ual (controlled) transition system is upper bounded by C1 (1−λ)
In order to obtain the
2n .
corresponding bound for the transition relation, note that due to (6.28) and (6.29), for each
li = (li , lj1 , . . . , ljNi ) it holds that
(li ,[wi ])

li −→ci li0

iff

li0 ∈ {l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅} and

[wi ] = [wi ](li ,li0 )

(6.43)

and that each action [wi ](li ,li0 ) is uniquely determined by the successor cell li0 . Thus, the cardinality of each agent’s i transition relation is evaluated by summing the numbers of the possible

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS27

successor cells over all the possible cell configurations of i. This observation implies by virtue
of (6.43) that
X
#{l ∈ I : Sl ∩ B(χi (δt); r) 6= ∅}.
(6.44)
# −→ci =
li ∈I Ni +1

Hence, by exploiting (6.39), (6.40), (6.41) and (6.42), we get that
 n
 n
4
4
1
1
Ni +1
c
Ni +1
# −→i ≤ #I
= (#I)
c
(1 − λ)n
c
(1 − λ)n

Ni +1  n
1
4
1
≤ C1
(1 − λ)2n
c
(1 − λ)n
 n
4
1
1
= C1Ni +1
= C2
,
c
(1 − λ)(2(Ni +1)+1)n
(1 − λ)(2(Ni +1)+1)n

(6.45)

with C2 as given in the statement of the corollary. Finally, from the definition of the product
controlled transition system, we obtain from (6.39) that the cardinality of its state set satisfies

N
1
1
1
c
N
N
#QP = #I = (#I) ≤ C1
= C10
,
= C1N
2n
2N
n
(1 − λ)
(1 − λ)
(1 − λ)2N n
with C10 as given in the statement of the corollary. In addition, we obtain that the cardinality
of the transition relation is given by
# −→cP =

N
X Y

#{l ∈ I : Sl ∩ B(χi,pri (l) (δt); r) 6= ∅},

l∈I N i=1

where for each l ∈ I N and i ∈ N , χi,pri (l) (δt) denotes the reference trajectory corresponding to
the cell configuration pri (l) of agent i. Thus, we get from (6.39), (6.40), (6.41) and (6.42) that
 N n
N  n
Y
4
1
4
1
N
# −→cP ≤ #I N
≤
(#I)
n
c
(1
−
λ)
c
(1
−
λ)N n
i=1
N  N n
 N n

4
1
4
1
1
1
N
= C1
= C20
,
≤ C1
(1 − λ)2n
c
(1 − λ)N n
c
(1 − λ)3N n
(1 − λ)3N n
with C20 as given in the statement of the corollary. The proof is now complete.



7. Example and Simulation Results
As an illustrative example we consider a system of four agents with states x1 , x2 , x3 , x4 ∈ R2 ,
whose initial conditions lie inside the circular domain int(B(R))(= {x ∈ R2 : |x| < R}) with
center zero and radius R > 0. Their dynamics are given as:
ẋ1 = satρ (x2 − x1 ) + g(x1 ) + v1 ,
ẋ2 = g(x2 ) + v2 ,
ẋ3 = satρ (x2 − x3 ) + g(x3 ) + v3 ,
ẋ4 = satρ (x3 − x4 ) + g(x4 ) + v4 ,

(7.1)

ρ
where the function satρ : R2 → R2 is defined as satρ (x) := x if |x| ≤ ρ; satρ (x) := |x|
x, if
|x| > ρ. The agents’ neighbors’ sets in this example are N1 = {2}, N2 = ∅, N3 = {2}, N4 = {3}
and specify the corresponding network topology. The constant ρ > 0 in (7.1) satisfies ρ ≤ R

28

D. BOSKOS AND D. V. DIMAROGONAS

and represents a bound on the distance between agents 1, 2, and agents 2, 3, that we will require
the system to satisfy during its evolution. The function g(·) is defined as

if |x| < R − ρ2 ,

0,
x
, if R − ρ2 ≤ |x| < R,
g(x) := ((R − ρ2 ) − |x|) |x|
(7.2)

 ρ x
if R ≤ |x|
− 2 |x| ,
and determines for each agent a repulsive vector field from the boundary of int(B(R)) when
the agent is located in int(B(R)), in order to ensure invariance of the agents’ trajectories inside
this circular domain.
We next show, that if the initial distances between agents 1 and 2 (and similarly for agents 2 and
3) is less than ρ, it will also remain less than ρ for all positive times, for an appropriate bound
on the magnitude of the free input terms vi . By selecting the energy function V (x1 , x2 ) :=
1
2
2 |x1 − x2 | and evaluating its derivative along the right hand side of (7.1), we obtain that
V̇ = hx1 − x2 , x2 − x1 + g(x1 ) + v1 − g(x2 ) − v2 i
≤ −|x1 − x2 |2 + hx1 − x2 , g(x1 ) − g(x2 )i + 2|x1 − x2 |vmax , if |x1 − x2 | < ρ
ρ
V̇ = hx1 − x2 ,
(x2 − x1 ) + g(x1 ) + v1 − g(x2 ) − v2 i
|x2 − x1 |
≤ −(ρ − 2vmax )|x1 − x2 | + hx1 − x2 , g(x1 ) − g(x2 )i, if |x1 − x2 | ≥ ρ

(7.3)

(7.4)

where h·, ·i denotes the inner product in R2 . Next, notice that
hx − y, g(x) − g(y)i ≤ 0, ∀x, y ∈ R2

(7.5)

Indeed, assume that without any loss of generality it holds |x| ≥ |y|. Then, it follows from
(7.2) that there exist α ≥ β ≥ 0, such that g(x) = −αx and g(y) = −βy. Hence, we get
that hx − y, g(x) − g(y)i = hx − y, −αx − βyi ≤ −α|x|2 + (α + β)|x||y| − β|y|2 . By evaluating
the discriminant of the latter second order expression, we obtain that it is always nonpositive,
which implies (7.5). By additionally assuming that
vmax =

ρ
2

(7.6)

we obtain from (7.3), (7.4) and (7.5) that V̇ ≤ 0 when |x1 − x2 | ≥ ρ. Thus, it follows that
|x1 (0) − x2 (0)| ≤ ρ implies that |x1 (t) − x2 (t)| ≤ ρ for all positive times. Analogously, by
considering the function V (x2 , x3 ) := 12 |x2 − x3 |2 it follows that the same holds for |x2 (t) −
x3 (t)|. Furthermore, under the selection of vmax = ρ2 , it can be deduced (along the lines of the
corresponding result in [6]) that the circular domain remains invariant for the dynamics of the
system. Finally, we obtain from (7.1) and (7.2) the following dynamics bounds and Lipschitz
constants in (3.3), (5.1) and (5.2), respectively:
M=

3
ρ,
2

L1 = 1,

L2 = 2.

(7.7)

Thus, it follows that system (7.1) satisfies all requirements for the derivation of well posed
discretizations.
In this example, it is also assumed that the reference point of each cell of the square partition
is the center of the square. This enables us to obtain the following improved bounds on the

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS29

feedback laws in (3.7), for their corresponding values of t, xi , xj and wi :


dmax
|ki,li ,1 (xi , xj )| ≤ L1 (M + vmax )δt +
2
dmax
|ki,li ,2 (xi0 )| ≤
2δt


dmax
|ki,li ,3 (t; xi0 , w)| ≤ L2 λvmax δt +
+ λvmax
2
Thus, in order to verify Property (P2), we need to select dmax and δt satisfying


dmax
dmax
dmax
)+
+ L2 λvmax δt +
+ λvmax ≤ vmax .
L1 ((M + vmax )δt +
2
2δt
2
Equivalently, by virtue of (7.6) and (7.7), it is required that




dmax
ρ
dmax
ρ
dmax
+
+ 2 λ δt +
≤ (1 − λ) ⇐⇒
2ρδt +
2
2δt
2
2
2
(1 − λ)δt − 4δt2
dmax ≤ ρ
3δt + 1
By evaluating the derivative of dmax (·) with respect to δt we obtain that
d˙max = 0 ⇐⇒ ((1 − λ) − 8δt)(3δt + 1) − 3((1 − λ)δt − 4δt2 ) = 0
⇐⇒ − 12δt2 − 8δt + (1 − λ) = 0
Hence, we obtain the time
p
p
¯ := 8 − 4 4 + 3(1 − λ) = −2 + 4 + 3(1 − λ)
δt
−24
6
corresponding to the maximum possible diameter
¯ − 4δt
¯2
(1 − λ)δt
¯
dmax = ρ
¯ +1
3δt
For the simulation results, we select the distance ρ = 10 and the radius of the circular domain
R = 10. We also assume that the agents 1, 2, 3 and 4, are initially located at x10 = (5, −3),
x20 = (5, 3), x30 = (0, 6) and x40 = (−4, 6), respectively. Thus, it follows that agents 1, 2,
and 2, 3, satisfy the requirement on their initial relative distance. In the sequel we will focus
on the behaviour of the system for times t ∈ [0, 2]. Given this time interval and a selection of
the planning parameter λ ∈ (0, 1), we choose the time step δt as the largest possible time step
¯ above, in such a way that the number of time steps N T := 2 is a positive
not exceeding δt
δt
integer. We also choose the largest possible cell diameter dmax corresponding to δt and consider
a√square grid in R2 . Each square has side length d, where d is the largest number not exceeding
2
2R
2 dmax , such that the quotient d is an integer. Thus, we can form a cell decomposition of the
circular domain D by defining as a cell each square in the grid which has nonempty intersection
with D. In Figs. 3, 4 we have plotted (half of) the grid lines, in order to illustrate how the grid
is affected by the choice of λ. We next consider two cases for the motion of agent 2, which is
unaffected by the coupled constraints.
Case I: It holds v2 (t) = v2c , ∀t ∈ [0, 2], with v2c = (−3, −3).

30

D. BOSKOS AND D. V. DIMAROGONAS

Case II: It holds v2 (t) = v2c + v2d (t), ∀t ∈ [0, 2], with v2c as above and v2d ∈ Ud ,√where√ Ud
is the set of all piecewise continuous functions ṽ : [0, 2] → R2 that satisfy ṽ(t) = γ(t)( 22 , − 22 ),
with −1 ≤ γ(t) ≤ 1 for all t ∈ [0, 0.9] and γ(t) = 0, for all t ∈ (0.9, 2].
Notice that in Case I we consider a pre-specified path for agent 2, by selecting a constant
control, whereas in Case II we allow for the possibility to modify this path and superpose a
motion perpendicular to it (up to certain bound) over the time interval [0, 0.9]. Furthermore,
in both cases the magnitude of v2 (·) is bounded by vmax (= 5).
For Case I, we assign reachability goals to agents 1, 3 and 4 which should be fulfilled at
the end of the time interval [0, 2], given the selected path for agent 2. Specifically, we want
agents 1, 3 and 4 to reach the corresponding boxes in the workspace that are depicted in
Fig. 3. First, we sample the trajectories of 2 at the time instants κδt, κ = 0, 1 . . . , N T and
specify the sequence l20 l21 · · · l2N T corresponding to the cells Slκ with x2 (κδt, x20 ) ∈ Slκ . Then,
we exploit the individual controlled transition systems of agents 1 and 3, in order to determine
(an underapproximation of) their reachable cells for the given sampled trajectory of agent
2. In particular, by denoting as l10 the index of the cell where the initial state x10 of agent 1
; l2κ−1 ),
belongs, we can evaluate the indices of its reachable cells at time κδt as Qκ1 = Postc1 (Qκ−1
1
c
0
0
κ = 0, 1, . . . , N T , where Q1 := {l1 } and we have used the notational convention Post1 (l1 ; l2 ) :=
Postc1 (l1 ; (l1 , l2 )) (recall that (l1 , l2 ) stands for a cell configuration of agent 1) and the definition
Postc1 (Q1 ; l2 ) := ∪l1 ∈Q1 Postc1 (l1 ; l2 ). The approach followed in this case is possible because agent
2 is decoupled from the other agents and the individual transition system of agent 1 depends
only on the cell indices of agent 2. Similarly, we can evaluate the reachable cells of agent 1 and
check whether it fulfils its reachability task. Next, by computing the reachable cells of agent 3
which lie in its target box at the final time step N T , we calculate the backward reachable cells
of the agent in order to encode the discrete trajectories which fulfil its reachability goal. Then,
we exploit the individual transition system of agent 4 in order to determine its reachable cells
for all the possible trajectories of agent 3 that satisfy its reachability task. The corresponding
simulation results are depicted in Fig. 3 for λ = 0.2 (left) and λ = 0.3 (right). The figure also
illustrates the effect of the parameter λ in the accomplishment of the reachability goals, since
for λ = 0.2 only agent 3 reaches its target box, whereas for λ = 0.3 all agents achieve their
corresponding task.

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS31

+

+

+

+
+

+

+

+

(i)

(ii)

Figure 3. Reachable cells of the agents for (i) λ = 0.2 and (ii) λ = 0.3.
Agents 1, 3 and 4 are initially located at the bottom right, top center and top
left of the illustrated workspace, respectively. The circles denote the sampled
trajectory of agent 2 as determined by Case I and the boxes the corresponding
target sets of agents 1, 3 and 4. The union of all discrete paths of agent 3
which end in its target box are highlighted within the union of its reachable
cells.
For Case II, we exploit the individual controlled transition system of agents 1, 3 and 4 in
order to obtain (an underapproximation of) the cells these agents can reach, irrespectively of
the choice of v2d for the free input of agent 2. In particular, we define the finite cell sequence
{Qκ2 }κ∈{0,1,...,N T } as Qκ2 = {l ∈ I : ∃v2,d ∈ Ud with x2 (κδt, x20 ; v2c + v2d (·)) ∈ Sl }. Also, we
inductively define for κ = 0, 1, . . . , N T the sets Qκ1 = ∪l1 ∈Qκ−1 ∩l2 ∈Qκ−1 Postc1 (l1 ; l2 ), Qκ3 =
1

2

∪l3 ∈Qκ−1 ∩l2 ∈Qκ−1 Post33 (l3 ; l2 ) and Qκ4 = ∪l4 ∈Qκ−1 ∩l3 ∈Qκ−1 Postc4 (l4 ; l3 ), with Q01 = {l10 },
4
3
3
2
Q03 = {l30 } and Q04 = {l40 } (we use the same notational convention as above for the operators
Postci (·), and the notation li0 for the initial cells of the agents i = 1, 3, 4). Next, consider any
selection of sequences l10 l11 · · · l1N T , l30 l31 · · · l3N T and l40 l41 · · · l4N T , of agents 1, 3 and 4, that satisfy
l1κ ∈ Qκ1 , l3κ ∈ Qκ3 and l4κ ∈ Qκ4 , respectively. Then, by taking into account the definition
of the sets Qκi , i = 1, 3, 4, the definition of the individual transition systems of agents 1, 3,
4, and the particular coupling between the agents in this example, we arrive at the following
conclusion. For each agent 1, 3 and 4, it is possible to assign a sequence of control laws,
such that each corresponding agent will reach the cells with indices l1κ , l3κ and l4κ at time κδt,
respectively, for any selection of the input v2d of agent 2. In Fig. 4 we illustrate the union
of the reachable cells of agents 1, 3 and 4 for λ = 0.3 and λ = 0.4, respectively. Notice that
the underapproximation of agents’ 1 and 3 reachable cells increases with the selection of the
larger parameter λ, namely, with the exploitation of a larger part of the free input for planning.
However, the same observation does not necessarily hold for the reachable cells of agent 4. The
reason why the area covered by the reachable cells of agent 4 remains approximately the same,
is that the corresponding area increases for agent 3 for larger values of λ. Thus, although
the reachability properties of agent 4 are improved, this is compensated by the fact that each

32

D. BOSKOS AND D. V. DIMAROGONAS

illustrated transition of agent 4 to a certain cell needs to be possible for an increasing number
of different positions of agent 3.

+

+

+

+

+

+

+

+

(i)

(ii)

Figure 4. Reachable cells of the agents for (i) λ = 0.3 and (ii) λ = 0.4.
Agents 1, 3 and 4 are initially located at the bottom right, top center and top
left of the illustrated workspace, respectively. The circles denote the nominal
sampled trajectory of agent 2 and their nearby cells represent the cells where
agent 2 can lie at the sampling times, for all possible inputs of Case II.

The code for the simulation results has been implemented in MATLAB and the worst case
running time for the illustrated results is of the order of 45 minutes, on a PC with an Intel(R)
Core(TM) i7-4600U CPU @ 2.10GHz processor.

8. Conclusions
We have provided a decentralized abstraction methodology for multi-agent systems and quantified bounds on the space and time discretization in order to obtain meaningful transition
systems with multiple transition possibilities. The abstraction framework is based on the design of hybrid feedback control laws that take into account the agents’ coupled constraints and
guarantee the implementation of the discrete transitions by the continuous time controllers.
Ongoing work includes the improvement of the acceptable choices of dmax and δt in order
to obtain coarser abstractions and reduce the size of each agent’s transition system. Another
possible direction for complexity reduction is the modification (localization) of the current
framework through an event based online abstraction with updated choices of dmax and δt.
Finally, it should be noted that while this report provides informal indicators of how the results
can be used for planning, we are currently formalizing a distributed planning methodology from
high level specifications that builds on the derived abstractions.

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS33

9. Appendix
In the Appendix we provide the proofs of Propositions 4.8 and 4.9 and certain technical parts
from the proof of Proposition 6.2.
0
Proof of Proposition 4.8. Indeed, consider a final cell configuration l0 = (l10 , . . . , lN
) as in the
statement of the proposition. By the definitions of the operators Posti (·), i ∈ N and the
transition relation of each corresponding agent’s individual transition system, it follows that
pr (l)

i
each transition li −→
li0 is well posed in the sense of Definition 4.3(i). Thus, given the initial

pr (l)

i
cell configuration pri (l) and the well posed transition li −→
li0 for each agent, it follows from
Definition 4.3(i) that we can pick for each i ∈ N a control law ki,pri (l) (·) that satisfies Property
(P) and a vector wi ∈ W , such that Condition (C) holds. Next, notice that for each agent i the
projection of the initial cell configuration l = (l1 , . . . , lN ) is pri (l), namely, the cell configuration
according to which the feedback law ki,pri (l) (·) was selected, and that the feedback law satisfies
Property (P). Thus, it follows from Condition (C) that the solution of the closed loop system
is well defined on [0, δt], and that for each i ∈ N , the i-th component of the solution satisfies
(4.7).


Proof of Proposition 4.9. Proof of (i). Let wi ∈ W , i ∈ N and x(0) ∈ DN with xi (0) ∈ Sli ,
i ∈ N be the initial condition of the closed-loop system. Then, it follows from the local
Lipschitz property on the functions fi (·) and the corresponding property on the mappings
ki,pri (l) (·; xi0 , wi ) provided by (P1), that the dynamics of the closed loop system are given by
a locally Lipschitz function on DN . Hence, there exists a unique solution x(·) = x(·, x(0)) to
the initial value problem, which is defined and remains in DN for all times in its right maximal
interval of existence [0, Tmax ). We proceed by proving that each component xi (·), i ∈ N of the
solution satisfies
xi (t) ∈ (Sli + B(Rmax )) ∩ D, ∀t ∈ [0, min{Tmax , T̃ }).

(9.1)

Indeed, suppose on the contrary that (9.1) is violated, and hence, by taking into account that
xi (t) ∈ D for all t ∈ [0, Tmax ), that there exists ι ∈ N and a time T with
T ∈ (0, min{Tmax , T̃ }) and xι (T ) ∈
/ Slι + B(Rmax ).

(9.2)

By recalling that xi (0) ∈ Sli , i ∈ N , we may define
τ := max{t̄ ∈ [0, T ] : xi (t) ∈ cl(Sli + B(Rmax )),
∀t ∈ [0, t̄], i ∈ N }.

(9.3)

Then, it follows from (4.9), (9.2) and (9.3) that there exists ` ∈ N such that
x` (τ ) ∈ ∂(Sl` + B(Rmax ))

(9.4)

τ ≤ T < T̃ ≤ δt.

(9.5)

and that

It also follows from (9.3), (4.9), (9.5) and Property (P2) that for all t ∈ [0, τ ] it holds
|k`,pr` (l) (t, x` (t), xj(`) (t); x`0 , w` )| ≤ vmax

(9.6)

34

D. BOSKOS AND D. V. DIMAROGONAS

Hence, we get from (3.1), (3.2), (4.1), (4.8), (9.6) and (9.5), which implies that τ < δt, that
Z τ
|f` (x` (s), xj(`) (s))|
|x` (τ ) − x`0 | ≤
0

+ |k` , pr` (l)(s, x` (s), xj(`) (s); x`0 , w` )|ds
Z τ
(M + vmax )ds < δt(M + vmax ) = Rmax .
≤

(9.7)

0

In order to finish the proof of (9.1) we exploit the following elementary fact.
Fact I. Consider a nonempty set S ⊂ Rn and a constant R > 0. Then for every x ∈ ∂(S +B(R))
it holds |x − y| ≥ R, ∀y ∈ S.
Proof of Fact I. Indeed, suppose on the contrary that there exists ỹ ∈ S with |x − ỹ| ≤ R − ε
for certain ε > 0. Then for all x̃ ∈ int(B(x; ε)) we have
|x̃ − ỹ| ≤ |x̃ − x| + |x − ỹ| < ε + R − ε = R,
and hence, x̃ ∈ S + B(R) for all x̃ ∈ int(B(x; ε)), which implies that x ∈
/ ∂(S + B(R)) and
contradicts our statement. /
By exploiting Fact I with S = Sl` , R = Rmax , y = x`0 and x = x` (τ ) we deduce from (9.7)
that x` (τ ) ∈
/ ∂(Sl` + B(Rmax )) which contradicts (9.4), and provides validity of (9.1).
We now prove the following claim:
Claim I. It holds Tmax ≥ T̃ .
.Proof of Claim I. Indeed, suppose on the contrary that
Tmax < T̃ .

(9.8)

For each i ∈ N let vi : [0, ∞) → Rn be a piecewise continuous function satisfying
vi (t) = ki,pri (l) (t, xi (t), xj (t); xi0 , wi ), ∀t ∈ [0, Tmax ).

(9.9)

Notice that due to (4.9) and (9.8) we have that Tmax < min{δt, min{T (xi0 , wi ) : i ∈ N }}, and
thus, we get from (9.1) and (P2) that |vi (t)| ≤ vmax , ∀t ∈ [0, Tmax ). Hence, we may select
vi (·) to satisfy |vi (t)| ≤ vmax , ∀t ≥ 0 (select for instance vi (t) = 0 for t ≥ Tmax ). Thus, if
we denote by ξ(·) the solution of (3.1)-(3.2) with free inputs vi (·), i ∈ N and the same initial
condition with x(·), it follows from the Invariance Assumption (IA) that ξ(t) is defined and
remains in DN for all t ≥ 0. Furthermore, it follows from standard arguments from the theory
of ODEs that ξ(t) = x(t), ∀t ∈ [0, Tmax ). Hence, since ξ(t) belongs to a compact subset of DN
for all t ∈ [0, Tmax ], the same holds for x(t) on [0, Tmax ). The latter contradicts maximality
of [0, Tmax ) since by (9.8) and (4.9) it holds Tmax < T̃ ≤ min{T (xi0 , wi ) : i ∈ N } and the
mappings ki,pri (l) (·) are defined for t ∈ [0, min{T (xi0 , wi ) : i ∈ N }). Hence, we have shown
Claim I. /
From Claim I, it follows that x(t) is defined and remains in DN for all t ∈ [0, T̃ ) and that
(9.1) holds for all t ∈ [0, T̃ ). Thus, by applying the same arguments with those in the proof
of Claim I, we can determine a continuous function ξ(·) with ξ(t) = x(t) for all t ∈ [0, T̃ ) and
ξ(T̃ ) ∈ DN , which establishes (4.10).
Proof of (iia). In the case where (P3) also holds, and hence by (4.9) we have that T̃ = δt, it
follows from part (i) of the proposition and standard arguments, that the solution x(·) is defined
on [0, Tmax ), with Tmax > δt. From the latter, we conclude that x(t) ∈ DN for all t ∈ [0, δt].
Moreover, since Tmax > δt = T̃ , it follows that (9.1) is satisfied for all t ∈ [0, δt). The latter, by
virtue of (P2), (P3) and continuity of x(·) implies (4.11).

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS35

Proof of (iib). By exploiting the result of part (iia) of the proposition and defining vi (t) =
ki,pri (l) (t, xi (t), xj (t); xi0 , wi ), ∀t ∈ [0, δt) we can extend vi (·) to a piecewise continuous function
on [0, ∞) which satisfies (3.4). Hence, by applying the same arguments with those in the proof
of Claim I, we conclude that the solutions x(·) of (3.1)-(3.2), (4.8) and ξ(·) of (3.1)-(3.2) (with
input v(·)) coincide on [0, δt].

Proof of the fact that the intervals provided by Cases I, II, III in Proposition 6.2
are well defined.
The fact that (6.6) and (6.7) are well defined is straightforward. We proceed by defining
ḡ(µ) :=

2
2(λ(1 − λ)µ − 2λ2 )vmax
.
2
µ ML

(9.10)

Then it follows that
ḡ(µ) > 0 ⇐⇒ λ(1 − λ)µ − 2λ2 > 0 ⇐⇒ µ >

2λ
.
1−λ

(9.11)

Furthermore,




d (1 − λ)µ − 2λ
˙
sgn(ḡ(µ))
= sgn
dµ
µ2


2
(1 − λ)µ − ((1 − λ)µ − 2λ)2µ
= sgn
µ4
= sgn((1 − λ)µ − 2((1 − λ)µ − 2λ)) = sgn(−(1 − λ)µ + 4λ),
which implies that
˙
sgn(ḡ(µ))[>
or =]0 ⇐⇒ µ[< or =]

4λ
.
1−λ

(9.12)

From (9.11) and (9.12) we get that

0 < ḡ(µ) < ḡ

4λ
1−λ



2
2
4λ2 vmax
(1 − λ)2 vmax
=
=
, ∀µ ∈
2
λ
4M L
16 (1−λ)
2 ML



2λ
4λ
,
1−λ 1−λ




∪


4λ
,∞ ,
1−λ
(9.13)

which implies that (6.8) and (6.10) are well defined. Also, by considering the function
00

h (dmax ) :=

(1 − λ)vmax +

p

2
(1 − λ)2 vmax
− 4M Ldmax
,
2M L

(9.14)

we deduce that
4λ
µ
(1 − λ)vmax
µ<
⇒
dmax <
≤ h00 (dmax ), ∀dmax ∈
1−λ
2λvmax
2M L




2
(1 − λ)2 vmax
0,
,
4M L

(9.15)

36

D. BOSKOS AND D. V. DIMAROGONAS

and thus, that (6.9) in Case II is well defined. Finally, in order to also show the latter for the
interval (6.9) in Case III, we note that due to (9.10) and (9.14) it holds that
q
2
2(λ(1−λ)µ−2λ2 )vmax
2
(1 − λ)vmax + (1 − λ)2 vmax
− 4M L
µ2 M L
00
h (ḡ(µ)) =
2M L
s

 2 
2
(1 − λ)2 − 8 µλ (1 − λ) + 16 µλ
(1 − λ)vmax + vmax
=

2M L
(1 − λ)vmax + vmax

=

r

(1 − λ) −

4λ
µ

2

h

(1 − λ) + (1 − λ) −

=

2M L

4λ
µ

i

vmax

2M L

.

Hence, by taking into account that
(1 − λ) −

4λ
4λ
≥ 0 ⇐⇒ µ ≥
µ
1−λ

(9.16)

4λ
and that in Case III it holds µ ≥ 1−λ
, we get that


vmax
2 (1 − λ) + 2λ
µ
((1 − λ)µ − 2λ)vmax
=
.
h00 (ḡ(µ)) =
2M L
µM L

(9.17)

Furthermore, we have that
2
µ
((1 − λ)µ − 2λ)vmax
µ 2(λ(1 − λ)µ − 2λ2 )vmax
=
.
ḡ(µ) =
2
2λvmax
2λvmax
µ ML
µM L

Thus, from (9.13), (9.17), (9.18) and the fact that h00 (·) is decreasing, it follows that
µ
h00 (dmax ) ≥
dmax , ∀dmax ∈ (0, ḡ(µ)],
2λvmax

(9.18)

(9.19)

which in conjunction with (9.10), implies that (6.9) is well defined.
Proof of the fact that for all Cases I, II and III (6.18)-(6.21) are satisfied in the proof
of Proposition 6.2.
Case I: 0 ≤ µ ≤

2λ
1−λ .

By defining
0

h (dmax ) :=

(1 − λ)vmax −

p

2
(1 − λ)2 vmax
− 4M Ldmax
,
2M L

(9.20)

we obtain that
ḣ0 (dmax ) = p

1
(1 −

2
λ)2 vmax

− 4M Ldmax

.

Hence,
ḣ0 (·) is positive and strictly increasing for 0 ≤ dmax <
and furthermore
ḣ0 (0) =

1
;
(1 − λ)vmax

h0 (0) = 0.

2
(1 − λ)2 vmax
4M L

(9.21)

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS37

The latter in conjunction with (9.21) implies that
h0 (dmax ) >

1
1
dmax ≥
dmax , ∀dmax ∈
(1 − λ)vmax
M + vmax

Also, we have that for 0 ≤ µ ≤

2λ
1−λ


0,


2
(1 − λ)2 vmax
.
4M L

(9.22)

it holds
2λ

µ
1
dmax ≤ 1−λ dmax =
dmax .
2λvmax
2λvmax
(1 − λ)vmax

(9.23)

Thus, it follows from (6.6), (6.7), (9.20), (9.23) and (9.22) that (6.18)-(6.21) are fulfilled (see
also Fig. 5).
δt
(1−λ)vmax
ML
2
(1−λ)vmax dmax

1
(1−λ)vmax dmax
µ
2λvmax dmax
1
M +vmax dmax
2
(1−λ)2 vmax
4M L

dmax

Figure 5. Case I. Feasible dmax − δt region for 0 < µ ≤

Case II:

2λ
1−λ

<µ<

2λ
1−λ

4λ
1−λ .

From (9.10) and (9.20) we obtain that
q
2
2(λ(1−λ)µ−2λ2 )vmax
2
(1 − λ)vmax − (1 − λ)2 vmax
− 4M L
µ2 M L
0
h (ḡ(µ)) =
2M L
s

 2 
2
(1 − λ)vmax − vmax
(1 − λ)2 − 8 µλ (1 − λ) + 16 µλ
=

2M L
(1 − λ)vmax − vmax

=

r

2M L

(1 − λ) −

4λ
µ

2

h
(1 − λ) − (1 − λ) −
=

2M L

2λ
4λ
Hence, by taking into account (9.16) and that 1−λ
< µ < 1−λ
, we get that


2 (1 − λ) − 2λ
vmax
µ
((1 − λ)µ − 2λµ)vmax
0
h (ḡ(µ)) =
=
.
2M L
µM L

4λ
µ

i

vmax
.

(9.24)

38

D. BOSKOS AND D. V. DIMAROGONAS

Thus, by the fact that

2λ
1−λ

<µ<

4λ
1−λ

h0 (dmax ) ≤

it follows from (9.13), (9.18), (9.21) and (9.24) that

µ
dmax , ∀dmax ∈ (0, ḡ(µ)]
2λvmax

(9.25)

and
h0 (dmax ) >

µ
dmax , ∀dmax ∈
2λvmax


ḡ(µ),


2
(1 − λ)2 vmax
.
4M L

(9.26)

It also holds that
µ>

µ
1
1
2λ
⇒
dmax >
dmax >
dmax , ∀dmax > 0.
1−λ
2λvmax
(1 − λ)vmax
M + vmax

(9.27)

Hence, it follows from (6.8)-(6.7), (9.10), (9.25), (9.26) and (9.27) that (6.18)-(6.21) are fulfilled
as well (see also Fig. 6).

δt
(1−λ)vmax
ML
2
(1−λ)vmax dmax
µ
2λvmax dmax
1
(1−λ)vmax dmax
1
M +vmax dmax
2
2(λ(1−λ)µ−2λ2 )vmax
µ2 M L

dmax

2
(1−λ)2 vmax
4M L

Figure 6. Case II. Feasible dmax − δt region for

Case III µ ≥

2λ
1−λ

<µ<

4λ
1−λ

4λ
1−λ .

4λ
In this case, notice that for µ = 1−λ
and dmax =
and thus, we deduce from (9.21) that

2
(1−λ)2 vmax
4M L

4λ
µ
µ≥
⇒
dmax ≥ h0 (dmax ), ∀dmax ∈
1−λ
2λvmax

we have



µ
2λvmax dmax


2
(1 − λ)2 vmax
0,
.
4M L

= h0 (dmax ),

(9.28)

Hence, it follows from (6.8), (6.9), (9.10), (9.13) and (9.28) that (6.18)-(6.21) hold (see also Fig.
7).

DECENTRALIZED ABSTRACTIONS FOR MULTI-AGENT SYSTEMS UNDER COUPLED CONSTRAINTS39

δt
µ
2λvmax dmax

(1−λ)vmax
ML

2
(1−λ)vmax dmax

1
(1−λ)vmax dmax
1
M +vmax dmax
2
2(λ(1−λ)µ−2λ2 )vmax
µ2 M L

2
(1−λ)2 vmax
4M L

dmax

Figure 7. Case III. Feasible dmax − δt region for µ ≥

4λ
1−λ

10. Acknowledgements
This work was supported by the H2020 ERC Starting Grant BUCOPHSYS and the Swedish
Research Council (VR).

References
[1] A. Abate, A. Tiwari, ans S. Sastry, Box invariance in biologically-inspired dynamical systems, Automatica
45(7):1601–1610, 2009.
[2] D. Angeli and E. D. Sontag, “Forward completeness, unbounded observability and their Lyapunov characterizations,” Syst. and Control Lett., vol. 38, pp. 209–217, 1999.
[3] E. Asarin, T. Dang, and A. Girard, Hybridization methods for the analysis of nonlinear systems, Acta
Informatica, 43(7):451–476, 2007.
[4] C. Baier and J. P. Katoen, Principles of Model Checking, Cmbridge, MA: The MIT Press, 2008.
[5] D. Boskos and D. V. Dimarogonas, Decentralized Abstractions for Feedback Interconnected Multi-Agent
Systems, in Proceedings of the 54th IEEE Conference on Decision and Control, 282–287, 2015.
[6] D. Boskos and D. V. Dimarogonas, Robust Connectivity Analysis for Multi-Agent Systems, in Proceedings
of the 54th IEEE Conference on Decision and Control, 6767–6772, 2015.
[7] M. E. Brouke and M. Gannes, Reach Control on Simplices by Piecewise Affine Feedback, SIAM Journal on
Control and Optimization, 52(5):3261–3286, 2014.
[8] P.E. Caines and Y.J. Wei, The hierarchical lattices of a finite machine, Systems and Control Letters,
25:257–263, 1995.
[9] Y. Chen, X. C. Ding, A. Stefanescu, and C. Belta. Formal approach to the deployment of distributed robotic
teams, IEEE Transactions on Robotics, 28(1):158–171, 2012.
[10] G. E. Fainekos, A. Girard, H. Kress-Gazit, and G. Pappas, Temporal Logic Motion Planning for Dynamic
Robots, Automatica 45(2):343–352, 2009.
[11] S. G. Loizou and K. J. Kyriakopoulos, Automatic Synthesis of Multi-Agent Motion Tasks Based on LTL
Specifications, in Proceedings of the 43rd IEEE Conference on Decision and Control, 153–158, 2004.
[12] A. Girard and S. Martin, Motion Planning for Nonlinear Systems using Hybridizations and Robust Controllers on Simplices, in Proceedings of the 47th IEEE Conference on Decision and Control, 239–244, 2008.
[13] A. Girard and S. Martin, Synthesis for constrained nonlinear systems using hybridization and robust controllers on simplice, IEEE Transactions on Automatic Control, 57(4):1046–1051, 2012.
[14] A. Girard, G. Pola, and P. Tabuada, Approximately bisimilar symbolic models for incrementally stable
switched systems, IEEE Transactions on Automatic Control, 55(1):116-126, 2010.

40

D. BOSKOS AND D. V. DIMAROGONAS

[15] E. A. Gol, X. Ding, M. Lazar, and C. Belta, Finite Bisimulations for Switched Linear Systems, IEEE
Transactions on Automatic Control, 59(12):3122–3134, 2014.
[16] L. Grüne, Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization,
Berlin, Germany: Springer-Verlag, 2002, vol. 1783.
[17] L. Habets, P. Collins, and J. van Schuppen, Reachability and control synthesis for piecewise-affine hybrid
systems on simplices, IEEE Transactions on Automatic Control 51(6):938–948, 2006.
[18] L. Habets and J. van Schuppen, Control of piecewise-linear hybrid systems on simplices and rectangles,
Lecture Notes in Computer Science: vol. 2034 Hybrid Systems:Computation and Control, 261–274, Springer,
2001.
[19] M.K. Helwa and P.E. Caines, In-Block Controllability of Affine Systems on Polytopes, in Proceedings of
the 53rd IEEE Conference on Decision and Control, 3936–3942, 2014.
[20] I. Karafyllis and J.-P. Jiang, Stability and Stabilization of Nonlinear Systems, London, U.K.: SpringerVerlag, 2011.
[21] M. Kloetzer and C. Belta, A Fully Automated Framework for Control of Linear Systems from Temporal
Logic Specifications, IEEE Transactions on Automatic Control 53(1):287–297, 2008.
[22] G. Pappas, Bisimilar linear systems, Automatica, 39(12):2035–2047, 2003.
[23] G. Pola, A. Girard, and P. Tabuada, Approximately bisimilar symbolic models for nonlinear control systems,
Automatica, 44(10):2508–2516, 2008.
[24] G. Pola, P. Pepe, and M. D. di Benedetto, Symbolic Models for Networks of Discrete-Time Nonlinear
Control Systems, in Proceedings of the American Control Conference, 1787–1792, 2014.
[25] G. Reissig, Computing Abstractions of Nonlinear Systems, IEEE Transactions on Automatic Control,
56(11):2583–2598, 2011.
[26] Sontag E, Mathematical Control Theory, 2nd ed. New York: Springer-Verlag, 1998.
[27] P. Tabuada, Verification and Control of Hybrid Systems, A Symbolic Approach, New York: Springer, 2009.
[28] Y. Tazaki and J. ichi Imura, Bisimilar finite abstractions of interconnected systems, in Hybrid Systems:Computation and Control, 4981:514–527, 2008.
[29] A. Tiwari, Abstractions for hybrid systems, Formal Methods in Systems Design, 32(1):57-83, 2008.
[30] A. Van der Schaft, Equivalence of Dynamical Systems by Bisimulation, IEEE Transactions on Automatic
Control, 49(12):2160–2172, 2004.
[31] M. Zamani, M. Mazo, and A. Abate, Symbolic Models for Networked Control Systems, arXiv:1401.6396,
2014.
[32] M. Zamani, G. Pola, M. Mazo, and P. Tabuada, Symbolic Models for Nonlinear Control Systems Without
Stability Assumptions, IEEE Transactions on Automatic Control, 57(7):1804–1809, 2012.
Department of Automatic Control, School of Electrical Engineering, KTH Royal Institute of
Technology, Osquldas väg 10, 10044, Stockholm, Sweden
E-mail address: boskos@kth.se
Department of Automatic Control, School of Electrical Engineering, KTH Royal Institute of
Technology, Osquldas väg 10, 10044, Stockholm, Sweden
E-mail address: dimos@kth.se

