# Controllability of Multiagent Systems with a Directed Tree

Authors: Li Wang; Xiao Han
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper addresses the controllability problem of multiagent systems with a directed tree based on the classic agreement protocol, in which the information communication topologies being a directed tree and containing a directed tree are both investigated. Different from the literatures, a new method, the star transform, is proposed to study the controllability of multiagent systems with directed topology. Some sufficient and necessary conditions are given for the controllability of such multiagent system. Numerical examples and simulations are proposed to illustrate the theoretical results.


---

## Body

## 1. Introduction

Distributed coordination of multiple dynamic agents systems has become a hot topic of major interest [1–6] in recent years. Studies in this direction have been greatly inspired by the cooperative behavior in nature, such as bird flocks, fish schools, ant swarms, and bacteria colonies [7], as well as being driven by the broad applications in engineering fields [8–16], such as cooperative control of unmanned air vehicles (UAVs), schooling of underwater vehicles, formation control of multirobots, attitude alignment of satellite clusters, and congestion control of communication networks [17].The controllability issue of multiagent systems is a key problem for coordinated control of multiagent systems and shows new features and difficulties. In general, the controllability of a multiagent network refers to transferring the follower agents of such system from any arbitrary initial states to any final state by controlling dynamics of leader agents under exchanged information between each other, in which the interplay between network topologies and agent dynamics plays an important role related to the controllability. The controllability problems were investigated for single-integrator kinematics [17, 18], double-integrator dynamics [19], and high-order-integrator dynamics [20], respectively.In 2004, Tanner [17] first studied a simple interconnected system model with a single leader that consists of multiple mobile agents with one-integrator dynamics, interconnected through nearest-neighbor rules. A necessary and sufficient condition was obtained for such system with fixed topology to be controllable by regulating the behaviors of the leader, which is assumed to be able to affect its neighbors but not be affected by other group members. In [18, 21], Liu et al. developed the controllability of the discrete system with switching topology and a single leader. The controllability of multiagent systems with multiple leaders based on fixed topology and switching topology was investigated in [22] and [23], respectively. Furthermore, the controllability of multiagent systems with double-integrator dynamics [19] and high-order-integrator dynamics [20] is studied.Notice that the results of [24–31] were studied based on an undirected nearest-neighbor topology. However, for the case of networks with directed topologies, as often encountered in practice, it is very hard to solve the controllability problems due to the complexity of the topology and make the controllability of dynamic networks an nontrivial new problem. To date, very few results available in the literature [32] for the controllability of multiagent systems with directed topologies were found. In the context of multiagent networks, we have focused on studying the controllability of multiagent systems with directed topologies in this paper. Some sufficient and necessary conditions for the controllability of such multiagent system with directed topologies are obtained. Compared to the existing works on the related problems [32], the contributions of this paper are summarized as follows: (1) the topology is directed; (2) a novel method, the star transform, is introduced; and (3) the geometric criteria for controllability of such multiagent system are given.The rest of the paper is organized as follows. Section2 states the problem formulation and some definitions. Section 3 gives the main results on the controllability. Section 4 presents numerical examples and simulation results. Section 5 summarizes the paper.


## 2. Preliminaries and Problem Formulation

### 2.1. Preliminaries

In this section, we briefly recall some basic notations and concepts in graph theory [33] which will be used in this paper.Aweighted directed graphG=(V,E,A) consists of avertex setV={v1,v2,…,vN} and anedge setE={(vi,vj):vi,vj∈V}, where anedge is an ordered pair of distinct vertices of V, and the nonsymmetric weighted adjacency matrix A=[aij], with aij>0 if and only if eij∈E and aij=0 if not. If all the elements of V are unordered pairs, then the graph is called anundirected graph. If vi,vj∈V, and (vi,vj)∈E, then we say that vi and vj are adjacent or vj is a neighbor of vi. The neighborhood set of node vi is denoted by Ni={vj∈V:(vi,vj)∈E}. The number of neighbors of each vertex is itsdegree. A graph is calledcomplete if every pair of vertices is adjacent. Apath of length r from vi to vj in a graph is a sequence of r+1 distinct vertices starting with vi and ending with vj such that consecutive vertices are adjacent. If there is a path between any two vertices of G, then G isconnected.A directed tree is a directed graph, where the node without any parent is called root, and the root can be connected to any other nodes through paths. Other nodes have exactly one parent (e.g., Figure 1).A spanning tree of a digraph is a directed tree formed by graph edges that connect all the nodes of the graph.A binary tree of a digraph is a directed tree with at most two children for every node, and each child is designated as its left child or right child.Ak-ary tree is a directed tree with at most k children for every node. If every node has k children or no children, the k-ary tree is called afullk-ary tree. Thedegree matrixΔ(G) of G is a diagonal matrix with rows and columns indexed by V, in which the (vi,vi)-entry is the degree of vertex vi. The symmetric matrix defined as(1)LG=ΔG-AGis theLaplacian of G. The Laplacian is always symmetric and positive semidefinite, and the algebraic multiplicity of its zero eigenvalue is equal to the number of connected components in the graph. For a weighted directed graph G with n nodes, theout-degree andin-degree of node vi in a weighted directed graph G with n nodes are, respectively, defined as(2)degoutvi=∑j=1naji,deginvi=∑j=1naij.Figure 1
A directed tree.


