# Distributed Coverage Control of Multi-Agent Systems in Uncertain
Environments using Heat Transfer Equations

Yinan Zheng, Chao Zhai Yinan Zheng and Chao Zhai are with the School of
Automation, China University of Geosciences, Wuhan 430074 P. R. China, and
with Hubei Key Laboratory of Advanced Control and Intelligent Automation for
Complex Systems, and Engineering Research Center of Intelligent Technology for
Geo-Exploration, Ministry of Education, Wuhan 430074, P. R. China.
Corresponding author: Chao Zhai (email: zhaichao@amss.ac.cn).

###### Abstract

This paper addresses the coverage control problem of multi-agent system in the
uncertain environment. With the aid of Voronoi partition, a distributed
coverage control formulation of multi-agent system is proposed to complete the
workload in the uncertain environments. Driven by the gradient of thermal
field, each agent is able to move around for clearing the workload on its own
subregion. Theoretical analysis is conducted to ensure the completion of
workload in finite time. Finally, numerical simulations are carried out to
demonstrate the effectiveness and advantages of the proposed coverage control
approach as compared to other existing approaches.

Keywords: Distributed coverage control, multi-agent system, uncertain
environments, heat transfer equation, region partition.

##  1 Introduction

With the rapid development of communication and electronic technology, multi-
agent systems have been widely used in many application fields, including
exploration, surveillance, region coverage, search and rescue [1]. Compared
with a single agent, a team of agents are more efficient to carry out a
complicated task, especially in the uncertain environment. Specifically, the
workload of each individual in the system is relatively reduced and the
increase in the number makes the whole system obtain more comprehensive
information. Meanwhile, distributed system design enables each agent to
cooperate to complete tasks while ensuring individual independence. Naturally,
the research on system cooperation has become the main content, and has a lot
of research results in [2]-[7].

Among various coordination tasks, multi-agent region coverage is a hot
research topic. Taking multi-sensor network as an example, the given area is
covered to accomplish the global monitoring task, in which the deployment mode
of the sensor has to be explored in order to achieve the maximum coverage rate
and the shortest coverage time. To deal with this problem, distributed
strategy (i.e., divide-and-conquer) may paly a crucial role in handling
environmental uncertainties. For instance, [8] and [9] capitalize on Voronoi
partition and introduce an optimization method to deploy the sensor networks.
In [10], environment information is learned online with prior information. In
[1]-[12], the online workload partition and distributed coverage control
algorithm are proposed, and the coverage time is estimated for algorithm
comparison.

In [13], a centralized coverage control algorithm is proposed based on
temperature transfer equation. While ensuring the coverage efficiency, it can
also deal with the coverage problem of non-convex regions. However, agents are
prone to collision during movement using this coverage method, and there may
be the problem that multiple agents cover the same area, which results in the
degradation of efficiency of transitional coverage. For this reason, this
paper aims to propose a distributed coverage algorithm by taking into account
workload partition and dynamic coverage. In brief, key contributions of this
work are summarized as follows:

  1. 1.

Propose a distributed coverage algorithm by integrating region partition (to
handle the uncertainties) with coverage control (to complete the workload).

  2. 2.

Provide theoretical guarentee on the finite-time completion of coverage task
with the aid of Delaunay triangulation.

  3. 3.

Make a quantitative comparison with other existing coverage control algorithms
through numerical simulations.

The remainder of the paper is organized as follows. Section 2 presents the
formulation of coverage problem in uncertain environment. Then the distributed
coverage algorithm using heat transfer equation is proposed in Section 3,
followed by theoretical analysis in Section 4. Numerical simulations are
carried out in Section 5. Finally, we draw conclusions and discuss future work
in Section 6.

##  2 Problem Formulation

From the perspective of coverage time, the coverage task of multi-agent
systems can be transformed into a single objective optimization problem. In
this section, we develop distributed region partition method of multi-agent
system, introduce the related concepts of coverage problem, and come up with
the optimization goal.

###  2.1 Region partition

Consider the 2-dimensional workspace $D~{}\subset~{}\mathbb{R}^{2}$ with
Lipschitz continuous boundary for $N$ mobile agents to complete the coverage
task, and the location of the agent $i$ can be represented by spatial
coordinates $\bf{s}_{i}=(x_{i},y_{i})$. In addition, any point in the
workspace is expressed as $\mathbf{x}=(x,y)$. The communication topology of
multi-agent systems can be expressed as an undirected graph $G=(V,E)$, where
$V$ represents a collection of $N$ nodes, and each node corresponds to an
individual agent. Here $E$ represents the set of connections between nodes,
that is, the interactive relationship between agents. For
$i,j\in\\{1,2,3,...,N\\}$, let $w_{ij}\in\\{0,1\\}$ represent the
communication or connection status between Agent $i$ and Agent $j$. When
$w_{ij}=1$, it means that Agent $i$ is connected with Agent $j$. In this
problem, we assume that there is communication relationship between agents
with overlapping edges in the subregion after Voronoi partition in [14]. For
the agent $i$, its Voronoi cell $D_{i}$ is defined as

