# Time-Efficient Coverage Path Planning for Energy-Constrained UAV

Authors: Yanxi Huang; Jiankang Xu; Mengting Shi; Liang Liu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Unmanned aerial vehicles (UAVs) have the characteristics of high mobility and wide coverage, making them widely used in coverage, search, and other fields. In these applications, UAV often has limited energy. Therefore, planning a time-efficient coverage path for energy-constrained UAV to cover the area of interest is the core issue. The existing coverage path planning algorithms assume that the UAV moves at a constant speed, without taking into account the cost of turns (including deceleration, turning, and acceleration), which is unrealistic. To solve the above problem, we propose a time-efficient coverage path planning (TECPP) algorithm for the energy-constrained UAV. We build a novel gadget-based graph model, which formalizes the time and energy costs of the flight path including straight flights and making turns (deceleration, turning, and acceleration). Moreover, our graph model is suitable for irregular-shaped areas with multiple obstacles. Finally, we transform the above problem into a generalized traveling salesman problem (GTSP) and use the generalized large neighborhood search (GLNS) solver to solve it. The experimental results show that TECPP outperforms the existing coverage path planning algorithms, and TECPP saves at least 21.6% of time.


---

## Body

## 1. Introduction

Unmanned aerial vehicles (UAVs) have high mobility and wide coverage, which are often applied to disaster monitoring [1, 2], photogrammetry [3, 4], precision agriculture [5, 6], search and rescue [7, 8], Internet of Things [9–11], etc. By dispatching UAVs equipped with onboard sensors (cameras, radars, etc.) to perform some specific tasks such as coverage and search, we can not only complete tasks conveniently and efficiently but also save human resources greatly.In practical applications, most UAVs have limited energy, which restricts deployments to less than 30 minutes [12]. Therefore, it is crucial to plan a time-efficient coverage path for energy-constrained UAV. The existing coverage path planning algorithms, such as [13–16], mainly take the energy consumption of UAVs as the optimization goal and ignore the time cost of completing tasks. Furthermore, they assume that UAV moves at a constant speed, without taking into account the cost of turns (deceleration, turning, and acceleration). Besides, most of them ignore the impact of obstacles. For example, the area of interest may be irregular-shaped with multiple obstacles, and UAV must bypass all obstacles to complete coverage or search missions successfully.In this paper, we study the time-efficient coverage path planning problem, which takes into account the cost of turns and the impact of obstacles. We call this problem the complex multifactor coverage path planning (CMFCPP) problem. To solve the CMFCPP problem, we propose a time-efficient coverage path planning (TECPP) algorithm for energy-constrained UAV, which takes the time consumption as the optimization goal and the energy consumption as the constraint. We build a novel gadget-based graph model, which formalizes the time and energy costs of the flight path including straight flights and making turns (deceleration, turning, and acceleration). Moreover, our graph model takes into account the impact of obstacles and is suitable for irregular-shaped areas with multiple obstacles. Finally, we transform the CMFCPP problem into a generalized traveling salesman problem (GTSP) and use the generalized large neighborhood search (GLNS) solver [17] to solve it.We summarize the major contributions as follows:(i)
We build a novel gadget-based graph model considering the impact of obstacles, which formalizes the time and energy costs of the flight path including straight flights and making turns (deceleration, turning, and acceleration)(ii)
Based on this graph model, we formulate the CMFCPP problem and transform the problem into a generalized traveling salesman problem (GTSP)(iii)
We propose TECPP for solving the CMFCPP problem, which can save at least 21.6% of time compared to the existing coverage path planning algorithmsThe remainder of the paper is organized as follows. In Section2, we discuss the related work. In Section 3, we introduce the preliminaries. In Section 4, we give the UAV system model, including the UAV coverage model and UAV movement model. In Section 5, we build a gadget-based graph model to formalize the time and energy costs of the flight path including straight flights and making turns (deceleration, turning, and acceleration). In Section 6, we formulate the CMFCPP problem and transform the problem into GTSP. In Section 7, we present our experimental results comparing TECPP to the traditional coverage path planning algorithm (baseline) and Lin-Kernighan heuristic algorithm for drones (LKH-D). We summarize our main results in Section 8.


## 2. Related Work

Recently, there have been many studies on coverage path planning for UAVs. We classify the existing coverage path planning algorithms involved in these studies as follows.


### 2.1. Geometric Algorithms

Torres et al. [13] propose the back-and-forth (BF) algorithm for concave or multiple polygon coverage. They calculate the optimal line sweep direction and decompose a complex region into several regular regions to minimize the number of turns in the process of performing coverage tasks. Finally, they plan a flight path for the UAV to move back and forth to reduce the energy consumption of the UAV as much as possible. In [14], the authors propose an E-spiral algorithm to solve the coverage path planning problem. They establish a new energy model to set the optimal speeds for different stages of straight flights to reduce energy consumption. Besides, they also improve the established energy model to predict the total energy consumption of completing coverage tasks. However, the above two geometric algorithms do not take into account the time cost of completing the tasks and the influence of obstacles that may be included in the area of interest.


### 2.2. Grid-Based Algorithms

In [18], the authors propose a grid-based path planning algorithm for irregular-shaped areas, which is mainly based on depth-limited search with a backtracking algorithm. This paper uses approximate cell decomposition to discretize the covered target area into regular square grids and converts them into a regular graph. What is more, they use a simple cost function to minimize the number of turns to reduce the energy consumption of UAV. However, some important factors that affect energy consumption, such as acceleration and deceleration in the specific process of turn, are not considered. Based on their work, [19] improves the algorithm and proposes an energy-aware grid-based algorithm to minimize the energy consumption of completing the search tasks in irregular-shaped areas. Moreover, this paper also applies two pruning techniques to the original algorithm and improves the speed of the algorithm greatly.


### 2.3. Column Generation Algorithms

Choi et al. [20] introduce a novel coverage path planning (CPP) algorithm for a unmanned aerial system (UAS) imagery mission. To mitigate the limitation of the conventional vehicle-routing-based approaches for the CPP not capturing a turning motion of the vehicle, they propose a vehicle-routing-based approach using a column generation algorithm. Based on [20, 21], it presents a new coverage path planning (CPP) algorithm for an aerial imaging mission with multiple unmanned aerial vehicles (UAVs). To solve a CPP problem with multiple UAVs, they divide the coverage mission into five mission segments: take-off, cruise, hovering, turning, and landing. They introduce a new route-based optimization model with column generation that can trace the amount of energy required for all different mission phases to solve the limitation of the traditional approaches.


### 2.4. Heuristic Algorithms

