# Distributed Control of Networked Unmanned Aerial Vehicles for Valley Area Coverage

Authors: Mengji Shi; Kaiyu Qin
Journal: Mobile Information Systems
 (2016)

---

## Abstract

The paper provides a novel cooperative motion scheme for networked Unmanned Aerial Vehicles (UAVs) to fully sweep-cover a priori unknown elongated areas with curved borders, which are termed “valley areas.” The UAVs’ motion is confined between the borders. Different from former research on straight-corridor-sweep-coverage, in each valley area, the width of different portions varies dramatically: the UAVs need to line up across the valley area to achieve full coverage of the widest portions while they can only pass through the narrowest parts one by one in a queue. The UAVs are provided with barrier detection and inter-UAV communication. According to the scheme, a distributed control law has been offered for discrete-time multi-UAV systems, guaranteeing crash avoidance and full coverage while considering the constrained mobility of the UAVs. Regular and extreme simulations are carried out to verify the efficacy and stability of the proposed algorithm. Solutions to U-shaped valley coverage and the case of insufficient UAVs available are discussed with validation simulations. Comparison simulations are conducted with respect to a line-sweep-coverage algorithm developed by a closely related work, and differences in performance are revealed subsequently. Conclusions are drawn with possible directions of future research.


---

## Body

## 1. Introduction

A fixed-wing Unmanned Aerial Vehicle (UAV) can quickly cover an area by flying at high speed and high altitude to locate forest fire [1] or report natural disasters [2] timely, while various tasks, such as pest monitoring, pesticide spraying, and transmission line inspection, also require slow-and-close operation by multirotor (or helicopter) UAVs [3–10]. The latter provides more accurate operation and clearer details but spends much more time [11]. Fortunately, cooperative operations by multiple networked UAVs may greatly improve the work efficiency [12–18].This paper designs a multi-UAV cooperative motion control algorithm to accomplish tasks such as the aforementioned ones by performing “coverage” function in continuous corridor-shaped areas with two a priori unknown but detectable curved borders and possibly dramatically varying width; the UAVs’ motion is confined between the borders. This type of areas is called “valley areas,” including forest or farmland in natural valleys (borders are the hillsides) and irregular-shaped areas that the UAV operations are not allowed to exceed their outlines due to air traffic control or to prevent additional pollution (when spraying pesticide).The UAVs are supposed to be tasked with flying in the same height, in order to avoid spraying pesticide on the lower ones or being dragged to the ground when one of them is shot down or malfunctioning. Moreover, UAVs should fly at a specific altitude during a vision-based task because pictures sampled from a certain height provide higher recognizability by balancing the visual range and resolution. Based on the mature technology of UAV vision and aircraft control for diverse purposes like pest monitoring [3–5], pesticide spraying [6], and transmission line inspection [7, 8], and so forth [9, 10], this article discusses the cooperative control scheme by modeling the UAVs as point masses in planar space. Accordingly, collision avoidance among them is required.A cooperative coverage strategy, termedsweep coverage [19], usually applies to corridor-shaped areas by deploying multiple UAVs in the form of a moving barrier to sweep across the desired region.We adopt the multi-UAV sweep coverage motion scheme demonstrated in Figure1 to solve the problem addressed above. Due to dramatically varying width of the valley, the UAVs have to line up and move in parallel lines to fully cover the widest portion (see UAVs at t1) while they can only pass through the narrowest part one by one (see UAVs at t2). According to Figure 1, the UAVs should reconfigure their formation to adapt to the environment instead of shrinking the space among them.Figure 1
Ideal cooperative sweep coverage motion paths of multiple UAVs in an a priori unknown valley area with dramatically varying width.To implement the illustrated scheme, a novel cooperative control algorithm is proposed (its novelty over existing works will be indicated in Section2). The idea is inspired by the case of manually moving the iron balls on a string in between two curved vertical tracks from the top down (as shown in Figure 2). The balls at the ends of the string are held in hands, while the motion of the ones in the middle is balanced by the gravity and the pull of the strings. In this model, the balls can easily line up in the widest part between the tracks and pass through the narrowest portion. Consulting the iron balls’ motion, a distributed control is designed for a multi-UAV system with discrete-time dynamics to cover valley areas. The mobility of the UAVs is restricted: the maximal and minimal linear speeds are specified, and the turning angle is bounded.Figure 2
Motion of iron balls on a string.The main contribution of this work is to develop a method that enables efficient coverage of unknown irregular-shaped areas by a team of UAVs performing a single flight through the region with smooth motion paths while considering the UAVs’ limited mobility and collision avoidance among the UAVs and the outlines of the areas.


## 2. Related Work