$D_{i}=\\{\mathbf{x}\in D|d(\mathbf{x},\bf{s}_{i})\leq
d(\mathbf{x},\mathbf{s}_{j}),\forall~{}j\in\\{1,2,3,...,N\\},i\neq j\\},$ (1)

where $d(\mathbf{x},\bf{s}_{i})=||\mathbf{x}-\bf{s}_{i}||$ is the Euclidean
distance between the location of $\mathbf{x}$ and $\bf{s}_{i}$. The partition
method is shown in Figure 1.

Figure 1: Voronoi partition method on the region $D$. (a): $\bf{s}_{i}$
represents the location of agent $i$, and the communication topology of multi-
agent systems can be expressed as the graph. (b): The subregion configuration
after Voronoi partition.

With the assistance of Voronoi partition, the whole area can be divided into
$N$ subregions with overlapping boundaries, and a single agent (say $i$) only
works in its own Voronoi cell $D_{i}$. The relatively independent workspace
enables the distributed implementation of coverage algorithm, which has the
following benefits. First of all, the distance from any point in the Voronoi
cell to its agent is always less than that to other agents, which is
determined by the nature of Voronoi diagram, so that the agent only needs to
be responsible for its nearest area to speed up coverage efficiency. Secondly,
because of region partition, the agent only needs to know the work tasks in
partial areas, which is consistent with most application scenarios, and
relatively separated working region can avoid the collision among agents. This
distributed design makes the system more robust. Finally, note that each agent
moves along the gradient of potential energy field in [13]. For multiple
agents close to each other, when the gradient is extremely small, it may
eventually lead to the problem that multiple agents pile up and stagnate,
which may lead to redundant coverage. Voronoi partition can effectively
alleviate this problem. However, the work interval divided by distance can not
guarantee the same workload, which will lead to unequal coverage time of
agents and the wasting of coverage resources. The solutions are thus
introduced in later sections.

###  2.2 Coverage metrics

After dividing the coverage region into multiple subregions, we need to
determine the performance index, which is used to describe the coverage level
of agents on the responsible region. Due to hardware limitations of agents,
the coverage scope of each agent is limited at certain time. [15] proposed a
monotonically decreasing differentiable function
$p_{i}(\mathbf{x},\bf{s}_{i})$ to quantify the coverage capacity of agent $i$
at the point $\mathbf{x}$ per unit time.

$p_{i}(\mathbf{x},\bf{s}_{i})=\begin{cases}P_{i}e^{-\lambda_{i}d(\mathbf{x},\bf{s}_{i})}&d(\mathbf{x},\bf{s}_{i})\leq
r\\\ 0&d(\mathbf{x},\bf{s}_{i})>r\end{cases},$ (2)

where $P_{i}>0$ represents the maximum coverage capacity of the agent $i$, and
$\lambda_{i}$ is the attenuation coefficient and $r$ is the effective coverage
radius. In the actual coverage process, the agent does not remain stationary.
Assume that the coverage capacity of each agent remains unchanged. For agent
$i$, its total coverage to point $\mathbf{x}\in D$ during the period $[0,t]$
is given by

$c_{i}(\textbf{x},t)=\int_{0}^{t}p_{i}(\textbf{x},s_{i}(\tau))d\tau.$ (3)

For the region $D$, the workload is represented by $m(\textbf{x},t)$, which
can be obtained as follows

$m(\textbf{x},t)=\max\left(0,m_{0}(\textbf{x})-\sum_{i=1}^{N}c_{i}(\textbf{x},t)\right),$
(4)

where $m_{0}(\textbf{x})$ is the initial value of workload on coverage region.
Thus, it can be expressed that the total workload of the area is

$M(t)=\int_{D}m(\textbf{x},t)d\textbf{x},\quad
M(0)=\int_{D}m_{0}(\textbf{x})d\textbf{x}.$ (5)

Through the above analysis, we can transform the task of area coverage into
making the total workload equal to 0, i.e. $\lim_{t\to\infty}M(t)=0$. However,
in addition to completing the coverage task, it is also required to achieve
region coverage in the shortest time. Let $T^{*}$ represent the optimal time
of covering the whole region and $T$ is the actual coverage time. Note that
the coverage velocity of each agent is equal, and it is denoted by $v$. In
light of (2), $v$ can be computed by

