# On the General Consensus Protocol in Multiagent Networks with Double-Integrator Dynamics and Coupling Time Delay

Authors: Tao Dong; Xiaofeng Liao
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

This paper considers the problem of the convergence of the consensus algorithm for multiple agents in a directed network where each agent is governed by double-integrator dynamics and coupling time delay. The advantage of this protocol is that almost all the existing linear local interaction consensus protocols can be considered as special cases of the present paper. By combining algebraic graph theory and matrix theory and studying the distribution of the eigenvalues of the associated characteristic equation, some necessary and sufficient conditions are derived for reaching the second-order consensus. Finally, an illustrative example is also given to support the theoretical results.


---

## Body

## 1.Introduction

Recently, coordinated control of multiple agents has attracted a great deal of attention in many fields such as biology, physics, robotics, and control engineering [1, 2]. Research on multiagent coordinated control problems not only helps in better understanding the general mechanisms and interconnection rules of natural collective phenomena, but also benefits many practical applications of networked cyberphysical systems, such as the coordination and control of distributed sensor networks [3], formation control in multirobots [4], unmanned autonomous vehicles (UAVs) formations [5, 6], flocking [7], complex networks [8, 9], and so on [10, 11]. A critical problem in coordinated control of multiple agents is to find control laws such that all agents can reach an agreement regarding a certain quantity of interest that depends on the states of all agents. This problem is usually called the consensus problem [12]. In recent years, numerous studies have been conducted on this problem, some special second-order consensus protocols were presented, and some consensus conditions were obtained [13–18].In the references on the consensus problem, multiagent systems with double-integrator dynamics have been paid great attentions because of their importance in practice. In [13], the authors studied some necessary and sufficient conditions for second-order consensus multiagent system, and revealed that both the real and imaginary parts of the eigenvalues of the Laplacian matrix of the corresponding directed network play key roles in reaching consensus. In [14], Zhu et al. discussed the consensus problem of coupled second-order linear harmonic oscillators with local interaction, which means that the states of all agents converge to the same periodic function. In [15], Zhu discussed a more general linear form of consensus protocols for multiagent systems with double-integrator dynamics. In [16], Li et al. investigated the final consensus convergence state of multiagent dynamical systems by using a kind of generalized linear local interaction protocols without time delay. However, most of the protocols discussed in the existing literature have neither addressed the consensus of positive exponential dynamics, namely, each agent’s state converges to a positive exponential function, nor considered the time delay in network. So, the observation provides us the motivation of this paper to investigate the consensus of second-order agents in directed networks double-integrators and coupling time delay.In this paper, we consider the convergence of the second-order consensus of multiagent systems composed of coupled double-integrators dynamics and coupling time delay. For this protocol, all the agents in the fixed directed network topology are governed by double-integrator dynamics. The advantage of this protocol is that almost all the existing linear local interaction consensus protocols can be considered as special cases of the present paper [13–16]. By combining algebraic graph theory and matrix theory and studying the distribution of the eigenvalues of the associated characteristic equation, we give explicitly the effect of delays for second-order consensus. The contribution of this paper is to obtain a necessary and sufficient condition that the second-order consensus can be achieved in a delayed multiagent system with a directed spanning tree if and only if the time delay is less than a certain critical value.The rest of this paper is outlined as follows. In Section2, some preliminaries on the graph theory and the model formulation are given. The main results are established in Section 3. In Section 4, several numerical examples are simulated to verify the theoretical analysis. Conclusions are finally drawn in Section 5.


## 2.Preliminaries

