Article

Simultaneous Deployment and Tracking Multi-Robot

Strategies with Connectivity Maintenance
Javier Tardós 1 , Rosario Aragüés 1 * and Carlos Sagüés 1
1 Universidad de Zaragoza, Instituto de Investigación en Ingeniería de Aragón; [email protected] (J.T.);
[email protected] (R.A.); [email protected] (C.S.)
* Correspondence: [email protected]; Tel.: +34 976 76 23 37

Version January 31, 2018 submitted to Sensors

Abstract: Multi-robot teams composed by ground and aerial vehicles have gained attention during the
arXiv:1801.10043v1 [cs.RO] 30 Jan 2018

last years. We present a scenario where both types of robots must monitor the same area from different
view points. In this paper we propose two Lloyd-based tracking strategies to allow the ground robots
–agents– follow the aerial ones –targets–, keeping the connectivity between the agents. The first
strategy establishes density functions on the environment so that the targets acquire more importance
than other zones, while the second one iteratively modifies the virtual limits of the working area
depending on the positions of the targets. We consider the connectivity maintenance due to the fact
that coverage tasks tend to spread the agents as much as possible, which is addressed by restricting
their motions so that they keep the links of a Minimum Spanning Tree of the communication graph.
We provide a thorough parametric study of the performance of the proposed strategies under several
simulated scenarios. In addition, the methods are implemented and tested using realistic robotic
simulation environments.

Keywords: multi-robot; coverage; Lloyd; Voronoi; tracking; connectivity maintenance; Minimum

Spanning Tree;

1. Introduction
The coordination of autonomous robot teams has been a rising topic of interest during the last
decades. Formation control, surveillance or coverage are some of the most faced topics. Heterogeneous
robot teams are gaining attention for monitoring tasks in dynamic environments. For instance, in [1] a
method is presented for computing the localization of a group with both ground and aerial robots,
using measurements that are not associated to identified robots. Considering the low battery life of
the aerial robots, in [2] a group of them is assisted by a team of ground robots so that they can dock
and recharge their batteries. Some authors focus on particular applications such as mobile sensory
systems for monitoring environmental variables in greenhouses [3] instead of large sensor networks, or
sediment sampling in estuarine mudflats [4] with drilling ground vehicles and aerial imagery robots.
We face the problem of coordinating an heterogeneous team composed of both ground and
aerial robots so that they cooperate to monitor an environment. This way, the different view points
of the sensors can be used to build a richer representation of the 3D scene. In these scenarios, the
design of the coordination strategy is challenging, since several restrictions should be simultaneously
satisfied. Ground and aerial robots should observe the same area to build the representation of the
scene. In order to cover the greater area, agents should be deployed far from each other. However, the
communication should be kept so that they can exchange data and perform the computations. In this
framework, we propose a strategy in which the aerial robots act as leaders of the formation. Ground
robots –also referred to as agents– execute different coverage-based algorithms to keep the aerial ones
–from now on targets– on their sensing range.

Submitted to Sensors, pages 1 – 22 www.mdpi.com/journal/sensors

Version January 31, 2018 submitted to Sensors 2 of 22

We consider two alternatives for the ground robots, both of them built on classical Centroidal
Voronoi-based deployment ideas, which are also known as the Lloyd method, and has been often
used for static deployment. The alternatives proposed in this paper face the adaptation of these
ideas for tracking tasks. The first strategy consists of building density functions –also known as
importance functions– with focuses on the aerial robots. As they move, the density functions are
adapted accordingly, making the ground robots track them. All of the ground agents need to know
where the density functions are. This strategy has been previously used in the literature as it is
immediately extracted from the Lloyd algorithm. In the second strategy, we build virtual boundaries
around the regions in which the aerial and ground robots are operating. Ground robots coordinate to
evenly deploy over the region enclosed by these time varying virtual boundaries. This strategy has
never been used in the literature, as far as we know. It has the benefit that only the agents next to the
boundaries need to be informed about them, and the others will react to their neighbors positions. For
both strategies we ensure the ground robots remain connected by making them keep the links of a
Minimum–distance Spanning Tree (MST) in the communication graph. This MST is recomputed at
each iteration, so that agents have more freedom to move. Our method is centralized, although some
of its steps admit a parallel execution.
We provide a thorough parametric study of the performance of the proposed strategies under
several simulated scenarios built on MATLAB. We also evaluate the performance of the methods using
realistic robotic simulation environments based on Gazebo and ROS (Robot Operating System).
This paper is organized as follows. Section 2 gathers a review of related work in coverage, tracking
and connectivity maintenance. In Section 3 we present a base coverage algorithm with connectivity
maintenance, using Lloyd method and MST, respectively. Then, in Section 4 we propose two strategies
to adapt the coverage algorithm for tracking tasks. These strategies are tested with MATLAB scenarios
in Section 5. In Section 6 we carry out some realistic simulations with Gazebo and ROS, in order to
detect implementation difficulties. Finally, a set of conclusions and future work are given in Section 7.

2. Related Work
As previously stated, we consider tasks of environmental monitoring where a team of ground
and aerial robots establish coordination strategies to cover the same planar region with different view
points. During their mission, ground agents must simultaneously satisfy several restrictions. They
must follow the aerial robots and adapt dynamically to the positions covered by them. They also have
to deploy in their coverage task, keeping the links of the communication network connected. Note
that in this paper we will consider that coverage and monitoring tasks are similar, and will refer them
indifferently. In this section, we give an overview of the strategies the most related to the situation
considered in this paper, and discuss works on swarm aggregation, formation abstraction, formation
control, containment control and leader-follower tracking. We discuss as well some applications of
Voronoi and Lloyd methods.
Leader-follower methods [5,6] are consensus–based control laws that make a team of followers
track the position of the leader. The aim is that robots remain and finish close to each other and to the
leader. Swarm aggregation methods [7,8] make robots move as a single entity through an environment,
while avoiding obstacles. Although they do not collide, agents tend to be quite close to each other. In
containment control tasks [9–11], there are multiple stationary or dynamic leaders, which are aware of
the global objectives of the task. The remaining agents execute distributed local rules to follow the
leaders, so that they converge to the convex hull spanned by the leaders. Another approach is formation
abstraction [12]. The idea is to make agents remain inside the boundaries of a shape, e.g., polygonal,
which can be modified or bent to adapt to the environment. The application is quite interesting, but
ensuring collision avoidance or accurate tracking of the abstraction is usually hard to analyze. Here
we consider a similar idea, but associated to the well known and widely used Lloyd method. In this
context, it is easy to introduce other ideas such as connectivity maintenance and collision avoidance,
as well as uniform distribution on the area. There are also other leader-follower behaviors of higher
Version January 31, 2018 submitted to Sensors 3 of 22

