Coverage path planning in irregular-shaped areas containing no-fly zones in the subregions bounds for collision avoidance.
If you are new to coverage path planning, it is basically a science that consists of finding the route that covers every point of a certain area of interest. As of recently, drones or unmanned aerial vehicles (UAVs) have been employed in such application domains that involved terrain coverage such as surveillance, smart farming, photogrammetry, disaster management, civil security, wildfire tracking and others.
In a new research paper, Tauã Cabreira, Lisane Brisolara and Paulo Ferreira Jr. of the Federal University of Pelotas, Brazil, decided to explore and analyze all of the existing studies in the literature that are related to the different approaches employed in the coverage path planning problems, especially the ones using drones.
More specifically, the authors addressed simple geometric flight patterns as well as more complex grid scenarios in order to consider the full and partial information about the area of interest.
They also talk about the Coverage Path Planning (CPP) problem which is nowadays classified as a motion planning subtopic in robotics, where it is necessary to build a path for robots to explore every location in any given scenario. Despite the technological progress in the type of aerial platform regarding autonomous flights, it is also important to emphasize that the phases including take-off, mission execution and landing are all assisted by two people for each UAV due to safety measures.
In one of the initial parts, the authors classify UAVs into two main top-level configurations – fixed-wing and rotary-wing UAVs. They also mention the hybrid UAV model which is a specific type of aerial platform that includes the advantages of both (rotary and fixed) and has a VTOL capability, high-flight speed and increased flight times.
As they note in the paper, they were motivated by a couple of factors:
“Although land exploration techniques revised in the previous surveys can be extended and applied to UAVs, several additional aspects must be considered when dealing with aerial vehicles such as vehicle’s physical characteristics, endurance, maneuverability limitations, restricted payload, environmental external conditions, among others.”
They also added the following:
“This paper presents a survey on coverage path planning. Our review considers only approaches related to unmanned aerial vehicles. The classic taxonomy defined by Choset [9] was adopted to classify the existing approaches according to the cellular decomposition technique employed. Approaches with no decomposition and methods using exact and approximate cellular decomposition are considered. The latter ones, also known as grid-based methods, are divided into two subsections, full and partial information.”
As such, their paper is organized in different parts to address coverage path planning problems and describe how the areas of interest are characterized and how they are treated in the flight planning.
Different areas of interest explored during CPP missions: (a) Rectangular; (b) Convex Polygon; (c) Concave Polygon with No-Fly Zones.
Speaking of which, the coverage path planning section uses a target environment that is split into non-interesting regions called cells using a decomposition technique. For larger cells, there are several motions necessary to fully cover only one unit.
Approximate cellular decomposition: (a) Projected area; (b) Regular grid with waypoints.
Simple flight patterns in rectangular areas with no decomposition: (a) Parallel; (b) Creeping Line; (c) Square; (d) Sector Search; (e) Barrier Patrol.
One of the major concerns that the authors address is the guarantee of a complete coverage of the scenario, which cannot happen and is usually achieved by applying cellular decomposition in the area of interest, splitting the target free space into cells in order to simplify the coverage.
In the Performance Metrics section, the authors noted:
“Coverage algorithms must consider several issues to guarantee the success of a coverage mission, such as the complexity of the area of interest, the presence or not of no-fly zones and the possibility to employ cellular decomposition techniques. Furthermore, the coverage algorithms should generate coverage paths according to the application requirements.”
Because of this, the performance metrics used to evaluate the candidate solutions for a coverage path must fulfill the application requirements at all times. The use of multiple robots helped the authors reduce the coverage flight time.
On top of this, there is a number of turning maneuvers often employed as the main performance metric in coverage.
“When an aerial vehicle executes a turning maneuver, it should reduce its speed, rotate and increase its speed again. Thus, the greater the number of executed maneuvers, the greater the time and the energy spent,” the authors explained.
After reviewing many other parts, figures, algorithms and techniques, the authors conclude that the coverage path planning problem with UAVs has been addressed by many authors in literature.
Surveillance mission in irregular-shaped areas with path segmentation using a team of heterogeneous UAVs: (a) Irregular area approximation; (b) Segmented single path.
However, while the simple areas of interest such as the rectangular and convex polygons do not require any discretization method or decomposition techniques, there are others that do.
“Several studies seek to minimize distance, flight time or maneuvers in order to decrease energy consumption. During turning maneuvers, the vehicles should decelerate, rotate and accelerate, extending flight time and, consequently, energy consumption,” they wrote.
The authors also briefly sum up some of the key studies and approaches on this particular problem, giving full insights on each while evaluating all of the benefits and challenges.
Citation: Survey on Coverage Path Planning with Unmanned Aerial Vehicles, Tauã M. Cabreira, Lisane B. Brisolara and Paulo R. Ferreira Jr., Drones 2019, 3(1), 4; doi:10.3390/drones3010004 – https://www.mdpi.com/2504-446X/3/1/4/htm