In this subsection, some basic concepts and results about algebraic grapy theory are introduced. For more details about algebraic graph theory, please refer to [19]. Suppose that information exchange among agents in multiagent systems can be modeled by an interaction digraph. Let g=(V,ε,A) denote a directed graph, where V={1,2,…,N} denotes the node set, ε⊆V×V represents the edge set, and A=(aij)N×N is the adjacency matrix. A directed edge εij in the network g is denoted by the ordered pair of nodes (i,j), where i is the head and j is the tail, which means that node i can receive information from node j [20]. The elements of the adjacency matrix A are defined such that aij=1⇔εij∈ε, while aij=0⇔εij∉ε. We always assume that there is no self-loop in network g; that is, aii=0 for all i∈V. Weighted adjacency matrix A of a weighted directed graph can be defined such that aij is a positive weight if εij∈ε, while aij=0 if εij∉ε. The set of neighbors of node i is denoted by Ni={j∈V:(i,j)∈ε}.If there is a sequence of edges of the form(i,j1),(j1,j2),…,(jm,j)∈ε composing a directed path beginning with i and ending with j in the directed graph g with distinct nodes jk,k=1,2,…,m, then the node j is said to be reachable from node i. A directed graph is strongly connected if for any distinct nodes i and j, there exists a directed path from node i to node j. A directed graph has a directed spanning tree if there exists at least one node called root which has a directed path to all the other nodes [21]. A directed graph is balanced if  ∑j=1naij=∑j=1naji for all i. Let (generally nonsymmetrical) Laplacian matrix L=(lij)N×N associated with directed network g be defined as lii=∑j=1,j≠iNaij and lij=-aij, where i≠j. Especially, for an undirected graph, L is symmetric positive semidefinite. However, L for a directed graph does not have this property.


### 2.1. Notations

Some mathematical notations are used for simplicity throughout this paper.In(On) denotes the identity (zero) matrix with n dimensions. Let 1n(0n) be a column vector with n elements being 1 (0). Re(·) and Im(·) represent the real part and imaginary part of a complex, respectively. Cn is the n-dimensional complex vector space.


### 2.2. Consensus Protocols

Suppose that theith agent in the network g is modeled by double-integrator dynamics and coupling time delay
(1)r˙i(t)=vi(t),v˙i(t)=ui(t),i=1,2,…,N,
where ri(t)∈R is the position state, vi(t)∈R is the velocity state, and ui(t)∈R is the control input, which is designed based on local information exchange. In this paper, the consensus protocol in a multiagents system is as follows:
(2)ui(t)=-αri(t)-βvi(t)+γ∑j∈Niaij(rj(t-τ)-ri(t-τ))+ξ∑j∈Niaij(vj(t-τ)-vi(t-τ)),i=1,2,…,N,
where  α>0(β>0)  denotes the position (velocity) damping gain, γ>0(ξ>0) represents the coupling strength of positions (velocities) between neighboring agents, and τ>0 is the communication time-delay.Equivalently, system (2) can be rewritten as follows:
(3)ui(t)=-αri(t)-βvi(t)-γ∑j∈NiLijrj(t-τ)-ξ∑j∈NiLijvj(t-τ),i=1,2,…,N.Letx(t)=[r1(t),r2(t),…,rN(t)]T and v(t)=[v1(t),v2(t),…,vN(t)]T. Then, network (1) can be rewritten in a compact matrix form as
(4)[x˙(t)v˙(t)]=Q[x(t)v(t)],
where Q=[ONIN-αIN-γLe-λτ-βIN-ξLe-λτ], and L∈RN×N is the (nonsymmetric) Laplacian matrix associated with directed graph g.Definition 1.
Second-order consensus in the multiagent system (1) under control input (2) is said to be achieved if for any initial conditions ri(0),  vi(0),  limt→∞|ri(t)-rj(t)|=0  and limt→∞|vi(t)-vj(t)|=0,  ∀i,j=1,2,…,N.


## 2.1. Notations

Some mathematical notations are used for simplicity throughout this paper.In(On) denotes the identity (zero) matrix with n dimensions. Let 1n(0n) be a column vector with n elements being 1 (0). Re(·) and Im(·) represent the real part and imaginary part of a complex, respectively. Cn is the n-dimensional complex vector space.


## 2.2. Consensus Protocols