The Lin-Kernighan heuristic algorithm for drones (LKH-D) [22] improves the traditional Lin-Kernighan heuristic (LKH) algorithm to minimize the total energy consumption of covering the target areas. Piao et al. [23] first explore the use of unmanned aerial vehicles to realize the automatic construction of CSI maps for indoor positioning. They propose an energy optimization problem based on the coverage path planning problem, which is eventually transformed into the generalized traveling salesman problem (GTSP). However, these two algorithms consider the problem of turn but ignore the specific process of turn (deceleration, turning, and acceleration).Yu et al. [5] consider that UAV can land on an unmanned ground vehicle (UGV). The UGV can also charge UAV while it is being transported to the next take-off location. In the scene of precision agriculture, a boustrophedon cell corresponds to a row of crops, and they use a UAV equipped with a camera sensor to monitor all crops. They propose a new regional coverage path planning algorithm to minimize the time cost and take into account the symbiotic relationship between UGV and UAV. Finally, they convert the problem into a generalized traveling salesman problem (GTSP), which can be solved using the GLNS solver. However, the algorithm ignores the influence of obstacles and the cost of the turning process.


### 2.5. Machine Learning Algorithms

Theile et al. [24] train a double deep Q-network to make control decisions for the UAV and balance limited power budget and coverage task. Steiger et al. [25] consider a scenario in which a UAV acts as an aerial base station to provide emergency communications services over an area of unknown and uneven user distribution, and they propose an online algorithm that simultaneously solves the path planning and coverage mapping problems using a deep learning model. To solve this problem of coverage path planning in cellular unmanned aerial vehicle networks, Challita et al. [26] propose a deep reinforcement learning algorithm based on echo state network (ESN) cells.In summary, most of the above algorithms plan to optimize the energy consumption of UAVs and ignore the time cost and the process of turn to complete coverage tasks. However, the optimization goal of our work is the time consumption of completing coverage tasks. In addition, we take into account the time and energy costs of UAV in the process of turn (deceleration, turning, and acceleration) and the influence of irregular-shaped areas with multiple obstacles.


## 2.1. Geometric Algorithms

Torres et al. [13] propose the back-and-forth (BF) algorithm for concave or multiple polygon coverage. They calculate the optimal line sweep direction and decompose a complex region into several regular regions to minimize the number of turns in the process of performing coverage tasks. Finally, they plan a flight path for the UAV to move back and forth to reduce the energy consumption of the UAV as much as possible. In [14], the authors propose an E-spiral algorithm to solve the coverage path planning problem. They establish a new energy model to set the optimal speeds for different stages of straight flights to reduce energy consumption. Besides, they also improve the established energy model to predict the total energy consumption of completing coverage tasks. However, the above two geometric algorithms do not take into account the time cost of completing the tasks and the influence of obstacles that may be included in the area of interest.


## 2.2. Grid-Based Algorithms

In [18], the authors propose a grid-based path planning algorithm for irregular-shaped areas, which is mainly based on depth-limited search with a backtracking algorithm. This paper uses approximate cell decomposition to discretize the covered target area into regular square grids and converts them into a regular graph. What is more, they use a simple cost function to minimize the number of turns to reduce the energy consumption of UAV. However, some important factors that affect energy consumption, such as acceleration and deceleration in the specific process of turn, are not considered. Based on their work, [19] improves the algorithm and proposes an energy-aware grid-based algorithm to minimize the energy consumption of completing the search tasks in irregular-shaped areas. Moreover, this paper also applies two pruning techniques to the original algorithm and improves the speed of the algorithm greatly.


## 2.3. Column Generation Algorithms

Choi et al. [20] introduce a novel coverage path planning (CPP) algorithm for a unmanned aerial system (UAS) imagery mission. To mitigate the limitation of the conventional vehicle-routing-based approaches for the CPP not capturing a turning motion of the vehicle, they propose a vehicle-routing-based approach using a column generation algorithm. Based on [20, 21], it presents a new coverage path planning (CPP) algorithm for an aerial imaging mission with multiple unmanned aerial vehicles (UAVs). To solve a CPP problem with multiple UAVs, they divide the coverage mission into five mission segments: take-off, cruise, hovering, turning, and landing. They introduce a new route-based optimization model with column generation that can trace the amount of energy required for all different mission phases to solve the limitation of the traditional approaches.


## 2.4. Heuristic Algorithms

The Lin-Kernighan heuristic algorithm for drones (LKH-D) [22] improves the traditional Lin-Kernighan heuristic (LKH) algorithm to minimize the total energy consumption of covering the target areas. Piao et al. [23] first explore the use of unmanned aerial vehicles to realize the automatic construction of CSI maps for indoor positioning. They propose an energy optimization problem based on the coverage path planning problem, which is eventually transformed into the generalized traveling salesman problem (GTSP). However, these two algorithms consider the problem of turn but ignore the specific process of turn (deceleration, turning, and acceleration).Yu et al. [5] consider that UAV can land on an unmanned ground vehicle (UGV). The UGV can also charge UAV while it is being transported to the next take-off location. In the scene of precision agriculture, a boustrophedon cell corresponds to a row of crops, and they use a UAV equipped with a camera sensor to monitor all crops. They propose a new regional coverage path planning algorithm to minimize the time cost and take into account the symbiotic relationship between UGV and UAV. Finally, they convert the problem into a generalized traveling salesman problem (GTSP), which can be solved using the GLNS solver. However, the algorithm ignores the influence of obstacles and the cost of the turning process.


## 2.5. Machine Learning Algorithms

Theile et al. [24] train a double deep Q-network to make control decisions for the UAV and balance limited power budget and coverage task. Steiger et al. [25] consider a scenario in which a UAV acts as an aerial base station to provide emergency communications services over an area of unknown and uneven user distribution, and they propose an online algorithm that simultaneously solves the path planning and coverage mapping problems using a deep learning model. To solve this problem of coverage path planning in cellular unmanned aerial vehicle networks, Challita et al. [26] propose a deep reinforcement learning algorithm based on echo state network (ESN) cells.In summary, most of the above algorithms plan to optimize the energy consumption of UAVs and ignore the time cost and the process of turn to complete coverage tasks. However, the optimization goal of our work is the time consumption of completing coverage tasks. In addition, we take into account the time and energy costs of UAV in the process of turn (deceleration, turning, and acceleration) and the influence of irregular-shaped areas with multiple obstacles.


## 3. Preliminaries

In Section6, we transform the CMFCPP problem into GTSP and use the GLNS solver to solve it. In Section 7, we take the Lin-Kernighan heuristic algorithm for drones (LKH-D) as one of the experimental comparison algorithms. For the readability of this paper, we briefly introduce GTSP, GLNS, and LKH-D in this section.


### 3.1. GTSP

