Structural Controllability of Multi-Agent Networks: Robustness
against Simultaneous Failures
Mohammad Amin Rahimian, Amir G. Aghdam
Department of Electrical and Computer Engineering, Concordia University,
1455 de Maisonneuve Blvd. West, Montr´eal, Qu´ebec, H3G 1M8, Canada
Abstract
In this paper, structural controllability of a leader-follower multi-agent system with multiple leaders is studied from a graph-theoretic
point of view. The problem of preservation of structural controllability under simultaneous failures in both the communication links and
the agents is investigated. The effects of the loss of agents and communication links on the controllability of an information flow graph
are previously studied. In this work, the corresponding results are exploited to introduce some useful indices and importance measures
that help characterize and quantify the role of individual links and agents in the controllability of the overall network. Existing results
are then extended by considering the effects of losses in both links and agents at the same time. To this end, the concepts of joint
(r, s)−controllability and joint t−controllability are introduced as quantitative measures of reliability for a multi-agent system, and their
important properties are investigated. Lastly, the class of jointly critical digraphs are introduced and it is stated that if a digraph is jointly
critical, then joint t−controllability is a necessary and sufficient condition for remaining controllable following the failure of any set of
links and agents, with cardinality less than t. Various examples are exploited throughout the paper to elaborate on the analytical findings.
Key words: Multi-Agent networks, Controllability, Graph theory
1
Introduction
The past decade has seen a growing interest in the control
of multi-agent networks [1,2]. This type of system consists
of a group of dynamic agents which interact according to a
given information flow topology [1,2]. Distributed and co-
operative control of these networked dynamic systems has
found applications in emerging areas such as formation con-
trol of satellite clusters and motion coordination of robots
[3,4]. An important class of multi-agent systems is the one
with leader-follower architecture [5]. Various problems re-
lated to the control of leader-follower multi-agent systems
include connectivity, containment, consensus, and flocking
[6,7].
The problem of controllability in a Laplacian-based leader-
follower multi-agent system with consensus-like interaction
rules is first formulated by Tanner [8], where necessary
and sufficient conditions for controllability are presented in
terms of eigenvectors and eigenvalues of a sub-matrix of the
graph Laplacian corresponding to the follower nodes. The
importance of a graph theoretic characterization of control-
⋆This work has been supported by the Natural Sciences and
Engineering Research Council of Canada (NSERC) under grant
STPGP-364892-08.
lability is also pointed out in [8]. The authors in [9] propose
a sufficient condition for controllability of the network that
is based on the null-spaces of the leader and follower inci-
dence matrices. The condition is then restated in terms of
the first homology of the network graph and its quotient over
follower nodes. In a different attempt, Rahmani and Mes-
bahi [10] use Tanner’s results to establish a relation between
the notion of graph symmetry and the system theoretic con-
cept of controllability by stating that symmetry with respect
to follower nodes results in the uncontrollability of the net-
work. The work [11] applies the concept of controllability to
a network represented by a weighted directed graph and pro-
vides an interpretation for the controllability matrix in terms
of the gains of fixed-length paths originated from the input
node. Further results by Ji and Egerstedt [12] show that the
existence of a common eigenvalue between the Laplacians
of the original graph and the graph corresponding to the fol-
lower nodes is a necessary and sufficient condition for un-
controllability. This result is subsequently used to develop a
sufficient condition based on the graph-theoretic concept of
equitable partitions [13], which is then refined into necessary
and sufficient conditions using relaxed equitable partitions
[14]. Moreover, while the results relating graph symmetry
to uncontrollability in [13] are shown to be explicable using
equitable partitions, the relaxed equitable partitions in [14]
provide a graph-theoretic characterization of the controllable
1
arXiv:1611.10007v1  [cs.SY]  30 Nov 2016
subspace in the network. Another recent result shows that a
multi-agent system is controllable if and only if no eigenvec-
tor of the graph Laplacian takes a zero value on the elements
corresponding to the leaders [15]. Other challenging scenar-
ios involving dynamic topologies and time-delay have also
been investigated in the literature. For example, it is shown
in [16] that switching between fixed uncontrollable topolo-
gies does not necessarily lead to an uncontrollable network.
The papers [17–19] approach the problem of link and agent
failures by deriving graphical conditions for the preservation
of structural controllability in the face of such failures. While
existing results on the controllability of multi-agent systems
provide an important measure of reliability of network to
faults, they cannot handle the important problem of simulta-
neous failures of communication links and agents. The chief
aim of this paper is to expand on the results of [17–20] by
considering the case when communication links and agents
in the network are both prone to failure. Moreover, the con-
cepts of link and agent controllability degrees introduced in
[17] and [19] are exploited to provide quantitative measures
for the importance of individual links and agents in pre-
serving the controllability of the overall digraph. In order to
quantify the resilience of a network against multiple simulta-
neous failures, the notions of joint (r, s)−controllability and
joint t−controllability are proposed and the latter is shown
to be computable in polynomial-time. Next, a class of di-
graphs are investigated, for which joint t−controllability is
a necessary and sufficient condition for remaining control-
lable after the failure of any set of links and agents with size
less than t.
Identification and characterization of key link-points are very
important for the reliable control of multi-agent networks.
Furthermore, the comparative study of the importance of in-
dividual agents in the network is key to the design of reliable
fault-tolerant multi-agent systems, as it provides guidelines
on where to focus the recovery operations and which agents
to prioritize in the case of a network-wide failure. The re-
sults are therefore of both theoretical and practical interest.
On the other hand, the study of simultaneous failures is im-
portant in light of the fact that in real-world multi-agent sys-
tems, some faults can affect part of the network, containing
a number of links and agents. This type of failure in multi-
agent systems, where terrain properties or hardware faults
disable a number of agents and limit the ability of others to
communicate, motivates the study of controllability under
simultaneous failure of links and agents in this work.
The remainder of this paper is organized as follows. Sec-
tion 2 gives some preliminaries on sets and graph theory,
and also reviews some results from [17] and [19]. The tools
and concepts introduced in this section are then used in Sec-
tion 3 to characterize and quantify the importance of every
link and agent in the controllability of the overall digraph.
In Section 4, first the notion of joint controllability is of-
fered for the characterization of simultaneous failures in the
network, and then the class of jointly critical digraphs are
introduced and their useful properties are pointed out. The
analytical results of Sections 3 and 4 are illustrated and dis-
cussed using some examples throughout the text, and con-
cluding remarks are provided in Section 5.
2
Preliminaries and Notation
Throughout the paper, N denotes the set of all natural num-
bers, and Nk is the set of integers {1, 2, . . . , k}. Further-
more, R denotes the set of all real numbers, W = N ∪{0},
and any other set is represented by a curved capital letter.
The cardinality of a set X is denoted by |X | and in the
strict mathematical sense, for two sets X and Y the in-
clusion symbols ⊂and ⊆are used interchangeably, while
the latter emphasizes the possibility of the trivial inclusion
X = Y for some special configurations or problem sce-
narios. The difference of two sets X and Y is defined as
X KY = {x|x ∈X ∧x /∈Y }. Moreover, X and Y are
called disjoint if X ∩Y = ∅.
2.1
Directed Information Flow Graph of a Multi-Agent
System and its Controllability
A directed graph or digraph is defined as an ordered pair
of sets (V , E ), where V = {ν1, . . . , νn} is the set of ver-
tices and E ⊆V × V is the set of directed edges. In the
graphical representation, each edge ϵ := (τ, ν) ∈E is de-
noted by a directed arc from the vertex τ ∈V to vertex
ν ∈V . Vertices ν and τ are referred to as the head and tail
of the edge ϵ, respectively. Notice that the definition of E
does not allow for the existence of parallel arcs in the graph-
ical representation of digraph G = (V , E ). Therefore, two
edges that share the same pair of head and tail are identi-
cal. Given a set of vertices X ⊂V , the set of all edges
for which the tails belong to X but the heads do not, is
termed the out-cut of X , and is denoted by ∂+
G X ⊂E .
The cardinality of ∂+
G X is called the out-degree of X , and
is characterized as d+
G X = |∂+
G X |. Similarly, the set of all
edges for which the heads belong to X but the tails do not,
is termed the in-cut of X , and is denoted by ∂−
G X ⊂E .
Given an integer k ∈Nn−2, a set {α1, α2, . . . , αk} = Nk
and two vertices τ, ν ∈V , a sequence of distinct edges
of the form (τ, να1), (να1, να2), . . . , (ναk−1, ναk)(ναk, ν) is
called a τν path if for any two edges (¯τ, ¯ν), (ˆτ, ˆν) of this
sequence, ¯ν ̸= ˆν ←→¯τ ̸= ˆτ. For any R ⊂V , a τν path
is called R−rooted if τ ∈R. The set R associated with an
R−rooted τν path is referred to as the root-set, and a vertex
ν ∈V KR is called reachable from the root-set R if there
exists an R−rooted τν path, for some τ ∈R. Two distinct
τν paths are called edge-disjoint if they do not share any
edges. Two edge-disjoint τν paths are called disjoint if τ
and ν are the only vertices that are common to both of them.
Consider a team of n single integrator agents given by:
˙xi(t) = ui(t), i ∈Nn,
(1)
2
where the first n −m agents are followers, and the last m
agents are leaders, with the following control inputs:
ui(t) =