Cooperation of multiple intelligent units in wireless networks (known as multiagent systems) has attracted considerable attention in the recent decades. Numerous research has offered control algorithms for various collective behavior of multiagent systems, for example, consensus [21–24] and formation [25–27], to achieve diverse functions like tracking [22, 23], coverage [28, 29], surrounding [30], and so forth [31]. The key principle of multiagent cooperation is that each agent pursues its own local goal and that the global goal emerges from the interaction of agents [32]. The multiagent cooperation usually provides better performance than simply aggregated efforts made by individual agents without interaction.Owing to the natural advantages of multiagent cooperation, approaches based on it are developed to drive UAVs to perform area coverage for different purposes: in [12], the authors have proposed a UAVs-UGVs (Unmanned Ground Vehicles) cooperation strategy for forest monitoring and fire detection in assigned areas by applying leader-following formation algorithms on both UAV and UGV teams; literature [13] has planned paths for multi-UAV surveillance over forested regions while maximizing ground visibility using satellite data of tree-cover; research work in [14–16] has accomplished multi-UAV monitoring and surveillance missions via area partition-coverage schemes. However, none of these algorithms is capable of handling coverage problems in a priori unknown environments. papers [17, 18] have devised multi-UAV motion algorithms for coverage of unknown areas with obstacles, while the flight paths are winding all over the area according to the sensing range of each UAV.Sweep coverage schemes usually yield smooth flight paths, and that is an important reason of our choice. Authors of [20, 33–37] have come up with kinematic models of multiagent sweep coverage control under different conditions. The most closely related work to ours is [20, 36, 37]. Papers [20, 37] have studied multirobot sweep coverage along a priori unknown paths by providing control schemes based on consensus algorithms, and the robots perform linear deployment of given lengths. Paper [36] has provided control laws solving corridor sweep coverage problems by lining up the robots and making them move in parallel lines between the borders. However, fixed linear formations in the above algorithms do not accommodate the case of covering valleys with dramatically varying width, eventhough the space among the agents can slightly shrink after deployment. Furthermore, the existing schemes do not take the constrained UAV mobility into account.Our work features two major advantages over the above coverage strategies: (i) the proposed algorithm covers a priori unknown areas while providing smooth motion paths for the UAVs, both of which cannot be achieved by [12–18]; (ii) the new sweep coverage scheme deals with irregular-shaped corridor while the methods proposed in [20, 36, 37] only handle the ones with almost constant width, excluding consideration of collision avoidance among the robots.


## 3. Modeling of the Coverage Scheme

This section aims to formulate the multi-UAV coverage scheme displayed in Figure1 in a mathematical way by modeling the valley areas and the multi-UAV systems with equations and setting standards for the coverage achievements. The algorithmic solutions to the motion control will be presented in Section 4. Coordinate transformation will not be discussed as there are mature algorithms in existing literatures (see [38]).Consider an elongated regionF between two curves in a plane as the 2-dimensional model of a valley area. Let functions f1(x),fn(x) be two nonintersecting smooth curves, where f1(x)>fn(x) for all x. The valley region F is defined as follows: (1)F≜x,y∈R2:fnx≤y≤f1x.Using smooth curves as the borders of the valley areas might trigger questions over the meaningfulness of this work. Possible problems related to this setting will be indicated with solutions in Section 5.Consider a network ofn UAVs. The interconnection topology among them is represented by a directed graph G(V,E), which consists of a set of nodes V={hi},i∈I≜{1,2,…,n}, where each node represents a UAV, and a set of edges E⊆V×V. The existence of an edge eij∈E (which is marked as an arrow in G) indicates that the ith UAV hi transmits information to UAV hj through the network.Remark 1.
In general, for a multi-UAV system to reach a collective behavior, the network among the UAVs should be connected; that is, graphG has at least one spanning tree.Besides a communication device which provides the network connection, each UAV is also supposed to have these functional modules installed:(1)
Task executor: for theith UAV to execute tasks within its coverage region a(i,t) which is assumed to be a disk area centered on the ith UAV with the coverage range Ra, as depicted in Figure 3. Different executors are installed for different tasks: cameras for monitoring, radars for surveillance, sprayers for pesticide spraying, and so forth.(2)
Barrier sensor: to help every UAV distinguish and measure the position of other UAVs or borders if they enter its circular sensing areas(i,t) of radius Rs, which is centered on hi. Information obtained by a barrier sensor comprises three parts: the type of the sensed object (UAV or border), the relative angle of the object, and the distance. To be specific, when the jth UAV enters s(i,t), the ith UAV will be informed of the distance between the centers of the two UAVs, which is denoted by dij(t), and the relative angle θij(t) measured from the heading of the ith UAV to the vector connecting the centers of hi and hj on the counterclockwise direction (see Figure 3). Similarly, if the ith UAV gets close enough to a border fk(x),k∈{1,n}, the distance difk(t) and the relative angle θifk(t) of the border will be measured at the nearest point on the border. Note that the distances only make sense when dij(t),difk(t)≤Rs.Figure 3
Coverage area and barrier sensing areas of the UAVs.A UAV can obtain the position of another one either via the network communication or when it gets close enough to have its positions measured by the barrier sensors of each other; a UAV can only capture its distance from the borders through its barrier sensor.Letpi(t)≜(xi(t),yi(t))∈R2 be the coordinates of the ith UAV hi; let vi(t) and θi(t) be the linear velocity and heading of it, respectively. The kinematic equations of the UAVs are given by(2)x˙it=vitcosθit,y˙it=vitsinθit,for all i∈I. The heading θi is with respect to the x-axis measured from the positive x-axis in the counterclockwise direction.For a given periodT>0, the UAVs gather information about their surrounding environment with sensors and communication devices at a discrete time t=kT,k=0,1,2,…. The discrete-time dynamics of hi are then written as in the following model: (3)xik+1T=xikT+vikTTcosθikT,yik+1T=yikT+vikTTsinθikT,for all i∈I. The heading θi and linear velocity vi are the control inputs. Because of the limited mobility of UAVs, the linear velocity of each UAV is supposed to be restricted: for given scalars vmax>vmin>0 and vmax≥vi(t)≥vmin. And the turning angle is also constrained by given scalar Δθmax∈(0,π/2): (4)θik+1T-θikT≤Δθmax.The control objective of this paper is to properly drive the UAVs in order to achieve the collective motion illustrated in Figure1 to fully cover the valley area, meeting the following conditions.Condition 1.
During the motion, the UAVs should always stay between the borders and never collide with each other; that is,(5)yit∈fnxit+Rp,f1xit-Rp,minpit-pjt>2Rp,for all i,j∈I(i≠j), where 0<Rp=min⁡(Rs,Ra) is the allowed minimal distance between the center of a UAV and any point inside a physical object (other UAVs or hill sides) and |α| is the Euclidean norm of the vector α enclosed hereinafter.Condition 2.
All the UAVs finally move along positivex-axis. Namely, ∀t1, ∃tm>t1, and ∀t2>tm that for all i∈I, (6)xit2>xit1.Condition 3.
After the UAVs are properly deployed, the portion of valley area that they go through should be fully covered by their task executors. That is,∃tp, ∀t1,t2 that t2>t1>tp; if max[xi(t1)]<min⁡[xi(t2)], then (7)⋃i∈I,t∈t1,t2ai,t⊇F∩x,y∈R2:maxxit1≤x≤minxit2.For a valley areaF with borders f1(x),fn(x), let W1≜max[f1(x)-fn(x)] and Wn≜min[f1(x)-fn(x)] be the width of its widest and narrowest part, respectively. To guarantee the possibility for UAVs to pass through the valley without crash and sufficiency of available UAVs for full coverage, we make the following assumption.Assumption 2.
For a given scalarRm∈(2Rp,2Ra), the number of the UAVs satisfies n>(W1-Rs)/Rm+1; and the minimal width of the valley area satisfies Wn>2Rp.To measure the capability of a control algorithm, we introduce a scalarM to describe how dramatically the borders of a valley are curved.Assumption 3.
f ˙ k ( x )   ( k = 1 , n ) are continuous functions. For given M>0, |f˙k(x)|≤M holds for all x,k=1,n, where α˙(β)=dα/dβ is the first-order derivative of α hereinafter.Definition 4.
Given a valley areaF, a control law is said to be an effective sweep coverage control for an n-UAV system, if the UAV collective motion driven by it satisfies Conditions 1, 2, and 3.