The generalized traveling salesman problem (GTSP) [27–29] is a promotion of the classic traveling salesman problem (TSP). GTSP can be expressed as finding a special Hamiltonian loop on a fully weighted graph G=V,E,W. V is the set of all vertices, representing all city sets. E is the set of all arcs, denoting the set of edges connected between two cities. W is a set of weight, representing the distance or cost between any two cities in graph G.GTSP is to find a Hamiltonian loop with the smallest sum of weights in the above graphG. This loop does not need to pass through all cities but must pass through each city group once and only once. Moreover, GTSP can be divided into two types. The first type of GTSP is that the Hamiltonian circuit corresponding to the optimal solution passes through each city group once and only passes through one city in each city group. The second type of GTSP is that the Hamiltonian corresponding to the optimal solution passes through each city group once but can pass through multiple cities in each city group. At present, common problems such as coverage path planning, random vehicle scheduling, and mailbox fetching can all be transformed into GTSP.


### 3.2. GLNS

Generalized large neighborhood search (GLNS) [17], based on adaptive large neighborhood search framework, is an efficient solver for the first type of generalized traveling salesman problem (GTSP). GLNS is proposed by Smith et al., who present a novel insertion mechanism that contains special cases nearest, farthest, and random insertions. The mechanism allows for greater randomization when exploring neighbors of a given GTSP tour.Besides, they provide extensive benchmarking results for the GLNS solver in comparison to the state of the art on a wide range of existing and new problem libraries. They show that, on the one hand, GLNS is competitive with the most famous algorithms on the GTSP-LIB library. And on the other hand, given the same amount of time, GLNS can find higher-quality solutions than existing approaches on several other libraries.


### 3.3. LKH-D

The Lin-Kernighan heuristic (LKH) algorithm [30] achieves local optimization through the iterative improvement of random solutions, which is mainly used to solve the classic TSP. However, LKH is not suitable for solving the coverage path planning problem, because it does not take into account the cost of turns.Based on LKH, Modares et al. [22] propose a Lin-Kernighan heuristic algorithm for drones (LKH-D). LKH-D uses a complex cost function to account for the cost of UAV in the specific process of turn, which is calculated as a weighted sum of the length of the tour and the sum of the turn angles within the tour. Finally, they transform the UAV coverage path planning problem into a variant TSP problem and solve it.


## 3.1. GTSP

The generalized traveling salesman problem (GTSP) [27–29] is a promotion of the classic traveling salesman problem (TSP). GTSP can be expressed as finding a special Hamiltonian loop on a fully weighted graph G=V,E,W. V is the set of all vertices, representing all city sets. E is the set of all arcs, denoting the set of edges connected between two cities. W is a set of weight, representing the distance or cost between any two cities in graph G.GTSP is to find a Hamiltonian loop with the smallest sum of weights in the above graphG. This loop does not need to pass through all cities but must pass through each city group once and only once. Moreover, GTSP can be divided into two types. The first type of GTSP is that the Hamiltonian circuit corresponding to the optimal solution passes through each city group once and only passes through one city in each city group. The second type of GTSP is that the Hamiltonian corresponding to the optimal solution passes through each city group once but can pass through multiple cities in each city group. At present, common problems such as coverage path planning, random vehicle scheduling, and mailbox fetching can all be transformed into GTSP.


## 3.2. GLNS

Generalized large neighborhood search (GLNS) [17], based on adaptive large neighborhood search framework, is an efficient solver for the first type of generalized traveling salesman problem (GTSP). GLNS is proposed by Smith et al., who present a novel insertion mechanism that contains special cases nearest, farthest, and random insertions. The mechanism allows for greater randomization when exploring neighbors of a given GTSP tour.Besides, they provide extensive benchmarking results for the GLNS solver in comparison to the state of the art on a wide range of existing and new problem libraries. They show that, on the one hand, GLNS is competitive with the most famous algorithms on the GTSP-LIB library. And on the other hand, given the same amount of time, GLNS can find higher-quality solutions than existing approaches on several other libraries.


## 3.3. LKH-D

The Lin-Kernighan heuristic (LKH) algorithm [30] achieves local optimization through the iterative improvement of random solutions, which is mainly used to solve the classic TSP. However, LKH is not suitable for solving the coverage path planning problem, because it does not take into account the cost of turns.Based on LKH, Modares et al. [22] propose a Lin-Kernighan heuristic algorithm for drones (LKH-D). LKH-D uses a complex cost function to account for the cost of UAV in the specific process of turn, which is calculated as a weighted sum of the length of the tour and the sum of the turn angles within the tour. Finally, they transform the UAV coverage path planning problem into a variant TSP problem and solve it.


## 4. System Model

### 4.1. UAV Coverage Model

The UAVs can be classified into two main categories: fixed-wing and rotary-wing UAVs [31]. The fixed-wing UAV has greater endurance to support longer flights and high-speed motion. However, the fixed-wing UAV cannot perform hovering tasks, since it needs to constantly move during missions. The rotary-wing UAV presents maneuverability advantages using rotary blades. Therefore, the rotary-wing UAV can perform vertical take-off and landing, low-altitude flight, and hovering tasks. In summary, the rotary-wing UAV is more suitable and has been widely used for coverage tasks. As shown in Figure 1, the Crazyflie UAV is a typical rotary-wing UAV, which is used for indoor tasks.Figure 1
The Crazyflie UAV.The area of interest may be an irregular-shaped area with multiple obstacles. We draw lessons from the work of Cabreira et al. [19] and divide the area into several square grids. Figure 2 shows that a quadrotor UAV equipped with a camera sensor is dispatched to perform coverage tasks. By adjusting the flying height of the UAV and the relevant parameters of the onboard camera (angle of view, image resolution, etc.), the camera footprint of the UAV just overlaps the grid when the UAV passes through the center of the grid as shown in Figure 2.Figure 2
UAV coverage model.


### 4.2. UAV Movement Model

This paper mainly considers the following two choices of actions:(1)
Straight flight: without loss of generality, we assume that UAV can only move in eight directions (the angle between adjacent directions is 45°) on the same horizontal plane as shown in Figure 3. During straight flights, UAV has to accelerate before reaching a constant speed of v0 and decelerate before hovering. In other words, the process of straight flights may be accompanied by acceleration, deceleration, and constant-speed phases. To formalize the time and energy costs of straight flight, we represent the time cost to pass through the adjacent grid by Ts and the energy cost by Es(2)
Making a turn: for a turn, the UAV needs to decelerate in one direction until hovering, then turn, and finally accelerate in another direction until reaching the constant speed of v0. In other words, the specific process of turn is composed of three phases (deceleration, turning, and acceleration). Without loss of generality, we assume that UAV has only four possible turn angles: 45°, 90°, 135°, and 180°. In addition, the deceleration distance and the acceleration distance are both constant denoted by Sdec and Sacc. To formalize the time and energy costs of the turning process, we denote the time and energy costs for making a turn by Tt and EtFigure 3
The movement directions of UAV.


