# Fast Consensus Tracking of Multiagent Systems with Diverse Communication Delays and Input Delays

Authors: Chun-xi Yang; Wei-xing Hong; Ling-yun Huang; Hua Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The consensus tracking problem for discrete-time multiagent systems with input and communication delays is studied. A sufficient condition is obtained over a directed graph based on the frequency-domain analysis. Furthermore, a fast decentralized consensus tracking conditions based on
incrementPID algorithm are discussed for improving convergence speed of the multiagent systems. Based on this result, genetic algorithm is introduced to construct increment PID based on genetic algorithm for obtaining optimization consensus tracking performance. Finally, a numerable example is given to compare convergence speed of three tracking algorithms in the same condition. Simulation results show the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

As an effective method to solve decentralized multiagent cooperative control which is widely applied into many fields such as flocking [1, 2], formation control [3, 4], and unmanned air vehicles [5], consensus algorithms designing of multiagent systems has attracted great attention in recent years. A key task for consensus algorithms is to achieve a global common behavior through designing a distributed protocol based on local information. Reference [6] proposed a simple model for phase transition of self-driven of the model. A simple consensus protocol to solve the average consensus problem was discussed in [7]. Furthermore, two survey papers which introduce the basic concepts of consensus of multiagent systems, the methods of convergence, and performance analysis for the protocols and recent development can be seen in [8, 9]. In real applications, when local information data travel along channels in a multiagent network, a communication delay exists due to the physical characteristics of the medium transmitting the information. And at the same time, each agent also needs computing time to process its information. As a result, time-delay problem including communication delays and computing delays (also called input delays) is not avoided in designing consensus algorithms. Reference [10] discusses the consensus problem for multiagent systems with input and communication delays based on the frequency-domain in discrete-time formulation and a conclusion where the consensus condition is dependent on input delays but independent of communication delays is obtained.Convergence rate or speed is an important performance index in the analysis of consensus problems. For example, sensors need to reach fast consensus on the estimates between sensor observing intervals in distributed estimation problem. In this field, main research works focus on fast consensus [11–13] and finite-time consensus [14–16]. Reference [11] proposes a new consensus protocol which considers the average information of the agents' states in a certain time interval and increases consensus speed of multiagent systems through determining suitable upper limit of time interval based on the frequently domain analysis and matrix theory. Reference [12] proposes a class of pinning predictive controllers for consensus networks to substantially increase their convergence speed towards consensus. In [13], an optimal synchronization protocol was designed for the fastest convergence speed when the protocol is perturbed by an additive measurement and process noise. As to finite-time consensus algorithms design, [14] designed continuous distributed control algorithms for double integrators leaderless and leader-follower multiagent systems with external disturbances based on the finite-time control technique. Based on positive or negative values of errors between their neighbor's values and their own state values in multiagent systems, a simple distributed continuous-time protocol is introduced by [15] that guarantees finite-time consensus in networks of autonomous agents when the network has directed switching network topologies and time-delayed communications.Although fast or finite-time consensus without a virtual leader is interesting, it is sometimes more meaningful and interesting to study consensus tracking problem when the virtual leader's state (also called reference) may represent the state of interest for these systems. In [17], a coordinated tracking algorithm with a time-varying leader for first-order dynamics is proposed and bounded control and directed switching interaction topologies are considered when a time-varying consensus reference state is available to only a subset of a team. However, this algorithm requires the estimates of the neighbors’ velocities. In [18], distributed coordinated tracking algorithms are studied when only partial measurements of the states of the virtual leader and the followers are available. Reference [19] studies the issues associated with distributed coordinated tracking for multiple networked Euler-Lagrange systems where only a subset of the followers has access to the leader. As to discrete-time formulation, [20] considers consensus tracking problem when location information of the active leader is completely known but the acceleration information may not be measured; a neighbor-based pinning control law and a neighbor-based state estimation rule are proposed. Although consensus tracking problem is discussed widely, few works focus on fast consensus tracking with time-delays in discrete-time formulation.Motivated by these topics, fast consensus tracking problem of discrete-time multiagent systems with communication delays and input delays is discussed in this paper. The main contribution of this paper is to establish a simple protocol in order to guarantee consensus tracking convergence in general directed network topology based on the frequency-domain analysis. Then, an incrementPID algorithm is introduced to improve the convergent speed and an inequity condition which can describe relations of controller gain, input delays, communications delays and topology structure is obtained. Furthermore, genetic algorithm [21] is introduced to construct incrementPID based on genetic algorithm for obtaining optimization consensus tracking performance. This makes the proposed protocol more practical for application to real-time applications.This paper is organized as follows. In the next section, preliminary notions and multiagent systems model are provided. A conventionalP-like discrete-time consensus tracking algorithm for a single-integrator systems is stated in Section 3 and a fast discrete-time consensus tracking algorithm based on incrementPID is established in Section 4. By applying to genetic algorithms, the fast consensus tracking algorithm mentioned above is optimized in order to obtain an optimal cost in Section 5. Simulation example is shown in Section 6. Finally, concluding remarks are stated in Section 7.


## 2. Preliminaries and Multiagent Systems Modeling

### 2.1. Graph Theory Notions