### 2.2. Problem Formulation

Consider a multiagent system with a directed topology which is a directed tree, composed ofn agents. Choose the first agent (labeled 1) as the root and the remainder n-1 agents (labeled from 2 to n) as children or followers, and each agent moves according to the following dynamics:(3)x˙it=∑j∈Niaijxjt-xit+zi,i=1,…,n,where xi∈R1 is the state of agent i and i∈n_, n_ is the index set (1,2,…,n); Ni is the neighbor set of agent i; A=[aij]∈Rm×m is a matrix describing the interaction or coupling weight between agents, with aij≥0 and aii=0. Since the topology is a directed tree, the root agent plays a special role and is responsible for receiving external input or signal and conveying information to the children agents, and hence in model (3), the external input or signal only acts on the root agent (e.g., Figure 2). So, z1≠0, zi=0, and a1i=0 for ∀i=2,…,n.Figure 2
The topologyG.Letx=(x1,x2,…,xn)T be the state vector of all the agents; then system (3) follows that(4)x˙=Ax+bz1,where(5)A=001×n-1A1n-1×1Aen-1×n-1∈Rn×n,b=10n-1×1∈Rn×1,with(6)A1=a21,a31,…,an1T∈Rn-1×1,Ae=a22⋯a2n⋮⋱⋮an2⋯ann∈Rn-1×n-1.Define a star transform matrixS as(7)S=100⋯01-10⋯0⋮⋮⋮⋱⋮100⋯-1.It can be easily seen thatS=S-1, and for the convenience of matrix operations, we partition S as(8)S=101×n-1ln-1×1Sen-1×n-1.Obviously,Se∈R(n-1)×(n-1) is a negative identity matrix.Denotey=[y1,yeT]T, where ye=[y2,y3,…,yn]T. Let(9)y=Sx,and then we can get y1=x1 and ye=[x1-x2,x1-x3,…,x1-xn]T. Therefore, we can have an equivalent system of system (4) as follows:(10)y˙=SAS-1y+Sbz1.According to block matrix multiplication, we can have(11)y˙1=101×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+101×n-110n-1×1z1=001×n-1101×n-1ln-1×1Sen-1×n-1y1ye+z1=001×n-1y1ye+z1=z1,y˙e=ln-1×1Sen-1×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+ln-1×1Sen-1×n-110n-1×1z1=ln-1×1Sen-1×n-1001×n-10n-1×1Aen-1×n-1Sen-1×n-1y1ye+ln-1×1Sen-1×n-110n-1×1z1=0n-1×1Sen-1×n-1Aen-1×n-1Sen-1×n-1y1ye+ln-1×1z1=Sen-1×n-1Aen-1×n-1Sen-1×n-1ye+ln-1×1z1=Aen-1×n-1ye+ln-1×1z1.Furthermore, we can know(12)y˙=y˙1y˙e=101×n-1ln-1×1Sen-1×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+101×n-1ln-1×1Sen-1×n-110n-1×1z1=001×n-10n-1×1Aen-1×n-1y1ye+11n-1×1z1=A~y+b~z1,where(13)A~=001×n-10n-1×1Aen-1×n-1∈Rn×n,b~=1n×1∈Rn×1.


## 2.1. Preliminaries

