Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Georgios Fevgas
 + 5509 word(s) 5509 2022-02-09 07:39:09 |
2 numbering
Georgios Fevgas
 Meta information modification 5509 2022-02-09 12:37:55 | |
3 update layout and reference
Rita Xu
 -1114 word(s) 4395 2022-02-10 02:55:53 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Fevgas, G. Coverage Path Planning Methods Focusing on Energy Efficient. Encyclopedia. Available online: https://encyclopedia.pub/entry/19281 (accessed on 19 May 2024).
Fevgas G. Coverage Path Planning Methods Focusing on Energy Efficient. Encyclopedia. Available at: https://encyclopedia.pub/entry/19281. Accessed May 19, 2024.
Fevgas, Georgios. "Coverage Path Planning Methods Focusing on Energy Efficient" Encyclopedia, https://encyclopedia.pub/entry/19281 (accessed May 19, 2024).
Fevgas, G. (2022, February 09). Coverage Path Planning Methods Focusing on Energy Efficient. In Encyclopedia. https://encyclopedia.pub/entry/19281
Fevgas, Georgios. "Coverage Path Planning Methods Focusing on Energy Efficient." Encyclopedia. Web. 09 February, 2022.
Coverage Path Planning Methods Focusing on Energy Efficient
Edit
This entry is adapted from the peer-reviewed paper 10.3390/s22031235

The coverage path planning (CPP) algorithms aim to cover the total area of interest with minimum overlapping. The goal of the CPP algorithms is to minimize the total covering path and execution time. Significant research has been done in robotics, particularly for multi-unmanned unmanned aerial vehicles (UAVs) cooperation and energy efficiency in CPP problems.

coverage path planning unmanned aerial vehicle cell decomposition decomposition methods energy-aware approaches energy optimal path multi-robot systems multi-UAV

1. Introduction

In recent years, due to rapid technological development, UAVs and sensors they can carry have been developed to the extent that they can cover a wide range of applications [1] that cannot be satisfied by other types of robots [2]. Some of the applications are precision agriculture [3][4], search and rescue [5], firefighting [6], law enforcement [7], powerline inspection [8], oil and gas [9], disaster management [10], and cell network expansion [11]. However, a fundamental problem is the optimal use of autonomous aircraft in terms of time and space [2].
Recently, CPP algorithms have been developed, considering the parameters required for more efficient data retrieval from remote sensing sensors [12][13]. In addition, algorithms have been developed that use multi-UAV to cover the area, thus reducing the coverage time of the area of interest [14][15]. The way to cover an area with autonomous robots differs depending on the algorithm [2][16][17]. In the literature, CPP algorithms use different methods (e.g., grids, graphs, and neural networks) with calculations performed online or offline for known or unknown areas [18].
The CPP algorithms can be classified into two main categories: offline and online [19]. Offline algorithms need to know the environment and the information included, such as obstacles and the geometry of the area of interest. Of course, in a real-life environment, many dynamic parameters cannot be known in advance. Offline algorithms have prior knowledge of the coverage area environment [20]. They also provide more efficient and convenient route plans and use less central processing unit (CPU) power than online algorithms [21].
The online algorithms are based on real-time environment data retrieved from onboard sensors to cover the area of interest. Online algorithms do not fully understand the coverage area environment, and the coverage path is executed in real-time by the UAV after processing the data using the sensors it carries. The benefits of online algorithms are the design of the in-flight route to complete the mission regardless of unforeseen situations and the unnecessary prior detailed knowledge of the coverage area [20][22].
Furthermore, there are two categories of problems in area coverage: single coverage and repeat coverage. The goal of single coverage is to cover the entire area of interest and, at the same time, minimize the time and distance traveled by the coverage route [23]. On the other hand, repetitive coverage aims to repeatedly cover all points of interest in the area, maximize the frequency of visits to points of interest, and minimize time and total coverage [24].

2. No Decomposition

There is no need for decomposition in areas with regular shapes and without complexity, such as rectangular areas. Patterns with simple path planning, such as boustrophedon or square, are adequate for total coverage of a non-complex area without overlapping. The boustrophedon method, which means “the way of the ox,” is a pattern of simple back and forth motion along the longest side of the polygon, as shown in Figure 1 [25][26][27].
Sensors 22 01235 g001 550
Figure 1. Boustrophedon pattern.
The literature assumes that the actual path is closely true to the plan when this method is executed from a ground vehicle. On the other hand, UAVs are aerodynamically directly affected by the direction and intensity of the wind, which means that the actual trajectory of the flight in most cases is not close to that planned.
The square method is represented by Andersen [28], and it is a pattern for a search and rescue mission. The flight path is straight lines with right 90 degrees turns. The pattern starts from the center of the area of interest and expands until the borders, as shown in Figure 2.
Sensors 22 01235 g002 550
Figure 2. Square pattern.

3. Exact Cellular Decomposition

The cellular decomposition methods are based on dividing an irregular space into cells. One class of these methods is the exact one. The exact cellular decomposition method decomposes the irregular space into cells, and their connections produce an accurate free space composition. Accurate methods are complete because they guarantee the finding of an accessible path, if any [29]. The sub-areas that arise from the decomposition can be covered from a single UAV or multiple UAVs. There are patterns for a single UAV, such as boustrophedon and spiral for polygon and concave areas. Nevertheless, there are strategies for the cooperation of multiple UAVs in order to minimize the coverage time [30].

4. Trapezoidal Decomposition

One exact cellular decomposition technique for irregular spaces that can give a complete coverage path is trapezoidal decomposition. This method is classified in the offline category of algorithms because it does not use remote-sensing information [31][32]. Each cell is a trapezoid in this method, and simple methods such as back and forth can be used to cover every cell. The coverage can be achieved by an exhaustive walk that generates a path to cover each cell to execute the path using back and forth motions such as boustrophedon, as shown in Figure 3. Often, this method is used for agriculture applications where the fields are polygonal and clear from obstacles. Oksanen and Visala [33] introduced an algorithm for CPP in agricultural fields and used the path cost function to optimize the final path.

