Systematically Improving the Efficiency of Grid-Based Coverage Path Planning Methodologies in Real-World UAVs’ Operations
<p>Summary of UAVs’ remote sensing operations—parameters explained.</p> "> Figure 2
<p>Discretization procedure—representation of the ROI on grid.</p> "> Figure 3
<p>Representation of the ROI on two different grids. (<b>a</b>) Representation on a non-transformed grid. (<b>b</b>) Representation on rotated and shifted grid.</p> "> Figure 4
<p>Flowchart of the introduced CPP method with three ad-hoc coverage modes. Note: <span class="html-italic">Core Method</span> refers to [<a href="#B24-drones-07-00399" class="html-bibr">24</a>].</p> "> Figure 5
<p>Mega-cell and sub-cells—checks performed. (<b>a</b>) Step 1: mega-cell’s and sub-cells’ centers. (<b>b</b>) Step 2: rectangle with sub-cells’ centers vertices. (<b>c</b>) Step 3: cross shaped polygon.</p> "> Figure 6
<p>Representation of the ROI on the grid with the sub-nodes checking method.</p> "> Figure 7
<p>Representation of the ROI on the grid with the cross-checking method.</p> "> Figure 8
<p>Example of coverage paths with [<a href="#B24-drones-07-00399" class="html-bibr">24</a>] in testbed #1.</p> "> Figure 9
<p>Example of coverage paths with GCM in testbed #1.</p> "> Figure 10
<p>Example of coverage paths with BCM in testbed #1.</p> "> Figure 11
<p>Example of coverage paths with CCM in testbed #1.</p> "> Figure 12
<p>Modes’ ranking. Note: <span class="html-italic">SotA</span> refers to [<a href="#B24-drones-07-00399" class="html-bibr">24</a>].</p> "> Figure 13
<p>Modes evaluation in testbed #2. (<b>a</b>) [<a href="#B24-drones-07-00399" class="html-bibr">24</a>]. (<b>b</b>) GCM. (<b>c</b>) BCM. (<b>d</b>) CCM.</p> "> Figure 14
<p>Modes evaluation in testbed #3. (<b>a</b>) [<a href="#B24-drones-07-00399" class="html-bibr">24</a>]. (<b>b</b>) GCM. (<b>c</b>) BCM. (<b>d</b>) CCM.</p> "> Figure A1
<p>Spanning Tree Coverage algorithm explained. (<b>a</b>) Area representation on grid. (<b>b</b>) From cells to nodes. (<b>c</b>) MST generation. (<b>d</b>) MST as a navigation guide. (<b>e</b>) Circumnavigating path. (<b>f</b>) Final coverage trajectory.</p> ">
Abstract
:1. Introduction
1.1. Related Work
1.2. Contributions
- Geo-fenced Coverage Mode (GCM) which guarantees no crossing of the paths with the NGZs or the boundaries of the ROI.
- Better Coverage Mode (BCM) which guarantees no crossing of the paths with the NGZs but allows the paths to get slightly outside the ROI to provide better coverage in the marginal areas.
- Complete Coverage Mode (CCM) which guarantees no crossing of the paths with the NGZs or the boundaries of the ROI but also ensures complete coverage even for the most complex-shaped regions, by modifying the principals of the STC algorithm.
- The presented ideas and introduced methods for the representation of the ROI on grid, which manage to address the issues usually faced in real-world operations with grid-based CPP methods.
- A highly efficient in UAVs’ real-world operations CPP method, with the three aforementioned ad-hoc coverage modes.
- A quantitative simulated evaluation performed using publicly available ROIs, method, and metrics, which proves our method’s claimed benefits and sets a new benchmark for CPP methods in general (grid-based or not).
1.3. Paper Outline
2. Problem Formulation
2.1. CPP for UAVs’ Remote Sensing Operations
2.2. Representation of the ROI on Grid
- There will not be achieved complete coverage or the ROI, as parts of it are considered “obstacles”.
- Coverage paths can be generated outside the actual ROI since there are parts outside of it that are represented as ROI.
- Coverage paths can be generated so that they will cross the user-defined NGZs, for the same reason.
3. Methodology
3.1. Grid’s Cells Labeling Methods
3.1.1. Polygon
- Step 1: the first check performed is whether the center of each mega-cell of the grid (Figure 5a) is placed inside the polygon of the ROI. The ones that are placed outside of the ROI are labeled at this step as obstacle.
- Step 2: for the remaining mega-cells (that are not labeled as obstacle in the previous step), it is checked if the rectangle whose vertices are the centers of the four sub-cells (Figure 5b) is intersected by the polygon of the ROI. If an intersection is detected, then the mega-cell is labeled as an obstacle.
- Step 3: for the remaining mega-cells, a final additional check is performed. For each mega-cell a cross-shaped polygon is created, such as the one shown in Figure 5c. This polygon has strictly angles, the vertices inside the mega-cell are the sub-cells’ centers and the “external” sides of it are part of the sides of the mega-cell. The sides of the cross-shaped polygon are classified into four groups, specifically:
- –
- Group A: sides (1), (2), (3)
- –
- Group B: sides (4), (5), (6)
- –
- Group C: sides (7), (8), (9)
- –
- Group D: sides (10), (11), (12)
3.1.2. No-Go-Zones
3.2. Coverage Modes
3.2.1. Geo-Fenced Coverage Mode (GCM)
3.2.2. Better Coverage Mode (BCM)
3.2.3. Complete Coverage Mode (CCM)
4. Evaluation
4.1. Evaluation Methodology
- 0: Not covered
- 1: Covered—unique coverage
- ≥2: Covered—overlapping coverage
4.2. Modes Evaluation
5. Conclusions and Future Work
Author Contributions
Funding
Data Availability Statement
Conflicts of Interest
Nomenclature
Abbreviations | Meaning |
3D | Three Dimensional |
BCM | Better Coverage Mode |
CCM | Complete Coverage Mode |
CPP | Coverage Path Planning |
DARP | Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning |
DFA | Dynamic Floyd Algorithm |
GCM | Geo-fenced Coverage Mode |
GUI | Graphical User Interface |
mCPP | Multi-robot Coverage Path Planning |
MST | Minimum Spanning Tree |
N/A | Not Applicable |
N/E | Not Evaluated |
NED | North East Down (Coordinate System) |
NGZ | No Go Zone |
PPS | Parallel Partitioning along a Side |
PSAACO | Parallel Self-Adaptive Ant Colony Optimization Algorithm |
ROI | Region of Interest |
STC | Spanning Tree Coverage |
UAV | Unmanned Air Vehicle |
VTOL | Vertical Take-off and Landing |
WGS84 | World Geodetic (Coordinate) System 1984 |
Metrics | Meaning |
Length | Path Length |
N-Lenght | Normalized Path Length |
N-Turns | Normalized Number of Turns |
PoC | Percentage of Coverage |
PoOC | Percentage of Overlapping Coverage |
Time | Estimated execution time |
Turns | Number of Turns/Waypoints |
Variables | Meaning |
Capturing Density | |
Length of land covered by the horizonal side of the sensor | |
Scanning Density | |
Length of land covered by the vertical side of the sensor | |
h | Flying Altitude |
Horizontal Field of View | |
Ground Sampling Distance | |
WGS84 latitude | |
WGS84 longitude | |
Percentage of Frontlap | |
Percentage of Sidelap | |
Horizontal Resolution | |
Vertical Resolution | |
Vertical Field of View |
Appendix A. Spanning Tree Coverage (STC)
Appendix B. Pseudocode
Algorithm A1: A-ROICheck1 (Section 3.1.1-(1)) |
Algorithm A2: A-ROICheck2 (Section 3.1.1-(2)) |
Algorithm A3: A-NGZCheck1 (Section 3.1.2-(1)) |
Algorithm A4: A-NGZCheck2 (Section 3.1.2-(2)) |
Algorithm A5: A-GCM (Section 3.2.1) |
Algorithm A6: A-BCM (Section 3.2.2) |
Algorithm A7: A-CCM (Section 3.2.3) |
References
- Tsouros, D.C.; Bibi, S.; Sarigiannidis, P.G. A review on UAV-based applications for precision agriculture. Information 2019, 10, 349. [Google Scholar] [CrossRef] [Green Version]
- Raptis, E.K.; Krestenitis, M.; Egglezos, K.; Kypris, O.; Ioannidis, K.; Doitsidis, L.; Kapoutsis, A.C.; Vrochidis, S.; Kompatsiaris, I.; Kosmatopoulos, E.B. End-to-end Precision Agriculture UAV-Based Functionalities Tailored to Field Characteristics. J. Intell. Robot. Syst. 2023, 107, 23. [Google Scholar] [CrossRef]
- Karatzinis, G.D.; Apostolidis, S.D.; Kapoutsis, A.C.; Panagiotopoulou, L.; Boutalis, Y.S.; Kosmatopoulos, E.B. Towards an integrated low-cost agricultural monitoring system with unmanned aircraft system. In Proceedings of the 2020 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 1–4 September 2020; pp. 1131–1138. [Google Scholar]
- Alotaibi, E.T.; Alqefari, S.S.; Koubaa, A. Lsar: Multi-uav collaboration for search and rescue missions. IEEE Access 2019, 7, 55817–55832. [Google Scholar] [CrossRef]
- Zhang, N.; Nex, F.; Vosselman, G.; Kerle, N. Training a Disaster Victim Detection Network for UAV Search and Rescue Using Harmonious Composite Images. Remote Sens. 2022, 14, 2977. [Google Scholar] [CrossRef]
- Banić, M.; Miltenović, A.; Pavlović, M.; Ćirić, I. Intelligent machine vision based railway infrastructure inspection and monitoring using UAV. Facta Univ. Ser. Mech. Eng. 2019, 17, 357–364. [Google Scholar] [CrossRef]
- Kapoutsis, A.C.; Michailidis, I.T.; Boutalis, Y.; Kosmatopoulos, E.B. Building synergetic consensus for dynamic gas-plume tracking applications using UAV platforms. Comput. Electr. Eng. 2021, 91, 107029. [Google Scholar] [CrossRef]
- Koutras, D.I.; Kapoutsis, A.C.; Kosmatopoulos, E.B. Autonomous and cooperative design of the monitor positions for a team of uavs to maximize the quantity and quality of detected objects. IEEE Robot. Autom. Lett. 2020, 5, 4986–4993. [Google Scholar] [CrossRef]
- Scherer, J.; Rinner, B. Multi-UAV surveillance with minimum information idleness and latency constraints. IEEE Robot. Autom. Lett. 2020, 5, 4812–4819. [Google Scholar] [CrossRef]
- Galceran, E.; Carreras, M. A survey on coverage path planning for robotics. Robot. Auton. Syst. 2013, 61, 1258–1276. [Google Scholar] [CrossRef] [Green Version]
- Choset, H.; Pignon, P. Coverage path planning: The boustrophedon cellular decomposition. In Field and Service Robotics; Springer: Berlin/Heidelberg, Germany, 1998; pp. 203–209. [Google Scholar]
- Cabreira, T.M.; Brisolara, L.B.; Paulo R, F.J. Survey on coverage path planning with unmanned aerial vehicles. Drones 2019, 3, 4. [Google Scholar] [CrossRef] [Green Version]
- Almadhoun, R.; Taha, T.; Seneviratne, L.; Zweiri, Y. A survey on multi-robot coverage path planning for model reconstruction and mapping. SN Appl. Sci. 2019, 1, 847. [Google Scholar] [CrossRef] [Green Version]
- Nam, L.; Huang, L.; Li, X.J.; Xu, J. An approach for coverage path planning for UAVs. In Proceedings of the 2016 IEEE 14th International Workshop on Advanced Motion Control (AMC), Auckland, New Zealand, 22–24 April 2016; pp. 411–416. [Google Scholar]
- Kapoutsis, A.C.; Chatzichristofis, S.A.; Kosmatopoulos, E.B. DARP: Divide areas algorithm for optimal multi-robot coverage path planning. J. Intell. Robot. Syst. 2017, 86, 663–680. [Google Scholar] [CrossRef] [Green Version]
- Gabriely, Y.; Rimon, E. Spanning-tree based coverage of continuous areas by a mobile robot. Ann. Math. Artif. Intell. 2001, 31, 77–98. [Google Scholar] [CrossRef]
- Cabreira, T.M.; Ferreira, P.R.; Di Franco, C.; Buttazzo, G.C. Grid-based coverage path planning with minimum energy over irregular-shaped areas with UAVs. In Proceedings of the 2019 International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, GA, USA, 11–14 June 2019; pp. 758–767. [Google Scholar]
- Ghaddar, A.; Merei, A. Energy-aware grid based coverage path planning for UAVs. In Proceedings of the SENSORCOMM, Nice, France, 27–31 October 2019; pp. 34–45. [Google Scholar]
- Ghaddar, A.; Merei, A.; Natalizio, E. PPS: Energy-Aware grid-based coverage path planning for UAVs using area partitioning in the presence of NFZs. Sensors 2020, 20, 3742. [Google Scholar] [CrossRef]
- Huang, X.; Sun, M.; Zhou, H.; Liu, S. A multi-robot coverage path planning algorithm for the environment with multiple land cover types. IEEE Access 2020, 8, 198101–198117. [Google Scholar] [CrossRef]
- Xiao, S.; Tan, X.; Wang, J. A simulated annealing algorithm and grid map-based UAV coverage path planning method for 3D reconstruction. Electronics 2021, 10, 853. [Google Scholar] [CrossRef]
- Cho, S.W.; Park, J.H.; Park, H.J.; Kim, S. Multi-uav coverage path planning based on hexagonal grid decomposition in maritime search and rescue. Mathematics 2021, 10, 83. [Google Scholar] [CrossRef]
- Gong, Y.; Chen, K.; Niu, T.; Liu, Y. Grid-Based coverage path planning with NFZ avoidance for UAV using parallel self-adaptive ant colony optimization algorithm in cloud IoT. J. Cloud Comput. 2022, 11, 29. [Google Scholar] [CrossRef]
- Apostolidis, S.D.; Kapoutsis, P.C.; Kapoutsis, A.C.; Kosmatopoulos, E.B. Cooperative multi-UAV coverage mission planning platform for remote sensing applications. Auton. Robot. 2022, 46, 373–400. [Google Scholar] [CrossRef]
- Kakarla, S.C.; Ampatzidis, Y. Types of Unmanned Aerial Vehicles (UAVs), Sensing Technologies, and Software for Agricultural Applications. Available online: https://edis.ifas.ufl.edu (accessed on 3 May 2023).
- Cai, G.; Chen, B.M.; Lee, T.H. Coordinate systems and transformations. In Unmanned Rotorcraft Systems; Springer: Berlin/Heidelberg, Germany, 2011; pp. 23–34. [Google Scholar]
- Englot, B.; Hover, F. Sampling-based coverage path planning for inspection of complex structures. In Proceedings of the International Conference on Automated Planning and Scheduling, Sao Paulo, Brazil, 25–19 June 2012; Volume 22, pp. 29–37. [Google Scholar]
- Chen, J.; Du, C.; Zhang, Y.; Han, P.; Wei, W. A clustering-based coverage path planning method for autonomous heterogeneous UAVs. IEEE Trans. Intell. Transp. Syst. 2021, 23, 25546–25556. [Google Scholar] [CrossRef]
- Gower, J.C.; Ross, G.J.S. Minimum Spanning Trees and Single Linkage Cluster Analysis. Appl. Stat. 1969, 18, 54. [Google Scholar] [CrossRef] [Green Version]
Method | Real-World ROI | Support NGZs | Geo-Fenced Path(s) | Complete Coverage |
---|---|---|---|---|
[14] | ✓ | ✗ | ✗ | N/E * |
[15] | ✗ | ✓ | N/A | N/A |
[17] | ✓ | ✓ | ✗ | N/E |
[18] | ✓ | ✗ | ✗ | N/E ** |
[19] | ✓ | ✓ | ✗ | N/E ** |
[20] | ✓ *** | ✓ | ✗ | N/E |
[21] | ✓ | ✗ | ✗ | N/E ** |
[22] | ✓ | ✗ | ✗ | N/E |
[23] | ✓ | ✓ | ✓ **** | N/E ** |
[24] | ✓ | ✓ | ✗ | ✗ |
Features | GCM | BCM | CCM |
---|---|---|---|
Geo-fenced Trajectories | ✓ | ✗ | ✓ |
Turns | ✓ | ✓ | ✗ |
Non-Overlapping Trajectories | ✓ | ✓ | ✗ |
Complete Coverage | ✗ | ✗ | ✓ |
Short | Metric | Unit |
---|---|---|
PoC | Percentage of Coverage (Scans ) | % |
PoOC | Percentage of Overlapping Coverage (Scans ) | % |
Turns | Number of Turns/Waypoints | - |
N-Turns | Normalized Number of Turns | |
Length | Path Length | km |
N-Length | Normalized Path Length | |
Time | Estimated execution time (3 m/s speed & 1 s delay/turn) | min |
Metrics | [24] | GCM | BCM | CCM |
---|---|---|---|---|
PoC | 95.92% | 95.79% | 98.95% | 99.97% |
PoOC | 51.90% | 52.23% | 53.28% | 59.67% |
Turns | 75.35 | 75.65 | 79.65 | 103.50 |
N-Turns | 0.10 | 0.10 | 0.12 | 0.18 |
Length | 21,799.96 | 21,799.95 | 33,895.96 | 26,753.30 |
N-Length | 23.69 | 23.66 | 39.17 | 30.86 |
Time | 122.37 | 122.37 | 189.64 | 150.35 |
Metrics | [24] | GCM | BCM | CCM |
---|---|---|---|---|
PoC | 94.19% | 95.24% | 97.33% | 100.00% |
PoOC | 49.68% | 48.63% | 50.07% | 87.30% |
Turns | 8 | 8 | 12 | 25 |
N-Turns | 0.21 | 0.21 | 0.32 | 0.67 |
Length | 800.00 | 799.99 | 1119.99 | 1744.89 |
N-Length | 21.44 | 21.44 | 30.02 | 46.77 |
Time | 4.58 | 4.58 | 6.42 | 10.11 |
Metrics | [24] | GCM | BCM | CCM |
---|---|---|---|---|
PoC | 95.71% | 95.85% | 99.32% | 99.98% |
PoOC | 53.44% | 53.51% | 54.19% | 60.26% |
Turns | 63 | 64 | 72 | 83 |
N-Turns | 0.11 | 0.11 | 0.12 | 0.14 |
Length | 13,759.99 | 13,759.98 | 16,159.98 | 18,044.70 |
N-Length | 23.87 | 23.87 | 28.03 | 31.30 |
Time | 77.49 | 77.51 | 90.98 | 101.63 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Apostolidis, S.D.; Vougiatzis, G.; Kapoutsis, A.C.; Chatzichristofis, S.A.; Kosmatopoulos, E.B. Systematically Improving the Efficiency of Grid-Based Coverage Path Planning Methodologies in Real-World UAVs’ Operations. Drones 2023, 7, 399. https://doi.org/10.3390/drones7060399
Apostolidis SD, Vougiatzis G, Kapoutsis AC, Chatzichristofis SA, Kosmatopoulos EB. Systematically Improving the Efficiency of Grid-Based Coverage Path Planning Methodologies in Real-World UAVs’ Operations. Drones. 2023; 7(6):399. https://doi.org/10.3390/drones7060399
Chicago/Turabian StyleApostolidis, Savvas D., Georgios Vougiatzis, Athanasios Ch. Kapoutsis, Savvas A. Chatzichristofis, and Elias B. Kosmatopoulos. 2023. "Systematically Improving the Efficiency of Grid-Based Coverage Path Planning Methodologies in Real-World UAVs’ Operations" Drones 7, no. 6: 399. https://doi.org/10.3390/drones7060399