# Cluster Consensus on Discrete-Time Multi-Agent Networks

Authors: Li Xiao; Xiaofeng Liao; Huiwei Wang
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

Nowadays, multi-agent networks are ubiquitous in the real world. Over the last decade, consensus has  received an increasing attention from various disciplines. This paper investigates cluster consensus for discrete-time multi-agent networks. By utilizing a special coupling matrix and the Kronecker product, a criterion based on linear matrix inequality (LMI) is obtained. It is shown that the addressed discrete-time multi-agent networks achieve cluster consensus if a certain LMI is feasible. Finally, an example is given to demonstrate the effectiveness of the proposed criterion.


---

## Body

## 1. Introduction

In recent years, the consensus problem of coordinating the motion of multi-agent networks has attracted great attention. Research on multi-agent consensus not only helps in better understanding the general mechanisms and interconnection rules of natural collective phenomena, but also benefits broad applications of multi-agent systems in many areas including cooperative control of unmanned air vehicles [1], formation control [2], flocking [3], and attitude alignment of clusters of satellites [4].Consensus, along with stability [5] and bifurcation [6], is fundamental phenomenon in nature [7]. Consensus problem can refer to how to make the states of multi-agent networks reach an agreement on a common value regarding a certain quantity of interest, especially by negotiating with their neighbors. To realize consensus, many effective approaches were proposed [8–10]. Since the network can be regarded as a graph, the issues can be depicted by the graph theory. The recent approaches concentrate on matrix analysis [11], convex analysis [12], and graph theory [13]. Especially the concept of spanning tree is widely used to describe the communicability between agents in networks that can guarantee the consensus [14, 15]. For more consensus problem, the reader may refer to [16] and the references therein.Cluster synchronization, as a particular synchronization, is firstly explored by In Belykh and his colleagues for the coupled chaotic oscillators [17], in which the synchronization occurs in each group but there is no synchronization among the different groups. Now, cluster synchronization has become one of the hottest topics of discussion partly due to that it is considered to be more momentous than other synchronization types in broad areas including brain science and engineering, social science, and distributed computation. Some papers concerning the cluster synchronization have been published [18–21]. In [19], cluster synchronization of linearly coupled complex networks has been investigated under an adaptive strategy, whereas the similar topic has been addressed in [20] by employing a pinning controller. For more studies concerning cluster synchronization, please see [21] and the references therein.Of note is that nonlinear oscillators are commonly introduced in complex networks and their synchronization problems are carefully studied [22]. Motivated by that and utilizing the cluster synchronization phenomenon in complex networks, this paper aims to further investigate the cluster consensus of multi-agent networks. Roughly speaking, similar to the cluster synchronization, the cluster consensus means that a multi-agent network consists of multiple clusters where the consensus can be achieved in each cluster, but there is no consensus among the different clusters. To the authors’ knowledge, cluster consensus is a more general concept compared to that traditional consensus and it is also a fundamental phenomenon in the real world, such as the cluster formation of personal opinions, the pattern formation of bacteria colonies, and the emergence of subgroups in a flock of birds or a school of fish [23].For the truth that the discretization process of a continuous-time network cannot preserve the dynamics of the continuous-time part even for small sampling periods [24], and moreover, a discrete-time network is in a better position to model digitally transmitted signals in a dynamical way than its continuous-time analog, so in this paper, we aim to investigate the cluster consensus problem for discrete-time multi-agent networks using the tools from algebraic graph theory, matrix theory, and Lyapunov control approach. A cluster consensus criteria-based linear matrix inequality is obtained. And by expanding the cluster consensus criteria, we obtain the global consensus criteria of the multi-agent networks.The remainder of the paper is organized as follows. In Section2, some necessary preliminaries and the model formulation are given. Cluster consensus of multi-agent networks with nonsymmetric coupling matrix is discussed in Section 3. In Section 4, numerical simulations are also given to validate the proposed cluster consensus criteria. Finally, some concluding remarks are stated in Section 5.


## 2. Preliminaries and Model Formulation