Suppose that theith agent in the network g is modeled by double-integrator dynamics and coupling time delay
(1)r˙i(t)=vi(t),v˙i(t)=ui(t),i=1,2,…,N,
where ri(t)∈R is the position state, vi(t)∈R is the velocity state, and ui(t)∈R is the control input, which is designed based on local information exchange. In this paper, the consensus protocol in a multiagents system is as follows:
(2)ui(t)=-αri(t)-βvi(t)+γ∑j∈Niaij(rj(t-τ)-ri(t-τ))+ξ∑j∈Niaij(vj(t-τ)-vi(t-τ)),i=1,2,…,N,
where  α>0(β>0)  denotes the position (velocity) damping gain, γ>0(ξ>0) represents the coupling strength of positions (velocities) between neighboring agents, and τ>0 is the communication time-delay.Equivalently, system (2) can be rewritten as follows:
(3)ui(t)=-αri(t)-βvi(t)-γ∑j∈NiLijrj(t-τ)-ξ∑j∈NiLijvj(t-τ),i=1,2,…,N.Letx(t)=[r1(t),r2(t),…,rN(t)]T and v(t)=[v1(t),v2(t),…,vN(t)]T. Then, network (1) can be rewritten in a compact matrix form as
(4)[x˙(t)v˙(t)]=Q[x(t)v(t)],
where Q=[ONIN-αIN-γLe-λτ-βIN-ξLe-λτ], and L∈RN×N is the (nonsymmetric) Laplacian matrix associated with directed graph g.Definition 1.
Second-order consensus in the multiagent system (1) under control input (2) is said to be achieved if for any initial conditions ri(0),  vi(0),  limt→∞|ri(t)-rj(t)|=0  and limt→∞|vi(t)-vj(t)|=0,  ∀i,j=1,2,…,N.


## 3.Main Results

