Theoretical and Experimental Collaborative Area Coverage Schemes Using Mobile Agents

Abstract

This chapter is concerned with the development of collaborative control schemes for mobile ground robots for area coverage purposes. The simplest scheme assumes point omnidirectional robots with heterogeneous circular sensing patterns. Using information from their spatial neighbors, each robot (agent) computes its cell relying on the power diagram partitioning. If there is uncertainty in inferring the locations of these robots, the Additively Weighted Guaranteed Voronoi scheme is employed resulting in a rather conservative performance. The aforementioned schemes are enhanced by using a Voronoi-free coverage scheme that relies on the knowledge of any arbitrary sensing pattern employed by the agents. Experimental results are offered to highlight the efficiency of the suggested control laws.

1. Introduction

The problem of area coverage is one that has been widely studied in the past decade and consists of the deployment of a sensor-equipped mobile robot team. It is usually categorized as either blanket or sweep coverage. In blanket or static coverage the goal of the robot team is a final static configuration at which an objective function is maximized [1, 2, 3]. In sweep or dynamic coverage on the other hand the mobile agents are tasked with maximizing a constantly changing objective, resulting in potentially continuous motion of the agents [4, 5, 6].

Several aspects of the area coverage problem have been studied over the years, including the effect of robot dynamics [7, 8, 9], communication constraints among agents [10, 11, 12], complex non-convex regions [13, 14, 15] or guaranteeing collision avoidance among the mobile robots [16, 17]. A wide variety of methods has also been employed for multirobot area coverage such as geometric optimization [18], optimal control [19] or event-triggered control [20]. Due to the widespread adoption of unmanned aerial vehicles (UAVs), they have become a popular platform for area coverage [21, 22, 23] since they are usually equipped with visual sensors [24, 25, 26].

In this chapter we focus on the blanket coverage problem for a convex region of interest. The techniques outlined are based on geometric optimization principles and result in distributed control schemes. In a distributed control law, each agent uses only local information from its neighboring agents in order to compute its own control input so that a common objective function is maximized. Distributed control laws are highly desirable in multiagent systems because they are easily scalable to large robot teams and because they significantly reduce the computational burden and communication requirements on the agents. Moreover, they are more robust to failures and can adapt to unexpected changes without the need to recompute a new solution as is the case with most centralized control schemes.

The chapter is organized as follows. Section 2.1 contains some mathematical preliminaries which will be relevant throughout the chapter. In Section 2.2 the problem of blanket area coverage in a convex region by a heterogeneous team of agents with omnidirectional sensors is examined. In Section 2.3 the results are extended by taking into account the uncertain positioning of the mobile robots. Section 2.4 presents a tessellation-free method for area coverage by agents with anisotropic sensing patterns. Section 2.5 contains some experimental results and it is followed by concluding remarks.

2. Area coverage using mobile agents

2.1. Mathematical preliminaries

Throughout the chapter we assume a compact, convex region $\mathrm{\Omega }\subset {\mathbb{R}}^2$ to be covered by the mobile agents and a space density function $\varphi :\mathrm{\Omega }\to {\mathbb{R}}_{+}$. The space density function is used to encode any a priori information regarding the importance of points in $\mathrm{\Omega }$, for example the likelihood that an event may occur at a given point. The boundary of a set $S$ is denoted $\partial S$ and its interior is denoted $\mathit{Int}\left(S\right)$. The set $\left\{1,\dots ,n\right\}$ is denoted $I_n$. The indicator function ${\mathbf{1}}_S\left(q\right)$ for a set $S$ and the $2\times 2$ rotation matrix $\mathbf{R}\left(\theta \right)$ are respectively