Suppose that the multi-agent networks under consideration consist ofN agents, which update their states based on local information exchange. To study the consensus problem for directed coupled nonlinear networks, we consider the following consensus protocol for discrete-time multi-agent network, which was also proposed in [25]:
(2.1)xi(k+1)=f(xi(k))+∑j=1NGijΓg(xj(k)),i=1,2,…,N,
where xi(k)=(xi1(k),xi2(k),…,xin(k))T denotes the state of agent i. f(·) and g(·) are vector-valued functions, which represent the dynamics of the agents. Γ=diag{γ1,γ2,…,γn}≥0 is the connection weight matrix, where γj≠0. Gij∈RN×N denotes the inner coupling configuration matrix satisfying
(2.2)Gii=∑j=1,j≠iNGij,i,j=1,2,…,N.
In the following, we present the following assumptions and definitions.Assumption 2.1.
For the nonlinear vector-valued functionsf(·) and g(·), the following conditions hold:(1)
f(·) and g(·) are continuous,(2)
[f(α)-f(β)-U1(α-β)]T[f(α)-f(β)-U2(α-β)]≤0,∀α,β∈R, [g(α)-g(β)-V1(α-β)]T[g(α)-g(β)-V2(α-β)]≤0, ∀α,β∈R,
whereU1, U2, V1, and V2 are constant matrices.Assumption 2.2.
The coupling matrix satisfying(2.3)G=[N11N12⋯N1tN21N22⋯N2t⋮⋮⋱⋮Nt1Nt2⋯Ntt],
where Nii∈Rmi×mi, Nij∈Rmi×mj, i,j=1,2,…,t, have the same row vectors. For example, Nij=(μ,μ,…,μ)T, where μ=(μ1,μ2,…,μmj)T is a vector.Definition 2.3.
The setS*={x=(x1(s),x2(s),…,xN(s)):xi(s)∈C(N[-ρ,0],RN), xj(s)(∀i,j=1,2,…,N)}, is called a global consensus manifold.Definition 2.4.
The setS={x=(x1(s),x2(s),…,xN(s)):xi(s)∈C(N[-dM,0],RN),  [x1(s)=x2(s)=⋯=xm1(s)],  [xm1+1(s)=xm1+2(s)=⋯=xm1+m2(s)],…,[xm1+m2+⋯+mt-1+1(s) = xm1+m2+⋯+mt-1+2(s)=⋯=xm1+m2+⋯+mt-1+mt(s)],  m1+m2+⋯+mt=N} is called cluster consensus manifold.Definition 2.5.
A multi-agent network consisting ofN agents is said to achieve cluster consensus if, for the N, nodes are divided into several different clusters, such as {(1,2,…,m1),(m1+1,m1+2,…,m1+m2),…,   (m1+m2+⋯+mt-1+1,m1+m2+⋯+mt-1+2,…,m1+m2+⋯+mt),  m1+m2+⋯+mt=N}, each node synchronizes with one another in the same cluster, which means any two different agents xi(k) and xj(k) satisfying the condition limk→+∞∥xi(k)-xj(k)∥=0.Definition 2.6 (see [7]).
LetR~ denote a ring, and T~(R~,K~)=  {the set of matrices with entries R~ such that the sum of the entries in each row is equal to K~ for some K~∈R~}.Lemma 2.7 (see [7]).
LetG be an N×N matrix in the set T~(R~,K~). When the (N-1)×(N-1) matrix H satisfies MG=HM, where H=MGJ, and
(2.4)M=[1-11-1⋱1-1](N-1)×N,J=[111⋯1011⋯1⋮⋮⋮⋱⋮0⋯0110⋯0010⋯000]N×(N-1),
in which 1 is the multiplicative identity of R~. For i,j∈1,2,…,N-1, the matrix H can be rewritten explicitly as follows:
(2.5)H(i,j)=∑k=1jG(i,k)-G(i+1,k).Lemma 2.8 (see [18]).
Under Assumption2.2, the matrix H-(N-t)×(N-t) satisfies M-G=H-M-, where H-=M-N-J- and
(2.6)N-=[N11N22⋱Ntt]N×N,M-=[M1M2⋱Mt](N-t)×N,J-=[J1J2⋱Jt]N×(N-t),Nii∈Rmi×mi,Mi∈R(mi-1)×mi,Ji∈Rmi×(mi-1).Lemma 2.9 (see [18]).
x
∈
S if and only if ∥M~x∥=0.