$v=\int_{d(\textbf{x},\bf{s}_{i})\leq r}p_{i}(\textbf{x},s_{i})d\textbf{x}.$
(6)

$T^{*}$ can be computed by

$T^{*}=\frac{1}{Nv}M(0),$ (7)

which is unavailable due to environmental uncertainties, and the error is
given by $\Delta T=T-T^{*}$. The objective of this study is to design a
distributed online coverage scheme to minimize the actual coverage time.

##  3 Coverage Control Algorithm

In this section, we present a coverage control method for multi-agent systems
to clear the workload in a given region by using heat transfer equation.

###  3.1 Heat field-induced control

Instead of generating global temperature field [13], the coverage of each
Voronoi cell $D_{i}$ is taken into account by solving heat transfer equation
locally. While adopting the distributed method, it also retains the global
advantage of temperature field on the coverage area. The coverage for a
certain time can be regarded as a static temperature field with adiabatic
boundary. For region $D_{i}$, its temperature field $T_{i}$ at time $t$
satisfies

$\alpha\Delta T_{i}(\textbf{x},t)+h_{i}(\textbf{x},t)=\beta
T_{i}(\textbf{x},t),$ (8)

with the Neumann boundary condition

$\frac{\partial T_{i}(\textbf{x},t)}{\partial\mathbf{n}}=0,$ (9)

where $\alpha>0$, $\beta>0$, $\Delta$ is a Laplace operator, $\mathbf{n}$ is
the outward normal vector. Note that the above equation is independent of
time, and the boundary of subregions results from Voronoi partition. In the
heat equation (8), $\alpha\Delta T_{i}$ represents the net heat flow. Thermal
diffusivity $\alpha$ represents the ability of the temperature of all parts of
the object, and it tends to be the same when the object is heated or cooled.
The larger the value, the smaller the temperature difference in all parts of
the object. To deal with the coverage problem, we convert the workload level
into internal heat source $h_{i}(\textbf{x},t)$

$h_{i}(\textbf{x},t)=\frac{m(\textbf{x},t)}{\bar{m}_{i}},\quad x\in D_{i},$
(10)

where $\bar{m}_{i}$ represents the maximum workload in the initial case for
region $D_{i}$.

$\bar{m}_{i}=\max(m_{0}(\textbf{x})).$ (11)

When the agent does not cover a point x in the area, the energy of heat source
releases heat flow to the low-temperature area. When the agent completes the
coverage of point x, it will no longer provide energy as a heat source.
Similar to [13], the term $\beta T_{i}$ governs cooling over the whole region.
It can be considered as the difference between the current temperature and $0$
degree. The larger the difference is, the more remarkable the cooling effect
is. Parameter $\beta$ is the global cooling coefficient, which controls the
global cooling effect.

According to Fourier theorem, the heat flow vector at any point in the system
is directly proportional to the temperature gradient at that point, but in the
opposite direction, always along the direction of temperature reduction. The
motion of the agent can be compared with the flow of heat flow, but the motion
direction is opposite to the heat flow vector, which makes the agent always
move in the direction of heat source, that is, in the direction towards more
workload. Therefore, the dynamics of agent $i$ is given as

$\bf{\dot{s}_{i}}=u_{i},$ (12)

where the control input $\bf{u}_{i}$ is given by

$\bf{u}_{i}=V_{i}\frac{\bigtriangledown
T_{i}(\bf{s}_{i}(t),t)}{||\bigtriangledown T_{i}(\bf{s}_{i}(t),t)||},$ (13)

with the constant speed $V_{i}$.

1 Partition the region $D$ with (1) ;

// Agent $i$ performs simultaneously as follow

2 while  _$M(t) >0$_ do

3 Calculate the temperature field on $D_{i}$ with (8);

4 Compute control input $u_{i}$ with (13);

5 Update the total workload $M(t)$ with (5);

6 end while

Algorithm 1 Coverage Control on General Subregions

###  3.2 Implementation of cooperative coverage algorithm

Section 2.1 presents a method of workspace partition based on Voronoi diagram,
but there is a problem left, that is, even if Voronoi partition can ensure the
minimum distance from the point in the region to the agent, it can not ensure
the equal workload of each workspace. In extreme cases, the time required for
agents to cover their respective areas varies greatly. This may result in the
fact that some agents complete their workload in advance and are in the idle
condition, which causes the wasting of resources and decrease of efficiency.
In this section, we propose a method of iterative partition, which can make
full use of agent resources while ensuring the division of subregions, and
finally complete the overall coverage mission in finite time.