Sensors 22 01235 g003 550
Figure 3. Trapezoidal decomposition.

5. Boustrophedon Decomposition

Trapezoidal decomposition produces many cells, some of which can be merged. This characteristic is a disadvantage because as many cells exist, the coverage path will be longer. To overcome this limitation, a method that creates nonconvex cells is needed. The boustrophedon cellular decomposition is similar to trapezoidal decomposition but considers vertices in the area called critical points [25][27]. The boustrophedon decomposition reduces the number of cells compared with trapezoidal decomposition, which means shorter path planning, as shown in Figure 4. As the trapezoidal decomposition, this method is for polygonal areas, and the environment of the coverage area should be known. For this reason, it can be classified as an offline method.
Sensors 22 01235 g004 550
Figure 4. Boustrophedon decomposition.

6. Morse-Based Decomposition

Another cellular decomposition method proposed by Acar et al. [34] is based on Morse functions [35]. The Morse-based decomposition method has the advantage of different cells shapes such as circular and can be applied in any dimensional space, such as concave, polygon, and irregular space. The cell decomposition is succeeded with a slice that sweeps through the area of interest. A slice is discontinued at the critical point of the Morse function, which is restricted from the obstacle boundaries, as shown in Figure 5. This method uses information concerning the area during motion planning. For this reason, the method can be classified as online [36][37].
Sensors 22 01235 g005 550
Figure 5. Morse-based decomposition.

7. Online Topological Coverage Algorithm

Wong [38] presented an algorithm that finds the cell boundaries online using slice decomposition. Slice decomposition is a method for determining the cell boundaries using a sweeping line over the area of interest. As the line sweeps over the area, it separates the obstacles and free space in two regions or more, as shown in Figure 6. The algorithm constructs a topological map using the slice decomposition on the area of interest [39].
Sensors 22 01235 g006 550
Figure 6. Slice decomposition.

8. Contact Sensor-Based Coverage of Rectilinear Environments

Butler et al. [40] present an exact cell decomposition algorithm for contact sensor-based robots for online coverage of the rectilinear environment. In contact sensor-based coverage, the robot’s path is cycling with retracing, while at the same time it repeatedly constructs a cellular decomposition of the area of interest. When a robot’s full-cycle path is unsuccessful, it chooses a new path based on its position and environment. The robot’s motion depends on the area’s cell decomposition state, updated as the CPP progresses.

9. Grid-Based Methods

Grid-based methods are classified as approximate cellular decomposition due to the restriction of the grid’s shape, which is uniform in space. It is impossible to represent precisely the shape of the target space and its obstacles [19]. The grid-based methods decomposed the space into uniform grid cells, which can be squares or other shapes, as shown in Figure 7. Moravec and Elfes [41] proposed a grid map presentation based on a sonar mounted on a mobile robot mapping an indoor environment.
Sensors 22 01235 g007 550
Figure 7. Grid-based decomposition.

9.1. Wavefront Algorithm

The first CPP’s grid-based method was proposed by Zelinsky et al. [42]. Their method has a start cell and a goal cell. A grid represents the coverage area, and a wavefront algorithm is used from the goal cell to the start cell. Its operation is based on propagating a “wavefront” from the target cell passing through the free cells and bypassing all obstacles to the starting cell.
More specifically, the transmission of the “wavefront” from the target cell to the starting cell is used to assign specific numbers to each cell of the grid, as shown in Figure 8. Firstly, 0 is assigned to the target cell and then 1 to all adjacent cells. Then, all the other adjacent cells of 1 to which no number has been assigned are assigned 2. The process repeats incrementally until the wavefront reaches the starting point [13][20]. The environment should be known in this method, so the method can be classified offline.
Sensors 22 01235 g008 550
Figure 8. Wavefront Transmission from starting cell (S) to target cell (T).
Nevertheless, Shivashankar et al. [43] proposed a wavefront algorithm to accomplish an online CPP with a mobile robot in an unknown spatial environment.

9.2. Spanning Tree Coverage

The spanning tree coverage (STC) algorithm solves the problem of covering an area using a robot [30]. The method used by the STC algorithm is first to decompose the region into cells and calculate a connecting tree of the resulting graph. Finally, the robot’s path starts near the “connecting tree” and follows its perimeter, as shown in Figure 9 [29]. A Spiral-STC algorithm was proposed by Gabriely and Rimon [44]. This online method converts the space into a grid map. The mobile robots execute a spanning tree-generated spiral path using onboard sensors.
Sensors 22 01235 g009 550
Figure 9. Spanning Tree-based coverage.

10. Neural Network-Based Coverage on Grid Maps

The CPP using a neural network is an online coverage method. First, in a 2D coverage area, a grid map is constructed where the length of the diagonal of each cell is equal to the coverage radius of the robot (e.g., the coverage radius of a robotic broom), and then a neuron is associated with each cell in the grid. Each neuron is connected to the eight primary neighboring neurons, as shown in Figure 10. Finally, the robot’s path to the coverage area is executed by knowing each output value of each neuron at a given time, so that the robot is attracted to cells it has not visited while at the same time being rejected by cells it has visited [45][46].
Table 1. CPP and decomposition methods.
CPP Approach Decomposition Method Algorithm Processing Shape of Area Reference
Boustrophedon None Offline Rectangular [25][26][27]
Square None Offline Square [28]
Boustrophedon, Spiral Exact cellular Offline Polygon, Concave [29]
Back and Forth Trapezoidal Offline Polygon [31][32]
Boustrophedon Boustrophedon Offline Polygon [25][27]
Boustrophedon Morse-based Online Any dimensional [34]
Online Topological Slice Online Polygon [38]
Contact Sensor-based Exact cellular Online Rectilinear [40]
Wavefront Approximate cellular Offline Polygon, Concave [42]
Wavefront Approximate cellular Online Polygon, Concave [43]
STC Approximate cellular Offline Polygon, Concave [29]
Spiral-STC Approximate cellular Online Polygon, Concave [44]
Neural Network-based Approximate cellular Online Polygon, Concave [45][46]
Sensors 22 01235 g010 550
Figure 10. Neural Network-based coverage.