## 3. Main Results

This section focused on the cluster consensus analysis of network (2.1). Before deducing our main results, we first denote the following notations for convenience:
(3.1)xi(k)=(xi1(k),xi2(k),…,xin(k))T∈Rn,i=1,2,…,N,x(k)=(x1T(k),x2T(k),…,xNT(k))T,f~(x(k))=(fT(x1(k)),fT(x2(k)),…,fT(xN(k)))T,g~(x(k))=(gT(x1(k)),gT(x2(k)),…,gT(xN(k)))T,Σ1=U1TU2+U2TU12,Σ2=U1T+U2T2,Σ3=V1TV2+V2TV12,Σ4=V1T+V2T2,G~=G⊗Γ,H-=M-N-J-,H~=H-⊗Γ,Σ~l=EN-t⊗Σl,l=1,2,3,4.With the Kronecker product, the multi-agent network (2.1) can be rewritten in the compact form as
(3.2)x(k+1)=f~(x(k))+G~g~(x(k)).
For the model (3.2), we have the following conclusions.Theorem 3.1.
Suppose Assumptions2.1 and 2.2 hold, the cluster consensus manifold S of the multi-agent network (3.2) is globally attractive if there exit a positive definite matrix P∈R(N-t)n×(N-t)n and two positive scalars δ1 and δ2 such that the following LMI holds:
(3.3)Π=[-P-δ1Σ~1-δ2Σ~3δ1Σ~2δ2Σ~4O*-δ1EnOP**-δ2EnH~TP***-P]<0.Proof.
By Assumption2.1, We can get that (3.4a)[M~x(k)M~f~(x(k))]T[Σ~1-Σ~2-Σ~2En][M~x(k)M~f~(x(k))]≤0,(3.4b)[M~x(k)M~g~(x(k))]T[Σ~3-Σ~4-Σ~4En][M~x(k)M~g~(x(k))]≤0.
Now, we construct the following Lyapunov function candidate for the multi-agent networks (3.2):
(3.5)V(k)=[M~x(k)]TP[M~x(k)].
Calculating the difference ofV(k) along the solution of (3.2), we have
(3.6)ΔV(k)=[M~f~(x(k))+M~G~g~(x(k))]TP[M~f~(x(k))+M~G~g~(x(k))]-[M~x(k)]TP[M~x(k)].
By the structure of M~ and Lemma 2.8, the following equalities are easy to versify:
(3.7)M~G~=(M-⊗En)(G⊗Γ)=M-G⊗Γ=H-M-⊗Γ=(H-⊗Γ)(M-⊗En)=H~M~.
Based on the above, one obtains
(3.8)ΔV(k)=[M~f~(x(k))+H~M~g~(x(k))]TP[M~f~(x(k))+H~M~g~(x(k))]-[M~x(k)]TP[M~x(k)].
Consequently, for the two positive scalars δ1 and δ2, combining (3.4a), (3.4b) and (3.6)-(3.8) give
(3.9)ΔV(k)≤ζT(k)Πζ(k),
where ζ(k)=([M~x(k)]T,[M~f~(x(k))]T,[M~g~(x(k))]T)T.
Noticing (3.3) and (3.9), one has ΔV(k)≤0. And, if ζ(k)≡0, then ΔV(k)=0. Consequently, we have V(k)≤V(0), which implies that V(k) is a bounded function. Thus, ∥M~x(k)∥→0. The proof is completed.Theorem3.1 shows a condition based on the certain linear matrix inequality for the multi-agent networks cluster consensus. From the above analysis, for = 1, one can deduce multi-agent networks global consensus criterion-based LMI as follows.Theorem 3.2.
Suppose Assumptions2.1 and 2.2 hold, the global consensus manifold S* of the multi-agent network (3.2) is globally attractive if there exit a positive definite matrix P∈R(N-t)n×(N-t)n and a positive scalar δ1 so that the following LMI holds:
(3.10)Π=[-P-δ1Σ~1-δ2Σ~3δ1Σ~2δ2Σ~4O*-δ1EnOP**-δ2EnH~TP***-P]<0.Proof.
The proof is similar to that of Theorem3.1 and thus omitted here. Thus, the proof is completed.


## 4. Numerical Example