In delayed systems, the time delays can be regarded as the bifurcation parameters. In [17, 18], it was found that Hopf bifurcation occurs when time delays pass through some critical values where the conditions for local asymptotical stability of the equilibrium are not satisfied. Similarly, in this section, we aim to find the maximum time delay with which the consensus can be achieved in the multiagent system (1). Before reaching our main results, we first give the following lemmas.Lemma 2 (see [5]).
LetL be the (nonsymmetric) Laplacian matrix associated with directed network g. Then, L has a simple zero eigenvalue and its other eigenvalues have positive real parts if and only if g has a directed spanning tree.
The characteristic equation for system (4) is
(5)det[λIN-INαIN+γLe-λτλIN+βIN+ξLe-λτ]=det(λIN(λIN+βIN+ξLe-λτ)+αIN+γLe-λτ)=det(λ2IN+βλIN+αIN+e-λτ(λINξL+γL))=∏i=1N[λ2+βλ+α-(λξμi+γμi)e-λτ]=0.
Let gi(λ)=λ2+βλ+α-(λξμi+γμi)e-λτ and g(λ)=∏i=1Ngi(λ). From (5), it is easy to see that L has a zero eigenvalue of algebraic multiplicity m if and only if g(λ)=0 has a zero eigenvalue of algebraic multiplicity 2m.
In the following, one considers the case thatgi(λ) has a pair of purely imaginary roots ±iωi. If  iωi(ωi>0) is a root of gi(λ)=0, substituting it into gi(λ), one can obtain
(6)-ωi2+βiωi+α-(iωiξμi+γμi)e-iωτ=0.
Separating the real and imaginary parts of (6) leads to
(7)[R(μi)γ-l(μi)ωiξ]cosωiτ+[R(μi)ωiξ+l(μi)γ]sinωiτ=-ωi2+α,[R(μi)ωiξ+l(μi)γ]cosωiτ-[R(μi)γ-l(μi)ωiξ]sinωiτ=βωi.
By squaring and adding the previous equations, it follows that
(8)ωi4-(∥μi∥2ξ2+2α-β2)ωi2-∥μi∥2γ2+α2=0.
By solving (8), one can obtain
(9)ωi2=∥μi∥2ξ2+2α-β2±(∥μi∥2ξ2+2α-β2)2+4(∥μi∥2r2-α2)2.Lemma 3.
(1)  If∥μi∥2ξ2+2α<β2 and ∥μi∥2γ2<α2, then (8) has no positive root.
(2)  If∥μi∥2ξ2+2α>β2 and ∥μi∥2γ2>α2, then (8) has only one positive root.
(3)  If∥μi∥2ξ2+2α>β2 and ∥μi∥2γ2<α2, then (8) has two positive roots.
Suppose that (8) has positive roots; without loss of generality, one assumes that it has two positive roots defined by ωik, (k=1,2). By (7), one has
(10)cos(ωikτ)=(-ωik2+α)[R(μi)γ-l(μi)ωikξ]+βωik[R(μi)ωikξ+l(μi)γ](ωik2-α)2+β2ωik2
Thus, denoting
(11)τikj=1ωikarccos(-ωik2+α)[R(μi)γ-l(μi)ωikξ]+βωik[R(μi)ωikξ+l(μi)γ](ωik2-α)2+β2ωik2+2jπωik,
where j=0,1,…, then ±iωi is a pair of purely imaginary roots of gi(λ)=0 with τikj.
Defineτi0=mink=1,2{τik} and τ0=mini=2,…,N{τi0}.Lemma 4 (see [15]).
Consider the exponential polynomial(12)P(λ,e-λτ,…,e-λτm)=λn+p1(0)λn-1+⋯+pn-1(0)λ+pn(0)+[p1(1)λn-1+⋯+pn-1(1)λ+pn(1)]e-λτ+⋯+[p1(m)λn-1+⋯+pn-1(m)λ+pn(m)]e-λτm,
where τi≥0 (i=1,2,…,m) and pj(i)(j=1,2,…,m) are constants. As (τ1,τ2,…,τm) vary, the sum of  the order of the zeros of P(λ,e-λτ,…,e-λτm) on the open right half plane can change only if a zero appears on or crosses the imaginary axis.
Let(13)δ=max2≤i≤N{-2αβ2+4Re(μi)αβξ-2Re2(μi)αξ2-2Re(μi)β3ξ+2Re(μi)β2γ+Re2(μi)β2ξ2-2Re3(μi)βξ3-2[2Re2(μi)+Im2(μi)]βγξ+2Re(μi)[Re2(μi)+Im2(μi)]ξ2γ+2Im2(μi)γ2}.Lemma 5.
Suppose that the network contains a directed spanning tree, and all the roots of (5) have negative real parts if and only if the following conditions are satisfied: δ<0 and τ∈[0,τ0).Proof.
Forτ=0, (5) can be rewritten in the following form:
(14)∏i=1N[λ2+(β-ξμi)λ+α-γμi]=0.
Therefore, the roots of (14) satisfy
(15)λ2+(β-ξμi)λ+α-γμi=0.
We know that each eigenvalue of -L, μi, corresponds to two eigenvalues of Q, denoted by λi±. Their relationships can be described by
(16)λi±=-β+ξμi±(β-ξμi)2-4(α-γμi)2,i=1,2,…,N.
From Lemma 2, one knows that -L has a simple zero eigenvalue, and all the other eigenvalues have negative parts if and only if the directed network g has a directed spanning tree. That is to say, Re(λi±)<0, i=2,…,N. For convenience, let (β-ξμi)2-4(α-γμi)=c+id, where c,d are real numbers, and i=-1. It follows from (16) that Re(λi±)<0 implies (-β+ξRe(μi)±c)/2<0, i=2,…,N. This is equivalent to the following two inequalities ξRe(μi)-β<c<-ξRe(μi)+β and Re(μi)<0  which hold simultaneously. Therefore,
(17)c2<ξ2Re2(μi)+β2-2ξβRe(μi),i=2,3,…,N.
Also note that(β-ξμi)2-4(α-γμi)=c2-d2+i2cd.  By some calculations and separating the real and imaginary parts, one obtains
(18)β2+ξ2Re2(μi)-ξ2Im2(μi)-2βξRe(μi)-4α+4γRe(μi)=c2-d2,ξ2Re(μi)Im(μi)-βξIm(μi)+2γIm(μi)=cd.
It follows from (18) that
(19)c4-Bc2-A=0,
where
(20)B=β2+ξ2Re2(μi)-ξ2Im2(μi)-2βξRe(μi)-4α+4γRe(μi),A=[ξ2Re(μi)Im(μi)-βξIm(μi)+2γIm(μi)]2.
Solving (19) and combining (17) yield
(21)c2=B±B2+4A2<ξ2Re2(μi)+β2-2ξβRe(μi),i=2,3,…,N.
After some simplifications, we can derive that the inequality δ<0 in Lemma 5 holds. Using Lemma 4 and similar to the approach in [22, 23], we complete the proof.Summarizing the previous discussions, we have the following theorem.Theorem 6.
Suppose that the network contains a directed spanning tree; we have the following results.(1)
Ifmax{∥μi∥2ξ2+2α}<β2,max{∥μi∥2r2}<α2, and δ<0, the second-order consensus in system (1) is achieved.(2)
Ifmin{∥μi∥2ξ2+2α}>β2,  δ<0 and τ∈[0,τ0), the second-order consensus in system (1) is achieved.Corollary 7.
Forα=β=0, γ,ξ>0, and τ>0, second-order consensus in multiagent system (1) can be achieved if and only if the network contains a directed spanning tree and
(22)ξ2γ>max2≤i≤N{Im2(μi)-Re(μi)[Re2(μi)+Im2(μi)]},τ<τ0=min2≤i≤N{θi1ωi1},
where μi are nonzero eigenvalues of matrix -L, i=2,3,…,N. In [13], Yu et al. studied the second-order consensus under the linear protocol:
(23)ui(t)=γ∑j∈Niaij(rj(t)-ri(t))+ξ∑j∈Niaij(vj(t)-vi(t)),i=1,2,…,N,
and obtained the similar conclusions as Corollary 7. Therefore, Theorem 6 can be viewed as the extension of the results in [13].Corollary 8.
Forτ=0, second-order consensus in multiagent system (1) can be achieved if and only if the network contains a directed spanning tree and δ<0. In [15], Zhu investigated the second-order consensus under the linear protocol:
(24)ui(t)=-αri(t)-βvi(t)+γ∑j∈Niaij(rj(t)-ri(t))+ξ∑j∈Niaij(vj(t)-vi(t)),i=1,2,…,N,
and obtained the similar conclusions as Corollary 8. Therefore, Theorem 6 can be viewed as the extension of the results in [15].