Notations. The notation used in this paper for graph theory is quite standard. For a system with N agents, the communication graph among these agents is modeled by a directed weighted graph G
=
(
V
,
W
,
A
), where V
=
{
v
1
,
v
2
,
…
,
v
n
}, W
⊆
V
2, and A
=
{
a
i
j
}
∈
ℜ
n
×
n represent the set of agents, the edge set, and the weighted adjacency matrix, respectively. The agent indexes belong to a finite index set Φ
=
{
1,2
,
…
,
N
}. An edge denoted as (
v
i
,
v
j
) means that the v
jth agent can access the information of the v
ith agent. We assume that the adjacency elements associated with the edges of the digraph are positive. That means a
i
j
>
0, if agent i receives information from agent j otherwise a
i
j
=
0. Moreover, we assume feedback gain a
i
i
>
0 for all i
∈
Φ, if ith agent has feedback control loop and a
i
i
=
0 otherwise. Define the set of neighbors of agent v
i as N
i
=
{
v
j
∈
V
:
(
v
i
,
v
j
)
∈
W
}. For the directed digraph the outdegree of agent i is defined as deg
⁡
out
(
v
i
)
=
∑
j
=
1
n
a
i
j. Let D be the degree matrix of G, which is defined as a diagonal matrix with the degree of each agent along its diagonal. The Laplacian matrix of the weighted digraph is defined as L
=
D
-
A satisfying zero-row sum.In multiagent systems, each agent can be considered as a node in a digraph, and the information flow between two agents can be regarded as a directed path between the nodes. Thus, a directed graph has a directed spanning tree if there exists at least one agent called a globally reachable agent that has a directed path to all other agents.


### 2.2. Multiagent System Modeling

Consider agents with a single-integrator kinematics in discrete-time formulation given by(1)
x
i
(
k
+
1
)
=
x
i
(
k
)
+
u
i
(
k
)
,
i
∈
Φ
,
where x
i
∈
ℜ and u
i
∈
ℜ denote the state and the control input of agent i, respectively. The following consensus tracking protocol for the multiagent systems (1) is a classical formulation mentioned by literature [10] which can be described by
(2)
u
i
(
k
)
=
-
g
i
(
0
)
a
i
i
(
x
i
(
k
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
)
-
x
i
(
k
)
)
,
where ζ
r
(
k
) is a time-varying reference state or a virtual leader with the states, named agent 0 and the other agents indexed by 1,2
,
…
,
N are referred to as followers without loss of generality. (Especially, if ζ
r
(
k
)
=
ζ
r, this reference state can be simplified to a constant one). g
i
(
0
) is 1 if agent i has access to ζ
r
(
k
) and 0 otherwise. N
i denotes the neighbors of agent i and a
i
j
>
0 is the adjacency element of A in the directed digraph G
=
(
V
,
W
,
A
). a
i
i
>
0 denotes the feedback control gain of agent i and a
i
i
=
0 otherwise.When agenti is subjected to a time-varying input delay T
i
i
(
t
), system (1) can be rewritten as follows:
(3)
x
i
(
k
+
1
)
=
x
i
(
k
)
+
u
i
(
k
-
T
i
i
(
t
)
)
,
i
∈
Φ
.Consider the total delay where an agent receives data from its neighbors is sum of time-varying input delay and time-varying diverse communication delay, so the consensus tracking protocol becomes(4)
u
i
(
k
-
T
i
i
(
t
)
)
=
-
g
i
(
0
)
a
i
i
(
x
i
(
k
-
T
i
i
(
t
)
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
T
j
j
(
t
)
-
T
i
j
(
t
)
)
-
x
i
(
k
-
T
i
i
(
t
)
)
)
,
where T
i
i
(
t
)
,
T
j
j
(
t
) denotes time-varying input delays of agent i
,
j and T
i
j
(
t
) denotes time-varying communication delay from agent j to agent i, respectively. It is assumed that each agent has similar computer capacity, so the time-varying input delay of each agent can be treated with the same time-delay value; that is, T
i
i
(
t
)
=
T
j
j
(
t
). To simplify the complexity of calculation, we assume that agent i needs to possess memory capability such that x
i
(
k
-
T
i
i
(
t
)
-
T
i
j
(
t
)
) can be used in the consensus tracking protocol. Substitute state x
i
(
k
-
T
i
i
(
t
)
) in coupling terms of (4) for x
i
(
k
-
T
i
i
(
t
)
-
T
i
j
(
t
)
) and let the total delay T
^
i
j
(
t
)
=
T
i
i
(
t
)
+
T
i
j
(
t
) which satisfies T
i
i
(
t
)
≤
T
^
i
j
(
t
). As a result, (4) can be rewritten as
(5)
u
i
(
k
-
T
i
i
(
t
)
)
=
-
g
i
(
0
)
K
i
(
x
i
(
k
-
T
i
i
(
t
)
)
-
ζ
r
(
k
)
)
+


∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
T
^
i
j
(
t
)
)
-
x
i
(
k
-
T
^
i
j
(
t
)
)
)
.Moreover, these two classes of delays can be approximated byT
i
i
(
t
)
=
(
m
i
-
1
)
T
+
ε
i and T
^
i
j
(
t
)
=
(
n
i
j
-
1
)
T
+
ε
i
j, respectively. Where T
i
i
(
t
)
,
T
^
i
j
(
t
)
≥
0, T denotes sample period of this discrete-time system, m
i
,
n
i
j are all nonnegative integers and ε
i
,
ε
i
j are unknown-but-bounded variables which belong to interval (
0
,
T
). So it is reasonable that T
i
i
(
t
) and T
^
i
j
(
t
) are approximated by m
i and n
i
j although some artificial delays are included. In the end, (4) can be rewritten as
(6)
u
i
(
k
-
m
i
)
=
-
g
i
(
0
)
K
i
(
x
i
(
k
-
m
i
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
n
i
j
)
-
x
i
(
k
-
n
i
j
)
)
.Substituting protocol (6) to the system (3), we have
(7)
x
i
(
k
+
1
)
=
x
i
(
k
)
-
g
i
(
0
)
K
i
[
x
i
(
k
-
m
i
)
-
ζ
r
(
k
)
]
+
∑
v
j
∈
N
i
‍
a
i
j
[
x
j
(
k
-
n
i
j
)
-
x
i
(
k
-
n
i
j
)
]
,
i
∈
Φ
.
Using algorithm (6), each agent essentially updates its next state based on its past state with limited time delay and its neighbors' current as well as the reference's current if the reference is a neighbor of the agent. As a result, (6) can be easily implemented in practice.


