# Consensus of Multiagent Systems with Packet Losses and Communication Delays Using a Novel Control Protocol

Authors: Zheping Yan; Di Wu; Wei Zhang; Yibo Liu
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

This paper studies the consensus problem of multiagent system with packet losses and communication delays under directed communication channels. Different from previous research results, a novel control protocol is proposed depending only on periodic sampling and transmitting data in order to be convenient for practical implementation. Due to the randomicity of transmission delays and packet losses, each agent updates its input value asynchronously at discrete time instants with synchronized time stamped information and evolves in continuous time. Consensus conditions for multiagent system consists of three typical dynamics including single integrator, double integrator, and high-order integrator that are all discussed in this paper. It is proved that, for single integrator agents and double integrator systems with only communication delays, consensusability can be ensured through stochastic matrix theory if the designed communication topology contains a directed spanning tree. While, for double integrator agents and high-order integrator agents with packet losses and communication delays, the interval system theory is introduced to prove the consensus of multiagent system under the condition that the designed communication topology is a directed spanning tree. Finally, simulations are carried out to validate the effectiveness of the proposed solutions.


---

## Body

## 1. Introduction

Consensus of multiagent system has attracted increasing focuses of researchers from different areas including multiple robotics system, large-scale oceanographic survey, and wireless sensor networks [1–4]. Among all the problems studied aiming at achieving consensus through local interaction, packet losses and communication delays that usually result from unreliable communication links are significant factors which influence the consensusability of multiagent system [5–25]. Considering those problems, three typical agent dynamics, single integrator [5, 9, 16, 23], double integrator [6, 8, 10, 12, 14, 17, 18], and high-order integrator [11, 15], are most widely discussed because they can represent a majority of autonomous systems.Even though plenty of research results have been carried out about consensus problem of multiagent systems with communication delays, most of the controllers designed cannot be easily practiced. Take two typical controllers; for example, in Gao and Wang [10], the structure of controller implies that each agent has to memorize system states all the time between two sampling instants because of the randomicity of communication delay. In Lin and Jia [12], to deploy the control protocol, each agent has to broadcast the information all the time and only one transmitted data is useful to calculate the control input. In both cases, system resources are wasted to some extent, especially for embedded systems whose resources are ordinarily limited. So in this paper, in order to be convenient for practical implementation and economical for limited system resource, a novel controller structure is proposed depending only on periodic sampling and transmitting data which is the main contribution of this paper. Compared with previously proposed solutions, this protocol greatly relieves the computational burden of each agent. In addition, with this control protocol, it is worth being noticed that since the communication delays are random, each agent updates its input asynchronously at discrete time instants based on received data. But the information transmitted is with synchronized time stamp and the whole system evolves in continuous time.With the proposed control protocol, interaction topology is time varying due to communication delays and packet losses. Also, many research results about consensus of multiagent systems with dynamically changing topology have been obtained based on stochastic matrix theory and Lyapunov theory. However, Lyapunov theory usually needs the topology to be undirected or balanced [7, 13, 14]. When random transmission delays and packet losses are concerned, undirected or balanced assumption is unreasonable. With the novel control protocol proposed in this paper, it will be shown that, for single integrator agent and second order agent without packet losses, similar results can be obtained as in [8, 9] according to stochastic matrix theory. That is, the consensus can be reached as long as the designed communication topology contains a directed spanning tree. However, when it comes to second order and high-order agent with packet losses and communication delays, stochastic theory is no longer easily applicable since the nonnegativity of the system matrix is not always guaranteed. Actually, to the best of the authors’ knowledge, few results have been obtained to handle this problem. Based on the theory of interval matrix, it will be proved that the consensus of the system can be reached as long as the designed communication topology is a directed spanning tree which is another contribution of this paper. Of course, in this situation, the states of all agents will converge to the root node and average consensus cannot be obtained. However, this assumption can also simplify the system architecture indicating that one agent can only receive message from its superior and send information to its inferiors; this kind of hierarchy structure is actually more efficient and convenient in real-world application. Since the protocol proposed in this paper can be easily implemented for system with limited resources and unreliable communication links, it would have a wide application prospect in multiple autonomous systems, especially for multiple marine systems such AUVs, UUVs, and USVs, that rely on acoustic communication which is characterized by intermittent failures and latency [16].The rest of the paper is organized as follows. In Section2, preliminaries are presented and problems concerned are formulated. In Section 3, consensus of the multiagent system with single integrator, double integrator, and high-order integrator are analyzed under different situations. And simulations to prove the results are given in Section 4. Conclusions are made in Section 5.


## 2. Preliminaries and Problem Formulation

### 2.1. Graph Theory

