Collaborative Visual Area Coverage using Unmanned Aerial Vehicles

arXiv:1612.02065v1 [] 6 Dec 2016

Sotiris Papatheodorou, Anthony Tzes and Yiannis Stergiopoulos

Abstract— This article addresses the visual area coverage
problem using a team of Unmanned Aerial Vehicles (UAVs).
The UAVs are assumed to be equipped with a downward facing
camera covering all points of interest within a circle on the
ground. The diameter of this circular conic-section increases
as the UAV flies at a larger height, yet the quality of the
observed area is inverse proportional to the UAV’s height. The
objective is to provide a distributed control algorithm that
maximizes a combined coverage-quality criterion by adjusting
the UAV’s altitude. Simulation studies are offered to highlight
the effectiveness of the suggested scheme.
Index Terms— Cooperative Control, Autonomous Systems,
Unmanned Aerial Vehicles

I. I NTRODUCTION
Area coverage over a planar region by ground agents has
been studied extensively when the sensing patterns of the
robots are circular [1, 2]. Most of these techniques are based
on a Voronoi or similar partitioning [3, 4] of the region
of interest. However there have been studies concerning
arbitrary sensing patterns [5, 6] where the partitioning is not
Voronoi based [7]. Both convex and non-convex domains
have been examined [8].
Many algorithms have been developed for the mapping by
UAVs [9–11] relying mostly in Voronoi-based tessellations.
Extensive work has also been done in area monitoring by
UAVs equipped with cameras [12, 13]. In these pioneering
research efforts, there is no maximum allowable height that
can be reached by the UAVs and for the case where there
is overlapping of the covered areas, this is considered an
advantage compared to the same area viewed by a single
camera.
In this paper the persistent coverage problem of a planar
region by a network of UAVs is considered. The UAVs are
assumed to have downwards facing visual sensors with a
circular sensing footprint, while no assumptions are made
about the type of the sensor. The covered area as well as
the coverage quality of that area depend on the altitude
of each UAV. A partitioning scheme of the sensed region,
similar to [7], is employed and a gradient based control
law is developed. This control law leads the network to a
locally optimal configuration with respect to a combined
coverage-quality criterion, while also guaranteeing that the
UAVs remain within a desired range of altitudes. This article,
compared to [13] assumes the flight of the UAVs within a
This work has received funding from the European Union’s Horizon
2020 Research and Innovation Programme under the Grant Agreement
No.644128, AEROWORKS.
The authors are with the Electrical & Computer Engineering Department,
University of Patras, Rio, Achaia 26500, Greece. Corresponding author’s
email: tzes@ece.upatras.gr