In this section, we briefly recall some basic notations and concepts in graph theory [33] which will be used in this paper.Aweighted directed graphG=(V,E,A) consists of avertex setV={v1,v2,…,vN} and anedge setE={(vi,vj):vi,vj∈V}, where anedge is an ordered pair of distinct vertices of V, and the nonsymmetric weighted adjacency matrix A=[aij], with aij>0 if and only if eij∈E and aij=0 if not. If all the elements of V are unordered pairs, then the graph is called anundirected graph. If vi,vj∈V, and (vi,vj)∈E, then we say that vi and vj are adjacent or vj is a neighbor of vi. The neighborhood set of node vi is denoted by Ni={vj∈V:(vi,vj)∈E}. The number of neighbors of each vertex is itsdegree. A graph is calledcomplete if every pair of vertices is adjacent. Apath of length r from vi to vj in a graph is a sequence of r+1 distinct vertices starting with vi and ending with vj such that consecutive vertices are adjacent. If there is a path between any two vertices of G, then G isconnected.A directed tree is a directed graph, where the node without any parent is called root, and the root can be connected to any other nodes through paths. Other nodes have exactly one parent (e.g., Figure 1).A spanning tree of a digraph is a directed tree formed by graph edges that connect all the nodes of the graph.A binary tree of a digraph is a directed tree with at most two children for every node, and each child is designated as its left child or right child.Ak-ary tree is a directed tree with at most k children for every node. If every node has k children or no children, the k-ary tree is called afullk-ary tree. Thedegree matrixΔ(G) of G is a diagonal matrix with rows and columns indexed by V, in which the (vi,vi)-entry is the degree of vertex vi. The symmetric matrix defined as(1)LG=ΔG-AGis theLaplacian of G. The Laplacian is always symmetric and positive semidefinite, and the algebraic multiplicity of its zero eigenvalue is equal to the number of connected components in the graph. For a weighted directed graph G with n nodes, theout-degree andin-degree of node vi in a weighted directed graph G with n nodes are, respectively, defined as(2)degoutvi=∑j=1naji,deginvi=∑j=1naij.Figure 1
A directed tree.


## 2.2. Problem Formulation

Consider a multiagent system with a directed topology which is a directed tree, composed ofn agents. Choose the first agent (labeled 1) as the root and the remainder n-1 agents (labeled from 2 to n) as children or followers, and each agent moves according to the following dynamics:(3)x˙it=∑j∈Niaijxjt-xit+zi,i=1,…,n,where xi∈R1 is the state of agent i and i∈n_, n_ is the index set (1,2,…,n); Ni is the neighbor set of agent i; A=[aij]∈Rm×m is a matrix describing the interaction or coupling weight between agents, with aij≥0 and aii=0. Since the topology is a directed tree, the root agent plays a special role and is responsible for receiving external input or signal and conveying information to the children agents, and hence in model (3), the external input or signal only acts on the root agent (e.g., Figure 2). So, z1≠0, zi=0, and a1i=0 for ∀i=2,…,n.Figure 2
The topologyG.Letx=(x1,x2,…,xn)T be the state vector of all the agents; then system (3) follows that(4)x˙=Ax+bz1,where(5)A=001×n-1A1n-1×1Aen-1×n-1∈Rn×n,b=10n-1×1∈Rn×1,with(6)A1=a21,a31,…,an1T∈Rn-1×1,Ae=a22⋯a2n⋮⋱⋮an2⋯ann∈Rn-1×n-1.Define a star transform matrixS as(7)S=100⋯01-10⋯0⋮⋮⋮⋱⋮100⋯-1.It can be easily seen thatS=S-1, and for the convenience of matrix operations, we partition S as(8)S=101×n-1ln-1×1Sen-1×n-1.Obviously,Se∈R(n-1)×(n-1) is a negative identity matrix.Denotey=[y1,yeT]T, where ye=[y2,y3,…,yn]T. Let(9)y=Sx,and then we can get y1=x1 and ye=[x1-x2,x1-x3,…,x1-xn]T. Therefore, we can have an equivalent system of system (4) as follows:(10)y˙=SAS-1y+Sbz1.According to block matrix multiplication, we can have(11)y˙1=101×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+101×n-110n-1×1z1=001×n-1101×n-1ln-1×1Sen-1×n-1y1ye+z1=001×n-1y1ye+z1=z1,y˙e=ln-1×1Sen-1×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+ln-1×1Sen-1×n-110n-1×1z1=ln-1×1Sen-1×n-1001×n-10n-1×1Aen-1×n-1Sen-1×n-1y1ye+ln-1×1Sen-1×n-110n-1×1z1=0n-1×1Sen-1×n-1Aen-1×n-1Sen-1×n-1y1ye+ln-1×1z1=Sen-1×n-1Aen-1×n-1Sen-1×n-1ye+ln-1×1z1=Aen-1×n-1ye+ln-1×1z1.Furthermore, we can know(12)y˙=y˙1y˙e=101×n-1ln-1×1Sen-1×n-1001×n-1A1n-1×1Aen-1×n-1101×n-1ln-1×1Sen-1×n-1y1ye+101×n-1ln-1×1Sen-1×n-110n-1×1z1=001×n-10n-1×1Aen-1×n-1y1ye+11n-1×1z1=A~y+b~z1,where(13)A~=001×n-10n-1×1Aen-1×n-1∈Rn×n,b~=1n×1∈Rn×1.