Let $t$ denote the time from the start of the coverage to the current time,
and $t^{\prime}$ represents the time from the start of iteration to the
current time. Suppose that in the $k$-th iteration, agent $i$ first completes
the coverage task of its subregion $D^{k}_{i}$, it takes total time $T^{k}$.
We need to determine the segmentation result of iteration $k+1$. Before
partition, we need to update the workload $m_{0}^{k+1}(\textbf{x})$. The
workload at the end of last iteration is used as the initial value of the next
iteration.

$m_{0}^{k+1}(\textbf{x})=m^{k}(\textbf{x},T^{k}),$ (14)

where $m^{k}(\textbf{x},T^{k})$ is the value of function
$m^{k}(\textbf{x},t^{\prime})$ at time $T^{k}$. Similar to (4),
$m^{k}(\textbf{x},t^{\prime})$ is defined as

$m^{k}(\textbf{x},t^{\prime})=\max\left(0,m_{0}^{k}(\textbf{x})-\sum_{i=1}^{N}\int_{0}^{t^{\prime}}p_{i}(\textbf{x},s_{i}^{k}(\tau))d\tau\right).$
(15)

Then agent $i$ moves to the subregion of agent $j$ that it can communicate
with. Besides, the remaining workload in $D_{j}^{k}$ is the largest compared
with that of other neighbors of agent $i$. Thus, the number $j$ can be
determined by

$j=\arg\underbrace{\max}_{j}w_{ij}\int_{D_{j}^{k}}m_{0}^{k+1}(\textbf{x})d\textbf{x}.$
(16)

Set the initial position of agent $i$ in the $k+1$ iteration as the point with
the largest workload in area $D_{j}^{k}$, and assume that the moving time is
ignored, because the moving speed of agent without coverage can be much
greater than $V_{i}$, that is, the time consumption between iterations is
ignored

$\bf{s}_{i}^{k+1}(0)=\arg\underbrace{\max}_{\textbf{x}}m_{0}^{k+1}(\textbf{x}),\quad\textbf{x}\in
D_{j}^{k}.$ (17)

After that, we can use the (1) to get new region partition results
$D_{i}^{k+1}$. Since the solution of heat transfer equation in Section 3.1 is
not directly related to time, it can be used to control the movement of agent,
but the difference is that when any agent completes the subregion, it will be
regarded as the end of iterations and go to the next iteration until $M(t)$
approaches 0. In order to achieve finite-time coverage, we propose a
temperature field update method (i.e., Maximal Update). In each iteration,
Maximal Update is used after Real-time Update. Generally, the time $T_{u}^{k}$
of Real-time Update can be set for each iteration. After that, when
$t^{\prime}>T_{u}^{k}$, Maximal Update is adopted until the end of this
iteration.

When the temperature field remains unchanged, the agent moves towards local
maximum point according to (13). For the subregion where each agent is
located, Delaunay triangulation in [16] can be carried out to obtain the
triangular mesh of the region. For the triangular region with local maximum
points $(x_{max},y_{max})$, there is a minimum coverage circle centered on
local maximum point, which can cover the triangular region, and it satisfies

$(x-x_{max})^{2}+(y-y_{max})^{2}=r_{min}^{2},\quad r_{min}\leq H_{max}\leq<r.$
(18)

Here $r_{min}$ is the radius of the minimum coverage circle, which is
equivalent to the maximum distance from the local maximum point to the vertex
of the triangle. $H_{max}$ is the maximum mesh edge mesh. At the same time, it
is required that the coverage radius of the agent should be greater than
$H_{max}$, which ensures that once the agent enters the triangular area, the
whole area will be within the coverage range. When the agent is moving towards
the local maximum point, the temperature field remains unchanged. When the
agent enters the triangular area where the local maximum value is located, it
is ensured that the coverage of maximum point by defining the coverage circle,
As shown in the Figure 2. At this time, we keep the agent stationary and
update the temperature field after completing the work task of the triangular
area. The agent runs to the next local maximum point according to the gradient
of temperature field. This iteration continues until the end. (For details,
refer to Algorithm 2). Due to less workload on subregions at the end of
coverage, we set the maximum iterations $k_{max}$. When $k=k_{max}$, the agent
is only responsible for clearing workload on its subregion until all workload
is completed. The complete coverage algorithm is presneted in Algorithm 3.

Figure 2: Illustration of Maximal Update Method: blackish green pentagram is
the local maximum point and its minimun coverage circle. The trajectory of
agent is shown in the figure and the pentagram is the location that agent
reach the triangular area. In addition, the figure shows the length
relationship between $r$, $r_{min}$, $H_{max}$.