## 4. The Distributed Control Algorithm for Valley Area Coverage Based on the Proposed Scheme

In the existing literatures, straight corridor coverage motion is usually achieved by lining up all the agents (robots) and driving them to move in parallel lines through the corridor. However, different from straight corridors, a valley area may have some narrow parts that the UAVs cannot all pass through in parallel. Our strategy is to line up the UAVs across the valley area still but shift the formation as the width varies. The following lemma shows a more practical way of reaching the standards that set for achieving valley area coverage.Lemma 5.
Consider ann-UAV collective motion; if Conditions 1 and 2 are met, and ∃tp,∀t>tp that (8)pit-pi+1t<2Ra,fori∈1,2,…,n-1,ykt-fkxkt<Ra,fork∈1,n,are satisfied, then Condition 3 is satisfied.Proof.
Suppose (8) is satisfied at time t=tr≥tp, then ⋃a(i,tr) for all i∈I is a connected area across the valley region intersecting both borders. For any time t1,t2 where t2>t1≥tr, if max[xi(t1)]<min[xi(t2)], then every UAV will pass through the vertical lines x=max[xi(t1)] and x=min[xi(t2)] successively during the time interval [t1,t2]. Therefore, ⋃‍a(i,t) for t∈[t1,t2] will contain a continuous region surrounded by the following curves and lines: (9)x,y∈R2:maxxit1≤x≤minxit2,y=fkx,k=1,n,x,y∈R2:x=maxxit1,fnx≤y≤f1x,x,y∈R2:x=minxit2,fnx≤y≤f1x.That is to say, (7) is satisfied, and the lemma is proven.Conforming to the iron ball model portrayed in Figure2, a possible control strategy requires two extreme UAVs to move along the borders, respectively, and sync up with each other at the x coordinate for most of the time (except when they pass through the very narrow part one by one). We assign h1 and hn to seek the paths along the borders f1(x) and fn(x), respectively. The communication topology among the UAVs via a connected wireless network is designed as shown in Figure 4: the UAVs hi,i∈{2,3,…,n-1}, in the middle receive information from their specified neighbors hi+1 and hi-1. The interactions between the extreme UAVs h1 and hn help them adjust their motion. To be cost effective, the connection between them is interruptible when they get far from each other, and the information for the hi to get from the network is pj(t) if eij∈E. We specify a desired speed component along x-axis for the two extreme UAVs, denoted by vx0. Assume that vx0 is known to them; thus, once their x-coordinates meet, they can keep pace with each other without connection until they get close again. The desired linear velocity of the kth UAV (k=1,n) at time t is vk0(t)=vx0/cos[θk(t)].Figure 4
The interconnection topology among the UAVs.We make the following assumption to avoidvk,k=1,n, from exceeding the upper bound.Assumption 6.
The condition(10)vmin≤vx0≤vmax1+M2holds for all the UAVs.Assumption 7.
∀ i ∈ I, θi(t)∈[-π/2,π/2] holds all the time.Define operatorΔθ,d:{(R,R)}→(R,R) as (e,b)=Δθ,d({(ei,bi)}) by satisfying the following equation: (11)bcose,sine=∑ibicosei,∑ibisinei.And define operator T:(R,R,R)→R by (12)Ta,amin,amax=maxamin,minamax,a.Letϑi(t) and Di(t) be the angle and the scale of the collision factor for hi at time t. They are generated with the information from its barrier sensor, representing the joint effect of potential threats of crash. For a given scalar rm<Rm, the factor (ϑi(t),Di(t)) is determined by the following equations: (13)ϑit,Dit=Δθ,dπ+θijt,max0,rm-dijt:j∈Uit∪π+θifkt,max0,rm-difkt:fk∈Bit,k≠i,where Ui(t) and Bi(t) are the sets of UAVs and borders that entered s(i,t), respectively.The control inputs for the extreme UAVs are given by(14)θik+1T=TθikT+Tδie,-Δθmax,Δθmax,-π2,π2,vik+1T=T12vikT+vi0kT+1+lkTxn+1-ikT-xikT,vmin,vmax,δie,die=Δθ,dϑikT,DikT,θifikT,rm-difikT,θifikT-siπ2,v0x,for i=1,n, where s(i)=2(1-i)/(n-1)+1 is the sign function and l(kT)≥0 is the connection coefficient: if the network between the two UAVs is connected at time kT, then l(kT)>0; otherwise, l(kT)=0.And we choose the update rule for the UAVshi(i∈{2,3,…,n-1}) in the middle as (15)θik+1T=TθikT+Tδit,-Δθmax,Δθmax,-π2,π2,vik+1T=Tditcosδitcosθik+1T-θikT,vmin,vmax,δit,dit=Δθ,dϑikT,DikT,argpitkT-θikT,12Rm-pitkT,0,v0x,where pit(kT)=pi(kT)-[pi+1(kT)+pi-1(kT)]/2 is the vector variable representing the effect asserted by hi’s neighbors.Motion of the iron balls in Figure2 has been consulted when designing the update rules: the extreme UAVs move along the borders by adjusting the heading to θifi(kT)-s(i)π/2 direction, matching the performance of the manually moved balls; the UAVs in the middle maintain their spatial relationship by keeping a certain distance from their neighbors, and the purpose of the parameter pit(kT) is to regulate the motion of the UAVs to have similar behavior as the iron balls in the middle. On the other hand, a crash avoidance mechanism has been constructed by considering the collision factor (ϑi(kT),Di(kT)) when calculating the turning angle for the update rules of the UAVs.Assumption 8.
The initial states of the UAVs satisfyUi(0)∈∅ for all i∈I; Bi(0)∈∅ for i∈{2,3,…,n-1}; dkfk(0)∈(3Tvk(0)cos⁡[θkfk(0)],Rm) for i∈{1,n}; vi(0)∈(vmin,vmax) for all i∈I.Assumption 9.
Without losing generality, we assume thatRa=Rs>32Rp.Assumption 10.
Condition(16)Rm-M+1VmaxT1+M2≥2Rpholds.The following presents the main result of this section.Theorem 11.
Consider an n-UAV system given by (3) with mentioned restrictions. Suppose that all the assumptions (Assumptions 2–10) are satisfied. Then, the distributed control law presented by (14) and (15) is an effective sweep coverage control for a valley area F.Proof.
Obviously, Assumption7 offers satisfaction of Condition 2.
According to Assumptions8 and 9, crash has been avoided for at least the first 3 steps. Consider the situation that would most possibly lead to a crash: a UAV hi heading to a border f1(x) at time kT with θif1=π/2, and the slope of the border on the right side of xi(kT) is -M. Suppose that at time kT, dif1(kT)=Rm, and the linear speed of it is Vmax. Then, the distance of the UAV’s motion during the sample period is VmaxT. At time (k+1)T, according to the control law, we have dif1[(k+1)T]=Rm-VmaxT and θif1[(k+1)T]=0. We put the UAV in an extreme case again by assuming its speed to be Vmax. Accordingly, at time (k+2)T, the distance between the border and the UAV is (17)Rm-M+1VmaxT1+M2.According to Assumption 10, it is greater than Rp, which means collision has been avoided, and there is less risk of crash in the subsequently updated states because there is enough space for the UAV to move toward a “correct” direction. In other words, Condition 1 has been satisfied.
Intuitively, according to the definition of the operatorΔθ,d, whose scale is 1, it is a compact way of maintaining a tight spatial relationship among the agents and borders by the algorithm. Hence, once the UAVs are deployed to have ⋃a(i,tr) as a connected area at time kT (i.e., (8) is satisfied), then |pi[(k+1)T]-pi+1[(k+1)T]| will not change until they have to pass by the narrowest part of the valley one by one. And even if that happens, the distance will recover with the varying width of the valley. Thus, (8) will always be met for the rest of the time. According to Lemma 5, the control law guarantees an effective sweep coverage of the valley. The proof is completed.