11. Multi-Robot CPP Strategies

Multiple robots have an advantage over single robotic systems [24]. The use of multiple robots accelerates coverage of an area of interest. The problem of covering an area with multiple robots lies in the calculation of optimal routes in order to minimize the coverage time [30]. Using multiple robots in a CPP work reduces the completion time due to workload division [20]. This section discusses multi-robot coverage methods based on single robot approaches, multi-robot strategies, and multiple UAVs to cover an area of interest. Some drawbacks of multiple UAV strategies are spatial orientation and communication difficulties. Table 2 at the end of this section summarizes the multi-robot CPP strategies and presents the CPP approach, the decomposition method, the algorithm processing, and the corresponding reference.

12. Multi-Robot Boustrophedon Decomposition

Rekleitis et al. [16] presented a set of online algorithms for solving the CPP using a group of mobile robots in an unknown environment. The algorithms employ the same planar cellular decomposition as the Boustrophedon single robot coverage algorithm, with additions to manage how robots cover a single cell and distribute among cells. Their solution takes into account the team members’ communication limitations. The robots serve two roles to accomplish coverage where some members, known as explorers, cover the boundaries of the actual target cell, while others, known as coverers, conduct basic back-and-forth motions to cover the cell.

13. Multi-Robot Spanning Tree Coverage

Their experimental data reveal that their technique outperforms multi-robot spanning tree coverage (MSTC) by a significant margin. Nevertheless, the coverage time of an area with the multi-robot forest coverage (MFC) algorithm is shorter than the MSTC algorithm [30]. Moreover, an online, robust version of MSTC was provided by Hazon et al. [47]. They show that the approach is robust analytically, providing as much coverage as a single robot can.

14. Multi-Robot Neural Network-Based Coverage

A neural network approach for multi-robot coverage where each robot sees all the others as obstacles and the avoidance ability of stalemate situations was proposed by Luo and Yang [46][48][49]. The multi-robot neural-network based coverage is inspired by single robot neural-network coverage. During the coverage of the irregular-shaped area of interest, the robots see each other as moving obstacles.

15. Multi-Robot Graph-Based and Boundary Coverage

Easton and Burdick [50] presented a two-dimensional boundary coverage method for multiple robots. A team of robots must inspect all points on the boundary of the two-dimensional target environment, and each robot’s inspection routes are planned to use a heuristic search. The planned paths cover the entire boundary. Moreover, the algorithm has been validated by simulations. The multi-robot boundary coverage is inspired by the need to inspect the blade surfaces inside a turbine.
Table 2. Multi-robot CPP strategies.
CPP Approach Decomposition Method Algorithm Processing Reference
Boustrophedon Exact cellular Online [16]
Spanning Tree Coverage Approximate cellular Online [47]
Neural network-based Approximate cellular Online [46][48][49]
Graph-based and Boundary Approximate cellular Offline [50]

16. Multi-UAV CPP Methods

The number of applications where UAVs can be used is increasing as remote-sensing technology is developed. In the literature, there are a lot of multi-UAV CPP methods using different coverage algorithms with heterogeneous or homogeneous UAVs that were used in a variety of applications, such as agriculture [51], surveillance [52], mapping [53], and search and rescue missions [54]. Table 3 at the end of this section summarizes the multi-UAV CPP strategies and presents the CPP approach, the type of UAVs, the algorithm processing, the evaluation metrics, and the corresponding reference.

17. Multi-UAV Coverage

In the agricultural sector, Barrientos et al. [13] proposed a method for area coverage using a fleet of mini aerial robots. Their method divides the area of interest in k non-overlapping subtasks and assigns them in k UAVs. A decentralized method for surveillance missions using homogeneous UAVs was proposed by Acevedo et al. [55]. This method’s primary goal is to minimize latency, which means a short sharing time of information between the UAVs. In a later work, Acevedo et al. [56] developed a method for surveillance in urban environments with heterogeneous UAVs that fly at low altitudes and avoid obstacles. Finally, in their most recent work, Acevedo et al. [57] developed a method based on grid-shape area partition, which can readjust the area shape and UAVs’ capacity.
A terrain coverage method using a fleet of heterogeneous UAVs was presented by Maza and Ollero [53]. Their method divides the irregular-shaped area of interest per each UAV capability, such as total flight time. Each partition is assigned to a UAV that plans a zig-zag covering pattern according to the area’s characteristics to minimize the number of turns. The method was validated in simulation.
A coverage algorithm for fixed-wing UAVs with the ability for obstacle and previously scanned regions avoidance was presented by Xu et al. [23][58]. Their method uses boustrophedon cellular decomposition [25], an exact cellular decomposition, and presents better accuracy than trapezoidal decomposition. The method can be classified as online in the phase of region scanning and offline in the coverage phase.

18. Back-and-Forth

Maza and Ollero [53] present a cooperative technique using heterogeneous UAVs in a convex polygonal area. A ground control station divides the area into sub-regions and assigns them to every UAV by the capability and starting position. Every UAV calculates back-and-forth patterns according to the camera footprint to reduce the number of turns.

19. Spiral