1 Partition the region $D$ with (1) ;

// Agent $i$ performs simultaneously as follow

2 while  _$\int_{D_{i}^{k}}m^{k}(\textbf{x},t^{\prime})d\textbf{x} >0$ and no
other agents complete workload_ do

3 if  _$t^{\prime}\leq T_{u}^{k}$_ then

4 Calculate the temperature field on subregion $D_{i}^{k}$ with (8);

5 Update $s_{i}$ with (12) and (13) and $m^{k}(\textbf{x},t^{\prime})$ with
(15);

6 else

7 if  _agent $i$ is at the boundary of triangulation region with local
maximum_ then

8 Keep static and clear triangle workload;

9 Calculate the temperature field on subregion $D_{i}^{k}$ with (8);

10 Update $s_{i}$ with (12) and (13) and $m^{k}(\textbf{x},t^{\prime})$ with
(15);

11 else

12 Update $s_{i}$ with (12) and (13) and $m^{k}(\textbf{x},t^{\prime})$ with
(15);

13 end if

14

15 end if

16

17 end while

Algorithm 2 Coverage Control on Triangulated Subregions

1 $k\leftarrow 1$;

2 while  _$M(t) >0$_ do

3 if  _$k <k_{max}$_ then

4 Run Algorithm 2 ;

5 Determine the subregion and move to $D_{j}^{k}$ with (16);

6 Drive agent to the maximum workload with (17);

7 $k\leftarrow k+1$;

8 else

9 Run Algorithm 1;

10 end if

11

12 end while

Algorithm 3 Distributed Coverage Control on Global Region

##  4 Theoretical Analysis

In this section, we provide theoretical results on the finite-time coverage of
multi-agent systems using the proposed thermal field-induced coverage control
method.

######  Proposition 4.1.

$\forall\Delta t\geq 0$, $\textbf{x}\in D_{i}$, $i\in\textsc{Z}^{+}$,
$h_{i}(\textbf{x},t)=0\Longleftrightarrow\bigtriangledown
T_{i}(\textbf{x},t+\Delta t)=0$.

###### Proof.

For $h_{i}(\textbf{x},t)=0\Rightarrow\bigtriangledown T_{i}(\textbf{x},t)=0$
and $\bigtriangledown T_{i}(\textbf{x},t+\Delta t)=0$. When
$h_{i}(\textbf{x},t)=0$, $\textbf{x}\in D_{i}$, rewrite the (8) as follows:

$\alpha(\frac{\partial^{2}T_{i}(\textbf{x},t)}{\partial
x^{2}}+\frac{\partial^{2}T_{i}(\textbf{x},t)}{\partial y^{2}})=\beta
T_{i}(\textbf{x},t).$

Obviously, $T(\textbf{x},t)=0$ is the solution of the partial differential
equation and satisfies the boundary conditions at the same time. From which we
can deduce

$\frac{\partial T_{i}(\textbf{x},t)}{\partial x}=0,\quad\frac{\partial
T_{i}(\textbf{x},t)}{\partial y}=0.$

Because $h$ is a monotonically decreasing function with $t$ and $h\geq 0$, we
can get $h_{i}(\textbf{x},t+\Delta t)=0$ easily. Likewise, we can obtain
$\bigtriangledown T_{i}(\textbf{x},t+\Delta t)=0$. The conditions
$\bigtriangledown T_{i}(\textbf{x},t)=0$ and $\bigtriangledown
T_{i}(\textbf{x},t+\Delta t)=0$ leads to $h_{i}(\textbf{x},t)=0$. From

$\bigtriangledown T_{i}(\textbf{x},t)=0\Rightarrow\Delta
T_{i}(\textbf{x},t)=0,\quad\bigtriangledown T_{i}(\textbf{x},t+\Delta
t)=0\Rightarrow\Delta T_{i}(\textbf{x},t+\Delta t)=0,$

we can get

$h_{i}(\textbf{x},t)=\beta T_{i}(\textbf{x},t)=c_{1},\quad
h_{i}(\textbf{x},t+\Delta t)=\beta T_{i}(\textbf{x},t+\Delta t)=c_{2},$

where $c_{1}$ and $c_{2}$ are constants. Owing to $c_{1}\neq 0$, we have

$h_{i}(\textbf{x},t+\Delta t)=\frac{m(\textbf{x},t+\Delta t)}{\hat{m}_{i}},$

