Keywords

1 Introduction

In recent years, as a reusable aircraft, UAVs have become more and more widely used in many application fields, such as aerial surveying and mapping [1], disaster search and rescue with many advantages such as simple structure, small size, high operability, and powerful performance [2], smart farm [3], wildfire tracking [4], cloud monitoring [5], building maintenance [6], pipeline inspection [7] and many other fields. The key difficulty in all such applications is the CPP problem [8], which was first proposed in the path planning of the sweeping robot [9] to allow the robot to perform cleaning tasks covering a certain area; Under the development of robots, this problem has been extended to perform exploration tasks in unfamiliar underwater environments [10]; Based on the matured UAV technology, UAVs have been further expanded to be applied to various tasks such as search and rescue in the area, aerial photography and so on.

UAVs are small, light, and flexible to be used, but due to battery technology, their endurance has been limited. Therefore, the endurance anxiety can be alleviated to a certain extent by reasonable path planning. Most of the existing ground station software is oriented towards completing the established tasks, and less consideration is given to the CPP optimization problem of the flight process. Based on the existing research [11,12,13,14,15,16,17], a detailed discussion of UAV CPP technology was given in the paper.

On the basis of comprehensive collection and reading of existing literature, the main tasks include: the defineing of the full coverage path planning; secondly, three aspects of coverage problem are discussed: decomposition, traversal strategy, and trajectory optimization; finally, the shortcoming of the UAV CPP problem and the further problems need to be solved are pointed out.

2 Definition of Full Coverage Path Planning

The main task of traditional path planning is to find the shortest path from point to point when there are no obstacles in the middle of the demarcated area. Different from traditional path planning, in the path planning with full coverage of the area, it is necessary to ensure that the robot traverses every task point in the entire area and completes the task requirements. The problem of UAV full coverage path planning can be defined as follows:

  • * The UAV must traverse every mission point in the entire mission area

  • * UAVs must ensure a certain overlap rate between the traversed areas

  • * The UAV must avoid all obstacles to ensure its own safety

  • * The planned UAV path is as continuous, simple and smooth as possible

  • * As far as possible, plan a ‘best’ path in the existing environment

The goal of regional full coverage path planning is to optimize the overall efficiency of the UAV system on the basis of completing the task to the greatest extent. According to the task requirements, the regional full coverage problem is essentially a multi-constrained multi-objective optimization problem and the optimal solution need to be found in a reasonable time.

In view of the fact that the battery problem has always been a pain point of UAV, energy consumption or flight time is often considered to be the most important factor among flight time, passing distance, turning times and hovering time.

3 Coverage Area Decomposition

For UAV coverage missions, the first thing is to define the coverage area. UAV coverage area has the following classification criteria: area shape, area size and whether the area information is known. If the shape of the region is regular, the region can be traversed off-line in a simple round-trip manner without decomposition. If the shape of the region is complex and contains obstacles, the obstacles need to be marked and modeled to decompose the region.

The region can be divided into two types according to the size: small region and large region. If the area is too large for a single UAV to complete, multiple traversal by a single UAV or cooperative strategy of multiple UAVs can also be considered.

The region can be divided into three types according to the region shape: regular rectangular region, convex polygon region and concave polygon region. The ground station software can customize the shape of the UAV’s flying area, and add no-fly areas or obstacle areas as needed.

The region decomposition method can be divided into online and off-line methods according to the regional information is known sufficiently. Online refers to the use of UAV’s own sensors to sense the surrounding environment when the global information of the region is unknown or partially known, for example, robot indoor Simultaneous Localization and Mapping (SLAM). Off-line is to transmit the planned path to the UAV when the global information of the area (including the shape of the area, the position and shape of the obstacle, etc.) is known, and the UAV traverses according to the established route.

In addition, the coverage area can also be divided into two-dimensional and three-dimensional space according to the UAV flight altitude. If the UAV flies at a fixed altitude above the building and below the altitude limit, the coverage area becomes a two-dimensional flat space. If the plant protection UAV needs to perform tasks such as pesticide spraying in rugged fruit trees and gardens, it needs to adjust the altitude in real time according to the airborne sensors, and the coverage area becomes a 3D space.

Generally, classical decomposition methods can be divided into three categories: non-decomposition method, exact cellular decomposition method and approximate decomposition method, as shown in Fig. 1.

Fig. 1.
figure 1

Methods of coverage area decomposition

Full size image

3.1 Exact Cellular Decomposition

