# Collective Coordination of High-Order Dynamic Multiagent Systems Guided by Multiple Leaders

Authors: Xin-Lei Feng; Ting-Zhu Huang; Jin-Liang Shao
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

For second-order and high-order dynamic multiagent systems with multiple leaders, the coordination schemes that all the follower agents flock to the polytope region formed by multiple leaders are considered. Necessary and sufficient conditions which the follower agents can enter the polytope region by the leaders are obtained. Finally, numerical examples are given to illustrate our theoretical results.


---

## Body

## 1. Introduction

Recently, collective coordinations of multiagent systems have received significant attention due to their potential impact in numerous civilian, homeland security, and military applications, and so forth. For example, Wei et al. [1] described a multiagent recommender system in which the agents form a marketplace and compete to provide the best recommendation for a given user. De Meo et al. [2] presented an XML-based multiagent system for supporting e-recruitment services, in which the various agents collaborate to extract data and rank them according to user queries and needs.Consensus plays an important role in achieving distributed coordination. The basic idea of consensus is that a team of vehicles reaches an agreement on a common value by negotiating with their neighbors. Consensus algorithms are studied for both first-order dynamics [3–5] and high-order dynamics [6–10].Formal study of consensus problems in groups of experts originated in management science and statistics in 1960s. Distributed computation over networks has a tradition in systems and control theory starting with the pioneering work of Borkar and Varaiya [11] and Tsitsiklis [12] in 1980s. In 1995, Vicsek et al. [13] provided a formal analysis of emergence of alignment in the simplified model of flocking. Due to providing Vicsek Model, [13] has an important influence on the development of the multiagent systems consensus theory. On the study of consensus of continuous-time system, the classical model of consensus is provided by Olfati-Saber and Murray [14] in 2004.In multiagent coordination, leader-follower is an important architecture. Hu and Yuan [15] presented a first-order dynamic collective coordination algorithm of multiagent systems guided by multiple leaders, which make all the follower agents flock to the polytope region formed by the leaders. In this paper, we consider the second-order and high-order dynamic collective coordination algorithms of multiagent systems guided by multiple leaders.


## 2. Preliminaries

A directed graph (digraph)G=(V,E) of order n consists of a set of nodes V={1,…,n} and a set of edges E=V×V. (j,i) is an edge of G if and only if (j,i)∈G. Accordingly, node j is a neighbor of node i. The set of neighbors of node i is denoted by 𝒩i(t). Suppose that there are n nodes in the graph. The weighted adjacency matrix A∈ℝn×n is defined as aii=0,aij≥0, and aij>0 if and only if (j,i)∈E. A graph with the property that (i,j)∈E implies (j,i)∈E is said to be undirected. The Laplacian matrix L∈ℝn×n is defined as lii=∑j≠iaij,lij=-aij, for i≠j. Moreover, matrix L is symmetric if an undirected graph has symmetric weights, that is, aij=aji.In this paper, we consider a system consisting ofn follower-agents and k leaders, and the interconnection topology among them can be described by an undirected graph G¯. Where each follower-agent (or leader) is regarded as a node in a graph G¯=(V¯,E¯), and each available information channel between the follower-agent (or leader) i and the follower-agent (or leader) j corresponds to a couple of edges (i,j),(j,i)∈E¯. (i,j)∈E¯ is said that i and j is connected. Moreover, the interconnection topology among follower-agents can be described by an undirected graph G. The undirected graph G¯ is connected; we mean that at least one node in each component of G is connected to the nodes who are leaders. A diagonal matrix B to be a leader adjacency matrix associate with G¯ with diagonal elements bi(i∈{1,…,n}) such that each bi is some positive number if agent i is connected to the leader node and 0 otherwise.LetS⊂ℝm, S is said to be convex if (1-γ)x+γy∈S whenever x∈S,y∈S and 0<γ<1. A vector sum γ1x1+γ2x2+⋯+γnxn is called a convex combination of x1,…,xn, if the coefficients γi are all nonnegative and γ1+⋯+γn=1. The intersection of all convex sets containing S is the convex hull of S. The convex hull of a finite set of points x1,…,xn∈ℝm is a polytope [16].The Kronecker product ofA=[aij]∈Mm,n(F) and B=[bij]∈Mp,q(F) is denoted by A⊗B and is defined to be the block matrix [17]Lemma 2.1 (see [4]).
(i) All the eigenvalues of Laplacian matrixL have nonnegative real parts; (ii) Zero is an eigenvalue of  L with  1n (where  1n is the  n×1 column vector of all ones) as the corresponding right eigenvector. Furthermore, zero is a simple eigenvalue of  L if and only if graph  G has a directed spanning tree.