where $\frac{m(\textbf{x},t)}{\bar{m}_{i}}=c_{1}$. However, $m(\textbf{x},t)$
is a monotonically increasing function and $c_{1}\neq 0$, leading to
$\frac{m(\textbf{x},t+\Delta t)}{\bar{m}_{i}}\neq c_{1}$, which conflicts with
$h_{i}(\textbf{x},t+\Delta t)=c_{2}$, even $c_{2}=c_{1}$. According to the
above counter example, it is concluded that $c_{1}=0$. Thus, the proof is
completed. ∎

######  Remark 4.1.

$\forall\Delta t>0$, $\textbf{x}\in D_{i}$. When $h_{i}(\textbf{x},t)=0$, the
coverage of region $D_{i}$ is finished. $\bigtriangledown
T_{i}(\textbf{x},t)=0$ and $\bigtriangledown T_{i}(\textbf{x},t+\Delta t)=0$
means the gradient of temperature field is zero everywhere, that is, the agent
stops moving. It can be concluded that when the gradient of temperature field
becomes zero at a certain time and then all become zero (the agent stops
moving at a certain time and then remains stationary), the coverage of the
area is completed.

######  Lemma 4.1.

$\forall x_{0}\in D_{i}$, $i\in\textsc{Z}^{+}$,
$H(T_{i}(x_{0},t))<0\Longrightarrow h_{i}(x_{0},t)>0$, where
$H(T_{i}(x_{0},t))<0$ is Hessian matrix of $T_{i}(x_{0},t)$.

###### Proof.

In the 2D plane, we can get Hessian matrix of $T_{i}(x_{0},t)$.

$H(T_{i}(x_{0},t))=\begin{bmatrix}\frac{\partial^{2}T_{i}(x_{0},t)}{\partial
x\partial x}&\frac{\partial^{2}T_{i}(x_{0},t)}{\partial x\partial y}\\\
\frac{\partial^{2}T_{i}(x_{0},t)}{\partial y\partial
x}&\frac{\partial^{2}T_{i}(x_{0},t)}{\partial y\partial y}\end{bmatrix}.$

Since $H(T_{i}(x_{0},t))$ is negative definite, we can get
$\frac{\partial^{2}T_{i}(x_{0},t)}{\partial x\partial x}<0$ and
$\frac{\partial^{2}T_{i}(x_{0},t)}{\partial y\partial y}<0$. It is concluded
that

$\alpha\Delta
T_{i}(\textbf{x},t)=\alpha(\frac{\partial^{2}T_{i}(x_{0},t)}{\partial
x\partial x}+\frac{\partial^{2}T_{i}(x_{0},t)}{\partial y\partial y})<0.$

Because of the existence of the term $\beta T_{i}(\textbf{x},t)$ in the
equation, the temperature of whole field is greater than zero. The specific
reasons can be seen in the physical principle of heat transfer equation and
(10). So, we can get

$T_{i}(x_{0},t)>0.$

For point $x_{0}$, (8) can be written as

$\alpha\Delta T_{i}(x_{0},t)+h_{i}(x_{0},t)=\beta T_{i}(x_{0},t).$

Through the above analysis, it is concluded that the right side of the
equation is less than 0 and $\alpha\Delta T_{i}(x_{0},t)$ is less than 0, we
can get $h_{i}(x_{0},t)>0$, which completes the proof. ∎

######  Lemma 4.2.

Each agent can reach the triangular area with local maximum in finite time
using Maximal Upgrade Method.

###### Proof.

In Maximal Upgrade Method, before the update, the temperature field remains
unchanged. $T_{i}(x_{0})$ is the temperature value of local maximum point in
region $D_{i}$, $T_{i}(\bf{s}_{i}(t))$ is the temperature value of each point
on the trajectory of agent $i$. Contruct the following Lyapunov-Krasovskii
function:

$V_{i}(t)=T_{i}(x_{0})-T_{i}(\bf{s}_{i}(t)).$

Calculating the time derivative of $V_{i}(t)$ yields

$\displaystyle\dot{V}_{i}(t)$ $\displaystyle=-\bigtriangledown
T_{i}(\bf{s}_{i}(t))\dot{l}_{i}^{T}(t)$ $\displaystyle=-\bigtriangledown
T_{i}(\bf{s}_{i}(t))V_{i}\frac{\bigtriangledown
T_{i}^{T}(\bf{s}_{i}(t))}{||\bigtriangledown T_{i}(\bf{s}_{i}(t))||}$
$\displaystyle=-V_{i}||\bigtriangledown T_{i}(\bf{s}_{i}(t))||.$

