Open access peer-reviewed chapter

Theoretical and Experimental Collaborative Area Coverage Schemes Using Mobile Agents

By Sotiris Papatheodorou and Anthony Tzes

Submitted: January 26th 2018Reviewed: May 18th 2018Published: November 5th 2018

DOI: 10.5772/intechopen.78940

Downloaded: 155

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 ΩR2to be covered by the mobile agents and a space density function ϕ:ΩR+. The space density function is used to encode any a priori information regarding the importance of points in Ω, for example the likelihood that an event may occur at a given point. The boundary of a set Sis denoted Sand its interior is denoted IntS. The set 1nis denoted In. The indicator function 1Sqfor a set Sand the 2×2rotation matrix Rθare respectively

1Sq=1ifqS0ifqS,Rθ=cosθsinθsinθcosθ,

while the 2×2identity matrix is denoted I2.

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 nmobile ground agents is deployed inside the region of interest Ω. Each agent iInis approximated by a point mass located at qiΩwhich is governed by the following kinematic model

q̇i=ui,qΩ,uiR2E1

where uiis the velocity control input of the agent.

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

SiqiRi=qΩ:qqiRi.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

H=ΩmaxiIn1Siqϕqdq.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 Hover 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 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 Ωand a set of disks S=S1Snwith centers Q=q1qnand radii R=R1Rn, the power diagram assigns a convex cell PiΩto each disk Si

PiΩS=qΩ:qqi2Ri2qqj2Rj2jIni,iIn.

The power diagram is a complete tessellation of Ω, thus it holds that

Ω=iInPi,IntPiIntPj=,ij.

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 Piof point qi, only the power-weighted Delaunay neighbors Niof point qineed to be considered. The power-weighted Delaunay neighbors of agent ihave the property that

Ni=jIni:PiPj,E4

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

PiΩQ=qΩ:qqi2Ri2qqj2Rj2jNi,iIn.E5

Since it holds that NiIn, each agent irequires information only from its power-weighted Delaunay neighbors in order to compute its own power cell Pi, thus rendering the computation of the power diagram distributed.

Remark 2.1. When the agents’ sensing radii are equal, i.e., Ri=Rj,i,j, the power diagram converges to the Voronoi diagram. In that case the computation of the cell of agent irequires 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 iand jwith SiSjit holds that SiPiPjSjand SjPjPiSidue 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 ias PiR=PiSi. Thus by utilizing the power diagram, the coverage objective Hcan be computed as follows

H=iInPiRϕqdq.E6

Since Hcan 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 His distributed.

2.2.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective 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

ui=αiPiRSiniϕqdq,E7

where αiis a positive constant and niis the outward unit normal vector on PiR, 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 Ht=iInHqiqit=iInHqiq̇i=iInHqiui.By selecting the control law ui=αiHqi,αi>0, we can guarantee monotonic increase of the coverage objective.

The partial derivative Hqiis evaluated as follows

Hqi=qiiInPiRϕqdq=qiPiRϕqdq+jiqiPjRϕqdq.

Since only the cells of power-weighted Delaunay neighbors of agent iare affected by its movement and ϕqqi=0, by using the Leibniz integral rule [32], the previous equation becomes

Hqi=PiRυiiniϕqdq+jNiPjRυjinjϕqdq

where υjiis the Jacobian matrix υji=qqi,qPjRand niis the outward unit normal vector on PiR. The boundary PiRcan be decomposed into three disjoint sets PiR=PiRSiPiR∂ΩjNiPiRPjR,where PiRSidenotes part of the r-limited cell’s boundary that is also part of the boundary of the agent’s sensing disk, PiR∂Ωdenotes the common boundary between the r-limited cell and the region, while PiRPjRdenotes the common boundary with the r-limited cell of some neighboring agent j. This decomposition is presented in Figure 1 where PiRSi, PiR∂Ωand PiRPjRare shown in solid green, red, and blue lines, respectively.

Figure 1.

Decomposition of ∂PiR into disjoint sets and corresponding normal vectors.

Since the region Ωis assumed to be static, it holds that υii=0,qPiR∂Ω. In addition, since qPiRSiare points on a circle with center qi, it holds that υii=I2,qPiRSi. Finally, PjRis only affected by the movement of agent iat the common boundary PiRPjR, resulting in the expression

Hqi=PiRSiniϕqdq+jNiPiRPjRυiiniϕqdq+jNiPiRPjRυjinjϕqdq.

