# Consensus of Second-Order Multiagent Systems with Fixed Topology and Time-Delay

Authors: Xue Li; Huai Wu; Yikang Yang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We are concerned with the consensus problems for networks of second-order agents, where each agent can only access the relative position information from its neighbours. We aim to find the largest tolerable input delay such that the system consensus can be reached. We introduce a protocol with time-delay and fixed topology. A sufficient and necessary condition is given to guarantee the consensus. By using eigenvector-eigenvalue method and frequency domain method, it is proved that the largest tolerable time-delay is only related to the eigenvalues of the graph Laplacian. And simulation results are also provided to demonstrate the effectiveness of our theoretical results.


---

## Body

## 1. Introduction

In the last few years, consensus problems have attracted a great deal of attention owing to their enormous potential applications including formation control, attitude alignment of clusters of satellites, and flocking. And a large number of results have been obtained for consensus problems of multiagent systems [1–8]. For example, to solve the consensus problems with state constraints, [2] proposed a ground-breaking consensus algorithm with a nonlinear projection operator and gave corresponding convergence analysis on dynamically changing balanced graphs whose adjacency matrices are doubly stochastic. And in [5], Ren and Beard presented some second-order consensus algorithms to guarantee state consensus of systems subjected to the saturation of the actuator and limited available information.In reality, due to packet loss and asynchronous clocks of the agents, there unavoidably exist communication delays in the exchange of the agent states [9–16]. Consensus problems with communication delays for the discrete-time systems have attracted great attention in the past decades, and also for the continuous-time multiagent systems. In [9], Lin and Ren investigated a constrained consensus problem of discrete-time multiagent systems in dynamically changing unbalanced networks in the presence of communication delays where each agent is required to stay in a closed convex set. In [10], Lin and Jia studied the linear consensus problems for the discrete-time system without any constraints on the agents states in the presence of communication delays and showed that the communication delays can be arbitrarily bounded. Reference [11] investigated consensus problems of a class of second-order continuous-time multiagent systems with time-delay and jointly connected topologies. There are also many methods to prove that the consensus for the giving protocols can be achieved. In [15], by using Lyapunov function method and LaSalle’s invariance principle, the heterogeneous multiagent system can solve the consensus problems when the communication topologies are undirected connected graphs and leader-following networks, respectively. In [16], by the way of solving the eigenvector-eigenvalue and using frequency domain method, Lin et al. obtained a sufficient and necessary condition to guarantee the consensus for directed networks with fixed topology. In [17], Hong et al. studied a leader-follower scheme with jointly connected topologies by a Lyapunov-based approach and related space decomposition technique.In this paper, we investigate the consensus problems for networks of second-order agents with time-delay and fixed topology using the method of  [16], where each agent can only access the relative position information from its neighbours. Compared with [16], the problem studied in this paper is more complicated, for second-order multiagent systems are studied which is much more complicated than the first-order ones due to the coupling of the position and velocity states.


## 2. Graph Theory

At first, we introduce some preliminary knowledge of graph theory for the following analysis (referring to [18]). Let G
(
V
,
ɛ
,
A
) be an undirected graph of order n, where V
=
{
s
1
,
…
,
s
n
} is the set of nodes, ɛ
⊆
V
×
V is the set of edges, and A
=
[
a
i
j
] is a weighted adjacency matrix. The node indexes belong to a finite index set I
=
{
1,2
,
…
,
n
}. An edge of G is denoted by e
i
j
=
(
s
i
,
s
j
). The adjacency matrix is defined as a
i
i
=
0 and a
i
j
≥
0; a
i
j
=
a
j
i
>
0 if and only if e
i
j
∈
ɛ. Since the graph is considered undirected, it means that once e
i
j
∈
ɛ, then e
j
i
∈
ɛ. Thus, the adjacency matrix A is a symmetric nonnegative matrix. The set of neighbours of node s
i is denoted by N
i
=
{
s
j
∈
V
:
s
i
,
s
j
∈
ɛ
}. The in-degree and out-degree of node s
i are defined, respectively, as d
in
(
s
i
)
=
∑
j
=
1
n
‍
a
j
i and d
o
(
s
i
)
=
∑
j
=
1
n
‍
a
i
j. Then, the Laplacian corresponding to the undirected graph is defined as L
=
[
l
i
j
], where l
i
i
=
d
o
(
s
i
) and l
i
j
=
-
a
i
j, i
≠
j. Obviously, the Laplacian of any undirected graph is symmetric. A path is a sequence of ordered edges of the form (
s
i
1
,
s
i
2
)
,
s
i
2
,
s
i
3
,
…, where i
j
∈
I and s
i
j
∈
V. If there is a path from every node to every other node, the graph is said to be connected.Lemma 1 (see [18]).
If the undirected graphG is connected, then the Laplacian L of G has the following properties:(a)
Zero is one eigenvalue ofL, and 1
n is the corresponding eigenvector; that is, L
1
n
=
0.
(b)
The remainingn
-
1 eigenvalues are all positive and real.