where $\dot{s}_{i}(t)$ is defined in (13). We can easily get $V_{i}(t)>0$ and
$\dot{V}_{i}(t)<0$. Hence, the system (12) is asymptotical stable. In other
words, the agent can reach the local maximum point when
$t\longrightarrow\infty$. According to Lyapunov asymptotical stability and the
definition of limit, $\forall\epsilon>0$, $\exists T>0$, when $t>T$, one has
$||\bf{s}_{i}(t)-x_{0}||\leq\epsilon$. Take $\epsilon$ equals the radius of
minimum covering circle $r_{min}$, which completes the proof. ∎

######  Lemma 4.3.

Delaunay triangulation enables each agent to complete workload on its
subregion in finite time.

###### Proof.

Since the use time $T_{u}^{k}$ of Real-time Update is fixed, its value does
not affect the proof result. In Maximal Update, before updating the
temperature field each time, the number of local maximum points corresponding
to the current temperature field is limited, which is determined by the
limited number of triangles in the triangulation result of the region. For
each update of the temperature field, according to Lemma 4.2., $\exists
T_{1}>0$, $||\bf{s}_{i}(T_{1})-x_{0}||\leq r_{min}$. Then, according to (18),
the agent can cover the triangular area where the local maximum point is
located after stopping the movement, and the coverage time is

$T_{2}=\frac{m^{k}(x_{0})}{p_{i}(x_{0},\bf{s}_{i})},$

where $m^{k}(x_{0})$ is the workload of local maximum point, $\bf{s}_{i}$ is
the location of agent $i$. It can be concluded that the coverage time of the
triangular region where the local maximum point is located is $T_{1}+T_{2}$,
which is limited. According to the definition of maximum point $x_{0}$, we
have

$\bigtriangledown T_{i}(x_{0})=0,\quad H(T_{i}(x_{0}))<0.$

According to Lemma 4.1, we have $h_{i}(x_{0})>0$. For the triangular region
that has not been covered, due to finite triangulation cells of subregion
$D_{i}$, it can be deduced that the coverage time of the region is finite,
which completes the proof. ∎

######  Theorem 4.1.

Algorithm 3 ensures the finite-time completion of cooperative coverage
mission.

###### Proof.

When $k<k_{max}$, each iteration takes finte time, which can be proved by
Lemma 4.3.. For the $k_{max}$-th itration, the completion time depends on the
maximum time for the agent to complete the subregion coverage. It is finite-
time and can be proved in a similar way to Lemma 4.3.. ∎

##  5 Numerical Simulations

In this section, we provide simulation results to verify the proposed coverage
algorithm and compare it with other existing approaches.

Figure 3: Coverage process of five agents using Algorithm 3 on the region $D$.
(a), (b): Initial workload distribution for two iterations. (c), (d):
Temprature value distribution at the beginning of first and second iteration.

For simplicity, we consider five agents in a region. Region $D$ is a concave
area formed by digging $5\times 5$ small squares out of $15\times 15$ large
squares. Parameters are selected as follow: $P=6$, $r=0.5$, $\lambda=1$,
$\alpha=1$, $\beta=1$, $V_{i}=0.5$, $T_{u}=500$, $k_{max}=7$. Besides, the
initial workload on the coverage region is set as follows

$\begin{array}[]{r}m_{0}(\textbf{x})=m_{0}^{1}(\textbf{x})=40e^{-\frac{(x-8)^{2}+(y-7)^{2}}{20}}+20e^{-\frac{(x-2.5)^{2}+(y-13)^{2}}{20}}+40e^{-\frac{(x-14)^{2}+(y-13)^{2}}{20}}\\\
+20e^{-\frac{(x-2.5)^{2}+(y-5)^{2}}{20}}+20e^{-\frac{(x-14)^{2}+(y-7)^{2}}{20}}.\end{array}$
(19)

Four snapshots during implementing Algorithm 3 are shown in Figure 3. Through
the distribution of temperature value, it is obvious that each region forms
its own relatively independent temperature field after Voronoi partition. But
at the same time, it also retains the value information of the initial
workload distribution. According to the second iteration, although the
distribution of workload is discontinuous, it is successfully transformed into
a continuous temperature field through the construction of temperature
transfer function. After seven iterations, we finally get the motion
trajectories of five agents, as shown in Figure 4 where the square is the
starting position and the pentagram is the ending position. Compare Algorithm
3 (ALGO 3) with centralized temperature field control algorithm ([13]) and
Algorithm 1 (ALGO 1), and get the curve of workload changing with time in
Figure 5.

Figure 4: Trajectories of five agents on region $D$.

Figure 5: Curve of workload using [13], ALGO 1 and ALGO 3.