Since υii=υjiand ni=njon the common boundary PiRPjR, as shown in Figure 1, the two sums in the previous expression cancel out and by multiplying it with αiwe get (7). □

2.2.4. Simulation study I

An indicative simulation is presented in this section. The region Ωis chosen as the convex polygon defined by the vertices with xand ycoordinates

Ωx=0.50.50.450.40.460.50.480.340.05,Ωy=0.430.20.30.50.440.10.370.470.5

respectively. The space density function was ϕq=1,qΩ. 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 Hr, is the value of the coverage objective Has a percentage of the objective over the whole region which in the case where ϕq=1,qΩit is equal to the area of Ω. This metric indicates to what extent the agents cover the region Ω, with high values of Hrcorresponding to high coverage over Ω. The second metric, denoted Ha, is the value of the coverage objective Has a percentage of the agents’ maximum possible covered area which is only meaningful in the case where ϕq=1,qΩ. This metric indicates to what extent the agents’ sensors are utilized, with high values of Haindicating that the agents’ sensors are utilized close to their full capabilities. Low values of Hasimultaneously with high values of Hrindicate an overabundance of agents given the size of the current region Ω. The two metrics are more formally defined as

Hr=100HΩϕqdq,Ha=100HiInSidq.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 Hain solid blue and Hrin 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 qiis the agent’s position as reported by the localization system, while riis a known upper bound on the localization error. Thus we define the positioning uncertainty region Uias follows

Uiqiri=qR2:qqi ri,E9

which is a circular disk that contains all possible positions of agent igiven its reported position qiand positioning uncertainty upper bound ri.

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

SigqiriRi=qUiSiqRi,E10

which is the region that is guaranteed to be sensed by agent igiven all of its possible positions within its positioning uncertainty region. Given the fact that both Siand Uiare disks, the above expression can be simplified into

SigqiriRi=qR2:qqi Rig=Riri.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 Ω, a set of uncertain regions U=U1Unand a set of weights Rg=R1gRng, the AWGV diagram assigns a convex cell Gi  Ωto each region-weight pair UiRigas follows

GiΩURg=qΩ:maxqUiqqiRig  minqUjqqjRjgjIni,iIn.

Contrary to the Voronoi diagram, the AWGV diagram is not a complete tessellation of the region Ωsince a part of Ωis left unassigned. This part is called the neutral region Oand it holds that

Ω=OiInGi.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 Giof the region-weight pair UiRig, only the additively weighted Delaunay neighbors Niof UiRigneed to be considered. By using the previous definition, the Voronoi diagram can be formulated as

GiΩURg=qΩ:maxqUiqqiRig  minqUjqqjRjgjNii,iIn.E13

Since it holds that NiIn, each agent irequires information only from its additively weighted Delaunay neighbors in order to compute its own AWGV cell Gi, thus rendering the computation of the AWGV diagram distributed.

The previous definition of the AWGV can be written as Gi=jNiHij,iIn,where Hij=qΩ:qqjqqi+ri+rjRig+Rjg. Thus the boundary Hijis one branch of a hyperbola with foci located at qiand qiand semi-major axis aij=ri+rjRig+Rjg2. Since the quantity aijmay be either positive or negative, Hijmay correspond to the ‘East’ or ‘West’ branch of the hyperbola, which results in the region Hijbeing convex or non-convex respectively.

We define the r-limited AWGV cell of agent ias GiR=GiSig. We now define the coverage objective as

H=iInGiRϕqdq,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 His 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 Ni, the computation of His distributed.

2.3.3. Control law formulation

Since the computation of the coverage objective His 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

ui=αiGiRSigniϕqdq+αijNiGiRHijμiiniϕqdq+GjRHjiμjinjϕqdqE15

where αiis a positive constant, nithe outward unit normal vector on GiR, 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 ui=αiHqi,αi>0, we can guarantee monotonic increase of the coverage objective.

The partial derivative Hqiis evaluated as follows

Hqi=qiiInGiRϕqdq=qiGiRϕqdq+jiqiGjRϕqdq.

Since only the cells of additively weighted Delaunay neighbors of agent iare affected by its movement and ϕqqi=0, the previous equation becomes

Hqi=GiRμiiniϕqdq+jNiGjRμjinjϕqdq

where μjiis the Jacobian matrix

μji=qqi,qGjR

and niis the outward unit normal vector on GiR. The boundary GiRcan be decomposed into three disjoint sets as follows