## 3. Model

Suppose that the multiagent system under consideration consists ofn agents. Each agent is regarded as a node in an undirected graph G. Each edge (
s
j
,
s
i
)
∈
ɛ
(
G
) corresponds to an available information channel between the agent s
i and the agent s
j at time t. Moreover, each agent updates its current states based upon the information received from its neighbours. Suppose the ith agent (i
∈
I) has the dynamics as follows:(1)
x
˙
i
=
v
i
,
v
˙
i
=
k
0
v
i
+
u
iwith the initial conditions x
i
(
s
)
=
φ
i
(
s
) and v
i
(
s
)
=
ϕ
i
s
(
s
∈
(
-
∞
,
0
]
), where x
i
t
∈
R is the position state, v
i
(
t
)
∈
R is the velocity state, k
0 is a scalar, u
i
(
t
)
∈
R is the control input, and φ
i
(
s
), ϕ
i
s
∈
C
-
∞
,
0
,
R satisfy (1) with u
i
(
s
)
=
0
(
s
∈
(
-
∞
,
0
]
). We say the protocol u
i
(
t
) asymptotically solves the consensus problem, that is, the agreement of the position states, if and only if the states of agents satisfy(2)
lim
t
→
∞
⁡
x
i
t
-
x
j
t
=
0
,
lim
t
→
∞
⁡
v
i
t
-
v
j
t
=
0for all i, j
∈
I.We consider the system with fixed topology and time-delay. In this paper, we are expected to calculate the largest tolerable time-delay. Using the following consensus protocol and considering the communication time-delays are the same, we can get(3)
p
˙
i
=
-
γ
p
i
-
∑
s
j
∈
N
i
t
a
i
j
x
j
t
-
τ
-
x
i
t
-
τ
,
x
˙
i
=
v
i
,
v
˙
i
=
k
0
v
i
+
k
1
∑
s
j
∈
N
i
t
a
i
j
x
j
t
-
τ
-
x
i
t
-
τ
+
p
i
, where k
1
>
0, γ
>
0, p
i
(
t
) is an auxiliary variable with p
i
(
0
)
=
0, and τ denotes the communication time-delay.Here, the proposed protocol only uses the relative position information. The variablep
i
(
t
) is included to describe the effects of relative velocity and it can be seen as an estimation of ∑
s
j
∈
N
i
(
t
)
‍
a
i
j
[
v
j
(
t
-
τ
)
-
v
i
(
t
-
τ
)
].Letξ
=
[
x
1
,
v
1
,
p
1
,
…
,
x
n
,
v
n
,
p
n
]
T, A
=
0
1
0
0
k
0
1
0
0
-
γ, and B
=
0
0
0
k
1
0
0
-
1
0
0Using protocol (3), the network dynamics is(4)
ξ
˙
=
I
n
⊗
A
ξ
t
-
L
⊗
B
ξ
t
-
τ
.


## 4. Main Results