complexity, as [13], where a team of leaders move so that they induce a set of periodic trajectories to be
followed by the dependent robots. All these methods are not appropriate to deal with the problem we
consider in this paper, since they may group too many agents, whereas we would like them to spread
as much as possible to cover a larger area as they explore the environment. Moreover, some of the
strategies described do not have control on the specific positions of the dependent robots.
Coverage and deployment algorithms are better suited for our purposes. The solutions
considering Voronoi partitioning or the Lloyd method are the most common. They give rise to
an easy to implement method, highly appealing. Voronoi partitioning consists of attaching to every
robot the set of points of the working area that are closer to them, and is very popular on deployment
and coverage tasks. In fact, many researches take advantage of Voronoi ideas. Some examples include
[14], where agents detect evaders within their Voronoi partition and pursue them. In [15] the goal
is to capture targets randomly distributed at an environment. Each agent detects targets inside its
Voronoi cell and estimate their position with a Kalman Filter. The Lloyd method uses the Voronoi
partitions to deploy the robots in the environment and they are iteratively moved to the centroid of
their Voronoi cell, separating them from each other and spreading over the working area. This method
is widely used in the literature. The situation where some areas have more importance, and robots
have unlimited sensing and communication capabilities, can be solved [16–18] by iteratively moving
the robots so that they reach centroidal Voronoi configurations. Several variations of this method have
been presented to consider, e.g., robots using outdated information about the positions of the other
team members [19], or agents that can only sporadically send information to a central base station
[20]. The works discussing limited sensing and communication capabilities are more realistic and
thus have a higher interest. Circular sensing footprints are included in [21], while [22] focuses on how
to learn and adjust the regions associated to each robot depending on their sensing and actuating
performances. Lloyd methods also allow the inclusion of obstacle-avoidance by the definition of safety
regions that ensure there will be no collisions between the agents [23]. These previous Lloyd-based
strategies focus on static environments, while we want to make the agents track the mobile aerial
robots. Lloyd coverage methods have been also used to track moving targets. The most commonly
used solution is to assign the density functions describing the importance of the environment to the
targets, and make them change with time. It has been experimentally validated that the Lloyd method
works properly in these cases [24,25]. This is one of the strategies we also adopt in our work. However,
in the presence of density functions, agents tend to accumulate nearby the targets. For this reason,
we explore an alternative strategy, that makes the agents spread uniformly along a varying working
region.
A limitation of some multi-robot strategies is that often there are no guarantees that the network
will remain connected as the agents operate. This is an important issue, since robots often must be able
to exchange data and communicate with each other in order to coordinate and to successfully fulfill
their tasks. In [26] this term is included in the control law governing the global coordination objective.
It keeps an accurate estimate of the time-varying Fiedler eigenvector. Depending on the high-level
coordination strategy, the connectivity control term will affect its achievement. It is remarkable that
they study both theoretically and experimentally these effects. In [27] there is a control law that enforces
connectivity, and an additional bounded control term, that encapsulates the high-level control law for
multi-robot cooperation. In addition, they design a control law that guarantees that the trajectories of
the agents remain within a domain. This is done by means of a repulsion vector nearby the boundaries
of the domain. A review of other connectivity control methods can be found in [28]. All these control
methods often rely on keeping up to date estimates of data that encapsulates global properties.
An alternative to maintain connectivity is to make the agents keep a set of links in the network.
The less restrictive method is to build a Tree in the graph. Specifically, the most used is the Minimum
Spanning Tree (MST), where the links are selected depending on an assigned weight. Note also that
as agents move, the weights of the tree branches change as well, and the last MST becomes obsolete.
So, this MST should be periodically recomputed. Several works adopt this method for connectivity
Version January 31, 2018 submitted to Sensors 4 of 22

maintenance in different situations. A method for continuous-time systems that preserves a set of
links is proposed in [29]. They mention that the best structure to be kept would be a Spanning
Tree, but any strategy is discussed for adapting the Tree–links as robots move. In [30] a high-level
method is presented for managing Tree topologies which can be combined with motion tasks such as
coverage, but the connections between the successive Trees and the Minimum Spanning Tree of the
communication graph have not been established yet. In [31] the authors present a formation control
method for unicycle kinematics robots that keeps the connectivity. A triggered method for readjusting
the Tree at some time instances during deployment tasks is developed in [32]. In [33] the connectivity
control takes place in a middle-ware layer to modify the goals of the robots when there is some risk
of breaking some constraint. Also in [34] the goal is to keep the links of a Tree, done in this case in a
separate layer at constant time intervals. In this paper we explore a different approach. We make the
agents keep the links of the Minimum–distance Spanning Tree (MST) of the communication graph. So,
we consider the re-computation of the MST at every time step, as it is done in [33,34]. However, in
order to alleviate the communication load, a triggering strategy as the one proposed in [31,32] could
be used.
As a result, our methods are centralized. However, as acknowledged in [35], some of the
assumptions established for graph-based distributed control strategies are difficult to accommodate in
realistic systems, and it may be reasonable to relax requirements on distributed methods. Some of the
parts of our method are anyway highly parallelizable. For instance, the MST computation could be
alleviated by using the distributed algorithm presented in [36]. We will investigate in the future ways
to transfer information on densities functions and on the virtual boundaries along the robot networks,
to get an even more distributed method. Our aim is to get one step closer to a real implementation of
the aerial-ground task, so we will use a realistic simulation environment.

3. Coverage for Static Deployment with Connectivity Maintenance

This section describes the basis of the coverage algorithm with connectivity maintenance for
a static environment. The ideas described in this section are a compound of the methods used in
[16–18,21,32,36,37]. The coverage task is performed using the Lloyd method, while the connectivity
maintenance is accomplished through a Minimum Spanning Tree. It is appropriate to remark here that
the algorithm described is implemented only in the ground robots.

3.1. Static Deployment

Considering a planar environment given by a convex polygon Q ∈ R2 , we want to deploy n
agents with positions pi ∈ Q, for i = {1, . . . , n}, in order to minimize the distances between them
and any point q ∈ Q. This is known in the literature as a locational optimization problem, and here
is solved using the Voronoi regions method. Partitioning Q into n regions, W = {W1 , ..., Wn }, the
coverage goal is accomplished by minimizing the cost function [16]
n Z
H ( P, W ) = ∑ f (kq − pi k) φ (q) dq, (1)
i =1 Wi

where f (kq − pi k) describes the performance of the sensing devices of the agents, and φ(q) is a
distribution density function that denotes the importance of each point. We assume W as the Voronoi
partition, V = {V1 , ..., Vn }, where

Vi = q ∈ Q | kq − pi k ≤ q − p j , ∀ j 6= i ,

i.e., the regions defined by attaching to each node, pi , their closest points, q. So, the cost function (Eq. 1)
to minimize is now
Version January 31, 2018 submitted to Sensors 5 of 22

n Z
H ( P, V ) = ∑ f (kq − pi k) φ (q) dq. (2)
i =1 Vi

