## 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.

### Keywords

- area coverage
- multiagent systems
- mobile robot systems
- distributed control
- cooperative control

## 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

while the

### 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

where

Each agent has been equipped with an omnidirectional sensor with limited sensing radius

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

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

#### 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

Given a planar region

The power diagram is a complete tessellation of

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

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

Since it holds that

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

For any two agents

Since

#### 2.2.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective

**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*

*where* *is a positive constant and* *is the outward unit normal vector on* *, 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

The partial derivative

Since only the cells of power-weighted Delaunay neighbors of agent

where

Since the region

Since

#### 2.2.4. Simulation study I

An indicative simulation is presented in this section. The region

respectively. The space density function was

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

Figure 2d shows

### 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

which is a circular disk that contains all possible positions of agent

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

which is the region that is guaranteed to be sensed by agent

#### 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

Contrary to the Voronoi diagram, the AWGV diagram is not a complete tessellation of the region

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

Since it holds that

The previous definition of the AWGV can be written as

We define the r-limited AWGV cell of agent

which is the area of the region that is guaranteed to be closest to and at the same time sensed by each agent. Since

#### 2.3.3. Control law formulation

Since the computation of the coverage objective

**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*

*where* *is a positive constant,* *the outward unit normal vector on* *, 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

The partial derivative

Since only the cells of additively weighted Delaunay neighbors of agent

where

and

where

Since the region

#### 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

In order to avoid such a situation, a subset

By using this subset

where

#### 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

Figure 4d shows

### 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

where

where

We define the base sensing pattern

The sensing pattern of agent

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

#### 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

Given a planar region

The part of

Having defined the cells and the common region, it holds that

We can define the neighbors of agent

Moreover, if the maximum base sensing radius

then it is guaranteed it will be able to communicate with all of its neighbors

**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

Since

#### 2.4.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective

**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*

*where* *are positive constants and* *is the outward unit normal vector on* *, 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)

By selecting the control law

we can guarantee monotonic increase of the coverage objective.

The partial derivative

Due to the partitioning scheme (24) only the common region

where

and

where

Since the region

#### 2.4.4. Simulation study III

An indicative simulation is presented in this section. The region

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

#### 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

### 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 *AmigoBot*s by *Omron Adept MobileRobots*. The robots are *AmigoBot*s 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

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

The control scheme was implemented as a loop in the main computer with an iteration period of

where

#### 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.

## 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.