Lemma 2.
Letα
(
t
)
=
(
1
/
n
)
∑
i
=
1
n
‍
x
i
(
0
)
+
∫
0
t
‍
β
(
s
)
d
s, β
(
t
)
=
(
1
/
n
)
∑
i
=
1
n
‍
v
i
(
0
)
e
k
0
t, and δ
(
t
)
=
ξ
(
t
)
-
1
n
⊗
α
β
0
T. Then (
1
n
T
⊗
I
3
)
δ
(
t
)
=
0. And system (4) is equivalent to(5)
δ
˙
t
=
I
n
⊗
A
δ
t
-
L
⊗
B
δ
t
-
τ
.Proof.
SinceG is undirected, from (3) we can get ∑
i
=
1
n
‍
p
˙
i
(
t
)
=
-
γ
∑
i
=
1
n
‍
p
i
(
t
), which implies ∑
i
=
1
n
‍
p
i
(
t
)
=
e
-
γ
t
∑
i
=
1
n
‍
p
i
(
0
)
=
0. So we can see that (
1
/
n
)
∑
i
=
1
n
‍
v
i
(
t
)
=
e
k
0
t
(
1
/
n
)
∑
i
=
1
n
‍
v
i
(
0
)
=
β
(
t
). Thus, (
1
/
n
)
∑
i
=
1
n
‍
x
i
(
t
)
=
(
1
/
n
)
∑
i
=
1
n
‍
x
i
(
0
)
+
∫
0
t
‍
β
(
s
)
d
s
=
α
(
t
). Evidently, (
1
n
T
⊗
I
3
)
δ
(
t
)
=
0. By simple computations, system (4) is equivalent to system (5).Lemma 3 (see [16]).
Assume the communication topologyG is connected. For an undirected network of agents with fixed topology and fixed time-delay, the following statements hold.
Denote the nonzero eigenvalues ofL by λ
2
,
λ
3
,
…
,
λ
n; then there exists an orthogonal matrix W satisfying(6)
Λ
=
W
T
L
W
=
diag
⁡
0
,
λ
2
,
…
,
λ
n
. And system (4) is equivalent to(7)
δ
¯
˙
t
=
I
n
-
1
⊗
A
δ
¯
t
-
Λ
¯
⊗
B
δ
¯
t
-
τ
,where(8)
W
T
⊗
I
3
δ
t
=
0
0
0
δ
¯
T
t
T
,
Λ
¯
=
diag
⁡
λ
2
,
λ
3
,
…
,
λ
n
.Lemma 4.
Consider a network of second-order agents with a fixed topologyG that is connected. Given the protocol (3) when τ
=
0, the following statements hold:(a)
Fork
0
≤
0, all agents asymptotically reach consensus if and only if γ
k
1
>
1.
(b)
Fork
0
>
0, all agents asymptotically reach consensus if and only if γ
>
k
0, k
1
λ
m
i
n
>
k
0
γ, γ
k
1
>
1, and k
0
(
k
0
γ
-
k
1
λ
m
i
n
-
γ
2
)
+
λ
m
i
n
>
0.Lemma 5.
Consider the equation(9)
a
x
3
+
b
x
2
+
c
x
+
d
=
0
,where a
>
0, b
>
0, c
<
0, d
<
0, and a, b, c, d
∈
R. Then (9) has only one positive real root and another two roots located on the open left-half-plane (LHP).Proof.
For (9), we assume its roots are x
1, x
2, and x
3. So, by the theory of Vieta, we can obtain x
1
+
x
2
+
x
3
=
-
b
/
a
<
0, x
1
x
2
x
3
=
-
d
/
a
>
0. Thus (9) has only one positive real root and another two roots located on the open LHP.Theorem 6.
Assume the communication topologyG is undirected and connected. Then protocol (3) globally asymptotically solves the consensus problem if and only if τ
<
τ
∗ with τ
∗ given by(10)
τ
∗
=
min
i
=
2,3
,
…
,
n
⁡
φ
i
,
φ
i
=
arcsin
⁡
μ
i
γ
-
k
0
/
λ
i
μ
i
k
1
2
+
γ
k
1
-
1
2
-
arcsin
⁡
γ
k
1
-
1
/
μ
i
k
1
2
+
γ
k
1
-
1
2
μ
i
,where λ
i is the eigenvalue of L and μ
i is the positive root of the following equation:(11)
μ
3
+
μ
2
γ
2
+
k
0
2
+
μ
γ
2
k
0
2
-
λ
i
2
k
1
2
-
λ
i
2
γ
k
1
-
1
2
=
0
.Proof.
From Lemma3, linear system (7) is equivalent to (4). We can analyze system (7) instead of (4). Using Laplace transform, we can get s
X
(
s
)
-
X
(
0
)
=
(
I
n
-
1
⊗
A
)
X
(
s
)
-
(
Λ
¯
⊗
B
)
X
(
s
)
e
-
τ
s. By simply calculating, it is easy to see that (12)
X
s
=
s
I
n
-
1
-
I
n
-
1
⊗
A
+
Λ
¯
⊗
B
·
e
-
τ
s
-
1
X
0
. Define Y
τ
(
s
)
=
s
I
n
-
1
-
I
n
-
1
⊗
A
+
Λ
¯
⊗
B
·
e
-
τ
s. Calculating the determinant of Y
τ
(
s
) yields(13)
det
⁡
Y
τ
s
=
∏
i
=
2
n
s
3
+
s
2
γ
-
k
0
+
s
λ
i
k
1
e
-
τ
s
-
γ
k
0
+
γ
λ
i
k
1
e
-
τ
s
-
λ
i
e
-
τ
s
. From (13), all the roots of Y
τ
(
s
) are on the LHP if and only if the roots of(14)
s
3
+
s
2
γ
-
k
0
+
s
λ
i
k
1
e
-
τ
s
-
γ
k
0
+
γ
λ
i
k
1
e
-
τ
s
-
λ
i
e
-
τ
s
=
0are all located on the open LHP. Then, we compute the smallest value of the time-delay that guarantees that Y
τ
(
s
) has a root on the imaginary axis. Set s
=
j
w in (14); we get(15)
-
w
2
γ
-
k
0
+
w
λ
i
k
1
sin
⁡
w
τ
+
γ
k
1
-
1
λ
i
cos
⁡
w
τ
=
0
,
(16)
-
w
3
+
w
λ
i
k
1
cos
⁡
w
τ
-
w
γ
k
0
-
γ
k
1
-
1
λ
i
sin
⁡
w
τ
=
0
.From Lemma 4, we can easily get that, without communication delay, all agents asymptotically reach consensus if and only if γ
>
k
0, γ
k
1
>
1, k
1
λ
m
i
n
>
k
0
γ, and k
0
(
k
0
γ
-
k
1
λ
m
i
n
-
γ
2
)
+
λ
m
i
n
>
0. There we assume w
≥
0. Set s
i
n
(
θ
)
=
γ
k
1
-
1
/
(
w
k
1
)
2
+
(
γ
k
1
-
1
)
2, θ
∈
[
0
,
π
/
2
); then c
o
s
(
θ
)
=
w
k
1
/
(
w
k
1
)
2
+
(
γ
k
1
-
1
)
2. From (15) we get(17)
w
k
1
sin
⁡
w
τ
w
k
1
2
+
γ
k
1
-
1
2
+
γ
k
1
-
1
c
o
s
w
τ
w
k
1
2
+
γ
k
1
-
1
2
=
w
2
γ
-
k
0
λ
i
w
k
1
2
+
γ
k
1
-
1
2
. By simplifying we obtain(18)
sin
⁡
θ
+
w
τ
=
w
2
γ
-
k
0
λ
i
w
k
1
2
+
γ
k
1
-
1
2
. From (16) we get(19)
w
k
1
cos
⁡
w
τ
w
k
1
2
+
γ
k
1
-
1
2
-
γ
k
1
-
1
sin
⁡
w
τ
w
k
1
2
+
γ
k
1
-
1
2
=
w
3
+
w
γ
k
0
λ
i
w
k
1
2
+
γ
k
1
-
1
2
. By simplifying we obtain(20)
cos
⁡
θ
+
w
τ
=
w
3
+
w
γ
k
0
λ
i
w
k
1
2
+
γ
k
1
-
1
2
. Note that s
i
n
2
(
θ
+
w
τ
)
+
c
o
s
2
(
θ
+
w
τ
)
=
1; we get (21)
w
4
γ
-
k
0
2
+
w
2
w
2
+
γ
k
0
2
=
λ
i
2
w
k
1
2
+
γ
k
1
-
1
2
. Thus (22)
w
6
+
w
4
γ
2
+
k
0
2
+
w
2
γ
2
k
0
2
-
λ
i
2
k
1
2
-
λ
i
2
γ
k
1
-
1
2
=
0
. Set x
=
w
2, so x follows that(23)
x
3
+
x
2
γ
2
+
k
0
2
+
x
γ
2
k
0
2
-
λ
i
2
k
1
2
-
λ
i
2
γ
k
1
-
1
2
=
0
. Thus, from Lemma 5, (23) has only one positive real root μ
i and another two roots located on the open LHP.
Now we prove thatμ
i
(
γ
-
k
0
)
>
λ
i
(
γ
k
1
-
1
).
SetH
(
x
)
=
x
3
+
x
2
γ
2
+
k
0
2
+
x
(
γ
2
k
0
2
-
λ
i
2
k
1
2
)
-
λ
i
2
(
γ
k
1
-
1
)
2; then (24)
H
λ
i
γ
k
1
-
1
γ
-
k
0
=
λ
i
3
γ
k
1
-
1
3
γ
-
k
0
3
+
λ
i
2
γ
k
1
-
1
2
γ
2
+
k
0
2
γ
-
k
0
2
+
λ
i
γ
k
1
-
1
γ
2
k
0
2
-
λ
i
2
k
1
2
γ
-
k
0
-
λ
i
2
γ
k
1
-
1
2
. By simply calculating, it is easy to see that H
(
λ
i
(
γ
k
1
-
1
)
/
γ
-
k
0
)
<
0 is equivalent to F
(
λ
i
)
<
0, where F
(
λ
i
) is defined by the following statement: (25)
F
λ
i
=
λ
i
2
2
γ
k
0
k
1
2
-
2
γ
k
1
+
1
-
k
0
2
k
1
2
+
2
λ
i
γ
k
0
γ
2
k
1
-
γ
k
0
k
1
-
γ
+
k
0
+
γ
2
k
0
2
γ
-
k
0
2
. For 2
γ
k
0
k
1
2
-
2
γ
k
1
+
1
-
k
0
2
k
1
2
=
(
1
-
k
0
k
1
)
(
1
+
k
0
k
1
)
-
2
γ
k
1
(
1
-
k
0
k
1
)
=
(
1
-
k
0
k
1
)
(
1
+
k
0
k
1
-
2
γ
k
1
), by Lemma 4 we can see γ
>
k
0, γ
k
1
>
1, and k
0
k
1
<
1, so 1
+
k
0
k
1
-
2
γ
k
1
<
1
+
γ
k
1
-
2
γ
k
1
=
1
-
γ
k
1
<
0. Considering the equation λ
i
2
(
2
γ
k
0
k
1
2
-
2
γ
k
1
+
1
-
k
0
2
k
1
2
)
+
2
λ
i
γ
k
0
(
γ
2
k
1
-
γ
k
0
k
1
-
γ
+
k
0
)
+
γ
2
k
0
2
(
γ
-
k
0
)
2
=
0, its symmetric axis is (26)
λ
i
=
-
2
γ
k
0
γ
2
k
1
-
γ
k
0
k
1
-
γ
+
k
0
2
γ
k
0
k
1
2
-
2
γ
k
1
+
1
-
k
0
2
k
1
2
=
-
k
0
γ
k
1
-
1
γ
2
-
k
0
γ
1
-
k
0
k
1
1
+
k
0
k
1
-
2
γ
k
1
.For γ
k
1
-
1
/
2
γ
k
1
-
k
0
k
1
-
1
<
γ
k
1
-
1
/
γ
k
1
-
1
=
1, it can be seen that -
k
0
(
γ
k
1
-
1
)
(
γ
2
-
k
0
γ
)
/
(
1
-
k
0
k
1
)
(
1
+
k
0
k
1
-
2
γ
k
1
)
<
k
0
(
γ
2
-
k
0
γ
)
/
1
-
k
0
k
1. By Lemma 4, λ
m
i
n
>
k
0
(
γ
2
-
k
0
γ
)
/
1
-
k
0
k
1. So for all λ
i
≥
λ
m
i
n
>
k
0
(
γ
2
-
k
0
γ
)
/
1
-
k
0
k
1, λ
i is on the right side of the symmetry axis, for(27)
F
k
0
γ
2
-
k
0
γ
1
-
k
0
k
1
=
γ
2
k
0
2
γ
-
k
0
2
1
-
k
0
k
1
2
1
-
k
0
k
1
1
+
k
0
k
1
-
2
γ
k
1
+
2
γ
2
k
0
2
γ
-
k
0
2
1
-
k
0
k
1
γ
k
1
-
1
+
γ
2
k
0
2
γ
-
k
0
2
. By simplifying, we get(28)
F
k
0
γ
2
-
k
0
γ
1
-
k
0
k
1
=
γ
2
k
0
2
γ
-
k
0
2
1
+
k
0
k
1
-
2
γ
k
1
+
2
γ
k
1
-
1
+
1
-
k
0
k
1
1
-
k
0
k
1
=
0
. Considering that 1
+
k
0
k
1
-
2
γ
k
1
<
0 and for all λ
i
≥
λ
m
i
n
>
k
0
(
γ
2
-
k
0
γ
)
/
1
-
k
0
k
1, λ
i is on the right side of the symmetry axis, so for all λ
i
>
k
0
(
γ
2
-
k
0
γ
)
/
1
-
k
0
k
1, there must be F
(
λ
i
)
<
0, so H
(
λ
i
(
γ
k
1
-
1
)
/
γ
-
k
0
)
<
0. The positive real root μ
i of (23) satisfies μ
i
>
λ
i
(
γ
k
1
-
1
)
/
γ
-
k
0. Thus, we get (29)
arcsin
⁡
μ
i
γ
-
k
0
λ
i
μ
i
k
1
2
+
γ
k
1
-
1
2
>
arcsin
⁡
γ
k
1
-
1
μ
i
k
1
2
+
γ
k
1
-
1
2
.Then, the smallest τ
∗ satisfies(30)
τ
∗
=
min
i
=
2,3
,
…
,
n
⁡
φ
i
,
φ
i
=
arcsin
⁡
μ
i
γ
-
k
0
/
λ
i
μ
i
k
1
2
+
γ
k
1
-
1
2
-
arcsin
⁡
γ
k
1
-
1
/
μ
i
k
1
2
+
γ
k
1
-
1
2
μ
i
. Using the same method, when w
<
0, we can also get (31)
τ
∗
=
min
i
=
2,3
,
…
,
n
⁡
φ
i
,
φ
i
=
arcsin
⁡
μ
i
γ
-
k
0
/
λ
i
μ
i
k
1
2
+
γ
k
1
-
1
2
-
arcsin
⁡
γ
k
1
-
1
/
μ
i
k
1
2
+
γ
k
1
-
1
2
μ
i
.Due to the continuous dependence of the roots of (14) in τ, for all τ
∈
(
0
,
τ
∗
), all the roots of (14) are on the open LHP and hence the poles of Y
τ
-
1
(
s
) are all stable.