$${\mathbf{1}}_S\left(q\right)=\left\{\begin{array}{ll}1& \text{if}q\in S\\ 0& \text{if}q\notin S\end{array}\right.,\mathbf{R}\left(\theta \right)=\left[\begin{array}{cc}cos\theta & -sin\theta \\ sin\theta & cos\theta \end{array}\right],$$

while the $2\times 2$ identity matrix is denoted ${\mathbb{I}}_2$.

2.2. Heterogeneous agents with omnidirectional sensing

One of the simplest variants of the area coverage problem is the case of a team of homogeneous agents with circular sensing footprints. This was one of the first variants to be studied and there is extensive work on the topic [27, 28]. One generalization of this problem arises by allowing each agent to have a different sensing performance, resulting in a heterogeneous team [29, 30, 31]. In this chapter we will focus in the coverage of a convex region by a team of unicycle robots equipped with heterogeneous omnidirectional sensors.

2.2.1. Problem statement

A team of $n$ mobile ground agents is deployed inside the region of interest $\mathrm{\Omega }$. Each agent $i\in I_n$ is approximated by a point mass located at $q_i\in \mathrm{\Omega }$ which is governed by the following kinematic model

$${\dot{q}}_i=u_i,q\in \mathrm{\Omega },u_i\in {\mathbb{R}}^2$$E1

where $u_i$ is the velocity control input of the agent.

Each agent has been equipped with an omnidirectional sensor with limited sensing radius $R_i$, which is allowed to differ among agents, resulting in a circular sensing pattern

$$S_i\left(q_i,R_i\right)=\left\{q\in \mathrm{\Omega }:\parallel q-q_i\parallel \le R_i\right\}.$$E2

Since the goal of the mobile agent team is the maximization of the covered area using their sensors, while also taking into account the space density function, we define the coverage objective as

$$\mathcal{H}=\underset{\mathrm{\Omega }}{\int }\underset{i\in I_n}{max}{\mathbf{1}}_{S_i}\left(q\right)\varphi \left(q\right)\mathit{dq}.$$E3

The control objective is the design of a distributed control law for the mobile agents in order to guarantee monotonic increase of the coverage objective $\mathcal{H}$ over time.

2.2.2. Space partitioning

The first step in designing a distributed control law is finding a method to distribute the computation of the coverage objective $\mathcal{H}$. Due to the heterogeneous sensing performance of the agents, the Voronoi diagram is inadequate for the task as it does not take this information into account. To that extent the power diagram will be used in order to assign a region of responsibility to each agent. In contrast to the Voronoi diagram whose generators are points, the generators of the power diagram are disks.

Given a planar region $\mathrm{\Omega }$ and a set of disks $S=\left\{S_1,\dots ,S_n\right\}$ with centers $Q=\left\{q_1,\dots ,q_n\right\}$ and radii $R=\left\{R_1,\dots ,R_n\right\}$, the power diagram assigns a convex cell $P_i\hspace{0.17em}\subseteq \hspace{0.17em}\mathrm{\Omega }$ to each disk $S_i$

$$P_i\left(\mathrm{\Omega },S\right)=\left\{q\in \mathrm{\Omega }:\parallel q-q_i{\parallel }^2-{R_i}^2\le \parallel q-q_j{\parallel }^2-{R_j}^2,\forall j\in I_n\setminus i\right\},i\in I_n.$$

The power diagram is a complete tessellation of $\mathrm{\Omega }$, thus it holds that

$$\mathrm{\Omega }=\bigcup _{i\in I_n}{P}_i,\mathit{Int}\left(P_i\right)\cap \mathit{Int}\left(P_j\right)=\varnothing ,\forall i\ne j.$$

A notable property of power diagrams is their duality with power-weighted Delaunay graphs. It has been shown that in order to compute the power cell $P_i$ of point $q_i$, only the power-weighted Delaunay neighbors $N_i$ of point $q_i$ need to be considered. The power-weighted Delaunay neighbors of agent $i$ have the property that

$$N_i=\left\{j\in I_n\setminus i:P_i\cap P_j\ne \varnothing \right\},$$E4

By using the previous definition, the power diagram can be formulated as

$$P_i\left(\mathrm{\Omega },Q\right)=\left\{q\in \mathrm{\Omega }:\parallel q-q_i{\parallel }^2-{R_i}^2\le \parallel q-q_j{\parallel }^2-{R_j}^2,\forall j\in N_i\right\},i\in I_n.$$E5

Since it holds that $N_i\hspace{0.17em}\subseteq \hspace{0.17em}{I}_n$, each agent $i$ requires information only from its power-weighted Delaunay neighbors in order to compute its own power cell $P_i$, thus rendering the computation of the power diagram distributed.

Remark 2.1. When the agents’ sensing radii are equal, i.e., $R_i=R_j,\forall i,j$, the power diagram converges to the Voronoi diagram. In that case the computation of the cell of agent $i$ requires information only from the Delaunay neighbors of agent $i$. Thus the power diagram can be also utilized in the case of agents with homogeneous sensing performance.

For any two agents $i$ and $j$ with $S_i\cap S_j\ne \varnothing$ it holds that $S_i\setminus P_i\in P_j\cap S_j$ and $S_j\setminus P_j\in P_i\cap S_i$ due to the properties of the power diagram. Thus if a part of some agent $i$ ’s sensing pattern is inside the cell of some other agent $j$, then that part is guaranteed to be sensed by $j$. Consequently, we define the r-limited power cell of agent $i$ as $P_i^R=P_i\cap S_i$. Thus by utilizing the power diagram, the coverage objective $\mathcal{H}$ can be computed as follows

$$\mathcal{H}=\sum _{i\in I_n}\underset{P_i^R}{\int }\varphi \left(q\right)\mathit{dq}.$$E6

Since $\mathcal{H}$ can be written as a sum of integrals over r-limited power cells and since an agent can compute its own power cell using information just from its power-weighted Delaunay neighbors, the computation of $\mathcal{H}$ is distributed.

2.2.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective $\mathcal{H}$, what is left is the derivation of a distributed control law for its maximization.

Theorem 2.1. For a team of mobile ground agents with kinematics (1), sensing performance (2) and using the power diagram partitioning (5), the control law

$$u_i={\alpha }_i\underset{\partial P_i^R\cap \partial S_i}{\int }{n}_i\varphi \left(q\right)\mathrm{d}q,$$E7

where ${\alpha }_i$ is a positive constant and $n_i$ is the outward unit normal vector on $\partial P_i^R$, leading the agents to trajectories that result in monotonic increase of the coverage objective (6).

Proof. We start by evaluating the time derivative of the objective using the agent dynamics (1) we get $\frac{\partial \mathcal{H}}{\partial t}={\displaystyle \sum _{i\in I_n}}\frac{\partial \mathcal{H}}{\partial q_i}\frac{\partial q_i}{\partial t}={\displaystyle \sum _{i\in I_n}}\frac{\partial \mathcal{H}}{\partial q_i}{\dot{q}}_i={\displaystyle \sum _{i\in I_n}}\frac{\partial \mathcal{H}}{\partial q_i}{u}_i.$ By selecting the control law $u_i={\alpha }_i\frac{\partial \mathcal{H}}{\partial q_i},{\alpha }_i>0$, we can guarantee monotonic increase of the coverage objective.

The partial derivative $\frac{\partial \mathcal{H}}{\partial q_i}$ is evaluated as follows

$$\frac{\partial \mathcal{H}}{\partial q_i}=\frac{\partial }{\partial q_i}\sum _{i\in I_n}\underset{P_i^R}{\int }\varphi \left(q\right)\mathrm{d}q=\frac{\partial }{\partial q_i}\underset{P_i^R}{\int }\varphi \left(q\right)\mathrm{d}q+\sum _{j\ne i}\frac{\partial }{\partial q_i}\underset{P_j^R}{\int }\varphi \left(q\right)\mathrm{d}q.$$

Since only the cells of power-weighted Delaunay neighbors of agent $i$ are affected by its movement and $\frac{\partial \varphi \left(q\right)}{\partial q_i}=0$, by using the Leibniz integral rule [32], the previous equation becomes

$$\frac{\partial \mathcal{H}}{\partial q_i}=\underset{\partial P_i^R}{\int }{\upsilon }_i^i{n}_i\varphi \left(q\right)\mathrm{d}q+\sum _{j\in N_i}\underset{\partial P_j^R}{\int }{\upsilon }_j^i{n}_j\varphi \left(q\right)\mathrm{d}q$$

where ${\upsilon }_j^i$ is the Jacobian matrix ${\upsilon }_j^i=\frac{\partial q}{\partial q_i},q\in \partial P_j^R$ and $n_i$ is the outward unit normal vector on $\partial P_i^R$. The boundary $\partial P_i^R$ can be decomposed into three disjoint sets $\partial P_i^R=\left(\partial P_i^R\cap \partial S_i\right)\cup \left(\partial P_i^R\cap \mathrm{\partial \Omega }\right)\cup \left[{\displaystyle \underset{j\in N_i}{\cup }}\left(\partial P_i^R\cap \partial P_j^R\right)\right],$ where $\partial P_i^R\cap \partial S_i$ denotes part of the r-limited cell’s boundary that is also part of the boundary of the agent’s sensing disk, $\partial P_i^R\cap \mathrm{\partial \Omega }$ denotes the common boundary between the r-limited cell and the region, while $\partial P_i^R\cap \partial P_j^R$ denotes the common boundary with the r-limited cell of some neighboring agent $j$. This decomposition is presented in Figure 1 where $\partial P_i^R\cap \partial S_i$, $\partial P_i^R\cap \mathrm{\partial \Omega }$ and $\partial P_i^R\cap P_j^R$ are shown in solid green, red, and blue lines, respectively.

Figure 1.

Decomposition of $\partial P_i^R$ into disjoint sets and corresponding normal vectors.

Since the region $\mathrm{\Omega }$ is assumed to be static, it holds that ${\upsilon }_i^i=0,\forall q\in \partial P_i^R\cap \mathrm{\partial \Omega }$. In addition, since $q\in \partial P_i^R\cap \partial S_i$ are points on a circle with center $q_i$, it holds that ${\upsilon }_i^i={\mathbb{I}}_2,\forall q\in \partial P_i^R\cap \partial S_i$. Finally, $P_j^R$ is only affected by the movement of agent $i$ at the common boundary $\partial P_i^R\cap \partial P_j^R$, resulting in the expression

$$\frac{\partial \mathcal{H}}{\partial q_i}=\underset{\partial P_i^R\cap \partial S_i}{\int }{n}_i\varphi \left(q\right)\mathrm{d}q+\sum _{j\in N_i}\underset{\partial P_i^R\cap \partial P_j^R}{\int }{\upsilon }_i^i{n}_i\varphi \left(q\right)\mathrm{d}q+\sum _{j\in N_i}\underset{\partial P_i^R\cap \partial P_j^R}{\int }{\upsilon }_j^i{n}_j\varphi \left(q\right)\mathrm{d}q.$$

Since ${\upsilon }_i^i={\upsilon }_j^i$ and $n_i=-n_j$ on the common boundary $\partial P_i^R\cap \partial P_j^R$, as shown in Figure 1, the two sums in the previous expression cancel out and by multiplying it with ${\alpha }_i$ we get (7). □

2.2.4. Simulation study I

An indicative simulation is presented in this section. The region $\mathrm{\Omega }$ is chosen as the convex polygon defined by the vertices with $x$ and $y$ coordinates

$$\begin{array}{l}{\mathrm{\Omega }}_x=\left[0.5,0.5,0.45,0.4,-0.46,-0.5,-0.48,-0.34,0.05\right],\\ {\mathrm{\Omega }}_y=\left[0.43,0.2,-0.3,-0.5,-0.44,-0.1,0.37,0.47,0.5\right]\end{array}$$

respectively. The space density function was $\varphi \left(q\right)=1,\forall q\in \mathrm{\Omega }$. A team of eight agents with heterogeneous sensing radii is deployed inside the region.

The initial and final agent configurations are shown in Figure 2a and c respectively where the agent positions are marked by black dots, the boundaries of their sensing disks are shown as dashed black lines, the boundaries of their cells are marked by solid black lines while their interiors are filled in color. The agent trajectories are shown in Figure 2b with the initial positions marked by dots and the final positions by circles. It is observed that the agents are successfully deployed inside the region, increasing the covered area in the process. In order to provide a more objective measure of the agents’ performance, two different metrics are used. The first, denoted ${\mathcal{H}}^r$, is the value of the coverage objective $\mathcal{H}$ as a percentage of the objective over the whole region which in the case where $\varphi \left(q\right)=1,\forall q\in \mathrm{\Omega }$ it is equal to the area of $\mathrm{\Omega }$. This metric indicates to what extent the agents cover the region $\mathrm{\Omega }$, with high values of ${\mathcal{H}}^r$ corresponding to high coverage over $\mathrm{\Omega }$. The second metric, denoted ${\mathcal{H}}^a$, is the value of the coverage objective $\mathcal{H}$ as a percentage of the agents’ maximum possible covered area which is only meaningful in the case where $\varphi \left(q\right)=1,\forall q\in \mathrm{\Omega }$. This metric indicates to what extent the agents’ sensors are utilized, with high values of ${\mathcal{H}}^a$ indicating that the agents’ sensors are utilized close to their full capabilities. Low values of ${\mathcal{H}}^a$ simultaneously with high values of ${\mathcal{H}}^r$ indicate an overabundance of agents given the size of the current region $\mathrm{\Omega }$. The two metrics are more formally defined as

$${\mathcal{H}}^r=100\frac{\mathcal{H}}{{\displaystyle \underset{\mathrm{\Omega }}{\int }}\varphi \left(q\right)\mathrm{d}q},{\mathcal{H}}^a=100\frac{\mathcal{H}}{{\displaystyle \sum _{i\in I_n}}{\displaystyle \underset{S_i}{\int }}\mathrm{d}q}.$$E8

Figure 2.

Simulation study I: (a) initial configuration, (b) agent trajectories, (c) final configuration and (d) evolution of the coverage objective over time.

Figure 2d shows ${\mathcal{H}}^a$ in solid blue and ${\mathcal{H}}^r$ in dashed red with their final values being 90.0 and 88.9% respectively, indicating that the final agent configuration is an efficient one.

2.3. Heterogeneous agents with omnidirectional sensing under positioning uncertainty

The inherent uncertainty in all localization systems’ measurements can often create unexpected problems in algorithms designed with precise localization in mind. Consequently algorithms robust to positioning errors have been sought for the area coverage problem [33, 34]. This section presents an extension to the control law presented in [35] which allows for teams of agents with heterogeneous sensing performance.

2.3.1. Agent model

The agents’ kinematic model is described by (1) and their sensing performance by (2). Due to the localization systems’ inherent inaccuracy, we assume that $q_i$ is the agent’s position as reported by the localization system, while $r_i$ is a known upper bound on the localization error. Thus we define the positioning uncertainty region $U_i$ as follows

$$U_i\left(q_i,r_i\right)=\left\{q\in {\mathbb{R}}^2:\parallel q-q_i\parallel \le r_i\right\},$$E9

which is a circular disk that contains all possible positions of agent $i$ given its reported position $q_i$ and positioning uncertainty upper bound $r_i$.

In order to take into account the agents’ positioning uncertainty, we define for each agent the guaranteed sensed region $S_i^g$ as

$$S_i^g\left(q_i,r_i,R_i\right)=\bigcap _{\forall q\in U_i}{S}_i\left(q,R_i\right),$$E10

which is the region that is guaranteed to be sensed by agent $i$ given all of its possible positions within its positioning uncertainty region. Given the fact that both $S_i$ and $U_i$ are disks, the above expression can be simplified into

$$S_i^g\left(q_i,r_i,R_i\right)=\left\{q\in {\mathbb{R}}^2:\parallel q-q_i\parallel \le R_i^g=R_i-r_i\right\}.$$E11

2.3.2. Space partitioning and problem statement

In order to take into account the agents’ positioning uncertainty as well as their heterogeneous sensing capabilities, the Additively Weighted Guaranteed Voronoi (AWGV) diagram is employed. The AWGV is an extension of the Guaranteed Voronoi (GV) diagram [36] that incorporates additive weights.

Given a planar region $\mathrm{\Omega }$, a set of uncertain regions $U=\left\{U_1,\dots ,U_n\right\}$ and a set of weights $R^g=\left\{R_1^g,\dots ,R_n^g\right\}$, the AWGV diagram assigns a convex cell $G_i \subseteq \mathrm{\Omega }$ to each region-weight pair $\left(U_i,R_i^g\right)$ as follows

$$G_i\left(\mathrm{\Omega },U,R^g\right)=\left\{q\in \mathrm{\Omega }:\underset{q\in U_i}{max}\parallel q-q_i\parallel -R_i^g \le \underset{q\in U_j}{min}\parallel q-q_j\parallel -R_j^g,\forall j\in I_n\setminus i\right\},i\in I_n.$$

Contrary to the Voronoi diagram, the AWGV diagram is not a complete tessellation of the region $\mathrm{\Omega }$ since a part of $\mathrm{\Omega }$ is left unassigned. This part is called the neutral region $\mathcal{O}$ and it holds that

$$\mathrm{\Omega }=\mathcal{O}\cup \bigcup _{i\in I_n}{G}_i.$$E12

A notable property of AWGV diagrams is their duality with additively weighted Delaunay graphs. It has been shown that in order to compute the AWGV cell $G_i$ of the region-weight pair $\left(U_i,R_i^g\right)$, only the additively weighted Delaunay neighbors $N_i$ of $\left(U_i,R_i^g\right)$ need to be considered. By using the previous definition, the Voronoi diagram can be formulated as

$$G_i\left(\mathrm{\Omega },U,R^g\right)=\left\{q\in \mathrm{\Omega }:\underset{q\in U_i}{max}\parallel q-q_i\parallel -R_i^g \le \underset{q\in U_j}{min}\parallel q-q_j\parallel -R_j^g,\forall j\in N_i\setminus i\right\},i\in I_n.$$E13

Since it holds that $N_i\subseteq I_n$, each agent $i$ requires information only from its additively weighted Delaunay neighbors in order to compute its own AWGV cell $G_i$, thus rendering the computation of the AWGV diagram distributed.

The previous definition of the AWGV can be written as $G_i=\bigcap _{j\in N_i}{H}_{\mathit{ij}},i\in I_n,$ where $H_{\mathit{ij}}=\left\{q\in \mathrm{\Omega }:\parallel q-q_j\parallel -\parallel q-q_i\parallel \ge +r_i+r_j-R_i^g+R_j^g\right\}$. Thus the boundary $\partial H_{\mathit{ij}}$ is one branch of a hyperbola with foci located at $q_i$ and $q_i$ and semi-major axis $a_{\mathit{ij}}=\frac{r_i+r_j-R_i^g+R_j^g}{2}$. Since the quantity $a_{\mathit{ij}}$ may be either positive or negative, $\partial H_{\mathit{ij}}$ may correspond to the ‘East’ or ‘West’ branch of the hyperbola, which results in the region $H_{\mathit{ij}}$ being convex or non-convex respectively.

We define the r-limited AWGV cell of agent $i$ as $G_i^R=G_i\cap S_i^g$. We now define the coverage objective as

$$\mathcal{H}=\sum _{i\in I_n}\underset{G_i^R}{\int }\varphi \left(q\right)\mathit{dq},$$E14

which is the area of the region that is guaranteed to be closest to and at the same time sensed by each agent. Since $\mathcal{H}$ is a sum of integrals over r-limited AWGV cells and since an agent can compute its own AWGV cell using information just from the agents in $N_i$, the computation of $\mathcal{H}$ is distributed.

2.3.3. Control law formulation

Since the computation of the coverage objective $\mathcal{H}$ is distributed due to the AWGV partitioning, what is left is the derivation of a distributed control law for its maximization.

Theorem 2.2. For a team of mobile ground agents with kinematics (1), sensing performance (2), positioning uncertainty (9) and using the AWGV partitioning (13), the control scheme

$$u_i={\alpha }_i\underset{\partial G_i^R\cap \partial S_i^g}{\int }{n}_i\varphi \left(q\right)\mathrm{d}q+{\alpha }_i\sum _{j\in N_i}\left[\underset{\partial G_i^R\cap \partial H_{\mathit{ij}}}{\int }{\mu }_i^i{n}_i\varphi \left(q\right)\mathrm{d}q+\underset{\partial G_j^R\cap \partial H_{\mathit{ji}}}{\int }{\mu }_j^i{n}_j\varphi \left(q\right)\mathrm{d}q\right]$$E15

where ${\alpha }_i$ is a positive constant, $n_i$ the outward unit normal vector on $\partial G_i^R$, leads the agent to trajectories that result in monotonic increase of the coverage objective (14).

Proof. We start by evaluating the time derivative of the objective using the agent dynamics (1) as in the proof of Theorem 2.1 and by selecting the control law $u_i={\alpha }_i\frac{\partial \mathcal{H}}{\partial q_i},{\alpha }_i>0$, we can guarantee monotonic increase of the coverage objective.

The partial derivative $\frac{\partial \mathcal{H}}{\partial q_i}$ is evaluated as follows

$$\frac{\partial \mathcal{H}}{\partial q_i}=\frac{\partial }{\partial q_i}\sum _{i\in I_n}\underset{G_i^R}{\int }\varphi \left(q\right)\mathrm{d}q=\frac{\partial }{\partial q_i}\underset{G_i^R}{\int }\varphi \left(q\right)\mathrm{d}q+\sum _{j\ne i}\frac{\partial }{\partial q_i}\underset{G_j^R}{\int }\varphi \left(q\right)\mathrm{d}q.$$

Since only the cells of additively weighted Delaunay neighbors of agent $i$ are affected by its movement and $\frac{\partial \varphi \left(q\right)}{\partial q_i}=0$, the previous equation becomes

$$\frac{\partial \mathcal{H}}{\partial q_i}=\underset{\partial G_i^R}{\int }{\mu }_i^i{n}_i\varphi \left(q\right)\mathrm{d}q+\sum _{j\in N_i}\underset{\partial G_j^R}{\int }{\mu }_j^i{n}_j\varphi \left(q\right)\mathrm{d}q$$

where ${\mu }_j^i$ is the Jacobian matrix

$${\mu }_j^i=\frac{\partial q}{\partial q_i},q\in \partial G_j^R$$

and $n_i$ is the outward unit normal vector on $\partial G_i^R$. The boundary $\partial G_i^R$ can be decomposed into three disjoint sets as follows

$$\partial G_i^R=\left(\partial G_i^R\cap \partial S_i^g\right)\cup \left(\partial G_i^R\cap \mathrm{\partial \Omega }\right)\cup \left[\bigcup _{j\in N_i}\left(\partial G_i^R\cap \partial H_{\mathit{ij}}\right)\right],$$E16

where $\partial G_i^R\cap \partial S_i^g$ denotes part of the r-limited cell’s boundary that is also part of the boundary of the agent’s sensing disk, $\partial G_i^R\cap \mathrm{\partial \Omega }$ denotes the common boundary between the r-limited cell and the region, while $\partial G_i^R\cap \partial H_{\mathit{ij}}$ denotes parts of the boundary that consist of hyperbolic arcs induced by some neighboring agent $j$. This decomposition is presented in Figure 3 where $\partial G_i^R\cap \partial S_i^g$, $\partial G_i^R\cap \mathrm{\partial \Omega }$, $\partial G_i^R\cap \partial H_{\mathit{ij}}$ and $\partial G_j^R\cap \partial H_{\mathit{ji}}$ are shown in solid green, red, blue and purple lines respectively.

Figure 3.

Decomposition of $\partial G_i^R$ into disjoint sets and corresponding normal vectors.

Since the region $\mathrm{\Omega }$ is assumed to be static, it holds that ${\mu }_i^i=0,\forall q\in \partial G_i^R\cap \partial \Omega$. In addition, since $q\in \partial G_i^R\cap \partial S_i^g$ are points on a circle with center $q_i$, it holds that ${\mu }_i^i={\mathbb{I}}_2,\forall q\in \partial G_i^R\cap \partial S_i^g$. Finally, $G_j^R$ is only affected by the movement of agent $i$ at the induced hyperbolic arc $\partial G_j^R\cap \partial H_{\mathit{ji}}$ and by grouping the hyperbolic arcs in pairs and multiplying by ${\alpha }_i$ we get (15). □

2.3.4. Constraining agents inside the region

When the control law (15) is used, there can be cases where the positioning uncertainty regions of some agent does not remain entirely inside $\mathrm{\Omega }$, i.e. it is possible that $U_i\cap \mathrm{\Omega }\ne U_i$ for some agent $i$. This has the implication that the control law (15) may lead some agent $i$ outside the region $\mathrm{\Omega }$, given the fact that an agent may reside anywhere within its positioning uncertainty region $U_i$.

In order to avoid such a situation, a subset ${\mathrm{\Omega }}_i^s \subseteq \mathrm{\Omega }$ is used instead, instead of the region $\mathrm{\Omega }$. This subset ${\mathrm{\Omega }}_i^s$ is in the general case different among agents due to their differing measures of positioning uncertainty $r_i$. This subset of $\mathrm{\Omega }$ is computed as the Minkowski difference of $\mathrm{\Omega }$ with the disk $U_i^0\left(r_i\right)=\left\{q\in \mathrm{\Omega }:\parallel q\parallel \le r_i\right\}$ which is ${\mathrm{\Omega }}_i^s=\left\{q\in \mathrm{\Omega }:q+U_i^0 \subseteq \mathrm{\Omega }\right\},i\in I_n$.

By using this subset ${\mathrm{\Omega }}_i^s$, constraining agents inside $\mathrm{\Omega }$ is simpler, since this is equivalent to constraining each agent’s reported position $q_i$ inside its respective subset region ${\mathrm{\Omega }}_i^s$. This is achieved by stopping an agent if its reported position $q_i$ is located on the boundary of ${\mathrm{\Omega }}_i^s$ and simultaneously its current control input leads the agent toward the exterior of ${\mathrm{\Omega }}_i^s$. Thus the control law being implemented is

$${\tilde{u}}_i=\left\{\begin{array}{ll}0& \text{if}{q}_i\in \partial {\mathrm{\Omega }}_i^s\wedge q_i+\epsilon u_i \notin {\mathrm{\Omega }}_i^s\\ u_i& \text{otherwise}\end{array}\right.$$E17

where $\epsilon$ is an infinitesimally small positive constant.

2.3.5. Simulation study II

An indicative simulation is presented in this section. This simulation is identical to the one presented in Section 2.2.4 with the only difference being the addition of positioning uncertainty to the agents.

The initial and final agent configurations are shown in Figure 4a and c respectively where the agent positioning uncertainty regions are shown as black circles, the boundaries of their sensing disks are shown as dashed black lines, the boundaries of their cells are marked by solid black lines while their interiors are filled in color. The agent trajectories are shown in Figure 4b with the initial positions marked by dots and the final positions by circles. It is observed that the agents successfully deploy inside the region, increasing the covered area in the process. In order to provide a more objective measure of the agents’ performance, the two metrics described in Section 2.2.4 are used which in the case of uncertainty positioning are more formally defined as

$${\mathcal{H}}^r=100\frac{\mathcal{H}}{{\displaystyle \underset{\mathrm{\Omega }}{\int }}\varphi \left(q\right)\mathrm{d}q},{\mathcal{H}}^a=100\frac{\mathcal{H}}{\sum _{i\in I_n}\underset{S_i^g}{\int }\mathrm{d}q}.$$

Figure 4.

Simulation study II: (a) initial configuration, (b) agent trajectories, (c) final configuration and (d) evolution of the coverage objective over time.

Figure 4d shows ${\mathcal{H}}^a$ in solid blue and ${\mathcal{H}}^r$ in dashed red with their final values being 94.0 and 70.0% respectively. In this simulation we observe that although ${\mathcal{H}}^a$ reaches a high value, this is not the case with ${\mathcal{H}}^r$. The first reason for this result is the fact that the computation of $\mathcal{H}$ is based on the agents’ guaranteed sensing patterns $S_i^g$, which by definition are lower in area than their respective sensing patterns $S_i$. Moreover, due to the definition of $\mathcal{H}$ being conservative, only the area of the r-limited cells $G_i^R$ counts toward the value of $\mathcal{H}$, thus parts of the neutral region $\mathcal{O}$ that are covered by the agents do not contribute to $\mathcal{H}$. Consequently, in the case of the AWGV partitioning (13), coverage objective (14) and control law (15), it is expected for ${\mathcal{H}}^r$ to achieve a lower value.

2.4. Heterogeneous agents with anisotropic sensing

Although the omnidirectional sensors examined in the previous two sections can significantly simplify the problem formulation and solution, they are usually inadequate for precise modeling of real-life sensors. For this reason there have been several differing approaches to area coverage using agents with anisotropic sensing patterns [37, 38, 39, 40]. In this section we will follow the methodology presented in [41] which is a distributed optimization technique resulting in a gradient-based control law.

2.4.1. Problem statement

A team of $n$ mobile ground agents is deployed inside the region of interest $\mathrm{\Omega }$. Given the anisotropic nature of the sensing patterns examined in this section, the mobile agents should be able to change their orientation as well as move around inside the region of interest. A realistic model for a mobile agent with the ability to rotate is that of the differential drive robot whose kinematic model is

$$\begin{array}{l}{\dot{q}}_i=\left[\begin{array}{c}cos{\theta }_i\\ sin{\theta }_i\end{array}\right]\frac{{\rho }_i}{2}\left({\mathrm{\Omega }}_i^R+{\mathrm{\Omega }}_i^L\right),q_i\in \mathrm{\Omega },\\ {\dot{\theta }}_i=\frac{{\rho }_i}{l_i}\left({\mathrm{\Omega }}_i^R-{\mathrm{\Omega }}_i^L\right),{\theta }_i\in \left[-\pi ,\pi \right],\end{array}$$

where ${\mathrm{\Omega }}_i^R,{\mathrm{\Omega }}_i^L$ are the rotational velocities of the right and left wheels, respectively, ${\rho }_i$ is the wheel radius, and $l_i$ is the length of the wheel axis. In this chapter however a simpler single integrator kinematic model is used for the agents. Each agent $i\in I_n$ is approximated by a point mass located at $q_i\in \mathrm{\Omega }$ with orientation ${\theta }_i$ which is governed by the kinematic model described by

$${\dot{q}}_i=u_i,q\in \mathrm{\Omega },u_i\in {\mathbb{R}}^2,$$E18

$${\dot{\theta }}_i={\omega }_i,\theta ,{\omega }_i\in \mathbb{R},$$E19

where ${\omega }_i$ is the rotational velocity control input of the agent. This single integrator model simplifies the derivation of the control law, although the control law can be extended for differential drive robots as well.

We define the base sensing pattern $S_i^b$ of agent $i$ as the region sensed by the agent when $q_i={\left[0,0\right]}^T$ and ${\theta }_i=0$. The only requirements with regards to the base sensing pattern are that $q_i\in \mathit{Int}\left(S_i^b\right)$ and that its boundary $\partial S_i^b$ can be described by a set of parametric equations. Let the radius $R_i$ of a base sensing pattern be defined as $R_i\left(S_i^b\right)={\displaystyle \underset{q\in \partial S_i^b}{max}}\parallel q\parallel$. This is the maximum distance from the origin, which is also the base sensing pattern’s center of rotation, to its boundary.

The sensing pattern of agent $i$ as a function of its position $q_i$ and orientation ${\theta }_i$, can be computed by rotating around the origin and translating its base sensing pattern as follows

$$S_i\left(q_i,{\theta }_i\right)=q_i+\mathbf{R}\left({\theta }_i\right)S_i^b.$$E20

By allowing a different base sensing pattern for each agent, teams of heterogeneous agents can be effectively utilized.

Since the goal of the mobile agent team is the maximization of the covered area using their sensors, while also taking into account the space density function, we define the coverage objective as in (3). The control objective is the design of a distributed control law for the mobile agents in order to guarantee monotonic increase of the coverage objective $\mathcal{H}$ over time.

2.4.2. Space partitioning

The first step in designing a distributed control law is finding a method to distribute the computation of the coverage objective $\mathcal{H}$. Due to the agents’ anisotropic sensing patterns, the partitioning scheme employed in this case is highly different from Voronoi-like partitioning schemes. Instead of partitioning the whole region $\mathrm{\Omega }$ based on the agents’ positions, only the sensed region ${\displaystyle \underset{i\in I_n}{\cup }}{S}_i$ is partitioned based on the agents’ sensing patterns. Each agent is assigned the part of $\mathrm{\Omega }$ that only itself is able to sense, with parts being sensed by multiple or no agents being left unassigned.

Given a planar region $\mathrm{\Omega }$ and a set of sensing patterns $S=\left\{S_1,\dots ,S_n\right\}$, each agent $i$ is assigned a cell $W_i$ as follows

$$W_i\left(\mathrm{\Omega },S\right)=\left(\mathrm{\Omega }\cap S_i\right)\setminus \bigcup _{j\in I_n\setminus i}{S}_j,i{\in }_{I}n.$$

The part of $\mathrm{\Omega }$ sensed by multiple agents is left unassigned but still contributes toward the coverage objective $\mathcal{H}$. This part is called the common region and is computed as follows

$$W_c\left(\mathrm{\Omega },S\right)=\mathrm{\Omega }\cap \bigcup _{i\in I_n}\left(S_i\setminus W_i\right).$$E21

Having defined the cells and the common region, it holds that $\bigcup _{i\in I_n}{S}_i=\bigcup _{i\in I_n}{W}_i\cup W_c \subseteq \mathrm{\Omega }$ .

We can define the neighbors of agent $i$ as those agents that affect the computation of its cell. Since the computation of the cells relies entirely on the agents’ sensing patterns, the neighbors can be defined as

$$N_i=\left\{j\in I_n\setminus i:S_i\cap S_j\ne \varnothing \right\}.$$E22

Moreover, if the maximum base sensing radius $R^{\max }={\displaystyle \underset{i\in I_n}{max}} R_i$ is known by all agents, and if each agent is able to communicate with all others within a radius

$$C_i=R_i+R^{\max },$$E23

then it is guaranteed it will be able to communicate with all of its neighbors $N_i$. By using the neighbor definition, the proposed partitioning scheme can be computed in a distributed manner as follows

$$W_i\left(\mathrm{\Omega },S\right)=\left(\mathrm{\Omega }\cap S_i\right)\setminus \bigcup _{j\in N_i\setminus i}{S}_j,i\in I_n.$$E24

Remark 2.2. The partitioning scheme (24) may result in the cell of some agent being empty or consisting of multiple disjoint regions. It should be noted however that such cases are handled successfully by the control law presented in Section 2.4.3.

Thus by utilizing the aforementioned partitioning scheme, the coverage objective $\mathcal{H}$ can be computed as follows

$$\mathrm{\mathscr{H}}=\sum _{i\in I_n}\underset{W_i}{\int }\varphi \left(q\right)\mathit{dq}+\underset{W_c}{\int }\varphi \left(q\right)\mathit{dq}.$$E25

Since $\mathcal{H}$ can be written as a sum of integrals over the assigned cells and since an agent can compute its own cell using information just from its neighbors, the computation of $\mathcal{H}$ is distributed.

2.4.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective $\mathcal{H}$, what is left is the derivation of a distributed control law for its maximization.

Theorem 2.3. For a team of mobile ground agents with kinematics (18, 19), sensing performance (20) and using the partitioning (24), the control scheme

$$u_i={\alpha }_{i,u}\underset{\partial W_i\cap \partial S_i}{\int }{n}_i \varphi \left(q\right)\mathrm{d}q,$$E26

$${\omega }_i={\alpha }_{i,\omega }\underset{\partial W_i\cap \partial S_i}{\int }{n}_i\mathit{R}\left(\frac{\pi }{2}\right)\left(q-q_i\right)\varphi \left(q\right)\mathrm{d}q,$$E27

where ${\alpha }_{i,u},{\alpha }_{i,\omega }$ are positive constants and $n_i$ is the outward unit normal vector on $\partial W_i$, leading the agent to trajectories that result in monotonic increase of the coverage objective (25).

Proof. We start by evaluating the time derivative of the objective using the chain rule and the agent dynamics (18, 19)

$$\frac{\partial \mathcal{H}}{\partial t}=\sum _{i\in I_n}\frac{\partial \mathcal{H}}{\partial q_i}\frac{\partial q_i}{\partial t}+\frac{\partial \mathcal{H}}{\partial {\theta }_i}\frac{\partial {\theta }_i}{\partial t}=\sum _{i\in I_n}\frac{\partial \mathcal{H}}{\partial q_i}{\dot{q}}_i+\frac{\partial \mathcal{H}}{\partial {\theta }_i}{\dot{\theta }}_i=\sum _{i\in I_n}\frac{\partial \mathcal{H}}{\partial q_i}{u}_i+\frac{\partial \mathcal{H}}{\partial {\theta }_i}{\omega }_i.$$

By selecting the control law

$$u_i={\alpha }_{i,u}\frac{\partial \mathcal{H}}{\partial q_i},{\omega }_i={\alpha }_{i,\omega }\frac{\partial \mathcal{H}}{\partial {\theta }_i},{\alpha }_{i,u},{\alpha }_{i,\omega }>0,$$

we can guarantee monotonic increase of the coverage objective.

The partial derivative $\frac{\partial \mathcal{H}}{\partial q_i}$ is evaluated as follows

$$\frac{\partial \mathcal{H}}{\partial q_i}=\frac{\partial }{\partial q_i}\underset{W_i}{\int }\varphi \left(q\right)\mathrm{d}q+\sum _{j\ne i}\frac{\partial }{\partial q_i}\underset{W_j}{\int }\varphi \left(q\right)\mathrm{d}q+\frac{\partial }{\partial q_i}\underset{W_c}{\int }\varphi \left(q\right)\mathrm{d}q.$$

Due to the partitioning scheme (24) only the common region $W_c$ is affected by the movement of agent $i$ and since $\frac{\partial \varphi \left(q\right)}{\partial q_i}=0$, by using the Leibniz integral rule [32], the previous equation becomes

$$\frac{\partial \mathcal{H}}{\partial q_i}=\underset{\partial W_i}{\int }{\upsilon }_i^i{n}_i\varphi \left(q\right)\mathrm{d}q+\underset{\partial W_c}{\int }{\upsilon }_c^i{n}_c\varphi \left(q\right)\mathrm{d}q$$

where ${\upsilon }_j^i$ is the Jacobian matrix

$${\upsilon }_j^i=\frac{\partial q}{\partial q_i},q\in \partial W_j$$

and $n_i$ is the outward unit normal vector on $\partial W_i$. The boundary $\partial W_i$ can be decomposed into three disjoint sets as follows

$$\partial W_i=\left(\partial W_i\cap \partial S_i\right)\cup \left(\partial W_i\cap \mathrm{\partial \Omega }\right)\cup \left(\partial W_i\cap \partial W_c\right),$$E28

where $\partial W_i\cap \partial S_i$ denotes part of the cell’s boundary that is also part of the boundary of the agent’s sensing disk, $\partial W_i\cap \mathrm{\partial \Omega }$ denotes the common boundary between the cell and the region, while $\partial W_i\cap \partial W_c$ denotes the common boundary of the cell and the common region. This decomposition is presented in Figure 5 where $\partial W_i\cap \partial S_i$, $\partial W_i\cap \mathrm{\partial \Omega }$ and $\partial W_i\cap \partial W_c$ are shown in solid green, red and blue lines respectively.

Figure 5.

Decomposition of $\partial W_i$ into disjoint sets and corresponding normal vectors.

Since the region $\mathrm{\Omega }$ is assumed to be static, it holds that ${\upsilon }_i^i=0,\forall q\in \partial W_i\cap \partial \Omega$. In addition, from Eq. (20) we get that ${\upsilon }_i^i={\mathbb{I}}_2,\forall q\in \partial W_i\cap \partial S_i$. Finally, on all the common boundaries $\partial W_j\cap \partial W_c,j\in I_n$ it holds that ${\upsilon }_i^j={\upsilon }_i^c$ and $n_j=-n_c$, as shown in Figure 5, leaving only an integral over $\partial W_i\cap \partial S_i$. By multiplying with ${\alpha }_{i,u}$ we get (26). The same procedure is used for the derivation of the rotational part of the control law (27). □

2.4.4. Simulation study III

An indicative simulation is presented in this section. The region $\mathrm{\Omega }$, the space density function $\varphi \left(q\right)$ and the agent initial positions are the same as in the simulation presented in Section 2.2.4. In this simulation however the agents are equipped with heterogeneous sensors with elliptical sensing patterns.

The initial and final agent configurations are shown in Figure 6a and c respectively where the agent positions are marked by black dots, the agent orientations are marked by black arrows, the boundaries of their sensing disks are shown as dashed black lines, the boundaries of their cells are marked by solid black lines while their interiors are filled in color. The agent trajectories are shown in Figure 6b with the initial positions marked by dots and the final positions by circles. It is observed that the agents successfully deploy inside the region, increasing the covered area in the process. In order to provide a more objective measure of the agents’ performance, the two metrics defined in Eq. (8) are used. Figure 6d shows ${\mathcal{H}}^a$ in solid blue and ${\mathcal{H}}^r$ in dashed red with their final values being 91.3 and 93.5% respectively. This indicates that the final configuration results in both high coverage of $\mathrm{\Omega }$ and efficient use of the agents sensors.

Figure 6.

Simulation study III: (a) initial configuration, (b) agent trajectories, (c) final configuration and (d) evolution of the coverage objective over time.

2.4.5. Simulation study IV

This simulation study serves to highlight the need for taking into account the agents’ anisotropic sensing patterns instead of approximating them with circular ones. To that end, Simulation Study III was repeated by approximating the agents’ elliptical sensing patterns with their maximal inscribed circles. The initial agent configuration, agent trajectories and final agent configuration are shown in Figure 7a, b and c respectively. It is observed that the agent’s performance is decreased significantly when using this underapproximation of their sensing patterns. In order to provide a more objective measure of the agents’ performance, the two metrics defined in Eq. (8) are used. Figure 7d shows ${\mathcal{H}}^a$ in solid blue and ${\mathcal{H}}^r$ in dashed red with their final values being 100% and 35.2% respectively, indicating a 62.4$\%$ decrease in the coverage of $\mathrm{\Omega }$ compared to Simulation Study III.

Figure 7.

Simulation study IV: (a) initial configuration, (b) agent trajectories, (c) final configuration and (d) evolution of the coverage objective over time.

2.5. Experimental implementation

An experimental implementation of a simplified version of one of the previously examined control schemes is briefly presented in this section. This experimental study first appeared and is presented in greater detail in [42]. The experiment consisted of three differential-drive robots, a visual pose tracking system using fiducial markers and a computer communicating with the robots and pose tracking system via a WiFi router. The methodology presented in Section 2.3 was used in order to take into account the positioning uncertainty of the pose tracking system. The experimental results are compared with a simulation using the same initial conditions.

2.5.1. Experimental setup

The robots used in the experiment were the differential-drive AmigoBots by Omron Adept MobileRobots. The robots are $33\mathrm{cm}\times 28\mathrm{cm}\times 15\mathrm{cm}$ in size, weigh $3.6\mathit{kg}$ and are able to carry a payload of up to $1\mathrm{kg}$. Their maximum linear and rotational velocities are $v^{\max }=1\mathrm{m}/\mathrm{s}$ and ${\omega }^{\max }={100}^{\mathrm{o}}/\mathrm{s}$. Although these robots are equipped with encoders measuring $\mathrm{39,000}\text{ticks}/\text{revolution}$ which can be used for estimating their pose, an external pose tracking system was used instead due to the encoders’ drifting error. Since the AmigoBots lack any omnidirectional sensors, for the sake of the control law it was assumed that they were equipped with sensors with a common sensing radius of $R=0.3\mathrm{m}$.

The external pose tracking system consists of a USB camera and an ODROID-XU4 computer. Pose tracking is achieved by attaching a fiducial marker on top of each robot and using the ArUco [43] library to estimate the pose of these markers. As is the case with all positioning systems, ArUco has a certain degree of uncertainty in its pose estimations. In order to get an estimate of this uncertainty, a fiducial marked was placed on the vertices and the centroid of the region $\mathrm{\Omega }$ resulting in a maximum error of $0.032\mathrm{m}$, which was used as the measure of positioning uncertainty $r$ for all robots.

The control scheme was implemented as a loop in the main computer with an iteration period of $T_s=0.1$ seconds. At each iteration, a simplified version of the control law (15) is computed for each agent, and from that, a target point $q_i^t$ is derived for each agent. Then a feedback controller is used in order to lead each robot to each respective target point. Once all robots are within a predefined distance $d^t=0.02\mathrm{m}$ of their respective target points, new target points are computed from the robots’ current positions. The feedback control law used for each robot was

$$v_i=min\left(\frac{\parallel q_i^t-q_i\parallel }{T_s},v^{\max }\right)cos\left(d{\theta }_i\right),{\omega }_i=min\left(\frac{\mid d{\theta }_i\mid }{T_s},{\omega }^{\max }\right)sin\left(d{\theta }_i\right),$$

where $q_i$ and ${\theta }_i$ are the robot’s current position and orientation, $v_i$ and ${\omega }_i$ the robots linear and rotational velocity control inputs respectively and $d{\theta }_i=\measuredangle \left(q_i^t-q_i\right)-{\theta }_i$.

2.5.2. Experimental results

The robots’ initial configuration, which is common between the experiment and simulation is shown in Figure 8a. The final configurations of the experiment and the simulation are shown in Figure 8c and d, respectively. The boundaries of the agents’ positioning uncertainty regions are shown as black circles, the boundaries of their sensing disks are shown in dashed black line and the boundaries of their cells are marked by solid black lines while their interiors are filled in color. Some photographs of the robots’ initial and final configurations are presented in Figure 9a and b respectively where the ArUco fiducial markers can be seen. In both the experiment and the simulation it is observed from the robots’ final configurations that their guaranteed sensed regions are completely contained within their respective AWGV cells, i.e. $S_i^g\subset G_i,\forall i\in I_n$, which is a globally optimal configuration. The robots’ trajectories are depicted in Figure 8b in blue for the experiment and in red for the simulation, with the initial and final positions marked by dots and circles respectively. The simulation trajectories are smooth but the experimental trajectories have many turns due to the robots moving to target points. The robots’ final positions have an error of $9.27\%$ the diameter of $\mathrm{\Omega }$ between the experiment and the simulation. This large error is attributed to the difference between the implemented control laws as well as the existence of multiple global optima for this particular coverage setup. Figure shows the evolution of the metric ${\mathcal{H}}^a$ over time for the experiment in blue and the simulation in red where it is seen that it increased from $83.70$ to $98.95\%$ in the experiment. Although in the case of the experiment its increase was not monotonic, this is to be expected as the implemented control law differed from the theoretical one. The lower convergence speed is also attributed to this difference as well as the constraints on the robots’ translational and rotational velocities.

Figure 8.

Experiment: (a) initial configuration, (b) experimental (blue) and simulated (red) robot trajectories, (c) experiment final configuration and (d) simulation final configuration.

Figure 9.

Experiment: (a) initial configuration, (b) final configuration and (c) evolution of the coverage objective over time for the experiment and simulation.

3. Conclusions and future work

This chapter presented an overview of past and current work on area coverage problems. A strong theoretical background has been provided, along with indicative simulations results and an experimental implementation of one of the presented control schemes. The problem of multiagent area coverage still offers possibilities for original research. One possible extension would be the usage of more realistic sensor models, such as visual sensors. The usage of visual sensors can result in the incorporation of coverage quality metrics in the objective or in variable sensing patterns in the case of pan-tilt-zoom cameras. Another aspect of multirobot area coverage problem that has not been studied thoroughly yet is the development of communication systems and algorithms that allow the agents to exchange information in a distributed manner. Finally, implementations in actual robotic systems in order to solve practical problems are not yet common.

Conflict of interest

The authors declare no conflict of interest.