ui
ext(t),
i ∈NnKNn−m
X
j∈Nn
αijxj(t),
i ∈Nn−m
(2a)
(2b)
where αij ∈R and αii ̸= 0 in (2b). Note that the leaders are
influenced by external control inputs, whereas the followers
are governed by a control law which is the linear combina-
tion of the states of neighboring agents as given by (2b). The
interaction structure between the agents in (1) can be de-
scribed by a directed information flow graph G = (V , E ),
where each vertex represents an agent, and a directed edge
from vertex νj to vertex νi indicates that xj(t) is transmit-
ted to agent i and αij ̸= 0 in (2b). Moreover, the condition
αii ̸= 0 in (2b) implies the existence of a self-loop on each
follower vertex of G ; however, the self-loops are omitted to
simplify the graphical representations. In a digraph corre-
sponding to a leader-follower multi-agent system, the root-
set R consists of all leaders, and by assumption |R| = m.
The state of each agent xi(t) is its absolute position w.r.t. an
inertial reference frame, and the agent dynamics is assumed
to be decoupled along each axis of the frame.
Remark 1 Consider a leader-follower multi-agent system
represented by the information flow digraph G = (V , E )
with the root-set R. The control laws in (2) imply that no
edges enter the root-set, i.e. ∂−
G R = ∅.
Definition 1 The information flow digraph G correspond-
ing to the leader-follower multi-agent system (1) is called
controllable if one can choose the non-zero coefficients αij
in (2b) such that by properly moving the leaders, the follow-
ers would assume any desired configuration in an arbitrary
time T > 0.
The above definition of controllability, where the choices of
non-zero parameters are arbitrary, is closely related to the
study of controllability for linear structured systems [21,22].
The following theorem, borrowed from [19], provides a nec-
essary and sufficient condition for the controllability of an
information flow digraph as defined above, and is funda-
mental to all controllability results that follow.
Theorem 1 The information flow digraph G = (V , E ) with
the root-set R ⊂V is controllable if and only if every vertex
ν ∈V KR is reachable from the root-set R.
The next subsection summarizes the main results of [17] and
[19], upon which Sections 3 and 4 expand.
2.2
Link and Agent Controllability Degrees
Link and agent controllability degrees, defined below,
provide quantitative insight into the reliability of a leader-
follower multi-agent system in the face of agent and link
failures and are known to be computable in polynomial-
time, as investigated in [17] and [19] for a single leader and
multiple leaders, respectively. A conceptually related issue
is the fault tolerance of networks and the connectivity of
their interconnection digraphs, as discussed in Section 1.5
of [23].
Definition 2 An information flow digraph G = (V , E ) with
the root-set R ⊂V is said to be p−link controllable if
p is the largest number such that the controllability of the
digraph is preserved after removing any group of at most
p −1 edges. Moreover, a minimal set of p edges whose
removal makes G uncontrollable is referred to as a critical
link-set and is denoted by Cp ⊂E . A link is said to be critical
if it belongs to a critical link-set and uncritical otherwise.
The number p is referred to as the link controllability degree
of the digraph G w.r.t. the root-set R, and is denoted by
lc(G ; R).
Definition 3 An information flow digraph G = (V , E ) with
the root-set R ⊂V is said to be q−agent controllable if
q is the largest number such that the controllability of the
digraph is preserved after removing any group of at most
q−1 non-root vertices. Moreover, a minimal set of q non-root
vertices whose removal makes G uncontrollable is referred
to as a critical agent-set, and is denoted by Cq ⊆V KR. An
agent is said to be critical if it belongs to a critical agent-
set, and uncritical otherwise. The number q is referred to as
the agent controllability degree of the digraph G w.r.t. the
root-set R and is denoted by ac(G ; R). Furthermore, for
any ν ∈V KR, the minimum number of vertices of G whose
removal makes the vertex ν unreachable from the set R is
denoted by ac(G , ν; R).
Remark 2 An information flow digraph G = (V , E ) with
the root-set R ⊂V is not controllable if and only if
ac(G ; R) = lc(G ; R) = 0. Moreover, for such a digraph
all links and agents are assumed to be critical.
Remark 3 Let G , V and R be given as in Definition 3. For
all ν ∈V KR, if ∂+
G R∩∂−
G {ν} ̸= ∅, then the follower agent
ν remains reachable from the root-set R after the removal of
any set of follower agents that does not include ν. For such
an agent ν, the relation ac(G , ν; R) = |V |−|R| holds true.
In the next section, the results of [24] and [25] are summa-
rized, which provide quantitative measures for the impor-
tance of individual links and agents to the overall control-
lability of the network. A relevant discussion on the robust-
ness of control law against link failure and the subsequent
classification of links can be found in [26].
3
Importance of Individual Links and Agents to Net-
work Controllability
According to Definition 2, the links in a multi-agent network
can be categorized as critical and uncritical ones, based on
3
their importance. Now to compare the role of two uncriti-
cal links, the designer can consider the resultant increase in
the number of critical links in the network that is due to the
removal of each uncritical link. This so-called link control-
lability index provides a means to determine which uncriti-
cal links take precedence in terms of their importance in the
network. The next definition uses the notion of agent con-
trollability degree (Definition 3) to introduce a second mea-
sure of importance, namely the agent controllability index,
that would apply to both critical and uncritical links. Sim-
ilarly to the link controllability index, the higher the agent
controllability index of a link, the more important its role in
the preservation of controllability throughout the network.
Definition 4 Consider an information flow digraph G =
(V , E ) with the root-set R. Let ϵ ∈E be an arbitrary edge in
G , and G1 = (V , E K{ϵ}). The agent controllability index of
the edge ϵ is defined as ρ(G , ϵ; R) := ac(G ; R)−ac(G1; R).
Lemma 1 Consider an information flow digraph G
=
(V , E ) with the root-set R. Let ϵ ∈E K∂+
G R be an arbi-
trary edge in G whose head is the vertex ν ∈V KR. If G1 =
(V , E K{ϵ}), then ρ(G , ϵ; R) = ac(G , ν; R)−ac(G1, ν; R).
Proof. The proof follows from the fact that the removal of
the edge ϵ ∈E K∂+
G R can affect the agent controllability
degree of digraph G only by altering the available paths that
connect the root-set R to the head vertex ν, through other
agents in the network. On the other hand, if ϵ ∈∂+
G R, then
ϵ provides a direct path from R to ν which does not include
any other agent in the network, and according to Remark 3,
ac(G , ν; R) = |V | −|R|, regardless of the available paths.
■
Theorem 2 Consider an information flow digraph G =
(V , E ) with the root-set R. If there exist a vertex ν ∈V
and an edge ϵ such that {ϵ} ⊆∂+
G R ∩∂−
G {ν} ̸= ∅, then
∀ˆϵ ∈∂−
G {ν}K{ϵ}, ρ(G , ˆϵ; R) = 0.
Proof. Let ˆ
G = (V , E K{ˆϵ}). For the case where ˆϵ /∈∂+
G R ∩
∂−
G {ν}, the proof follows from Remark 3 and Lemma 1 upon
noting that since the edge ϵ connects the vertex ν directly
to the root-set, ac(G , ν; R) = ac( ˆ
G , ν; R) = |V | −|R|,
and hence ac(G , ν; R) −ac( ˆ
G , ν; R) = 0. On the other
hand, if ˆϵ ∈∂+
G R ∩∂−
G {ν}, then the proof follows from
the fact that both ϵ and ˆϵ are providing a direct connection
from the root-set R to their common head vertex ν that
does not rely on any other follower agent in the network.
Therefore, as long as this direct connection from the root-
set R to the head vertex ν exists, removing either one of
the edges ϵ or ˆϵ would not impact the agent controllability
degree of digraph G . Hence, if {ϵ, ˆϵ} ⊆∂+
G R ∩∂−
G {ν}, then
ρ(G , ϵ; R) = ρ(G , ˆϵ; R) = 0.
■
Theorem 2 facilitates the characterization of the agent con-
trollability index for those edges whose heads are directly
connected to the root-set. In the special case that there ex-
ist multiple edges connecting the root-set to a vertex, The-
orem 2 reduces to the following corollary.
Corollary 1 Given an information flow digraph G
=
(V , E ) with the root-set R and a vertex ν ∈V KR, if
|∂+
G R∩∂−
G {ν}| > 1, then ∀ϵ ∈∂+
G R∩∂−
G {ν}, ρ(G , ϵ; R) =
0.
The next theorem provides a full characterization of the
agent controllability index for those edges whose heads are
not directly connected to the root-set.
Theorem 3 Consider an information flow digraph G =
(V , E ) with the root-set R, and let τ, ν ∈V KR be two ver-
tices in G such that ϵ := (τ, ν) ∈E K∂+
G R and ∂−
G {ν} ∩
∂+
G R = ∅. If ρ(G , ϵ; R) ̸= 0, then ρ(G , ϵ; R) = 1 and
there exists a critical agent-set Cq ⊂V KR of G such that
τ ∈Cq.
Proof. Let G1 = (V , E K{ϵ}) and consider a critical agent-
set C 1
q
⊂V KR of G1. If τ ∈C 1
q or ν ∈C 1
q , then
ρ(G , ϵ; R) = 0, because C 1
q is then a critical agent-set of
G as well. Since ρ(G , ϵ; R) ̸= 0, it is true that τ /∈C 1
q .
The proof now follows upon noting that Cq = C 1
q ∪{τ} is
a critical agent-set of G and τ ∈Cq.
■
Remark 4 Theorems 2 and 3 address two mutually exclu-
sive cases: the former applies to the incoming edges of the
vertices that are directly connected to the root-set, while any
other edge in the network is addressed by the latter.
Example 1 Criticality and Agent Controllability Index.
In all of the examples herein, nodes belonging to the root-
set (leaders) are represented by dark vertices. The digraph
¯
G1 in Fig. 1(a) is 2−agent and 3−link controllable, and all
of its links are critical. However, only for those links that
belong to the out-cut of the root-set ρ = 1, and for the rest
of the links ρ = 0.
Next, consider the digraph ¯
G2 of Fig. 1(b). Every dotted link
in this digraph is critical (and vice versa) and it follows from
Theorem 2 that those critical links which do not belong to
the out-cut of the root-set have zero agent controllability
index, while all other critical links have ρ = 2. On the
other hand, the solid links are all uncritical with unity agent
controllability index.
In what follows, the notions of agent and link controllability
degrees are exploited to judge the importance of an agent
as reflected through its outgoing links. The agent and link
criticality indices are defined next, and the former is shown
to distinguish between critical and uncritical agents based
solely on their outgoing links.
Definition 5 Consider
an
information
flow
digraph
G
= (V , E ) with the root-set R, and let ν ∈V KR
4
(a) ¯
G1
(b) ¯
G2
Fig. 1. (a) The digraph
¯
G1, which is 2−agent and 3−link con-
trollable. (b) The digraph ¯
G2 of Example 1, for which critical and
uncritical links are denoted by dotted and solid edges, respectively.
be an arbitrary non-root vertex in G . Let also G1 =
(V , E K∂+
G {ν}). The agent criticality index of vertex ν
is denoted by δ(G , ν; R), and is given by δ(G , ν; R) =
ac(G ; R) −ac(G1; R). In a similar manner, the link crit-
icality index of vertex ν is characterized as θ(G , ν; R) =
lc(G ; R) −lc(G1; R).
Lemma 2 Given an information flow digraph G = (V , E )
with the root-set R, if ac(G ; R) = |V | −|R|, then ∀ν ∈
V KR, ∂−
G {ν}∩∂−
G R ̸= ∅and δ(G , ν; R) = 0. Conversely,
if for all ν ∈V KR, ∂−
G {ν} ∩∂−
G R ̸= ∅, then ac(G ; R) =
|V | −|R| and ∀ν ∈V KR, δ(G , ν; R) = 0.
Proof. The proof for the first part follows by contradiction,
since if ac(G ; R) = |V | −|R|, then all follower agents are
critical and Cq = V KR is the only critical agent-set. Now, if
there exists a vertex ˆν that is not the head of a link belonging
to the out-cut of the root-set R, then the removal of the
agent-set CqK{ˆν} will make ˆν unreachable from the root-set
R, which is in contradiction with Cq being a critical agent-
set. By the same token, to prove the converse suppose that
ac(G ; R) < |V | −|R|. Then there exist a critical agent-set
C 1
q ⫋V KR and an agent ˜ν ∈V K
R ∪C 1
q