## 3. Coordination Algorithms That All the Follower-Agents Flock to the Polytope Region Formed by the Leaders

A continuous-time second-order dynamics ofn follower-agents is described as follows:(3.1)ẋi=vi,v̇i=ui,
where xi,vi∈ℝm are the position and velocity of follower-agent i. We consider the following dynamical protocol:(3.2)ui=∑j∈Niaij(xj-xi)+∑q=1kbiq(x0q-xi)+∑j∈Niaij(vj-vi)+∑q=1kbiq(v0q-vi),
where x0j,v0j(j=1,…,k) are the position and velocity of the leader j, nonnegative constant biq>0 if and only if follower-agent i is connected to leader q(q=1,…,k). The objective of this paper is to lead all the follower-agents to enter the polytope region formed by the leaders, namely, xi,i=1,…,n, will be contained in a convex hull of x0q,q=1,…,k, as t→∞.Furthermore, (3.1) and (3.2) can be rewritten as vector form:(3.3)ẋ=v,v̇=-(H⊗Im)x+[B(Ik⊗1n)]⊗Imx0-(H⊗Im)v+[B(Ik⊗1n)]⊗Imv0,
where H=L+B(1k⊗In), Bq∈ℝn×n is a diagonal matrix with diagonal entry biq, and B=[B1⋯Bk]∈ℝn×nk.Theorem 3.1.
For the multiagent systems given by (3.1) and (3.2), the follower-agents can enter the polytope region formed by the leaders if and only if  G¯ is connected.Proof.
Sufficiency: Let
(3.4)x¯=x-[H-1B(Ik⊗1n)]⊗Imx0,v¯=v-[H-1B(Ik⊗1n)]⊗Imv0.
Then, (3.3) can be rewritten as
(3.5)x¯̇=v¯,v¯̇=-(H⊗Im)x¯-(H⊗Im)v¯.
Further, (3.5) can be rewritten as
(3.6)(x¯̇v¯)=(0mn×mnImn-(H⊗Im)-(H⊗Im))(x¯v¯).
Let λ be an eigenvalue of Γ=(0mn×mnImn-H⊗Im-H⊗Im), and (fg) be the corresponding eigenvector of Γ. Then we get
(3.7)(0mn×mnImn-H⊗Im-H⊗Im)x=λx,
which implies
(3.8)g=λf,-(H⊗Im)f-(H⊗Im)g=λg.
Let μi,i=1,…,n be the eigenvalues of H⊗Im. Thus,
(3.9)-(H⊗Im)f-(H⊗Im)λf=λ2f.
That is, each eigenvalue of H⊗Im, μi>0 ([11, Lemma 1]), corresponds to two eigenvalues of Γ, denoted by
(3.10)λ2i-1,2i=-μi±μi2-4μi2.
From (3.10), we can obtain that all the eigenvalues of Γ have negative real parts. By (3.6), we can get
(3.11)(x¯v¯)=eΓt(x¯(0)v¯(0)),
which implies that x¯→0 and v¯→0 when t→∞. Therefore,
(3.12)x=[H-1B(Ik⊗1n)]⊗Imx0,v=[H-1B(Ik⊗1n)]⊗Imv0.
We also know that [H-1B(Ik⊗1n)]⊗Im is a row-stochastic matrix which is a nonnegative matrix and the sum of the entries in every row equals 1 [15]. So the follower-agents can enter the polytope region formed by the leaders.
Necessity: If G¯ is not connected, by the definition of connectivity, then some follower-agents, without loss of generality, are denoted by xi,i=1,…,l(0<l<n), will not get information from the leaders, and the other follower-agents xj,j=l+1,…,n. Then these follower-agents xi,i=1,…,l will not get any position information about leaders. Therefore, follower-agents xi,i=1,…,l can not enter the polytope region formed by the leaders. So G¯ must be connected.Remark 3.2.
(1) For switching network topologies of multiagents systems, if topologies are finite, and the shift is made in turn, then the system given by (3.1) and (3.2) is still asymptotically convergence.
(2) The system given by (3.1) can solve formation control of network. This can be made by the following protocol.(3.13)ui=∑j∈Niaij(xj-xi-fij)+∑q=1kbiq(x0q-xi)+∑j∈Niaij(vj-vi)+∑q=1kbiq(v0q-vi),
where fij can be decomposed into fij=fi-fj for any i,j=1,…,n,  fi and fj are some specified constants. Let(3.14)x̃=xi-fi,v0i=v0j,i,j=1,…,m.
Then Protocol (3.13) has the same form as (3.2), and the system will asymptotically converge. By choosing suitable fi and fj, we can obtain on appropriate formation of network.In the following, a continuous-time high-order dynamics ofn follower-agents system are considered.Consider multiagent systems with l-th(l≥3) order dynamics given by(3.15)ẋi(0)=xi(1),⋮ẋi(l-2)=xi(l-1),ẋi(l-1)=ui,
where xi(d)∈ℝm,  d=0,…,l-1 are the states of follower-agents, ui∈ℝm is the control input, and xi(d) denotes the k-th derivation of xi, with xi(0)=xi, i=1,…,n. We consider the following dynamical protocol:(3.16)ui=∑j∈Niaij[∑d=ol-1(xj(d)-xi(d))]+∑q=1kbiq∑d=0l-1(xq0(d)-xi(d)),
where xq0(d),  q=1,…,k, are the states of the leaders, xq0(d) denotes the d-th derivation of xq0.Furthermore, the above equations can be rewritten as vector form:(3.17)ẋ(0)=x(1),⋮ẋ(l-2)=x(l-1),(3.18)ẋ(l-1)=-∑d=ol-1(H⊗Im)x(d)+∑d=ol-1[B(Ik⊗In)]⊗Imx0(d),
where H=L+B(1k⊗In),  x=[x1T⋯xnT]T and x0=[x10T⋯xk0T]T.Denotex¯=[x¯1T⋯x¯lT]T and x¯0=[x¯01T⋯x¯0lT]T as the stacked vector of the follower-agents' states and the leaders' states, respectively,(3.19)x¯s=[(x1(s-1))T⋯(xn(s-1))T]T,x¯0s=[(x10(s-1))T⋯(xk0(s-1))T]T,s=1,…,l,
and x0=x¯01. Then the above equations can be rewritten as(3.20)x¯=Γx¯+Υx¯0,
where
(3.21)Γ=(0mn×mnImn0mn×mn⋯0mn×mn0mn×mn0mn×mnImn⋯0mn×mn0mn×mn0mn×mn0mn×mn⋯0mn×mn⋮⋮⋱⋮-H⊗Im-H⊗Im-H⊗Im⋯-H⊗Im),(3.22)Υ=(0nm×km0nm×km0nm×km⋯0nm×km0nm×km0nm×km0nm×km⋯0nm×km0nm×km0nm×km0nm×km⋯0nm×km⋮⋮⋱⋮ΛΛΛ⋯Λ),Λ=[B(Ik⊗1n)]⊗Im.
Let x̃=x¯-Il⊗{[H-1B(Ik⊗1n)]⊗Im}x¯0. Then (3.20) can be written as(3.23)x̃̇=Γx̃.For high-order dynamic systems (3.23), we have the following theorem.Theorem 3.3.
For the multiagent system (3.23), the follower-agents can enter the polytope region formed by the leaders, if and only if  G¯ is connected and  λl+μiλl-1+⋯+μi is Hurwitz stable, where  μi,   i=1,…,mn are eigenvalues of  H⊗Im.Proof.
Sufficiency. Let λ be an eigenvalue of Γ, and x̃=[x̃1T⋯x̃lT]T be the corresponding eigenvector of Γ. Then we get
(3.24)x̃2=λx̃1,x̃3=λx̃2,⋯x̃l=λx̃i-1-H⊗Imx̃1-H⊗Imx̃2-⋯-H⊗Imx̃l=λx̃l.
Furthermore, we have
(3.25)-H⊗Imx̃1-λH⊗Imx̃1-⋯-λl-1H⊗Imx̃l=λlx̃l.
Let μi,i=1,…,n be the eigenvalues of H⊗Im. Then we get characteristic equation of Γ(3.26)λl+λl-1μi+⋯+μi=0.
By (3.23), we get
(3.27)x̃=eΓtx̃(0).
If λl+λl-1μi+⋯+μi is Hurwitz stable, then all the eigenvalues of Γ have negative real parts. Therefore, x̃→0, when t→∞. So
(3.28)x¯=Il⊗{[H-1B(Ik⊗1n)]⊗Im}x¯0.
Thus,
(3.29)x=[H-1B(Ik⊗1n)]⊗Imx0,…,x(l)=[H-1B(Ik⊗1n)]⊗Imx¯0l.[H-1B(Ik⊗1n)]⊗Im is a row stochastic matrix which is a nonnegative matrix and the sum of the entries in every row equals 1, so the follower-agents can enter the region formed by the leaders.
Necessity: Similar to the Proof of Theorem 3.1.