Graph theory has played an important role in analysis of multiagent systems for its advantages in modeling the interactions between agents. As graph theory has been introduced in many relative articles, only necessary notations are put forward here. Consider a system withn agents and the topology graph consists of a vertex set υ
=
{
1,2
,
…
,
n
}, an edge set ε
=
{
(
j
,
i
)
:
i
,
j
∈
υ
}
⊆
υ
×
υ, and an adjacent matrix A
=
[
a
i
j
]
∈
R
n
×
n. If ε
j
i
∈
ε, then a
i
j
>
0 which means that agent i can receive information from agent j; else a
i
j
=
0. The set of neighbors of agent i is denoted by N
i
=
{
υ
j
:
(
υ
j
,
υ
i
)
∈
ε
}. A directed spanning tree is a graph that has one node called root node, which has a directed path to all of the other nodes. The Laplacian matrix L
∈
R
n
×
n is defined as follows:
(1)
L
=
{
-
a
i
j
,
i
≠
j
;
i
,
j
∈
υ
∑
j
=
1
,
j
≠
i
n
a
i
j
.The following definitions are introduced for further discussion.Definition 1 (subgraph [8]).
Considering a topology graphG
=
(
υ
,
ε
,
A
), then G
1
=
(
υ
1
,
ε
1
,
A
1
) is a subgraph of G if (
1
)  υ
1
⊆
υ; (
2
)  ε
1
⊆
ε.Definition 2 (union of graphs [7]).
Set the union of topology graphsG
k
=
(
υ
k
,
ε
k
,
A
k
) as G
=
(
υ
,
ε
,
A
); then, (
1
)  υ
k
∈
υ; (
2
)  ε
k
∈
ε.


### 2.2. Control Protocol

In this paper, system states are sampled and transmitted at discrete instants and the controller is designed based on the periodic sampling and transmitting information. For agenti, control input between [
t
k
,
t
k
+
1
) can be presented as follows:
(2)
u
i
(
t
)
=
K
∑
j
∈
N
i
a
i
j
(
t
)
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
t
k
≤
t
<
t
k
+
1
,
where K is controller gain with proper dimension to be decided, the value of a
i
j
(
t
) should be defined as (7). 								(3)
a
i
j
(
t
)
=
{
0
t
k
≤
t
<
t
k
+
τ
i
j
(
k
)
1
t
k
+
τ
i
j
(
k
)
≤
t
<
t
k
+
1
.
In the above equation, τ
i
j
(
k
) denotes the transmission delay between agent i and agent j during the period [
t
k
,
t
k
+
1
). From the structure of the controller, it is obvious that the control input is not constant during [
t
k
,
t
k
+
1
) and each agent in the system updates its input asynchronously. It is also worth noticing that (3) implies that τ
i
j
<
t
k
+
1
-
t
k, which is not necessarily guaranteed for communication system with random delays. So the following assumption is introduced about communication delays.Assumption 3 (bounded transmission delays).
There exist positive constant valuesτ
min
⁡ and τ
i
j denoting the delay between agent i and agent j; T presents the time period for sampling and transmitting data. The following condition is satisfied;
(4)
T
-
τ
i
j
(
k
)
>
τ
min
⁡
,
for
any
k
.From a practical point of view, it can be assumed that, for any packet with transmission delay that cannot satisfy Assumption3, the packets are regarded as being lost.


### 2.3. Model

With the proposed control algorithm as in (2), the multiagent systems consist of three typical dynamics that are concerned. And the corresponding discrete-time system presentations are also presented in Table 1.Table 1
Continuous time and discrete time presentations of agent dynamics.
Agent type
Continuous time system
Discrete time presentation
Single integrator
x
˙
i
(
t
)
=
u
i
(
t
)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
Double integrator
x
˙
i
(
t
)
=
v
i
(
t
)
v
˙
i
(
t
)
=
u
i
(
t
)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
T
2
2
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
T
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
High-order integrator
x
˙
i
(
t
)
=
A
x
i
(
t
)
+
B
u
i
(
t
)
x
i
(
t
k
+
1
)
=
e
A
T
x
i
(
t
k
)
+
∫
0
T
e
A
t
B
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
d
tFormth high-order system, the matrices A
a
n
d
B are as follows:
(5)
A
=
[
0
1
0
⋯
0
0
0
1
⋱
⋮
0
0
0
⋱
0
⋮
⋮
⋮
⋱
1
0
0
0
⋯
0
]
∈
R
m
×
m
,
B
=
[
0
⋯
0
1
]
T
∈
R
m
×
1
.Definition 4 (consensus [11]).
Consensus of the multiagent system is regarded as being achieved when the following equation is satisfied:(6)
lim
⁡
t
→
∞
∥
x
i
(
t
)
-
x
j
(
t
)
∥
=
0
,
∀
i
,
j
∈
υ
.


## 2.1. Graph Theory

Graph theory has played an important role in analysis of multiagent systems for its advantages in modeling the interactions between agents. As graph theory has been introduced in many relative articles, only necessary notations are put forward here. Consider a system withn agents and the topology graph consists of a vertex set υ
=
{
1,2
,
…
,
n
}, an edge set ε
=
{
(
j
,
i
)
:
i
,
j
∈
υ
}
⊆
υ
×
υ, and an adjacent matrix A
=
[
a
i
j
]
∈
R
n
×
n. If ε
j
i
∈
ε, then a
i
j
>
0 which means that agent i can receive information from agent j; else a
i
j
=
0. The set of neighbors of agent i is denoted by N
i
=
{
υ
j
:
(
υ
j
,
υ
i
)
∈
ε
}. A directed spanning tree is a graph that has one node called root node, which has a directed path to all of the other nodes. The Laplacian matrix L
∈
R
n
×
n is defined as follows:
(1)
L
=
{
-
a
i
j
,
i
≠
j
;
i
,
j
∈
υ
∑
j
=
1
,
j
≠
i
n
a
i
j
.The following definitions are introduced for further discussion.Definition 1 (subgraph [8]).
Considering a topology graphG
=
(
υ
,
ε
,
A
), then G
1
=
(
υ
1
,
ε
1
,
A
1
) is a subgraph of G if (
1
)  υ
1
⊆
υ; (
2
)  ε
1
⊆
ε.Definition 2 (union of graphs [7]).
Set the union of topology graphsG
k
=
(
υ
k
,
ε
k
,
A
k
) as G
=
(
υ
,
ε
,
A
); then, (
1
)  υ
k
∈
υ; (
2
)  ε
k
∈
ε.


## 2.2. Control Protocol

In this paper, system states are sampled and transmitted at discrete instants and the controller is designed based on the periodic sampling and transmitting information. For agenti, control input between [
t
k
,
t
k
+
1
) can be presented as follows:
(2)
u
i
(
t
)
=
K
∑
j
∈
N
i
a
i
j
(
t
)
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
t
k
≤
t
<
t
k
+
1
,
where K is controller gain with proper dimension to be decided, the value of a
i
j
(
t
) should be defined as (7). 								(3)
a
i
j
(
t
)
=
{
0
t
k
≤
t
<
t
k
+
τ
i
j
(
k
)
1
t
k
+
τ
i
j
(
k
)
≤
t
<
t
k
+
1
.
In the above equation, τ
i
j
(
k
) denotes the transmission delay between agent i and agent j during the period [
t
k
,
t
k
+
1
). From the structure of the controller, it is obvious that the control input is not constant during [
t
k
,
t
k
+
1
) and each agent in the system updates its input asynchronously. It is also worth noticing that (3) implies that τ
i
j
<
t
k
+
1
-
t
k, which is not necessarily guaranteed for communication system with random delays. So the following assumption is introduced about communication delays.Assumption 3 (bounded transmission delays).
There exist positive constant valuesτ
min
⁡ and τ
i
j denoting the delay between agent i and agent j; T presents the time period for sampling and transmitting data. The following condition is satisfied;
(4)
T
-
τ
i
j
(
k
)
>
τ
min
⁡
,
for
any
k
.From a practical point of view, it can be assumed that, for any packet with transmission delay that cannot satisfy Assumption3, the packets are regarded as being lost.


## 2.3. Model

With the proposed control algorithm as in (2), the multiagent systems consist of three typical dynamics that are concerned. And the corresponding discrete-time system presentations are also presented in Table 1.Table 1
Continuous time and discrete time presentations of agent dynamics.
Agent type
Continuous time system
Discrete time presentation
Single integrator
x
˙
i
(
t
)
=
u
i
(
t
)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
Double integrator
x
˙
i
(
t
)
=
v
i
(
t
)
v
˙
i
(
t
)
=
u
i
(
t
)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
T
2
2
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
T
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
High-order integrator
x
˙
i
(
t
)
=
A
x
i
(
t
)
+
B
u
i
(
t
)
x
i
(
t
k
+
1
)
=
e
A
T
x
i
(
t
k
)
+
∫
0
T
e
A
t
B
K
∑
j
∈
N
i
a
i
j
(
x
j
(
t
k
)
-
x
i
(
t
k
)
)
d
tFormth high-order system, the matrices A
a
n
d
B are as follows:
(5)
A
=
[
0
1
0
⋯
0
0
0
1
⋱
⋮
0
0
0
⋱
0
⋮
⋮
⋮
⋱
1
0
0
0
⋯
0
]
∈
R
m
×
m
,
B
=
[
0
⋯
0
1
]
T
∈
R
m
×
1
.Definition 4 (consensus [11]).
Consensus of the multiagent system is regarded as being achieved when the following equation is satisfied:(6)
lim
⁡
t
→
∞
∥
x
i
(
t
)
-
x
j
(
t
)
∥
=
0
,
∀
i
,
j
∈
υ
.


## 3. Consensus of Multiagent System

In this section, consensus problem of multiagent system consists of different agent dynamics that is discussed separately. With proper assumptions made, we have proposed the conditions needed for consensusability of the multiagent system.


### 3.1. Case 1: Single Integrator Agent

#### 3.1.1. With Communication Delays and No Packet Losses

DefineX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
Tas the state of the multiagent system. Since it can be easily extended to multistate through Kronecker production, it is assumed here that each agent has only one state for briefness of description. Based on the controller as (2) and the discrete time model in Table 1, the dynamics of multiagent system can be denoted by
(7)
X
(
t
k
+
1
)
=
(
I
-
α
(
t
0
L
0
+
t
1
L
1
+
⋯
+
t
m
L
m
)
)
X
(
t
k
)
,
where controller gain K is presented as α
∈
R in this case. Because of transmission delays, Laplacian matrix is not invariant. So L
0
,
L
1
,
…
,
L
m represent the Laplacian matrices that exist during [
t
k
,
t
k
+
1
) and t
0
,
t
1
,
…
,
t
m are the durations for corresponding Laplacian matrices satisfying t
0
+
t
1
+
⋯
+
t
m
=
T. In fact, L
0 is a Laplacian matrix with no connections between agents and since no packet losses are concerned, for any 0
≤
i
≤
m
-
1, the topology associated with L
i is a subgraph of the topology associated L
i
+
1. To prove the consensusability of discrete-time system as in (7), following lemmas about nonnegative matrix and stochastic matrix are introduced beforehand.Lemma 5 (see [26]).
LetM
∈
R
n
×
n be a stochastic matrix. If M has an eigenvalue λ
=
1 with algebraic multiplicity equal to one and all of the other eigenvalues satisfy |
λ
|
<
1, then M is SIA. That is, lim
⁡
n
→
∞
M
n
→
1
y
T.Lemma 6 (see [9]).
A stochastic matrix has algebraic multiplicity equal to one for its eigenvalueλ
=
1 if and only if the graph associated with the matrix has a spanning tree. Furthermore, a stochastic matrix with positive diagonal elements has the property that |
λ
|
<
1 for every eigenvalue not equal to one.Lemma 7 (see [27]).
LetS
1
,
S
2
,
…
,
S
k be a finite set of SIA matrices with property that, for each sequence S
i
1
,
S
i
2
,
…
,
S
i
j of positive length, the matrix product S
i
j
S
i
j
-
1
⋯
S
i
1 is SIA. Then, for each infinite sequence S
i
1
,
S
i
2
,
…, there exists a column vector y such that lim
⁡
j
→
∞
S
i
j
,
S
i
j
-
1
,
…
,
S
i
1
=
1
y
T.Lemma 8 (Gershgorin circle criterion [28]).
All eigenvalues of a matrixE
=
[
e
i
j
]
∈
R
N
×
N are located within the union of N discs as follows:
(8)
⋃
i
=
1
N
{
z
∈
C
:
|
z
-
e
i
i
|
≤
∑
j
≠
i
|
e
i
j
|
}
.Lemma 9 (see [29]).
Letm
≥
2 be a positive integer and let P
1
,
P
2
,
…
,
P
m be nonnegative matrices with positive diagonal elements; then, P
1
P
2
⋯
P
m
≥
γ
(
P
1
+
P
2
+
⋯
+
P
m
), with γ
>
0. And if the digraph associated with γ
(
P
1
+
P
2
+
⋯
+
P
m
) has a spanning tree, the graph associated with P
1
P
2
⋯
P
m also has a spanning tree.Besides, some assumptions also need to be proposed.Assumption 10 (quantized transmission delays).
There exists a small positive valueΔ such that, for all i
,
j
∈
1,2
,
…
,
n,
(9)
τ
i
j
(
k
)
=
q
Δ
,
q
∈
1,2
,
…
,
m
q
.
Assumption10 indicates that transmission delays can be quantized and must be a multiple of fundamental delay time Δ. Assumption 10 is realizable and practical because all agents are operated under digital computers and the smaller the Δ is, the higher the accuracy is.Assumption 11.
The designed communication topology for the multiagent system has a directed spanning tree.This assumption means that if there are no packet losses and communication delays, the topology of the multiagent system has a spanning tree at every instantt
k. Combing with Assumption 3, it can be derived that the union of digraphs associated with L
0
,
L
1
,
…
,
L
m has a directed spanning tree. Then based on introduced lemmas and assumptions, the consensus of the system described as in (7) can be proposed.Theorem 12.
For multiagent system consisting of single integrator dynamics, with control protocol designed as (2) and Assumptions 3–11, the consensus of the multiagent system can be reached if the controller gain is set to be α
=
1
/
T
d
max
⁡, where d
max
⁡ is the largest in-degree of the Laplacian matrices L
0
,
L
1
,
…
L
m.Proof.
First of all, since there are a limited number of possible Laplacian matrices for fixed number of agents,d
max
⁡ can be precalculated without consideration about communication delays; then, it can be viewed as a constant in subsequent presentation. By substituting α
=
1
/
T
d
max
⁡ into (7), the system can be transformed as
(10)
X
(
t
k
+
1
)
=
(
I
-
1
d
max
⁡
(
t
0
T
L
0
+
t
1
T
L
1
+
⋯
+
t
m
T
L
m
)
)
X
(
t
k
)
=
M
k
X
(
t
k
)
.
Since Assumption11 holds and there are no packet losses, L
m has a spanning tree and the interaction graphs associated with L
0
,
L
1
,
…
,
L
m
-
1 are subgraphs of the topology associated with L
m. Then, for the union of graphs L
0
,
L
1
,
…
,
L
m
-
1, there is a simple eigenvalue equal to zero. According to Lemma 8, it is not difficult to conclude that all of other eigenvalues of (
1
/
d
max
⁡
)
(
(
t
0
/
T
)
L
0
+
(
t
1
/
T
)
L
1
+
⋯
+
(
t
m
/
T
)
L
m
) are located within the circle with origin point of (
1,0
) and radius of 1. Thus, it can be obtained that M
k is a matrix with simple eigenvalues equal to one and the others within the unit circle of the complex plane which means that the topology associated with M
k has a spanning tree according to Lemma 6.
In addition, since all the nondiagonal entries of Laplacian matrices are nonpositive, the nondiagonal entries ofM
k are nonnegative. All diagonal elements of M
k are less than one due to the choice of α. And since Laplacian matrices L
0
,
L
1
,
…
,
L
m all have zero row sums, M
k has row sum equal to one; that is, M
k is a stochastic matrix. As a conclusion, M
k is a stochastic nonnegative matrix with positive diagonal elements and it can be derived from Lemma 5 that M
k is SIA.
BecauseM
k has a spanning tree, M
k
M
k
+
1
⋯
M
k
+
l also has a spanning tree according to Lemma 9. In addition, the stochastic matrices with positive diagonal entries are closed under matrix multiplication, so that M
k
M
k
+
1
⋯
M
k
+
l is also a stochastic matrix with positive diagonal elements. According to Lemmas 6 and 5, the matrix M
k
M
k
+
1
⋯
M
k
+
l is SIA.
With Assumption10, it can be derived that there is a finite number of M
k. After that, Lemma 7 can be applied to acquire that the multiagent system as in (10) can reach a consensus. Theorem 12 is proved.


#### 3.1.2. With Packet Losses and Communication Delays

In the above section, consensus problem with communication delays has been solved that lay firm foundation for the problem concerned in the situation where packet losses must be taken into consideration. In this case, Assumption3 is no longer satisfied. As mentioned previously, Assumption 3 is a relative strict condition to be fulfilled in practice. So the following assumption is proposed in addition.Assumption 13.
Set the success ratio of transmission between two agents asp
∈
(
0,1
), ∀
μ
∈
(
0,1
); there exists an integer l that satisfies 1
-
(
1
-
p
)
l
>
μ. If μ is chosen to be close to 1 enough, it is reasonable to assume that the transmission can be successful for at least one time during l periods. Besides, under Assumption 13, the communication delay can still satisfy Assumption 3 for the successful transmitted information. With Assumption 11, this assumption essentially means that the union of digraphs within l periods has a directed spanning tree.Theorem 14.
For multiagent system consisting of single integrator dynamics satisfying Assumptions10–13, with control protocol designed as in (2), the consensus of the multiagent system can be reached with the same controller gain α adopted as in Theorem 12.Proof.
In this situation, since Assumption3 is no longer satisfied all the time, L
m cannot always have a spanning tree. However, according to Assumptions 11 and 13, the digraph associated with M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1 will have a spanning tree. Since M
k is still a stochastic nonnegative matrix with positive diagonal elements, Lemma 9 still holds; that is, the relation M
k
M
k
+
1
⋯
M
k
+
l
-
1
≥
γ
(
M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1
) exists. Thus, define Q
k
,
l
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1 such that
(11)
X
(
t
k
+
l
)
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1
X
(
t
k
)
=
Q
k
,
l
X
(
t
k
)
.
SinceQ
k
,
l is a stochastic nonnegative matrix with positive diagonal elements and the associated graph has a spanning tree, the problem regarding packet losses and communication delays can be handled in a similar way as in proof of Theorem 12. So, the consensusability of multiagent system with packet losses and communication delays is guaranteed.Remark 15.
Based on the analysis of this section, it can be found that Theorem12 can be viewed as a special case of Theorem 14 with l
=
1. With the proposed control protocol and proper choice of controller gain, the multiagent system can reach consensus as long as the union of the digraphs within finite periods has a spanning tree.


### 3.2. Case 2: Double Integrator Agent

#### 3.2.1. With Communication Delays and No Packet Losses

For second order multiagent system, the corresponding variables are defined asX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
T, V
(
t
)
=
[
v
1
(
t
)
v
2
(
t
)
⋯
v
n
(
t
)
]
T, respectively. Then based on the discrete time model of second order system in Table 1, it can be obtained that for agent i
(12)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
u
i
j
(
k
)
,
(13)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
2
2
u
i
j
(
k
)
,
where u
i
j
(
k
) is the control input results from the relative state information between agent i and agent j. u
i
0 denotes the default control value of agent i that is usually set as 0 and τ
i
0
=
0 since the input is default.To make (13) more concise, some transformations need to be carried out. Set u
i
j
(
k
)
=
(
2
/
(
T
-
τ
i
j
(
k
)
)
2
)
u
i
j
′
(
k
). The transformation process is applicable because, during the period [
t
k
,
t
k
+
1
), τ
i
j
(
k
) are known to the agent i. Equations (12) and (13) are revised as
(14)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
2
(
t
k
+
1
-
τ
i
j
)
u
i
j
′
,
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
u
i
j
′
.With the controller gain chosen asK
=
[
α
β
], u
i
j
′
(
k
)
=
α
(
x
j
(
t
k
)
-
x
i
(
k
)
)
+
β
(
v
j
(
t
k
)
-
v
i
(
k
)
). The dynamics of the multiagent system can be presented as
(15)
[
X
(
t
k
+
1
)
V
(
t
k
+
1
)
]
=
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
[
X
(
t
k
)
V
(
t
k
)
]
.As we know, topology associated withL
k will have a spanning tree if Assumption 11 holds. L
k
′ has the same structure as L
k except for all its items that have been multiplied by 2
/
(
T
-
τ
i
j
(
k
)
). Thus, topology of L
k
′ also has a spanning tree. The consensus problem for system depicted as (15) can be discussed in a similar way as in Cao and Ren [8].Lemma 16 (Cao and Ren [8]).
With the decomposition of system transfer matrix as in (16), since L
k, L
k
′ all have spanning tree, if the conditions (
1
) and (
2
) are satisfied, consensus of the system can be reached
(16)
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
=
[
I
n
-
T
I
n
-
α
L
k
T
I
n
-
β
L
k
T
I
n
-
α
L
k
′
I
n
-
T
I
n
-
β
L
k
′
]
+
[
T
I
n
0
-
T
I
n
T
I
n
]
.
(1)
I
n
-
T
I
n
-
α
L
k
,
(
1
-
T
)
I
n
-
β
L
k
′ are nonnegative matrices with positive diagonal entries and T
I
n
-
β
L
k
,
T
I
n
-
α
L
k
′ are nonnegative matrices.
(2)
The infinite norm of matrix[
T
I
n
0
-
T
I
n
T
I
n
] is less than 1.The first condition is aimed to guarantee that the first matrix is a nonnegative one with positive diagonal entries. In addition, it is not difficult to find that the matrix is also stochastic. Then the matrix is SIA and Lemma7 is applicable. And the second condition is to make sure that multiplication of infinite number of the second matrix goes to zero. More detailed proofs can be found in Cao and Ren [8].Theorem 17.
For multiagent system consisting of double integrator agents, with Assumptions3–11 holding, if the sampling and transmitting period T and controller gain K can satisfy the following conditions, the consensus of the multiagent system is guaranteed:(1)
1
/
4
<
T
<
1
/
2;
(2)
α
=
β
=
τ
min
⁡
/
4
d
max
⁡.Proof.
If condition(
1
) is satisfied, the infinite norm of matrix [
T
I
n
0
-
T
I
n
T
I
n
] is less than 1. Define d
max
⁡, d
max
⁡
′ that represent the largest in-degree for L
k
,
L
k
′, respectively. d
max
⁡
′ is random due to the randomicity of transmission delays. From Assumption 3, it is obvious that
(17)
τ
min
⁡
d
max
⁡
′
<
d
max
⁡
.
Then, with the second condition, it can be acquired that(18)
sup
⁡
(
τ
min
⁡
4
d
max
⁡
d
max
⁡
′
)
<
1
4
.
As a result,T
-
α
d
max
⁡
′
>
0. Besides, it is not difficult to find that 1
-
T
-
β
d
max
⁡
′
>
0 since τ
min
⁡
<
T. As a result, it can be concluded that if the conditions are satisfied, Lemma 16 is also fulfilled and the consensusability of the multiagent system with double integrator dynamics is proved.


#### 3.2.2. With Communication Delays and Packet Losses

For second order system with packet losses, Assumption11 cannot hold and the Laplacian matrices L
k, L
k
′ discussed in the above section no longer have a spanning tree all the time. In this situation, Lemma 16 cannot directly be applied. Inspired by Qin et al. [17], a covariable can be introduced here with definition as
(19)
y
i
(
t
k
)
=
a
v
i
(
t
k
)
+
b
x
i
(
t
k
)
,
where a
,
b are constant parameters. It is easily derived that if x
(
t
k
) and y
(
t
k
) can reach consensus, the velocity of the system will also achieve consensus. So in the following discussion, the consensus problem of system states x
(
t
k
) and y
(
t
k
) is concerned. Besides, default control of agent i also needs to be set as u
i
0
′
=
-
c
v
i
(
t
k
), i
∈
{
1,2
,
…
,
n
}.As a result, the multiagent system can be transformed into(20)
[
x
(
t
k
+
1
)
y
(
t
k
+
1
)
]
=
[
(
1
-
b
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
T
a
(
1
-
c
T
)
I
n
-
β
a
L
k
(
c
b
T
-
b
2
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
′
(
b
T
a
(
1
-
c
T
)
+
1
-
c
T
)
I
n
-
β
a
L
k
′
]
[
x
(
t
k
)
y
(
t
k
)
]
.With proper choices of parametersα
,
β
,
a
,
b, and T, the system matrix can be a nonnegative stochastic matrix with positive diagonal elements. In fact, to ensure that the transfer matrix is stochastic, b
≡
1. Then if Assumption 13 holds, the system described as (20) can reach a consensus with similar proof as Theorem 14. However, because of the existence of default control input, the consensus value of system velocity is zero which is usually the case for rendezvous problem not for formation control or flocking. So in order to obtain the consensus for multiagent system without adding the control input u
i
0
′, in the subsequence of this paper, a different assumption about interaction topology needs to be made.Assumption 18.
The designed communication topology for the multiagent system is a directed spanning tree. Similarly, with Assumption13, this assumption essentially means that the union of digraphs within l periods is a directed spanning tree.Consider two agentsi, j and assume that there is a directed link from agent i to j. According to Assumption 13, there exist a positive integer g with 1
≤
g
≤
l such that the data transmission is successful during the period [
t
k
+
g
-
1
,
t
k
+
g
) and packets dropout during the previous g
-
1 periods. Define the delay during [
t
k
+
g
-
1
,
t
k
+
g
) as τ
i
j
(
t
k
g
) which satisfies Assumption 3. Adopt the controller gain as α
j
(
t
k
g
)
=
β
j
(
t
k
g
)
=
(
T
-
τ
i
j
(
t
k
g
)
)
/
4 and the following dynamics can be obtained for agents i and j: (21)
[
x
i
(
t
k
+
g
)
x
j
(
t
k
+
g
)
v
i
(
t
k
+
g
)
v
j
(
t
k
+
g
)
]
=
[
1
0
g
T
0
(
T
-
τ
i
j
(
t
k
g
)
)
4
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
0
0
1
0
1
2
-
1
2
1
2
(
1
+
(
g
-
1
)
T
)
1
2
(
1
-
(
g
-
1
)
T
)
]
×
[
x
i
(
t
k
)
x
j
(
t
k
)
v
i
(
t
k
)
v
j
(
t
k
)
]
.Define the states error between agentsi and j at time instants as t
k and t
k
+
g as follows:
(22)
ζ
i
j
(
d
+
1
)
=
x
j
(
t
k
+
g
)
-
x
i
(
t
k
+
g
)
,
ξ
i
j
(
d
+
1
)
=
v
j
(
t
k
+
g
)
-
v
i
(
t
k
+
g
)
,
ζ
i
j
(
d
)
=
x
j
(
t
k
)
-
x
i
(
t
k
)
,
ξ
i
j
(
d
)
=
v
j
(
t
k
)
-
v
i
(
t
k
)
,
where d represents the number of successful transmissions. Then the following equation is acquired denoting the error dynamics between agents i and j
:
(23)
[
ζ
i
j
(
d
+
1
)
ξ
i
j
(
d
+
1
)
]
=
[
(
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
[
ζ
i
j
(
d
)
ξ
i
j
(
d
)
]
.According to the error dynamics depicted as above, the following lemma can be proposed.Theorem 19.
For multiagent system consisting of double integrator dynamics as in Table1, with Assumptions 13 and 18, the consensusability of the system can be guaranteed with packet losses and transmission delays as long as the discrete error dynamics as in (23) is stable.Proof.
Without loss of generality, set agenti as the root node of the directed spanning tree. Define N
i
0 as the set of agents that receive information from agent i. If the error dynamics as in (23) is stable, that is, lim
⁡
d
→
∞
ζ
i
j
(
d
)
=
0,  lim
⁡
d
→
∞
ξ
i
j
(
d
)
=
0. It is obvious that agents i and j can reach a consensus for any j
∈
N
i
0 with finite time periods since Assumption 18 holds.
Then there exist a positive numberm
j and a time instant t
m
j such that [
ζ
i
j
(
m
j
)
ξ
i
j
(
m
j
)
]
T
=
[
0
0
]
T for t
>
t
m
j. With definition of t
m
=
max
⁡
{
t
m
j
}
,
j
∈
N
i
0, it can be derived that when t
>
t
m, x
j
(
t
)
=
x
i
(
t
)
,
v
j
(
t
)
=
v
i
(
t
), for all j
∈
N
i
0 which means that the consensus has been reached between agents i and N
i
0. Since the discrete error dynamics is as in (23) set no restrictions on initial states of agents and the agents belonging to N
j
0 will reach consensus with agent j in a similar way. Finally, the whole multiagent system will reach a consensus.To be more illustrative, the process can be shown in Figure1. The error dynamics between different agents in the dash line circle can be presented as (23). The agents in the real line circle mean that the consensus has been reached among them.Figure 1
Consensus process of multiagent system under directed spanning tree.In the following, an algorithm to testify the Schur stability of discrete-time dynamics system as in (23) is proposed. Since all communication delay τ
i
j is random, the transfer matrix(24)
M
=
[
(
1
-
T
-
τ
i
j
(
t
k
g
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]can be viewed as an interval matrix [
M
m
,
M
M
]
=
{
M
=
[
m
i
j
]
:
m
i
j
m
<
m
i
j
<
m
i
j
M
,
i
,
j
=
1,2
} for fixed g with the expressions of M
m and M
M as follows:
(25)
M
m
=
[
1
-
T
4
g
T
-
T
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
;
M
M
=
[
1
-
τ
min
⁡
4
g
T
-
τ
min
⁡
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
.The following lemma needs to be introduced concerning the stability of interval matrix.Lemma 20.
An interval matrix[
R
m
,
R
M
] is Schur stable if and only if there are finitely subinterval matrices [
R
i
m
,
R
i
M
]
⊂
[
R
m
,
R
M
], 1
≤
i
≤
k, such that
(26)
[
R
m
,
R
M
]
=
⋃
i
=
1
k
[
R
i
m
,
R
i
M
]
.
And for eachi, 1
≤
i
≤
k, [
R
i
m
,
R
i
M
] satisfies the following conditions.(1)
R
i
0 is Schur stable and there exists a positive definite matrix P
=
P
T satisfying
(27)
R
i
0
T
P
i
R
i
0
-
P
i
+
I
=
0
.
(2)
ϕ
(
Δ
R
i
)
<
[
ϕ
(
R
i
0
)
2
+
1
/
|
P
i
|
∞
]
1
/
2
-
ϕ
(
R
i
0
). ϕ
(
·
) is an operator ϕ
(
R
)
=
max
⁡
{
|
R
|
1
,
|
R
|
∞
} and the definitions of Δ
R
i and R
i
0 are as follows:
(28)
Δ
R
i
=
1
2
(
R
i
M
-
R
i
m
)
,
R
i
0
=
1
2
(
R
i
M
+
R
i
m
)
.
(3)
Subinterval matrices⋃
i
=
1
k
[
R
i
m
,
R
i
M
] are complete decomposition of interval matrix [
R
m
,
R
M
] which means that ∀
R
∈
[
R
m
,
R
M
], ∃
i
∈
[
1,2
,
…
,
k
] such that R
∈
[
R
i
m
,
R
i
M
].Proof.
See Wang et al. [30] and Liao et al. [31] for details.Consider the parameters in (23), according to Assumption 3 and τ
min
⁡ actually denotes the smallest processing time available for the embedded system. T is the sampling and transmitting period for the multiagent system and for acoustic communication system it also indicates the largest distance available between two linked agents since the relation Dis
<
v
c
(
T
-
τ
min
⁡
) has to be satisfied, where v
c is the acoustic velocity. Due to the physical meanings of τ
min
⁡, T, they usually are predetermined once the multiagent system structure is determined. As for g, according to Assumption 13 and the derivation of (23), g is a time varying positive integrator variable satisfying 1
≤
g
≤
l. So the following lemma is put forward.Lemma 21.
The system transfer matrix in (23) is Schur stable if, for every fixed g
∈
[
1,2
,
…
,
l
], [
M
m
,
M
M
] is Schur stable.Proof.
Define the interval matrix[
M
m
,
M
M
] as [
M
j
m
,
M
j
M
] when g
=
j, 1
≤
j
≤
l. If [
M
j
m
,
M
j
M
] is Schur stable, then there exist a finite number of subinterval matrices [
M
j
m
,
M
j
M
]
=
⋃
i
=
1
k
[
M
i
j
m
,
M
i
j
M
] satisfying conditions in Lemma 20. In addition, the system matrix in (23) can be completely decomposed as
(29)
[
M
m
,
M
M
]
=
⋃
g
=
1
l
[
M
j
m
,
M
j
M
]
.
Then it can be derived that(30)
[
M
m
,
M
M
]
=
{
⋃
i
=
1
k
[
M
i
1
m
,
M
i
1
M
]
}
∪
{
⋃
i
=
1
k
[
M
i
2
m
,
M
i
2
M
]
}
∪
⋯
∪
{
⋃
i
=
1
k
[
M
i
l
m
,
M
i
l
M
]
}
.
The above equation means that the system matrix can be decomposed into finite number of subinterval matrices that all satisfy the conditions in Lemma20. The matrix is Schur stable.Even though Lemmas20 and 21 have provided conditions to guarantee the Schur stability of the discrete interval system matrix, method to completely decompose an interval matrix is needed. Based on the definition of R
i
0 and Δ
R
i in (28), the interval matrix [
R
m
,
R
M
] can be presented as [
R
0
±
Δ
R
]. With this presentation, it is natural to adopt the decomposition as [
R
m
,
R
M
]
=
[
R
0
-
Δ
R
,
R
0
]
∪
[
R
0
,
R
0
+
Δ
R
]. However, the decomposition is not always complete. Denote the element of the interval matrix at ith row and jth column by [
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]. Then divide the interval into two subintervals as follows:
(31)
[
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]
=
R
L
(
i
,
j
)
∪
R
H
(
i
,
j
)withR
L
(
i
,
j
) and R
H
(
i
,
j
) defined as
(32)
R
L
(
i
,
j
)
=
[
R
0
(
i
,
j
)
-
Δ
R
(
i
,
j
)
,
R
0
(
i
,
j
)
]
,
R
H
(
i
,
j
)
=
[
R
0
(
i
,
j
)
,
R
0
(
i
,
j
)
+
Δ
R
(
i
,
j
)
]IfR
m
,
R
M
∈
R
n
×
n, the interval matrix can be decomposed as follows:
(33)
[
R
m
,
R
M
]
=
⋃
k
=
1
2
n
×
n
R
inv
(
k
)
.Each element inR
inv
(
k
) at ith row and jth column will be either R
L
(
i
,
j
) or R
H
(
i
,
j
). Then, it is obvious that the decomposition is complete. Now, Algorithm 1 is proposed in pseudocode to testify the Schur stability of the interval matrix. If a limited number of subintervals can be obtained for each [
M
j
m
,
M
j
M
], 1
≤
j
≤
l that satisfy the Schur stability conditions in Lemma 20, the system matrix in (23) is stable according to Lemma 21. That is, the multiagent system consists of second order agent with communication delays and packet losses can reach a consensus.Algorithm 1:
Initialization of parameters
τ
min
⁡, T and l;
For
j
=
1: l
Test the Schur stability
(
[
M
j
m
,
M
j
M
]
)
{
If
[
M
j
m
,
M
j
M
]
is Schur stable
Break;
Else
If
M
j
o
is not Hurwitz stable
[
M
j
m
,
M
j
M
]
is not stable; break;
Else
Decompose
[
M
j
m
,
M
j
M
];
Test the Schur stability (each subinterval);
}
EndThrough Algorithm1, the consensusability of the multiagent system concerned can be testified. However, since the controller gain and the system parameters are predefined, no analytical solutions are provided by this method for multiagent system that could not reach consensus. Besides, the computational burden of the algorithm will increase exponentially with the order of agents. Therefore, in the next section, a theorem will be proposed to design the controller gain and solve the consensus problem of multiagent system with high-order integrator agents.


### 3.3. High-Order Integrator Agent

Assume that Assumption18 still holds; similar result can be obtained as in Theorem 19; that is, if the root agent i and agent j, j
∈
N
i
0, can reach consensus, the multiagent system can reach consensus. So for the high-order integrator dynamics introduced in Table 1, with communication delays, the discrete system dynamics for agent i and agent j can be presented as
(34)
X
i
(
t
k
+
1
)
=
e
A
T
X
i
(
t
k
)
,
X
j
(
t
k
+
1
)
=
e
A
T
X
j
(
t
k
)
+
∫
o
T
-
τ
i
j
(
t
k
)
e
A
t
d
t
·
B
K
(
X
i
(
t
k
)
-
X
j
(
t
k
)
)
with K
=
[
k
1
k
2
⋯
k
m
] as the controller gain to be designed; τ
i
j
(
t
k
) is the communication delay satisfying Assumption 3. Let the states error between agent i and agent j at time t
k
(35)
δ
(
t
k
)
=
X
i
(
t
k
)
-
X
j
(
t
k
)
.The error dynamics between two agents is(36)
δ
(
t
k
+
1
)
=
(
e
A
T
-
∫
o
T
-
τ
i
j
(
t
k
)
e
A
t
d
t
·
B
K
)
δ
(
t
k
)
.Considering packet losses and according to Assumption13, there exists an integer g
∈
[
1
,
…
,
l
] such that the error dynamics during the period [
t
k
,
t
k
+
g
) can be presented as
(37)
δ
(
t
k
+
g
)
=
e
(
g
-
1
)
A
T
(
e
A
T
-
∫
o
T
-
τ
i
j
(
t
k
g
)
e
A
t
d
t
·
B
K
)
δ
(
t
k
)
.Algorithm1 can still be applied to test the Schur stability of system matrix equation (36) and (37). Except for the computational complexity increases exponentially with the system order, the controller gain is also difficult to design comparing with second order multiagent system. So in order to circumvent those difficulties, the following lemmas are applied to achieve the controller gain.Lemma 22 (see [32]).
For discrete time interval system as in (38), M
∈
R
n
×
n
,
N
∈
R
n
×
p, the system is stabilizable if and only if there exist a matrix G
∈
R
p
×
n and a symmetric positive definite matrix H
∈
R
n
×
n and scalars λ
i
j
>
0,  i
,
j
=
1,2
,
…
,
n,  δ
i
j
>
0,  i
=
1,2
,
…
,
n,  j
=
1,2
,
…
,
p, satisfying (39). And the controller gain can be adopted as K
=
G
H
-
1. Consider
(38)
δ
(
d
+
1
)
=
[
M
min
⁡
,
M
max
⁡
]
δ
(
d
)
+
[
N
min
⁡
,
N
max
⁡
]
u
(
d
)
,
u
(
d
)
=
K
δ
(
d
)
,
(39)
[
-
H
H
M
o
T
+
G
N
o
T
H
d
G
d
M
0
H
+
N
0
G
-
H
+
Σ
0
0
H
d
T
0
-
Λ
G
d
T
0
-
Δ
]
<
0
,
where Σ
=
∑
i
,
j
=
1
n
λ
i
j
|
Δ
m
i
j
|
2
e
i
e
i
T
+
∑
i
=
1
n
∑
j
=
1
p
δ
i
j
|
Δ
n
i
j
|
2
e
i
e
i
T, e
i is a column vector with ith element being 1. And
(40)
H
d
=
[
H
,
…
,
H
]
︸
n
,
G
d
=
[
G
T
,
…
,
G
T
]
︸
n
,
Λ
=
diag
⁡
{
λ
11
,
λ
12
,
…
,
λ
1
n
,
…
,
λ
n
1
,
λ
n
2
,
…
,
λ
n
n
}
,
Δ
=
diag
⁡
{
δ
11
,
δ
12
,
…
,
δ
1
p
,
…
,
δ
n
1
,
δ
n
2
,
…
,
δ
n
p
}
.Lemma 23.
The interval system matrices[
M
min
⁡
,
M
max
⁡
] and [
N
min
⁡
,
N
max
⁡
] are stabilizable if there are a finite number of subintervals [
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
], 1
≤
i
≤
k such that, for each i
∈
{
1,2
,
…
,
k
}, the system matrices [
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
] are stabilizable. And the interval system is completely decomposed which means that, at any time instant t, if N
(
t
)
∈
[
N
min
⁡
i
,
N
max
⁡
i
], then M
(
t
)
∈
[
M
min
⁡
i
,
M
max
⁡
i
], 1
≤
i
≤
k. And the complete decomposition can be denoted by
(41)
[
M
min
⁡
,
M
max
⁡
]
=
⋃
i
=
1
k
[
M
min
⁡
i
,
M
max
⁡
i
]
,
[
N
min
⁡
,
N
max
⁡
]
=
⋃
i
=
1
k
[
N
min
⁡
i
,
N
max
⁡
i
]
.Proof.
Since the system matrices[
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
] are stabilizable, suppose that the controller gain is denoted by K; then, it can be derived that [
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K is Schur stable. Because the interval system is completely decomposed, the following decomposition is also complete
(42)
[
M
min
⁡
,
M
max
⁡
]
+
[
N
min
⁡
,
N
max
⁡
]
K
=
⋃
i
=
1
k
(
[
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K
)
.
Then according to Lemma21, the Schur stability of [
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K
,
i
∈
{
1,2
,
…
,
k
} indicated Schur stability of the multiagent system.Comparing (36) with (37), it can be concluded that (36) is the special case of (37) when g
=
1. Actually, the interval matrices in (37) are piecewise interval, and the system can be completely decomposed into l subinterval systems easily. The subinterval systems can be presented as follows:
(43)
δ
(
t
k
+
g
)
=
e
g
A
T
δ
(
t
k
)
-
e
(
g
-
1
)
A
T
∫
o
T
-
τ
i
j
(
t
k
g
)
e
A
t
B
d
t
·
u
(
t
k
)
=
M
g
δ
(
t
k
)
+
N
g
u
(
t
k
)
for
g
∈
{
1,2
,
…
,
l
}
.Theorem 24.
For multiagent system consisting of high order agents, under Assumptions13 and 18, the consensusability of the system can be guaranteed with transmission delays and packet losses if there exists a controller gain K such that the conditions in Lemma 22 can be satisfied for each M
g
+
N
g
K, g
∈
{
1,2
,
…
,
l
}.Proof.
If the conditions in Lemma22 are satisfied, M
g
+
N
g
K is Schur stable. From (43), the interval system in (37) can be completely decomposed by M
g and N
g, g
∈
{
1,2
,
…
,
l
}. Then according to Lemma 23, the theorem is established.In fact, the existence of controller gainK is important in the above lemma. According to (39) in Lemma 22, matrix K can be obtained by solving the LMI with matlab. In order to guarantee the conditions in Lemma 23, l LMIs should be solved simultaneously to calculate the feedback gain K. Besides, it should be noticed that Theorem 24 is a general solution for controller gain of multiagent system and can be applied to all kinds of agent dynamics including single integrator, second order integrator, and general linear system.


## 3.1. Case 1: Single Integrator Agent

### 3.1.1. With Communication Delays and No Packet Losses

DefineX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
Tas the state of the multiagent system. Since it can be easily extended to multistate through Kronecker production, it is assumed here that each agent has only one state for briefness of description. Based on the controller as (2) and the discrete time model in Table 1, the dynamics of multiagent system can be denoted by
(7)
X
(
t
k
+
1
)
=
(
I
-
α
(
t
0
L
0
+
t
1
L
1
+
⋯
+
t
m
L
m
)
)
X
(
t
k
)
,
where controller gain K is presented as α
∈
R in this case. Because of transmission delays, Laplacian matrix is not invariant. So L
0
,
L
1
,
…
,
L
m represent the Laplacian matrices that exist during [
t
k
,
t
k
+
1
) and t
0
,
t
1
,
…
,
t
m are the durations for corresponding Laplacian matrices satisfying t
0
+
t
1
+
⋯
+
t
m
=
T. In fact, L
0 is a Laplacian matrix with no connections between agents and since no packet losses are concerned, for any 0
≤
i
≤
m
-
1, the topology associated with L
i is a subgraph of the topology associated L
i
+
1. To prove the consensusability of discrete-time system as in (7), following lemmas about nonnegative matrix and stochastic matrix are introduced beforehand.Lemma 5 (see [26]).
LetM
∈
R
n
×
n be a stochastic matrix. If M has an eigenvalue λ
=
1 with algebraic multiplicity equal to one and all of the other eigenvalues satisfy |
λ
|
<
1, then M is SIA. That is, lim
⁡
n
→
∞
M
n
→
1
y
T.Lemma 6 (see [9]).
A stochastic matrix has algebraic multiplicity equal to one for its eigenvalueλ
=
1 if and only if the graph associated with the matrix has a spanning tree. Furthermore, a stochastic matrix with positive diagonal elements has the property that |
λ
|
<
1 for every eigenvalue not equal to one.Lemma 7 (see [27]).
LetS
1
,
S
2
,
…
,
S
k be a finite set of SIA matrices with property that, for each sequence S
i
1
,
S
i
2
,
…
,
S
i
j of positive length, the matrix product S
i
j
S
i
j
-
1
⋯
S
i
1 is SIA. Then, for each infinite sequence S
i
1
,
S
i
2
,
…, there exists a column vector y such that lim
⁡
j
→
∞
S
i
j
,
S
i
j
-
1
,
…
,
S
i
1
=
1
y
T.Lemma 8 (Gershgorin circle criterion [28]).
All eigenvalues of a matrixE
=
[
e
i
j
]
∈
R
N
×
N are located within the union of N discs as follows:
(8)
⋃
i
=
1
N
{
z
∈
C
:
|
z
-
e
i
i
|
≤
∑
j
≠
i
|
e
i
j
|
}
.Lemma 9 (see [29]).
Letm
≥
2 be a positive integer and let P
1
,
P
2
,
…
,
P
m be nonnegative matrices with positive diagonal elements; then, P
1
P
2
⋯
P
m
≥
γ
(
P
1
+
P
2
+
⋯
+
P
m
), with γ
>
0. And if the digraph associated with γ
(
P
1
+
P
2
+
⋯
+
P
m
) has a spanning tree, the graph associated with P
1
P
2
⋯
P
m also has a spanning tree.Besides, some assumptions also need to be proposed.Assumption 10 (quantized transmission delays).
There exists a small positive valueΔ such that, for all i
,
j
∈
1,2
,
…
,
n,
(9)
τ
i
j
(
k
)
=
q
Δ
,
q
∈
1,2
,
…
,
m
q
.
Assumption10 indicates that transmission delays can be quantized and must be a multiple of fundamental delay time Δ. Assumption 10 is realizable and practical because all agents are operated under digital computers and the smaller the Δ is, the higher the accuracy is.Assumption 11.
The designed communication topology for the multiagent system has a directed spanning tree.This assumption means that if there are no packet losses and communication delays, the topology of the multiagent system has a spanning tree at every instantt
k. Combing with Assumption 3, it can be derived that the union of digraphs associated with L
0
,
L
1
,
…
,
L
m has a directed spanning tree. Then based on introduced lemmas and assumptions, the consensus of the system described as in (7) can be proposed.Theorem 12.
For multiagent system consisting of single integrator dynamics, with control protocol designed as (2) and Assumptions 3–11, the consensus of the multiagent system can be reached if the controller gain is set to be α
=
1
/
T
d
max
⁡, where d
max
⁡ is the largest in-degree of the Laplacian matrices L
0
,
L
1
,
…
L
m.Proof.
First of all, since there are a limited number of possible Laplacian matrices for fixed number of agents,d
max
⁡ can be precalculated without consideration about communication delays; then, it can be viewed as a constant in subsequent presentation. By substituting α
=
1
/
T
d
max
⁡ into (7), the system can be transformed as
(10)
X
(
t
k
+
1
)
=
(
I
-
1
d
max
⁡
(
t
0
T
L
0
+
t
1
T
L
1
+
⋯
+
t
m
T
L
m
)
)
X
(
t
k
)
=
M
k
X
(
t
k
)
.
Since Assumption11 holds and there are no packet losses, L
m has a spanning tree and the interaction graphs associated with L
0
,
L
1
,
…
,
L
m
-
1 are subgraphs of the topology associated with L
m. Then, for the union of graphs L
0
,
L
1
,
…
,
L
m
-
1, there is a simple eigenvalue equal to zero. According to Lemma 8, it is not difficult to conclude that all of other eigenvalues of (
1
/
d
max
⁡
)
(
(
t
0
/
T
)
L
0
+
(
t
1
/
T
)
L
1
+
⋯
+
(
t
m
/
T
)
L
m
) are located within the circle with origin point of (
1,0
) and radius of 1. Thus, it can be obtained that M
k is a matrix with simple eigenvalues equal to one and the others within the unit circle of the complex plane which means that the topology associated with M
k has a spanning tree according to Lemma 6.
In addition, since all the nondiagonal entries of Laplacian matrices are nonpositive, the nondiagonal entries ofM
k are nonnegative. All diagonal elements of M
k are less than one due to the choice of α. And since Laplacian matrices L
0
,
L
1
,
…
,
L
m all have zero row sums, M
k has row sum equal to one; that is, M
k is a stochastic matrix. As a conclusion, M
k is a stochastic nonnegative matrix with positive diagonal elements and it can be derived from Lemma 5 that M
k is SIA.
BecauseM
k has a spanning tree, M
k
M
k
+
1
⋯
M
k
+
l also has a spanning tree according to Lemma 9. In addition, the stochastic matrices with positive diagonal entries are closed under matrix multiplication, so that M
k
M
k
+
1
⋯
M
k
+
l is also a stochastic matrix with positive diagonal elements. According to Lemmas 6 and 5, the matrix M
k
M
k
+
1
⋯
M
k
+
l is SIA.
With Assumption10, it can be derived that there is a finite number of M
k. After that, Lemma 7 can be applied to acquire that the multiagent system as in (10) can reach a consensus. Theorem 12 is proved.


### 3.1.2. With Packet Losses and Communication Delays

In the above section, consensus problem with communication delays has been solved that lay firm foundation for the problem concerned in the situation where packet losses must be taken into consideration. In this case, Assumption3 is no longer satisfied. As mentioned previously, Assumption 3 is a relative strict condition to be fulfilled in practice. So the following assumption is proposed in addition.Assumption 13.
Set the success ratio of transmission between two agents asp
∈
(
0,1
), ∀
μ
∈
(
0,1
); there exists an integer l that satisfies 1
-
(
1
-
p
)
l
>
μ. If μ is chosen to be close to 1 enough, it is reasonable to assume that the transmission can be successful for at least one time during l periods. Besides, under Assumption 13, the communication delay can still satisfy Assumption 3 for the successful transmitted information. With Assumption 11, this assumption essentially means that the union of digraphs within l periods has a directed spanning tree.Theorem 14.
For multiagent system consisting of single integrator dynamics satisfying Assumptions10–13, with control protocol designed as in (2), the consensus of the multiagent system can be reached with the same controller gain α adopted as in Theorem 12.Proof.
In this situation, since Assumption3 is no longer satisfied all the time, L
m cannot always have a spanning tree. However, according to Assumptions 11 and 13, the digraph associated with M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1 will have a spanning tree. Since M
k is still a stochastic nonnegative matrix with positive diagonal elements, Lemma 9 still holds; that is, the relation M
k
M
k
+
1
⋯
M
k
+
l
-
1
≥
γ
(
M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1
) exists. Thus, define Q
k
,
l
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1 such that
(11)
X
(
t
k
+
l
)
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1
X
(
t
k
)
=
Q
k
,
l
X
(
t
k
)
.
SinceQ
k
,
l is a stochastic nonnegative matrix with positive diagonal elements and the associated graph has a spanning tree, the problem regarding packet losses and communication delays can be handled in a similar way as in proof of Theorem 12. So, the consensusability of multiagent system with packet losses and communication delays is guaranteed.Remark 15.
Based on the analysis of this section, it can be found that Theorem12 can be viewed as a special case of Theorem 14 with l
=
1. With the proposed control protocol and proper choice of controller gain, the multiagent system can reach consensus as long as the union of the digraphs within finite periods has a spanning tree.


## 3.1.1. With Communication Delays and No Packet Losses

DefineX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
Tas the state of the multiagent system. Since it can be easily extended to multistate through Kronecker production, it is assumed here that each agent has only one state for briefness of description. Based on the controller as (2) and the discrete time model in Table 1, the dynamics of multiagent system can be denoted by
(7)
X
(
t
k
+
1
)
=
(
I
-
α
(
t
0
L
0
+
t
1
L
1
+
⋯
+
t
m
L
m
)
)
X
(
t
k
)
,
where controller gain K is presented as α
∈
R in this case. Because of transmission delays, Laplacian matrix is not invariant. So L
0
,
L
1
,
…
,
L
m represent the Laplacian matrices that exist during [
t
k
,
t
k
+
1
) and t
0
,
t
1
,
…
,
t
m are the durations for corresponding Laplacian matrices satisfying t
0
+
t
1
+
⋯
+
t
m
=
T. In fact, L
0 is a Laplacian matrix with no connections between agents and since no packet losses are concerned, for any 0
≤
i
≤
m
-
1, the topology associated with L
i is a subgraph of the topology associated L
i
+
1. To prove the consensusability of discrete-time system as in (7), following lemmas about nonnegative matrix and stochastic matrix are introduced beforehand.Lemma 5 (see [26]).
LetM
∈
R
n
×
n be a stochastic matrix. If M has an eigenvalue λ
=
1 with algebraic multiplicity equal to one and all of the other eigenvalues satisfy |
λ
|
<
1, then M is SIA. That is, lim
⁡
n
→
∞
M
n
→
1
y
T.Lemma 6 (see [9]).
A stochastic matrix has algebraic multiplicity equal to one for its eigenvalueλ
=
1 if and only if the graph associated with the matrix has a spanning tree. Furthermore, a stochastic matrix with positive diagonal elements has the property that |
λ
|
<
1 for every eigenvalue not equal to one.Lemma 7 (see [27]).
LetS
1
,
S
2
,
…
,
S
k be a finite set of SIA matrices with property that, for each sequence S
i
1
,
S
i
2
,
…
,
S
i
j of positive length, the matrix product S
i
j
S
i
j
-
1
⋯
S
i
1 is SIA. Then, for each infinite sequence S
i
1
,
S
i
2
,
…, there exists a column vector y such that lim
⁡
j
→
∞
S
i
j
,
S
i
j
-
1
,
…
,
S
i
1
=
1
y
T.Lemma 8 (Gershgorin circle criterion [28]).
All eigenvalues of a matrixE
=
[
e
i
j
]
∈
R
N
×
N are located within the union of N discs as follows:
(8)
⋃
i
=
1
N
{
z
∈
C
:
|
z
-
e
i
i
|
≤
∑
j
≠
i
|
e
i
j
|
}
.Lemma 9 (see [29]).
Letm
≥
2 be a positive integer and let P
1
,
P
2
,
…
,
P
m be nonnegative matrices with positive diagonal elements; then, P
1
P
2
⋯
P
m
≥
γ
(
P
1
+
P
2
+
⋯
+
P
m
), with γ
>
0. And if the digraph associated with γ
(
P
1
+
P
2
+
⋯
+
P
m
) has a spanning tree, the graph associated with P
1
P
2
⋯
P
m also has a spanning tree.Besides, some assumptions also need to be proposed.Assumption 10 (quantized transmission delays).
There exists a small positive valueΔ such that, for all i
,
j
∈
1,2
,
…
,
n,
(9)
τ
i
j
(
k
)
=
q
Δ
,
q
∈
1,2
,
…
,
m
q
.
Assumption10 indicates that transmission delays can be quantized and must be a multiple of fundamental delay time Δ. Assumption 10 is realizable and practical because all agents are operated under digital computers and the smaller the Δ is, the higher the accuracy is.Assumption 11.
The designed communication topology for the multiagent system has a directed spanning tree.This assumption means that if there are no packet losses and communication delays, the topology of the multiagent system has a spanning tree at every instantt
k. Combing with Assumption 3, it can be derived that the union of digraphs associated with L
0
,
L
1
,
…
,
L
m has a directed spanning tree. Then based on introduced lemmas and assumptions, the consensus of the system described as in (7) can be proposed.Theorem 12.
For multiagent system consisting of single integrator dynamics, with control protocol designed as (2) and Assumptions 3–11, the consensus of the multiagent system can be reached if the controller gain is set to be α
=
1
/
T
d
max
⁡, where d
max
⁡ is the largest in-degree of the Laplacian matrices L
0
,
L
1
,
…
L
m.Proof.
First of all, since there are a limited number of possible Laplacian matrices for fixed number of agents,d
max
⁡ can be precalculated without consideration about communication delays; then, it can be viewed as a constant in subsequent presentation. By substituting α
=
1
/
T
d
max
⁡ into (7), the system can be transformed as
(10)
X
(
t
k
+
1
)
=
(
I
-
1
d
max
⁡
(
t
0
T
L
0
+
t
1
T
L
1
+
⋯
+
t
m
T
L
m
)
)
X
(
t
k
)
=
M
k
X
(
t
k
)
.
Since Assumption11 holds and there are no packet losses, L
m has a spanning tree and the interaction graphs associated with L
0
,
L
1
,
…
,
L
m
-
1 are subgraphs of the topology associated with L
m. Then, for the union of graphs L
0
,
L
1
,
…
,
L
m
-
1, there is a simple eigenvalue equal to zero. According to Lemma 8, it is not difficult to conclude that all of other eigenvalues of (
1
/
d
max
⁡
)
(
(
t
0
/
T
)
L
0
+
(
t
1
/
T
)
L
1
+
⋯
+
(
t
m
/
T
)
L
m
) are located within the circle with origin point of (
1,0
) and radius of 1. Thus, it can be obtained that M
k is a matrix with simple eigenvalues equal to one and the others within the unit circle of the complex plane which means that the topology associated with M
k has a spanning tree according to Lemma 6.
In addition, since all the nondiagonal entries of Laplacian matrices are nonpositive, the nondiagonal entries ofM
k are nonnegative. All diagonal elements of M
k are less than one due to the choice of α. And since Laplacian matrices L
0
,
L
1
,
…
,
L
m all have zero row sums, M
k has row sum equal to one; that is, M
k is a stochastic matrix. As a conclusion, M
k is a stochastic nonnegative matrix with positive diagonal elements and it can be derived from Lemma 5 that M
k is SIA.
BecauseM
k has a spanning tree, M
k
M
k
+
1
⋯
M
k
+
l also has a spanning tree according to Lemma 9. In addition, the stochastic matrices with positive diagonal entries are closed under matrix multiplication, so that M
k
M
k
+
1
⋯
M
k
+
l is also a stochastic matrix with positive diagonal elements. According to Lemmas 6 and 5, the matrix M
k
M
k
+
1
⋯
M
k
+
l is SIA.
With Assumption10, it can be derived that there is a finite number of M
k. After that, Lemma 7 can be applied to acquire that the multiagent system as in (10) can reach a consensus. Theorem 12 is proved.


## 3.1.2. With Packet Losses and Communication Delays

In the above section, consensus problem with communication delays has been solved that lay firm foundation for the problem concerned in the situation where packet losses must be taken into consideration. In this case, Assumption3 is no longer satisfied. As mentioned previously, Assumption 3 is a relative strict condition to be fulfilled in practice. So the following assumption is proposed in addition.Assumption 13.
Set the success ratio of transmission between two agents asp
∈
(
0,1
), ∀
μ
∈
(
0,1
); there exists an integer l that satisfies 1
-
(
1
-
p
)
l
>
μ. If μ is chosen to be close to 1 enough, it is reasonable to assume that the transmission can be successful for at least one time during l periods. Besides, under Assumption 13, the communication delay can still satisfy Assumption 3 for the successful transmitted information. With Assumption 11, this assumption essentially means that the union of digraphs within l periods has a directed spanning tree.Theorem 14.
For multiagent system consisting of single integrator dynamics satisfying Assumptions10–13, with control protocol designed as in (2), the consensus of the multiagent system can be reached with the same controller gain α adopted as in Theorem 12.Proof.
In this situation, since Assumption3 is no longer satisfied all the time, L
m cannot always have a spanning tree. However, according to Assumptions 11 and 13, the digraph associated with M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1 will have a spanning tree. Since M
k is still a stochastic nonnegative matrix with positive diagonal elements, Lemma 9 still holds; that is, the relation M
k
M
k
+
1
⋯
M
k
+
l
-
1
≥
γ
(
M
k
+
M
k
+
1
+
⋯
+
M
k
+
l
-
1
) exists. Thus, define Q
k
,
l
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1 such that
(11)
X
(
t
k
+
l
)
=
M
k
M
k
+
1
⋯
M
k
+
l
-
1
X
(
t
k
)
=
Q
k
,
l
X
(
t
k
)
.
SinceQ
k
,
l is a stochastic nonnegative matrix with positive diagonal elements and the associated graph has a spanning tree, the problem regarding packet losses and communication delays can be handled in a similar way as in proof of Theorem 12. So, the consensusability of multiagent system with packet losses and communication delays is guaranteed.Remark 15.
Based on the analysis of this section, it can be found that Theorem12 can be viewed as a special case of Theorem 14 with l
=
1. With the proposed control protocol and proper choice of controller gain, the multiagent system can reach consensus as long as the union of the digraphs within finite periods has a spanning tree.


## 3.2. Case 2: Double Integrator Agent

### 3.2.1. With Communication Delays and No Packet Losses

For second order multiagent system, the corresponding variables are defined asX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
T, V
(
t
)
=
[
v
1
(
t
)
v
2
(
t
)
⋯
v
n
(
t
)
]
T, respectively. Then based on the discrete time model of second order system in Table 1, it can be obtained that for agent i
(12)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
u
i
j
(
k
)
,
(13)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
2
2
u
i
j
(
k
)
,
where u
i
j
(
k
) is the control input results from the relative state information between agent i and agent j. u
i
0 denotes the default control value of agent i that is usually set as 0 and τ
i
0
=
0 since the input is default.To make (13) more concise, some transformations need to be carried out. Set u
i
j
(
k
)
=
(
2
/
(
T
-
τ
i
j
(
k
)
)
2
)
u
i
j
′
(
k
). The transformation process is applicable because, during the period [
t
k
,
t
k
+
1
), τ
i
j
(
k
) are known to the agent i. Equations (12) and (13) are revised as
(14)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
2
(
t
k
+
1
-
τ
i
j
)
u
i
j
′
,
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
u
i
j
′
.With the controller gain chosen asK
=
[
α
β
], u
i
j
′
(
k
)
=
α
(
x
j
(
t
k
)
-
x
i
(
k
)
)
+
β
(
v
j
(
t
k
)
-
v
i
(
k
)
). The dynamics of the multiagent system can be presented as
(15)
[
X
(
t
k
+
1
)
V
(
t
k
+
1
)
]
=
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
[
X
(
t
k
)
V
(
t
k
)
]
.As we know, topology associated withL
k will have a spanning tree if Assumption 11 holds. L
k
′ has the same structure as L
k except for all its items that have been multiplied by 2
/
(
T
-
τ
i
j
(
k
)
). Thus, topology of L
k
′ also has a spanning tree. The consensus problem for system depicted as (15) can be discussed in a similar way as in Cao and Ren [8].Lemma 16 (Cao and Ren [8]).
With the decomposition of system transfer matrix as in (16), since L
k, L
k
′ all have spanning tree, if the conditions (
1
) and (
2
) are satisfied, consensus of the system can be reached
(16)
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
=
[
I
n
-
T
I
n
-
α
L
k
T
I
n
-
β
L
k
T
I
n
-
α
L
k
′
I
n
-
T
I
n
-
β
L
k
′
]
+
[
T
I
n
0
-
T
I
n
T
I
n
]
.
(1)
I
n
-
T
I
n
-
α
L
k
,
(
1
-
T
)
I
n
-
β
L
k
′ are nonnegative matrices with positive diagonal entries and T
I
n
-
β
L
k
,
T
I
n
-
α
L
k
′ are nonnegative matrices.
(2)
The infinite norm of matrix[
T
I
n
0
-
T
I
n
T
I
n
] is less than 1.The first condition is aimed to guarantee that the first matrix is a nonnegative one with positive diagonal entries. In addition, it is not difficult to find that the matrix is also stochastic. Then the matrix is SIA and Lemma7 is applicable. And the second condition is to make sure that multiplication of infinite number of the second matrix goes to zero. More detailed proofs can be found in Cao and Ren [8].Theorem 17.
For multiagent system consisting of double integrator agents, with Assumptions3–11 holding, if the sampling and transmitting period T and controller gain K can satisfy the following conditions, the consensus of the multiagent system is guaranteed:(1)
1
/
4
<
T
<
1
/
2;
(2)
α
=
β
=
τ
min
⁡
/
4
d
max
⁡.Proof.
If condition(
1
) is satisfied, the infinite norm of matrix [
T
I
n
0
-
T
I
n
T
I
n
] is less than 1. Define d
max
⁡, d
max
⁡
′ that represent the largest in-degree for L
k
,
L
k
′, respectively. d
max
⁡
′ is random due to the randomicity of transmission delays. From Assumption 3, it is obvious that
(17)
τ
min
⁡
d
max
⁡
′
<
d
max
⁡
.
Then, with the second condition, it can be acquired that(18)
sup
⁡
(
τ
min
⁡
4
d
max
⁡
d
max
⁡
′
)
<
1
4
.
As a result,T
-
α
d
max
⁡
′
>
0. Besides, it is not difficult to find that 1
-
T
-
β
d
max
⁡
′
>
0 since τ
min
⁡
<
T. As a result, it can be concluded that if the conditions are satisfied, Lemma 16 is also fulfilled and the consensusability of the multiagent system with double integrator dynamics is proved.


### 3.2.2. With Communication Delays and Packet Losses

For second order system with packet losses, Assumption11 cannot hold and the Laplacian matrices L
k, L
k
′ discussed in the above section no longer have a spanning tree all the time. In this situation, Lemma 16 cannot directly be applied. Inspired by Qin et al. [17], a covariable can be introduced here with definition as
(19)
y
i
(
t
k
)
=
a
v
i
(
t
k
)
+
b
x
i
(
t
k
)
,
where a
,
b are constant parameters. It is easily derived that if x
(
t
k
) and y
(
t
k
) can reach consensus, the velocity of the system will also achieve consensus. So in the following discussion, the consensus problem of system states x
(
t
k
) and y
(
t
k
) is concerned. Besides, default control of agent i also needs to be set as u
i
0
′
=
-
c
v
i
(
t
k
), i
∈
{
1,2
,
…
,
n
}.As a result, the multiagent system can be transformed into(20)
[
x
(
t
k
+
1
)
y
(
t
k
+
1
)
]
=
[
(
1
-
b
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
T
a
(
1
-
c
T
)
I
n
-
β
a
L
k
(
c
b
T
-
b
2
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
′
(
b
T
a
(
1
-
c
T
)
+
1
-
c
T
)
I
n
-
β
a
L
k
′
]
[
x
(
t
k
)
y
(
t
k
)
]
.With proper choices of parametersα
,
β
,
a
,
b, and T, the system matrix can be a nonnegative stochastic matrix with positive diagonal elements. In fact, to ensure that the transfer matrix is stochastic, b
≡
1. Then if Assumption 13 holds, the system described as (20) can reach a consensus with similar proof as Theorem 14. However, because of the existence of default control input, the consensus value of system velocity is zero which is usually the case for rendezvous problem not for formation control or flocking. So in order to obtain the consensus for multiagent system without adding the control input u
i
0
′, in the subsequence of this paper, a different assumption about interaction topology needs to be made.Assumption 18.
The designed communication topology for the multiagent system is a directed spanning tree. Similarly, with Assumption13, this assumption essentially means that the union of digraphs within l periods is a directed spanning tree.Consider two agentsi, j and assume that there is a directed link from agent i to j. According to Assumption 13, there exist a positive integer g with 1
≤
g
≤
l such that the data transmission is successful during the period [
t
k
+
g
-
1
,
t
k
+
g
) and packets dropout during the previous g
-
1 periods. Define the delay during [
t
k
+
g
-
1
,
t
k
+
g
) as τ
i
j
(
t
k
g
) which satisfies Assumption 3. Adopt the controller gain as α
j
(
t
k
g
)
=
β
j
(
t
k
g
)
=
(
T
-
τ
i
j
(
t
k
g
)
)
/
4 and the following dynamics can be obtained for agents i and j: (21)
[
x
i
(
t
k
+
g
)
x
j
(
t
k
+
g
)
v
i
(
t
k
+
g
)
v
j
(
t
k
+
g
)
]
=
[
1
0
g
T
0
(
T
-
τ
i
j
(
t
k
g
)
)
4
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
0
0
1
0
1
2
-
1
2
1
2
(
1
+
(
g
-
1
)
T
)
1
2
(
1
-
(
g
-
1
)
T
)
]
×
[
x
i
(
t
k
)
x
j
(
t
k
)
v
i
(
t
k
)
v
j
(
t
k
)
]
.Define the states error between agentsi and j at time instants as t
k and t
k
+
g as follows:
(22)
ζ
i
j
(
d
+
1
)
=
x
j
(
t
k
+
g
)
-
x
i
(
t
k
+
g
)
,
ξ
i
j
(
d
+
1
)
=
v
j
(
t
k
+
g
)
-
v
i
(
t
k
+
g
)
,
ζ
i
j
(
d
)
=
x
j
(
t
k
)
-
x
i
(
t
k
)
,
ξ
i
j
(
d
)
=
v
j
(
t
k
)
-
v
i
(
t
k
)
,
where d represents the number of successful transmissions. Then the following equation is acquired denoting the error dynamics between agents i and j
:
(23)
[
ζ
i
j
(
d
+
1
)
ξ
i
j
(
d
+
1
)
]
=
[
(
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
[
ζ
i
j
(
d
)
ξ
i
j
(
d
)
]
.According to the error dynamics depicted as above, the following lemma can be proposed.Theorem 19.
For multiagent system consisting of double integrator dynamics as in Table1, with Assumptions 13 and 18, the consensusability of the system can be guaranteed with packet losses and transmission delays as long as the discrete error dynamics as in (23) is stable.Proof.
Without loss of generality, set agenti as the root node of the directed spanning tree. Define N
i
0 as the set of agents that receive information from agent i. If the error dynamics as in (23) is stable, that is, lim
⁡
d
→
∞
ζ
i
j
(
d
)
=
0,  lim
⁡
d
→
∞
ξ
i
j
(
d
)
=
0. It is obvious that agents i and j can reach a consensus for any j
∈
N
i
0 with finite time periods since Assumption 18 holds.
Then there exist a positive numberm
j and a time instant t
m
j such that [
ζ
i
j
(
m
j
)
ξ
i
j
(
m
j
)
]
T
=
[
0
0
]
T for t
>
t
m
j. With definition of t
m
=
max
⁡
{
t
m
j
}
,
j
∈
N
i
0, it can be derived that when t
>
t
m, x
j
(
t
)
=
x
i
(
t
)
,
v
j
(
t
)
=
v
i
(
t
), for all j
∈
N
i
0 which means that the consensus has been reached between agents i and N
i
0. Since the discrete error dynamics is as in (23) set no restrictions on initial states of agents and the agents belonging to N
j
0 will reach consensus with agent j in a similar way. Finally, the whole multiagent system will reach a consensus.To be more illustrative, the process can be shown in Figure1. The error dynamics between different agents in the dash line circle can be presented as (23). The agents in the real line circle mean that the consensus has been reached among them.Figure 1
Consensus process of multiagent system under directed spanning tree.In the following, an algorithm to testify the Schur stability of discrete-time dynamics system as in (23) is proposed. Since all communication delay τ
i
j is random, the transfer matrix(24)
M
=
[
(
1
-
T
-
τ
i
j
(
t
k
g
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]can be viewed as an interval matrix [
M
m
,
M
M
]
=
{
M
=
[
m
i
j
]
:
m
i
j
m
<
m
i
j
<
m
i
j
M
,
i
,
j
=
1,2
} for fixed g with the expressions of M
m and M
M as follows:
(25)
M
m
=
[
1
-
T
4
g
T
-
T
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
;
M
M
=
[
1
-
τ
min
⁡
4
g
T
-
τ
min
⁡
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
.The following lemma needs to be introduced concerning the stability of interval matrix.Lemma 20.
An interval matrix[
R
m
,
R
M
] is Schur stable if and only if there are finitely subinterval matrices [
R
i
m
,
R
i
M
]
⊂
[
R
m
,
R
M
], 1
≤
i
≤
k, such that
(26)
[
R
m
,
R
M
]
=
⋃
i
=
1
k
[
R
i
m
,
R
i
M
]
.
And for eachi, 1
≤
i
≤
k, [
R
i
m
,
R
i
M
] satisfies the following conditions.(1)
R
i
0 is Schur stable and there exists a positive definite matrix P
=
P
T satisfying
(27)
R
i
0
T
P
i
R
i
0
-
P
i
+
I
=
0
.
(2)
ϕ
(
Δ
R
i
)
<
[
ϕ
(
R
i
0
)
2
+
1
/
|
P
i
|
∞
]
1
/
2
-
ϕ
(
R
i
0
). ϕ
(
·
) is an operator ϕ
(
R
)
=
max
⁡
{
|
R
|
1
,
|
R
|
∞
} and the definitions of Δ
R
i and R
i
0 are as follows:
(28)
Δ
R
i
=
1
2
(
R
i
M
-
R
i
m
)
,
R
i
0
=
1
2
(
R
i
M
+
R
i
m
)
.
(3)
Subinterval matrices⋃
i
=
1
k
[
R
i
m
,
R
i
M
] are complete decomposition of interval matrix [
R
m
,
R
M
] which means that ∀
R
∈
[
R
m
,
R
M
], ∃
i
∈
[
1,2
,
…
,
k
] such that R
∈
[
R
i
m
,
R
i
M
].Proof.
See Wang et al. [30] and Liao et al. [31] for details.Consider the parameters in (23), according to Assumption 3 and τ
min
⁡ actually denotes the smallest processing time available for the embedded system. T is the sampling and transmitting period for the multiagent system and for acoustic communication system it also indicates the largest distance available between two linked agents since the relation Dis
<
v
c
(
T
-
τ
min
⁡
) has to be satisfied, where v
c is the acoustic velocity. Due to the physical meanings of τ
min
⁡, T, they usually are predetermined once the multiagent system structure is determined. As for g, according to Assumption 13 and the derivation of (23), g is a time varying positive integrator variable satisfying 1
≤
g
≤
l. So the following lemma is put forward.Lemma 21.
The system transfer matrix in (23) is Schur stable if, for every fixed g
∈
[
1,2
,
…
,
l
], [
M
m
,
M
M
] is Schur stable.Proof.
Define the interval matrix[
M
m
,
M
M
] as [
M
j
m
,
M
j
M
] when g
=
j, 1
≤
j
≤
l. If [
M
j
m
,
M
j
M
] is Schur stable, then there exist a finite number of subinterval matrices [
M
j
m
,
M
j
M
]
=
⋃
i
=
1
k
[
M
i
j
m
,
M
i
j
M
] satisfying conditions in Lemma 20. In addition, the system matrix in (23) can be completely decomposed as
(29)
[
M
m
,
M
M
]
=
⋃
g
=
1
l
[
M
j
m
,
M
j
M
]
.
Then it can be derived that(30)
[
M
m
,
M
M
]
=
{
⋃
i
=
1
k
[
M
i
1
m
,
M
i
1
M
]
}
∪
{
⋃
i
=
1
k
[
M
i
2
m
,
M
i
2
M
]
}
∪
⋯
∪
{
⋃
i
=
1
k
[
M
i
l
m
,
M
i
l
M
]
}
.
The above equation means that the system matrix can be decomposed into finite number of subinterval matrices that all satisfy the conditions in Lemma20. The matrix is Schur stable.Even though Lemmas20 and 21 have provided conditions to guarantee the Schur stability of the discrete interval system matrix, method to completely decompose an interval matrix is needed. Based on the definition of R
i
0 and Δ
R
i in (28), the interval matrix [
R
m
,
R
M
] can be presented as [
R
0
±
Δ
R
]. With this presentation, it is natural to adopt the decomposition as [
R
m
,
R
M
]
=
[
R
0
-
Δ
R
,
R
0
]
∪
[
R
0
,
R
0
+
Δ
R
]. However, the decomposition is not always complete. Denote the element of the interval matrix at ith row and jth column by [
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]. Then divide the interval into two subintervals as follows:
(31)
[
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]
=
R
L
(
i
,
j
)
∪
R
H
(
i
,
j
)withR
L
(
i
,
j
) and R
H
(
i
,
j
) defined as
(32)
R
L
(
i
,
j
)
=
[
R
0
(
i
,
j
)
-
Δ
R
(
i
,
j
)
,
R
0
(
i
,
j
)
]
,
R
H
(
i
,
j
)
=
[
R
0
(
i
,
j
)
,
R
0
(
i
,
j
)
+
Δ
R
(
i
,
j
)
]IfR
m
,
R
M
∈
R
n
×
n, the interval matrix can be decomposed as follows:
(33)
[
R
m
,
R
M
]
=
⋃
k
=
1
2
n
×
n
R
inv
(
k
)
.Each element inR
inv
(
k
) at ith row and jth column will be either R
L
(
i
,
j
) or R
H
(
i
,
j
). Then, it is obvious that the decomposition is complete. Now, Algorithm 1 is proposed in pseudocode to testify the Schur stability of the interval matrix. If a limited number of subintervals can be obtained for each [
M
j
m
,
M
j
M
], 1
≤
j
≤
l that satisfy the Schur stability conditions in Lemma 20, the system matrix in (23) is stable according to Lemma 21. That is, the multiagent system consists of second order agent with communication delays and packet losses can reach a consensus.Algorithm 1:
Initialization of parameters
τ
min
⁡, T and l;
For
j
=
1: l
Test the Schur stability
(
[
M
j
m
,
M
j
M
]
)
{
If
[
M
j
m
,
M
j
M
]
is Schur stable
Break;
Else
If
M
j
o
is not Hurwitz stable
[
M
j
m
,
M
j
M
]
is not stable; break;
Else
Decompose
[
M
j
m
,
M
j
M
];
Test the Schur stability (each subinterval);
}
EndThrough Algorithm1, the consensusability of the multiagent system concerned can be testified. However, since the controller gain and the system parameters are predefined, no analytical solutions are provided by this method for multiagent system that could not reach consensus. Besides, the computational burden of the algorithm will increase exponentially with the order of agents. Therefore, in the next section, a theorem will be proposed to design the controller gain and solve the consensus problem of multiagent system with high-order integrator agents.


## 3.2.1. With Communication Delays and No Packet Losses

For second order multiagent system, the corresponding variables are defined asX
(
t
)
=
[
x
1
(
t
)
x
2
(
t
)
⋯
x
n
(
t
)
]
T, V
(
t
)
=
[
v
1
(
t
)
v
2
(
t
)
⋯
v
n
(
t
)
]
T, respectively. Then based on the discrete time model of second order system in Table 1, it can be obtained that for agent i
(12)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
u
i
j
(
k
)
,
(13)
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
(
T
-
τ
i
j
(
k
)
)
2
2
u
i
j
(
k
)
,
where u
i
j
(
k
) is the control input results from the relative state information between agent i and agent j. u
i
0 denotes the default control value of agent i that is usually set as 0 and τ
i
0
=
0 since the input is default.To make (13) more concise, some transformations need to be carried out. Set u
i
j
(
k
)
=
(
2
/
(
T
-
τ
i
j
(
k
)
)
2
)
u
i
j
′
(
k
). The transformation process is applicable because, during the period [
t
k
,
t
k
+
1
), τ
i
j
(
k
) are known to the agent i. Equations (12) and (13) are revised as
(14)
v
i
(
t
k
+
1
)
=
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
2
(
t
k
+
1
-
τ
i
j
)
u
i
j
′
,
x
i
(
t
k
+
1
)
=
x
i
(
t
k
)
+
T
v
i
(
t
k
)
+
∑
j
∈
N
i
,
j
=
0
u
i
j
′
.With the controller gain chosen asK
=
[
α
β
], u
i
j
′
(
k
)
=
α
(
x
j
(
t
k
)
-
x
i
(
k
)
)
+
β
(
v
j
(
t
k
)
-
v
i
(
k
)
). The dynamics of the multiagent system can be presented as
(15)
[
X
(
t
k
+
1
)
V
(
t
k
+
1
)
]
=
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
[
X
(
t
k
)
V
(
t
k
)
]
.As we know, topology associated withL
k will have a spanning tree if Assumption 11 holds. L
k
′ has the same structure as L
k except for all its items that have been multiplied by 2
/
(
T
-
τ
i
j
(
k
)
). Thus, topology of L
k
′ also has a spanning tree. The consensus problem for system depicted as (15) can be discussed in a similar way as in Cao and Ren [8].Lemma 16 (Cao and Ren [8]).
With the decomposition of system transfer matrix as in (16), since L
k, L
k
′ all have spanning tree, if the conditions (
1
) and (
2
) are satisfied, consensus of the system can be reached
(16)
[
I
n
-
α
L
k
T
I
n
-
β
L
k
-
α
L
k
′
I
n
-
β
L
k
′
]
=
[
I
n
-
T
I
n
-
α
L
k
T
I
n
-
β
L
k
T
I
n
-
α
L
k
′
I
n
-
T
I
n
-
β
L
k
′
]
+
[
T
I
n
0
-
T
I
n
T
I
n
]
.
(1)
I
n
-
T
I
n
-
α
L
k
,
(
1
-
T
)
I
n
-
β
L
k
′ are nonnegative matrices with positive diagonal entries and T
I
n
-
β
L
k
,
T
I
n
-
α
L
k
′ are nonnegative matrices.
(2)
The infinite norm of matrix[
T
I
n
0
-
T
I
n
T
I
n
] is less than 1.The first condition is aimed to guarantee that the first matrix is a nonnegative one with positive diagonal entries. In addition, it is not difficult to find that the matrix is also stochastic. Then the matrix is SIA and Lemma7 is applicable. And the second condition is to make sure that multiplication of infinite number of the second matrix goes to zero. More detailed proofs can be found in Cao and Ren [8].Theorem 17.
For multiagent system consisting of double integrator agents, with Assumptions3–11 holding, if the sampling and transmitting period T and controller gain K can satisfy the following conditions, the consensus of the multiagent system is guaranteed:(1)
1
/
4
<
T
<
1
/
2;
(2)
α
=
β
=
τ
min
⁡
/
4
d
max
⁡.Proof.
If condition(
1
) is satisfied, the infinite norm of matrix [
T
I
n
0
-
T
I
n
T
I
n
] is less than 1. Define d
max
⁡, d
max
⁡
′ that represent the largest in-degree for L
k
,
L
k
′, respectively. d
max
⁡
′ is random due to the randomicity of transmission delays. From Assumption 3, it is obvious that
(17)
τ
min
⁡
d
max
⁡
′
<
d
max
⁡
.
Then, with the second condition, it can be acquired that(18)
sup
⁡
(
τ
min
⁡
4
d
max
⁡
d
max
⁡
′
)
<
1
4
.
As a result,T
-
α
d
max
⁡
′
>
0. Besides, it is not difficult to find that 1
-
T
-
β
d
max
⁡
′
>
0 since τ
min
⁡
<
T. As a result, it can be concluded that if the conditions are satisfied, Lemma 16 is also fulfilled and the consensusability of the multiagent system with double integrator dynamics is proved.


## 3.2.2. With Communication Delays and Packet Losses

For second order system with packet losses, Assumption11 cannot hold and the Laplacian matrices L
k, L
k
′ discussed in the above section no longer have a spanning tree all the time. In this situation, Lemma 16 cannot directly be applied. Inspired by Qin et al. [17], a covariable can be introduced here with definition as
(19)
y
i
(
t
k
)
=
a
v
i
(
t
k
)
+
b
x
i
(
t
k
)
,
where a
,
b are constant parameters. It is easily derived that if x
(
t
k
) and y
(
t
k
) can reach consensus, the velocity of the system will also achieve consensus. So in the following discussion, the consensus problem of system states x
(
t
k
) and y
(
t
k
) is concerned. Besides, default control of agent i also needs to be set as u
i
0
′
=
-
c
v
i
(
t
k
), i
∈
{
1,2
,
…
,
n
}.As a result, the multiagent system can be transformed into(20)
[
x
(
t
k
+
1
)
y
(
t
k
+
1
)
]
=
[
(
1
-
b
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
T
a
(
1
-
c
T
)
I
n
-
β
a
L
k
(
c
b
T
-
b
2
T
a
(
1
-
c
T
)
)
I
n
-
(
α
-
b
β
a
)
L
k
′
(
b
T
a
(
1
-
c
T
)
+
1
-
c
T
)
I
n
-
β
a
L
k
′
]
[
x
(
t
k
)
y
(
t
k
)
]
.With proper choices of parametersα
,
β
,
a
,
b, and T, the system matrix can be a nonnegative stochastic matrix with positive diagonal elements. In fact, to ensure that the transfer matrix is stochastic, b
≡
1. Then if Assumption 13 holds, the system described as (20) can reach a consensus with similar proof as Theorem 14. However, because of the existence of default control input, the consensus value of system velocity is zero which is usually the case for rendezvous problem not for formation control or flocking. So in order to obtain the consensus for multiagent system without adding the control input u
i
0
′, in the subsequence of this paper, a different assumption about interaction topology needs to be made.Assumption 18.
The designed communication topology for the multiagent system is a directed spanning tree. Similarly, with Assumption13, this assumption essentially means that the union of digraphs within l periods is a directed spanning tree.Consider two agentsi, j and assume that there is a directed link from agent i to j. According to Assumption 13, there exist a positive integer g with 1
≤
g
≤
l such that the data transmission is successful during the period [
t
k
+
g
-
1
,
t
k
+
g
) and packets dropout during the previous g
-
1 periods. Define the delay during [
t
k
+
g
-
1
,
t
k
+
g
) as τ
i
j
(
t
k
g
) which satisfies Assumption 3. Adopt the controller gain as α
j
(
t
k
g
)
=
β
j
(
t
k
g
)
=
(
T
-
τ
i
j
(
t
k
g
)
)
/
4 and the following dynamics can be obtained for agents i and j: (21)
[
x
i
(
t
k
+
g
)
x
j
(
t
k
+
g
)
v
i
(
t
k
+
g
)
v
j
(
t
k
+
g
)
]
=
[
1
0
g
T
0
(
T
-
τ
i
j
(
t
k
g
)
)
4
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
0
0
1
0
1
2
-
1
2
1
2
(
1
+
(
g
-
1
)
T
)
1
2
(
1
-
(
g
-
1
)
T
)
]
×
[
x
i
(
t
k
)
x
j
(
t
k
)
v
i
(
t
k
)
v
j
(
t
k
)
]
.Define the states error between agentsi and j at time instants as t
k and t
k
+
g as follows:
(22)
ζ
i
j
(
d
+
1
)
=
x
j
(
t
k
+
g
)
-
x
i
(
t
k
+
g
)
,
ξ
i
j
(
d
+
1
)
=
v
j
(
t
k
+
g
)
-
v
i
(
t
k
+
g
)
,
ζ
i
j
(
d
)
=
x
j
(
t
k
)
-
x
i
(
t
k
)
,
ξ
i
j
(
d
)
=
v
j
(
t
k
)
-
v
i
(
t
k
)
,
where d represents the number of successful transmissions. Then the following equation is acquired denoting the error dynamics between agents i and j
:
(23)
[
ζ
i
j
(
d
+
1
)
ξ
i
j
(
d
+
1
)
]
=
[
(
1
-
(
T
-
τ
i
j
(
t
k
g
)
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
[
ζ
i
j
(
d
)
ξ
i
j
(
d
)
]
.According to the error dynamics depicted as above, the following lemma can be proposed.Theorem 19.
For multiagent system consisting of double integrator dynamics as in Table1, with Assumptions 13 and 18, the consensusability of the system can be guaranteed with packet losses and transmission delays as long as the discrete error dynamics as in (23) is stable.Proof.
Without loss of generality, set agenti as the root node of the directed spanning tree. Define N
i
0 as the set of agents that receive information from agent i. If the error dynamics as in (23) is stable, that is, lim
⁡
d
→
∞
ζ
i
j
(
d
)
=
0,  lim
⁡
d
→
∞
ξ
i
j
(
d
)
=
0. It is obvious that agents i and j can reach a consensus for any j
∈
N
i
0 with finite time periods since Assumption 18 holds.
Then there exist a positive numberm
j and a time instant t
m
j such that [
ζ
i
j
(
m
j
)
ξ
i
j
(
m
j
)
]
T
=
[
0
0
]
T for t
>
t
m
j. With definition of t
m
=
max
⁡
{
t
m
j
}
,
j
∈
N
i
0, it can be derived that when t
>
t
m, x
j
(
t
)
=
x
i
(
t
)
,
v
j
(
t
)
=
v
i
(
t
), for all j
∈
N
i
0 which means that the consensus has been reached between agents i and N
i
0. Since the discrete error dynamics is as in (23) set no restrictions on initial states of agents and the agents belonging to N
j
0 will reach consensus with agent j in a similar way. Finally, the whole multiagent system will reach a consensus.To be more illustrative, the process can be shown in Figure1. The error dynamics between different agents in the dash line circle can be presented as (23). The agents in the real line circle mean that the consensus has been reached among them.Figure 1
Consensus process of multiagent system under directed spanning tree.In the following, an algorithm to testify the Schur stability of discrete-time dynamics system as in (23) is proposed. Since all communication delay τ
i
j is random, the transfer matrix(24)
M
=
[
(
1
-
T
-
τ
i
j
(
t
k
g
)
4
)
(
g
T
-
T
-
τ
i
j
(
t
k
g
)
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]can be viewed as an interval matrix [
M
m
,
M
M
]
=
{
M
=
[
m
i
j
]
:
m
i
j
m
<
m
i
j
<
m
i
j
M
,
i
,
j
=
1,2
} for fixed g with the expressions of M
m and M
M as follows:
(25)
M
m
=
[
1
-
T
4
g
T
-
T
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
;
M
M
=
[
1
-
τ
min
⁡
4
g
T
-
τ
min
⁡
4
(
1
+
(
g
-
1
)
T
)
)
-
1
2
1
2
(
1
-
(
g
-
1
)
T
)
]
.The following lemma needs to be introduced concerning the stability of interval matrix.Lemma 20.
An interval matrix[
R
m
,
R
M
] is Schur stable if and only if there are finitely subinterval matrices [
R
i
m
,
R
i
M
]
⊂
[
R
m
,
R
M
], 1
≤
i
≤
k, such that
(26)
[
R
m
,
R
M
]
=
⋃
i
=
1
k
[
R
i
m
,
R
i
M
]
.
And for eachi, 1
≤
i
≤
k, [
R
i
m
,
R
i
M
] satisfies the following conditions.(1)
R
i
0 is Schur stable and there exists a positive definite matrix P
=
P
T satisfying
(27)
R
i
0
T
P
i
R
i
0
-
P
i
+
I
=
0
.
(2)
ϕ
(
Δ
R
i
)
<
[
ϕ
(
R
i
0
)
2
+
1
/
|
P
i
|
∞
]
1
/
2
-
ϕ
(
R
i
0
). ϕ
(
·
) is an operator ϕ
(
R
)
=
max
⁡
{
|
R
|
1
,
|
R
|
∞
} and the definitions of Δ
R
i and R
i
0 are as follows:
(28)
Δ
R
i
=
1
2
(
R
i
M
-
R
i
m
)
,
R
i
0
=
1
2
(
R
i
M
+
R
i
m
)
.
(3)
Subinterval matrices⋃
i
=
1
k
[
R
i
m
,
R
i
M
] are complete decomposition of interval matrix [
R
m
,
R
M
] which means that ∀
R
∈
[
R
m
,
R
M
], ∃
i
∈
[
1,2
,
…
,
k
] such that R
∈
[
R
i
m
,
R
i
M
].Proof.
See Wang et al. [30] and Liao et al. [31] for details.Consider the parameters in (23), according to Assumption 3 and τ
min
⁡ actually denotes the smallest processing time available for the embedded system. T is the sampling and transmitting period for the multiagent system and for acoustic communication system it also indicates the largest distance available between two linked agents since the relation Dis
<
v
c
(
T
-
τ
min
⁡
) has to be satisfied, where v
c is the acoustic velocity. Due to the physical meanings of τ
min
⁡, T, they usually are predetermined once the multiagent system structure is determined. As for g, according to Assumption 13 and the derivation of (23), g is a time varying positive integrator variable satisfying 1
≤
g
≤
l. So the following lemma is put forward.Lemma 21.
The system transfer matrix in (23) is Schur stable if, for every fixed g
∈
[
1,2
,
…
,
l
], [
M
m
,
M
M
] is Schur stable.Proof.
Define the interval matrix[
M
m
,
M
M
] as [
M
j
m
,
M
j
M
] when g
=
j, 1
≤
j
≤
l. If [
M
j
m
,
M
j
M
] is Schur stable, then there exist a finite number of subinterval matrices [
M
j
m
,
M
j
M
]
=
⋃
i
=
1
k
[
M
i
j
m
,
M
i
j
M
] satisfying conditions in Lemma 20. In addition, the system matrix in (23) can be completely decomposed as
(29)
[
M
m
,
M
M
]
=
⋃
g
=
1
l
[
M
j
m
,
M
j
M
]
.
Then it can be derived that(30)
[
M
m
,
M
M
]
=
{
⋃
i
=
1
k
[
M
i
1
m
,
M
i
1
M
]
}
∪
{
⋃
i
=
1
k
[
M
i
2
m
,
M
i
2
M
]
}
∪
⋯
∪
{
⋃
i
=
1
k
[
M
i
l
m
,
M
i
l
M
]
}
.
The above equation means that the system matrix can be decomposed into finite number of subinterval matrices that all satisfy the conditions in Lemma20. The matrix is Schur stable.Even though Lemmas20 and 21 have provided conditions to guarantee the Schur stability of the discrete interval system matrix, method to completely decompose an interval matrix is needed. Based on the definition of R
i
0 and Δ
R
i in (28), the interval matrix [
R
m
,
R
M
] can be presented as [
R
0
±
Δ
R
]. With this presentation, it is natural to adopt the decomposition as [
R
m
,
R
M
]
=
[
R
0
-
Δ
R
,
R
0
]
∪
[
R
0
,
R
0
+
Δ
R
]. However, the decomposition is not always complete. Denote the element of the interval matrix at ith row and jth column by [
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]. Then divide the interval into two subintervals as follows:
(31)
[
R
m
(
i
,
j
)
,
R
M
(
i
,
j
)
]
=
R
L
(
i
,
j
)
∪
R
H
(
i
,
j
)withR
L
(
i
,
j
) and R
H
(
i
,
j
) defined as
(32)
R
L
(
i
,
j
)
=
[
R
0
(
i
,
j
)
-
Δ
R
(
i
,
j
)
,
R
0
(
i
,
j
)
]
,
R
H
(
i
,
j
)
=
[
R
0
(
i
,
j
)
,
R
0
(
i
,
j
)
+
Δ
R
(
i
,
j
)
]IfR
m
,
R
M
∈
R
n
×
n, the interval matrix can be decomposed as follows:
(33)
[
R
m
,
R
M
]
=
⋃
k
=
1
2
n
×
n
R
inv
(
k
)
.Each element inR
inv
(
k
) at ith row and jth column will be either R
L
(
i
,
j
) or R
H
(
i
,
j
). Then, it is obvious that the decomposition is complete. Now, Algorithm 1 is proposed in pseudocode to testify the Schur stability of the interval matrix. If a limited number of subintervals can be obtained for each [
M
j
m
,
M
j
M
], 1
≤
j
≤
l that satisfy the Schur stability conditions in Lemma 20, the system matrix in (23) is stable according to Lemma 21. That is, the multiagent system consists of second order agent with communication delays and packet losses can reach a consensus.Algorithm 1:
Initialization of parameters
τ
min
⁡, T and l;
For
j
=
1: l
Test the Schur stability
(
[
M
j
m
,
M
j
M
]
)
{
If
[
M
j
m
,
M
j
M
]
is Schur stable
Break;
Else
If
M
j
o
is not Hurwitz stable
[
M
j
m
,
M
j
M
]
is not stable; break;
Else
Decompose
[
M
j
m
,
M
j
M
];
Test the Schur stability (each subinterval);
}
EndThrough Algorithm1, the consensusability of the multiagent system concerned can be testified. However, since the controller gain and the system parameters are predefined, no analytical solutions are provided by this method for multiagent system that could not reach consensus. Besides, the computational burden of the algorithm will increase exponentially with the order of agents. Therefore, in the next section, a theorem will be proposed to design the controller gain and solve the consensus problem of multiagent system with high-order integrator agents.


## 3.3. High-Order Integrator Agent

Assume that Assumption18 still holds; similar result can be obtained as in Theorem 19; that is, if the root agent i and agent j, j
∈
N
i
0, can reach consensus, the multiagent system can reach consensus. So for the high-order integrator dynamics introduced in Table 1, with communication delays, the discrete system dynamics for agent i and agent j can be presented as
(34)
X
i
(
t
k
+
1
)
=
e
A
T
X
i
(
t
k
)
,
X
j
(
t
k
+
1
)
=
e
A
T
X
j
(
t
k
)
+
∫
o
T
-
τ
i
j
(
t
k
)
e
A
t
d
t
·
B
K
(
X
i
(
t
k
)
-
X
j
(
t
k
)
)
with K
=
[
k
1
k
2
⋯
k
m
] as the controller gain to be designed; τ
i
j
(
t
k
) is the communication delay satisfying Assumption 3. Let the states error between agent i and agent j at time t
k
(35)
δ
(
t
k
)
=
X
i
(
t
k
)
-
X
j
(
t
k
)
.The error dynamics between two agents is(36)
δ
(
t
k
+
1
)
=
(
e
A
T
-
∫
o
T
-
τ
i
j
(
t
k
)
e
A
t
d
t
·
B
K
)
δ
(
t
k
)
.Considering packet losses and according to Assumption13, there exists an integer g
∈
[
1
,
…
,
l
] such that the error dynamics during the period [
t
k
,
t
k
+
g
) can be presented as
(37)
δ
(
t
k
+
g
)
=
e
(
g
-
1
)
A
T
(
e
A
T
-
∫
o
T
-
τ
i
j
(
t
k
g
)
e
A
t
d
t
·
B
K
)
δ
(
t
k
)
.Algorithm1 can still be applied to test the Schur stability of system matrix equation (36) and (37). Except for the computational complexity increases exponentially with the system order, the controller gain is also difficult to design comparing with second order multiagent system. So in order to circumvent those difficulties, the following lemmas are applied to achieve the controller gain.Lemma 22 (see [32]).
For discrete time interval system as in (38), M
∈
R
n
×
n
,
N
∈
R
n
×
p, the system is stabilizable if and only if there exist a matrix G
∈
R
p
×
n and a symmetric positive definite matrix H
∈
R
n
×
n and scalars λ
i
j
>
0,  i
,
j
=
1,2
,
…
,
n,  δ
i
j
>
0,  i
=
1,2
,
…
,
n,  j
=
1,2
,
…
,
p, satisfying (39). And the controller gain can be adopted as K
=
G
H
-
1. Consider
(38)
δ
(
d
+
1
)
=
[
M
min
⁡
,
M
max
⁡
]
δ
(
d
)
+
[
N
min
⁡
,
N
max
⁡
]
u
(
d
)
,
u
(
d
)
=
K
δ
(
d
)
,
(39)
[
-
H
H
M
o
T
+
G
N
o
T
H
d
G
d
M
0
H
+
N
0
G
-
H
+
Σ
0
0
H
d
T
0
-
Λ
G
d
T
0
-
Δ
]
<
0
,
where Σ
=
∑
i
,
j
=
1
n
λ
i
j
|
Δ
m
i
j
|
2
e
i
e
i
T
+
∑
i
=
1
n
∑
j
=
1
p
δ
i
j
|
Δ
n
i
j
|
2
e
i
e
i
T, e
i is a column vector with ith element being 1. And
(40)
H
d
=
[
H
,
…
,
H
]
︸
n
,
G
d
=
[
G
T
,
…
,
G
T
]
︸
n
,
Λ
=
diag
⁡
{
λ
11
,
λ
12
,
…
,
λ
1
n
,
…
,
λ
n
1
,
λ
n
2
,
…
,
λ
n
n
}
,
Δ
=
diag
⁡
{
δ
11
,
δ
12
,
…
,
δ
1
p
,
…
,
δ
n
1
,
δ
n
2
,
…
,
δ
n
p
}
.Lemma 23.
The interval system matrices[
M
min
⁡
,
M
max
⁡
] and [
N
min
⁡
,
N
max
⁡
] are stabilizable if there are a finite number of subintervals [
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
], 1
≤
i
≤
k such that, for each i
∈
{
1,2
,
…
,
k
}, the system matrices [
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
] are stabilizable. And the interval system is completely decomposed which means that, at any time instant t, if N
(
t
)
∈
[
N
min
⁡
i
,
N
max
⁡
i
], then M
(
t
)
∈
[
M
min
⁡
i
,
M
max
⁡
i
], 1
≤
i
≤
k. And the complete decomposition can be denoted by
(41)
[
M
min
⁡
,
M
max
⁡
]
=
⋃
i
=
1
k
[
M
min
⁡
i
,
M
max
⁡
i
]
,
[
N
min
⁡
,
N
max
⁡
]
=
⋃
i
=
1
k
[
N
min
⁡
i
,
N
max
⁡
i
]
.Proof.
Since the system matrices[
M
min
⁡
i
,
M
max
⁡
i
], [
N
min
⁡
i
,
N
max
⁡
i
] are stabilizable, suppose that the controller gain is denoted by K; then, it can be derived that [
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K is Schur stable. Because the interval system is completely decomposed, the following decomposition is also complete
(42)
[
M
min
⁡
,
M
max
⁡
]
+
[
N
min
⁡
,
N
max
⁡
]
K
=
⋃
i
=
1
k
(
[
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K
)
.
Then according to Lemma21, the Schur stability of [
M
min
⁡
i
,
M
max
⁡
i
]
+
[
N
min
⁡
i
,
N
max
⁡
i
]
K
,
i
∈
{
1,2
,
…
,
k
} indicated Schur stability of the multiagent system.Comparing (36) with (37), it can be concluded that (36) is the special case of (37) when g
=
1. Actually, the interval matrices in (37) are piecewise interval, and the system can be completely decomposed into l subinterval systems easily. The subinterval systems can be presented as follows:
(43)
δ
(
t
k
+
g
)
=
e
g
A
T
δ
(
t
k
)
-
e
(
g
-
1
)
A
T
∫
o
T
-
τ
i
j
(
t
k
g
)
e
A
t
B
d
t
·
u
(
t
k
)
=
M
g
δ
(
t
k
)
+
N
g
u
(
t
k
)
for
g
∈
{
1,2
,
…
,
l
}
.Theorem 24.
For multiagent system consisting of high order agents, under Assumptions13 and 18, the consensusability of the system can be guaranteed with transmission delays and packet losses if there exists a controller gain K such that the conditions in Lemma 22 can be satisfied for each M
g
+
N
g
K, g
∈
{
1,2
,
…
,
l
}.Proof.
If the conditions in Lemma22 are satisfied, M
g
+
N
g
K is Schur stable. From (43), the interval system in (37) can be completely decomposed by M
g and N
g, g
∈
{
1,2
,
…
,
l
}. Then according to Lemma 23, the theorem is established.In fact, the existence of controller gainK is important in the above lemma. According to (39) in Lemma 22, matrix K can be obtained by solving the LMI with matlab. In order to guarantee the conditions in Lemma 23, l LMIs should be solved simultaneously to calculate the feedback gain K. Besides, it should be noticed that Theorem 24 is a general solution for controller gain of multiagent system and can be applied to all kinds of agent dynamics including single integrator, second order integrator, and general linear system.


## 4. Simulations

In this section, simulation results will be presented to demonstrate the theoretical results in Section3. A multiagent system consists of five agents with the designed interaction topology as in Figure 2 that is concerned. The success ratio p in Assumption 13 is set as 0.8 according to the property of ordinary acoustic communication equipment; if μ is chosen to be 0.999, then l can be set as 5 which means that the transmission will be successful at least one time during five periods. τ
min
⁡ is set to be 0.1, which is long enough for system to calculate the system inputs. Sampling and transmitting period T
=
0.5. With all above initialization, single integrator, second order, and high-order agents are discussed separately and consensusability for every typical multiagent system is testified with packet losses and communication delays.Figure 2
Interaction topology.


### 4.1. Single Integrator Agent

In this case, the initial state of each agent in the multiagent system is chosen randomly from 0 to 50,α
=
2. Simulation result is shown in Figure 3. It can be concluded that, for single integrator system, the position of each agent will converge to the state of agent 1 and the consensus of the system will be reached fast.Figure 3
Consensus of single integrator system.


### 4.2. Second Order Agent

In this case, we need to test Schur stability of the error dynamics with Algorithm1; it can be calculated that, with 582 subintervals, the conditions in Lemma 20 can be satisfied for every subinterval. Similar to Case 1, the initial values for position and velocity are randomly adopted within [
0,50
] and [
0,10
], respectively. The simulation results are shown in Figures 4 and 5. It can be seen that, during some time intervals at the beginning, the difference of states may increase, especially for velocity of the agent, but the consensus will be reached with enough time. It is also worth noticing that the sampling and transmitting period T adopted in this case cannot satisfy the condition in Theorem 17; however, the consensus can still be guaranteed which indicated that the condition from stochastic matrix theory is more conservative if Assumption 18 holds.Figure 4
Consensus of position for second order system.Figure 5
Consensus of velocity for second order system.


### 4.3. High-Order Agent

Considering the third order integrator agent, corresponding structure of matricesA and B can be obtained through Table 1. Then according to Lemmas 22 and 23, the controller gain K can be calculated through solving the 5 LMIs with matlab. It can be found that K
=
[
2.36
2.57
3.59
] is a proper solution and the simulations are carried out with results presented in Figures 6, 7, and 8. Even though it takes more time to reach the consensus for the multiagent system, with the proposed controller structure and controller gain, the consensusability is guaranteed. In addition, the initial states for position, velocity, and acceleration are randomly chosen from [
0,50
], [
0,10
], and [
0,3
].Figure 6
Consensus of position for high-order system.Figure 7
Consensus of velocity for high-order system.Figure 8
Consensus of acceleration for high-order system.


## 4.1. Single Integrator Agent

In this case, the initial state of each agent in the multiagent system is chosen randomly from 0 to 50,α
=
2. Simulation result is shown in Figure 3. It can be concluded that, for single integrator system, the position of each agent will converge to the state of agent 1 and the consensus of the system will be reached fast.Figure 3
Consensus of single integrator system.


## 4.2. Second Order Agent

In this case, we need to test Schur stability of the error dynamics with Algorithm1; it can be calculated that, with 582 subintervals, the conditions in Lemma 20 can be satisfied for every subinterval. Similar to Case 1, the initial values for position and velocity are randomly adopted within [
0,50
] and [
0,10
], respectively. The simulation results are shown in Figures 4 and 5. It can be seen that, during some time intervals at the beginning, the difference of states may increase, especially for velocity of the agent, but the consensus will be reached with enough time. It is also worth noticing that the sampling and transmitting period T adopted in this case cannot satisfy the condition in Theorem 17; however, the consensus can still be guaranteed which indicated that the condition from stochastic matrix theory is more conservative if Assumption 18 holds.Figure 4
Consensus of position for second order system.Figure 5
Consensus of velocity for second order system.


## 4.3. High-Order Agent

Considering the third order integrator agent, corresponding structure of matricesA and B can be obtained through Table 1. Then according to Lemmas 22 and 23, the controller gain K can be calculated through solving the 5 LMIs with matlab. It can be found that K
=
[
2.36
2.57
3.59
] is a proper solution and the simulations are carried out with results presented in Figures 6, 7, and 8. Even though it takes more time to reach the consensus for the multiagent system, with the proposed controller structure and controller gain, the consensusability is guaranteed. In addition, the initial states for position, velocity, and acceleration are randomly chosen from [
0,50
], [
0,10
], and [
0,3
].Figure 6
Consensus of position for high-order system.Figure 7
Consensus of velocity for high-order system.Figure 8
Consensus of acceleration for high-order system.


## 5. Conclusions

In this paper, the consensus problem of multiagent system with packet losses and communication delays is discussed. A novel control protocol that depends on periodic sampling and transmitting information is proposed to make it more convenient for implementation. Then, sufficient conditions for consensusability of multiagent systems consist of single integrator, second order, and high-order agents that are established, respectively, according to stochastic matrix theory and interval matrix theory. Finally, simulations are carried out to verify the theoretical results obtained. However, to reach the consensus for second and high-order systems with packet losses and communication delays, the directed communication topology is limited to a directed spanning tree. Even though this kind of structure has its own advantages in real-world applications, being convenient and economical, for example, it also has some flaws in modeling the system with massive agents such as flock and fish school. Therefore, in the follow-up study of this research, the directed topology will not be limited to a directed spanning tree in order to make the whole system more distributive.



---

*Source: 159609-2014-04-07.xml*