## 4. Simulation Examples

In this section, some numerical results of simulating system (1) are given to verify the theorems obtained earlier. Consider the network (1) with the topology shown in Figure 1. In Figure 1, the adjacency matrix A and the Laplacian matrix L of directed network g are given in (25). Moreover, it is easily to see that there exists a directed spanning tree Figure 1. With simple calculations, we obtain the eigenvalues of -L, μ1=0,  μ2=-1+i,  μ3=-1-i,  μ4=-2,  and  μ5=-2. Consider
(25)A=[0110000100000100000101000],L=[2-1-10001-100001-100001-10-1001].
Let us set the parameters of the system (1) as follows: α=0.1,  β=0.2,  γ=0.5, and  ξ=1.  According to (11) and Lemma 5, we obtain τ0=0.3939 andδ=-0.3962<0.Figure 1
The directed interaction topology of five agents.Considerτ=0.39<τ0; from Theorem 6, we know that the second-order consensus can be reached. The position and velocity states of all the agents are shown in Figure 2. It is easy to see that the consensus of all agents is achieved.Velocity and position states of five agents in a network under linear consensus protocols whereτ=0.39<τ0.
(a)
(b)Considerτ=0.394>τ0; from Theorem 6, we know that the second-order consensus cannot be reached. The position and velocity states of all the agents are shown in Figure 3. It is easy to see that the consensus of all agents is not achieved.Velocity and position states of five agents in a network under periodic consensus protocols whereτ=0.394>τ0.
(a)
(b)


## 5. Conclusions

In this paper, the convergence of the second-order consensus of multiagent systems composed of coupled double-integrators dynamics and coupling time delay has been studied. The advantage of the considered protocol is that it can be treated as the extensions of most linear local interaction protocols in the existing literatures. By combining algebraic graph theory and matrix theory and studying the distribution of the eigenvalues of the associated characteristic equation, some necessary and sufficient conditions are derived for reaching the second-order consensus. Several simulation results further validate the effectiveness of theoretical analysis.



---

*Source: 590894-2013-03-28.xml*