given regime and attempts to provide visual information of
an area using a single UAV-camera.
The problem statement, along with the definition of the
coverage-quality criterion and the sensed space partitioning
scheme are presented in Section II. In Section III, the
distributed control law is derived and its main properties are
explained. In Section IV, the partitioning scheme and the
control law are examined for two particular coverage quality
functions. Finally, in Section V, simulations are provided to
show the efficiency of the proposed technique.
II. P ROBLEM S TATEMENT
A. Main assumptions - Preliminaries
Let Ω ⊂ R2 be a compact convex region under surveillance. Assume a swarm of n UAVs, each positioned at
the spatial coordinates Xi = [xi , yi , zi ]T , i ∈ In , where In =
{1, . . . , n}. We also define the vector qi = [xi yi ]T , qi ∈ Ω to
note the projection of the center of each UAV on the ground.
The minimum and maximum altitudes each UAV can fly to
max ], i ∈ I .
are zmin
and zmax
respectively, thus zi ∈ [zmin
n
i
i , zi
i
The simplified UAV’s kinodynamic model is
q̇i

= ui,q , qi ∈ Ω, ui,q ∈ R2 ,

żi

= ui,z , zi ∈ [zmin
, zmax
], ui,z ∈ R.
i
i

(1)

where [ui,q , ui,z ] is the corresponding ‘thrust’ control input
for each robot (node). The minimum altitude zmin
is used to
i
ensure the UAVs will fly above ground obstacles, whereas
the maximum altitude zmax
guarantees that they will not fly
i
out of range of their base station. In the sequel, all UAVs
are assumed to have common minimum zmin and maximum
zmax altitudes.
As far as the sensing performance of the UAVs (nodes)
is concerned, all members are assumed to be equipped with
identical downwards pointing sensors with conic sensing
patterns. Thus the region of Ω sensed by each node is a
disk defined as
Cis (Xi , a) = {q ∈ Ω :k q − qi k≤ zi tan a} , i = 1, . . . , n, (2)
where a is half the angle of the sensing cone. As shown in
Figure 1, the higher the altitude of a UAV, the larger the area
of Ω surveyed by its sensor.
The coverage quality of each node is in the general case a
function fi (q) : R2 → [0, 1] which is dependent on the node’s
position Xi as well as its altitude constraints zmin , zmax and
the angle a of its sensor. The higher the value of fi (q), the
better the coverage quality of point q ∈ R2 , with fi = 1 when
zi = zmin and fi = 0 when zi = zmax . It is assumed that as the
altitude of a node increases, the visual quality of its sensed

area decreases. The properties of fi are examined in Section
IV along with some example functions.
For each point q ∈ Ω, an importance weight is assigned via
the space density function φ : Ω → R+ , encapsulating any a
priori information regarding the region of interest. Thus the
coverage-quality objective is
4

H =

Z

max fi (q) φ (q) dq.

Ω i∈In

(3)

In the sequel, we assume φ (q) = 1, ∀q ∈ Ω but the expressions can be easily altered to take into account any a priori
weight function.

Fig. 2: Examples of an empty cell (node 8) and one consisting of two disjoint regions (node 1).

III. S PATIALLY D ISTRIBUTED C OORDINATION
A LGORITHM

Fig. 1: UAV-visual area coverage concept
B. Sensed space partitioning
The assignment of responsibility regions to the nodes is
done in a manner similar to [7]. Only the subset of Ω sensed
by the nodes is partitioned. Each node is assigned a cell
4
Wi = q ∈ Ω : fi (q) ≥ f j (q), j 6= i
(4)

Based on the nodes kinodynamics (1), their sensing performance (2) and the coverage criterion (5), a gradient
based control law is designed. The control law utilizes the
partitioning (4) and result in monotonous increase of the
covered area.
Theorem 1: In a UAV visual network consisting of nodes
with sensing performance as in (2), governed by the kinodynamics in (1) and the space partitioning described in Section
II-B, the control law

Z
Z
∂ fi (q)
dq +
ni fi (q) dq +
ui,q = αi,q 
∂ qi
Wi
∂Wi ∩∂ O

Z
j6=i

H =

Z

∑

i∈In Wi

fi (q) φ (q) dq.

(5)

(6)

∂Wi ∩∂W j



with the equality holding true only at the boundary ∂Wi ,
so that the cells Wi comprise a complete tessellation of the
sensed region.
Definition 1: We define the neighbors Ni of node i as
4
Ni = j 6= i : Csj ∩Cis 6= 0/ .
The neighbors of node i are those nodes that sense at least
a part of the region that node i senses. It is clear that only
the nodes in Ni need to be considered when creating Wi .
Remark 1: The aforementioned
partitioning is a complete
S
tessellation of the sensed region i∈In Cis , although it is not a
complete tessellation of Ω. Let us denote the neutral region
S
not assigned by the partitioning scheme as O = Ω \ i∈In Wi .
Remark 2: The resulting cells Wi are compact but not
necessarily convex. It is also possible that a cell Wi consists
of multiple disjoint regions, such as the cell of node 1 shown
in yellow in Figure 2. It is also possible that the cell of a
node is empty, such as node 8 in Figure 2. Its sensing circle
∂C8s is shown in a dashed black line.
By utilizing this partitioning scheme, the network’s coverage performance can be written as


υii ni ( fi (q) − f j (q)) dq

∑

Z

ui,z

Z

= αi,z 

tan(a) fi (q) dq +
∂Wi ∩∂ O

Z

∑

j6=i

Wi

∂ fi (q)
dq +
∂ zi



νii · ni ( fi (q) − f j (q)) dq

(7)

∂Wi ∩∂W j

where αi,q , αi,z are positive constants and ni the outward
pointing normal vector of Wi , maximizes the performance
criterion (5) monotonically along the nodes’ trajectories,
leading in a locally optimal configuration.
Proof: Initially we evaluate the time derivative of the
optimization criterion H


dH
∂H
∂H
=∑
q̇i +
żi .
dt
∂ zi
i∈In ∂ qi
.
The usage of a gradient based control law in the form
ui,q = αi,q

∂H
∂H
, ui,z = αi,z
∂ qi
∂ zi

will result in a monotonous increase of H .
By using the Leibniz integral rule [14] we obtain



∂H
∂ qi

Z

=

∑

i∈In

υii ni fi (q) dq +

υii ni fi (q) dq +

=

Z

Wi

∂Wi

Z

∂ fi (q)
dq
∂ qi

∂ fi (q)
dq +
∂ qi

Z

Wi

∂Wi

Z

υ ij n j f j (q) dq +



∑

Z

Wj

∂W j

∂Wi ∩∂ O

∑

∂ f j (q)

dq
∂ qi

∑

j6=i

4

Since

∂ f j (q)
∂ qi

∂H
∂ qi

∂q
, q ∈ ∂W j , i, j ∈ In .
∂ qi

j6=i

(8)

= 0 we obtain
Z

=

υii ni fi (q) dq +

Wi

∂Wi

Z

∑

j6=i

Z

υ ij

∂ fi (q)
dq +
∂ qi

n j f j (q) dq

υ ij n j f j (q) dq.

∂W j ∩∂Wi

The evaluation of υii on ∂Wi ∩ ∂ O can be found in the
Appendix, whereas its evaluation on ∂W j ∩ ∂Wi depends on
the choice of fi (q) and is not examined in this section.
Because the boundary ∂Wi ∩ ∂W j is common among nodes
i and j, it holds true that υ ij = υii when evaluated over it
and that n j = −ni . Finally the sums and the integrals within
then can be combined, producing the final form of the planar
control law
Z
Z
∂ fi (q)
∂H
=
ni fi (q) dq +
dq +
∂ qi
∂ qi
∂Wi ∩∂ O

Wi

Z

whose three terms indicate how a movement of node i affects
the boundary of its cell, its whole cell and the boundaries
of the cells of other nodes. It is clear that only the cells W j
which have a common boundary with Wi will be affected
and only at that common boundary.
The boundary ∂Wi can be decomposed in disjoint sets as
[

(∂Wi ∩ ∂W j )}. (9)

j6=i

These sets represent the parts of ∂Wi that lie on the boundary
of Ω, the boundary of the node’s sensing region and the parts
that are common between the boundary of the cell of node
i and those of other nodes. This decomposition can be seen
in
Figure 3 with the sets ∂Wi ∩ ∂ Ω, ∂Wi ∩ ∂ O and ∂Wi ∩
S
j6=i ∂W j appearing in solid red, green and blue respectively.

ni fi (q) dq +

∂Wi ∩∂W j

∂W j

∂Wi = {∂Wi ∩ ∂ Ω} ∪ {∂Wi ∩ ∂ O} ∪ {

υii

Z

where υ ij stands for the Jacobian matrix with respect to qi
of the points q ∈ ∂W j ,
υ ij (q) =

Wi

Z




j6=i

common boundary ∂W j ∩∂Wi of node i with any other node j
is affected by the movement of node i, ∂∂H
qi can be simplified
as
Z
Z
∂H
∂ fi (q)
=
υii ni fi (q) dq +
dq +
∂ qi
∂ qi



υii ni ( fi (q) − f j (q)) dq.

∑

j6=i

∂W j ∩∂Wi

Similarly, by using the same ∂Wi decomposition and
4
defining ν ij (q) = ∂∂zqi , q ∈ ∂W j , i, j ∈ In , the altitude control
law is
Z
Z
∂H
∂ fi (q)
tan(a) fi (q) dq +
=
dq +
∂ zi
∂ zi
∂Wi ∩∂ O

Z

∑

j6=i

Wi

νii · ni ( fi (q) − f j (q)) dq

∂W j ∩∂Wi

where the evaluation of νii (q)·ni on ∂Wi ∩∂ O and ∂W j ∩∂Wi
can be found in the Appendix.
Remark 3: The cell Wi of node i is affected only by its
neighbors Ni thus resulting in a distributed control law. The
finding of the neighbors Ni depends on their coordinates
X j , j ∈ Ni and does not correspond to the classical 2DDelaunay neighbors. The computation of the Ni set demands
node i to be able to communicate with all nodes within a
sphere centered around Xi and radius ric


2

2
ric = max 2zi tan a, zi + zmin tan2 a + z− zmin ,
o
(zi + zmax )2 tan2 a + (z− zmax )2 .

Fig. 3: ∂Wi -decomposition into disjoint sets
At q ∈ ∂ Ω it holds that υii = 02×2 since we assume
the region of interest is static. Additionally, since only the

Figure 4 highlights the case where nodes 2, 3 and 4 are
at zmin , z1 and zmin respectively. These are the worst case
scenario neighbors of node 1 , the farthest of which dictates
the communication range r1c .
Remark 4: When zi = zmax , both the planar and altitude
control laws are zero because fi (qi ) = 0. This results in the
UAV being unable to move any further in the future and
additionally its contribution to the coverage-quality objective

Fig. 4: Ni neighbor set
being zero. However this degenerate case is of little concern,
as shown in Sections III-A and III-C.
A. Stable altitude
The altitude control law ui,z moves each UAV towards
an altitude in which ui,z = 0 which corresponds to an
equilibrium point for that particular node. We call this the
stable altitude zstb
i and it is the solution with respect to zi of
the equation:

C. Degenerate cases

ui,z = 0 ⇒
R
∂Wi ∩∂ O

∑

tan(a) fi (q) dq +

R

j6=i ∂Wi ∩∂W j

R ∂ fi (q)
Wi

∂ zi

dq +

νii · ni ( fi (q) − f j (q)) dq = 0.

Both integrals over ∂Wi are non-negative since their integrands are non-negative, whereas the integral over Wi is negative since coverage quality decreases as altitude increases.
The stable altitude is not common among nodes as it
depends on one’s neighbors Ni and is not constant over time
since the neighbors change over time.
When the integrals over ∂Wi are both zero, the resulting
control law has a negative value. This will lead to a reduction
of the node’s altitude and in time the node will reach zstb =
zmin . Once the node reaches zmin its altitude control law will
be 0 until the integral over ∂Wi stops being zero. The planar
control law however is unaffected, so the node’s performance
in the future is not affected. This situation may arise in a node
with several neighboring nodes at lower altitude that result
in ∂Cis ∩ ∂Wi = 0.
/
When the integral over Wi is zero, the resulting control
law has a positive value. This will lead to an increase of the
node’s altitude and in time the node will reach zstb = zmax and
as shown in Remark 4 the node will be immobilized from
this time onwards. However this situation will not arise in
practice as explained in Section III-C.
When the integral over Wi and at least one of the integrals
over ∂Wi are non-zero, then zstb ∈ zmin , zmax .
B. Optimal altitude
It is useful to define an optimal altitude zopt as the altitude
a node would reach if: 1) it had no neighbors (Ni = ∅), and 2)
no part of Wi on ∂ Ω, (∂ Ω ∩ ∂Cis = ∅). This optimal altitude
is the solution with respect to zi of the equation
Z