## 3. Main Results

In this section, we first give the definition of the controllability of multiagent systems and some lemmas.Definition 1.
A nonzero statex0 of system (4) is controllable at the initial time t0 if there exists a finite time tf and a control input z1(t), such that x(t0)=x0 and x(tf)=0. If any nonzero state x0 of system (4) is controllable, then system (4) is said to be controllable.Lemma 2 (see [2]).
System (4) is controllable iff Qc has row full rank, where the controllability matrix of system (4) is defined as(14)Qc=b~A~b~⋯A~n-1b~.From Lemma2, we can have the following result.Theorem 3.
System (4) is controllable iff Q~c has row full rank, where(15)Q~c=A1AeA1⋯Aen-2A1.Proof.
It is easy to find(16)A~k=001×n-10n-1×1Aekn-1×n-1∈Rn×n,and Ae(n-1)×(n-1)1(n-1)×1=-A1(n-1)×1; then(17)Qc=100⋯01n-1×1Aen-1×n-11n-1×1Ae2n-1×n-11n-1×1⋯Aen-1n-1×n-11n-1×1=101n-1×1-Q~c,where Q~c=A1AeA1⋯Aen-2A1. Therefore, Qc has full row rank if and only if Q~c has full row rank. This completes the proof.Note that, for the multiagent system with multiple agents and high dimension, the controllable matrix of such system is too complex to calculate. But it is so easy to compute the eigenvalues of the system matrix using the PBH rank method by MATLAB. Next, we give a more simple and more easily checkable method.Theorem 4 (PBH rank test).
System (4) is controllable iff system (4) satisfies one of the following conditions:(i)
rank⁡sI-Ae,A1=n-1, ∀s∈C;(ii)
rank⁡(λiI-Ae,A1)=n-1, where λi, ∀i=1,2,…,n-1, is the eigenvalue of matrix Ae.Proof.
The proof is similar to that of Theorem3 in [22], here omitted.Since the topology graph is a directed tree, we can relabel all agents so thatA is a lower triangular matrix, and then A1 is a lower triangular matrix. So we can have the following results.Theorem 5.
System (4) is controllable if coupling weights among agents are all distinct.Proof.
The proof is similar to that of Theorem3.1 in [32], here omitted.Corollary 6.
A directed path is controllable.Proof.
From Figure3, we have(18)Ae=-a2100⋯00a32-a320⋯000a43-a43⋯00⋮⋮⋮⋱⋮⋮000⋯-an-1,n-20000⋯an,n-1-an,n-1.By computing, then(19)Q~c=Aen-1×n-11n-1×1Ae2n-1×n-11n-1×1⋯Aen-1n-1×n-11n-1×1=-a21a212⋯-1n-2a21n-2-1n-1a21n-10-a32a21⋯∗∗⋮⋮⋱⋮⋮00⋯-an-1,n-2⋯a32a21∗00⋯0-an,n-1an-1,n-2⋯a32a21.Obviously, Q~c has row full rank. Hence, the directed path is controllable.Figure 3
A directed path.Corollary 7.
Ak-ary tree is uncontrollable if the weights of two children of some one agent are identical.Furthermore, in fact, the network can be a digraph, which is not a directed tree but contains a directed tree (e.g., Figure4). We have the following result.Figure 4
Containing a directed tree.Theorem 8.
System (4) containing a directed tree is controllable if the following conditions are satisfied:(i)
The eigenvalues ofAe are all distinct.(ii)
The elements ofU-1A1 are all nonzero, where U=[ε2,…,εn], with εi being eigenvector of Ae corresponding to eigenvalue λi (i=2,…,n).Proof.
BecauseA is a lower triangular matrix, Ae is also a lower triangular matrix. Then the diagonal elements of Ae are its eigenvalue λi=-deginvi(i=2,3,…,n). Let U≜[ε2,…,εn], where εi is eigenvector of Ae corresponding to eigenvalue λi (i=2,…,n). If the eigenvalues of Ae are all distinct, then U is invertible. Let x~=U-1x; then(20)x~˙=U-1x˙=U-1AeUx~+U-1A1u=Λx~+U-1A1u,where Λ=U-1AeU=diag⁡(λ2,…,λn). So(21)λiI-Λ,U-1A1=λi-λ20⋯0b20λi-λ3⋯0b3⋮⋮⋱⋮⋮00⋯λi-λnbn.Obviously, if conditions (i) and (ii) hold, then the system is controllable. This completes the proof.