such that the
removal of C 1
q will make ˜ν unreachable from the root-set
R. This, however, is also a contradiction since ˜ν is the head
of a link belonging to the out-cut of the root-set R. In both
cases, the equality δ(G , ν; R) = 0 for all ν ∈V KR follows
from the fact that ∀ν ∈V KR, ac(G ; R) = ac(G1; R) =
|V | −|R|, where G1 = (V , E K∂+
G {ν}).
■
Remark 5 Digraph G = (V , E ) with root-set R for which
ac(G ; R) = |V | −|R|, corresponds to a pathological case
where all agents are critical and they receive their “informa-
tion” from the root-set “directly”. In such a case, measures
other than the agent criticality index are used to distinguish
between the follower agents in terms of their significance in
the network.
Theorem 4 Given an information flow digraph G = (V , E )
with the root-set R, suppose that ac(G ; R) < |V | −|R|.
For all ν ∈V KR, δ(G , ν; R) = 1 if and only if ν is critical,
and δ(G , ν; R) = 0 otherwise.
Proof. Since ac(G ; R)
<
|V | −|R|, the patholog-
ical case set forth in Lemma 2 does not apply. Let
G1 = (V , E K∂+
G {ν}), and suppose that Cq is an arbitrary
critical agent-set of G . The removal of Cq will make G1
uncontrollable, and if ν ∈Cq, then C 1
q = CqK{ν} is a crit-
ical agent-set of G1. Hence, δ(G , ν; R) = |Cq| −|C 1
q | = 1.
This proves that if ν is critical, then δ(G , ν; R) = 1. On the
other hand, if ν is uncritical, then every critical agent-set
of G is a critical agent-set of G1 and vice versa. Hence,
δ(G , ν; R) = ac(G ; R) −ac(G1; R) = 0, which completes
the proof.
■
Remark 6 Theorem 4 indicates that the criticality of an
agent in any digraph (except for the pathological case de-
scribed in Lemma 2 and Remark 5) is completely charac-
terized by its outgoing links and through its agent criticality
index given in Definition 5.
The primary influence of an agent on the information flow
structure is captured by the agent and link criticality indices
δ and θ, the latter being the more conclusive of the two. If
two agents have the same criticality indices δ and θ, then
the one with a greater number of critical links amongst its
out-going links, has a more prominent role, due to its ef-
fect in maintaining the critical links in the network. As an-
other measure of importance, one can remove the uncritical
links amongst the outgoing links of an agent, and consider
the resultant increase in the number of critical links in the
network. These last two effects are measured by the critical
and uncritical link indices, respectively [24]. Together these
indices offer a means for ordering and prioritizing agents in
a network.
The following section and the subsequent definitions, lem-
mas, and theorems provide useful tools for investigating the
impact of simultaneous link and agent failures on the con-
trollability of an information flow digraph.
4
Joint Controllability
The concept of joint controllability degree parallels the no-
tions of agent and link controllability degrees in Section 2,
and facilitates the extension of the previous results to the
cases where multiple simultaneous failures occur, affecting
both links and agents in the network.
4.1
Joint Controllability Degree
Definition 6 An information flow digraph G = (V , E ) with
the root-set R ⊂V is said to be joint (r, s)−controllable
if it remains controllable in the case of simultaneous failure
of any set of links of size u ⩽r and any set of non-root
vertices of size v ⩽s, where u + v < r + s (note the strict
inequality in the last expression).
The next lemma follows immediately from Definitions 2, 3
and 6.
5
Lemma 3 The following statements hold:
a) If G is joint (r, s)−controllable, then for all u ⩽r and
v ⩽s, G is joint (u, v)−controllable.
b) If G is joint (r, s)−controllable, then r ⩽lc(G ; R) and
s ⩽ac(G ; R).
c) If G is joint (r, s)−controllable and lc(G ; R) = r, then
s = 0.
d) If G is joint (r, s)−controllable and ac(G ; R) = s, then
r = 0.
Definition 7 An information flow digraph G = (V , E ) with
the root-set R ⊂V is said to be joint t−controllable if t is
the largest number such that G is joint (u, v)−controllable
for all u + v ⩽t. Moreover, a minimal set of r vertices and
s = t −r edges whose removal makes G uncontrollable
is referred to as a critical agent-link set, and is denoted
by Crs ⊂(V ∪E ) KR. The number t is called the joint
controllability degree of the digraph G w.r.t. the root-set R,
and is denoted by jc(G ; R).
From Definitions 6 and 7, it follows that a sufficient condi-
tion for the preservation of controllability in the face of si-
multaneous failures in links and agents is that the total num-
ber of failed links and agents is less than the joint control-
lability degree of the underlying information flow digraph.
Theorem 5 Given an information flow digraph G = (V , E )
with the root-set R, jc(G ; R) = min {lc(G ; R), ac(G ; R)}.
Proof. The proof follows by contradiction. Let lc(G ; R) =
p, ac(G ; R) = q and jc(G ; R) = t, and suppose that
t < min(p, q). From Definition 7, for some {r, s} ⊂Nt and
r+s = t, there exists a critical agent-link set Crs which can
be partitioned as Crs = A ∪L , where A ⊂V , L ⊂E ,
|A | = s, and |L | = r. Moreover, the removal of Crs from
G leads to an uncontrollable digraph G1 = (V1, E1), where
V1 = V KA . Let B denote the set of agents correspond-
ing to the heads of the links in L . It follows that |B| ⩽r
and B ∩A = ∅, because otherwise the links whose heads
belong to B ∩A can be deleted from Crs leading to a
smaller agent-link set whose removal makes G uncontrol-
lable, which contradicts with Definition 7 and Crs being a
critical agent-link set. Next, it follows from B∩A = ∅and
|B| ⩽r that |A ∪B| ⩽r+s = t < q. Thus, the deletion of
the agent-set A ∪B from G leads to a controllable digraph
G2 = (V2, E2), where V2 = V1KB. This in turn implies that
every agent belonging to V1KB in the digraph G1 is reach-
able from R and vice versa. The latter converse statement
follows from the fact that if there exists a vertex ν ∈B that
is reachable from the root-set in G1, then the corresponding
link in L whose head is ν can be deleted from Crs, lead-
ing to a contradictorily smaller critical agent-link set. Next
note in the digraph G1 that since every vertex in B is un-
reachable from R while every vertex in V1KB is reachable
from R, one should have ∂+
G1V1 ∩∂−
G1B = ∅or equiva-
lently ∂+
G V1 ∩∂−
G B = L , because otherwise those vertices
in B which are the heads of some links in ∂+
G1V1 ∩∂−
G1B
will be reachable from the root-set in G1. Now, consider an
arbitrary vertex ˆν belonging to the agent-set B in the di-
graph G . Such a vertex is the head of some links in L , say
l links, where l ⩽|L |. In addition to these l links, ˆν can
only be the head of some links whose tails are either any of
the m ⩽|L | −l = r −l agents in B or any of the s agents
in A . Hence, |∂−
G {ˆν}| ⩽l + m + s ⩽r + s. On the other
hand, the removal of ∂−
G {ˆν} will make ˆν unreachable from
any vertex in G , and therefore renders the digraph uncon-
trollable. This, however, is in contradiction with Definition 2
and the fact that |∂−
G {ˆν}| ⩽r + s = t < p.
■
The next definition and the theorem which follows, pro-
vide a mechanism to transform the problem of joint
t−controllability of a given digraph into q−agent control-
lability of another digraph. This will, in turn, enable the
multi-agent control system designer to take advantage of
the polynomial-time algorithms developed in [17] and [19]
for specifying the critical agent-link sets of a given digraph.
Definition 8 Given a digraph G = (V , E ), replace every
edge ϵ ∈E with two edges ˆϵ1 and ˆϵ2 in the same direction
as ϵ, and connect them through an intermediate vertex ˆνϵ,
termed a black vertex. The resulting digraph ˆ
G = ( ˆ
V , ˆE )
is called the edge-duplicate of G . Every vertex of ˆ
G that is
not a black vertex is referred to as a white vertex.
Remark 7 Given a digraph G = (V , E ) and its edge-
duplicate
ˆ
G = ( ˆ
V , ˆE ), the following equalities hold for
the number of vertices and edges: | ˆ
V | = |V | + |E | and
| ˆE | = 2|E |. Moreover, every white vertex ˆνν ∈
ˆ
V corre-
sponds to one vertex ν ∈V and every black vertex ˆνϵ ∈ˆ
V
corresponds to one edge ϵ ∈E . There exists a one-to-one
correspondence between the sets V ∪E and ˆ
V .
Theorem 6 Consider a digraph G = (V , E ) with the root-
set R ⊂V and its edge-duplicate ˆ
G = ( ˆ
V , ˆE ). The di-
graph G is joint t−controllable if and only if ˆ
G is t−agent
controllable.
Proof. The proof follows by construction, from the fact that
Definition 8 specifies a bijection between the sets V ∪E and
ˆ
V . Using this bijection, any critical agent-link set of G can
be transformed into a critical agent-set of ˆ
G and vice versa.
■
In the next subsection, the important class of jointly criti-
cal digraphs is introduced and their role in characterizing
robustness against simultaneous failures in both links and
agents is highlighted.
4.2
Jointly Critical Digraphs
The notion of agent controllability index from Definition 4
can be exploited to characterize and compare the relative
susceptibility of digraphs with regard to agent or link failure.
6
Accordingly, in Lemmas 4 and 5, as well as Theorem 8
which follow, three classes of digraphs, termed as agent-
critical, link-critical and jointly critical, are introduced and
some of their important characteristics are pointed out.
Lemma 4 For an information flow digraph G = (V , E )
with root-set R ⊂V , if ∀ϵ ∈∂+
G R, ρ(G , ϵ; R) = 1, then
jc(G ; R) = ac(G ; R). Such a digraph for which the afore-
mentioned assumption holds will be referred to as agent-
critical.
Proof. Using Theorem 5, it suffices to introduce a set
A ⊂V KR with the property |A | ⩽lc(G ; R), whose
removal makes G uncontrollable. To this end, consider
a solution R ⊆X
⊂V to the minimization problem
minR⊆X ⊂V d+
G X in Theorem 3 of [19], which means that
|∂+
G X | = lc(G ; R). Routine 1 utilizes ∂+
G X to generate
one such set A with the desired characteristics.
■
Routine 1
1: A = ∅
2: for all (τ, ν) ∈∂+
G X
do
3:
if τ /∈R then
4:
A = A ∪{τ}
5:
else
6:
A = A ∪{ν}
7:
end if
8: end for
9: return A
Remark 8 When applying Routine 1 to an agent-critical di-
graph, it is notable that the assumption in Lemma 4 together
with Corollary 1 ensures that step 6 will not be executed
more than once for a given vertex ν.
Fig. 1(a) shows the case of an agent-critical digraph, for
which the agent and link controllability degrees are given by
q = 2 and p = 3, respectively, and they satisfy the relation
q ⩽p, as suggested by Lemma 4.
Lemma 5 Consider an information flow digraph G
=
(V , E ) with the root-set R ⊂V . If there exists a critical
agent-set Cq ⊂V KR of G such that ∀ν ∈Cq, ∃ϵ ∈∂+
G {ν}
for which ρ(G , ϵ; R) ̸= 0, then jc(G ; R) = lc(G ; R). Such
a digraph for which the aforementioned assumption holds
will be referred to as link-critical.
Proof. The proof follows by using Theorem 5 and intro-
ducing a set B ⊂E with the property |B| ⩽ac(G ; R),
whose removal makes G uncontrollable. Let Cq be a critical
agent-set satisfying the condition of Lemma 5. Routine 2
utilizes Cq to generate one such set B with the property that
B ⊂E K∂+
G R and |B| = |Cq| = ac(G ; R).
■
Remark 9 When applying Routine 2 to a link-critical di-
graph, it is notable that with Cq satisfying the conditions
of Lemma 5, step 5 will be executed exactly once for every
vertex ν ∈Cq.
Routine 2
1: B = ∅
2: for all ν ∈Cq do
3:
for all ϵ ∈∂+
G {ν} do
4:
if B ∩∂+
G {ν} = ∅and ρ(G , ϵ; R) = 1 then
5:
B = B ∪{ϵ}
6:
end if
7:
end for
8: end for
9: return B
Remark 10 Using Theorem 3, it can be stated that digraph
G in Lemma 5 is link-critical if there exists a critical agent-
set Cq ⊂V KR of G such that ∀ν ∈Cq, ∃ϵ ∈∂+
G {ν} for
which ρ(G , ϵ; R) = 1.
Digraph
¯
G2 in Fig. 1 is 3-agent and 2-link controllable.
This digraph is link-critical, and satisfies the condition of
Lemma 5.
Theorem 7 Consider a joint (r, s)−controllable infor-
mation flow digraph G
=
(V , E ) with the root-set
R
⊂
V . If G
is agent-critical or link-critical, then
r + s ⩽max {lc(G ; R), ac(G ; R)}.
Proof. According to the results of Lemmas 4 and 5, it suffices
to prove that if G is agent-critical, then r + s ⩽lc(G ; R),
and if G is link-critical, then r + s ⩽ac(G ; R). For an
agent-critical digraph G , consider a solution R ⊆X ⊂V
to the minimization problem minR⊆X ⊂V d+
G X . According
to Theorem 3 of [19], the link controllability degree of G is
equal to the out-degree of X , i.e. |∂+
G X | = lc(G ; R), and
it follows from part (b) of Lemma 3 that r ⩽lc(G ; R). If
r = lc(G ; R), then part (c) of Lemma 3 requires that s = 0,
and hence the statement of the above theorem holds. If on
the other hand r < lc(G ; R), then choose a set of edges
Zr ⊂E such that Zr ⊂∂+
G X and |Zr| = r. Use Routine 1
after replacing ∂+
G X with ∂+
G X KZr to generate a set A ⊂
V . Now, A ∪Zr is a set of |A | vertices and |Zr| = r
edges, for which GA ,Zr = (V KA , E KZr) is uncontrollable.
However, G is joint (r, s)−controllable, which implies that
s ⩽|A |. On the other hand, it follows from Routine 1
that |A | ⩽|∂+
G X KZr|. Hence s ⩽|∂+
G X KZr| or s ⩽
lc(G ; R)−r, which completes the proof for an agent-critical
digraph. A similar argument can be utilized to prove the
statement for the case where G is link-critical. From part
(b) of Lemma 3, it is clear that s ⩽ac(G ; R). Now, starting
from a critical agent-set Cq that satisfies the condition of
Lemma 5, select an arbitrary subset Zs ⊂Cq of s = |Zs|
agents. If s = ac(G ; R), then part (d) of Lemma 3 requires
that r = 0 and the statement for the link-critical case holds.
If s < ac(G ; R), then applying Routine 2 to CqKZs yields
a set B of |CqKZs| = ac(G ; R) −s = |B| links, whose
deletion together with deletion of the s agents in Zs will
render G uncontrollable. The proof for a link-critical digraph
G follows now upon the realization that since G is joint
(r, s)−controllable, one should have |B| = ac(G ; R)−s ⩾
r.
■
7
Remark 11 Using the pathological class of digraphs de-
scribed in Lemma 2 and Remark 5, it is straightforward
to construct a joint (r, s)−controllable digraph G with the
root-set R, such that r + s > max {ac(G ; R), lc(G ; R)}.
Non-trivial counterexamples are also possible and impor-
tant. The joint (3, 2)−controllable digraph in Fig. 2 is
4−link and 3−agent controllable.
Fig. 2. An example of a joint (r, s)−controllable digraph G which
does not satisfy the relation r + s ⩽max {ac(G ; R), lc(G ; R)}.
Theorems 5 and 6 in [17] provide the following bounds
on the number of edges |E | of a digraph G = (V , E ):
|E | ⩾(|V | −1)lc(G ; R) and |E | ⩾|V | + ac(G ; R) −2.
These two inequalities, together with Theorem 5 in the
previous subsection, imply that |E | ⩾max { (|V | −1)
jc(G ; R), |V | + jc(G ; R) −2}. In the same vein, Theo-
rem 7 proved in this subsection, yields the following corol-
lary, specifying some necessary conditions on the number
of edges of an agent-critical or link-critical digraph, which
is joint (r, s)−controllable. These results can be used in the
design of reliable multi-agent control systems.
Corollary 2 Consider a joint (r, s)−controllable informa-
tion flow digraph G = (V , E ). The following statements
hold: if G is agent-critical, then |E | ⩾(|V | −1)(r + s).
Moreover, if G is link-critical, then |E | ⩾|V | + r + s −2.
The next theorem and the remark that follows capture the
significance of joint controllability degree for the so-called
jointly critical digraphs.
Theorem 8 If an information flow digraph G = (V , E )
with the root-set R ⊂V is both agent-critical and link-
critical, then jc(G ; R) = ac(G ; R) = lc(G ; R). More-
over, for every (r, s) ∈W × W, the digraph G is joint
(r, s)−controllable if and only if r + s ⩽jc(G ; R). Such a
digraph, which is both agent-critical and link-critical, will
be referred to as jointly critical.
Proof. From Lemmas 4 and 5, it is immediate that
jc(G ; R) = ac(G ; R) = lc(G ; R). The rest of the proof,
also, can be sketched as a combination of the proofs of
Lemmas 4 and 5. Starting from a critical link-set Cp ⊆E ,
one can use Routine 1 to transform any set of links L ⊆Cp
into a set of agents A , where |A | ⩽|L |, such that
the removal of A along with the links in CpKL renders
the digraph uncontrollable. Moreover, |A | = |L | be-
cause the inequality |A | < |L | contradicts the fact that
ac(G ; R) = lc(G ; R) = |Cp|. On the other hand, starting
from a critical agent-set Cq ⊆V KR that satisfies the con-
dition of Lemma 5, one can use Routine 2 to transform any
set of agents B ⊆Cq into a set of |B| links, which if re-
moved together with the agents in CqKA , then the digraph
becomes uncontrollable.
■
Remark 12 If a digraph G with the joint controllability
degree t is jointly critical, then for all (r, s) ∈W × W
satisfying the inequality r + s
>
t, G
is not joint
(r, s)−controllable. Hence, the joint controllability degree
alone completely characterizes the controllability preserva-
tion properties of the digraph G . In other words, if the values
of (r, s) ∈W × W for which G is joint (r, s)−controllable
are depicted as discrete points in the plane, then a pair of
non-negative integers belongs to the jointly controllable set
if and only if the corresponding point in the (r, s)-plane
lies in the region r + s ⩽t.
Three special cases of interest are addressed in the sequel.
4.2.1
Complete Digraphs
As a special case, a digraph Gcn = (Vcn, Ecn) is called
complete if Ecn = Vcn×Vcn. Select a vertex r in a complete
digraph as the root, and remove the |Vcn| −1 edges headed
by the vertex r. Then the resultant information flow digraph
is (|Vcn| −1)−link controllable [17]. This is the maximum
value for the link controllability degree in an information
flow digraph with n = |Vcn| vertices, because a complete
digraph possesses the maximum possible number of edges
per a given number of vertices. The following proposition
suggests that the joint controllability degree of a complete
information flow digraph Gcn is also n −1.
Proposition 1 Given a complete digraph Gcn = (Vcn, Ecn)
with |Vcn| = n, choose a vertex r as the root and re-
move the n −1 edges which are headed by r. The result-
ing information flow digraph is jointly critical and joint
(n −1)−controllable.
Proof. The proof follows from the fact that Gcn has exactly
n −1 disjoint rν paths for every ν ∈VcnK {r}.
■
Remark 13 It is to be noted that jc(Gcn; {r}) = n−1 is the
highest attainable joint controllability degree for a digraph
with n vertices. This explains the desirable controllability
preservation properties of the complete digraphs in the face
of simultaneous link and agent failures.
4.2.2
Kautz Digraphs
Kautz digraphs are introduced and discussed in Section 3.3
of [23]. Accordingly, a Kautz digraph Gk = (Vk, Ek) with
|Vk| = n is given by:
Vk = {ν1, . . . , νn} ,
(3)
Ek = {(νi, νj)|i, j ∈Nn ∧j ≡(−id −τ) mod n, τ ∈Nd} ,
8
for some d ∈NK{1} and κ ∈N, such that dκ + dκ−1 = n.
The following proposition gives the joint link controllability
degree of an information flow digraph derived from a Kautz
digraph.
Proposition 2 Consider a Kautz digraph Gk = (Vk, Ek)
where Vk and Ek are given by (3). Choose a vertex r as
the root and remove all edges which are headed by r. The
resulting information flow digraph is jointly critical and joint
d−controllable.
Proof. The proof follows upon noting that Gk has exactly d
disjoint rν paths for every ν ∈VkK {r}.
■
4.2.3
Circulant Digraphs
Circulant digraphs are introduced and discussed in Section
3.4.5 of [23]. Accordingly, a circulant digraph Gc = (Vc, Ec)
with |Vc| = n is given by:
Vc = {ν1, . . . , νn} ,
(4)
Ec = {(νi, νj)|i, j ∈Nn ∧j −i ≡b mod n, b ∈B} ,
for some B ⊆Nn−1. Choose a vertex r ∈Vc as the root,
and remove every edge whose head is r. Then in the result-
ing information flow digraph Gc, lc(Gc; {r}) = |B|. This is
due to the fact that Gc has exactly |B| edge-disjoint rν paths
for every ν ∈VcK {r}. For |Vi| = 5, i ∈N3, the choices
of B1 = {1}, B2 = {1, n −1}, and B3 = {1, n −2}
correspond to a simple loop G1
=
(V1, E1), a dis-
tributed double-loop G2 = (V2, E2), and a daisy chain
loop G3
=
(V3, E3), respectively. These digraphs are
introduced in Section 3.4.1 of [23], and they are de-
picted in Figs. 3(a)−(c). For a simple loop, the equality
lc(G1; {r}) = ac(G1; {r}) = jc(G1; {r}) = 1 holds,
while for the other two cases lc(Gi; {r}) = ac(Gi; {r}) =
jc(Gi; {r}) = 2,
i = 2, 3. These three digraphs have
the additional property that for any r, s satisfying the in-
equality r + s > jc(Gi; {r}), i ∈N3, Gi is not joint
(r, s)−controllable. Accordingly, the joint controllability
degree alone completely characterizes the controllability
preservation properties for Gi, i ∈N3. This is due to the
fact that Gi, i ∈N3, are jointly critical.
On the other hand, for the circulant digraph G4 with |V4| = 6,
B4 = {2, 3, 5} and the uppermost vertex selected as the root
r, the resulting information flow digraph, shown in Fig. 3(d),
is 3−link and 2−agent controllable [17]. This digraph is nei-
ther agent-critical nor link-critical, and hence is not jointly
critical. The joint controllability degree for G4 is 2, and un-
like Gi, i ∈N3, jc(G4; {r}) = 2 does not proffer a full
characterization of the controllability preservation proper-
ties for G4. Accordingly, G4 is joint (r, s)−controllable for
(r, s) ∈{(2, 1), (3, 0)}, although r + s > jc(G4; {r}). To
clarify this point, let the values of (r, s) ∈W×W for which
Gi is joint (r, s)−controllable, i ∈N4, be shown as discrete
points in the plane. For i ∈N3, the line r + s = jc(Gi; {r})
divides the first quadrant of the (r, s)-plane into two regions,
where for r+s ⩽jc(Gi; {r}), Gi is joint (r, s)−controllable
and otherwise it is not. This is depicted in Fig. 4 for G2,
G3 and G4. In the case of G2 and G3, the closed shaded
region contains all pairs of integers belonging to the joint
controllability set (the points associated with these pairs are
shown by black circles). This property, however, does not
hold for G4, where there exist two points above the line
r + s = jc(G4; {r}) representing the pairs for which G4 is
still joint (r, s)−controllable.
(a) G1
(b) G2
(c) G3
(d) G4
Fig. 3. Circulant digraphs
0
1
2
3
0 
1 
2 
3 
4 
s (agents)
r (links)
 
 
Joint (r, s)−Controllable
Joint t−Controllability Borderline
Fig. 4. The joint controllability of the circulant digraphs G2, G3
and G4 given in Figs. 3(b) to 3(d) is considered here. For G2 and
G3, the shaded area contains all of the filled circles representing
the pairs of integers that belong to their jointly controllable set;
this property, however, does not hold true in the case of G4.
9
5
Conclusions
Structural controllability of a network of single-integrator
agents with leader-follower architecture was investigated.
The notions of agent controllability index, as well as agent
and link criticality index were defined to characterize and
quantify the importance of individual links and agents to
the controllability of the overall network. The results pro-
vide the designer of a multi-agent system with useful means
to evaluate (and enhance) the reliability of the network by
deciding on which links and agents to prioritize for fault
management and recovery operations.
In the next step, the concepts of joint (r, s)−controllability
and joint t−controllability were proposed as quantitative
measures of reliability in a multi-agent system subject to si-
multaneous failures of communication links and agents. It
was noted that joint t−controllability is a conservative re-
quirement which provides a sufficient condition for remain-
ing controllable following the removal of any set of links
and agents with size less than t. Nonetheless, for the impor-
tant class of jointly critical digraphs, the joint controllability
degree t proffers a necessary and sufficient condition, which
fully characterizes the controllability preservation properties
of the digraph. By and large, a digraph remains controllable
after the removal of any u links and v agents if and only if
there exists a pair (r, s) ∈W × W such that the digraph is
joint (r, s)−controllable and u ⩽r ∧v ⩽s∧u+v < r +s.
However, the authors’ ongoing research indicates that for
some digraphs, which are neither agent nor link critical,
determining all (r, s) pairs for which the digraph is joint
(r, s)−controllable may not be tractable in polynomial-time,
and future research on this topic is of much interest. The pre-
sented results provide design guidelines for improving the
network robustness against simultaneous failures of multi-
ple links and agents. A number of examples were offered to
elucidate the results.
References
[1]
M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in
Multiagent Networks.
Princeton University Press, 2010.
[2]
F. Bullo, J. Cort´es, and S. Mart´ınez, Distributed Control of Robotic
Networks.
Princeton University Press, 2009.
[3]
J.
Lavaei,
A.
Momeni,
and
A.
G.
Aghdam,
“A
model
predictive decentralized control scheme with reduced communication
requirement for spacecraft formation,” IEEE Transactions on Control
Systems Technology, vol. 16, no. 2, pp. 268–278, 2008.
[4]
N.
Moshtagh,
N.
Michael,
A.
Jadbabaie,
and
K.
Daniilidis,
“Vision-based distributed control laws for motion coordination of
nonholonomic robots,” IEEE Transactions on Robotics, vol. 25, pp.
851–860, 2009.
[5]
W. Ren and R. W. Beard, “Consensus seeking in multiagent
systems under dynamically changing interaction topologies,” IEEE
Transactions on Automatic Control, vol. 50, no. 5, pp. 655–661,
2005.
[6]
A. Ajorlou, A. Momeni, and A. G. Aghdam, “A class of bounded
distributed control strategies for connectivity preservation in multi-
agent systems,” IEEE Transactions on Automatic Control, vol. 55,
no. 12, pp. 2828–2833, 2010.
[7]
R.
Olfati-Saber,
“Flocking
for
multi-agent
dynamic
systems:
algorithms and theory,” IEEE Transactions on Automatic Control,
vol. 51, no. 3, pp. 401–420, 2006.
[8]
H.
Tanner,
“On
the
controllability
of
nearest
neighbor
interconnections,” in Proceedings of the 43rd IEEE Conference on
Decision and Control, Dec. 2004, pp. 2467–2472.
[9]
M. Ji, A. Muhammad, and M. Egerstedt, “Leader-based multi-agent
coordination: controllability and optimal control,” in Proceedings of
the American Control Conference, Jun. 2006, pp. 1358–1363.
[10] A. Rahmani and M. Mesbahi, “On the controlled agreement problem,”
in Proceedings of the American Control Conference, Jun. 2006, pp.
1376–1381.
[11] A.
Lombardi
and
M.
H¨ornquist,
“Controllability
analysis
of
networks,” Physical Review E, vol. 75, no. 5, p. 056110, 2007.
[12] M. Ji and M. Egersted, “A graph-theoretic characterization of
controllability for multi-agent systems,” in Proceedings of the
American Control Conference, Jul. 2007, pp. 4588–4593.
[13] A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt, “Controllability
of multi-agent systems from a graph-theoretic perspective,” SIAM
Journal on Control and Optimization, vol. 48, no. 1, pp. 162–186,
2009.
[14] S. Martini, M. Egerstedt, and A. Bicchi, “Controllability analysis
of multi-agent systems using relaxed equitable partitions,” Int. J.
Systems, Control and Communications, vol. 2, no. 1,2,3, pp. 100–
121, 2010.
[15] Z. Ji, Z. Wang, H. Lin, and Z. Wang, “Interconnection topologies
for
multi-agent
coordination
under
leaderfollower
framework,”
Automatica, vol. 45, no. 12, pp. 2857–2863, 2009.
[16] B. Liu, T. Chu, L. Wang, and G. Xie, “Controllability of a
leader-follower dynamic network with switching topology,” IEEE
Transactions on Automatic Control, vol. 53, no. 4, pp. 1009–1013,
2008.
[17] S. Jafari, A. Ajorlou, A. G. Aghdam, and S. Tafazoli, “On the
structural controllability of multi-agent systems subject to failure:
A graph-theoretic approach,” in Proceedings of the 49th IEEE
Conference on Decision and Control, Dec. 2010, pp. 4565–4570.
[18] S. Jafari, A. Ajorlou, and A. G. Aghdam, “Leader selection in
multi-agent systems subject to partial failure,” in Proceedings of the
American Control Conference, Jun. 2011, pp. 5330–5335.
[19] ——, “Leader localization in multi-agent systems subject to failure:
A graph-theoretic approach,” Automatica, vol. 47, no. 8, pp. 1744–
1750, 2011.
[20] M. A. Rahimian and A. G. Aghdam, “Structural controllability of
multi-agent systems subject to simultaneous failure of links and
agents,” in Proceedings of the 50th IEEE Conference on Decision
and Control and European Control Conference, Dec. 2011, pp. 1443–
1448.
[21] C.-T.
Lin,
“Structural
controllability,”
IEEE
Transactions
on
Automatic Control, vol. 19, no. 3, pp. 201–208, 1974.
[22] H.
Mayeda,
“On
structural
controllability
theorem,”
IEEE
Transactions on Automatic Control, vol. 26, no. 3, pp. 795–798,
1981.
[23] J. Xu, Topological Structure and Analysis of Interconnection
Networks.
Kluwer Academic Publishers, 2001.
[24] M. A. Rahimian and A. G. Aghdam, “Structural controllability
of multi-agent networks: Importance of individual agents,” in
Proceedings
of
the
ACM
Research
in
Applied
Computation
Symposium, Dec. 2012, pp. 221–226.
[25] ——, “Structural controllability of multi-agent networks: Importance
of individual links,” in Proceedings of the American Control
Conference, Jun. 2013, pp. 6887 – 6892.
[26] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barab´asi, “Controllability of
complex networks,” Nature, vol. 473, no. 7346, pp. 167–173, 2011.
10