## 5. Simulations and Discussions

This section first carries out a regular simulation to verify the proposed algorithm and an extreme simulation to illustrate the stability and then present solutions to two special cases that the proposed algorithm does not directed apply to, and validation simulations are provided; comparison with a line-sweep-coverage algorithm in a closely related work is made in the last simulation scenario with two experiments.


### 5.1. Regular and Extreme Simulations

As a numeric instance of the coverage control, we setn=6,Ra=Rs=7,Rp=1,Rm=5,T=0.5, and a valley area with borders: (18)f1x=15cos0.04x+12,fnx=12.5sin0.03x+1.5-17.5.Let M=max(f˙1(x),f˙n(x))=0.6,vmax=2.5,vmin=0.5,v0x=1.2, so that Assumptions 6 and 10 are satisfied. We ensure that all the UAVs are initially in the valley area, and the UAVs h1,h6 are close enough to the borders to sense them. The initial velocities are vi(0)=vmin, and the headings θi(0)=0 for all i∈I. Therefore, all the assumptions are fulfilled.Figure5 exhibits the simulation with a duration of kT∈[0,250]. Figure 5(a) reveals the motion paths colored with different gray levels. Similar to Figure 1, the UAV groups (marked with circular dots) in different portions of the valley area represent the states of UAVs at different time. No crash happened at all; namely, min({dij/2}∪{difk})=1.13>Rp for all i,j∈I,k∈{1,n}. Figure 5(b) has portrayed the covered areas during the simulation. Vertical lines are applied to present the coverage because the efficacy of the algorithm is assessed by the connectivity of each robot’s coverage area on the vertical direction according to Lemma 5. Achievement of a full coverage has emerged in the figures. According to Definition 4, the control protocol effectively enables the UAVs to complete the coverage motion in a valley area between the borders given by (18) with smooth flight paths.Figure 5
Regular simulation of multi-UAV motion achieving coverage of a valley area with dramatically varying borders.
(a)
The motion paths of the UAVs (b)
The covered areaRemark 12.
Noting that the proposed control algorithm has guaranteed full coverage by keeping each pair of neighbors within a proper distance (see Lemma5), the UAVs do not suffer from breaking connections. Consequently, the simulation results will be constant; that is, different simulation runs under the same conditions and parameters will always present the same result. Thus, we perform a single run for each simulation.An extreme simulation is conducted to demonstrate the stability of the algorithm: the initial positions of UAVs are set far outside the valley, which challenges Assumption8. And their initial velocities and headings meet vi(0)≥vmax,θi(0)≥π/2 for all i∈I, which conflicts with Assumption 7. Moreover, vmax is set to 5, which contradicts Assumption 10. This scenario should not be practiced in the real world while being just an experimental instance to demonstrate the impact of extreme conditions on the system.The simulation result with duration ofkT∈[0,800] is provided in Figure 6. The UAVs collide with the border for several times in the beginning (x∈[0,100]) due to violation of the assumptions by applying exceedingly large vmax and extraordinary initial states, and the flight paths are winding all through the first half portion of the displayed piece of valley. After x=700, the flight paths are finally stabilized mainly because those important UAV parameters including Ra,Rs,Rp,Rm, and v0x are the same as those in the regular simulation, configured with which, once the UAVs reach a proper deployment, they will tend to follow the paths depicted in Figure 5(a). According to Figure 6(b), full coverage is achieved for all x≥200, as the UAVs are properly deployed then. The simulation result suggests that the proposed algorithm with an appropriate set of parameters can finally stabilize the motion of UAVs in the real world even if the initial states are slightly out of expectation.Figure 6
Extreme simulation of multi-UAV motion performing coverage of a valley area with dramatically varying borders.
(a)
The motion paths of the UAVs (b)
The covered area