## 4.1. UAV Coverage Model

The UAVs can be classified into two main categories: fixed-wing and rotary-wing UAVs [31]. The fixed-wing UAV has greater endurance to support longer flights and high-speed motion. However, the fixed-wing UAV cannot perform hovering tasks, since it needs to constantly move during missions. The rotary-wing UAV presents maneuverability advantages using rotary blades. Therefore, the rotary-wing UAV can perform vertical take-off and landing, low-altitude flight, and hovering tasks. In summary, the rotary-wing UAV is more suitable and has been widely used for coverage tasks. As shown in Figure 1, the Crazyflie UAV is a typical rotary-wing UAV, which is used for indoor tasks.Figure 1
The Crazyflie UAV.The area of interest may be an irregular-shaped area with multiple obstacles. We draw lessons from the work of Cabreira et al. [19] and divide the area into several square grids. Figure 2 shows that a quadrotor UAV equipped with a camera sensor is dispatched to perform coverage tasks. By adjusting the flying height of the UAV and the relevant parameters of the onboard camera (angle of view, image resolution, etc.), the camera footprint of the UAV just overlaps the grid when the UAV passes through the center of the grid as shown in Figure 2.Figure 2
UAV coverage model.


## 4.2. UAV Movement Model

This paper mainly considers the following two choices of actions:(1)
Straight flight: without loss of generality, we assume that UAV can only move in eight directions (the angle between adjacent directions is 45°) on the same horizontal plane as shown in Figure 3. During straight flights, UAV has to accelerate before reaching a constant speed of v0 and decelerate before hovering. In other words, the process of straight flights may be accompanied by acceleration, deceleration, and constant-speed phases. To formalize the time and energy costs of straight flight, we represent the time cost to pass through the adjacent grid by Ts and the energy cost by Es(2)
Making a turn: for a turn, the UAV needs to decelerate in one direction until hovering, then turn, and finally accelerate in another direction until reaching the constant speed of v0. In other words, the specific process of turn is composed of three phases (deceleration, turning, and acceleration). Without loss of generality, we assume that UAV has only four possible turn angles: 45°, 90°, 135°, and 180°. In addition, the deceleration distance and the acceleration distance are both constant denoted by Sdec and Sacc. To formalize the time and energy costs of the turning process, we denote the time and energy costs for making a turn by Tt and EtFigure 3
The movement directions of UAV.


## 5. Problem Modeling

### 5.1. Graph Representation of Coverage Tasks

To approach the CMFCPP problem, we divide the given area with multiple obstacles into several square grids as shown in Figure4(a). The gray grids represent no-fly zones with obstacles that the UAV cannot pass, and the nongray grids represent free zones that the UAV can pass. By connecting the centers of adjacent nongray grids, we model the irregular-shaped area by a graph G=V,E as shown in Figure 4(b), where V represents the set of all vertices and each vertex denotes a nongray grid. E represents the set of all edges, and each edge eij denotes the path that the UAV can pass through. To complete coverage tasks, the UAV needs to visit all the vertices.Figure 4
Graph representation of coverage tasks.
(a)
The area of interest(b)
Graph representationAs described above, the UAV has two choices of actions, i.e., straight flight and making a turn. To model the actions, we assign the costs of the actions as the weights of corresponding edges in the graph. Then, by finding a loop on the graph, we can obtain a sequence of actions for the UAV to perform. Finally, the minimum cost is attained by minimizing the summed weights of the visited edges. To achieve this, we should ensure that the cost of UAV’s actions is precisely modeled by the weight of edges. We next present the modeling of the cost for a straight flight and making a turn in detail.


### 5.2. The Cost Model of Straight Flight and Making a Turn

As shown in Figure5, the UAV has a flight path a⟶k⟶m⟶b⟶n⟶c. The speed of constant-speed phases is v0. Let xi,yi denote the coordinates of vertex i, vi denote the speed of UAV at vertex i, and di,j denote the distance between any two vertices i,j. Moreover, dak and dbn are equal to Sacc, and dmb is equal to Sdec.Figure 5
The cost model of straight flight and making a turn.The Cartesian coordinate distance between any two verticesi and j can be obtained by the following equation:
(1)dij=xi−xj2+yi−yj2.


#### 5.2.1. The Cost Model of Straight Flight

During the straight flight of the UAV from vertexa to vertex b, we need to confirm the flight speed of the UAV at vertex a and vertex b to determine whether this process is accompanied by deceleration or acceleration. We use γ and δ to represent the time and energy costs of the UAV moving one meter. Moreover, we denote the time and energy costs of acceleration by Tacc and Eacc and use Tdec and Edec to denote the time and energy costs of deceleration.We get the time costTab and energy cost Eab of the UAV in this process as follows:
(2)Tab=γdam,ifva=v0,Tacc+γdkm,ifva=0,(3)Eab=δdam,ifva=v0,Eacc+δdkm,ifva=0.Finally, we denote the time costTs and energy cost Es of the UAV passing through the adjacent grids by
(4)Ts=Tab,ifeabistraversed,∞,otherwise,(5)Es=Eab,ifeabistraversed,∞,otherwise.


#### 5.2.2. The Cost Model of Making a Turn

During the process of making a turn, we represent the time and energy costs of the UAV turning one degree byα and β. By calculating the lengths of the sides eab, ebc, and eac and then using the Law of Cosines, the angle of turn at vertex b can be calculated by θabc.We get the time costTabc and energy cost Eabc of the turning process m⟶b⟶n as follows:
(6)Tabc=Tdec+180×θabcπ×α+Tacc,(7)Eabc=Edec+180×θabcπ×β+Eacc,(8)θabc=π−cos−1dab2+dbc2−dac22dabdbc.Therefore, we denote the time costTt and energy cost Et of the UAV making a turn by
(9)Tt=Tabc,ifeab,ebcistraversed,∞,otherwise,(10)Et=Eabc,ifeab,ebcistraversed,∞,otherwise.


### 5.3. The Improvements of Modeling