## 2.1. Graph Theory Notions

Notations. The notation used in this paper for graph theory is quite standard. For a system with N agents, the communication graph among these agents is modeled by a directed weighted graph G
=
(
V
,
W
,
A
), where V
=
{
v
1
,
v
2
,
…
,
v
n
}, W
⊆
V
2, and A
=
{
a
i
j
}
∈
ℜ
n
×
n represent the set of agents, the edge set, and the weighted adjacency matrix, respectively. The agent indexes belong to a finite index set Φ
=
{
1,2
,
…
,
N
}. An edge denoted as (
v
i
,
v
j
) means that the v
jth agent can access the information of the v
ith agent. We assume that the adjacency elements associated with the edges of the digraph are positive. That means a
i
j
>
0, if agent i receives information from agent j otherwise a
i
j
=
0. Moreover, we assume feedback gain a
i
i
>
0 for all i
∈
Φ, if ith agent has feedback control loop and a
i
i
=
0 otherwise. Define the set of neighbors of agent v
i as N
i
=
{
v
j
∈
V
:
(
v
i
,
v
j
)
∈
W
}. For the directed digraph the outdegree of agent i is defined as deg
⁡
out
(
v
i
)
=
∑
j
=
1
n
a
i
j. Let D be the degree matrix of G, which is defined as a diagonal matrix with the degree of each agent along its diagonal. The Laplacian matrix of the weighted digraph is defined as L
=
D
-
A satisfying zero-row sum.In multiagent systems, each agent can be considered as a node in a digraph, and the information flow between two agents can be regarded as a directed path between the nodes. Thus, a directed graph has a directed spanning tree if there exists at least one agent called a globally reachable agent that has a directed path to all other agents.


## 2.2. Multiagent System Modeling

Consider agents with a single-integrator kinematics in discrete-time formulation given by(1)
x
i
(
k
+
1
)
=
x
i
(
k
)
+
u
i
(
k
)
,
i
∈
Φ
,
where x
i
∈
ℜ and u
i
∈
ℜ denote the state and the control input of agent i, respectively. The following consensus tracking protocol for the multiagent systems (1) is a classical formulation mentioned by literature [10] which can be described by
(2)
u
i
(
k
)
=
-
g
i
(
0
)
a
i
i
(
x
i
(
k
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
)
-
x
i
(
k
)
)
,
where ζ
r
(
k
) is a time-varying reference state or a virtual leader with the states, named agent 0 and the other agents indexed by 1,2
,
…
,
N are referred to as followers without loss of generality. (Especially, if ζ
r
(
k
)
=
ζ
r, this reference state can be simplified to a constant one). g
i
(
0
) is 1 if agent i has access to ζ
r
(
k
) and 0 otherwise. N
i denotes the neighbors of agent i and a
i
j
>
0 is the adjacency element of A in the directed digraph G
=
(
V
,
W
,
A
). a
i
i
>
0 denotes the feedback control gain of agent i and a
i
i
=
0 otherwise.When agenti is subjected to a time-varying input delay T
i
i
(
t
), system (1) can be rewritten as follows:
(3)
x
i
(
k
+
1
)
=
x
i
(
k
)
+
u
i
(
k
-
T
i
i
(
t
)
)
,
i
∈
Φ
.Consider the total delay where an agent receives data from its neighbors is sum of time-varying input delay and time-varying diverse communication delay, so the consensus tracking protocol becomes(4)
u
i
(
k
-
T
i
i
(
t
)
)
=
-
g
i
(
0
)
a
i
i
(
x
i
(
k
-
T
i
i
(
t
)
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
T
j
j
(
t
)
-
T
i
j
(
t
)
)
-
x
i
(
k
-
T
i
i
(
t
)
)
)
,
where T
i
i
(
t
)
,
T
j
j
(
t
) denotes time-varying input delays of agent i
,
j and T
i
j
(
t
) denotes time-varying communication delay from agent j to agent i, respectively. It is assumed that each agent has similar computer capacity, so the time-varying input delay of each agent can be treated with the same time-delay value; that is, T
i
i
(
t
)
=
T
j
j
(
t
). To simplify the complexity of calculation, we assume that agent i needs to possess memory capability such that x
i
(
k
-
T
i
i
(
t
)
-
T
i
j
(
t
)
) can be used in the consensus tracking protocol. Substitute state x
i
(
k
-
T
i
i
(
t
)
) in coupling terms of (4) for x
i
(
k
-
T
i
i
(
t
)
-
T
i
j
(
t
)
) and let the total delay T
^
i
j
(
t
)
=
T
i
i
(
t
)
+
T
i
j
(
t
) which satisfies T
i
i
(
t
)
≤
T
^
i
j
(
t
). As a result, (4) can be rewritten as
(5)
u
i
(
k
-
T
i
i
(
t
)
)
=
-
g
i
(
0
)
K
i
(
x
i
(
k
-
T
i
i
(
t
)
)
-
ζ
r
(
k
)
)
+


∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
T
^
i
j
(
t
)
)
-
x
i
(
k
-
T
^
i
j
(
t
)
)
)
.Moreover, these two classes of delays can be approximated byT
i
i
(
t
)
=
(
m
i
-
1
)
T
+
ε
i and T
^
i
j
(
t
)
=
(
n
i
j
-
1
)
T
+
ε
i
j, respectively. Where T
i
i
(
t
)
,
T
^
i
j
(
t
)
≥
0, T denotes sample period of this discrete-time system, m
i
,
n
i
j are all nonnegative integers and ε
i
,
ε
i
j are unknown-but-bounded variables which belong to interval (
0
,
T
). So it is reasonable that T
i
i
(
t
) and T
^
i
j
(
t
) are approximated by m
i and n
i
j although some artificial delays are included. In the end, (4) can be rewritten as
(6)
u
i
(
k
-
m
i
)
=
-
g
i
(
0
)
K
i
(
x
i
(
k
-
m
i
)
-
ζ
r
(
k
)
)
+
∑
v
j
∈
N
i
‍
a
i
j
(
x
j
(
k
-
n
i
j
)
-
x
i
(
k
-
n
i
j
)
)
.Substituting protocol (6) to the system (3), we have
(7)
x
i
(
k
+
1
)
=
x
i
(
k
)
-
g
i
(
0
)
K
i
[
x
i
(
k
-
m
i
)
-
ζ
r
(
k
)
]
+
∑
v
j
∈
N
i
‍
a
i
j
[
x
j
(
k
-
n
i
j
)
-
x
i
(
k
-
n
i
j
)
]
,
i
∈
Φ
.
Using algorithm (6), each agent essentially updates its next state based on its past state with limited time delay and its neighbors' current as well as the reference's current if the reference is a neighbor of the agent. As a result, (6) can be easily implemented in practice.


## 3.P-Like Discrete-Time Consensus Tracking with Input Delays and Communication Delays

