Automatica 45 (2009) 2857–2863
Contents lists available at ScienceDirect
Automatica
journal homepage: www.elsevier.com/locate/automatica
Brief paper
Interconnection topologies for multi-agent coordination under
leader–follower framework
I
Zhijian Ji
a,∗
, Zidong Wang
b
, Hai Lin
c
, Zhen Wang
a
a
College of Automation Engineering, Qingdao University, Qingdao, Shandong, 266071, China
b
Department of Information Systems and Computing, Brunel University, Uxbridge, Middlesex, UB8 3PH, UK
c
Department of Electrical and Computer Engineering, National University of Singapore, 117576, Singapore
a r t i c l e i n f o
Article history:
Received 10 November 2008
Received in revised form
25 June 2009
Accepted 7 August 2009
Available online 4 October 2009
Keywords:
Multi-agent systems
Controllability
Local interactions
Leader-follower structure
a b s t r a c t
In this paper, the formation control problem of the network of multiple agents is studied in terms of
controllability, where the network is of the leader–follower structure with some agents taking leaders role
and others being followers interconnected via the neighbor-based rule. It is shown that the controllability
of a multi-agent system can be uniquely determined by the topology structure of interconnection graph,
for which the investigation comes down to that for a multi-agent system with the interconnection graph
being connected. Based on these observations, two kinds of uncontrollable interconnection topologies are
characterized, and a necessary and sufficient eigenvector-based condition is presented. Our studies also
touch upon the selection of leaders.
© 2009 Elsevier Ltd. All rights reserved.
1. Introduction
Recently, the collective behavior in swarms of entities in the real
world has inspired intensive study of networked systems (Bliman
& Ferrari-Trecate, 2008; Hong, Gao, Cheng, & Hu, 2007; Jadbabaie,
Lin, & Morse, 2003; Olfati-Saber & Murray, 2004; Ren, Beard,
& Atkins, 2007). Understanding the cooperative and operational
principles of such systems may facilitate the development of
the formation control of unmanned air and underwater vehicles,
satellite clusters etc. Formation control problem has been studied
from various perspectives (see e.g. Fax & Murray, 2004; Ji, Lin, &
Lee, 2008; Lin, Francis, & Maggiore, 2005; Lozano, Spong, Guerrero,
& Chopra, 2008; Rahmani & Mesbahi, 2006; Tanner, 2004; Yu,
Hendrickx, Fidan, & Anderson, 2007). In Tanner (2004), the concept
of controllability was put forward for the first time for formation
control of multi-agent systems. The main idea is to transform
the formation control into a classical controllability problem for
fixed topology as well as a switched controllability problem for
switching topology. To date, few results have been available
I
This paper was not presented at any IFAC meeting. This paper was
recommended for publication in revised form by Associate Editor Hideaki Ishii
under the direction of Editor Ian R. Peterson.
∗
Corresponding author. Tel.: +86 10 62751017; fax: +86 10 62764044.
E-mail addresses: jizhijian@pku.org.cn (Z. Ji), Zidong.Wang@brunel.ac.uk
(Z. Wang), elelh@nus.edu.sg (H. Lin), zhenwang_qdu@hotmail.com (Z. Wang).
along these lines. In Ji and Egerstedt (2007), the controllability
was characterized by graph theory. The controllability problem
was studied under fixed and switching topologies in Liu, Xie,
Chu, and Wang (2006) for the continuous-time case, and in Liu,
Chu, Wang, and Xie (2008) for the discrete-time case. Different
from the classical control, the dynamical behavior of networked
systems relies heavily on how the network is connected, i.e.,
its topology structure. In particular, how the controllability
is affected by the interconnection topology structure among
agents remains a fundamental problem, and the corresponding
investigation is at the very outset. Accordingly, the properties of
interconnection topology structures call for specific investigation
for the controllability problem. This motivates the present study.
In this paper, we consider a multi-agent system of the leader–
follower structure, where some agents take the leaders’ role and
others are followers interconnected via the neighbor-based rule.
The leaders are unaffected by followers and do not abide by
the agreement protocol, whereas the followers are influenced by
leaders directly or indirectly. We show that the controllability
can be uniquely determined by the interconnection topology. A
necessary and sufficient condition is then derived by dividing
the overall system into several connected components. The result
leads to the simplification of controllability for the investigation
of that on a connected interconnection graph. Finally, two
kinds of topology structures are constructed to identify the
uncontrollability of networks. Note that the results in Ji et al.
(2008) were expressed in terms of eigenvalues and eigenvectors
0005-1098/$ – see front matter © 2009 Elsevier Ltd. All rights reserved.
doi:10.1016/j.automatica.2009.09.002