Balampanis et al. [59][60] present a spiral CPP algorithm using multiple heterogeneous UAVs. The area of interest is divided according to UAVs sensing capabilities using a constrained Delaunay triangulation (CDT) [61]. The CDT generates triangle cells that match almost exactly the shape of the area of interest. To make the triangles more uniform, they applied Lloyd optimization [62]. Then, a spiral algorithm generates the coverage pattern for each sub-area. This method can generate smoother trajectories considering avoiding no-fly zones and the shape of the coverage area. However, it generates more extensive coverage paths and a higher number of turns than classical grid decomposition and motion methods [63][64].

20. Multi-Objective Path Planning (MOPP) with Genetic Algorithm (GA)

Hayat et al. [65] propose multi-objective path planning (MOPP) with a genetic algorithm (GA) for search and rescue missions using multiple UAVs. The mission is divided into two phases: search and response. The search phase monitors an event to guarantee the total coverage in a given area, and the response phase spreads detection updates on the network. The MOPP algorithm performs the planning task during the search, while the GA minimizes the mission completion time. As a result, the method can be classified as offline in the search phase and online in the response phase.

21. Genetic Algorithm (GA) with Flood Fill Algorithm

Based on the Trujillo et al. [66] approach, Darrah et al. [67] present a CPP method for missions over more extensive areas using multi-UAVs. The method produces equitable sub-areas of the area of interest to cover by multi-UAVs or several flights performed by a single UAV. The flood fill algorithm integrated with game theory was applied to partition the area of interest. Each UAV is a player and has a starting position. According to a predefined pattern in a diamond shape, the UAVs take turns flooding the neighbor cells. The UAVs cannot fly over building cells or cells previously occupied by other UAVs. The partitioning method guarantees an approximate amount of work for each assigned UAV by balancing the tasks. An improved version of the approach proposed by Trujillo et al. [66] was used for each sub-area’s coverage trajectories. The method can be classified initially as offline and then as online.

Table 3. Multi-UAV CPP strategies.

CPP Approach Type of UAVs Algorithm Processing Evaluation Metrics Reference
Sub-perimeter method Homogeneous Online Minimize latency [55]
Back-and-Forth Homogeneous Online/Offline Total path length
Time coverage		 [23][58]
Back-and-Forth Heterogeneous Offline Number of turns [53]
Spiral Heterogeneous Offline Coverage path, Number of turns [59][60]
Multi-Objective Path Planning with GA Homogeneous Offline/Online Mission Completion Time [65]
GA with flood fill algorithm Homogeneous Offline/Online Path length [66][67]

22. Energy-Saving CPP Algorithms

In the literature, there are a lot of CPP strategies for energy saving. One method for energy saving proposed by Lawrance and Sukkarieh [68] is the energy exploitation of the wind using a small gliding UAV. The authors present an algorithm that generates energy gain paths according to the UAV’s constraints, the field’s wind conditions, and static and dynamic soaring. One of the limitations of this method is the requirement for prior knowledge of the field’s wind conditions. In future research, an online stochastic wind estimation and planning method using current wind conditions of the field should be developed.
Another method for minimizing the power consumption of a UAV is reducing the number of turns of the CPP. Torres et al. [69] present an algorithm that reduces the number of turns and the total flying path to minimize battery consumption.
The effect of wind direction and intensity on the time of mission completion was presented by Coombes et al. [70]. The authors used a fixed-wing UAV and the boustrophedon method to cover the area of interest. Their simulated experiments used a constant direction of the wind and six different speeds, and for the coverage path used different directions of the fixed-wing UAV motion from 0 to 360 degrees in increments of 10 degrees. The results showed that the direction of the coverage path should be 90 degrees to the wind direction to minimize the coverage time. Furthermore, the direction of the turns is directly affected by the vertical component of the wind. In a later work, Coombes et al. [71] presented the flight time in wind (FTIW) function, which computes the total flight time for a total coverage of the area of interest. The flight time needed for the total coverage of the area is less than the previous methods. Their approach was validated after simulations and real flights.
An energy-efficient back and forth CPP algorithm proposed by Di Franco and Buttazzo [18] computes the best motion trajectory and the maximum altitude according to the ground sample distance (image resolution) to minimize the number of turns. Another approach for energy efficiency is to find an optimal constant speed according to the coverage path. An energy-aware spiral CPP algorithm uses wider angle turns to minimize the acceleration and deceleration to maintain an optimal constant speed Cabreira et al. [72]. After simulated and real flights, the most energy-efficient CPP method between energy-efficient back and forth CPP [18] and the energy-aware spiral CPP approach proposed by Cabreira et al. [72] for a convex area was the energy-aware spiral CPP method which adopted the energy model proposed by Di Franco and Buttazo [73].
Another energy-aware CPP algorithm for UAVs was proposed by Li et al. [74], where the algorithm has three stages. In the first stage, the algorithm builds a 3D terrain model. In the second stage, constant power consumption is computed by total take-off weight, flight speed, and air friction. In the third stage, a genetic algorithm generates an energy-optimal coverage path, which represents the amount of energy consumption in every part of the path.
Another problem concerning UAV energy consumption is the deceleration and acceleration at every turn of a conventional trajectory such as boustrophedon. Artemenko et al. [75] present an algorithm that modifies conventional trajectories using Bézier curves, smoothing the turns on a given path to minimize deceleration and acceleration before and after the turning point. The authors concluded that their algorithm could reduce energy spending compared to conventional algorithms. Restrictions, such as the UAV motion and camera’s location, can be overcome using integer linear programming. Ahmadzadeh et al. [76] present a cooperative coverage technique with critical time for rectangular areas utilizing several fixed-wing heterogeneous UAVs, some carrying a frontal camera, flying circular paths and some of them carrying a camera on the left side, flying straight lines with left turn paths. Their proposed method uses four fixed-wing UAVs covering 100% of the area of interest instead of the simple methods covering 80%. The proposal was validated in simulation tests and real flights.
Araujo et al. [77] propose an algorithm where the workspace is divided into sub-areas assigned to each UAV according to its relative capability. According to the kinematics constraints of the UAVs, the algorithm generates an optimal number of stripes to minimize the number of stripes and eventually the number of turns, which means less energy consumption.
Majeed and Lee [78] present a CPP method for UAV low-altitude navigation in three-dimensional urban areas with fixed convex obstacles based on footprint sweeps fitting and a sparse waypoint graph. The primary goals of the proposed approach are to reduce computational time, the number of turns, and path overlapping while minimizing the total coverage path of the area of interest. The suggested method outperforms the similarly related CPP approaches according to simulation findings.
In a later work, Majeed and Hwang [79] present a CPP algorithm for UAV navigation to cover areas of interest (AOIs) surrounded by obstacles in three-dimensional urban areas with fixed obstacles. The proposed method is applicable in a wide range of practical applications that involve computing a low-cost coverage for spatially distributed AOIs in an urban environment. However, the proposed algorithm has not incorporated and tested for constraints and limitations, such as image resolution and UAV battery.
Cheng et al. [80] present a bio-inspired method for cooperative coverage. This method represents the trajectory of each UAV as the B-spline curve containing control points. This optimization problem aims to maximize the desirability of a path by combining four variables: path distance, minimum turning angle, maximum pitch rate, and superposition of the actual trajectory over different UAV trajectories. According to the authors, the beginning and last control points are at the area’s borders because the UAV always travels from left to right. The ant colony optimization (ACO) algorithm was adapted for coverage with multiple UAVs by Kuiper and Nadjm-Tehrani [81]. The y-axis in the intermediate control points is optimized using the ACO algorithm to maximize the coverage. Several ants are launched during the algorithm repetitions, passing through the starting, intermediate, and endpoints.
Table 4 summarizes the energy-saving CPP methods reviewed in this paper according to the method used for energy saving. The table presents the CPP method, the energy-saving factor, the type of UAV, and the corresponding reference.

