Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection

Lea Matlekovic*, Peter Schneider-Kamp

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

7 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number563
JournalDrones
Volume7
Issue number9
Number of pages25
ISSN2504-446X
DOIs
Publication statusPublished - Sept 2023

Keywords

  • constraint programming
  • infrastructure inspection
  • multi-UAVs
  • optimization
  • path planning

Fingerprint

Dive into the research topics of 'Constraint Programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection'. Together they form a unique fingerprint.

Cite this