A Design Method for Controllable Topologies of Multi-Agent
Networks*
Zhijian Ji
1
, Tongwen Chen
2
, Haisheng Yu
1
1. College of Automation Engineering, Qingdao University, Qingdao 266071, P. R. China
E-mail: jizhijian@pku.org.cn
2. Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, Canada T6G 2V4
E-mail: tchen@ualberta.ca
Abstract: For a multi-agent system with each agent having general linear dynamics, necessary and sufficient algebraic conditions
are proposed for controllability. Then the difference in algebraic controllability conditions between single-integrator and generic
multi-agent systems is pointed out. Based on these conditions and the identified indecisive graph node, a method is finally
developed for the design of controllable topologies. The result also indicates the importance of recognition of uncontrollable
topology structures.
Key Words: Controllability, Leader-follower structure, Multi-agent systems, Local interactions
1 Introduction
Designing control strategies directly from network topolo-
gies has recently drawn a lot of attention in the literature,
which contributes to an efficient manipulation of network-
s and a better understanding of the nature of the system.
The problem requires a study of interplay between network
topologies and system dynamics [1, 23]. Recently, a lot of
efforts have been made along this line in the multi-agent lit-
erature to understand how communication topology struc-
tures lead to controllability. This is also the focus of this
paper.
The multi-agent controllability was formulated under a
leader-follower framework, where the influence over net-
work is achieved by exerting control inputs over leader n-
odes, see e.g., [2, 3, 4]. Roughly speaking, a multi-agent
system is controllable if followers can be steered to proper
positions to make up any desirable configuration by regulat-
ing the movement of leaders. So far most of results are on
the controllability of single-integrator multi-agent systems.
The earliest necessary and sufficient algebraic condition on
multi-agent controllability was presented in [2], which was
expressed in terms of eigenvalues and eigenvectors of sub-
matrices of the Laplacian of the communication graph. An-
other one is an eigenvector based necessary and sufficien-
t algebraic condition proposed in [5], where a relationship
between eigenvectors of the Laplacian and the controllabil-
ity was presented, which provided a method of determining
leaders from the elements of eigenvectors. With these prepa-
rations, the virtue that leaders should have in controllabili-
ty was characterized from both the algebraic and graphical
perspectives [6]. There are some other algebraic condition-
s found in, e.g., [7, 8, 9, 10, 11, 12, 13, 21, 22, 24]. Re-
cently, a protocol design method was proposed for control-
lability in [3]. It was proved that controllability of single-
integrator, high-order and generic linear multi-agent systems
all amounted to the topology structure of the communication
graph, which could be achieved by proper design of proto-
*This work was supported by the National Natural Science Foundation
of China (Nos. 61374062, 61174131), Science Foundation of Shandong
Province for Distinguished Young Scholars (No. JQ201419) and the Natural
Sciences and Engineering Research Council of Canada.
cols. It is worth noting that in [14], the authors obtained in-
teresting graph-theoretic characterizations of controllability
by using the proposed notion of graph controllability classes.
Algebraic conditions lay the foundation for a further in-
vestigation of interactions between topology structures and
controllability. Although this issue is interesting and mean-
ingful, previous work has suggested that it is quite involved,
even for the simplest path topology structure [15]. Special
topologies, naturally, were studied first, such as grid graphs
[16], switching topologies [17], multi-chain topologies [18]
and tree graphs [6]. It is worth noting that controllability
can be fully addressed by a complete analysis of eigenvec-
tors of Laplacian, see e.g., [15, 16]. Topologies construction
offers another way of attacking the problem, which some-
times relates to the partition of communication graphs. In
this regard, topologies are designed by using, for example,
the vanishing coordinates based partition [6] and an eigen-
vector based partition [3, 19]. In particular, the construction
of uncontrollable topologies not only facilitates the design of
control strategies but also deepens understanding of control-
lable ones [18, 5].
The above work guides a further study of this issue in the
paper. The paper presents a design method for controllable
topologies, which implies that the identification of uncon-
trollable topologies helps to better understand the control-
lable ones. As far as we know, there are almost no results
reported in the literature on how to directly construct con-
trollable topologies. Further contributions of the paper lie
in a unified and compact proof to the necessary and suf-
ficient conditions on controllability for generic multi-agent
systems, as well as an identification of the difference of al-
gebraic controllability conditions between single-integrator
and generic multi-agent systems.
2 Problem formulation
Consider a group of n + l single integrator agents given
by
!
˙y
i
= u
i
,i=1,...,n;
˙z
j
= u
n+j
,j=1,...,l,
(1)
where n and l are the numbers of followers and leaders, re-
spectively; y
i
and z
j
are the states of the ith and (n + j)th
Proceedings of the 35th Chinese Control Conference
Jul