Table 4. CPP energy-aware methods.

CPP Method Energy-Saving Approach Type of UAV Reference
Energy gain path Energy exploitation of the wind Fixed-wing [68]
Back and Forth Reducing the number of turns and the total flying path Rotorcraft [69]
Boustrophedon The direction of the UAV path and the turns according to the wind direction Fixed-wing [70]
Back and Forth Altitude maximization according to the Ground Sample Distance to reduce the number of turns Rotorcraft [18]
Spiral Wider angle turns to minimize the acceleration and deceleration Rotorcraft [72]
Three stages energy optimal path An energy-aware algorithm computes the take-off weight, flight speed, and air friction to generate an energy-optimal path Rotorcraft [74]
Smoothing turns Smoothing the turns on a given path to minimize deceleration and acceleration before and after the turning point Rotorcraft/Fixed-wing [75]
Circular and straight lines with left turns paths Cooperative coverage algorithm with critical time Multiple Fixed-wing [76]
Back and Forth Minimizing the number of stripes and eventually the number of turns Multiple Fixed-wing [77]
Back and Forth Reduce computational time, the number of turns, and path overlapping while minimizing the total coverage path Rotorcraft [78]
Back and Forth Reducing the computational time and path length for the inter-regional path, the number of turning maneuvers, and path overlapping Rotorcraft [79]
ACO with Gaussian distribution functions Path length, rotation angle, and area overlapping rate Rotorcraft/Fixed-wing [80]