### 5.2. Solutions to Special Cases with Validation Simulations

This section discusses two special cases that challenge the applicability of the proposed algorithm in some real-life environments.Special Case  1. Sweep coverage of U-shaped valleys or the ones having rough borders with corners and traps. The challenge lies in the setting that two smooth curves are adopted as the borders of the valley area while providing positive x-axis as the main heading direction of multi-UAV motion.Explanation and Possible Solution. We wish to solve a more general problem by revealing the essentials: the impact of varying width on the multi-UAV coverage motion. A U-shaped valley or the ones having corners and traps on the borders are particular cases of the main problem, and they can be solved by combining the proposed scheme with navigation and obstacle avoidance algorithms. To be specific, the UAVs can change the main direction (the positive x-axis) during the coverage motion according to navigation methods offered in [31, 39] for U-turn environment and apply obstacle avoidance strategy provided by [25, 26] when encountering corners and traps on the borders, which can be taken as obstacles.Validation Simulation. Take a U-shaped valley with sharp concave parts (the corners and traps) in Figure 7 as an example. Figure 8 portrays the simulation result. During the motion, the UAVs alter their main heading (marked with black arrows) when one of them “sees” a great change of the valley’s extension direction. The motion has covered almost everywhere in the valley except the last part which is too wide and the tips of the sharp concave parts which are smoothed with obstacle avoidance algorithms to avoid collisions. The motion paths are smooth.Figure 7
A U-shaped valley.Figure 8
Simulation of multi-UAV motion performing coverage of a U-shaped valley.
(a)
The motion paths of the UAVs, where each black arrow represents a new main heading direction which takes effect when the UAVs are at marked positions nearby (b)
The covered area presented with rotating linesRemark 13.
The borders are not formulated as functions but presented by series of sampled points in this simulation case. This also applies to the simulation scenario discussed in Special Case 2.Special Case  2. The algorithm requires the UAVs to line up across the widest part to achieve full coverage. What would happen if no enough UAVs are available?Possible Solution. Divide the area with virtual borders, and treat the area as a U-shaped area. If the task area is unknown, let one extreme UAV (here we suppose it is hn) follow the border and the other extreme UAV (h1) follow a virtual border gained by f^1(x)=fn(x)+q, where q<W1 under Assumption 2. For h1, the information of fn(x) is obtained from hn via the network, and only the detected part could be known to h1. Prediction algorithms could be applied to estimate future fn(x). h1 should always remember the yielded virtual border f^1(x), so that when the UAVs reach an end, they will change the main heading to cover the other side of the virtual border. On the other hand, if the task area is preknown, then the virtual border can be predesigned to optimize the performance.Validation Simulation. The simulation shown in Figure 9 is constructed to illustrate the idea of virtual border (labeled with the bold dashed line). Comparing to Figure 8, the flight path is less smooth because two sudden changes of main heading direction are made at the round tip of the virtual border which is quite small to buffer the distance between the two extreme UAVs on the new heading direction. This may be improved by using alternative navigation algorithms. If the valley is too wide, the UAVs can build more virtual borders iteratively, as presented in Figure 10.Figure 9
Simulation of insufficient available UAVs performing coverage motion in a valley area by dividing it with a virtual border.
(a)
The motion paths of the UAVs, where the bold dashed line is the virtual border (b)
The covered areaFigure 10
Demonstration of insufficient available UAVs covering an exceedingly wide valley by building multiple virtual borders iteratively.Remark 14.
In this experiment, we assume that the area is preknown to users. The virtual border is constructed based on manual partition of the area. The virtual border is designed to be of a folded shape instead of a single line. Because this helps to slightly smooth the flight paths and reduce the coverage overlaps, we are confident that the gap surrounded by the virtual border will be covered by an extreme UAV during its motion.