GiR=GiRSigGiR∂ΩjNiGiRHij,E16

where GiRSigdenotes part of the r-limited cell’s boundary that is also part of the boundary of the agent’s sensing disk, GiR∂Ωdenotes the common boundary between the r-limited cell and the region, while GiRHijdenotes parts of the boundary that consist of hyperbolic arcs induced by some neighboring agent j. This decomposition is presented in Figure 3 where GiRSig, GiR∂Ω, GiRHijand GjRHjiare shown in solid green, red, blue and purple lines respectively.

Figure 3.

Decomposition of ∂GiR into disjoint sets and corresponding normal vectors.

Since the region Ωis assumed to be static, it holds that μii=0,qGiRΩ. In addition, since qGiRSigare points on a circle with center qi, it holds that μii=I2,qGiRSig. Finally, GjRis only affected by the movement of agent iat the induced hyperbolic arc GjRHjiand by grouping the hyperbolic arcs in pairs and multiplying by αiwe 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 Ω, i.e. it is possible that UiΩUifor some agent i. This has the implication that the control law (15) may lead some agent ioutside the region Ω, given the fact that an agent may reside anywhere within its positioning uncertainty region Ui.

In order to avoid such a situation, a subset Ωis  Ωis used instead, instead of the region Ω. This subset Ωisis in the general case different among agents due to their differing measures of positioning uncertainty ri. This subset of Ωis computed as the Minkowski difference of Ωwith the disk Ui0ri=qΩ:q  riwhich is Ωis=qΩq+Ui0  Ω,iIn.

By using this subset Ωis, constraining agents inside Ωis simpler, since this is equivalent to constraining each agent’s reported position qiinside its respective subset region Ωis. This is achieved by stopping an agent if its reported position qiis located on the boundary of Ωisand simultaneously its current control input leads the agent toward the exterior of Ωis. Thus the control law being implemented is

u˜i=0ifqiΩisqi+εui  ΩisuiotherwiseE17

where ε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

Hr=100HΩϕqdq,Ha=100HiInSigdq.

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 Hain solid blue and Hrin dashed red with their final values being 94.0 and 70.0% respectively. In this simulation we observe that although Hareaches a high value, this is not the case with Hr. The first reason for this result is the fact that the computation of His based on the agents’ guaranteed sensing patterns Sig, which by definition are lower in area than their respective sensing patterns Si. Moreover, due to the definition of Hbeing conservative, only the area of the r-limited cells GiRcounts toward the value of H, thus parts of the neutral region Othat are covered by the agents do not contribute to H. Consequently, in the case of the AWGV partitioning (13), coverage objective (14) and control law (15), it is expected for Hrto 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 nmobile ground agents is deployed inside the region of interest Ω. 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

q̇i=cosθisinθiρi2ΩiR+ΩiL,qiΩ,θ̇i=ρiliΩiRΩiL,θiππ,

where ΩiR,ΩiLare the rotational velocities of the right and left wheels, respectively, ρiis the wheel radius, and liis the length of the wheel axis. In this chapter however a simpler single integrator kinematic model is used for the agents. Each agent iInis approximated by a point mass located at qiΩwith orientation θiwhich is governed by the kinematic model described by

q̇i=ui,qΩ,uiR2,E18
θ̇i=ωi,θ,ωiR,E19

where ωiis 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 Sibof agent ias the region sensed by the agent when qi=00Tand θi=0. The only requirements with regards to the base sensing pattern are that qiIntSiband that its boundary Sibcan be described by a set of parametric equations. Let the radius Riof a base sensing pattern be defined as RiSib=maxqSibq. 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 ias a function of its position qiand orientation θi, can be computed by rotating around the origin and translating its base sensing pattern as follows

Siqiθi=qi+RθiSib.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 Hover 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 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 Ωbased on the agents’ positions, only the sensed region iInSiis partitioned based on the agents’ sensing patterns. Each agent is assigned the part of Ωthat only itself is able to sense, with parts being sensed by multiple or no agents being left unassigned.

Given a planar region Ωand a set of sensing patterns S=S1Sn, each agent iis assigned a cell Wias follows

WiΩS=ΩSijIniSj,iIn.

The part of Ωsensed by multiple agents is left unassigned but still contributes toward the coverage objective H. This part is called the common region and is computed as follows

WcΩS=ΩiInSiWi.E21

Having defined the cells and the common region, it holds that iInSi=iInWiWc  Ω.