The sensors of the agents observe better nearby points and, considering this fact, their performance
function is defined as f (kq − pi k) = kq − pi k2 . Recalling some basic quantities associated to a region
W and a density function φ, the mass MW , center of mass CW and polar moment of inertia JW,p are
defined as

1
Z Z Z
MW = φ (q) dq, CW = q φ (q) dq, JW,p = kq − pk2 φ (q) dq.
W MW W W

Considering the parallel axis theorem JW,p = JW,CW + MW k p − CW k2 , the cost function (Eq. 3)
and its gradient (Eq. 4) can be calculated as
n n
∑ JVi ,CVi + ∑ MVi pi − CVi
2
H ( P) = (3)
i =1 i =1

∂H

( P) = 2MVi pi − CVi , (4)
∂pi
as done in [16]. Thus, in order to deploy the agents so as to optimize the cost function, they iteratively
compute their Voronoi regions and move to their center of mass (Eq. 5). This gradient descent method
is commonly known as Lloyd method.
Z  −1 Z
CVi = φ (q) dq q φ (q) dq (5)
Vi Vi

Note that before the calculation of the Voronoi region of each agent, we need to know which agents
are their neighbors. The process we follow to solve this problem is the simple criterion proposed in
[37], explained next for the node p1 (see Figure 1). Assuming that we know the position of all the nodes,
pi , the method starts computing the boundaries of the Voronoi region, V1 , by the nearest neighbor,
then the second nearest, etc. After incorporating each one of these closest nodes, the algorithm checks
whether there is any other node inside a circle B( p1 , R), where R is a changing radius equal to the
maximum distance from p1 to any point of the region E1 computed until that iteration. This region is

Figure 1. Criterion for selecting the Voronoi neighbors.

Version January 31, 2018 submitted to Sensors 6 of 22

the one composed from drawing parallel lines to the Voronoi boundaries through the corresponding
already found neighbors. If there are not any more agents inside this circle, all the neighbors have been
found. In the example shown, p2 , p3 , p5 and p6 are Voronoi neighbors of p1 , while p4 and p7 are not.

3.2. Limited Sensing

The sensors carried by the agents have a limited range, so that they can not correctly observe
objects outside a circle with center pi and radius, their sensing radius s. Thus, instead of the
performance sensing model f (kq − pi k) = kq − pi k2 , we have a sensing area limited by s [32].