In the previous subsection, we have formalized the cost of straight flight and making a turn. However, the cost of the turning process cannot be expressed by the weight of edges in the graphG. As shown in Figure 6(a), the weight of the edge does not reflect the turning cost. For example, the cost for path a⟶b⟶c is equal to the cost for path a⟶b⟶d, and the cost of turning at vertex b is not considered.Figure 6
The improvements of modeling.
(a)
Original graph(b)
A gadget(c)
Expansive graph(d)
Gadget-based graphTo accurately express the turning cost of the UAV, we improve the original graph as follows.We expand the vertices in the original graph as shown in Figure6(b), and a vertex is expanded into 8 vertices, representing 8 different directions, respectively. We call the 8 vertices as a gadget and establish a weighted edge between any two vertices in a gadget. The weight of each edge in a gadget means that the UAV takes corresponding costs at different turn angles. The time cost weight Ttij,ik and energy cost weight Etij,ik of any two vertices ij,ik in a gadget are defined as
(11)Ttij,ik=Tacc+minn,8−n×45α+Tdec,ifj−k=nor8−n,n∈1,2,3,4,(12)Etij,ik=Eacc+minn,8−n×45β+Edec,ifj−k=nor8−n,n∈1,2,3,4.By introducing the concept of gadget, we establish an expansive graph as shown in Figure6(c). However, the cost for paths a2⟶b6⟶b7⟶f3 and a2⟶b6⟶b1⟶e5 is unreasonable. It cannot reflect the fact that the UAV will spend more time and energy costs as the turn angles increase.To solve the above problem, we transform Figures6(c) and 6(d). As shown in Figure 6(d), we establish weighted directed edges between two vertices in the adjacent gadgets that represent the same direction. The weights of these edges represent the cost of straight flights. In this way, the cost for paths a2⟶b2⟶b7⟶f7 and a2⟶b2⟶b1⟶e1 consists with the fact. Thus, the cost of making turns can be expressed accurately by weighted directed edges.


### 5.4. Gadget-Based Graph Model

The gadget-based graph is a weighted directed graphG=V,E,W. V represents the set of all vertices (a gadget contains 8 vertices), and we use Gη⊂V to denote the gadget. E represents the set of all edges, including the weighted directed edges between adjacent gadgets and the 28 weighted edges inside each gadget. W (including WT, WE) represent the weights on each edge, WT represents the time cost on each edge, and WE represents the energy cost on each edge. Among them, WT∈Ts,Tt,WE∈Es,Et.On the above graphG, a loop represents a flight path for UAV, and the sum of its weights is equal to the total time or energy cost. In the next section, we will present our solution to find the shortest loop passing all gadgets on the graph.


## 5.1. Graph Representation of Coverage Tasks

To approach the CMFCPP problem, we divide the given area with multiple obstacles into several square grids as shown in Figure4(a). The gray grids represent no-fly zones with obstacles that the UAV cannot pass, and the nongray grids represent free zones that the UAV can pass. By connecting the centers of adjacent nongray grids, we model the irregular-shaped area by a graph G=V,E as shown in Figure 4(b), where V represents the set of all vertices and each vertex denotes a nongray grid. E represents the set of all edges, and each edge eij denotes the path that the UAV can pass through. To complete coverage tasks, the UAV needs to visit all the vertices.Figure 4
Graph representation of coverage tasks.
(a)
The area of interest(b)
Graph representationAs described above, the UAV has two choices of actions, i.e., straight flight and making a turn. To model the actions, we assign the costs of the actions as the weights of corresponding edges in the graph. Then, by finding a loop on the graph, we can obtain a sequence of actions for the UAV to perform. Finally, the minimum cost is attained by minimizing the summed weights of the visited edges. To achieve this, we should ensure that the cost of UAV’s actions is precisely modeled by the weight of edges. We next present the modeling of the cost for a straight flight and making a turn in detail.


## 5.2. The Cost Model of Straight Flight and Making a Turn

As shown in Figure5, the UAV has a flight path a⟶k⟶m⟶b⟶n⟶c. The speed of constant-speed phases is v0. Let xi,yi denote the coordinates of vertex i, vi denote the speed of UAV at vertex i, and di,j denote the distance between any two vertices i,j. Moreover, dak and dbn are equal to Sacc, and dmb is equal to Sdec.Figure 5
The cost model of straight flight and making a turn.The Cartesian coordinate distance between any two verticesi and j can be obtained by the following equation:
(1)dij=xi−xj2+yi−yj2.


### 5.2.1. The Cost Model of Straight Flight

During the straight flight of the UAV from vertexa to vertex b, we need to confirm the flight speed of the UAV at vertex a and vertex b to determine whether this process is accompanied by deceleration or acceleration. We use γ and δ to represent the time and energy costs of the UAV moving one meter. Moreover, we denote the time and energy costs of acceleration by Tacc and Eacc and use Tdec and Edec to denote the time and energy costs of deceleration.We get the time costTab and energy cost Eab of the UAV in this process as follows:
(2)Tab=γdam,ifva=v0,Tacc+γdkm,ifva=0,(3)Eab=δdam,ifva=v0,Eacc+δdkm,ifva=0.Finally, we denote the time costTs and energy cost Es of the UAV passing through the adjacent grids by
(4)Ts=Tab,ifeabistraversed,∞,otherwise,(5)Es=Eab,ifeabistraversed,∞,otherwise.


### 5.2.2. The Cost Model of Making a Turn

During the process of making a turn, we represent the time and energy costs of the UAV turning one degree byα and β. By calculating the lengths of the sides eab, ebc, and eac and then using the Law of Cosines, the angle of turn at vertex b can be calculated by θabc.We get the time costTabc and energy cost Eabc of the turning process m⟶b⟶n as follows:
(6)Tabc=Tdec+180×θabcπ×α+Tacc,(7)Eabc=Edec+180×θabcπ×β+Eacc,(8)θabc=π−cos−1dab2+dbc2−dac22dabdbc.Therefore, we denote the time costTt and energy cost Et of the UAV making a turn by
(9)Tt=Tabc,ifeab,ebcistraversed,∞,otherwise,(10)Et=Eabc,ifeab,ebcistraversed,∞,otherwise.


## 5.2.1. The Cost Model of Straight Flight

During the straight flight of the UAV from vertexa to vertex b, we need to confirm the flight speed of the UAV at vertex a and vertex b to determine whether this process is accompanied by deceleration or acceleration. We use γ and δ to represent the time and energy costs of the UAV moving one meter. Moreover, we denote the time and energy costs of acceleration by Tacc and Eacc and use Tdec and Edec to denote the time and energy costs of deceleration.We get the time costTab and energy cost Eab of the UAV in this process as follows:
(2)Tab=γdam,ifva=v0,Tacc+γdkm,ifva=0,(3)Eab=δdam,ifva=v0,Eacc+δdkm,ifva=0.Finally, we denote the time costTs and energy cost Es of the UAV passing through the adjacent grids by
(4)Ts=Tab,ifeabistraversed,∞,otherwise,(5)Es=Eab,ifeabistraversed,∞,otherwise.


## 5.2.2. The Cost Model of Making a Turn