In this section we consider consensus tracking problem of multiagent systems with both communication delays and input delays. Firstly, two lemmas related to this topic need to be introduced. Then, a sufficient consensus tracking condition of multiagent systems (7) with conventional P-like algorithmn is proposed based on the frequency-domain analysis and matrix theory.Lemma 1 (Gershgorin’s disk theorem).
LetΛ
=
(
a
i
j
) be a N
×
N complex matrix; then all eigenvalues of matrix Λ belong to the union set of N circular disc on the complex plane; that is,
(8)
D
i
(
Λ
)
=
{
z
|
|
z
-
a
i
i
|
≤
R
i
,
(
i
=
1,2
,
…
,
N
)
,
where R
i
=
|
a
i
1
|
+
|
a
i
2
|
+
⋯
|
a
i
,
i
-
1
|
+
|
a
i
,
i
+
1
|
+
⋯
+
|
a
i
N
|.Lemma 2 (see [10]).
The following inequality:(9)
sin
(
(
(
2
D
+
1
)
/
2
)
ω
)
sin
(
ω
/
2
)
≤
2
D
+
1
holds for all nonnegative integers D and all ω
∈
[
-
π
,
π
].In the following, we apply Lemmas1 and 2 to derive our main result.Theorem 3.
Consider multiagent systems (3) with algorithm (6). Assume that the interconnection topology digraph G
=
(
V
,
W
,
A
) of the system has no less than a globally reachable agent and at least one globally reachable agent can receive reference information. Then the system achieves a consensus tracking asymptotically if
(10)
K
i
i
(
2
m
i
+
1
)
+
K
i
j
(
2
n
i
j
+
1
)
<
1
,
where K
i
i
=
g
i
(
0
)
K
i denotes the feedback control gain of agent i, K
i
j
=
∑
v
j
∈
N
i
a
i
j denotes outdegree of agent i.Proof.
The multiagent systems of (3) with (6) are given by (7). Taking the z-transformation of the system (7), we get
(11)
z
X
i
(
z
)
=
X
i
(
z
)
-
g
i
(
0
)
K
i
[
z
-
m
i
X
i
(
z
)
-
ζ
r
(
z
)
]
+
∑
v
j
∈
N
i
‍
a
i
j
[
z
-
n
i
j
X
j
(
z
)
-
z
-
n
i
j
X
i
(
z
)
]
,
where X
i
(
z
) and ζ
r
(
z
) are the z-transformation of x
i
(
k
) and ζ
r
(
k
), respectively. Define a N
×
N matrix L
~
(
z
)
=
{
l
~
i
j
(
z
)
} as follows:
(12)
l
~
i
j
(
z
)
=
{
-
a
i
j
z
-
n
i
j
,
v
j
∈
N
i
,
g
i
(
0
)
K
i
z
-
m
i
+
∑
v
j
∈
N
i
‍
a
i
j
z
-
n
i
j
,
i
=
j
,
0
,
otherwise
,
and X
(
z
)
=
[
X
1
(
z
)
,
…
,
X
N
(
z
)
]
T, Q
=
diag
⁡
(
g
1
(
0
)
K
1
,
…
,
g
N
(
0
)
K
N
), and then (11) becomes
(13)
z
X
(
z
)
=
X
(
z
)
+
Q
(
1
⊗
ζ
r
(
z
)
)
-
L
~
(
z
)
X
(
z
)
.
Let ζ
r
(
z
) denote input signal and let X
(
z
) denote output signal; then the transform function is denoted by
(14)
G
(
z
)
=
X
(
z
)
ζ
r
(
z
)
=
Q
(
z
-
1
)
I
+
L
~
(
z
)
,
and correspondent characteristic equation of mulitagent system (13) is p
(
z
)
=
det
⁡
[
I
+
(
1
/
(
z
-
1
)
)
L
~
(
z
)
]. Then, we will prove that all the zeros of p
(
z
) have modulus less than unity in the following.
Based on the general Nyquist stability criterion, the modulus of all roots satisfyingp
(
z
)
=
0 should be less than unity, if all poles λ
(
(
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
)
) of (
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
) do not enclose the point (
-
1
,
j
0
) for ω
∈
[
-
π
,
π
]. By Lemma 1, all poles λ
(
(
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
)
) belong to the union set of N circular disks; that is,
(15)
D
i
=
{
∑
v
j
∈
N
i
‍
|
a
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
|
ξ
-
g
i
(
0
)
K
i
e
-
j
ω
m
i
+
∑
v
j
∈
N
i
‍
a
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
≤
∑
v
j
∈
N
i
‍
|
a
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
}
.
To simplify, we defineK
i
i
=
g
i
(
0
)
K
i
,
K
i
j
=
∑
v
j
∈
N
i
a
i
j and let
(16)
G
i
(
ω
)
=
K
i
i
e
-
j
ω
m
i
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
.
It is easy to see thatG
i
(
ω
) is the center of the disc D
i. Thus, the point (
-
1
,
j
0
) does not enclose in disc D
i for all ω
∈
[
-
π
,
π
] as long as the point (
-
a
,
j
0
) with a
≥
1. As a result, when ω
∈
[
-
π
,
π
]
,
a
≥
1, we have
(17)
|
-
a
+
j
0
-
K
i
i
e
-
j
ω
m
i
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
>
|
K
i
i
e
-
j
ω
m
i
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
.
Then this inequality can be rewritten as(18)
|
-
a
+
j
0
-
K
i
i
e
-
j
ω
m
i
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
2
-
|
K
i
i
e
-
j
ω
m
i
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
2
=
a
(
a
-
K
i
i
sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
+
K
i
j
sin
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
sin
(
ω
/
2
)
)
>
0
.
According to Lemma2, we have sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
m
i
+
1
,
sin
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
n
i
j
+
1 for ω
∈
[
-
π
,
π
]. Then the following inequality is obtained by
(19)
K
i
i
sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
+
K
i
j
sin
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
sin
(
ω
/
2
)
≤
K
i
i
(
2
m
i
+
1
)
+
K
i
j
(
2
n
i
j
+
1
)
<
a
.
Leta
=
1; then all disc D
i do not enclose the point (
-
1
,
j
0
). As a result, multiagent systems (7) can achieve a consensus tracking asymptotically. That is end of this proof.Remark 4.
If we rewrite (19) as (
K
i
i
+
K
i
j
)
(
2
m
i
+
1
)
+
2
K
i
j
(
n
i
j
-
m
i
)
<
1, it is easy to know that consensus tracking problem of multiagent systems is more sensitive to input delays than communication delays. Moreover, Theorem 3 is also suitable for the case when it only has input delays if we let m
i
=
n
i
j.


## 4. Fast Discrete-Time Consensus Tracking Algorithm Based on IncrementP
I
D

Considering feedback control gainsK
i
,
i
=
1,2
,
…
,
n is the similar with conventional P-like controllers, an incrementPID algorithm is proposed consequently to accelerate the convergence speed of multiagent systems (7). DiscretePID algorithm is described by
(20)
h
i
(
k
)
=
K
p
[
e
i
(
k
)
+
T
T
i
∑
j
=
0
k
‍
e
i
(
j
)
+
T
d
e
i
(
k
)
-
e
i
(
k
-
1
)
T
]
,
where h
i
(
k
) is feedback control signal of agent i at time interval k. e
i
(
k
) denotes the error of current state between agent i and current reference state and e
i
(
k
-
1
) denotes the error of the value between agent i and reference state at time interval k
-
1, respectively. K
p denotes proportional coefficient, T
i denotes integral time, T
d denotes derivative time, and sampling period is described by T.Throughh
i
(
k
)
-
h
i
(
k
-
1
), we obtain incrementPID algorithm as
(21)
Δ
h
i
(
k
)
=
h
i
(
k
)
-
h
i
(
k
-
1
)
=
A
-
e
i
(
k
)
-
B
-
e
i
(
k
-
1
)
+
C
-
e
i
(
k
-
2
)
,
where A
-
=
K
p
(
1
+
T
/
T
i
+
T
d
/
T
)
,
B
-
=
K
p
(
1
+
2
(
T
d
/
T
)
), and C
-
=
K
p
(
T
d
/
T
).Remark 5.
From (21) we know that if sampling period T and coefficient A
,
B
,
C are chosen, control signal Δ
h
i
(
k
) will be obtained by only using three adjacent deviation values. Because this algorithm is easily realized in the agent with limited computing capacity, it is very suitable for multiagent system.
Lete
i
(
k
-
m
i
)
=
x
i
(
k
-
m
i
)
-
ζ
r
(
k
) in (7) and substitute feedback control gains K
i into incrementPID algorithm as (21); (7) can be rewritten by
(22)
x
i
(
k
+
1
)
=
x
i
(
k
)
-
g
i
(
0
)
[
A
-
e
i
(
k
-
m
i
)
-
B
-
e
i
(
k
-
m
i
-
1
)
+
C
-
e
i
(
k
-
m
i
-
2
)
]
+
∑
v
j
∈
N
i
a
i
j
[
x
j
(
k
-
n
i
j
)
-
x
i
(
k
-
n
i
j
)
]
‍
,
i
,
j
∈
Φ
.
Then, we obtain sufficient fast consensus tracking condition of multiagent system (22) based on incrementPID algorithm as follows.Theorem 6.
Consider multiagent systems (3) with algorithm (5). Assume that the interconnection topology digraph G
=
(
V
,
W
,
A
) of the system has no less than a globally reachable agent and at least one globally reachable agent can receive reference information. Then the system achieves a fast consensus tracking asymptotically if
(23)
A
(
2
m
i
+
1
)
+
B
(
2
m
i
+
3
)
+
C
(
2
m
i
+
5
)
+
K
i
j
(
2
n
i
j
+
1
)
≤
1
,
i
,
j
∈
Φ
,
where A
=
g
i
(
0
)
K
p
(
1
+
T
/
T
i
+
T
d
/
T
)
,
B
=
g
i
(
0
)
K
p
(
1
+
2
(
T
d
/
T
)
), and C
=
g
i
(
0
)
K
p
(
T
d
/
T
) and K
i
j
=
∑
v
j
∈
N
i
a
i
j denotes outdegree of agent i.Proof.
The multiagent systems of (3) with (5) and (21) are given by (22). Taking the z-transformation of the system (22), we get
(24)
z
X
i
(
z
)
=
X
i
(
z
)
-
(
A
z
-
m
i
+
B
z
-
m
i
-
1
+
C
z
-
m
i
-
2
)
X
i
(
z
)
+
(
A
+
B
z
-
1
+
C
z
-
2
)
ζ
r
(
z
)
+
∑
v
j
∈
N
i
a
i
j
z
-
n
i
j
[
X
j
(
z
)
-
X
i
(
z
)
]
,
where X
i
(
z
) and ζ
r
(
z
) are the z-transformation of x
i
(
k
) and ζ
r
(
k
), respectively. Define a N
×
N matrix L
~
(
z
)
=
{
l
~
i
j
(
z
)
} as follows:
(25)
l
~
i
j
(
z
)
=
{
-
a
i
j
z
-
n
,
v
j
∈
N
i
A
z
-
m
i
+
B
z
-
m
i
-
1
+
C
z
-
m
i
-
2
+
∑
v
j
∈
N
i
‍
a
i
j
z
-
n
i
j
,
j
=
i
0
.
otherwise
and X
(
z
)
=
[
X
1
(
z
)
,
…
,
X
N
(
z
)
]
T, Q
=
A
+
B
z
-
1
+
C
z
-
2; then (24) becomes
(26)
z
X
(
z
)
=
X
(
z
)
+
Q
ζ
r
(
z
)
1
N
-
L
~
(
z
)
X
(
z
)
.
Let ζ
r
(
z
) denote input and let X
(
z
) denote output and 1
N as unit column vector with N
×
1 dimensions; then the characteristic equation of system (26) becomes p
(
z
)
=
det
⁡
[
I
+
(
1
/
(
z
-
1
)
)
L
~
(
z
)
]. In consequence, we will prove the all roots of p
(
z
)
=
0 whose module is less than unity.
According to general Nyquist stability criterion, modulus of all roots satisfiedp
(
z
)
=
0 should be less than unity, if all poles λ
(
(
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
)
) of (
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
) do not enclose the point (
-
1
,
j
0
) for ω
∈
[
-
π
,
π
]. By Lemma 1, all poles λ
(
(
1
/
(
e
j
ω
-
1
)
)
L
~
(
e
j
ω
)
) belong to the union set of N circular disks; that is,
(27)
D
i
=
{
≤
∑
v
j
∈
N
i
‍
|
a
i
j
e
-
j
ω
n
e
j
ω
-
1
|
|
ξ
-
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
∑
v
j
∈
N
i
a
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
≤
∑
v
j
∈
N
i
‍
|
a
i
j
e
-
j
ω
n
e
j
ω
-
1
|
}
.
Moreover, we have
(28)
D
i
=
{
|
ξ
-
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
<
|
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
}
,
where K
i
j
=
∑
v
j
∈
N
i
a
i
j.
DefineG
i
(
ω
)
=
(
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
)
/
(
e
j
ω
-
1
); it is easy to see that G
i
(
ω
) is center of disc D
i. Then, the point (
-
1
,
j
0
) does not enclose in disc D
i for all ω
∈
[
-
π
,
π
] as long as the point (
-
a
,
j
0
) with a
≥
1. As a result, when ∈
[
-
π
,
π
], we have
(29)
|
-
a
+
j
0
-
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
>
|
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
.
Through several trivial transform, we have(30)
|
-
a
+
j
0
-
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
2
-
|
A
e
-
j
ω
m
i
+
B
e
-
j
ω
(
m
i
+
1
)
+
C
e
-
j
ω
(
m
i
+
2
)
+
K
i
j
e
-
j
ω
n
i
j
e
j
ω
-
1
|
2
=
a
(
-
A
sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
+
B
sin
(
(
(
2
m
i
+
3
)
/
2
)
ω
)
2
sin
⁡
(
ω
/
2
)
-
C
sin
(
(
(
2
m
i
+
5
)
/
2
)
ω
)
+
K
i
j
sin
⁡
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
2
sin
⁡
(
ω
/
2
)
)
>
0
.
As for Lemma2, we have sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
m
i
+
1
,
sin
(
(
(
2
m
i
+
3
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
m
i
+
3
,
sin
(
(
(
2
m
i
+
5
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
m
i
+
5, and sin
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
/
sin
(
ω
/
2
)
≤
2
n
i
j
+
1. Then the following inequality is obtained by(31)
A
sin
(
(
(
2
m
i
+
1
)
/
2
)
ω
)
+
B
sin
(
(
(
2
m
i
+
3
)
/
2
)
ω
)
+
C
sin
(
(
(
2
m
i
+
5
)
/
2
)
ω
)
+
K
i
j
sin
⁡
(
(
(
2
n
i
j
+
1
)
/
2
)
ω
)
2
sin
⁡
(
ω
/
2
)
≤
A
(
2
m
i
+
1
)
+
B
(
2
m
i
+
3
)
+
C
(
2
m
i
+
5
)
+
K
i
j
(
2
n
i
j
+
1
)
<
a
.
Similar to (19), this inequality holds under the conditions of ω
∈
[
-
π
,
π
] and a
=
1. That is end of this proof.Remark 7.
Because an inequality is used in (28), the result of Theorem 6 is considerable conservatism. If A
=
K
i
i
,
B
,
C
=
0, we can obtain Theorem 3.That is to say, this conservatism can be ignored if B
,
C are very small.Remark 8.
By using incrementPID algorithm, the maximum allowable time delay of consensus tracking of multiagents system become larger; even input delays m
i and communication delay n
i
j in Theorem 6 are chosen to disobey the inequality; this multiagent systems is still converged to its reference in many cases.


## 5. Optimization Consensus TrackingPID Algorithm Based on Genetic Algorithm

The main result in Section4 gives a consensus tracking range whose multiagent systems can converge to reference. However, our interesting is how fast these multiagent systems can converge to reference or are there optimalPID parameters which make these systems track reference with optimal performances? Here, a new optimization incrementPID algorithm based on genetic algorithm (GA-PID) is proposed for optimization cost including rise time, output energy of controllers, and tracking error.Here, the fast consensus tracking problem of multiagent system is described as follows: finding the optimalPID parameters K
p
,
T
i
,
T
d of Theorem 6 which can make the system achieve faster consensus tracking. It is well known that the genetic algorithm is an effective method that can find the global optimal solution, so we improve the conventional genetic algorithm in order to solve this optimization tracking problem. The basic design steps of self-adjustingPID controller based on the genetic algorithm are as follows.(1)
To ascertain parameters. To ascertain the values ofPID parameters according to the mathematic model of the system so as to narrow the searching scope and improve the efficiency of optimization, here, let K
p
,
T
i
,
T
d
≤
1.
(2)
To select the initial population. Here, 50 initial populations are chosen at random, so populations sizeM is equal to 50.
(3)
To ascertain the adaptation parameter. Combing three control performances stability, raPIDity, and accuracy, the target functions shown as below can be used as the optimal index for the selection of parameters:
(32)
J
s
=
∑
‍
J
i
,
J
i
=
∫
0
∞
‍
(
ω
1
|
e
i
(
k
)
|
+
ω
2
u
i
2
(
k
)
)
d
t
+
ω
3
k
u
i
,
i
∈
Φ
,
where J
s is the global optimal index, J
i is the local optimal index of agent i for tracking reference. e
i
(
k
)
,
u
i
(
k
), and k
u
i are the error, controller input, and rising time of agent i, respectively. ω
1
,
ω
2
,
ω
3 denotes weighted values of these three parameters.In order to avoid overshooting, a punishment mechanism is introduced. That is, if the overshooting happened, this overshoot should become a term of local optimal index of agent i. As a result, the local optimal index becomes
(33)
If
e
i
(
k
)
<
0
,
then
J
i
=
∫
0
∞
‍
(
ω
1
|
e
i
(
k
)
|
+
ω
2
u
i
2
(
k
)
+
ω
4
|
e
i
(
k
)
|
)
d
t
+
ω
3
k
u
i
,
where ω
4 is a weighted value satisfying ω
4
≫
ω
1. Here related weighted values are ω
1
=
0.999, ω
2
=
0.001, and ω
3
=
2.0. The weighted value of punishment mechanism is ω
4
=
100. The fitness function is F
=
1
/
J
s.
(4)
Design of genetic operator. Designing genetic operator is a basic operation of genetic algorithm to populations including selection operator, crossover operator, and mutation operator. Selection operator is determined by its selection probability described byp
i
=
F
i
/
∑
1
M
‍
F
i, where F
i is fitness of agent i. Crossover operator is determined by crossover probability P
c. Mutation operator is determined by mutation probability P
m.
(5)
To ascertain evolution parameters. Here, let initial populationM
=
50, end-up generation G
=
100, crossover probability P
c
=
0.9, and initial mutation probability P
m
=
0.1.


## 6. Simulation Example

Example 9.
Consider the multiagent systems which are composed of one virtue leader and 6 following agents with an interconnection digraph shown by Figure1. The weights of the directed paths are a
12
=
0.1
,
a
16
=
0.05
,
a
23
=
0.15
,
a
36
=
0.1
,
a
43
=
0.05
,
a
45
=
0.1, and a
56
=
0.15
,
a
62
=
0.15. Agent “0" is consensus tracking reference ζ
r
(
k
) and interconnection with dotted line denotes a communication existing between reference agent and neighbors of this reference agent. Without loss of generality, the virtual leader 0 can also be known only for part of agents and differences topologies could be seen in Table 1. Initial state of all agents is x
(
0
)
=
(
8,6
,
5,3
,
0
,
-
2
)
T and sample period of these systems is T
=
1 second. For simplify, here let m
i
=
m
,
n
i
j
=
n
,
i
,
j
∈
(
1,2
,
…
,
6
).Table 1
Comparison of convergence time among three algorithms in different topologies (m
=
1, n
=
3).
Agents receivedconstant reference
P-like algorithm
P
=
0.1
IncrementP
I
D algorithm
P
=
0.1, I
=
2, D
=
0.1
IncrementP
I
D algorithm based on GA
All
84
45
24
Agent 6
155
87
60
Agent 2
179
76
56
Agent 3
123
78
56
Agents (1, 4, 5, and 6)
153
87
76
Agents (1, 4, 5, and 3)
119
78
64
Agents (1, 4, 5, and 2)
175
70
56
Agents (2, 6)
89
45
32
Agents (2, 3)
85
41
43
Agents (3, 6)
91
47
68
Agents (2, 3, and 6)
84
41
33Figure 1
Digraph of a group of seven agents.It is easy to see that there exist three globally reachable agents named agent 2, agent 3, and agent 6 in this directed graph. Firstly, all agents which can receive reference are considered when this reference is constant (ζ
r
(
k
)
=
4) or time varying (ζ
r
(
k
)
=
sin
(
0.15
k
)
+
4), respectively, and consensus tracking responds could be seen in Figures 2, 3, 4, 5, and 6 under the condition of m
=
1
,
n
=
3. From Figures 2–4, we can see that the multiagent systems can converge to the constant reference when P
-like
(
K
i
i
=
K
1
=
K
2
=
⋯
=
K
6
=
0.1
), Increment
P
I
D
(
K
p
=
0.1
,
T
i
=
0.5
,
T
d
=
0.1
), and GA
-
P
I
D
(
K
p
=
0.5122
,
T
i
=
2.4149
,
T
d
=
0.0515
) and GA-PID algorithm has faster convergent speed than that of the two. If we compare maximum allowable time delay, GA-PID has the largest consensus tracking allowable time delays known as m
=
1
,
n
=
21 in contrast to m
=
1
,
n
=
5 as to conventional P-like algorithm and m
=
1
,
n
=
12 as to incrementPID algorithm. Figure 5 show the optimization process of Best J based on genetic algorithm.Figure 2
States trajectory achieving consensus byP-like algorithm.Figure 3
States trajectory achieving consensus by incrementPID algorithm.Figure 4
States trajectory achieving consensus by GA-PID algorithm.Figure 5
BestJ for GA-PID algorithm.Figure 6
States trajectory with time-varying reference byP-like algorithm when P
=
0.1.In fact, the multiagent systems can converge to the reference on the condition that at least one globally reachable agent can receive the constant reference. Similar results can also be obtained in different topologies. Details could be seen in Table1. Comparing these three algorithms we can see that P-like algorithm has slowest convergence speed, incrementPID algorithm has strongest robustness performance, and incrementPID based on GA has fastest convergence speed in almost all cases. What is more, a very interesting thing is also deduced from Table 1. That is, convergence speed is similar between all agents receiving the reference and only globally reachable agents receiving the reference. This means that only globally reachable agents instead of all agents receive reference and a similar convergence speed can also be obtained.From [9] we know that conventional P-like algorithm is not sufficient for consensus tracking when all agents receive a time-varying consensus reference. However, if our incrementPID algorithm is adopted, consensus tracking can be achieved through choosing suitablePID parameters. Comparing Figure 6 with Figure 7 we can see that suitablePID parameters not only decrease errors between reference and current states of agents, but also increase the convergence speed. Regretfully, these three algorithms cannot be used to track a time-varying reference, that is, available to only a subset of the team members for only receiving time-varying reference state. If time-varying reference changes in a piecewise constant case, incrementPID algorithm based on genetic algorithm can track this time-varying reference whether the reference is available to all team members or to a subset of the team member. From Figure 8 we can see that the multiagent systems can converge to a piecewise constant reference within about 40 seconds when only agents (
2
,
3
,
6
) receive this time-varying reference. This characteristic can be applied to many fields such as synchronizing a network of clocks [13].Figure 7
States trajectory achieving consensus with time-varying reference by incrementPID algorithm when P
=
0.2
,
I
=
2.56, and D
=
0.125.Figure 8
Consensus tracking in piecewise constant by GA-PID algorithm only (2, 3, 6) receiving reference.


## 7. Conclusions

In this paper, three consensus tracking algorithms namedP-like algorithm, incrementPID algorithm, and incrementPID algorithm based on genetic algorithm, respectively, for discrete-time multiagent systems with time-varying input delays and communication delays are proposed based on the frequency-domain analysis. Firstly, a consensus tracking sufficient condition of conventional P-like algorithm is obtained. Secondly, a new incrementPID algorithm based on similar frequency-domain method is designed for improving consensus convergence speed and an inequality condition is also deduced. Finally, considering three control performances stability, rapidity, and accuracy, an incrementPID algorithm based on genetic algorithm is designed to find optimalPID parameters within an inequality allowable span for achieving optimization cost. These three algorithms can solve tracking problem of multiagent systems with a constant reference effectively when reference state is available to all the team members. If the reference state might only be available to a portion of the agents in the team, the convergence speed may increase in the same condition. As for a time-varying reference case, if the reference state has a directed path to all team agents, incrementPID algorithm and incrementPID algorithm based on genetic algorithm can realize consensus tracking through choosing suitablePID parameters while conventional P-like algorithm fails to track the reference. However, these three algorithms cannot be used to track a time-varying reference state when the reference is available to only a subset of team members. In the future research, we will focus on more complex issues in the controller design such as actuator delay and fault, H
∞ controller design with control delay, quantized control, and global consensus problem with saturated control [22–29].



---

*Source: 253806-2014-03-19.xml*