Z

tan(a) fi (q) dq +
∂Cis

Wi

Additionally, let us denote the sensing region of a node i at
s
zopt as Ci,opt
and Hopt the value of the criterion when all
nodes are located at zopt .
If Ω = R2 and because the planar control law ui,q results in
the repulsion of the nodes, the network will reach a state in
which no node will have neighbors and all nodes will be at
zopt . In that state, the coverage-quality criterion (5) will have
attained it’s maximum possible value Hopt for that particular
network configuration and coverage quality function fi . This
network configuration will be globally optimal.
When Ω is a convex compact subset of R2 , it is possible
for the network to reach a state where all the nodes are at
s
zopt only if n Ci,opt
disks can be packed inside Ω. This state
will be globally optimal. If that is not the case, the nodes
will converge at some altitude other than zopt and in general
different among nodes. It should be noted that although the
nodes do not reach zopt , the network configuration is locally
optimal.

∂ fi (q)
dq = 0.
∂ zi

It is possible due to the nodes’ initial positions that the
sensing disk of some node i is completely contained within
the sensing disk of another node j, i.e. Cis ∩Csj = Cis . In such
a case, it is not guaranteed that the control law will result
in separation of the nodes’ sensing regions and thus it is
possible that the nodes do not reach zopt . Instead, node j
may converge to a higher altitude and node i to a lower
altitude than zopt , while their projections on the ground qi
and q j remain stationary. Because the region covered by node
i is also covered by node j, the network’s performance is
impacted negatively. Since this degenerate case may only
arise at the network’s initial state, care must be taken to
avoid it during the robots’ deployment. Such a degenerate
case is shown in Figure 5 where the sensing disk of node 4
is completely contained within that of node 3.
Another case of interest is when some node i is not
assigned a region of responsibility, i.e. Wi = 0.
/ This is due to
the existence of other nodes at lower altitude that cover all of
Cis with better quality than node i. This is the case with node
8 in Figure 2. This situation is resolved since the nodes at
lower altitude will move away from node i and once node i
has been assigned a region of responsibility it will also move.
It should be noted that the coverage objective H remains
continuous even when node i changes from being assigned
no region of responsibility to being assigned some region of
responsibility.
In order for a node to reach zmax , as explained in Section
III-A, the integral over Wi of its altitude control law must
be zero, that is its cell must consist of just a closed curve
without its interior. In order to have Wi = ∂Wi , a second node
j must be directly below node i at an infinitesimal distance.
However just as node i starts moving upwards the integral
over Wi will stop being zero thus changing the stable altitude
to some value zstb < zmax . In other words, in order for a node
to reach zmax , the configuration described must happen at an
altitude infinitesimally smaller than zmax . So in practice, if