### 5.3. Comparison with a Line-Sweep-Coverage Algorithm by Simulation

Figure11 is the simulation result captured from [20] which has introduced a sweep coverage algorithm enabling the mobile robots to form a barrier with a given spatial relationship to sweep along an unknown but detectable line. The simulation has demonstrated a 6-robot sweep coverage motion driven by that algorithm while all the robots are initially heading to 90 degrees from the line’s direction. According to the simulation result, as the coverage task starts, the robots are soon deployed in a linear formation but moving toward the line, and when their sensing range first touches the line, they change their direction and display new linear formation sweeping along it. The simulation result indicates that the total sweep range is 14 while the both radii of barrier sensing area and coverage area of a robot are 2, and the distance between each two adjacent robots is 2, which suggests that the robots’ coverage overlaps with their neighbors’ considerably.Figure 11
Simulation result captured from [20] of sweep coverage motion of robots along a straight line. (a) is the initial deployment, and (b) is the sweep coverage motion driven by an algorithm with weighted average function. Both the barrier sensing range and coverage range are 2, and 6 robots are deployed.
(a) (b)As a comparison, simulations of solving the same line-sweep-coverage problem with our algorithm are carried out by constructing virtual borders. For fairness, the proposed algorithm will not be applied to the UAVs until the sensing area of the extreme UAVhn first touches the line fn(x) causing dnfn≤Rs, and the virtual border f^1(x)=fn(x)+q is formed subsequently, where the virtual valley’s width q=W1=Wn represents the total sweep range.We employ 6 UAVs to sweep along the linefn(x)=-8. The initial positions are set according to Figure 11 except that the overlapped UAVs are separated to avoid collisions by meeting dij>Rp. The sensing range and coverage range are Rs=Ra=2; thus set Rp=0.4 to fulfill Assumption 9. The initial velocities are vi(0)=v0x=0.2 for all i∈I and vmax=0.4,vmin=0.SinceW1<22 according to Assumption 2, two simulations are performed for q=14 (see Figure 12(a)) and q=20 (see Figure 12(b)), respectively. The bold solid lines in Figure 12 are the lines to sweep along; the bold dashed lines are the virtual borders. Comparing to Figure 11, the simulation results are turned 90 degrees clockwise. In Figure 12(a), the UAVs first achieve their final deployment when all xi(t)<10 while the robots in Figure 11 get farther (10~15) to reach final deployment. That means the UAVs driven by our algorithm require less space for deployment than the robots when the total sweep range is 14 in both simulations. In Figure 12(b), the coverage overlaps are significantly reduced by deploying the 6 UAVs to form a much wider barrier (the total sweep range increases to 20) while not taking much space for final deployment which appears when xi(t)∈(10,15). For the same total sweep range, 9 robots are needed according to the algorithm in [20]. Their algorithm has not consider collision among the robots, and they have designed close distribution of initial positions for simulation, which causes oscillation in the UAVs’ trajectories as they have to scatter to prevent crash. The flight paths are stabilized after a short distance.Figure 12
Simulations of sweeping along a line (the bold solid line) as a comparison with the one from [20].
(a)
The simulation result:q=14 (b)
The simulation result:q=20


## 5.1. Regular and Extreme Simulations