## 4. Simulation Study

In this section, we give some numerical examples and simulations to illustrate the effectiveness of the proposed theoretical results.


### 4.1. Example 1

Consider a five-agent network with six agents and with a directed tree described by Figure5. Let a21=1, a31=2, a42=3, a52=4, and a63=5, and system (4) is defined by(22)A=0000001-1000020-2000030-3000400-4000500-5,b=100000.Through the star transform, we can have(23)Ae=-100000-200030-300400-400500-5,A1=12000.By calculation, Rank(Q~c)=5. According to Theorem 3, the system is controllable.Figure 5
A directed tree topology.Figure6 shows the simulation result. The vertices (the agents, the black star dots) begin from random initial positions. Interconnections are depicted as lines connecting the corresponding vertices. Beginning from this initial configuration, the vertices are ultimately being controlled to a straight-line configuration.Figure 6
Aligning in a straight line.


### 4.2. Example 2

Consider a five-agent network containing a directed tree with six agents described by Figure7. Let a21=1, a31=2, a32=3, a41=4, a42=5, a51=6, and a63=7, and system (4) is defined by(24)A=0000001-1000023-5000450-9006000-6000700-7,b=100000.Through the star transform, we can have(25)Ae=-100003-500050-900000-600700-7,A1=12460.Figure 7
Containing a directed tree topology.By calculation, the eigenvalues ofAe are -7,-5,-9,-1,-6, and(26)U=0000.6065000.274700.45490001.00000.3790000001.00001.00000.961500.53070,U-1=1.7500-3.5000001.0000-2.73003.6401000-0.625001.0000001.648900000001.00000,and then U-1A1=[5.2500,-4.5501,-3.3750,-1.6489,-6.0000]T. According to Theorem 8, the system is controllable.Figure8 shows the simulation result, in which the agents begin from this initial configuration and are ultimately being controlled to a regular triangle configuration.Figure 8
Forming a regular triangle.


## 4.1. Example 1

Consider a five-agent network with six agents and with a directed tree described by Figure5. Let a21=1, a31=2, a42=3, a52=4, and a63=5, and system (4) is defined by(22)A=0000001-1000020-2000030-3000400-4000500-5,b=100000.Through the star transform, we can have(23)Ae=-100000-200030-300400-400500-5,A1=12000.By calculation, Rank(Q~c)=5. According to Theorem 3, the system is controllable.Figure 5
A directed tree topology.Figure6 shows the simulation result. The vertices (the agents, the black star dots) begin from random initial positions. Interconnections are depicted as lines connecting the corresponding vertices. Beginning from this initial configuration, the vertices are ultimately being controlled to a straight-line configuration.Figure 6
Aligning in a straight line.


## 4.2. Example 2

Consider a five-agent network containing a directed tree with six agents described by Figure7. Let a21=1, a31=2, a32=3, a41=4, a42=5, a51=6, and a63=7, and system (4) is defined by(24)A=0000001-1000023-5000450-9006000-6000700-7,b=100000.Through the star transform, we can have(25)Ae=-100003-500050-900000-600700-7,A1=12460.Figure 7
Containing a directed tree topology.By calculation, the eigenvalues ofAe are -7,-5,-9,-1,-6, and(26)U=0000.6065000.274700.45490001.00000.3790000001.00001.00000.961500.53070,U-1=1.7500-3.5000001.0000-2.73003.6401000-0.625001.0000001.648900000001.00000,and then U-1A1=[5.2500,-4.5501,-3.3750,-1.6489,-6.0000]T. According to Theorem 8, the system is controllable.Figure8 shows the simulation result, in which the agents begin from this initial configuration and are ultimately being controlled to a regular triangle configuration.Figure 8
Forming a regular triangle.


## 5. Conclusion

In this paper, we have investigated the controllability of continuous time networked systems based on consensus protocol in directed graph which is a directed tree or contains a directed tree. By applying the star transform, we can simplify the system and get an equivalent reduced-order system. We have obtained the controllability conditions of the original system from the equivalent reduced-order system.



---

*Source: 106769-2015-10-11.xml*