1

1

0.8

0.8

0.6

0.6
fip

fiu

all nodes are deployed initially at an altitude smaller than
zmax , no node will reach zmax in the future.

0.4

0.4

0.2

0.2

0
−0.15

−0.1

−0.05

0
x

0.05

0.1

0.15

0
−0.15

Fig. 6: Coverage quality functions:
[Right] for different values of b.
Fig. 5: Sensed space partitioning using the coverage quality
functions fiu [Left] and fip [Right].
IV. C OVERAGE QUALITY FUNCTIONS
The choice of coverage quality function affects both the
sensed space partitioning (4) and the control law (7). The
function fi , i ∈ In is required to have the following properties
1) fi (q) = 0, ∀q ∈
/ Cis ,
2) fi (q) ≥ 0, ∀q ∈ ∂Cis ,
3) fi (q) is first order differentiable with respect to qi and
zi , or ∂ ∂fiq(q)
and ∂ ∂fiz(q)
exist within Cis ,
i
i
4) fi (q) is symmetric around the z-axis,
5) fi (q) is a decreasing function of zi ,
6) fi (q) is a non-increasing function of k q − qi k,
7) fi (qi ) = 1 when zi = zmin and fi (qi ) = 0 when zi = zmax .
The need for the first property is clear since the coverage
quality with respect to node i should be zero outside Cis .
The second guarantees that the integrals of the control law
over some part of ∂Cis are not zero and the third is required
so that the integrals over Wi can be defined. The fourth
property is due to the fact that the sensing patterns are
rotation invariant. Two indicative coverage quality functions
are examined in the sequel along with the properties of the
resulting partitioning schemes and control laws.
A. Uniform coverage quality
The simplest coverage quality function that can be chosen
is the uniform one, i.e. the coverage quality is the same for all
points in Cis . This function can effectively model downward
facing cameras [15, 16] that provide uniform quality in the
whole image. This function will be referred to as fiu from
now on and is defined as
 