During the process of making a turn, we represent the time and energy costs of the UAV turning one degree byα and β. By calculating the lengths of the sides eab, ebc, and eac and then using the Law of Cosines, the angle of turn at vertex b can be calculated by θabc.We get the time costTabc and energy cost Eabc of the turning process m⟶b⟶n as follows:
(6)Tabc=Tdec+180×θabcπ×α+Tacc,(7)Eabc=Edec+180×θabcπ×β+Eacc,(8)θabc=π−cos−1dab2+dbc2−dac22dabdbc.Therefore, we denote the time costTt and energy cost Et of the UAV making a turn by
(9)Tt=Tabc,ifeab,ebcistraversed,∞,otherwise,(10)Et=Eabc,ifeab,ebcistraversed,∞,otherwise.


## 5.3. The Improvements of Modeling

In the previous subsection, we have formalized the cost of straight flight and making a turn. However, the cost of the turning process cannot be expressed by the weight of edges in the graphG. As shown in Figure 6(a), the weight of the edge does not reflect the turning cost. For example, the cost for path a⟶b⟶c is equal to the cost for path a⟶b⟶d, and the cost of turning at vertex b is not considered.Figure 6
The improvements of modeling.
(a)
Original graph(b)
A gadget(c)
Expansive graph(d)
Gadget-based graphTo accurately express the turning cost of the UAV, we improve the original graph as follows.We expand the vertices in the original graph as shown in Figure6(b), and a vertex is expanded into 8 vertices, representing 8 different directions, respectively. We call the 8 vertices as a gadget and establish a weighted edge between any two vertices in a gadget. The weight of each edge in a gadget means that the UAV takes corresponding costs at different turn angles. The time cost weight Ttij,ik and energy cost weight Etij,ik of any two vertices ij,ik in a gadget are defined as
(11)Ttij,ik=Tacc+minn,8−n×45α+Tdec,ifj−k=nor8−n,n∈1,2,3,4,(12)Etij,ik=Eacc+minn,8−n×45β+Edec,ifj−k=nor8−n,n∈1,2,3,4.By introducing the concept of gadget, we establish an expansive graph as shown in Figure6(c). However, the cost for paths a2⟶b6⟶b7⟶f3 and a2⟶b6⟶b1⟶e5 is unreasonable. It cannot reflect the fact that the UAV will spend more time and energy costs as the turn angles increase.To solve the above problem, we transform Figures6(c) and 6(d). As shown in Figure 6(d), we establish weighted directed edges between two vertices in the adjacent gadgets that represent the same direction. The weights of these edges represent the cost of straight flights. In this way, the cost for paths a2⟶b2⟶b7⟶f7 and a2⟶b2⟶b1⟶e1 consists with the fact. Thus, the cost of making turns can be expressed accurately by weighted directed edges.


## 5.4. Gadget-Based Graph Model

The gadget-based graph is a weighted directed graphG=V,E,W. V represents the set of all vertices (a gadget contains 8 vertices), and we use Gη⊂V to denote the gadget. E represents the set of all edges, including the weighted directed edges between adjacent gadgets and the 28 weighted edges inside each gadget. W (including WT, WE) represent the weights on each edge, WT represents the time cost on each edge, and WE represents the energy cost on each edge. Among them, WT∈Ts,Tt,WE∈Es,Et.On the above graphG, a loop represents a flight path for UAV, and the sum of its weights is equal to the total time or energy cost. In the next section, we will present our solution to find the shortest loop passing all gadgets on the graph.


## 6. Problem Solving

In this section, we formulate the CMFCPP problem based on the graphG. Then, we transform the problem to GTSP, which can be solved efficiently using the GLNS solver.


### 6.1. CMFCPP Formulation

Let a nonnegative integer variableMab denote the number of times UAV moves from vertex a to vertex b, and let the binary decision variable Da∈0,1 denote whether vertex a is visited and it is defined for each vertex a as
(13)Da=0,if∑b∈VMab+∑c∈VMca=0,1,if∑b∈VMab+∑c∈VMca≥1.Our goal is to minimize the time cost of the energy-constrained UAV to complete coverage tasks. In other words, we need to find a loop passing all widgets with minimum time cost and less energy cost thanEmax. Since a loop on the graph can be represented by a sequence of edges between vertices, the total cost of the loop is as follows:
(14)∑a,b∈VWTabMab,for∑a,b∈VWEabMabEmax.Next, we discuss the constraints that need to be met to solve the above problem.(1)
Gadget coverage constraint: we require each gadget in the gadget-based graph G to be visited at least once. Thus, the gadget coverage constraint is expressed as(15)∑a∈GηDa≥1,∀Gη⊂V(2)
Flow conservation constraint: for each vertex in the graph, the inflow should be consistent with the outflow, so the flow conservation constraint is as follows:(16)∑a∈V\bMab=∑c∈V\a,bMbc,∀b∈V(3)
Subtour elimination constraint: to avoid the generation of subtours, we set the following constraint to eliminate subtours:(17)∑a∈Gη,b∈V\GηMab+Mba≥1,∀Gη⊂V


### 6.2. Transform CMFCPP into GTSP

However, the above constraints cannot make exactly one vertex to be visited for each gadget. To solve this problem, we propose to transform the graphG into a complete graph by assigning the weight between any two vertices, which can be calculated using the Dijkstra algorithm. Then, the UAV can find the minimum weight of an edge between any two vertices with the total cost unchanged. Now, we require exactly one vertex to be visited for each gadget:
(18)∑a∈GηDa=1,∀Gη⊂V.In this way, we ensure that the solution visits each gadget once and there always exists a feasible solution. The resulted objective function and constraints now exactly model our CMFCPP problem, summarized as follows:(19)min∑a,b∈VWTabMab,for∑a,b∈VWEabMab<Emaxs.t.∑a∈GηDa=1,∀Gη⊂V∑a∈V\bMab=∑c∈V\a,bMbc,∀b∈V∑a∈Gη,b∈V\GηMab+Mba≥1,∀Gη⊂VMab∈ℕ,Da∈0,1Our goal is to find a path that traverses one vertex in each gadget and spends the minimum time cost for UAV to complete coverage tasks along this path without exhausting all of the energy as shown in Equation (19). Therefore, the CMFCPP problem is equivalent to the first type of generalized travelling salesman problem (GTSP), which is obviously a NP-hard problem.We propose a time-efficient coverage path planning (TECPP) algorithm to solve the CMFCPP problem as shown in Algorithm1. TECPP can give a feasible solution for an instance of GTSP at an acceptable cost (i.e., computation time and space). We can find an efficient flight path that takes the minimum time cost by traversing a vertex in each gadget, which is the solution to the problem. Finally, we use the GLNS [17] solver to solve the generalized traveling salesman problem (GTSP) in this algorithm.Algorithm 1: TECPP.
Input: Two-dimensional map of the interest area mapCoverage of all obstruction-free areasCoverageOutput: An efficient flight path of UAV path1: initializemap and divide map into square grids set S2: set the obstacle-free grids set asF, F⊆S3:for each grid node g in Fdo4:   expendg into 8 vertices v1-v85:   addv1-v8 to V6:end for7:for each vertex v in Vdo8:for each neighbor n of gdo9:evn⟵anedge10:     addevn to E11:wvn⟵energyandtimecostforonemotion12:     addwvn to W13:end for14:end for15: Directed Weighted GraphGV,E,W⟵V,E,W16:Vnum⟵V17:for each vertex v in Vdo18:Dijkstrav to get all minimum cost array cVnum19:wv⟵cv20:for each vertex v′ in Vdo21:     addevv′ to E22:end for23:end for24:for each vertex v in Vdo25:if!vinCoveragethen26:     remove vertexv from G27:end if28:end for29:coordPoints⟵GLNSG,vertSet30:path⟵ConvertToPathG,coordPoints31:returnpath