During the 1st iteration, the centralized control method achieves higher
coverage efficiency. The distributed segmentation method accelerates the
reduction of the workload of the sub area, resulting in the phenomenon that
the workload of the agent has been emptied through the location, which wastes
time. However, it can be seen that the iterative method has brought changes in
efficiency in the later stage, and the replacement of work area has alleviated
the waste of coverage resources. Based on the optimization objective, we can
compare the algorithm effect by observing the difference between the total
coverage time and the optimal time in Table 1. It can be seen that Algorithm 3
achieves the best performance.

Table 1: Comparison of different coverage control algorithms Method |  T |  $\Delta T$ |  $T^{*}$
---|---|---|---
[13] |  714 |  253 |  461
ALGO 1 |  663 |  202
ALGO 3 |  605 |  144

##  6 Conclusions

This work presents a distributed solution to multi-agent coverage problem in
uncertain environment. Voronoi partition is used to divide the whole coverage
region into multiple sub-regions, which allows agents to complete the coverage
task in a distributed manner. The temperature field induced control strategy
enables the agent to move in its own sub-region and complete the coverage
task. Besides, the iteration between region partition and coverage control
improves the coverage efficiency. Theoretical analysis is conducted to
guarantee the finite-time completion of coverage task, numerical simulations
are carried out to substantiate the efficiency and robustness of algorithm.

## Acknowledgement

This work was supported by the Fundamental Research Funds for the Central
Universities, China University of Geosciences (Wuhan).

## References

  * [1] C. Zhai, H. Zhang, and G. Xiao, Cooperative Coverage Control of Multi-Agent Systems and its Applications, Springer, ISBN 978-981-16-7624-6, 2021.
  * [2] J. Shamman, Cooperative Control of Distributed Multi-Agent Systems, Chichester, U.K. Wiley, 2007.
  * [3] H. Zhang, C. Zhai, and Z. Chen, A general alignment repulsion algorithm for flocking of multi-agent systems, IEEE Trans. Autom. Control, vol. 56, no. 2, pp. 430–435, Feb. 2011.
  * [4] G. Wen, G. Hu, W. Yu, J. Cao, and G. Chen, Consensus tracking for higher-order multi-agent systems with switching directed topologies and occasionally missing control inputs, Syst. Control Lett., vol. 62, no. 12, pp. 1151-1158, 2013.
  * [5] X. Liu, S. Ge, and C. Goh, Neural-network-based switching formation tracking control of multiagents with uncertainties in constrained space, IEEE Trans. Syst., Man, Cybern., Syst., vol. 49, no. 5, pp. 1006–1015, May 2019.
  * [6] Z. Li, Y. Yuan, F. Ke, W. He, and C. Su, Robust vision-based tube model predictive control of multiple mobile robots for leader-follower formation, IEEE Trans. Ind. Electron., vol. 67, no. 4, pp. 3096–3106, Apr. 2020.
  * [7] C. Ma and L. Xie, Necessary and sufficient conditions for leader-following bipartite consensus with measurement noise, IEEE Trans.Syst., Man, Cybern., Syst., vol. 50, no. 5, pp. 1976–1981, May 2020.
  * [8] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, Coverage control for mobile sensing network, IEEE Trans. Robot. Autom., vol. 20, no. 2, pp. 243–255, Apr. 2004.
  * [9] Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi tesseuations: Applications and algorithms, SIAM Rev., vol. 41, no. 4, pp. 637–676, 1999.
  * [10] M. Schwager, D. Rus, and J. Slotine, Distributed, adaptive control for coverage with networked robots, Int. J. Robot. Res., vol. 28, no. 3, pp. 357–375, 2009.
  * [11] C. Zhai and Y. Hong, Decentralized sweep coverage algorithm for multiagent systems with workload uncertainties, Automatica, vol. 49, no. 7, pp. 2154–2159, 2013
  * [12] C. Zhai, H Zhang, G. Xiao, and M. Chen, Design and assessment of sweep coverage algorithms for multiagent systems with online learning strategies, IEEE Trans.Syst., Man, Cybern., Syst., Nov. 25, 2021, DOI: 10.1109/TSMC.2021.3128186.
  * [13] S. Ivic, B. Crnkovic and I. Mezic, Ergodicity-Based Cooperative Multiagent Area Coverage via a Potential Field, IEEE Transactions on Cybernetics, vol. 47, no. 8, pp. 1983–1993, Aug. 2017.
  * [14] F. Aurenhammer, Voronoi diagrams – a survey of a fundamental geometric data structure, ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991.
  * [15] C. Cassandras and W. Li, Sensor Networks and Cooperative Control, European Journal of Control, vol. 11, pp. 436–463, 2005.
  * [16] D. Lee, B. Schachter, Two algorithms for constructing a Delaunay triangulation, International Journal of Computer & Information Sciences, vol. 9, no. 3, pp. 219–242, 1980.