For the complicated area, the exact cellular decomposition method needs to accurately outline the shape of the obstacle. After decomposition, the target area is divided into multiple independent small areas and the coverage task of the whole target area can be completed by the accomplishment of all small areas.

The trapezoidal decomposition method first proposed by Latombe [18] to model the obstacle area that the UAV cannot fly over (No Fly Zone, NFZ) into polygonal area. By the trapezoidal decomposition, the target area can be divided into multiple trapezoidal units, and the UAV can cover each unit through simple round-trip traversal. Each decomposed unit was numbered according to the sequence, and an adjacency graph was established according to the adjacency relation of the unit. The adjacency graph was traversed according to the depth-first traversal method to ensure the complete coverage of the whole area.

Choset [19] proposed the Boustrophedon decomposition based on the trapezoidal decomposition. The decomposition process is as follows: Define a scan line parallel to the boundary of the area and move from left to right. When the scan line intersects the boundary of the obstacle, the swept free area is called Old Cell. The obstacle divides the free area into two New cells, and then the IN decomposition operation is triggered. The scan line continues to move, and the two New cells are redefined as Old cells, until the next time the scan line intersects the boundary of the obstacle, the two Old cells will be combined into a New Cell, and then the OUT decomposition operation will be triggered. The scan line continues to move until a region boundary is encountered. Each generation of New Cell and Old Cell marks the generation of Cell dividing line. The decomposition effects of trapezoidal decomposition and Boustrophedon decomposition method are shown in Fig. 2.

Fig. 2.
figure 2

Comparison of trapezoidal and boustrophedon decomposition

Full size image

Choset [11] proposed a unit decomposition method based on Morse function, which Boustrophedon decomposition. In fact, Choset proved that Boustrophedon decomposition is a special case of Morse decomposition. The Morse decomposition does not necessarily deal with polygons, but with curved surfaces or spikes. Theoretically, the Morse decomposition method can be generalized to decompose the region containing any n-dimensional spatial obstacles.

Compared with the trapezoidal decomposition method, Boustrophedon decomposition can decompose fewer units, the connection between units need less consideration. Morse decomposition is more general in its requirements for obstacle shapes than the previous two, and can handle more complex situations.

3.2 Approximate Decomposition

The decomposition method based on network grid was proposed by Elfes and Moravec [15]. The size and shape of grid can be defined according to the visual area of UAV, The grid size can be defined based on the size of the small rectangle. Reducing the grid size makes NFZ modeling more accurate, but also increases memory usage.

The approximate cellular decomposition method is used to simply rasterize the entire target area. When modeling NFZ, the entire grid should be defined as an obstacle area even if there are only a few obstacles in the grid. The whole area is divided into obstacle area and free area according to whether the grid is occupied by obstacles, as shown in Fig. 3. After the approximate modeling of obstacles, some free areas are blurred as obstacle areas, so the complete coverage cannot be guaranteed from the very beginning. Every center point of the rasterized map is the central position of the UAV. As long as the UAV completes the task of traversing every center point of the raster in the free area, it will complete the entire coverage task. After the above processing, the coverage problem is modeled as a classic Traveling Salesman Problem (TSP) [20], for which there are many heuristic algorithms can be exploited.

Fig. 3.
figure 3

Network grid decomposition method

Full size image

4 Traversal Strategies

The traversal strategy determines which path the UAV takes to complete the entire mission. Traversal strategies can be adaptively divided into the following two types: non-heuristic traversal strategy and heuristic traversal strategy. Non-heuristic traversal means that the UAV itself is aware of the environment and allows the UAV to execute in a certain way according to the pre-planned path. Non-heuristic traversal methods mainly include round-trip traversal method and spiral traversal method. Heuristic traversal means that when planning a path, there are some uncertain factors and mechanisms as feedback to plan the path. Heuristic traversal methods are generally based on network grid modeling and are used in scenarios where CPP is modeled as a TSP problem.

4.1 Non-heuristic Traversal Strategy

The non-heuristic traversal method uses deterministic algorithm to plan UAV path. The two most commonly used methods are round-trip and spiral. Round-trip traversal [19] is inspired by cattle ploughing and lawn mowers, which covers an area in a round-trip cruise mode. Spiral traversal covers an area in a spiral to the center or to the outside of the area boundary, which in some environments is superior to round-trip traversal.