## 6.1. CMFCPP Formulation

Let a nonnegative integer variableMab denote the number of times UAV moves from vertex a to vertex b, and let the binary decision variable Da∈0,1 denote whether vertex a is visited and it is defined for each vertex a as
(13)Da=0,if∑b∈VMab+∑c∈VMca=0,1,if∑b∈VMab+∑c∈VMca≥1.Our goal is to minimize the time cost of the energy-constrained UAV to complete coverage tasks. In other words, we need to find a loop passing all widgets with minimum time cost and less energy cost thanEmax. Since a loop on the graph can be represented by a sequence of edges between vertices, the total cost of the loop is as follows:
(14)∑a,b∈VWTabMab,for∑a,b∈VWEabMabEmax.Next, we discuss the constraints that need to be met to solve the above problem.(1)
Gadget coverage constraint: we require each gadget in the gadget-based graph G to be visited at least once. Thus, the gadget coverage constraint is expressed as(15)∑a∈GηDa≥1,∀Gη⊂V(2)
Flow conservation constraint: for each vertex in the graph, the inflow should be consistent with the outflow, so the flow conservation constraint is as follows:(16)∑a∈V\bMab=∑c∈V\a,bMbc,∀b∈V(3)
Subtour elimination constraint: to avoid the generation of subtours, we set the following constraint to eliminate subtours:(17)∑a∈Gη,b∈V\GηMab+Mba≥1,∀Gη⊂V


## 6.2. Transform CMFCPP into GTSP

However, the above constraints cannot make exactly one vertex to be visited for each gadget. To solve this problem, we propose to transform the graphG into a complete graph by assigning the weight between any two vertices, which can be calculated using the Dijkstra algorithm. Then, the UAV can find the minimum weight of an edge between any two vertices with the total cost unchanged. Now, we require exactly one vertex to be visited for each gadget:
(18)∑a∈GηDa=1,∀Gη⊂V.In this way, we ensure that the solution visits each gadget once and there always exists a feasible solution. The resulted objective function and constraints now exactly model our CMFCPP problem, summarized as follows:(19)min∑a,b∈VWTabMab,for∑a,b∈VWEabMab<Emaxs.t.∑a∈GηDa=1,∀Gη⊂V∑a∈V\bMab=∑c∈V\a,bMbc,∀b∈V∑a∈Gη,b∈V\GηMab+Mba≥1,∀Gη⊂VMab∈ℕ,Da∈0,1Our goal is to find a path that traverses one vertex in each gadget and spends the minimum time cost for UAV to complete coverage tasks along this path without exhausting all of the energy as shown in Equation (19). Therefore, the CMFCPP problem is equivalent to the first type of generalized travelling salesman problem (GTSP), which is obviously a NP-hard problem.We propose a time-efficient coverage path planning (TECPP) algorithm to solve the CMFCPP problem as shown in Algorithm1. TECPP can give a feasible solution for an instance of GTSP at an acceptable cost (i.e., computation time and space). We can find an efficient flight path that takes the minimum time cost by traversing a vertex in each gadget, which is the solution to the problem. Finally, we use the GLNS [17] solver to solve the generalized traveling salesman problem (GTSP) in this algorithm.Algorithm 1: TECPP.
Input: Two-dimensional map of the interest area mapCoverage of all obstruction-free areasCoverageOutput: An efficient flight path of UAV path1: initializemap and divide map into square grids set S2: set the obstacle-free grids set asF, F⊆S3:for each grid node g in Fdo4:   expendg into 8 vertices v1-v85:   addv1-v8 to V6:end for7:for each vertex v in Vdo8:for each neighbor n of gdo9:evn⟵anedge10:     addevn to E11:wvn⟵energyandtimecostforonemotion12:     addwvn to W13:end for14:end for15: Directed Weighted GraphGV,E,W⟵V,E,W16:Vnum⟵V17:for each vertex v in Vdo18:Dijkstrav to get all minimum cost array cVnum19:wv⟵cv20:for each vertex v′ in Vdo21:     addevv′ to E22:end for23:end for24:for each vertex v in Vdo25:if!vinCoveragethen26:     remove vertexv from G27:end if28:end for29:coordPoints⟵GLNSG,vertSet30:path⟵ConvertToPathG,coordPoints31:returnpath


## 7. Simulations

We perform three sets of experiments to evaluate the performance of TECPP for the CMFCPP problem. In terms of time cost, energy cost, and calculation time, we compare TECPP with a baseline algorithm and the Lin-Kernighan heuristic algorithm for drones (LKH-D) in several scenarios.In the baseline, we use the traditional coverage path planning algorithm [13] as a baseline approach. This baseline algorithm considers the number of turns and obtains a path that reduces energy consumption by minimizing the number of turns.In these experiments, we set the appropriate simulation parameters for our gadget-based graph model as shown in Table1. It is assumed that the UAV with limited energy performs coverage task in the region of interest shown in Figure 4(a), as shown in Figure 7, and the optimal coverage path of each algorithm is given.Table 1
The cost parameters of UAV.
ParameterExplanationValuev0The speed of constant-speed phases2 m/sγTime cost parameter (straight flight)0.5 s/mδEnergy cost parameter (straight flight)0.12 KJ/mαTime cost parameter (making a turn)0.02 s/degβEnergy cost parameter (making a turn)0.018 KJ/degSaccAcceleration distance0.31 mSdecDeceleration distance0.22 mTaccTime cost of acceleration0.4 sTdecTime cost of deceleration0.3 sEaccEnergy cost of acceleration0.04 KJEdecEnergy cost of deceleration0.03 KJFigure 7
Optimal paths planned by TCC-CPP, LKH-D, and baseline algorithms.
(a)
TECPP(b)
LKH-D(c)
Baseline


### 7.1. The Impact of Area Size