## 5. Simulation Results

In this section, by presenting some numerical simulations, we will test and verify the theoretical results obtained in the previous section. These simulations are performed with four agents, whose initial conditions are set randomly. We use the fixed topology which is showed in Figure1. There we set γ
=
1, k
0
=
0.1, and k
1
=
1.1; by simple calculation, we have τ
∗
=
0.22. Figure 2 shows velocity trajectories for τ
<
τ
∗ and τ
=
τ
∗, respectively. Figure 3 shows position trajectories for τ
<
τ
∗ and τ
=
τ
∗, respectively. Clearly, the consensus can be achieved when τ
<
τ
∗ while synchronous oscillations are illustrated when τ
=
τ
∗.Figure 1
Topology.Figure 2
(a, b) Velocity-time.
(a)
(b)Figure 3
(a, b) Position-time.
(a)
(b)


## 6. Conclusion

In this paper, we investigate the consensus problem for networks of second-order agents with fixed topology and time-delay and without relative velocity measurement. For undirected networks with fixed topology and time-delay, a sufficient and necessary condition is also given by a frequency domain analysis that established a direct relation between the largest tolerable time-delay and the eigenvalues of the graph Laplacian. Simulation results are provided to demonstrate the effectiveness of our theoretical results.



---

*Source: 138276-2015-11-26.xml*