## 4. Simulation

In this section, simulation examples are presented to illustrate the proposed algorithms introduced in Section3.Example 4.1.
We consider a system of five follower-agents guarded by three leaders with the topologyG¯1 in Figure 1. The corresponding weights of edges of G¯1 are shown in Figure 1. Moreover, the initial positions and velocities of follower-agents and leaders are given as follows:
(4.1)x1(0)=(22),x2(0)=(33),x3(0)=(11),x4(0)=(11),x5(0)=(22),v1(0)=(22),v2(0)=(33),v3(0)=(11),v4(0)=(11),v5(0)=(33),x01(0)=(23),x02(0)=(32),x03(0)=(43),v01=(0.10.4),v02=(0.10.4),v03=(0.10.4),B=(100000000000000000000000001000000000000000000000000000000000000000000100000).Figure 1
Network topologyG¯1 of a multiagent system.Figure2 is position trajectories of the agents. In Figure 2, the red lines are the trajectories of the three leaders, and the others are the trajectories of the five follower-agents. From Figure 2, we can obtain that the five follower-agents can enter the polytope region formed by three leaders as the time t gradually increasing.Figure 2
Trajectories of the agents in the multiagent system with topologyG¯1 under the condition that the leaders have the same velocity.The velocities of leaders have no effect on follower-agents' flocking to the polytope region formed by leaders. We consider the following simulation for the same multiagent system as the above example. The network topology of multiagents is stillG¯1 in Figure 1. The initial positions and velocities of follower-agents, the initial positions of leaders and the corresponding weights of edges of G¯1 are the same as the above example, and only the velocities of leaders are changed as(4.2)v01=(12),v02=(23),v03=(-1-2),
Figure 3 is trajectories of the agents. The red lines are the trajectories of the three leaders, and the others are the trajectories of the five follower-agents. From Figure 3, though the velocities of leaders are different, we can still obtain that the five follower-agents can enter the polytope region formed by three leaders as the time t gradually increasing. The final states of the follower-agents are consistent with Theorem 3.1.Figure 3
Trajectories of the agents in the multiagent system with topologyG¯1 under the condition that the leaders have different velocities.Example 4.2.
We consider a system of five follower-agents guarded by four leaders with the topologyG¯2 in Figure 4. The corresponding weights of edges of G¯2 are shown in Figure 4. Moreover, the initial positions and velocities of leaders are given as follows:
(4.3)x01(0)=(23),x02(0)=(32),x03(0)=(43),x04(0)=(63),v01(0)=(0.10.4),v02(0)=(0.10.4),v03(0)=(0.10.4),v04(0)=(31),(4.4)B=(1000000000000000000000000000000100000000000000000000000000000000000000000000001000000000010000000000).
Likewise, the initial positions and velocities of follower-agents are the same as those in Example 4.1. The topology G2 of follower-agents is not connected, according to the definition in Preliminaries, but G¯2 is connected.
In Figure5, the red lines are the trajectories of the four leaders, and the others are the trajectories of the five follower-agents. From Figure 5, we can obtain that the five follower-agents can enter the polytope region formed by four leaders as the time t gradually increasing.Figure 4
Network topologyG¯2 of a multiagent system.Figure 5
Trajectories of the agents in the multiagent system with topologyG¯2.


## 5. Conclusion

In this paper, we consider the second order and high-order dynamic collective coordination algorithms of multiagent systems guided by multiple leaders. We give the necessary and sufficient conditions which follower-agents can enter the polytope region formed by leaders. Numerical examples are given to illustrate our theoretical results.



---

*Source: 791052-2011-06-01.xml*