As a numeric instance of the coverage control, we setn=6,Ra=Rs=7,Rp=1,Rm=5,T=0.5, and a valley area with borders: (18)f1x=15cos0.04x+12,fnx=12.5sin0.03x+1.5-17.5.Let M=max(f˙1(x),f˙n(x))=0.6,vmax=2.5,vmin=0.5,v0x=1.2, so that Assumptions 6 and 10 are satisfied. We ensure that all the UAVs are initially in the valley area, and the UAVs h1,h6 are close enough to the borders to sense them. The initial velocities are vi(0)=vmin, and the headings θi(0)=0 for all i∈I. Therefore, all the assumptions are fulfilled.Figure5 exhibits the simulation with a duration of kT∈[0,250]. Figure 5(a) reveals the motion paths colored with different gray levels. Similar to Figure 1, the UAV groups (marked with circular dots) in different portions of the valley area represent the states of UAVs at different time. No crash happened at all; namely, min({dij/2}∪{difk})=1.13>Rp for all i,j∈I,k∈{1,n}. Figure 5(b) has portrayed the covered areas during the simulation. Vertical lines are applied to present the coverage because the efficacy of the algorithm is assessed by the connectivity of each robot’s coverage area on the vertical direction according to Lemma 5. Achievement of a full coverage has emerged in the figures. According to Definition 4, the control protocol effectively enables the UAVs to complete the coverage motion in a valley area between the borders given by (18) with smooth flight paths.Figure 5
Regular simulation of multi-UAV motion achieving coverage of a valley area with dramatically varying borders.
(a)
The motion paths of the UAVs (b)
The covered areaRemark 12.
Noting that the proposed control algorithm has guaranteed full coverage by keeping each pair of neighbors within a proper distance (see Lemma5), the UAVs do not suffer from breaking connections. Consequently, the simulation results will be constant; that is, different simulation runs under the same conditions and parameters will always present the same result. Thus, we perform a single run for each simulation.An extreme simulation is conducted to demonstrate the stability of the algorithm: the initial positions of UAVs are set far outside the valley, which challenges Assumption8. And their initial velocities and headings meet vi(0)≥vmax,θi(0)≥π/2 for all i∈I, which conflicts with Assumption 7. Moreover, vmax is set to 5, which contradicts Assumption 10. This scenario should not be practiced in the real world while being just an experimental instance to demonstrate the impact of extreme conditions on the system.The simulation result with duration ofkT∈[0,800] is provided in Figure 6. The UAVs collide with the border for several times in the beginning (x∈[0,100]) due to violation of the assumptions by applying exceedingly large vmax and extraordinary initial states, and the flight paths are winding all through the first half portion of the displayed piece of valley. After x=700, the flight paths are finally stabilized mainly because those important UAV parameters including Ra,Rs,Rp,Rm, and v0x are the same as those in the regular simulation, configured with which, once the UAVs reach a proper deployment, they will tend to follow the paths depicted in Figure 5(a). According to Figure 6(b), full coverage is achieved for all x≥200, as the UAVs are properly deployed then. The simulation result suggests that the proposed algorithm with an appropriate set of parameters can finally stabilize the motion of UAVs in the real world even if the initial states are slightly out of expectation.Figure 6
Extreme simulation of multi-UAV motion performing coverage of a valley area with dramatically varying borders.
(a)
The motion paths of the UAVs (b)
The covered area


## 5.2. Solutions to Special Cases with Validation Simulations

This section discusses two special cases that challenge the applicability of the proposed algorithm in some real-life environments.Special Case  1. Sweep coverage of U-shaped valleys or the ones having rough borders with corners and traps. The challenge lies in the setting that two smooth curves are adopted as the borders of the valley area while providing positive x-axis as the main heading direction of multi-UAV motion.Explanation and Possible Solution. We wish to solve a more general problem by revealing the essentials: the impact of varying width on the multi-UAV coverage motion. A U-shaped valley or the ones having corners and traps on the borders are particular cases of the main problem, and they can be solved by combining the proposed scheme with navigation and obstacle avoidance algorithms. To be specific, the UAVs can change the main direction (the positive x-axis) during the coverage motion according to navigation methods offered in [31, 39] for U-turn environment and apply obstacle avoidance strategy provided by [25, 26] when encountering corners and traps on the borders, which can be taken as obstacles.Validation Simulation. Take a U-shaped valley with sharp concave parts (the corners and traps) in Figure 7 as an example. Figure 8 portrays the simulation result. During the motion, the UAVs alter their main heading (marked with black arrows) when one of them “sees” a great change of the valley’s extension direction. The motion has covered almost everywhere in the valley except the last part which is too wide and the tips of the sharp concave parts which are smoothed with obstacle avoidance algorithms to avoid collisions. The motion paths are smooth.Figure 7
A U-shaped valley.Figure 8
Simulation of multi-UAV motion performing coverage of a U-shaped valley.
(a)
The motion paths of the UAVs, where each black arrow represents a new main heading direction which takes effect when the UAVs are at marked positions nearby (b)
The covered area presented with rotating linesRemark 13.
The borders are not formulated as functions but presented by series of sampled points in this simulation case. This also applies to the simulation scenario discussed in Special Case 2.Special Case  2. The algorithm requires the UAVs to line up across the widest part to achieve full coverage. What would happen if no enough UAVs are available?Possible Solution. Divide the area with virtual borders, and treat the area as a U-shaped area. If the task area is unknown, let one extreme UAV (here we suppose it is hn) follow the border and the other extreme UAV (h1) follow a virtual border gained by f^1(x)=fn(x)+q, where q<W1 under Assumption 2. For h1, the information of fn(x) is obtained from hn via the network, and only the detected part could be known to h1. Prediction algorithms could be applied to estimate future fn(x). h1 should always remember the yielded virtual border f^1(x), so that when the UAVs reach an end, they will change the main heading to cover the other side of the virtual border. On the other hand, if the task area is preknown, then the virtual border can be predesigned to optimize the performance.Validation Simulation. The simulation shown in Figure 9 is constructed to illustrate the idea of virtual border (labeled with the bold dashed line). Comparing to Figure 8, the flight path is less smooth because two sudden changes of main heading direction are made at the round tip of the virtual border which is quite small to buffer the distance between the two extreme UAVs on the new heading direction. This may be improved by using alternative navigation algorithms. If the valley is too wide, the UAVs can build more virtual borders iteratively, as presented in Figure 10.Figure 9
Simulation of insufficient available UAVs performing coverage motion in a valley area by dividing it with a virtual border.
(a)
The motion paths of the UAVs, where the bold dashed line is the virtual border (b)
The covered areaFigure 10
Demonstration of insufficient available UAVs covering an exceedingly wide valley by building multiple virtual borders iteratively.Remark 14.
In this experiment, we assume that the area is preknown to users. The virtual border is constructed based on manual partition of the area. The virtual border is designed to be of a folded shape instead of a single line. Because this helps to slightly smooth the flight paths and reduce the coverage overlaps, we are confident that the gap surrounded by the virtual border will be covered by an extreme UAV during its motion.