References

  1. Lagkas, T.; Argyriou, V.; Bibi, S.; Sarigiannidis, P. UAV IoT Framework Views and Challenges: Towards Protecting Drones as “Things”. Sensors 2018, 18, 4015.
  2. Azpúrua, H.; Freitas, G.M.; Macharet, D.G.; Campos, M.F.M. Multi-Robot Coverage Path Planning Using Hexagonal Segmentation for Geophysical Surveys. Robotica 2018, 36, 1144–1166.
  3. Maes, W.H.; Steppe, K. Perspectives for Remote Sensing with Unmanned Aerial Vehicles in Precision Agriculture. Trends Plant Sci. 2019, 24, 152–164.
  4. Radoglou-Grammatikis, P.; Sarigiannidis, P.; Lagkas, T.; Moscholios, I. A Compilation of UAV Applications for Precision Agriculture. Comput. Netw. 2020, 172, 107148.
  5. Silvagni, M.; Tonoli, A.; Zenerino, E.; Chiaberge, M. Multipurpose UAV for Search and Rescue Operations in Mountain Avalanche Events. Geomat. Nat. Hazards Risk 2017, 8, 18–33.
  6. Yuan, C.; Liu, Z.; Zhang, Y. Aerial Images-Based Forest Fire Detection for Firefighting Using Optical Remote Sensing Techniques and Unmanned Aerial Vehicles. J. Intell. Robot. Syst. 2017, 88, 635–654.
  7. Straub, J. Unmanned Aerial Systems: Consideration of the Use of Force for Law Enforcement Applications. Technol. Soc. 2014, 39, 100–109.
  8. Deng, C.; Wang, S.; Huang, Z.; Tan, Z.; Liu, J. Unmanned Aerial Vehicles for Power Line Inspection: A Cooperative Way in Platforms and Communications. J. Commun. 2014, 9, 687–692.
  9. Cho, J.; Lim, G.; Biobaku, T.; Kim, S.; Parsaei, H. Safety and Security Management with Unmanned Aerial Vehicle (UAV) in Oil and Gas Industry. Procedia Manuf. 2015, 3, 1343–1349.
  10. Erdelj, M.; Natalizio, E. UAV-assisted disaster management: Applications and open issues. In Proceedings of the 2016 International Conference on Computing, Networking and Communications (ICNC), Kauai, HI, USA, 15–18 February 2016; pp. 1–5.
  11. Pliatsios, D.; Goudos, S.K.; Lagkas, T.; Argyriou, V.; Boulogeorgos, A.A.A.; Sarigiannidis, P. Drone-Base-Station for Next-Generation Internet-of-Things: A Comparison of Swarm Intelligence Approaches. IEEE Open J. Antennas Propag. 2021, 3, 32–47.
  12. Ballesteros, R.; Ortega, J.F.; Hernández, D.; Moreno, M.A. Applications of Georeferenced High-Resolution Images Obtained with Unmanned Aerial Vehicles. Part I: Description of Image Acquisition and Processing. Precis. Agric. 2014, 15, 579–592.
  13. Barrientos, A.; Colorado, J.; del Cerro, J.; Martinez, A.; Rossi, C.; Sanz, D.; Valente, J. Aerial Remote Sensing in Agriculture: A Practical Approach to Area Coverage and Path Planning for Fleets of Mini Aerial Robots. J. Field Robot. 2011, 28, 667–689.
  14. Maza, I.; Capitán, J.; Merino, L.; Ollero, A. Multi-UAV cooperation. In Encyclopedia of Aerospace Engineering; John Wiley & Sons, Ltd.: Hoboken, NJ, USA, 2015; pp. 1–10.
  15. Spyridis, Y.; Lagkas, T.; Sarigiannidis, P.; Zhang, J. Modelling and Simulation of a New Cooperative Algorithm for UAV Swarm Coordination in Mobile RF Target Tracking. Simul. Model. Pract. Theory 2021, 107, 102232.
  16. Rekleitis, I.; New, A.P.; Rankin, E.S.; Choset, H. Efficient Boustrophedon Multi-Robot Coverage: An Algorithmic Approach. Ann. Math. Artif. Intell. 2008, 52, 109–142.
  17. Nolan, P.; Paley, D.A.; Kroeger, K. Multi-UAS path planning for non-uniform data collection in precision agriculture. In Proceedings of the 2017 IEEE Aerospace Conference, Big Sky, MT, USA, 4–11 March 2017; pp. 1–12.
  18. Di Franco, C.; Buttazzo, G. Coverage Path Planning for UAVs Photogrammetry with Energy and Resolution Constraints. J. Intell. Robot. Syst. 2016, 83, 445–462.
  19. Choset, H. Coverage for Robotics—A Survey of Recent Results. Ann. Math. Artif. Intell. 2001, 31, 113–126.
  20. Galceran, E.; Carreras, M. A Survey on Coverage Path Planning for Robotics. Robot. Auton. Syst. 2013, 61, 1258–1276.
  21. Valente, J.; Del Cerro, J.; Barrientos, A.; Sanz, D. Aerial Coverage Optimization in Precision Agriculture Management: A Musical Harmony Inspired Approach. Comput. Electron. Agric. 2013, 99, 153–159.
  22. Paull, L.; Thibault, C.; Nagaty, A.; Seto, M.; Li, H. Sensor-Driven Area Coverage for an Autonomous Fixed-Wing Unmanned Aerial Vehicle. IEEE Trans. Cybern. 2014, 44, 1605–1618.
  23. Xu, A.; Viriyasuthee, C.; Rekleitis, I. Optimal complete terrain coverage using an unmanned aerial vehicle. In Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 9–13 May 2011; pp. 2513–2519.
  24. Fazli, P.; Davoodi, A.; Mackworth, A.K. Multi-Robot Repeated Area Coverage. Auton. Robots 2013, 34, 251–276.
  25. Choset, H.; Pignon, P. Path Planning: The Boustrophedon Cellular Decomposition. In Proceedings of the International Conference on Field and Service Robotics, Canberra, Australia, 12 October 1997; pp. 1311–1320.
  26. Choset, H.; Pignon, P. Coverage path planning: The boustrophedon cellular decompositio. In Field and Service Robotics; Springer: London, UK, 1998; pp. 203–209.
  27. Choset, H.; Acar, E.; Rizzi, A.A.; Luntz, J. Exact cellular decompositions in terms of critical points of Morse functions. In Proceedings of the 2000 ICRA. Millennium Conference, IEEE International Conference on Robotics and Automation, Symposia Proceedings (Cat. No.00CH37065), San Francisco, CA, USA, 24–28 April 2000; Volume 3, pp. 2270–2277.
  28. Andersen, H.L. Path Planning for Search and Rescue Mission Using Multicopters. 2014. 135. Available online: https://ntnuopen.ntnu.no/ntnu-xmlui/handle/11250/261317 (accessed on 12 December 2021).
  29. LaValle, S.M. Planning Algorithms; Cambridge University Press: Cambridge, UK, 2006.
  30. Zheng, X.; Jain, S.; Koenig, S.; Kempe, D. Multi-robot forest coverage. In Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada, 2–6 August 2005; pp. 3852–3857.
  31. Choset, H.; Lynch, K.M.; Hutchinson, S.; Kantor, G.A.; Burgard, W. Principles of Robot Motion: Theory, Algorithms, and Implementations; MIT Press: Cambridge, MA, USA, 2005.
  32. Latombe, J.-C. Robot Motion Planning; Stanford University, Kluwer Academic Publishers: New York, NY, USA, 1991.
  33. Oksanen, T.; Visala, A. Coverage Path Planning Algorithms for Agricultural Field Machines. J. Field Robot. 2009, 26, 651–668.
  34. Acar, E.U.; Choset, H.; Rizzi, A.A.; Atkar, P.N.; Hull, D. Morse Decompositions for Coverage Tasks. Int. J. Robot. Res. 2002, 21, 331–344.
  35. SStein, E.; Milnor, J.W.; Spivak, M.; Wells, R.; Wells, R.; Mather, J.N. Morse Theory; Princeton University Press: Princeton, NJ, USA, 1963; ISBN 978-0-691-08008-6.
  36. Acar, E.U.; Choset, H.; Atkar, P.N. Complete sensor-based coverage with extended-range detectors: A hierarchical decomposition in terms of critical points and Voronoi diagrams. In Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems, Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180), Maui, HI, USA, 29 October–3 November 2001; Volume 3, pp. 1305–1311.
  37. Acar, E.U.; Choset, H. Sensor-Based Coverage of Unknown Environments: Incremental Construction of Morse Decompositions. Int. J. Robot. Res. 2002, 21, 345–366.
  38. Wong, S. Qualitative Topological Coverage of Unknown Environments by Mobile Robots; The University of Auckland: Auckland, New Zealand, 2006.
  39. Wong, S.C.; MacDonald, B.A. Complete coverage by mobile robots using slice decomposition based on natural landmarks. In PRICAI 2004: Trends in Artificial Intelligence; Springer: Berlin/Heidelberg, Germany, 2004; pp. 683–692.
  40. Butler, Z.J.; Rizzi, A.A.; Hollis, R.L. Contact sensor-based coverage of rectilinear environments. In Proceedings of the 1999 IEEE International Symposium on Intelligent Control Intelligent Systems and Semiotics (Cat. No.99CH37014), Cambridge, MA, USA, 17 September 1999; pp. 266–271.
  41. Moravec, H.; Elfes, A. High resolution maps from wide angle sonar. In Proceedings of the 1985 IEEE International Conference on Robotics and Automation Proceedings, St. Louis, MO, USA, 25–28 March 1985; Volume 2, pp. 116–121.
  42. Zelinsky, A.; Jarvis, R.A.; Byrne, J.C.; Yuta, S. Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot. In Proceedings of the International Conference on Advanced Robotics, Tsukuba, Japan, 11 September 1993; Volume 13, pp. 533–538.
  43. Shivashankar, V.; Jain, R.; Kuter, U.; Nau, D. Real-Time Planning for Covering an Initially-Unknown Spatial Environment. In Proceedings of the Twenty-Fourth International FLAIRS Conference, Palm Beach, FL, USA, 20 March 2011.
  44. Gabriely, Y.; Rimon, E. Spiral-STC: An on-Line Coverage Algorithm of Grid Environments by a Mobile Robot. In Proceedings of the 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), Washington, DC, USA, 11–15 May 2002; Volume 1, pp. 954–960.
  45. Luo, C.; Yang, S.X.; Stacey, D.A.; Jofriet, J.C. A Solution to Vicinity Problem of Obstacles in Complete Coverage Path Planning. In Proceedings of the 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), Washington, DC, USA, 11–15 May 2002; Volume 1, pp. 612–617.
  46. Yang, S.X.; Luo, C. A Neural Network Approach to Complete Coverage Path Planning. IEEE Trans. Syst. Man Cybern. Part B Cybern. 2004, 34, 718–724.
  47. Hazon, N.; Mieli, F.; Kaminka, G.A. Towards Robust On-Line Multi-Robot Coverage. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation, ICRA 2006, Orlando, FL, USA, 15–19 May 2006; pp. 1710–1715.
  48. Luo, C.; Yang, S.X. A real-time cooperative sweeping strategy for multiple cleaning robots. In Proceedings of the of the IEEE Internatinal Symposium on Intelligent Control, Vancouver, BC, Canada, 30 October 2002; pp. 660–665.
  49. Luo, C.; Yang, S.X.; Stacey, D.A. Real-time path planning with deadlock avoidance of multiple cleaning robots. In Proceedings of the 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), Taipei, Taiwan, 14–19 September 2003; Volume 3, pp. 4080–4085.
  50. Easton, K.; Burdick, J. Inspection’. In Proceedings of the Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain, 18–22 April 2005; pp. 727–734.
  51. Ju, C.; Son, H. Multiple UAV Systems for Agricultural Applications: Control, Implementation, and Evaluation. Electronics 2018, 7, 162.
  52. Vincent, P.; Rubin, I. A framework and analysis for cooperative search using UAV swarms. In Proceedings of the 2004 ACM symposium on Applied Computing, New York, NY, USA, 14 March 2004; pp. 79–86.
  53. Maza, I.; Ollero, A. Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms. In Distributed Autonomous Robotic Systems 6; Springer: Tokyo, Japan, 2007; pp. 221–230.
  54. Alotaibi, E.T.; Alqefari, S.S.; Koubaa, A. LSAR: Multi-UAV Collaboration for Search and Rescue Missions. IEEE Access 2019, 7, 55817–55832.
  55. Acevedo, J.J.; Arrue, B.C.; Maza, I.; Ollero, A. Cooperative Large Area Surveillance with a Team of Aerial Mobile Robots for Long Endurance Missions. J. Intell. Robot. Syst. 2013, 70, 329–345.
  56. Acevedo, J.J.; Arrue, B.C.; Maza, I.; Ollero, A. Distributed Approach for Coverage and Patrolling Missions with a Team of Heterogeneous Aerial Robots under Communication Constraints. Int. J. Adv. Robot. Syst. 2013, 10, 28.
  57. Acevedo, J.J.; Arrue, B.C.; Diaz-Bañez, J.M.; Ventura, I.; Maza, I.; Ollero, A. One-to-One Coordination Algorithm for Decentralized Area Partition in Surveillance Missions with a Team of Aerial Robots. J. Intell. Robot. Syst. 2014, 74, 269–285.
  58. Xu, A.; Viriyasuthee, C.; Rekleitis, I. Efficient Complete Coverage of a Known Arbitrary Environment with Applications to Aerial Operations. Auton. Robots 2014, 36, 365–381.
  59. Balampanis, F.; Maza, I.; Ollero, A. Area Decomposition, Partition and Coverage with Multiple Remotely Piloted Aircraft Systems Operating in Coastal Regions. In Proceedings of the 2016 International Conference on Unmanned Aircraft Systems (ICUAS), Arlington, VA, USA, 7–10 June 2016; pp. 275–283.
  60. Balampanis, F.; Maza, I.; Ollero, A. Coastal Areas Division and Coverage with Multiple UAVs for Remote Sensing. Sensors 2017, 17, 808.
  61. Kallmann, M.; Bieri, H.; Thalmann, D. Fully Dynamic Constrained Delaunay Triangulations. In Geometric Modeling for Scientific Visualization; Springer: Berlin/Heidelberg, Germany, 2004; pp. 241–257.
  62. Shewchuk, J.R. Mesh generation for domains with small angles. In Proceedings of the Sixteenth Annual Symposium on Computational Geometry, New York, NY, USA, 1 May 2000; pp. 1–10.
  63. Balampanis, F.; Maza, I.; Ollero, A. Spiral-like coverage path planning for multiple heterogeneous UAS operating in coastal regions. In Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, 13–16 June 2017; pp. 617–624.
  64. Balampanis, F.; Maza, I.; Ollero, A. Area Partition for Coastal Regions with Multiple UAS. J. Intell. Robot. Syst. 2017, 88, 751–766.
  65. Hayat, S.; Yanmaz, E.; Brown, T.X.; Bettstetter, C. Multi-objective UAV path planning for search and rescue. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 29 May–3 June 2017; pp. 5569–5574.
  66. Trujillo, M.M.; Darrah, M.; Speransky, K.; DeRoos, B.; Wathen, M. Optimized flight path for 3D mapping of an area with structures using a multirotor. In Proceedings of the 2016 International Conference on Unmanned Aircraft Systems (ICUAS), Arlington, VA, USA, 7–10 June 2016; pp. 905–910.
  67. Darrah, M.; Trujillo, M.M.; Speransky, K.; Wathen, M. Optimized 3D mapping of a large area with structures using multiple multirotors. In Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, 13–16 June 2017; pp. 716–722.
  68. Lawrance, N.; Sukkarieh, S. Wind Energy Based Path Planning for a Small Gliding Unmanned Aerial Vehicle. In Proceedings of the AIAA Guidance, Navigation, and Control Conference, American Institute of Aeronautics and Astronautics, Chicago, IL, USA, 10–13 August 2009.
  69. Torres, M.; Pelta, D.A.; Verdegay, J.L.; Torres, J.C. Coverage Path Planning with Unmanned Aerial Vehicles for 3D Terrain Reconstruction. Expert Syst. Appl. 2016, 55, 441–451.
  70. Coombes, M.; Chen, W.-H.; Liu, C. Boustrophedon Coverage Path Planning for UAV Aerial Surveys in Wind. In Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, 13–16 June 2017; pp. 1563–1571.
  71. Coombes, M.; Fletcher, T.; Chen, W.-H.; Liu, C. Optimal Polygon Decomposition for UAV Survey Coverage Path Planning in Wind. Sensors 2018, 18, 2132.
  72. Cabreira, T.M.; Franco, C.D.; Ferreira, P.R.; Buttazzo, G.C. Energy-Aware Spiral Coverage Path Planning for UAV Photogrammetric Applications. IEEE Robot. Autom. Lett. 2018, 3, 3662–3668.
  73. Di Franco, C.; Buttazzo, G. Energy-Aware Coverage Path Planning of UAVs. In Proceedings of the 2015 IEEE International Conference on Autonomous Robot Systems and Competitions, Vila Real, Portugal, 8–10 April 2015; pp. 111–117.
  74. Li, D.; Wang, X.; Sun, T. Energy-Optimal Coverage Path Planning on Topographic Map for Environment Survey with Unmanned Aerial Vehicles. Electron. Lett. 2016, 52, 699–701.
  75. Artemenko, O.; Dominic, O.J.; Andryeyev, O.; Mitschele-Thiel, A. Energy-aware trajectory planning for the localization of mobile devices using an unmanned aerial vehicle. In Proceedings of the 2016 25th International Conference on Computer Communication and Networks (ICCCN), Waikoloa, HI, USA, 1–4 August 2016; pp. 1–9.
  76. Ahmadzadeh, A.; Keller, J.; Pappas, G.; Jadbabaie, A.; Kumar, V. An optimization-based approach to time-critical cooperative surveillance and coverage with UAVs. In Experimental Robotics: The 10th International Symposium on Experimental Robotics; Khatib, O., Kumar, V., Rus, D., Eds.; Springer: Berlin/Heidelberg, Germany, 2008; pp. 491–500.
  77. Araujo, J.F.; Sujit, P.B.; Sousa, J.B. Multiple UAV area decomposition and coverage. In Proceedings of the 2013 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA), Singapore, 16–19 April 2013; pp. 30–37.
  78. Majeed, A.; Lee, S. A New Coverage Flight Path Planning Algorithm Based on Footprint Sweep Fitting for Unmanned Aerial Vehicle Navigation in Urban Environments. Appl. Sci. 2019, 9, 1470.
  79. Majeed, A.; Hwang, S.O. A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments. Aerospace 2021, 8, 343.
  80. Cheng, C.-T.; Fallahi, K.; Leung, H.; Tse, C.K. Cooperative Path Planner for UAVs Using ACO Algorithm with Gaussian Distribution Functions. In Proceedings of the 2009 IEEE International Symposium on Circuits and Systems, Taipei, Taiwan, 24–27 May 2009; pp. 173–176.
  81. Kuiper, E.; Nadjm-Tehrani, S. Mobility Models for UAV Group Reconnaissance Applications. In Proceedings of the 2006 International Conference on Wireless and Mobile Communications (ICWMC’06), Bucharest, Romania, 29–31 July 2006; p. 33.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Computer Science, Artificial Intelligence; Robotics; Others
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Georgios Fevgas
View Times: 1.1K
Revisions: 3 times (View History)
Update Date: 10 Feb 2022
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback