Enforcing Biconnectivity in Multi-robot Systems

arXiv:1608.02286v1 [cs.RO] 8 Aug 2016

Mehran Zareh, Lorenzo Sabattini, and Cristian Secchi

Abstract— Connectivity maintenance is an essential task in
multi-robot systems and it has received a considerable attention
during the last years. A connected system can be broken into
two or more subsets simply if a single robot fails. A more robust
communication can be achieved if the network connectivity
is guaranteed in the case of one-robot failures. The resulting
network is called biconnected. In [1], we presented a criterion
for biconnectivity check, which basically determines a lower
bound on the third-smallest eigenvalue of the Laplacian matrix.
In this paper, we introduce a decentralized gradient-based
protocol to increase the value of the third-smallest eigenvalue
of the Laplacian matrix, when the biconnectivity check fails.
We also introduce a decentralized algorithm to estimate the
eigenvectors of the Laplacian matrix, which are used for
defining the gradient. Simulations show the effectiveness of the
theoretical findings.

I. I NTRODUCTION
In the last decade, decentralized control systems have been
increasingly investigated [2]–[4]. Advances in small size
computation, communication, sensing, and actuation have
caused a growing interest in decentralized control and decision making. Decentralized control of multi-robot systems
can be exploited for addressing many real world applications
(e.g., surveillance, exploration of unknown environments,
space-based interferometers, and automatic highways). In
these systems the robots coordinate their motion, in order
to achieve the global objective. Because of some unknown
obstacles, the robots might get trapped and hence disconnected from the team. Therefore, the robots must recognize
these phenomena and utilize proper strategies to preserve the
network connectivity. This is a substantial task that must be
seen as an objective of the control action. In the existing
literature on multi-robot control systems, the connectivity
of the network graph, i.e. the interaction pattern among the
robots, is assumed. There are two main approaches to preserve the connectivity: local and global maintenance. In local
connectivity maintenance the aim is to develop a controller
that keeps all initially existing communication links. Some
examples of decentralized control for local connectivity
maintenance can be found in [5], [6]. In comparison to the
local ones, the global connectivity maintenance algorithms
are based on global quantities of the network, and do not
restrict link failures or creation. In the last few years, several
works on this topic (see e.g. [7]–[10]) have appeared.
To obtain a robust communication in a multi-robot system,
the connectivity has to be guaranteed when a single robot
crashes or is suddenly called by a human user to perform
Authors are with the Department of Sciences and Methods
for Engineering (DISMI), University of Modena and Reggio
Emilia,
Italy
{mehran.zareh, lorenzo.sabattini,

cristian.secchi}@unimore.it

some unpredicted task. In other words, the resulting graph
must remain connected if one of the nodes and all its incident
edges are removed. Possessing this property, the graph is
called biconnected [11]. In addition to robustness, biconnectivity provides a better bandwidth for communication by
providing multiple paths to the destination. The connectivity
robustness of robot networks under failures is often neglected
in the literature. Some related works in graph theory describe
algorithms to find biconnected components in a graph based
on optimization theories. These algorithms mainly utilize
depth-first search or backtracking [12], [13] in a centralized
way. In [14], [15], the problem of biconnectivity check for
a network is presented. They propose an approach to detect
the biconnected component. Since the algorithm requires a
global probe, it cannot be seen as a decentralized one. Very
recently, [16] investigated the robustness problem in multirobot systems so that, despite robot failures, most of the
robots remain connected and are able to continue the mission.
Based on a maximum 2-hop communication, each robot is
able to detect dangerous topological configurations in the
sense of the connectivity and can mitigate in order to reach
a new position to get a better connectivity level. The paper,
based on local information, introduces a parameter, called
vulnerability, that allows each robot to detect the level of its
effect on the topological configuration.
In order to have a biconnected network graph, one needs to
recognize and relocate the robots, whose failure potentially
can cause disconnection, so that more connections are created. In [1], based on a decentralized algorithm, we proved
that the biconnectivity conditions are related to the thirdsmallest eigenvalue of the Laplacian matrix.
In this paper, we propose an algorithm to enable each node
of the network graph to detect if it is a crucial one for the
network connectivity. These nodes are termed as articulation
points. If there is no articulation point, then the resulting
graph is biconnected. Moreover, we provide an algorithm
for enforcing biconnectivity. First, each robot perturbs its
communication links’ weights, estimates the eigenvalues of
the perturbed Laplacian matrix, and checks the biconnectivity
condition introduced in [1]. Then, if the check fails, the
robots starts moving to new positions to create new links. The
main idea is to form a gradient-based controller to increase
the third-smallest eigenvalue of the Laplacian matrix. To
this end, we need to have decentralized estimates of the
third-smallest eigenvalue and an associated eigenvector. For
eigenvalue estimation we use the algorithm introduced by
[17]. We develop a decentralized protocol that allows each
robot to estimate the eigenvectors of the Laplacian matrix.
The outline of the paper is as follows. In Section II, we

introduce notations and some basic notions on graph theory,
which will be used in this work. The problem statement
is introduced in Section III. Section IV provides the main
contribution of this paper. We provide some theorems on
decentralized eigenvector and eigenvalue estimation, and
a gradient-based controller to achieve biconnectivity. In
Section V, the simulation results are given to verify the
theoretical findings. Finally, in Section VI, we conclude the
paper and describe the open problems.
II. P RELIMINARIES
In this section, we recall some basic notions and definitions on graph theory and introduce the notation used in the
paper.
The topology of bidirectional communication channels
among the robots is represented by an undirected graph
G(V, E) where V = {1, . . . , n} is the set of nodes (robots)
and E ⊂ V × V is the set of edges. An edge (i, j) ∈ E
exists if there is a communication channel between robots
i and j. Self loops (i, i) are not considered. The set of
robot i’s neighbors is denoted by Ni = {j : (j, i) ∈
E; j = 1, . . . , n}. The network graph G is encoded by the
so-called adjacency matrix, an n × n matrix A whose (i, j)th entry aij is greater than 0 if (i, j) ∈ E, 0 otherwise.
Obviously in an undirected graph matrix A is symmetric.
The degree P
matrix is defined as D = diag(d1 , d2 , . . . , dn )
n
where di = j=1 aij is the degree of node i. The Laplacian
matrix of a graph is defined as = D − A. The i-th column
of is denoted by li . The Laplacian matrix of a graph has
several structural properties. Due to the Gershgorin Circle
Theorem [18] applied to the rows or the columns of the
Laplacian, it is possible to show that it has non-negative
real eigenvalues for any undirected graph G. By construction
matrix has at least one null eigenvalue because either the
row sum or the column sum is zero. Furthermore, let 1 and
0 be respectively the vectors of ones and zeros with proper
dimensions, then 1 = 0 and 1T = 0T . Denote by λi (·) the
i-th smallest eigenvalue of a matrix, and vi (·) an associated
right eigenvector. Due to the symmetry, the eigenvalues of
the Laplacian matrix are all real, and can be ordered as
0 = λ1 () ≤ λ2 () ≤ . . . ≤ λn ().
In G a node i is reachable from a node j if there exists an
undirected path from j to i or vice versa. If G is connected
then is a symmetric positive semidefinite irreducible matrix.
Moreover, the algebraic multiplicity of the null eigenvalue
of is one. For a graph G, the second smallest eigenvalue of
the Laplacian matrix is called algebraic connectivity. This
eigenvalue gives a measure of connectedness of the graph.
Algebraic connectivity is a non-decreasing function of graphs
with the same set of vertices. This means that if G1 (V, E1 )
and G2 (V, E2 ) are two graphs constructed on the set V such
that E1 ⊆ E2 , then λ2 (G1 ) ≤ λ2 (G2 ). In other words, the
more connected the graph becomes the larger the algebraic
connectivity will be.
We denote ãi = [aij ]T ∈ Rn , j = 1, . . . , n, j 6= i. We
also define the perturbed adjacency matrix Ai () obtained

from A by multiplying all aij and aji s by  ∈ R+ . The associated perturbed degree Di () = diag(Ai ()1) and Laplacian
matrix i () = Di ()−Ai () are defined accordingly. Indicate
the reduced graph G Ri achieved from G by removing node i
and all its incident edges. Accordingly, ARi is the adjacency
matrix, DRi is the degree matrix, and Ri is the Laplacian
matrix of G Ri .
III. P ROBLEM S TATEMENT
We study the biconnectivity maintenance problem in
multi-robot systems. Communications are assumed to be
between each robot and its 1-hop neighbors, or neighborto-neighbor data-exchange. The connectivity of the initial
network is also presumed.
The following definitions from the algebraic graph theory
will be used in the rest of this paper.
Definition 1. A vertex i ∈ V of a connected graph G is
called an articulation point if GiR is not connected.
Definition 2. A connected graph is called biconnected if it
has no articulation point.
Definition 3. A block in G is a maximal induced connected
subgraph with no articulation point. If G itself is connected
and has no articulation point, then G is a block [20].
Definition 4. If the sub-graph based on node i and its
neighbors Ni is a block, then i is called a locally-biconnected
node.
We raise the two following problems.
Problem 1 For a multi-robot system with a connected interaction graph G, using a distributed algorithm, find if the
resulting network graph is biconnected.
Problem 2 If the network graph is not biconnected, then
provide an algorithm to enforce this property.
The former problem was investigated in the authors’
previous work [1]. In this paper, we focus on the latter. In
other words, we develop a decentralized algorithm to bring
a connected network into a biconnected one, i.e., the robots
keep their connectivity even if one of them, for any reason,
fails to communicate with the others.
IV. M AIN C ONTRIBUTION
To enable the robots to achieve a biconnected network
graph, they must be aware of their connectivity status in the
graph, when the corresponding nodes on the network graph
and all the incident edges are disconnected. If the graph
remains connected in the case of robot i failure, then the
node i in the graph is not an articulation point. By putting
weakly connected links between node i and its neighbors,
we aim at providing an estimate of the condition after a
complete disconnection. This was proven in our previous
work [1]. We obtained that, if the third-smallest eigenvalue
of the Laplacian matrix, for a nearly disconnected network,

at any locally biconnected node i and for some small  ∈ R,
meets the following condition
n
√ X
λ3 (i ()) >  n (
a2ik )1/2 ,

(1)

k=1

then the resulting system is biconnected. If this condition
does not hold, then in order to obtain a biconnected graph,
the third-smallest eigenvalue must increase. In order to
increase this value, we will hereafter define a decentralized
protocol based on gradient descent. Note that
λ3 (i ()) = v3T (i ())i ()v3 (i ()),
To obtain the gradient, an estimate of v3 (i ()) is required.
In this way, our approach to solve the biconnectivity
problem contains the following steps
a) First, using the algorithm introduced in [17], we estimate
the third-smallest eigenvalue of the Laplacian matrix.
b) Then, we propose a decentralized consensus estimator to
obtain the eigenvector associated with the third-smallest
eigenvalue of the Laplacian matrix.
c) Finally, using a decentralized gradient-based protocol, the
increment of the third-smallest eigenvalue is ensured.
The next section provides one of the key results of this
paper.
A. Eigenvector estimation
In this section, we introduce an estimation protocol to
obtain any eigenvector of the Laplacian matrix. These results
can be specified to obtain the eigenvector associated with the
third-smallest eigenvalue of the Laplacian matrix.
Assume that, in a multi-robot system, the network graph
G is connected. Let˜= − λ̃()I, with λ̃() ∈ {λ1 (), . . . , λn ()}.
The eigenspaces of and˜are identical. Specifically, the kernel
of ˜ lies in span(ṽ()). Denote by ˜li ∈ Rn the i-th column of
˜li ˜liT
˜. Let Pi = T , i = 1, . . . , n, and define a block-diagonal
˜li ˜li
matrix P = diag(P1 , . . . , Pn ).
Consider the following distributed estimator
żi (t) =

n
X

aij (zj (t) − zi (t)) − Pi zi (t), i = 1, . . . , n, (2)

j=1

in which zi , i = 1, . . . , n is the i-th agent’s estimation vector
for ṽ(). We can rewrite the above equation in state-space
form as
ż(t) = −M z(t),
(3)
in which z = [z1T , . . . , znT ]T , M = k(⊗I +P ), with k ∈ R+
being the estimator gain.
The following assumption will be used in the rest of this
paper.
Assumption 1 All eigenvalues of the Laplacian matrix are
simple.
Remark 1. Note that the elements of are functions of the
relative distances. Since the robot’s positions are supposed to
be random, the elements can get any real value. Accordingly,

is a doubly-stochastic unstructured matrix. Therefore, the
eigenvalues and the elements of any eigenvector of are
almost surely distinct. If the distances, in some applications,
get equal values, then we can define random edge weights
to ensure Assumption 1. Therefore, the above assumption is
not restrictive. This will be verified later by simulations.
The next lemmas demonstrate some properties of P and
⊗ I.
Lemma 1 Matrix P has all eigenvalues equal to 0 and 1.
Proof: From the definition of P , we can show that
P · P = diag(P1 · P1 , . . . , Pn · Pn ).
We have
P i · Pi =

˜li (˜liT ˜li )˜liT
˜li ˜liT
˜li ˜liT ˜li ˜liT
·
=
=
= Pi .
˜liT ˜li ˜liT ˜li
˜liT ˜li (˜liT ˜li )
˜liT ˜li

Consequently
P · P = diag(P1 , . . . , Pn ) = P.
Therefore λ2 (P ) = λ(P ), which gives λ(P ) = 0, or λ(P ) =
1.
In the next lemma, using the fact that any two eigenvectors
associated to two different eigenvalues of are perpendicular,
from Assumption 1, we select a set of orthonormal eigenvectors v1 (), . . . , vn ().
Lemma 2 The eigenvalues of ⊗ I are achieved by n-times
repeating each eigenvalue of , i.e.,
λkn+1 (⊗I) = . . . = λ(k+1)n (⊗I) = λk (), k = 0, . . . , n−1.
The set {vk ()⊗vl (), l = 1, . . . , n} forms an orthogonal basis
for the eigenspace of ⊗I associated with λk (), k = 1, . . . , n.
Proof: It is trivial to show that the eigenvalues of ⊗ I
are n times repeatedly achieved from those of .
By multiplying ⊗ I by vk () ⊗ vl () we get
( ⊗ I)(vk () ⊗ vl ())

= vk () ⊗ Ivl ()
= λk ()(vk () ⊗ vl ()),

which means that vk () ⊗ vl () is an eigenvector of ⊗ I
associated with λk (). Note that, for l 6= m we have
vlT ()vm () = 0. Then
(vk () ⊗ vl ())T (vk () ⊗ vm ())
= vkT ()vk () ⊗ vlT ()vk () = 0.
This shows the eigenvectors orthogonality and completes the
proof.
Corollary 1 The set {1 ⊗ v1 (), . . . , 1 ⊗ vn ()} forms an
orthogonal basis for the kernel of ⊗ I.
Lemma 3 The intersection of the kernels of ⊗ I and P is
span(1 ⊗ ṽ()).
Proof: It is trivial to show that 1 ⊗ ṽ is in the kernel
of P . Now, by contradiction we prove that there is no other
intersection between the kernels. Let 1 ⊗ ψ, ψ ∈ Rn ∈
/

span(ṽ()), be another intersection for the kernels of ⊗ I and
P . Then
P (1 ⊗ ψ) = 0.
From the definition of P we get that
1 ˜i ˜iT
l l ψ = 0, i = 1, . . . , n.
˜liT ˜li

From Lemma 4, we know that M is a positive semi-definite
matrix whose kernel is span(1⊗ ṽ()). As a consequence, M 2
is also a positive semi-definite matrix with only one nulleigenvalue, and V̇ gets a value equal to zero only on the
equilibrium space. This implies that the system converges
along the vector 1 ⊗ ṽ(). Or
lim z(t) = γ(1 ⊗ ṽ()), γ ∈ R

t→∞

This gives that
˜liT ψ = 0, i = 1, . . . , n.
Since span(ṽ()) is the kernel of˜, the above equation does not
give any solution for ψ. As a consequence, the intersection
of the kernels of and P is span(1 ⊗ ṽ()).
Lemma 4 For a connected graph G, if all Laplacian’s
eigenvalues are simple, the matrix M in (??) is positive
semidefinite, and has a simple null eigenvalue.
Proof: For any non-zero normalized vector x ∈
2
Rn , xT x = 1, the Rayleigh quotient [21] of M is defined
as
R(M, x) = xT M x.
(4)
Let γ1 ≤ . . . ≤ γn2 be eigenvalues of M . Since M , ⊗ I,
and P are symmetric matrices, and hence Hermitian, from
the min-max theorem [21] we get
γ1 = min{R(M, x) : x 6= 0}

= k min{R( ⊗ I, x)
+R(P, x) : x 6= 0}
= k min{R( ⊗ I, x) : x 6= 0}
+k min{R(P, x) : x 6= 0}
= kλ1 + kλPmin = 0.

From Lemma 2, we know that 1 ⊗ vj , j = 1, . . . , n form an
orthogonal basis for the kernel of ⊗ I. From Lemma 3, we
know that the intersection of the kernels of ⊗ I and P is
span(1 ⊗ ṽ()). This means that
R(M, x) = 0
occurs only for x = 1 ⊗ ṽ(). In other words, M is a positive
semi-definite with the only one null-eigenvalue associated
with the one-dimensional kernel span(1 ⊗ ṽ()).
The following theorem provides conditions to estimate the
eigenvectors of the Laplacian matrix.
Theorem 1 For the system given in (??) with a connected
undirected graph and a Laplacian matrix with all simple
eigenvalues, we get
lim zi (t) = γṽ(), i = 1, . . . , n, γ ∈ R.

t→∞

(5)

Proof: Note that z(t) = 1 ⊗ ṽ() is an equilibrium point
for the system in (??). Consider the following Lyapunov
functional
V (t) = z T (t)M z(t).
(6)
It is easy to show that z(t) = 1⊗ ṽ() is an equilibrium space.
By differentiating with respect to time we get
V̇ (t) = −z T (t)M 2 z(t).

(7)

which proves (??).
Theorem 1 says that, if the network graph does not change
during a certain time interval, then each agent’s estimate,
zi (t), converges to a vector parallel to the eigenvector of the
Laplacian matrix. This is a key result of this paper.
Remark 2. The presented algorithms for eigenvalue and
eigenvector estimation are independent. However, the latter
algorithm requires an estimate of the eigenvalues. Hence,
the total estimation time includes the time for eigenvalue
estimation plus the time for eigenvector estimation. It is
assumed that during this time the network graph remains
constant.
B. Decentralized gradient construction
In this section we derive the analytical form of a completely decentralized gradient controller to increase the value
of any non-null eigenvalue of the Laplacian matrix.
For an undirected graph G with the Laplacian matrix ,
consider the eigenvalue problem
v() = λ()v(),
with v() ∈ Rn being a normalized vector. By multiplying
both sides by v T () we obtain
v T ()v() = λ()v T ()v() = λ().
Derivation with respect to the node i’s position gives
d(v T ()v())
dv T ()
=
v()
dpi
dpi

dλ()
=
dpi

(8)

dv()
d
v() + v T ()
.
+v ()
dpi
dpi
T

Since is symmetric, we know that
v T ()

dv()
dv T ()
1 d(v T ()v())
=
v() = λ
= 0.
dpi
dpi
2
dpi

Then from (??) we get
dλ()
d
= v T ()
v().
dpi
dpi

(9)

Consider not a group of single integrator robots, ṗi = ui ,
where pi is the position of the i-th robot. Then, we introduce
the following gradient-based controller
ui =

dλ()
d
= v T ()
v().
dpi
dpi

(10)

If the conditions in (??) does not hold, we use the above
gradient control to increase the value of λ3 (()).

Node i starts

Is it locally
biconnecte?

yes

Fig. 2: Network graph of a randomly positioned multi-robot
system

no
Multiply
the adjacent
weights by 

V. S IMULATION RESULTS

Estimate
eigenvalues [17]

In this section we aim at showing the effectiveness of the
proposed algorithms. We suppose that the communication is
defined by the R-disk model, in which the elements of the
adjacency matrix are defined as

2
e−(kpi −pj k )/(2σ) kpi − pj k ≤ R
aij =
(11)
0
kpi − pj k > R,
The selected communication parameters are
R = 0.5 σ = 0.125.

Does
biconnectivity
check [1]
hold?

yes

In the following example, the performance of the eigenvector estimation algorithm is demonstrated.
Stop

no
Use gradientbased controller
in (??)

Estimate
v3 (i ())
from (??)

Fig. 1: Biconnectivity algorithm.

Remark 3. The elements of the Laplacian matrix that depend
on pi are the ones in the i-th row, and due to symmetry,
d
the i-th column. Consequently, the elements of
are
dpi
all zeros except for the i-th row and i-th column. This
implies that ui can be computed in a decentralized way.
Now we are ready to render our decentralized biconnectivity
enforcing algorithm. The flowchart in Fig. 1 shows how the
biconnectivity algorithm works.
Remark 4. Note that the algorithm is separately done by any
single robot, and all the included sub-algorithms are based
on the local data exchange. Therefore, the whole procedure
is totally decentralized.

Example 1. For the random graph in Fig. 2, the adjacency
and Laplacian matrices can be computed from (??).
The eigenvalues of the Laplacian matrix are
{0, 0.303, 0.412, 1.125, 1.288, 1.721, 2.327, 2.970}.
Normalized eigenvectors associated with the second and
the third-smallest eigenvalues (λ2 = 0.303 and λ3 = 0.412)
are




0, 494
0.208
 −0, 446 
 0.178 




 −0, 311 
 0.103 




 −0, 277 
 0.130 



v2 = 
v
=
3
 0, 490 
 0.069  .




 −0, 258 
 0.049 




 0, 277 
 0.189 
0, 031
−0.925
The simulation results for k = 50 and 500 are shown in
Figs. 3 and 4. The corresponding elements of the estimation
vectors for different robots are shown with the same colors.
We can see that, by use of the proposed algorithm, the state of
each robot very rapidly converges to the desired eigenvector.
By increasing k the convergence rate increases. We can see
that the Assumption 1 is true.
The next example demonstrates the results of a consensus
problem in a multi-robot system, once with and another time
without the biconnectivity algorithm.

(a) k=50

Fig. 5: Initial network graph of the multi-robot system in
Example 2.

(b) k=500

Fig. 3: Decentralized estimation of v2

Fig. 6: Network graph after t = 1 sec without biconnectivity
algorithm.

Example 2. Consider the graph in Fig. 5 with n = 8 nodes.
At time zero, the robots start running a simple consensus
protocol
ṗi = uci ,
where pi indicates the position of the robot i, and uci is the
local controller
X
uci =
aij (pj − pi ).
j∈Ni

(a) k=50

Fig. 6 shows that the system gets disconnected after t =
1 sec. Next, the biconnectivity algorithm is utilized. We first
check biconnectedness, following the procedure introduced
in [1]. Note that the node ∗ in Fig. 5, is the only not locally
biconnected one, and hence, it must meet the sufficient
conditions introduced in (??). Based on the criterion (??),
and multiplying the weight of the node ∗ by  = 0.05, we
get
n
p X
λ3 (∗ ()) = 0.013 <  (8)
a∗k = 0.0022,
k=1

(b) k=500

Fig. 4: Decentralized estimation of v3

which implies that the biconnectivity check fails. In order
to increase the value of λ3 (∗ ()), we use the gradient-based
controller in (??), by estimating v3 (∗ ()) implementing (??).
From (??) and (??), we obtain the following biconnectivity

(a) t = 0.4 sec.

(b) t = 1 sec.

Fig. 7: Network graph achieved from biconnectivity algorithm.