We can define the neighbors of agent ias 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

Ni=jIni:SiSj.E22

Moreover, if the maximum base sensing radius Rmax=maxiIn Riis known by all agents, and if each agent is able to communicate with all others within a radius

Ci=Ri+Rmax,E23

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

WiΩS=ΩSijNiiSj,iIn.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 Hcan be computed as follows

=iInWiϕqdq+Wcϕqdq.E25

Since Hcan 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 His distributed.

2.4.3. Control law formulation

Having found a partitioning scheme that allows distributed computation of the coverage objective 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

ui=αi,uWiSini ϕqdq,E26
ωi=αi,ωWiSiniRπ2qqiϕqdq,E27

where αi,u,αi,ωare positive constants and niis the outward unit normal vector on Wi, 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)

Ht=iInHqiqit+Hθiθit=iInHqiq̇i+Hθiθ̇i=iInHqiui+Hθiωi.

By selecting the control law

ui=αi,uHqi,ωi=αi,ωHθi,αi,u,αi,ω>0,

we can guarantee monotonic increase of the coverage objective.

The partial derivative Hqiis evaluated as follows

Hqi=qiWiϕqdq+jiqiWjϕqdq+qiWcϕqdq.

Due to the partitioning scheme (24) only the common region Wcis affected by the movement of agent iand since ϕqqi=0, by using the Leibniz integral rule [32], the previous equation becomes

Hqi=Wiυiiniϕqdq+Wcυcincϕqdq

where υjiis the Jacobian matrix

υji=qqi,qWj

and niis the outward unit normal vector on Wi. The boundary Wican be decomposed into three disjoint sets as follows

Wi=WiSiWi∂ΩWiWc,E28

where WiSidenotes part of the cell’s boundary that is also part of the boundary of the agent’s sensing disk, Wi∂Ωdenotes the common boundary between the cell and the region, while WiWcdenotes the common boundary of the cell and the common region. This decomposition is presented in Figure 5 where WiSi, Wi∂Ωand WiWcare shown in solid green, red and blue lines respectively.

Figure 5.

Decomposition of ∂Wi into disjoint sets and corresponding normal vectors.

Since the region Ωis assumed to be static, it holds that υii=0,qWiΩ. In addition, from Eq. (20) we get that υii=I2,qWiSi. Finally, on all the common boundaries WjWc,jInit holds that υij=υicand nj=nc, as shown in Figure 5, leaving only an integral over WiSi. By multiplying with αi,uwe 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 Ω, the space density function ϕqand 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 Hain solid blue and Hrin 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 Ω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 Hain solid blue and Hrin dashed red with their final values being 100% and 35.2% respectively, indicating a 62.4%decrease in the coverage of Ω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 33cm×28cm×15cmin size, weigh 3.6kgand are able to carry a payload of up to 1kg. Their maximum linear and rotational velocities are vmax=1m/sand ωmax=100o/s. Although these robots are equipped with encoders measuring 39,000ticks/revolutionwhich 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.3m.

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 Ωresulting in a maximum error of 0.032m, which was used as the measure of positioning uncertainty rfor all robots.

The control scheme was implemented as a loop in the main computer with an iteration period of Ts=0.1seconds. At each iteration, a simplified version of the control law (15) is computed for each agent, and from that, a target point qitis 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 dt=0.02mof their respective target points, new target points are computed from the robots’ current positions. The feedback control law used for each robot was

vi=minqitqiTsvmaxcosdθi,ωi=mindθiTsωmaxsindθi,

where qiand θiare the robot’s current position and orientation, viand ωithe robots linear and rotational velocity control inputs respectively and dθi=qitqiθ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. SigGi,iIn, 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 Ω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 Haover time for the experiment in blue and the simulation in red where it is seen that it increased from 83.70to 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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sotiris Papatheodorou and Anthony Tzes (November 5th 2018). Theoretical and Experimental Collaborative Area Coverage Schemes Using Mobile Agents, Applications of Mobile Robots, Efren Gorrostieta Hurtado, IntechOpen, DOI: 10.5772/intechopen.78940. Available from:

chapter statistics

155total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Mobile Robot Feature-Based SLAM Behavior Learning, and Navigation in Complex Spaces

By Ebrahim A. Mattar

Related Book

First chapter

Kinematic Performance Measures and Optimization of Parallel Kinematics Manipulators: A Brief Review

By Abdur Rosyid, Bashar El-Khasawneh and Anas Alazzam

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us