Round-trip Traversal. Round-trip paths are suitable for regular rectangular regions, choosing the long side as the traversal direction can reduce the number of turns, because the energy consumed by the UAV to turn is higher than that consumed by the straight-line flight. In the real scene, after the round-trip path is used to traverse the region, the distance between the stop point and the start point is far away, so the return journey to the starting point will waste a lot of energy. If the return path can be used as task point, as shown in Fig. 4(a), more energy can be saved [21].

Fig. 4.
figure 4

Comparison of different traversal strategy

Full size image

Spiral Traversal. Choi [22] used a sensor-based helical traversal method to cover the target area by decomposed the approximate units of the target area, and introduced constrained inverse distance transformation to connect simple helical paths for the first time. Experimental proved that the algorithm had good robustness in complex areas.

Gabriely [23] proposed a method based on Spiral Spanning Tree (STC), and discussed the algorithm performance of “offline”, “online” and “ant" when regional information is known. Taua M [24] proposed a planning method of spiral curve in literature. The main idea is to use the region that can be photographed by the camera as the central track point to construct helices along the side centroid of polygons. Compared with the round-trip traversal method, the spiral traversal method has more advantages for tasks like 3D reconstruction, but for conventional tasks, the traversal strategy needs to be selected according to the characteristics of the task.

4.2 Heuristic Traversal Strategy

Heuristic traversal method is mainly based on network grid method. After the target area is divided into small network grids, the full coverage path planning problem is transformed into TSP problem. CPP can be solved indirectly through TSP, and the typical algorithms to solve the former problem include genetic algorithm, ant colony algorithm, neural network algorithm and so on.

Sadek [25] proposed an online CPP problem solution based on sensors using Genetic algorithm (GA) and Dynamic programming (DP). In his paper, the CPP problem is decomposed into several sub-problems by DP technique, and then multi-objective GA is applied to each sub-problem to find its optimal solution. Tobias [26] defined four basic movements with different costs of straight line, left turn, right turn and U-turn after rasterization of the coverage area network, set the cost function to evaluate the path, and finally used GA to find the best traversal strategy of the coverage area.

Ant Colony optimization algorithm (ACO) was applied by Kuiper [27] to the CPP problem of multiple UAVs. These UAVs share a virtual map containing pheromones, and the probability visited by UAVs is high in the pheromone concentration areas and low in the other area. Areas with low pheromone concentrations will guide the UAV through. Rosalie [28] combined ACO algorithm and chaotic dynamics to introduce a coverage algorithm for regional detection scenarios, which improved the coverage of UAV clusters and was verified on ROS and robot simulator V-REP.

Yang [29] established a dynamic Neural Network (NN) architecture to solve the CPP problem, whose dynamic neural activity represents the dynamic changing environment. By properly defining the external input and internal neural connections from different environments, the neural activity in the free region and NFZ region stays at the peak or trough position in the network, respectively. The free region attracts the UAV in the global state space by neural network propagation, while the NFZ region has only local effects to avoid collisions. Based on the dynamic activity of the neural network and the current state of the UAV, the coverage path planning of the UAV was carried out in real time without collision.

Jalil Modares [30] designed a power sensor installed on a multi-rotor UAV, and tested the influence of UAV’s distance, speed and turning angle on UAV’s energy consumption respectively, established a linear model of energy on distance, speed and turning Angle, and adapted the traditional LKH algorithm to solve the TSP problem after grid modeling. The energy consumption is directly used as feedback function to optimize the path, and a better power-based traversal is obtained compared with round-trip and spiral traversal.

It is not difficult to find that the heuristic traversal method can not only traverse the known information area offline, but also has the ability to traverse the unknown information area online. Especially for the complex area, the heuristic traversal method can involve UAV’s own factors and regional information, so that the planned path is more in line with the application scenario.

5 Trajectory Optimization

The most important concern of CPP problem is the coverage efficiency, which decreases with the increase of total task time. Through flight trajectory optimization, the smoothness of flight path can be increased, and the UAV can track the trajectory without hovering, decelerating and turning sharply.

In order to plan a flight trajectory that conforms to UAV dynamics constraints, rigid body characteristics of UAV, such as minimum turning radius, must be considered when planning flight path points. Some UAV ground station software automatic planning of track is not in line with the expectations, such as the DJI UAV with return type by U type turning part, turning process is shown in Fig. 5, in AF on the vertical direction, from A point began to slow, slow to a speed 0 when arrived F point, Turn 90\(\circ \) right at point F, FC segment start to accelerate from 0 and slow down at CG segment, After turning 90\(\circ \) left at a speed of 0 at G point, accelerate straight along GE direction.

Fig. 5.
figure 5