In this section, we present an example to validate the theoretical results on the cluster consensus problems for discrete-time multi-agent networks in Section3.For simplicity, consider the network (3.2) of six nodes. Let n=2,
(4.1)Γ=[0.5000.5],G=[-0.30.298000.0010.0010.298-0.3000.0010.0010.0010.001-0.350.348000.0010.0010.348-0.35000.0020.00200-0.50.4960.0020.002000.496-0.5].
Denote the nonlinear vector-valued function
(4.2)f(xi(k))=g(xi(k))=(-0.1xi1(k)+tanh(0.2xi1(k))+0.2xi2(k),1.05xi2(k)-tanh(0.75xi2(k)))T.
Then, by simple calculations, we obtain
(4.3)Σ~1=Σ~3=[-0.10.201.05],Σ~2=Σ~4=[0.10.200.3].By using the MATLAB LMI Tool Box, (3.2) can be solved with the following feasible solutions:
(4.4)δ1=30.5215,δ2=22.4917,P=[19.6071-0.63330000-0.633312.905700000019.5325-0.62500000-0.625012.858300000019.2432-0.59940000-0.599412.6664].Therefore, according to Theorem3.1 and Definition 2.5, multi-agent networks (3.2) with given parameters reach the cluster consensus, and the agents in different clusters achieve different consensus states. In Figure 1, the time responses of the state variables xi1(k) and xi2(k)(1≤i≤6) can be easily in the network. For further validation, we denote the error functions as follows:
(4.5)e1-2(k)=∑i=12(x1i(k)-x2i(k))2,e3-4(k)=∑i=12(x3i(k)-x4i(k))2,e5-6(k)=∑i=12(x5i(k)-x6i(k))2,e(k)=∑i=12∑j=26(x1i(k)-xji(k))2.Cluster consensus of the state variablesxi1(k) and xi2(k)(1≤i≤6) in the discrete-time multi-agent network (2.1).
(a)
(b)From the above error functions, we can easily obtain the consensus error of each cluster and the consensus error of the whole multi-agent network, where the consensus error of the whole multi-agent network is illustrated in Figure2. Moreover, from Figure 1, the discrete-time multi-agent network (2.1) is divided into three cluster consensus manifolds, which can further verify the effectiveness of Theorem 3.1 and expand the useful range. Note that Figures 1 and 2 shows that the whole network does not reach global consensus, but each of the three clusters reaches consensus in its own group.Figure 2
Consensus error of the state variables in the discrete-time multi-agent network (2.1).If we take the coupling matrix as(4.6)G=[-0.50.10.10.10.10.10.1-0.50.10.10.10.10.10.1-0.50.10.10.10.10.10.1-0.50.10.10.10.10.10.1-0.50.10.10.10.10.10.1-0.5],
the other functions and parameters are unaltered. According to Theorem 3.2, multi-agent networks (3.2) with given parameters can reach the global consensus, which has been shown in Figure 3, and the consensus error of the whole multi-agent network is illustrated in Figure 4. From there, the global consensus of the state variables xi1(k) and xi2(k)(1≤i≤6) can be easily seen in the network. By using the MATLAB LMI Tool Box, (3.2) can be solved; however, they are omitted due to the space limitation.Global consensus of the state variablesxi1(k) and xi2(k)(1≤i≤6) in the discrete-time multi-agent network (2.1).
(a)
(b)Figure 4
Consensus error of the state variables in the discrete-time multi-agent network (2.1).


## 5. Conclusion

This paper has further investigated the cluster consensus of discrete-time multi-agent networks with nonsymmetric coupling matrix. A cluster consensus criterion with the certain LMI form is obtained by using the tools from the Lyapunov control approach, special coupling matrix, and the Kronecker product. Moreover, by expanding the cluster consensus criteria, we have the global consensus criteria of the multi-agent networks. Finally, the numerical simulations are also given to validate the proposed criteria. In our future work, we will further explore the theoretical analysis of the cluster consensus on discrete-time multi-agent networks with switched topology. Moreover, the method in this paper can be extended to aid the consensus problem of multi-agent networks with the intrinsic nonlinear dynamics of the agents incorporating the effects of time-delay, impulse and so on.



---

*Source: 274735-2012-10-22.xml*