Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection
Drones · 01.09.2023 · 7 (9) · 563
DOI: 10.3390/drones7090563 ↗Kurz gefasst
Fachartikel in der Zeitschrift Drones, online erschienen am 01.09.2023. Verfasst von Lea Matlekovic und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 60 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Union’s Horizon 2020 Research and Innovation Programme.
Abstract (Originalsprache)
This article presents a constraint modeling approach to global coverage-path planning for linear-infrastructure inspection using multiple autonomous UAVs. The problem is mathematically formulated as a variant of the Min–Max K-Chinese Postman Problem (MM K-CPP) with multi-weight edges. A high-level constraint programming language is used to model the problem, which enables model execution with different third-party solvers. The optimal solutions are obtained in a reasonable time for most of the tested instances and different numbers of vehicles involved in the inspection. For some graphs with multi-weight edges, a time limit is applied, as the problem is NP-hard and the computation time increases exponentially. Despite that, the final total inspection cost proved to be lower when compared with the solution obtained for the unrestricted MM K-CPP with single-weight edges. This model can be applied to plan coverage paths for linear-infrastructure inspection, resulting in a minimal total inspection time for relatively simple graphs that resemble real transmission networks. For more extensive graphs, it is possible to obtain valid solutions in a reasonable time, but optimality cannot be guaranteed. For future improvements, further optimization could be considered, or different models could be developed, possibly involving artificial neural networks.
Förderung
- European Union’s Horizon 2020 Research and Innovation Programme
Zitieren
APA
Matlekovic, L., & Schneider-Kamp, P. (2023). Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection. Drones, 7(9), 563. https://doi.org/10.3390/drones7090563
Vancouver
Matlekovic L, Schneider-Kamp P. Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection. Drones. 2023;7(9):563. doi:10.3390/drones7090563
BibTeX
@article{Matlekovic2023,
author = {Matlekovic, Lea and Schneider-Kamp, Peter},
title = {Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection},
journal = {Drones},
year = {2023},
volume = {7},
number = {9},
pages = {563},
doi = {10.3390/drones7090563}
}
EUVIMED