## 5.3. Comparison with a Line-Sweep-Coverage Algorithm by Simulation

Figure11 is the simulation result captured from [20] which has introduced a sweep coverage algorithm enabling the mobile robots to form a barrier with a given spatial relationship to sweep along an unknown but detectable line. The simulation has demonstrated a 6-robot sweep coverage motion driven by that algorithm while all the robots are initially heading to 90 degrees from the line’s direction. According to the simulation result, as the coverage task starts, the robots are soon deployed in a linear formation but moving toward the line, and when their sensing range first touches the line, they change their direction and display new linear formation sweeping along it. The simulation result indicates that the total sweep range is 14 while the both radii of barrier sensing area and coverage area of a robot are 2, and the distance between each two adjacent robots is 2, which suggests that the robots’ coverage overlaps with their neighbors’ considerably.Figure 11
Simulation result captured from [20] of sweep coverage motion of robots along a straight line. (a) is the initial deployment, and (b) is the sweep coverage motion driven by an algorithm with weighted average function. Both the barrier sensing range and coverage range are 2, and 6 robots are deployed.
(a) (b)As a comparison, simulations of solving the same line-sweep-coverage problem with our algorithm are carried out by constructing virtual borders. For fairness, the proposed algorithm will not be applied to the UAVs until the sensing area of the extreme UAVhn first touches the line fn(x) causing dnfn≤Rs, and the virtual border f^1(x)=fn(x)+q is formed subsequently, where the virtual valley’s width q=W1=Wn represents the total sweep range.We employ 6 UAVs to sweep along the linefn(x)=-8. The initial positions are set according to Figure 11 except that the overlapped UAVs are separated to avoid collisions by meeting dij>Rp. The sensing range and coverage range are Rs=Ra=2; thus set Rp=0.4 to fulfill Assumption 9. The initial velocities are vi(0)=v0x=0.2 for all i∈I and vmax=0.4,vmin=0.SinceW1<22 according to Assumption 2, two simulations are performed for q=14 (see Figure 12(a)) and q=20 (see Figure 12(b)), respectively. The bold solid lines in Figure 12 are the lines to sweep along; the bold dashed lines are the virtual borders. Comparing to Figure 11, the simulation results are turned 90 degrees clockwise. In Figure 12(a), the UAVs first achieve their final deployment when all xi(t)<10 while the robots in Figure 11 get farther (10~15) to reach final deployment. That means the UAVs driven by our algorithm require less space for deployment than the robots when the total sweep range is 14 in both simulations. In Figure 12(b), the coverage overlaps are significantly reduced by deploying the 6 UAVs to form a much wider barrier (the total sweep range increases to 20) while not taking much space for final deployment which appears when xi(t)∈(10,15). For the same total sweep range, 9 robots are needed according to the algorithm in [20]. Their algorithm has not consider collision among the robots, and they have designed close distribution of initial positions for simulation, which causes oscillation in the UAVs’ trajectories as they have to scatter to prevent crash. The flight paths are stabilized after a short distance.Figure 12
Simulations of sweeping along a line (the bold solid line) as a comparison with the one from [20].
(a)
The simulation result:q=14 (b)
The simulation result:q=20


## 6. Conclusion

The paper has come up with a cooperative motion scheme for multiple networked UAVs to complete tasks of performing coverage function over a class of irregular-shaped areas which are called the “valleys.” The multi-UAV motion has been confined between two curved borders of a valley. Inspired by the motion of a string of iron balls being manually moved with gravity through the irregular space between two curved vertical tracks, a distributed control algorithm based on the scheme has been proposed considering crash avoidance and the motion constraints of the UAVs. A regular simulation has been carried out to demonstrate the coverage motion, and an extreme simulation has also been performed to illustrate the stability of the algorithm. Two special cases challenging the applicability of the proposed algorithm in real-world environment have been addressed with possible solutions and, for each solution, a validation simulation has been conducted to verify the ideas. Additionally, for comparison, two simulations have been undertaken with respect to an experiment by the authors of [20], and differences among the simulation result of their algorithm and the ones of ours have been subsequently discussed.The simulation results indicate that the proposed algorithm leads to effective multi-UAV cooperative coverage of given valley with smooth flight paths as long as the parameters are configured under the given assumptions and, even with extreme initial deployment slightly violating the assumptions, the coverage is eventually achieved with stabilized flight path. And the provided solutions to the discussed special cases are testified to be constructive. Comparing to the simulation offered in [20] of line-sweep-coverage motion, related simulations with our algorithm show advances in reduced space requirement for the final deployment and extended total sweep range, respectively.Future studies should explore the impact of communication delays and stochastic disturbance on the performance of multi-UAV cooperative coverage motion in the valleys. Time delays are ubiquitous in wireless networks while frequently causing stability problems. Solving these problems may greatly help the process of bridging the gap between theoretical methods and real-world applications. On the other hand, optimizations for reducing the coverage overlaps would be considered as another direction of future research. According to the two experiments in the last simulation scenario, the UAVs cover a much wider area by extending the distance among the UAVs, and the overlapping coverage areas have been significantly lessened consequently.



---

*Source: 3680265-2016-10-10.xml*