protocol for node ∗
d∗ ()
= v3T (∗ ()) ∗ v3 (∗ ())
dp
Pn
p∗ − pj
,
= − j=1 a∗j (v3j (∗ ()) − (v3j (∗ ()))2
σ2
in which v3j (∗ ()) indicates the j-th element of the estimation vector v3 (∗ ()). As shown in Fig. 7, the graph reaches
biconnectivity after 1 second.
ub∗

VI. C ONCLUSIONS
In this paper, we developed a decentralized algorithm to
achieve graph biconnectivity in multi-robot systems. We presented an estimation protocol to be executed by every single
robot to estimate the eigenvectors of the Laplacian matrix.
Simulations showed that, by increasing the estimation gain,
we can expedite the convergence rate. Using the estimate of
the eigenvector, a gradient control was proposed to increase
the third-smallest eigenvalue of the Laplacian matrix, to
reach the requirements of the biconnectedness, introduced
by the authors in [1]. In our future work, we aim at finding
the convergence rate of the proposed algorithm.
R EFERENCES
[1] M. Zareh, C. Secchi, and L. Sabattini, “An algebraic decentralized
biconnectivity check in multi-robot systems with weighted communication graphs,” in Decision and Control Conference, CDC16, 55 IEEE
Conference on (Submitted). IEEE, 2016.

[2] R. Olfati-Saber and J. S. Shamma, “Consensus filters for sensor
networks and distributed sensor fusion,” in Decision and Control, 2005
and 2005 European Control Conference. CDC-ECC’05. 44th IEEE
Conference on. IEEE, 2005, pp. 6698–6703.
[3] M. Zareh, C. Seatzu, and M. Franceschelli, “Consensus of secondorder multi-agent systems with time delays and slow switching topology,” in Networking, Sensing and Control (ICNSC), 2013 10th IEEE
International Conference on, 2013, pp. 269–275.
[4] M. Zareh, “Consensus in multi-agent systems with time-delays,” Ph.D.
dissertation, University of Cagliari, May 2015.
[5] G. Notarstefano, K. Savla, F. Bullo, and A. Jadbabaie, “Maintaining
limited-range connectivity among second-order agents,” in American
Control Conference, 2006. IEEE, 2006, pp. 6–pp.
[6] A. Ajorlou, A. Momeni, and A. G. Aghdam, “A class of bounded
distributed control strategies for connectivity preservation in multiagent systems,” Automatic Control, IEEE Transactions on, vol. 55,
no. 12, pp. 2828–2833, 2010.
[7] M. M. Zavlanos, M. B. Egerstedt, and G. J. Pappas, “Graph-theoretic
connectivity control of mobile robot networks,” Proceedings of the
IEEE, vol. 99, no. 9, pp. 1525–1540, 2011.
[8] L. Sabattini, N. Chopra, and C. Secchi, “Decentralized connectivity
maintenance for cooperative control of mobile robotic systems,” The
International Journal of Robotics Research, vol. 32, no. 12, pp. 1411–
1423, 2013.
[9] L. Sabattini, C. Secchi, N. Chopra, and A. Gasparri, “Distributed
control of multirobot systems with global connectivity maintenance,”
Robotics, IEEE Transactions on, vol. 29, no. 5, pp. 1326–1332, 2013.
[10] P. Robuffo Giordano, A. Franchi, C. Secchi, and H. H. Bülthoff,
“A passivity-based decentralized strategy for generalized connectivity
maintenance,” The International Journal of Robotics Research, vol. 32,
no. 3, pp. 299–323, 2013.
[11] M. C. Golumbic, Algorithmic graph theory and perfect graphs.
Elsevier, 2004, vol. 57.
[12] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM
journal on computing, vol. 1, no. 2, pp. 146–160, 1972.
[13] R. E. Tarjan and U. Vishkin, “Finding biconnected componemts and
computing tree functions in logarithmic parallel time,” in Foundations
of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984,
pp. 12–20.
[14] M. Ahmadi and P. Stone, “A distributed biconnectivity check,” in
Distributed Autonomous Robotic Systems 7. Springer, 2006, pp. 1–10.
[15] ——, “Keeping in touch: Maintaining biconnected structure by homogeneous robots,” in Proceedings of the National Conference on
Artificial Intelligence, vol. 21, no. 1. Menlo Park, CA; Cambridge,
MA; London; AAAI Press; MIT Press; 1999, 2006, p. 580.
[16] C. Ghedini, C. Secchi, C. H. C. Ribeiro, and L. Sabattini, “Improving
robustness in multi-robot networks,” in IFAC Symposium on Robot
Control (SYROCO). IFAC, 2015.
[17] M. Franceschelli, A. Gasparri, A. Giua, and C. Seatzu, “Decentralized
estimation of laplacian eigenvalues in multi-agent systems,” Automatica, vol. 49, no. 4, pp. 1031–1036, 2013.
[18] C. D. Meyer, Matrix analysis and applied linear algebra. Siam, 2000.
[19] M. Fiedler, “A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory,” Czechoslovak Mathematical
Journal, vol. 25, no. 4, pp. 619–633, 1975.
[20] D. B. West, Introduction to graph theory. Prentice hall Upper Saddle
River, 2001, vol. 2.
[21] R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university
press, 2012.