U-turn speed change

Full size image

Multi-rotor UAV can hover, but for fixed wing UAV, it is impossible to decelerate to 0 and then achieve deflection. In fact, even with multi-rotor, this way through the U-turn is not the best way to handle it. Therefore, trajectory optimization of right-angle transition part (such as angle BFC, CGD) is expected to make it more consistent with the actual trajectory of UAV. One of the objectives of flight trajectory optimization is to connect AB and DE segments with curves, so that the UAV can better follow the curve movement, and the smoothness of curves should be considered during optimization.

5.1 Dubins Curves

The concept of Dubins curve is first proposed by Dubins [31], which takes the influence of aircraft’s turning radius into account, and discusses the problem of the shortest curve between the initial state of motion and the end state by applying geometric method. It has been proved that the shortest paths of two positions on a plane are Dubins curves. Yeol J W [32] proposed a method suitable for Dubins curve concept to obtain two-dimensional shortest path. Thomaschewski [33] applied Dubins curve to the study of aircraft, so that the flight trajectory planning of aircraft can be closer to the real flight process.

5.2 Clothoid Curves

Dubins curve composed of arcs and straight lines are used as the flight paths of the UAV, taking the directions of the UAV’s starting and ending points as well as the curvature radius constraints into account. The shortest Dubins curve is given the radius of curvature constraint, but the curvature of Dubins curve from straight line segment to arc segment is discontinuous, which makes it difficult for UAV to accurately track. Clothoid curve acts as a transition curve connecting straight line part and arc part, making the trajectory smoother. Experiments show that, the composite path based on Clothoid curve is easier for UAV to track the flight path [34].

Fig. 6.
figure 6

Comparison of Dubins and PH curve

Full size image

5.3 PH Curves

Farouki [35] proposed PH curve (Pythagorean Hodograph, PH for short) in 1990, to establish an accurate relationship between curve arc length and parameters. PH curve is a special kind of Bessel curve, which has the advantage that the arc length can be expressed as a polynomial function. In literature [36], the PH curve is used to optimize the path of UAV, and the motion-constrained path is transformed into a dynamic feasible path. The smoothing method of PH curve uses polynomial to simulate the isoline components conforming to Pythagorean theorem in the curve, so as to replace the integral operation and accurately calculate the curve length.

6 The Evaluation Index of CPP

Depending on the mission, evaluation indexs to measure mission efficiency will have their own bias, and effective regional full coverage path planning for UAVs for a certain evaluation index is the only way to ensure the quality of mission completion. Common evaluation indexs of UAV regional CPP are flight distance, mission time, number of turns, climb and descent altitude, energy, regional coverage, route overlap rate, etc.

Flight distance refers to the flight distance of the UAV in the horizontal direction, which consists of straight-line distance and turn distance. In simple area coverage, the coverage area is traversed only once, while in complex area scenarios, after area decomposition, each independent area needs to be covered continuously, and reducing the traversed distance between independent areas after decomposition can effectively reduce the distance. In the case of a certain distance, the faster the flight speed of the UAV, the shorter the mission time, the flight speed must be set according to the different tasks performed, in most scenarios, the UAV captures image data through the on-board camera, and a good balance between flight speed and image clarity is beneficial to the execution of the task.

Through practical tests, Jalil Modares [33] concluded that UAV turns consume more energy compared to straight-line flight, and the larger the turn angle, the more energy is consumed. Reducing the number of turns in the traversal approach can allow the UAV to have a longer range and cover more areas. This is the main reason for traversing along long edges when performing coverage tasks in regular rectangular areas. In addition, most UAV path planning tasks do not take climb and descent heights into account in the optimization process, and in fact these two processes still consume some energy.

The area coverage ratio is the ratio of the area covered by the UAV to complete the necessary points in the area to the area to be covered; the higher the coverage ratio, the better the mission is performed. The route overlap ratio generally includes the heading and side overlap ratio. In the image stitching task, there is a certain overlap ratio required between two images, and the image overlap ratio determines the interval distance between routes and the moment point of taking pictures, and the actual image overlap ratio will be smaller than the set one due to the horizontal drift of the UAV in the actual flight.

7 Conclusions

In this paper, the problem of UAV area coverage was summarized and analyzed in detail. With the evolution and development of UAV cluster, the intelligence of UAV individual is constantly evolving, and methods such as deep learning and deep reinforcement learning are being applied to UAV. It can be expected that UAV path planning technology in the future will be more intelligent and diversified.