(
kq − pi k2 , if kq − pi k < s,
f (kq − pi k) =
s2 , otherwise.

Therefore, the coverage region of each agent is the intersection between the sensing area of each agent,
B( pi , s), and its corresponding Voronoi partition, Vi . As a result, the cost function associated to this
limitation is
n Z
Hs ( P) = ∑ kq − pk2 φ (q) dq. (6)
i =1 Vi ∩ B( pi ,s)

And the gradient of Hs in this case is

∂H  
( P) = 2MVi ∩ B( pi ,s) pi − CVi ∩ B( pi ,s) , (7)
∂pi
i.e., the gradient descent move to the centroid, but of the region defined as the intersection between
the Voronoi region and the sensing area.
Referring to Proposition 2.7 in [21], a local minimum of this limited cost function (Eq. 6), P∗ =
( p1 , . . . , p∗n ), is a local minimum of the cost function without limited range interactions (Eq. 2) if
∗

Q ⊂ ∪i∈{1,...,n} B( pi , s). So, this approximation obtains the local optimum solution of the locational
problem considering only the area covered by the sensing radius of the agents.

3.3. Limited Communication

For the communication purposes, we consider an r-limited Delaunay graph, as defined in [21],
with a communication radius r. In order to be able to run the methods proposed in this section in a
distributed fashion, the r-limited Delaunay graph requires r ≥ 2s communication radius, knowing the
positions of the agents at a distance at least 2s. If our communication radius is smaller, we need to
consider an altered cost function in which we will reduce the sensing region. Suppose s∗ is our original
sensing radius, and s the reduced one, so that 2s ≤ r. Following the steps in Proposition 2.5 [21], we
can relate their corresponding limited cost functions Hs∗ and Hs . Let f ( x ) = x2 be our performance
function, where f (0) = 0. Since we have a limited sensing problem, the performance function f s∗ is
defined as f s∗ ( x ) = f ( x ) for x < s∗ , and f s∗ ( x ) = f (s∗ ) for x ≥ s∗ . Reducing the sensing radius for
our distributed purposes, for s ∈ [0, s∗ ], we define the performance function f s given by f s ( x ) = f ( x )
f (s∗ )
for x < s, and f s ( x ) = f (s) for x ≥ s. Considering that s∗ ≥ s, we also define a constant β = f (s) ≥ 1,
and setting b = f (s∗ ) then f s∗ ( x ) ≤ b, ∀ x ∈ [0, s∗ ].
By construction, f s ( x ) ≤ f s∗ ( x ), ∀ x ∈ [0, s∗ ], so we can conclude that Hs ( P) ≤ Hs∗ ( P). Now,
consider the function f˜( x ) = β f s ( x ). Note that f˜( x ) = β f ( x ) ≥ f s∗ ( x ) for x < s, and f˜( x ) = β f (s) =
b = f s∗ ( x ) for x ≥ s. Therefore, we also can conclude that βHs ( P) ≥ Hs∗ ( P) and then, for all
P ∈ {∪in=1 B( pi , s∗ )}n ,

β Hs ( P ) ≥ Hs∗ ( P ) ≥ Hs ( P ) > 0 (8)

Version January 31, 2018 submitted to Sensors 7 of 22

Thus, as we can see, reducing the sensing radius so that this part of the method can be run on
1-hop neighbors, gives rise to another cost function, with specific relations to the original one.

3.4. Particular Closed-Form Expressions for Constant Density Functions

When the density function, φ(q), is defined as a constant, the centers of mass of the coverage
regions of each agent coincide with their geometric centroids. Assuming that the coverage regions, Wi ,


are convex polygons with Ni vertexes labeled as ( x0 , y0 ) , ..., x Ni −1 , y Ni −1 , the geometric centroid
is calculated as [16]

Ni −1
1
CWi ,x =
6MWi ∑ ( x k + x k +1 ) ( x k y k +1 − x k +1 y k )
k =0
(9)
Ni −1
1
CWi ,y =
6MWi ∑ ( y k + y k +1 ) ( x k y k +1 − x k +1 y k ) ,
k =0

where

Ni −1
1
MWi =
2 ∑ ( x k y k +1 − x k +1 y k ) . (10)
k =0

3.5. Connectivity Maintenance

Regarding now the connectivity maintenance problem, we use a Minimum Spanning Tree (MST),
as done in [31–34]. This method joints the n agents with n − 1 links. The nodes are connected in a
communication tree that minimizes the sum of the lengths of the links in order to allow the maximum
motion freedom.
Each agent must be within the communication radius r of its neighbors to keep the connectivity in
the whole system. However, the motion of the ground robots towards the centroids of their coverage
regions may break the communication links, if no additional restrictions are included. At every step,
the algorithm has to limit the motion of each pair of nodes (i, j) that are linked. The next positions
are restricted to a circle with center at ( pi + p j )/2 and radius r as shown in [38]. Figure 2 shows
the maximum movement (red wide line) available in the worst case, where agents need to move in
opposite directions.

Figure 2. Motion restrictions for linked agents.

In addition, the MST must be recalculated at each step of the simulation. Otherwise, the links
would heavily restrict the motion as agents move along.
With all these considerations, the process that the algorithm runs at each iteration to calculate the
MST in a centralized version is shown in the Algorithm 3.1. A decentralized version can be found in
[36] and a triggered strategy is shown in [32].
Version January 31, 2018 submitted to Sensors 8 of 22

Algorithm 3.1 MST calculation

1: Distances(i, j ) = pi − p j
2: Communicables(i, j) = Distances(i, j) ≤ r
3: MST_Graph = zeros(nxn)
4: MST_Nodes = 1
5: while length(MST_Nodes) ≤ (n − 1) do
6: for all i ∈ MST_Nodes do
7: Candidates = f ind (Communicables(MST_Nodes(i ), :))
8: for all j ∈ Candidates do
9: if ∃ MST_Nodes = Candidates( j) then
10: MST_Graph(MST_Nodes(i ), Candidates( j)) = 0
11: MST_Graph(Candidates( j), MST_Nodes(i )) = 0
12: else
13: Curr_Distance = Distances(MST_Nodes(i ), Candidates( j))
14: if Curr_Distance < Best_Distance then
15: Best_Distance = Curr_Distance
16: Best_Candidate = Candidates( j)
17: Best_Source = MST_Nodes(i )
18: end if
19: end if
20: end for
21: end for
22: MST_Nodes = append(Best_Candidate)
23: MST_Graph(Best_Source, Best_Candidate) = 1
24: MST_Graph(Best_Candidate, Best_Source) = 1
25: end while

To sum up, an iteration of the Lloyd algorithm for a static environment presented along this
section includes the statements in Algorithm 3.2.

Algorithm 3.2 Static Lloyd algorithm

1: Detect (Neighbors) . [37]
2: Coverage_regions = Voronoi_regions(Neighbors) ∩ Sensing_regions(Neighbors, s) ∩ Q
3: R (MST_Graph
Compute −1 )R . Algorithm 3.1
4: CWi = W φ ( q ) dq W q φ ( q ) dq . Eq. (5)
i i
5: Goal_Positions = Limit(CWi , MST_Graph) . [38]
6: Navigate (Goal_Positions)
7: Send (New_Positions)

4. Simultaneous Deployment and Tracking

Once we revised the static Lloyd algorithm, in this section we propose two alternatives to make it
able to deal with tracking tasks. This capability allows the agents following the leader aerial robots.
Version January 31, 2018 submitted to Sensors 9 of 22

4.1. Varying Importance Functions

The first alternative solves the tracking issue through the density function φ(q) introduced in the
coverage algorithm. This approach has been previously used in the literature to set up a dynamic
coverage from the Voronoi tessellation, as it is immediate from Lloyd static method. Each target is
given an importance function defined as
2
φ (q) = e−kq−ok , (11)

where o is the position of the target. These values weight the calculation of the centroids forcing the
agents to reach the center of each function, where the targets place. Therefore, all the agents must be
informed about the positions of all targets. Varying the position of these functions depending on the
targets motion, we can achieve a tracking behavior. The ground agents will deploy covering the same
area as the aerial robots.
Figure 3 shows an example of the behavior of this method under fixed targets, in order to note
how the agents deploy. Later, in Section 5, we will present more examples with moving targets. Agents
are represented with small red circles and their communication tree is the set of gray lines that link
them. The big blue circles represent the coverage regions of each agent. Finally, the grayscale concentric
circles are the importance functions -with darker gray for higher values- where the targets are placed.

Step 1/30 Step 6/30

30 30

20 20
y (m)

y (m)

10 10

0 0
0 10 20 30 0 10 20 30
x (m) x (m)
Step 15/30 Step 30/30
30 30

20 20
y (m)

y (m)

10 10

Importance functions
Robots
MST links
Coverage regions
0 0
0 10 20 30 0 10 20 30
x (m) x (m)

Figure 3. Ground robots positions in four steps while covering three fixed targets which are assigned
importance functions.

In the first steps, the agents start moving towards the area of interest. When they reach it, they
group around the first targets they get. Then they deploy to cover all of them.
The process executed at each iteration of the simulation is gathered in Algorithm 4.1.
Version January 31, 2018 submitted to Sensors 10 of 22

Algorithm 4.1 Varying Importance Functions

1: Detect (oi )
2: Propagate (oi )
3: Update (φ(q))
4: Execute (Static_Lloyd Iteration) . Algorithm 3.2

We have observed that this method provides an accumulation of ground robots around the targets,
which is not the behavior desired for coverage tasks. In addition, the local optimal behavior of this
method sometimes implies that some targets may be uncovered. For these reasons, we propose another
alternative, explained next.

4.2. Fictitious Boundaries Redefining

We propose another alternative based on redefining the boundaries of the working area. Since in
coverage problems with constant density functions agents tend to evenly deploy over the area, here
the idea is to modify in a virtual way the boundaries of this area to make agents adapt accordingly.
The interest of this method lies in the even deployment of the agents over the modified working area.
In addition, only the agents next to the virtual limits need to be informed about them. As far as we
know, this solution has not been used before in the literature.
We decide to define the new area as the minimum rectangle including both targets and agents. As
the area reduces, agents deploy with no different importances until the zone is as small as possible. If
there are enough agents, they will spread so on to cover all the targets. So this method requires the

Step 1/30 Step 6/30

30 30

20 20
y (m)

y (m)

10 10

0 0
0 10 20 30 0 10 20 30
x (m) x (m)
Step 15/30 Step 30/30
30 30

20 20
y (m)

y (m)

10 10
Redefined boundaries
Targets
Robots
MST links
Coverage regions
0 0
0 10 20 30 0 10 20 30
x (m) x (m)

Figure 4. Ground robots positions in four steps while covering three fixed targets delimited by fictitious
boundaries.
Version January 31, 2018 submitted to Sensors 11 of 22

aerial robots, that will act as leaders of the mission, to move in ways that can be covered by the ground
robots. This restriction depends on some factors like the number of agents or their sensing radius, and
will be studied in Section 5.
Figure 4 shows the same example as the previous alternative. Here the redefined fictitious
boundaries are the green lines and the targets are represented just with small gray circles. In first steps,
the agents move towards the targets while the rectangle reduces. Once the rectangle is as small as
targets allow, the agents spread over the final area. At the end, they cover a greater zone than the
previous alternative, deploying uniformly. One can notice that the agents must have a fixed bearing
reference in order to identify the orientation of the rectangle that iteratively defines the area to cover.
In this paper, we make the assumption that they have this information. In real implementations,
a mechanism for achieving this should be included. For instance, agents can be equipped with a
compass, or run a localization method, as in [1].
The process that this alternative runs in a centralized way at each simulation step to follow the
targets is shown in Algorithm 4.2.

Algorithm 4.2 Fictitious Boundaries Redefining

1: Detect (oi )
2: xmin,Area = min( pi,x , oi,x )
3: xmax,Area = max ( pi,x , oi,x )
4: ymin,Area = min( pi,y , oi,y )
5: ymax,Area = max ( pi,y , oi,y )
6: Area = [ xmin,Area , xmax,Area , ymin,Area , ymax,Area ]
7: Q = Area
8: Execute (Static_Lloyd Iteration) . Algorithm 3.2

4.3. Comparison between Both Alternatives

The example studied allows making a comparison between the alternatives shown. In addition to
the previously discussed differences between the amount of agents that need to be informed of the
positions of the moving aerial robots, in this section we explain some behavioral differences.
On the one hand, the importance functions alternative tend to group the ground robots around
the targets. Depending on the initial relative positions, this could make leave some others uncovered.
On the other hand, the method redefining the boundaries achieves a wider formation, covering a
greater zone than the first alternative. So this method focuses on the area around the targets, while the
first method focus on the targets themselves.
Considering this information, the importance functions method is better suited for individual
objectives whose environment is not important, while the boundaries redefining alternative is more
appropriate for concentrations of targets or wide areas of interest.

5. Simulations and Results

Both alternatives presented so far, are built on deployment methods which were originally
designed for static setups. Since our aim is to use these methods to dynamically track variations in the
region to be covered, a question that arises is how slow the modifications in the environment must be
in order for the agents to efficiently track them. This question is hard to answer from an analytical
point of view. Moreover, this speed may depend on several facts (number of agents, area to be covered,
sensing radius, communication radius, etc.). In this section we make a thorough parametric study
to identify the factors that influence the allowable speed. Here, the simulations are only executed
with MATLAB in order to get repeatable results, abstracting from implementation issues that carry
Version January 31, 2018 submitted to Sensors 12 of 22

3D simulation. In Section 6, we will carry out some 3D simulations in order to detect the problems
derived from this kind of implementation.
We define now the base experiment for the parametric study. We have a group of six ground
robots implementing the boundaries redefining algorithm. We will consider the particular case where
the targets fly in a rectangular formation composed of twelve aerial robots, and move 0.3 meters per
simulation step. The sensing radius of the ground robots is s = 3 m, and their communication radius
is r = 6 m.
Starting from this experiment, we are varying four parameters in order to study how they influence
in the algorithm behavior. These four parameters are the velocity of the formation to track, the sensing
radius, the number of agents, and the tracking method, comparing the alternatives proposed in this
paper.

5.1. Formation Velocity

In the first study we vary the formation velocity in the interval 0.25–0.5 m/step. The formation of
targets moves from left to right and its initial position is described in Figure 5, as well as the initial
position of the ground agents.

30

20
y (m)

10 Redefined boundaries
Targets
Agents
MST links
Coverage regions
0
0 10 20 30
x (m)

Figure 5. Initial positions of agents and targets.

Since the velocity is different on each case and in all of the setups we run 60 steps of the method,
the final position of the formation will be different. In Figure 6 we show the final dispositions of
all the robots for 0.25 and 0.5 m/step cases. For lower velocities, the algorithm is able to keep the
formation covered as it moves. However, if velocity increases the agents can not correctly cover the
whole formation. Some of them agglomerate in the rear formation leaving the front targets uncovered.

30 30

20 20
y (m)

y (m)

10 Redefined boundaries 10 Redefined boundaries

Targets Targets
Agents Agents
MST links MST links
Coverage regions Coverage regions
0 0
0 10 20 30 40 50 0 10 20 30 40 50
x (m) x (m)
(a) (b)

Figure 6. Final positions of agents and targets for (a) 0.25 m/step and (b) 0.5 m/step.
Version January 31, 2018 submitted to Sensors 13 of 22

Now in Figure 7(a) we represent the cost functions (Eq. 1) for each velocity along the simulation
steps. One can realize that the cost function stabilizes in a constant value for each velocity. This
behavior means that in all cases the agents spread to a constant disposition and reach the speed of the
formation, advancing with it. Furthermore, the metric minimizes for the lowest speeds, because the
agents cover the whole formation of the targets, as we have seen in Figure 6.

700 30
v = 0.25 m/step
600 v = 0.3 m/step
v = 0.35 m/step

(m)
500 v = 0.4 m/step
v = 0.5 m/step 25
Cost function

Distances sum
400

300
20 v = 0.25 m/step
200 v = 0.3 m/step
v = 0.35 m/step
100 v = 0.4 m/step
v = 0.5 m/step
0 15
10 20 30 40 50 60 10 20 30 40 50 60
Step Step
(a) (b)

Figure 7. Performance metrics, (a) cost function and (b) sum of agents distances to the formation center,
along the simulation depending on the formation velocity.

The behavior of the algorithm can also be monitored with a variable defined as
n
∑ k pi − O k , (12)
i =1

i.e., the sum of the distances of each ground robot to the center of the formation, O. This variable
can describe the quality of the coverage performed. Figure 7(b) gathers this sum of distances along
the simulation with the velocities studied. We observe the same behavior of the curves as in the cost
function. In case of higher velocities the sum of distances increases since the agents can not cover the
whole formation. The metric minimizes also for lower velocities. For this reason, from now on we will
show this performance metric (Eq. 12), since it is easier to understand and its behavior keeps similar to
the cost function in the experiments remaining.
The results obtained evidence the existence of a maximum formation speed that the algorithm
can correctly track. In [18] authors prove that the static coverage task for an one-dimensional case,
with φ(q) = 1 and an relative precision ε, is achieved in a time that polynomially depends on the
number of agents. Our case is dynamic and two-dimensional, so this study would imply a much
higher complexity. We obtain the maximum speed experimentally instead. Taking a look at the graphs,
we conclude that this maximum velocity is around 0.3 m/step for the described base setup. That is
why the base experiment is designed with this formation velocity, in order to highlight the differences
in the following studies.
Note that the velocity units are m/step. This will allow a higher maximum speed of the targets for
systems that execute quicker a step of the algorithm. This includes, e.g., the communication between
the agents, the computational load or the motion restrictions of the ground robots.

5.2. Sensing Radius

In this case we test five scenarios with sensing radius in the interval 2–4 meters. In order
to maintain the relation s = r/2 discussed in Section 3, the communication radius is changed
proportionally in the simulations. Initial positions are the same as in the previous experiments
and the simulations are run with 80 steps so that every experiment reaches the steady state.
Version January 31, 2018 submitted to Sensors 14 of 22

The sensing radius is often one of the parameters that affect the allowable speed of the formation
to be tracked. Showing the final positions of the robots for 2 and 3.5 meters (Figure 8), one can conclude
that, with lower sensing radius, the agents can not perform a wide deployment to cover the targets,
and they accumulate at the rear formation.

30 30

20 20
y (m)

y (m)
10 Redefined boundaries 10 Redefined boundaries
Targets Targets
Agents Agents
MST links MST links
Coverage regions Coverage regions
0 0
0 10 20 30 40 0 10 20 30 40
x (m) x (m)
(a) (b)

Figure 8. Final positions of agents and targets for (a) 2 m and (b) 3.5 m.

Figure 9 represents the sum of the distances from the ground agents to the formation center for
each sensing radius. As we said before, the smaller radius clearly make this variable increase because
the agents get to the back of the formation. On the other hand, while the radius increases we can
observe that the curves tend to the same value. This behavior is due to the fact that the agents have
an equilibrium distribution that balances their advance with the formation speed. Even though the
radius were much higher, the balance position would be the same.

30
(m)

25
Distances sum

20 s=2 m
s = 2.5 m
s=3 m
s = 3.5 m
s=4 m
15
20 40 60 80
Step

Figure 9. Sum of agents distances to the formation center along the simulation depending on the
sensing radius.

From the results, we can observe that as the sensing radius of agents decreases, they have more
difficulties to follow the moving formation. One of the possible reasons for this behaviors is that, at
every step, agents perform motions that keep them inside the intersection between their own Voronoi
and sensing region. When this region is smaller, agents perform motions that may be too short and
may avoid them tracking the aerial formation.
Another possible explanation would be that the communication links were too restrictive for
the motion of the agents. Recall that with each variation of the sensing radius we have changed the
communication radius too in order to keep the relation r = 2s. If the communication radius were
Version January 31, 2018 submitted to Sensors 15 of 22

higher, one could think that the agents may expand over the region and cover all the targets. For this
reason, we have run another set of simulations with larger communication radius, keeping a sensing
radius of 2.5 m, that in the previous experiment could not cover all the formation. In Figure 10, we
can see the results of the sum of distances to the center of the formation varying the communication
radius from 5 to 10 meters. We can observe that all the graphs for each communication radius concur
in the same curve. So we can conclude that this is not the reason why the agents can not follow the
formation with lower sensing radius.

30
(m)

25
Distances sum

20
r=5 m
r = 7.5 m
r = 10 m
15
20 40 60 80
Step

Figure 10. Sum of agents distances to the formation center along the simulation depending on the
communication radius.

These results also let us think that the connectivity maintenance method is not interfering with
the coverage and tracking goal, as far as the region can be indeed covered by the agents.

5.3. Number of Agents

This time we vary the number of ground robots in the system, duplicating them iteratively in
order to highlight the differences in the experiments. In this case we test from 4 to 16 agents. The initial
positions can not be the same because the number of ground robots is variable. The agents start from
positions that are close to the previous experiments, and run a 300 step simulation in order to be able
to observe the behavior of the curve with the highest number of agents.

6
(m)
Mean distance

2
4 agents
8 agents
16 agents
0
50 100 150 200 250 300
Step

Figure 11. Mean agents distance to the formation center along the simulation depending on the number
of agents.
Version January 31, 2018 submitted to Sensors 16 of 22

Due to the fact that the number of agents is variable, now the sum of the agents distances to the
formation center is not an appropriate variable to represent. We graph the mean distance instead in
Figure 11. The curves do not start from the same point as in the previous experiments because of this
same reason.
Contrary to what one could have expected, we observe that, with a higher amount of agents, the
method does not perform better, even though they have larger capabilities to cover an area. The mean
distance to the center of the formation increases as the number of agents is higher. Observing Figure
12, one can see the reason of this behavior. When there are more ground robots than needed, the extra
agents tend to accumulate at the rear formation. In case that this excess is extreme, the agents are very
close and interfere with each other, making their available space to move too short. This prevents
them to advance with the formation of targets, and their mean distance to the center of the formation
increases.
30 30

20 20
y (m)

y (m)

10 Redefined boundaries 10 Redefined boundaries

Targets Targets
Agents Agents
MST links MST links
Coverage regions Coverage regions
0 0
70 80 90 100 110 70 80 90 100 110
x (m) x (m)
(a) (b)

Figure 12. Final positions of agents and targets for (a) 4 robots and (b) 16 robots.

The agents that lead the motion of the team are those that have direct contact with a boundary
perpendicular to the direction of the target formation, i.e., the ones that are at the front and rear. They
have a direct modification of their Voronoi and sensing region, implying a quicker reaction than the
agents that are in the middle part of the formation. So the accumulation of unnecessary ground robots
increases the number of agents in the center of the formation, obstructing the motion of the whole
team. In case that many ground robots were needed, the exploration strategy of the aerial team should
consider a limit speed appropriate for the features of the system.

5.4. Tracking Method

Finally we compare the behavior of the algorithm on the base experiment varying the particular
method for the tracking task between the proposed in this paper. The initial positions of the agents are
again the positions shown in Figure 5 in both cases.
After a 30 step simulation, the final positions of the agents are shown in Figure 13. The
distributions of the agents over the formation are very similar. Both alternatives cover the twelve
targets when the steady state is reached.
Representing the sum of the agents distances to the center of the formation (Figure 14) we can
see that the value of the importance functions method quickly decreases, so its deployment is faster
and its response time is lower. On the other hand, the boundaries redefining method achieves a lower
value, so the agents in this case are a bit better deployed.
Version January 31, 2018 submitted to Sensors 17 of 22

30 30

20 20
y (m)

y (m)
10 Redefined boundaries 10 Redefined boundaries
Targets Targets
Robots Robots
MST links MST links
Coverage regions Coverage regions
0 0
0 10 20 30 0 10 20 30
x (m) x (m)
(a) (b)

Figure 13. Final positions of agents and targets for (a) boundaries redefining and (b) importance
functions methods.

30
(m)

25
Distances sum

20

Boundaries redefining
Importance functions
15
5 10 15 20 25 30
Step

Figure 14. Sum of agents distance to the formation center along the simulation depending on the
tracking method.

We can conclude then that both methods are suitable for this experiment, but the one redefining
the boundaries leads the comparison with a better deployment. In addition, as we saw in Section 4,
this alternative is more appropriate for targets agglomerations like the ones considered in the scenario
discussed in this section.

6. Realistic Simulations
With the aim of getting one step closer to a real implementation of the methods proposed in
Section 4, we have implemented and tested our methods using a realistic 3D physics simulator
specialized in robotics, Gazebo. We have used models associated to real robots –Turtlebots– which
have a differential drive behavior. They are controlled with ROS through specific packages that include
the robot description, the robot controller or the navigation stack. Configuring and connecting the set
of packages, we are able to send goal positions to the ground agents once we compute the coverage
algorithm. Iteratively, Turtlebots execute the Algorithms 4.1 or 4.2 described in Section 4. Between
iterations, they navigate to their goal positions using local lower level controllers, taking into account
their own motion kinematics restrictions. Since in the higher level methods described in Sections 3 and
4 we have not included any collision avoidance method, we incorporate a reactive local method in the
Gazebo implementation so that agents do not collide as they navigate.
Version January 31, 2018 submitted to Sensors 18 of 22

Lloyd methods, as other distributed strategies, make some assumptions that make the problem
more tractable. For instance, we consider that the position of the targets –here, aerial robots– are
already known. We also assume that ground robots can achieve any possible new position in every
step of the algorithm. In addition, for the localization of the agents, we use the ground-truth data given
by Gazebo.
We have designed four obstacle-free scenarios in order to examine the behavior of the algorithm
in some common situations and some extreme cases where it might fail. The reader can find in [39]
four videos with names “case_i”, where i is a number from 1-4. The videos represent the simulations
carried out in this section, in order of appearance. They contain the simulation in Gazebo and the
graphs obtained from MATLAB. The first one is a simple expansion without targets or zones more
important than others. This is just a coverage task and we do not need to implement any of the tracking
alternatives proposed. Figure 15 shows the final layout of the ground agents. We have developed a
visualization system that helps to understand the movement of each agent in the Gazebo simulation.
The black ground robots are the Turtlebots, which are the ones actually running the algorithms. We
add some elements like the targets, implemented as aerial robots that are moved discretely. The colored
spheres represent the positions of the ground robots and their goal positions in the current simulation
step. And the gray cylinders represent the communication tree reached at present step.

Figure 15. Final layout in a expansion without targets.

The second experiment consists on five agents implementing the boundaries redefining method
covering and tracking a formation of ten quadrotors that fly in a triangular formation. The final
disposition of both ground and aerial robots is shown in Figure 16.

Figure 16. Final layout in a formation tracking experiment.

Version January 31, 2018 submitted to Sensors 19 of 22

Third and fourth experiments are implementing the method with the importance functions to
track the targets. In the third case the targets start together and separate in opposite directions. The
ground team spread in a straight line until the point the communication tree allows them. Figure 17
shows this final straight formation of the agents.

Figure 17. Final layout in a experiment with two targets separating in opposite directions.

Finally, in the fourth case two targets describe curve trajectories that cross in the center of the
working area. In the first part of the experiment, the ground team covers the aerial targets and track
them. During the crossing, the ground agents get too close. Their collision avoidance method works
well and prevents them from crashing. However, their redeployment can not be correctly performed
because of the agglomeration produced, finally leaving one of the targets uncovered. Figure 18 shows
this fact at the end of the simulation.

Figure 18. Final layout in a experiment with two targets following crossed trajectories.

7. Conclusions
We propose and test two strategies to solve the problem of simultaneous coverage and tracking,
taking into account sensing and communication limitations, while ensuring that the network remains
Version January 31, 2018 submitted to Sensors 20 of 22

connected. Both strategies are based on Lloyd methods for static deployment. The first consists of
modifying the positions of density functions according to the movement of the targets. This solution
has been commonly used in the literature for adapting the static algorithm to tracking tasks. The second
strategy iteratively modifies the boundaries of the working area in order to follow the targets while
covering their surroundings. As far as we know, this is a novel solution for the problem addressed in
this paper.
The density functions solution results to react faster to the targets motion. However, depending on
the initial disposition of the agents, some targets may end up uncovered, while the agents concentrate
around other targets. In addition, all of the agents need to know the current positions of the targets in
order to compute the algorithm.
On the other hand, the boundaries redefining solution performs a slower reaction to the targets
motion, but achieves an even deployment over the area of interest. Furthermore, the information
about the position of the targets is traduced into the position of the boundaries, and this information is
only needed by the agents that have contact with them. So, the communication load is lighter when
implementing many agents.
A parametric study over the second method remarks the existence of a maximum velocity of the
targets that it can follow. We have shown that this limit speed depends on the number of agents and
their sensing radius, and does not depend on the communication radius.
We have implemented the system on a realistic simulator in order to validate in a better way
the alternatives proposed. We have noticed that placing the obstacle avoidance strategy at the lower
control level, often interferes with the higher level task. Thus, it would be more interesting to modify
the algorithm so that it ensures collision avoidance by construction. We also have considered that
the localization of the agents and the detection of the targets are ideally precise. In the future, some
method to deal with uncertainty might be included to the realistic test. In addition, the localization
system must include an agreement on common orientation for the boundaries redefining method.
Future work will focus on solving any of the previous limitations in order to design a decentralized
version of the whole algorithm. This will allow to carry out an implementation over real robots.

Acknowledgments: Supported by Spanish Ministerio de Economía y Competitividad DPI2015-69376-R and

Vicerrectorado de Política Científica, Universidad de Zaragoza JIUZ-2017-TEC-01 projects.

References
1. Stegagno, P.; Cognetti, M.; Oriolo, G.; Bulthoff, H.H.; Franchi, A. Ground and Aerial Mutual Localization
Using Anonymous Relative-Bearing Measurements. IEEE Transactions on Robotics 2016, 32, 1133–1151.
2. Mathew, N.; Smith, S.L.; Waslander, S.L. Multirobot Rendezvous Planning for Recharging in Persistent
Tasks. IEEE Transactions on Robotics 2015, 31, 128–142.
3. Roldán, J.J.; Garcia-Aunon, P.; Garzón, M.; de León, J.; del Cerro, J.; Barrientos, A. Heterogeneous
Multi-Robot System for Mapping Environmental Variables of Greenhouses. Sensors 2016, 16.
4. Deusdado, P.; Guedes, M.; Silva, A.; Marques, F.; Pinto, E.; Rodrigues, P.; Lourenço, A.; Mendonça, R.;
Santana, P.; Corisco, J.; Almeida, S.M.; Portugal, L.; Caldeira, R.; Barata, J.; Flores, L. Sediment Sampling in
Estuarine Mudflats with an Aerial-Ground Robotic Team. Sensors 2016, 16.
5. Cao, Y.; Ren, W.; Li, Y. Distributed discrete-time coordinated tracking with a time-varying reference state
and limited communication. Automatica 2009, 45, 1299–1305.
6. Zhao, Y.; Duan, Z.; Wen, G.; Chen, G. Distributed finite-time tracking of multiple non-identical second-order
nonlinear systems with settling time estimation. Automatica 2016, 64, 86–93.
7. Dimarogonas, D.V.; Kyriakopoulos, K.J. Connectedness Preserving Distributed Swarm Aggregation for
Multiple Kinematic Robots. IEEE Transactions on Robotics 2008, 24, 1213–1223.
8. Leccese, A.; Gasparri, A.; Priolo, A.; Oriolo, G.; Ulivi, G. A Swarm Aggregation Algorithm based on Local
Interaction with Actuator Saturations and Integrated Obstacle Avoidance. IEEE Int. Conf. on Robotics and
Automation, 2013, pp. 1865–1870.
Version January 31, 2018 submitted to Sensors 21 of 22

9. Cao, Y.; Ren, W.; Egerstedt, M. Distributed containment control with multiple stationary or dynamic
leaders in fixed and switching directed networks. Automatica 2012, 48, 1586–1597.
10. Kan, Z.; Shea, J.M.; Dixon, W.E. Leader–follower containment control over directed random graphs.
Automatica 2016, 66, 56–62.
11. Shi, G.; Hong, Y.; Johansson, K.H. Connectivity and Set Tracking of Multi-Agent Systems Guided by
Multiple Moving Leaders. IEEE Transactions on Automatic Control 2012, 57, 663–676.
12. Yoshida, K.; Fukushima, H.; Kon, K.; Matsuno, F. Control of a Group of Mobile Robots Based on Formation
Abstraction and Decentralized Locational Optimization. IEEE Transactions on Robotics 2014, 30, 550—-565.
13. Sabattini, L.; Secchi, C.; Cocetti, M.; Levratti, A.; Fantuzzi, C. Implementation of Coordinated Complex
Dynamic Behaviors in Multirobot Systems. IEEE Transactions on Robotics 2015, 31, 1018–1032.
14. Du, S.; Sun, X.; Cao, M.; Wang, W. Pursuing an evader through cooperative relaying in multi-agent
surveillance networks. Automatica 2017, 83, 155–161.
15. Moon, S.; Frew, E.W. Distributed Cooperative Control for Joint Optimization of Sensor Coverage and
Target Tracking. Int. Conf. on Unmanned Aircraft Systems, 2017, pp. 759–766.
16. Cortés, J.; Martínez, S.; Karatas, T.; Bullo, F. Coverage Control for Mobile Sensing Networks. IEEE
Transactions on Robotics and Automation 2004, 20, 243–255.
17. Martínez, S.; Bullo, F.; Cortés, J.; Frazzoli, E. On synchronous robotic networks—Part I: Models, tasks, and
complexity. IEEE Transactions on Automatic Control 2007, 52, 2199–2213.
18. Martínez, S.; Bullo, F.; Cortés, J.; Frazzoli, E. On synchronous robotic networks—Part II: Time Complexity
of Rendezvous and Deployment Algorithms. IEEE Transactions on Automatic Control 2007, 52, 2214–2226.
19. Nowzari, C.; Cortés, J. Self-Triggered Coordination of Robotic Networks for Optimal Deployment.
Automatica 2012, 48, 1077–1087.
20. Patel, R.; Frasca, P.; Durham, J.W.; Carli, R.; Bullo, F. Dynamic Partitioning and Coverage Control With
Asynchronous One-to-Base-Station Communication. IEEE Transactions on Control of Network Systems 2016,
3, 24–33.
21. Cortés, J.; Martínez, S.; Bullo, F. Spatially-distributed coverage optimization and control with limited-range
interactions. ESAIM: Control, Optimisation and Calculus of Variations 2005, 11, 691–719.
22. Pierson, A.; Figueiredo, L.C.; Pimenta, L.; Schwager, M. Adapting to sensing and actuation variations in
multi-robot coverage. International Journal of Robotics Research 2017, 36, 337—-354.
23. Kantaros, Y.; Zavlanos, M.M. Distributed communication-aware coverage control by mobile sensor
networks. Automatica 2016, 63, 209–220.
24. Li, W.; Liu, Y. Dynamic Coverage Control for Mobile Robot Network with Limited and Nonidentical
Sensory Ranges. IEEE Int. Conf. on Robotics and Automation, 2017, pp. 775–780.
25. Lee, S.G.; Diaz-Mercado, Y.; Egerstedt, M. Multirobot Control Using Time-Varying Density Functions.
IEEE Transactions on Robotics 2015, 31, 489–493.
26. Gasparri, A.; Sabattini, L.; Ulivi, G. Bounded Control Law for Global Connectivity Maintenance in
Cooperative Multirobot Systems. IEEE Transactions on Robotics 2017, 33, 700–717.
27. Boskos, D.; Dimarogonas, D.V. Robustness and Invariance of Connectivity Maintenance Control for
Multiagent Systems. SIAM Journal on Control and Optimization 2017, 55, 1887–1914.
28. Zavlanos, M.M.; Egerstedt, M.B.; Pappas, G.J. Graph-Theoretic Connectivity Control of Mobile Robot
Networks. Proceedings of the IEEE 2011, 99, 1525–1540.
29. Li, X.; Xi, Y. Distributed Cooperative Coverage and Connectivity Maineinance for Mobile Sensing Devices.
IEEE Conf. on Decision and Control, 2009, pp. 7891–7896.
30. Schuresko, M.; Cortes, J. Distributed Tree Rearrangements for Reachability and Robust Connectivity. SIAM
Journal on Control and Optimization 2012, 50, 2588–2620.
31. Aranda, M.; Aragüés, R.; López-Nicolás, G.; Sagüés, C. Connectivity-Preserving Formation Stabilization of
Unicycles in Local Coordinates Using Minimum Spanning Tree. American Control Conference, 2016, pp.
1968–1974.
32. Aragüés, R.; Sagüés, C.; Mezouar, Y. Triggered Minimum Spanning Tree for Distributed Coverage with
Connectivity Maintenance. European Control Conference, 2014, pp. 1881–1887.
33. Soleymani, T.; Garone, E.; Dorigo, M. Distributed Constrained Connectivity Control for Proximity
Networks based on a Receding Horizon Scheme. American Control Conference, 2015, pp. 1369–1374.
Version January 31, 2018 submitted to Sensors 22 of 22

34. Wagenpfeil, J.; Trachte, A.; Hatanaka, T.; Fujita, M.; Sawodny, O. A distributed minimum restrictive
connectivity maintenance algorithm. IFAC Proceedings Volumes 2009, 42, 365–370.
35. Robin, C.; Lacroix, S. Multi-robot target detection and tracking: taxonomy and survey. Autonomous Robots
2016, 40, 792–760.
36. Gallager, R.G.; Humblet, P.A.; Spira, P.M. A Distributed Algorithm for Minimum-Weight Spanning Trees.
ACM Transactions on Programming Languages and Systems 1983, 5, 66–77.
37. Cao, M.; Hadjicostis, C. Distributed algorithms for Voronoi Diagrams and Application in Ad-hoc Networks.
Preprint, Oct 2002.
38. Ando, H.; Oasa, Y.; Suzuki, I.; Yamashita, M. Distributed Memoryless Point Convergence Algorithm for
Mobile Robots with Limited Visibility. IEEE Transactions on Robotics and Automation 1999, 15, 818–828.
39. Google Drive folder. https://drive.google.com/drive/folders/1m-mRhso8R2Oz3PexRvtnk3PgkiEALd_
a?usp=sharing.

c 2018 by the authors. Submitted to Sensors for possible open access publication under the terms and conditions
of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).