2
2 2


zi − zmin − zmax − zmin

, q ∈ Cis
fiu (q) =
max − zmin )4
(z



0,
q∈
/ Cis
It should be noted that the above definition of a uniform
coverage quality function is not unique, just the simplest of
the possible ones.
A projection of this function on the y−z planecan be seen
T
in the left portion of Figure 6 for a node at Xi = 0, 0, zmin .
It can be shown that fiu (q) = 0 when k q − qi k> zi tan a, i.e.
when q is outside the sensing disk.

−0.1

−0.05

0
x

0.05

0.1

fiu (q) [Left],

0.15

fip (q)

This choice of quality function simplifies the space partitioning since ∂W j ∩ ∂Wi is either an arc of ∂Ci if zi < z j or of
∂C j if zi > z j . In the case where zi = z j , ∂W j ∩ ∂Wi is chosen
arbitrarily as the line segment defined by the two intersection
points of ∂Ci and ∂C j . The resulting cells consist of circular
arcs and line segments.
If the sensing disk of a node i is contained within the
sensing disk of another node j, i.e. Cis ∩Csj = Cis , then Wi = Cis
and W j = Csj \ Cis . An example partitioning with all of the
above cases shown can be seen in Figure 5 [Left], where
the boundaries of the sensing disks ∂Cis are in red and the
boundaries of the cells ∂Wi in black. Nodes 1 and 2 are at
the same altitude so the arbitrary partitioning scheme is used.
The sensing disk of node 3 contains the sensing disk of node
4 and nodes 5, 6 and 7 illustrate the general case.
The control law is also significantly simplified. Since
∂ fi (q)
∂ qi = 0, the corresponding integral of the control law (7)
is 0. Additionally, υii and νii ni are evaluated as
(
I2 , zi ≤ z j
υii =
(10)
02 , zi > z j
(
tan(a), zi ≤ z j
i
νi · ni =
(11)
0, zi > z j
Because both υii and νii · ni are zero when zi > z j ⇒ fiu < f ju ,
the integrals over ∂Wi ∩ ∂W j are zero for both the planar and
altitude control laws when fiu < f ju and as a result need only
be evaluated when fiu > f ju .
The control law essentially maximizes the volume contained by all the cylinders defined by fiu , i ∈ In , under the
constraints imposed by the network and area of interest.
While the control law in the general case guarantees that
zi < zmax , ∀i ∈ In , this particular one also guarantees that
zi > zmin , ∀i ∈ In . If zi = zmin , then it follows that ∂ ∂fiz(q)
= 0,
i
resulting in the integral over Wi being zero. Since fiu is
positive and only arcs of ∂Wi where fiu > f ju are integrated
over, the remaining part of the control law is positive,
resulting in the node moving to a higher altitude.
B. Decreasing coverage quality
A more realistic assumption for some types of visual
sensors would be for the coverage quality to decrease as
distance from the node increases, to take into account lens
distortion for example. The coverage quality of a point
q ∈ Cis is maximum directly below the node and decreases
as k q − qi k increases. One such function is an inverted

paraboloid whose maximum value depends on zi and could
be defined as
#
 "
h
i

2
2
 1− 1−b
(x − xi ) + (y − yi )
fiu ,
p
fi (q) =
[zi tan(a)]2


0,

q ∈ Cis
q∈
/ Cis

where b ∈ (0, 1) is the coverage quality on ∂Ci as a percentage of the coverage quality on qi and fiu is the uniform
coverage quality function defined previously and is used to
set the maximum value of the paraboloid. A projection of this
function on the y − z plane can be seen in the right portion
of Figure 6 for a node at Xi = [0, 0, zmax ]T and various bvalues; b ∈ {1, 0.5, 0.2, 0} corresponds to blue, red, green
and black colored curves, respectively. It can be shown that
fip (q) = 0 when k q − qi k> zi tan a, i.e. when q is outside
the sensing disk. Additionally, when k q − qi k= zi tan a,
fip = b fiu .
For the space partitioning it is necessary to solve fip (q) ≥
p
f j (q) in order to find part of ∂W j ∩Wi . The resulting solution
on the x−y plane is a disk Ci,i j when zi 6= z j and the halfplane
defined by the perpendicular bisector of qi and q j when zi =
z j . Finally, the cell of node i with
 respectto node j is Wi =
Cis ∩Ci,i j if zi < z j and Wi = Cis \ Csj ∩Ci,i j if zi > z j . Figure
7 shows the intersection of two paraboloids fip and f jp with
zi < z j and the boundaries ofthe resulting
cells above them.

The red line shows ∂Ci,i j ∩ Cis ∩Csj , i.e. the boundary of
the intersection disk constrained within the sensing disks of
the two nodes, since only for q ∈ Cis ∩Csj can fip (q) = f jp (q).
The green arcs represent ∂Wi ∩ ∂Cis ∩W j while the blue ones
represent ∂Wi ∩ ∂ O. Thus the boundary of the cell of any
node i can be decomposed into disjoint sets as
(
∂Wi =

(∂Wi ∩ ∂ O)

[ 

)


(∂Wi ∩ ∂Ci,i j ) ∩ (∂Wi \ ∂Ci,i j ∩W j )

j∈Ni

.

sensing disks ∂Cis are in red and the cells Wi in black. The
sensing disk of node 3 contains the sensing disk of node 4
and nodes 5, 6 and 7 illustrate the general case.
For the evaluation of υii and νii · ni the partitioning of
∂Wi explained previously will be used. Since ∀q ∈ ∂Ci,i j ⇒
fip (q) = f jp (q), the integral over ∂Ci,i j is zero. For the remaining part of ∂Wi ∩W j which is ∂Wi \ ∂Ci,i j ∩W j , the evaluation
of υii and νii · ni is the same as in the case of the uniform
coverage function fiu . For the same reasons as in the uniform
coverage quality, the integrals over ∂Wi ∩ ∂W j are zero for
both the planar and altitude control laws when fip < f jp and
as a result need only be evaluated when fip > f jp .
The control law essentially leads to the maximization of
the volume contained by all the paraboloid-like functions
fip , i ∈ In , under the constraints imposed by the network and
area of interest.
This control law also guarantees that that zi > zmin , ∀i ∈ In
in addition to zi < zmax , ∀i ∈ In . Because fip is positive and
only arcs of ∂Wi where fip > f jp are integrated over, the
integral over ∂Wi is always positive when zi = zmin . It can
∂ f (q)
also be shown that ∂pzi > 0, ∀q ∈ Wi when zi = zmin and thus
the integral over Wi of ui,z will also be positive. As a result
the altitude control law is always positive when zi = zmin
resulting in the altitude increase of node i.
V. S IMULATION S TUDIES
Simulation results of the proposed control law using the
uniform coverage quality function fiu are presented in this
section. The region of interest Ω is the same as the one used
in [3] for consistency. All nodes are identical with a half
sensing cone angle a = 20◦ and zi ∈ [0.3, 2.3], ∀i ∈ In . The
boundaries of the nodes’ cells are shown in black and the
boundaries of their sensing disks in red.
Remark 5: When using fiu (q) it is possible to observe
jittering on the cells of some nodes i and j. This can happen
when zi = z j and the arbitrary boundary ∂Wi ∩ ∂W j is used.
Once the altitude of one of the nodes changes slightly,
the boundary between the cells will change instantaneously
from a line segment to a circular arc. The coverage-quality
objective H however will present no discontinuity when this
happens.
A. Case Study I

Fig. 7: ∂Wi -decomposition when fip is used.
If the sensing disk of a node i is contained within the
sensing disk of another node j, i.e. Cis ∩Csj = Cis , then Wi ⊂ Cis
and W j = Csj \Wi . It is important to note that in the general
case, ∂W j ∩ ∂Wi consists of circular arcs from both ∂Ci,i j and
∂Cis or ∂Csj (depending on the relationship of zi and z j ).
An example partitioning with all of the above cases shown
can be seen in Figure 5 [Right], where the boundaries of the

In this simulation three nodes start grouped as seen in
Figure (8) [Left]. Since the region of interest is large enough
s
for three optimal disks Ci,opt
to fit inside, all the nodes
converge at the optimal altitude zopt . As it can be seen
in Figure
11,
 the area covered by the network is equal to
S
s and the coverage-quality criterion has reached
A
C
i∈In 
i


s
Hopt = A
i∈In Ci,opt . However since all nodes converged
at zopt , the addition of more nodes will result in significantly
better performance coverage and quality wise, as is clear
from Figure 8 [Right] and Figure 11 [Left]. Figure 9 shows a
graphical representation of the coverage quality at the initial
and final stages of the simulation. It is essentially a plot of
all fiu (q) inside the region of interest. The volume of the

S

Fig. 8: Initial [Left] and final [Right] network configuration
and space partitioning.

cylinders in Figure 9 [Right] is the maximum possible. The
trajectories of the UAVs in R3 can be seen in Figure 10 in
blue and their projections on the region of interest in black.

Fig. 9: Initial [Left] and final [Right] coverage quality.

why H never reaches Hopt , as seen in Figure 15. It can
be clearly seen though from Figure 12 [Right] and Figure
15 [Left] that the network covers a significant portion of Ω
with better quality than Case Study I. The volume of the
cylinders in Figure 13 [Right] has reached a local optimum.
The trajectories of the UAVs in R3 can be seen in Figure
14 in blue and their projections on the region of interest in
black. It can be seen from the trajectories that the altitude of
some nodes was not constantly increasing. This is expected
behavior since nodes at lower altitude will increase the stable
altitude of nodes at higher altitude they share sensed regions
with. Once they no longer share sensed regions, or share a
smaller portion, the stable altitude of the upper node will
decrease, leading to a decrease in their altitude.

Fig. 12: Initial [Left] and final [Right] network configuration
and space partitioning.

z

1

0.5

0
2

2.5
1.5

2
1.5

1
1

0.5
y

0.5
0

x

0

80

60

60

40

Fig. 13: Initial [Left] and final [Right] coverage quality.

1
z

100

80

(%)

100

H
H opt

Acov (%)

Fig. 10: Node trajectories (blue) and their projections on the
sensed region (black).

0.5

40

0
20

20

2

2.5
1.5

0
0

5

10

15

0
0

5

T ime (s)

10

2

15

1.5

1

T ime (s)

1

0.5

A(
A (Ω)

s
i∈In Ci

S

Fig. 11:

)

[Left] and

H
Hopt

y

[Right].

B. Case Study II
A network of nine nodes, identical to those in Case Study
I, is examined in this simulation with an initial configuration
as seen in Figure 12 [Left]. The region Ω is not large enough
s
to contain these nine Ci,opt
disks and so the nodes converge
opt
at different altitudes
below
z
 . This is why the covered area
S
s
never reaches A
i∈In Ci , which is larger than A (Ω) and

0.5
0

0

x

Fig. 14: Node trajectories (blue) and their projections on the
sensed region (black).
VI. C ONCLUSIONS
Area coverage by a network of UAVs has been studied in
this article by use of a combined coverage-quality metric. A
partitioning scheme based on coverage quality is employed
to assign each UAV an area of responsibility. The proposed

140

100

120
80

(%)

80

H
H opt

Acov (%)

100

60

60

40

40
20
20
0
0

5

10
T ime (s)

15

0
0

20

A ( i∈In Cis )
A (Ω)

5

S

Fig. 15:

[Left] and

10
T ime (s)

H
Hopt

15

20

[Right].
R EFERENCES

control law leads the network to a locally optimal configuration which provides a compromise between covered area
and coverage quality. It also guarantees that the altitude of all
UAVs will remain within a predefined range, thus avoiding
potential obstacles while also keeping the UAVs below
their maximum operational altitude. Simulation studies are
presented to indicate the efficiency of the proposed control
algorithm.
APPENDIX
The parametric equation of the boundary of the sensing
disk Cis (Xi , a) defined in (2) is
  

x
xi + zi tan(a) cos(k)
γ(k) :
=
, k ∈ [0, 2π)
y
yi + zi tan(a) sin(k)
We will now evaluate ni , υii (q) and νii (q) on ∂Wi ∩ ∂ O
which is always an arc of the circle γ(k).
The normal vector ni is given by


cos(k)
ni =
, k ∈ [0, 2π)
sin(k)
It can be easily shown that
"

∂x
∂ yi
∂y
∂ yi

∂x
∂ xi
∂y
∂ xi

υii (q) =

#
= I2

and similarly that
"
νii (q) =

∂x
∂ zi
∂y
∂ zi

#


=

When fi (q) < f j (q), due to the partition scheme, the
common sensed region between nodes i and j will be
assigned to node j. As a result, ∂Wi ∩ ∂W j will be an arc
of ∂Csj which will not change when node i moves. Thus ni ,
υii (q) and νii (q) are both zero in this case.
It is thus concluded that for the integrals over ∂Wi ∩∂W j of
node i, only arcs where fi (q) > f j (q) need to be considered
when integrating.

tan(a) cos(k)
tan(a) sin(k)


.

It is now clear that
νii (q) · ni = tan(a).
The evaluation of ni , υii (q) and νii (q) on ∂W j ∩ ∂Wi
depends on the choice of f (q) and the partitioning scheme
described in Section II-B.
When fi (q) = f j (q), the evaluation of ni , υii (q) and νii (q)
is irrelevant since the corresponding integral will be 0 due
to the fi (q) − f j (q) term.
When fi (q) > f j (q), due to the partition scheme, the
common sensed region between nodes i and j will be
assigned to node i. As a result, ∂Wi ∩ ∂W j will be an arc of
∂Cis and will change when node i moves. Thus the evaluation
of ni , υii (q) and νii (q) will be the same as their evaluation
over ∂Wi ∩ ∂ O described previously.

[1] J. Cortés, S. Martinez, and F. Bullo, “Spatially-distributed coverage
optimization and control with limited-range interactions,” ESAIM:
Control, Optimisation and Calculus of Variations, vol. 11, no. 4, pp.
691–719, 2005.
[2] L. Pimenta, V. Kumar, R. Mesquita, and G. Pereira, “Sensing and
coverage for a network of heterogeneous robots,” in Proc. of the
47th Conference on Decision and Control, Cancun, Mexico, 2008,
pp. 3947–3952.
[3] Y. Stergiopoulos and A. Tzes, “Convex Voronoi-inspired space partitioning for heterogeneous networks: A coverage-oriented approach,”
IET Control Theory and Applications, vol. 4, no. 12, pp. 2802–2812,
2010.
[4] O. Arslan and D. E. Koditschek, “Voronoi-based coverage control of
heterogeneous disk-shaped robots,” in Proc. of the IEEE International
Conference on Robotics and Automation, (ICRA 2016), 2016, pp.
4259–4266, 2016.
[5] Y. Stergiopoulos and A. Tzes, “Spatially distributed area coverage optimisation in mobile robotic networks with arbitrary convex anisotropic
patterns,” Automatica, vol. 49, no. 1, pp. 232–237, 2013.
[6] Y. Kantaros, M. Thanou, and A. Tzes, “Distributed coverage control
for concave areas by a heterogeneous robot-swarm with visibility
sensing constraints,” Automatica, vol. 53, pp. 195–207, 2015.
[7] Y. Stergiopoulos and A. Tzes, “Cooperative positioning/orientation
control of mobile heterogeneous anisotropic sensor networks for area
coverage,” in Proc. IEEE International Conference on Robotics &
Automation, Hong Kong, China, 2014, pp. 1106–1111.
[8] Y. Stergiopoulos, M. Thanou, and A. Tzes, “Distributed collaborative
coverage-control schemes for non-convex domains,” IEEE Transactions on Automatic Control, vol. 60, no. 9, pp. 2422–2427, 2015.
[9] A. Renzaglia, L. Doitsidis, E. Martinelli, and E. Kosmatopoulos,
“Muti-robot three-dimensional coverage of unknwon areas,” The International Journal of Robotics Research, vol. 31, no. 6, pp. 738–752,
2012.
[10] A. Breitenmoser, J. Metzger, R. Siegwart, and D. Rus, “Distributed
coverage control on surfaces in 3D space,” in Proc. of the 2010 IEEE
International Conference on Intelligent Robots and Systems, Taipei,
Taiwan, 2010, pp. 5569–5576.
[11] M. Thanou and A. Tzes, “Distributed visibility-based coverage using
a swarm of uavs in known 3D-terrains,” in Proc. of the International
Symposium on Communications, Control and Signal Processing (ISCCSP 2014), Athens, Greece, 2014, pp. 458–461.
[12] M. Schwager, B. J. Julian, and D. Rus, “Optimal coverage for multiple
hovering robots with downward facing cameras,” in Proc. of the IEEE
International Conference on Robotics and Automation, (ICRA 2009),
2009, pp. 3515–3522.
[13] M. Schwager, B. J. Julian, M. Angermann, and D. Rus, “Eyes in
the sky: Decentralized control for the deployment of robotic camera
networks,” Proceedings of the IEEE, vol. 99, no. 9, pp. 1541–1561,
2011.
[14] H. Flanders, “Differentiation under the integral sign,” American Mathematical Monthly, vol. 80, no. 6, pp. 615–627, 1973.
[15] C. Di Franco and G. Buttazzo, “Coverage path planning for uavs
photogrammetry with energy and resolution constraints,” Journal of
Intelligent & Robotic Systems, pp. 1–18, 2016.
[16] G. Avellar, G. Pereira, L. Pimenta and P. Iscold, “Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time,”
Sensors, vol. 15, no. 11, pp. 27783–27803, 2015.