In this subsection, we study the impact of area size on time cost, energy cost, and computation time. We show the performances of the compared algorithms for simple rectangular areas with dimensions3×5, 5×8, 8×12, and 12×16 in Figure 8. The grids in each of these areas are 2m×2m squares without obstacles.Figure 8
The impact of area size on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation timeFigure8(a) shows how the time cost scales with the number of grids for each algorithm, and Figure 8(b) shows the energy cost under each algorithm. As would be expected, TECPP saves more time than the baseline and LKH-D as the number of grids increases. In addition, TECPP achieves a comparable performance to LKH-D and does better than the baseline in terms of the energy cost. The reason is that TECPP greatly optimizes the time cost under the constraint of energy and has high scalability. Although the baseline and LKH-D achieve comparable performance to TECPP for small areas, TECPP saves at least 24.3% of time as the increase of area size. Figure 8(c) shows TECPP is one order of magnitude faster than the baseline for large area.


### 7.2. The Impact of Obstacles

To elucidate the impact of obstacles on time cost, energy cost, and computation time, we generate four8×12 (2m×2m) rectangular areas with different numbers of obstacles as illustrated in Figure 9.Figure 9
Rectangular grid areas used to evaluate TECPP.
(a)
Area 1(b)
Area 2(c)
Area 3(d)
Area 4Figure10(a) shows the time cost for the compared algorithms when they are applied to the four areas defined in Figure 9, and Figure 10(b) shows the corresponding energy cost. In the four scenarios, TECPP saves at least 24.9% of time compared to LKH-D and 33.4% of time compared to the baseline. Figure 10(b) shows that TECPP is also better at saving energy than LKH-D as the number of obstacles increases. The reason is that our gadget-based graph model takes the impact of obstacles into account. As shown in Figure 10(c), LKH-D achieves comparable performance to TECPP and these two algorithms save more calculation time than baseline as the number of obstacles increases.Figure 10
The impact of obstacles on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation time


### 7.3. The Impact of Grid Size

In this subsection, to understand the impact of grid size on the time cost, energy cost, and computation time, we set the size of all grids in Area 4 of Figure9(d) as 1m×1m, 2m×2m, 3m×3m, and 4m×4m, respectively. As shown in Figure 11, we compare the performance of TECPP, baseline, and LKH-D in the above four cases. Figure 11(a) shows how the time cost scales with grid size for the compared algorithms, and Figure 11(b) shows the energy cost under each algorithm.Figure 11
The impact of grid size on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation timeFigure11(a) shows that TECPP saves at least 21.6% of time than LKH-D and 49.4% of time than the baseline as the grid size increases. Although LKH-D spends the least energy cost compared to the baseline and TECPP as shown in Figure 11(b), TECPP saves more time at a low energy cost as the grid size increases. Figure 11(c) shows that TECPP has a slightly better performance than LKH-D in speed, and the baseline is much slower than the other two algorithms.In summary, our TECPP takes into account the impact of obstacles and the cost of turns for the CMFCPP problem, which saves at least 21.6% of time and has a faster speed compared to the existing coverage path planning algorithms.


## 7.1. The Impact of Area Size

In this subsection, we study the impact of area size on time cost, energy cost, and computation time. We show the performances of the compared algorithms for simple rectangular areas with dimensions3×5, 5×8, 8×12, and 12×16 in Figure 8. The grids in each of these areas are 2m×2m squares without obstacles.Figure 8
The impact of area size on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation timeFigure8(a) shows how the time cost scales with the number of grids for each algorithm, and Figure 8(b) shows the energy cost under each algorithm. As would be expected, TECPP saves more time than the baseline and LKH-D as the number of grids increases. In addition, TECPP achieves a comparable performance to LKH-D and does better than the baseline in terms of the energy cost. The reason is that TECPP greatly optimizes the time cost under the constraint of energy and has high scalability. Although the baseline and LKH-D achieve comparable performance to TECPP for small areas, TECPP saves at least 24.3% of time as the increase of area size. Figure 8(c) shows TECPP is one order of magnitude faster than the baseline for large area.


## 7.2. The Impact of Obstacles

To elucidate the impact of obstacles on time cost, energy cost, and computation time, we generate four8×12 (2m×2m) rectangular areas with different numbers of obstacles as illustrated in Figure 9.Figure 9
Rectangular grid areas used to evaluate TECPP.
(a)
Area 1(b)
Area 2(c)
Area 3(d)
Area 4Figure10(a) shows the time cost for the compared algorithms when they are applied to the four areas defined in Figure 9, and Figure 10(b) shows the corresponding energy cost. In the four scenarios, TECPP saves at least 24.9% of time compared to LKH-D and 33.4% of time compared to the baseline. Figure 10(b) shows that TECPP is also better at saving energy than LKH-D as the number of obstacles increases. The reason is that our gadget-based graph model takes the impact of obstacles into account. As shown in Figure 10(c), LKH-D achieves comparable performance to TECPP and these two algorithms save more calculation time than baseline as the number of obstacles increases.Figure 10
The impact of obstacles on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation time


## 7.3. The Impact of Grid Size

In this subsection, to understand the impact of grid size on the time cost, energy cost, and computation time, we set the size of all grids in Area 4 of Figure9(d) as 1m×1m, 2m×2m, 3m×3m, and 4m×4m, respectively. As shown in Figure 11, we compare the performance of TECPP, baseline, and LKH-D in the above four cases. Figure 11(a) shows how the time cost scales with grid size for the compared algorithms, and Figure 11(b) shows the energy cost under each algorithm.Figure 11
The impact of grid size on the time cost, energy cost, and computation time.
(a)
Time cost(b)
Energy cost(c)
Computation timeFigure11(a) shows that TECPP saves at least 21.6% of time than LKH-D and 49.4% of time than the baseline as the grid size increases. Although LKH-D spends the least energy cost compared to the baseline and TECPP as shown in Figure 11(b), TECPP saves more time at a low energy cost as the grid size increases. Figure 11(c) shows that TECPP has a slightly better performance than LKH-D in speed, and the baseline is much slower than the other two algorithms.In summary, our TECPP takes into account the impact of obstacles and the cost of turns for the CMFCPP problem, which saves at least 21.6% of time and has a faster speed compared to the existing coverage path planning algorithms.


## 8. Conclusion

A time-efficient coverage path planning (TECPP) algorithm is proposed to solve the CMFCPP problem in this paper. We build a novel gadget-based graph model that takes into account the impact of obstacles, which formalizes the time and energy costs of the flight path including straight flights and making turns (deceleration, turning, and acceleration). Finally, we transform the CMFCPP problem to GTSP and use the efficient GLNS solver to solve the problem. Experimental results show that compared with the existing coverage path planning algorithms, TECPP saves at least 21.6% of time.As a future work, we intend to explore the path planning problem of UAV covering multiple nonadjacent target areas.



---

*Source: 5905809-2022-05-19.xml*