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

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.

1. Introduction

Autonomous unmanned aerial vehicles (UAVs), also known as drones, are emerging as a technology to replace manual tasks such as surveillance, monitoring, search and rescue, transportation, and infrastructure inspection [1]. Although it is currently possible to develop an autonomous UAV with a relatively high level of autonomy, there are still existing challenges that require the maturity of key technologies [2]. The main issues involve the battery capacity, which is required to be high in order to run computationally demanding processes on board the autonomous vehicle. Currently, researchers are attempting to balance between running important algorithms on board and off-boarding heavy computation by relying on a connection between the vehicle and a ground station. For simple tasks that only require localized movements, a stable connection can be achieved. However, if the task requires a high level of autonomy and flight beyond the visual line of sight, a stable connection becomes another great challenge.

This paper focuses on the challenge of continuous autonomous inspection of linear infrastructures such as transmission lines and railways, as well as bridges, using multiple UAVs. Nowadays, UAVs are already in use for infrastructure inspection purposes, as they reduce inspection costs and increase the safety of operators conducting the inspection [3]. However, they are either controlled manually or by using a simple automatic controller to follow the predetermined path. Furthermore, evolving regulations regarding flying UAVs still do not permit flight beyond visual line of sight (BVLOS), limiting the employment of autonomous UAVs for continuous infrastructure inspection [4]. Challenges such as battery capacity, stable communication, and regulations require further technological development in different research fields and the definition of certain rules for UAV air traffic. Such advancements could take time until autonomous BVLOS flight is entirely adopted into society. However, those are not the only challenges for autonomous flying agents.

In order to enable UAVs to fly autonomously, a set of different algorithms has to be developed and implemented to ensure autonomous decision-making. Such algorithms use previously known information about the environment or process data collected by UAV sensors to obtain environmental awareness in real time and produce appropriate instructions for UAVs [5]. Different path-planning algorithms have been proposed depending on the purpose of autonomous flight. For continuous infrastructure inspection, we assume the availability of multiple UAVs with infrastructure locations known in advance. The objective is to inspect all targets in a minimum total time. The algorithm is developed under the assumption that UAV self-recharging is accomplished with the attaching of the UAV to the transmission lines and its charging from there, as presented in [6]. This topic currently attracts substantial research attention [7,8,9,10], as using current from power lines to recharge UAVs could support not only autonomous inspections, but also numerous civil applications of UAVs. This approach is demonstrated in [11] for charging multi-rotor UAVs with a battery capacity of 12,000 mAh in 2.4 h and in [12] for charging fixed-wing UAVs with a battery capacity of 2200 mAh in 2.2 h from alternating-current power lines. Although it is currently developed as a proof of concept, we believe that the maturity of that technology is a prerequisite for continuous, long-distance BVLOS flight, as an alternative solution would be the placement of numerous charging stations along the way, which is expensive and could potentially eliminate the cost benefits of autonomous UAV infrastructure inspection. During an inspection, UAVs could attach themselves to the line, recharge, and continue executing their mission with a full battery. An ideal solution would be to enable wireless charging from power lines, as conceptually presented in [13], where UAVs would be able to conduct the mission and charge at the same time. However, this research question has not been properly investigated and requires more time and attention to be explored. We decided not to take charging time into account while determining coverage paths under the assumption that all drones start fully charged and that it takes equally long for each drone to deplete the battery as well as to fully charge it again. The development of a reliable battery depletion model would have to take into account running on-board AI algorithms that would assist a local path planner in deciding where to focus the inspection. Therefore, we leave it for future investigation, when more research regarding running global and local planners together with AI algorithms could be available. This work focuses on global path planning, which should be accompanied by an on-board re-planner in order to provide a complete inspection solution. As we cannot rely on a constant connection, the inspection mission is pre-planned and consists of mission flight points sent to the vehicles. The main question we investigate throughout this paper is how to plan paths on a global level in order to cover every infrastructure segment in minimal total time by having multiple UAVs available.

This problem traces its roots back to what in the literature can be found as the Chinese Postman Problem (CPP), which, for a given connected graph representing roads and intersections, determines the shortest closed walk for a postman to traverse each road at least once. It is one of the well-known arc-routing problems, and many different variations have been investigated in [14], including multiple postmen, where the objective is to minimize the total distance traveled. However, our case has increased complexity, as it requires a more balanced solution in which multiple vehicles cover a graph decomposition in a minimum total time. The objective of our problem is to minimize the cost of the longest route. We present a special case of the Min–Max K-Chinese Postman Problem (MM K-CPP) [15], where edges can be reused after they have been inspected if that contributes to lowering the total coverage time. We discuss trade-offs of having the same flight costs compared with using different costs depending on the UAV flight type (inspection/deadheading). Those inspection arcs carry higher costs than the ones that are just for traversal, and they must be covered. Furthermore, we experiment with unrestricted UAV starting and ending positions, making this problem highly complex to solve. We propose the solution by defining constraints for multiple problem variants, and we discuss their suitability under different circumstances. We achieve fast computation for small graphs with all model variants, which is good enough for our use case of linear infrastructure inspection. Linear infrastructure graphs, even if large, can be approximated with smaller ones without losing information. Larger graphs can be solved as well. However, depending on the generality of the model, we cannot always guarantee that the solution found in a reasonable time is the best one, as the execution time rises exponentially and a time limit has to be applied.

This article is organized as follows. Section 2 provides an overview of related works regarding the planning of UAV operations as well as similar arc routing problems. Section 3 presents the motivation for solving this problem and a futuristic concept of autonomous UAV linear infrastructure inspection. In Section 4, the problem is defined mathematically and conceptually. Section 5 describes the methodology for solving the problem by defining constraints we have implemented using the constraint modeling tool. Section 6 presents experimental results. We conclude in Section 7 by discussing trade-offs, performance, limitations, and future improvements.

2. Related Work

In this section, we present related work regarding UAV operations planning with a focus on coverage path planning using graph structures, as these use cases tackle similar problems to ours. Furthermore, we present well-investigated, similar problem formulations that preceded the MM K-CPP as well as their variations. We compare similarities and emphasize differences in our approach adapted for the specific purpose of autonomous UAVs’ continuous inspection of linear infrastructure.

2.1. Uavs Operations Planning

Planning UAV autonomous operations requires the development of path-planning approaches according to the type of operation. Different types of UAV operations have been identified in [16] such as area coverage, search operations, routing for a set of locations, data gathering and recharging in a wireless sensor network, allocating communication links and computing power to mobile devices, and operations of a self-organizing network of drones. Although our focus is on area coverage and routing operations, some other optimization types also propose approaches relevant to our problem. The planning of data-gathering operations may involve UAVs covering a set of locations in order to transfer data from sensors placed in an unavailable area, and the planning of the allocation of communication links may involve the allocation of drones as a wireless flying ad hoc network (FANET). Such problems involve solving coverage path planning under numerous constraints, typically with multiple optimization criteria. In [17], the authors propose a method to identify areas where the network coverage is not satisfying and use UAVs to serve as flying base stations to cover those areas. They identify the central point of each area and simply send UAVs in a straight trajectory to visit them and hover above. A similar problem is proposed in [18] with different optimization criteria for the selection of hovering points and solving TSP for coverage solutions. The authors employ trajectory planning based on the meta-heuristic Cuckoo search algorithm [19] and optimize either by energy consumption, latency, throughput optimization, or efficiency with a limited battery. In [20], the authors propose a solution for offloading computations from mobile devices to UAVs by optimizing trajectory to minimize mobile device energy consumption while satisfying the quality of service requirements. A mixed-integer non-convex optimization algorithm is proposed in [21,22,23] for enabling sustainable communication services to multiple ground users using UAVs. In the first work, the subcarrier allocation policy and the trajectory of the UAV are jointly optimized while taking into account the minimum required data rate for each user node, no-fly zones, the maximum UAV cruising speed, and initial/final UAV locations. In the second work, UAVs are powered by solar energy, taking into account aerodynamic power consumption, solar energy harvesting, finite energy storage capacity, and the quality-of-service requirements of the users. Despite the non-convexity of the optimization problem, the authors solve it optimally by applying monotonic optimization. The third work maximizes the minimum throughput over all ground users in the down-link communication by optimizing the multi-user communication scheduling and association jointly with the UAV’s trajectory and power control. The authors in [24] propose a mixed-integer programming (MIP) approach maximizing the throughput provided by the UAVs over a set of areas, energy sold to the grid as UAVs are solar powered, and energy bought from the grid. UAVs are intended to serve as flying stations to aid a fixed-based station of a cellular network, and there is one charging site available. A more complex problem with multiple base stations and charging sites is later solved in [25] using both the MIP approach and novel heuristics, as the MIP was not able to provide solutions for large instances in a reasonable time. Although these problems, when compared to ours, involve more optimization criteria and the optimization is not focused on fast mission completion, they suggest that MIP could also be a viable approach for solving our coverage path planning problem.

Area coverage operations require a UAV to cover or monitor an area using a sensor with a limited footprint. This challenge arises in terrain reconstruction [26], monitoring [27], agriculture for crop observations [28], and infrastructure inspection [29]. Such operations require finding coverage paths for UAVs so that all points within a designated area are covered at least once. Common objectives aim to minimize distance-related cost functions [30], completion time [31], or energy consumption [32]. Coverage paths can be established in two dimensions, as demonstrated in [33], or in three dimensions, as shown in [34]. The majority of coverage strategies rely on decomposing the target area into cells represented in a graph structure [35]. This transforms the problem into a routing operation, such as the traveling salesman problem (TSP) or the vehicle routing problem (VRP), to cover graph nodes, or the Chinese postman problem (CPP) to cover graph edges. For an extensive survey of published research regarding VRP over the last five decades, we refer interested readers to [36]. We focus on recently published coverage solutions involving UAVs, where coverage areas are represented as a graph, and a routing solution is applied to cover them.

In recent years, multiple area coverage solutions for UAVs have been proposed. However, solutions involving multiple UAVs are lacking [37]. The solution presented in [38] aims to cover an area using multiple fixed-wing UAVs in the shortest possible time. The approach involves representing the area as a graph structure and employing a lawnmower pattern for coverage. The algorithm’s objective is to minimize the total coverage time by adjusting the number of vehicles, considering each UAV’s speed and battery level. The coverage algorithm is developed as a variant of VRP, wherein UAVs are constrained to visit all nodes in a graph with a predetermined pattern. For the purposes of continuous linear infrastructure inspection, such an approach would not be suitable as it cannot guarantee the coverage of all edges. As stated by the authors, the main issue with this approach is that a solution cannot be found in cases where the area is too large, so the maximum number of available UAVs and their individual flight times are not sufficient to cover it all. Thus, this approach is suitable for limited area coverage, but not for our infrastructure inspection problem. Area coverage problems have received substantial attention, with some being proven to be NP-hard, such as the Rural Postman Problem (RPP) [15]. Consequently, several heuristic solutions have been proposed. These include coverage of disjoint areas using one UAV [39] as well as solutions using multiple UAVs [40,41]. Such heuristics employ two-step approaches to obtain near-optimal paths, involving determining visiting areas and ensuring coverage for each identified area. In [42], the authors address a problem similar to ours, known as the Length-Constrained K-Drones Rural Postman Problem (LC K-DRPP). This problem involves multiple UAVs jointly servicing a set of network lines. Unlike our scenario, only specific lines in the graph need servicing, allowing UAVs to enter a line at any point, service a portion, and exit through another point. Furthermore, UAVs have a limited range, implying a maximum distance range for each. The authors provide both an exact solution using the branch-and-cut algorithm and a heuristic approach for larger instances. Although this solution also differentiates between servicing and deadheading costs, our solution differs as our graph instances are interconnected and do not require the identification of optimal entry and exit points. Moreover, the LC K-DRPP limits the UAV range as it assumes that UAVs have to go back to the depot to charge. Even if the distance limit is removed, applying this approach in our case would cause unnecessarily high computation costs, as our problem does not require the interconnection of edges.

Although many articles regarding coverage path planning for infrastructure inspection have been found in the literature, none of them are focused on larger areas. Most of them focus on particular structures that are located in smaller areas. Infrastructure that is spread across countries and continents, such as transmission networks, railways, and highways, requires different approaches for autonomous UAV inspection. The objective of our work is to describe this problem conceptually and mathematically, as well as provide a viable solution.

2.2. Arc Routing Problems

The MM K-CPP evolved, together with many other arc routing problems, from a practical approach to graph theory. In graph theory, we find similar problems analyzed from a theoretical perspective, such as graph partitioning and decomposition problems. Graph partition problems concern dividing graphs according to the number of vertices in each partition or based on different criteria, considering costs assigned to vertices. This formulation could not be used for our problem as, during the partitioning, some edges are cut and excluded from the resulting partitions. Graph decomposition problems describe our problem more accurately, as graphs are decomposed into subgraphs according to set criteria and by using a vertex cut that preserves all the edges. A variation of such a problem with multiple edges is found in [43]. The authors approach it from the perspective of a graph theory and analyze the computational complexity and conditions required for a graph to have an NP-complete decomposition.

With foundations in graph theory, general routing problems, such as node routing and arc routing, are inspired by real-world problems, mostly vehicle routing, delivery, coverage, and collection tasks [44]. Some well-known arc routing problems are undirected CPP and directed CPP, which are known to be NP-complete. More complex variations, such as windy CPP and hierarchical CPP, also have exact solutions obtainable in polynomial time under certain conditions but, in general, are considered NP-hard. The most complex variations are mixed CPP, capacitated CPP, and MM K-CPP, which are NP-hard [45]. We focus our literature review on the MM K-CPP and its variants, as they share the most similarities to our problem.

The MM K-CPP is defined in [15] as follows. Given an undirected graph $G=(V,E)$ where V is a set of vertices and E is a set of edges, a cost $c_e\ge 0$ for each edge $e\in E$, a fixed number $K\ge 2$ of vehicles, and a depot node, find K closed walks starting and ending at the depot, traversing each edge at least once such that the cost of the longest of the K walks is minimal. A branch-and-cut algorithm based on the sparse formulation given in [46] is proposed in [47]. The model forces each edge to be serviced exactly once, although it can be used again for traversal. In contrast to our problem, each of the K vehicles is traversing a circular tour starting and ending at the selected depot. Furthermore, this problem does not differentiate costs depending on the flight type (servicing). Later, the authors proposed multiple heuristic solutions in [48], which led to the development of the tabu search algorithm presented in [49], which can be considered state-of-the-art. The approach is tested on the same set of instances used in [47], resulting in many near-optimal or optimal solutions, with improvement for some instances reaching up to 20–30%. This algorithm is extended in [50] and applied for the determination of security guards’ routes. It solves the Min-Max K-Rural Postman Problem (MM K-RPP), where not all edges in the graph have to be serviced. The approach improved surveillance by achieving a more balanced frequency of street traversals. A similar problem of security patrolling is presented in [51], and multiple variants of the problem are solved using mixed integer linear programming. Results clearly show that the execution time increases as the problem is generalized.

Similar to the MM K-RPP, the Min-Max K-Windy Rural Postman Problem (MM K-WRPP) searches for K routes on a windy graph. Each edge has two different costs, depending on the direction of traversal. The same authors proposed exact solutions, such as the branch-and-cut algorithm in [52,53] and branch-price-and-cut in [54] as well as a metaheuristic solution in [55]. The branch-and-cut algorithm follows a similar approach as in [47], except it differentiates between traversal directions. Improved results for a larger number of vehicles are achieved with the branch-price-and-cut algorithm. The metaheuristic approach begins by obtaining multiple WRPP solutions and, through three optimization steps, determines a single route split into K routes. Multiple improvements are carried out until the final results are achieved. The achieved results are compared to the results obtained by the branch-and-cut approach, deriving an average gap between the costs of solutions of only 0.4% with the maximum average processing time of 56.2 s for 2-vehicle instances.

Another problem variant named the Downhill Plow Problem (DPP) is presented in [56] and extended to the MM K-DPP in [57]. It bears a great similarity to our problem as it involves multiple different costs for plowing streets based on the plowing status (plow/deadhead) as well as the direction (uphill/downhill). In our case, the costs are differentiated based only on the servicing status (inspect/deadhead) in both directions, and we obtain the exact solution for smaller graph instances. The authors propose a heuristic solution tested on larger graphs, obtaining great-quality results. The computation time for graphs with up to 150 edges is reasonable for a different number of vehicles. As the number of vehicles increases, the processing time increases, depending on the size of the graph. This approach could be used for our problem in the case of heavy winds, where the difference in uphill and downhill costs would represent the wind direction. However, generating such a graph in near real-time would be challenging as the wind directions are always changing. Therefore, we do not take wind into account. Furthermore, for representing linear infrastructure in a graph structure, even in larger areas, approximation with small graphs is highly reliable.

Our problem is another variant of the above-mentioned problems that, to the best of our knowledge, has not been investigated before or applied for autonomous UAV coverage path planning. Moreover, we investigate a problem modification with unrestricted starting and ending nodes that has not been commonly researched due to its generality and lack of applications. We experiment with node determination through optimization as we want to reduce unnecessary flights due to strict flight regulations and the costs of inspection. Furthermore, in our problem formulation, we differentiate the costs of inspecting and deadheading regardless of the direction where deadheading can hold costs depending on the areas around the respective linear infrastructure. When the infrastructure is located in a residential area, the deadheading costs can be increased to lower the probability of disturbing residents with multiple flights. We present a novel approach for autonomous UAV infrastructure inspection by using a constraint programming language that is solver-independent.

3. Preliminaries

Motivation for this work emerged from the idea of infrastructure inspection using autonomous UAVs tackled in the Drones4Safety project [58]. The project investigates different approaches to autonomous UAV inspections and proposes the most suitable ones. In our recent work [59], we developed a cloud system that is supposed to serve as a tool for autonomous inspection mission planning, execution, and monitoring. The objective is to have an operator behind the screen provide high-level tasks to a swarm of autonomous UAVs, which require numerous algorithms implemented both in the cloud and on board the UAVs. In the cloud, the algorithms use knowledge about the environment available in advance to pass information and instructions to UAVs. On the other hand, on-board algorithms tackle uncertainties by using sensors to obtain information about the environment in real time and instruct a UAV to react appropriately. The operator interacts with the swarm through a map-based web interface, as shown in Figure 1. The map shows a graph made out of the transmission network in Denmark with targets (i.e., power towers) that can be chosen to direct the swarm to inspect them. Information about target locations is collected from the Open Street Maps, enabling us to write custom algorithms for building graph structures where edge weights are calculated as distances between targets. The shapes of the example graphs used for experiments in this article are inspired by the graph of the transmission network in Denmark, built from real-world data from our previous work. The backend system implements high-level path planning calculations. The resulting paths contain target locations (nodes) that may be sent to UAVs as flight waypoints, using the same approach as described and tested in the Gazebo simulation environment in [59]. Subsequently, UAVs use point-to-point flight controllers to navigate according to the waypoints received from the cloud system. The initially implemented algorithm for high-level path planning is only able to solve the Vehicle Routing Problem (VRP), meaning if there are specific targets that should be inspected, the operator can choose them on the map, and the algorithm determines which UAV is inspecting which target. However, for maintenance purposes, we would like to inspect all power towers and transmission lines between them. Therefore, the VRP solution is not the right choice. In order to inspect a wider area where targets are located, the operator should be able to select portions of a graph or an entire graph, select the available number of UAVs, and obtain coverage paths, resulting in the fastest inspection. By making the inspection as fast as possible, the drones are sooner available for the next mission, which improves efficiency and, naturally, reduces inspection costs. This article conceptually investigates the suitability of proposed problem formulations and constraint modeling solutions for continuous autonomous UAV coverage inspection missions.

4. Problem Formulation

On a high level, this problem concerns coverage path planning for autonomous UAV inspection of linear infrastructure. The objective is to inspect all given paths in minimal total time by using multiple UAVs. In this section, we consider multiple problem formulations and present the reasoning behind them.

4.1. Edge-Disjoin Formulation

Let G be an undirected and weighted graph $G=(V,E,w)$, representing the inspection path, where V is a set of vertices representing geographical locations and E is a set of edges, each having an inspection weight $w:E\to {\mathbb{R}}^{+}$, which is represented as the distance between the neighboring vertices multiplied by some factor. Let k be the number of UAVs ready to traverse the graph for the purpose of infrastructure inspection. The objective is to find a decomposition of the graph G into a collection of k edge-disjoint subgraphs $H_1,H_2,\dots ,H_k$ such that every edge of G belongs to exactly one H and that the maximum over sums of weights of each subgraph $max(\sum w\left(H_1\right),\sum w\left(H_2\right),\dots ,\sum w\left(H_k\right))$ is minimal. If we assume that flight speed is constant and equal for all vehicles, this constraint ensures minimal total inspection time as the maximum path a UAV is to cover over all k subgraphs is minimal. We assume that the initial graph is connected and that starting as well as ending nodes in each subgraph are unconstrained, i.e., UAVs can start and end the inspection at any node. Such a formulation is chosen as fixing the starting or ending position would potentially highly increase the total inspection time. Furthermore, a higher total inspection time consequentially increases the time UAVs would spend charging attached to the transmission lines. For such a solution to exist, the graph G either has to be an Eulerian graph, or its decomposition has to result in semi-Eulerian subgraphs. That would guarantee that each edge can be traversed exactly once, i.e., that a Eulerian trail exists in each subgraph. The Eulerian trail exists in any undirected graph if it has exactly zero or two vertices with an odd degree [60], which in our case we cannot guarantee when a random graph is given. Even if it were possible to reasonably decompose a non-Eulerian graph into n semi-Eulerian subgraphs, we cannot assure that the number of vehicles k is going to be equal to n. An optimal decomposition of an example graph $G1$ for this edge-disjoint problem is shown in Figure 2. This solution is somewhat unbalanced, with a total cost of inspecting $H_1$ equal to 16, while the total cost of inspecting $H_2$ is 24.

4.2. Eulerian Trail Formulation

In order to ensure that the solution can always be found, it must be possible to find a Eulerian trail in any given graph. One approach to enabling that is to allow edges to be reused by UAVs. Virtually, it may be described as creating edge duplicates, ensuring that the degree of each vertex of G is even, meaning that the graph is Eulerian and that the solution of the Eulerian trail can always be found. Therefore, the decomposition is no longer edge-disjoint. This formulation is the MM K-CPP, with the difference being in unrestricted depots. Although the solution shown in Figure 2 would be the same by using this approach, it allows us to obtain solutions for some graphs that would otherwise be unsolvable using the edge-disjoint approach, for example, the graphs shown in Figure 3.

4.3. Multi-Weight Formulation

Knowing that edges may be reused by UAVs and that each traversal represents an inspection, the question of total traversal cost arises. As there is no purpose in inspecting the same edge multiple times and under the assumption that during the inspection UAVs fly slower than their maximum speed, we consider decreasing the cost for each traversal not involving the inspection. Such an approach would decrease the total inspection time while ensuring that each edge is inspected only once.

We propose a problem reformulation where the graph is defined as $G=(V,E,w^i,w^f)$, and each edge $e\in E$ has two weight functions $w^i$ and $w^f$. Weight $w^i$ represents the distance between vertices penalized by some factor, as we suppose that inspection flight is slower than flying without engaging in inspection activities. For flying without inspection, weight $w^f$ represents a non-penalized distance. The objective is to find a decomposition with a shorter total inspection time than in the initial problem formulations by allowing edges to be included in multiple subgraphs, but with the inspection flight conducted in only one. Therefore, only one subgraph considers e with both $w^i$ and $w^f$ as coverage path candidates, while others consider only $w^f$. Edges with $w^i$ have to be covered, while those with $w^f$ are optional and are covered only if that minimizes the total inspection time. Figure 4 shows a solution for the described problem on the example graph $G1$, resulting in more balanced inspection costs and a minimized total inspection time. The cost of traversing $H_1$ is equal to 20, while the cost of traversing $H_2$ is 22, showing an improvement from the example above.

4.4. Fixed Start Formulation

Intuitively, by leaving UAVs’ starting and ending positions unconstrained, we expect to obtain the fastest inspection paths as the solution is determined by the solver. However, considering that it would surely take longer for the solver to determine it and that it could take a substantial amount of time to physically bring UAVs to different starting positions depending on the size of the inspection area, we decided to experiment with fixing the starting positions. If we assume that inspections will be conducted regularly for maintenance purposes, it could seem impractical to bring and collect UAVs from different locations. Alternatively, UAVs could be sent from the same location for the first time they engage in the inspection, and each successive time they could start where they previously ended while charging in the meantime. Similarly, assuming that starting from the same location would increase the inspection time more than it would take to transport UAVs, they could be brought to different locations the first time they are engaged in inspection, but each successive time the starting position could be fixed to where they previously ended. All the above-mentioned trade-offs would highly depend on the specific situation and technology available at the time of inspection. Therefore, we decided to investigate the impact that fixing the starting locations would have on the total inspection time as well as the execution time when using our constraint model.

5. Methodology

To solve the problems formulated in the previous section, we model them by defining a set of user-defined variables, decision variables, constraints on those variables, and optimization criteria. In the following subsections, we present the models in mathematical notation, matching the syntax of the open-source modeling language MiniZinc, which was used for their implementation. The greatest advantage offered by such a tool is the ability to describe the model on a high level, independent of a specific solver. Another benefit is the wide range of predefined constraints and data types that can be used to create new models.

5.1. Eulerian Trail Model

As we previously concluded that edge-disjoint decomposition would be infeasible for some graphs, we begin by modeling the problem formulation where the Eulerian trail is guaranteed, i.e., UAVs are allowed to reuse edges. In

Table 1. User-defined variables.

Input	Description
k	number of UAVs involved in inspection
D	array of integers representing each UAV from 1 to k
d	an element of D
E	array of all possible directions a UAV can take on each edge
e, $e^{\prime }$	an element of E
$rev$	array of reversed directions for each direction in E
$cost$	array of inspection costs for each direction in E
$makespan$	maximum theoretical inspection cost for a UAV, defined as a sum of costs in $cost$
$succ$	array of possible successors for each direction in E
$traverse[D,E]$	matrix of costs for UAVs taking each direction in E
$E_{end}$	array of all possible actions for UAVs to take; including all directions from E as well as $end$, signifying the end of the route

, we present user-defined variables necessary to model the problem. A user directly defines the following variables: k, E, $rev$, $cost$, and $succ$, while others are derived from those. By defining variables E, $rev$, $cost$, and $succ$, we describe a graph that would be solved. Variable E is declared as an enumerated type, a declaration allowed by the constraint programming language that allows us to define n elements that are named but act similarly as integers $1\dots n$ to make the model easier to understand and debug. Therefore, other arrays in the model can be associated with the enumerated type, e.g., each element in the array $cost$ is associated with elements in the enumerated type E in the order of placement. As E contains all possible actions for UAVs to take except the one that would signify the end of the traversal, we create another enumerated type $E_{end}$ by extending E with the constructor $end$. Enumerated type E is injected into the new type $E_{end}$ via a constructor function $R\left(E\right)$, which is also used when defining constraints to map values from the extended type $E_{end}$ into the base type E. For clarity, we use the same notation for the constructor function when presenting our constraint model. In

Table 2. Decision variables.

Output	Description
$next[D,E_{end}]$	matrix of actions taken after each option from $E_{end}$, for each UAV in D
$visit[D,E_{end}]$	matrix of accumulated costs for traversals identified in $next$, for each UAV in D
$scan[D,E]$	matrix of Boolean values marking directions from E as inspected or not inspected, for each UAV in D
$endcost$	optimization variable representing a total cost of inspection

, we define the decision variables, which are determined by the solver according to the defined constraints. Elements in matrix $visit[D,E_{end}]$, as well as variable $endcost$, are intuitively only allowed to hold values in the range from 0 to $makespan$.

The constraints are modeled as follows:

The next action that a UAV takes after taking each action from $E_{end}$ can either be in the direction of a successor (or the same direction if the UAV did not traverse there) or it signifies the end of the inspection.

$${\forall }_{d\in D,e\in E}next[d,R\left(e\right)]\in \{R\left(e^{\prime }\right)\mid e^{\prime }\in succ\left[e\right]\}\cup \{R\left(e\right),end\}$$

(1)

Intuitively, as there is no next action after reaching the end, we set the $end$ value to be the direction from where a UAV starts, as all other directions in the $next[D,E_{end}]$ will either hold information about its successor or signify that a UAV did not traverse there.

$${\forall }_{d\in D}next[d,end]\in R\left(E\right)$$

(2)

As we manually added $end$ into $E_{end}$ to represent the beginning or end of the traversal, it does not accumulate any cost. We set the cost of “traversing” from the end to the beginning to zero.

$${\forall }_{d\in D}visit[d,next[d,end]]=0$$

(3)

We want to avoid each UAV traversing in the same direction multiple times. Therefore, we specify that actions in $next[D,E_{end}]$ for each UAV in D are all different. We employ a predefined constraint $\mathtt{all}\_\mathtt{different}$, which is offered by most high-level constraint modeling tools.

$${\forall }_{d\in D}\mathtt{all}\_\mathtt{different}\left(next[d,E_{end}]\right)$$

(4)

As we are using only one variable to optimize the problem (the maximum of all solutions), there could be some unnecessary UAV actions in the solutions that are not involved in the optimization objective. Therefore, we define this constraint to prevent UAVs from unnecessarily taking a direction only to come back in the opposite direction to conduct the inspection. This constraint would not prevent other possible unnecessary actions, such as traversing without inspecting and finishing the inspection right afterward. Resolving that issue would require the addition of a second objective of optimization to our problem formulation, which would increase the complexity of the problem.

$${\forall }_{d\in De\in E}scan[d,e]\vee next[d,R\left(e\right)]\ne R\left(rev\left[e\right]\right)$$

(5)

Every edge needs to be inspected in exactly one direction.

$${\forall }_{e\in E}{\exists }_{d\in D}scan[d,e]\vee scan[d,rev\left[e\right]]$$

(6)

$${\forall }_{d\in D,e\in E}\neg (scan[d,e]\wedge scan[d,rev\left[e\right]])$$

(7)

If the edge is inspected in a specific direction, it means that the action has been taken (a UAV moved from the direction in $E_{end}$ to the direction of its successor).

$${\forall }_{d\in D,e\in E}scan[d,e]\Rightarrow next[d,R\left(e\right)]\ne R\left(e\right)$$

(8)

If the next direction is the same as the previous one, it means that the UAV did not traverse there, and without loss of generality, we can set the visiting cost to 0.

$${\forall }_{d\in D,e\in E}next[d,R\left(e\right)]=R\left(e\right)\Rightarrow visit[d,R\left(e\right)]=0$$

(9)

If the next direction is different from the previous one, it means that the UAV traversed there and the visiting cost should be increased according to the inspection cost for the associated direction in $traverse$.

$$\begin{array}{cc}\hfill {\forall }_{d\in D,e\in E}& next[d,R(e\left)\right]\ne R\left(e\right)\Rightarrow \hfill \\ & visit[d,next[d,R\left(e\right)\left]\right]=\hfill \\ & visit[d,R(e\left)\right]+traverse[d,e]\hfill \end{array}$$

(10)

We define the optimization variable as the maximum of all accumulated inspection costs for each UAV.

$$endcost=\mathtt{max}(visit[d_1,end],\dots ,visit[d_n,end])$$

(11)

We solve the optimization problem by minimizing the $endcost$.

$$\mathtt{minimize}endcost$$

(12)

As previously mentioned, the solver does not optimize the accumulated costs for other UAVs, which are not the maximum, and that may cause unnecessary traversals. To optimize other resulting costs as well, a second optimization objective could be defined as the sum of all resulting costs. To emphasize the desired order of optimization, the first objective $endcost$ would be scaled by a value at least as much as the maximum of the second objective. However, adding another optimization objective could increase the computation time. Therefore, we implement the constraint (5) to eliminate some unnecessary actions and accept the risk of others in favor of faster computation.

5.2. Multi-Weight Model

In this subsection, we modify the previous model in order to differentiate between the costs of deadheading and inspection flights. Newly defined as well as re-defined variables are presented and described in

Table 3. Newly defined and re-defined variables.

Input	Description
$cost$	array of deadheading costs for each direction in E
$multiply$	penalizing factor for increasing the cost of inspection flight
$makespan$	maximum theoretical total cost for a UAV, defined as a sum of inspection costs in one direction and deadheading costs in reversed direction
$traverse[D,E]$	matrix of costs for UAVs taking a direction depending on the traversal type (inspect/deadhead)

. The most significant difference in this model is that $traverse[D,E]$ is defined as a decision variable because it depends on the traversal type (inspect/deadhead) decided in $scan[D,E]$. If an edge is inspected, the cost of deadheading from $cost$ is penalized by the value $multiply$ otherwise, the cost is equal to the cost of deadheading from $cost$. Mathematically, each element in the matrix $traverse$ is defined as $scan[d,e]\ast (multiply-1)\ast cost\left[e\right]+cost\left[e\right]$, for each d from D and e from E. All constraints are modeled equally, as described in the previous subsection.

5.3. Fixed Start Model

To restrict the starting direction, additional constraints must be created. Depending on the desired choice, we may fix all available UAVs to the same start using the constraint (13) or they may start from different fixed positions enabled by the constraint (14) which must be specified for each UAV individually. UAVs as well as starting directions are chosen by accessing elements in arrays D and E positioned on the desired $index$ value.

$${\forall }_{d\in D}next[d,end]=R\left(E\left[index\right]\right)$$

(13)

$$next\left[D\right[index],end]=R\left(E\right[index\left]\right)$$

(14)

6. Experimental Evaluation

In order to evaluate our approach and determine the model’s suitability for the use case of coverage path planning for continuous autonomous UAV infrastructure inspection, we perform experiments on different graphs and with different numbers of vehicles k, comparing solutions of multiple previously presented model variants. We describe the experimental setup, evaluate the solutions, and discuss the advantages and disadvantages of selecting each model variant when planning the inspection missions.

We define eight graph instances $G1$-$G8$ inspired by the portions of a real transmission network graph shown in Figure 1 that was used in our previous work, and we use these instances for experimental evaluation. Instances are built to resemble linear power infrastructure, where nodes represent power towers containing geographical locations that are used to transfer flight instructions to UAVs after the algorithm determines optimal paths. Edges are representations of power lines, and costs represent their length, i.e., the distance between the power towers. As previously mentioned, such a graph can be built using infrastructure data available from the Open Street Maps, as presented in our previous work [59]. We ensured the inclusion of differently shaped graphs, encompassing cycle graphs, graphs representing trees, and a fusion of both aforementioned types. This choice stems from our presumption that, for continuous inspection, smaller segments of the complete transmission network graph would be selected, resembling one of these combinations. As the constraint modeling language is solver-independent, it allows us to test different third-party solvers and configurations to determine the most appropriate setup for our model.

Table 4. Computational performance of different solvers solving the graph $G1$ using the multi-weight constraint model.

Solver	Time [s]
	Solution	Execution
Gurobi	2.93	3.41
Gecode	0.39	0.62
Chuffed	0.42	0.53
OR-Tools	0.39	0.48

shows performance results for solving graph $G1$ depicted in Figure 4 using different solvers. As we are solving an optimization problem, the solver iterates through the options that satisfy given constraints based on the underlying algorithms and intents to find an optimal one. Every solution that is better than the previous one becomes the current solution until an even better one is found. The time until the optimal solution is found is what we refer to as the solution time. A runtime is the time until the program iterates through all options and finishes executing, which we refer to as an execution time. We proceeded to experiment using the OR-Tools CP-SAT solver, which is a state-of-the-art solver in constraint programming, and it outperformed other solvers in our computational performance experiment. We have to consider that computational performance is also affected by other aspects of the experiment, such as the graph complexity, the number of vehicles, the model itself, and the device running it. Computations are performed on a computer with an i9 2.9 GHz processor and 32 GB of RAM. All models are run on seven threads, which is an option available for the OR-Tools solver that uses different search strategies in parallel to speed up computations. As the MM K-CPP problem is known to be NP-hard and cannot be solved in polynomial time, the objective is to determine the suitability of our model for coverage path planning for autonomous UAV linear infrastructure inspection by identifying graphs that can be solved in a reasonable time and discussing trade-offs between the optimality of the results produced by different model variants and their computational times.

6.1. Eulerian Trail Model Simulation

We test the model for different graph types and sizes for single-objective optimization $endtime$ as well as for multi-objective optimization, as described in the previous section. The resulting paths for two-vehicle inspection are shown in Figure 5 and for four-vehicle inspection in Figure 6. For two-vehicle inspection, the final solutions are mostly balanced, meaning that each UAV covers an approximately equal portion of a graph. In the case of graphs $G4$ and $G7$, the property of deadheading was not engaged, as the optimal solutions were found without reusing edges. For four-vehicle inspection, the solutions are less balanced. For example, in graph $G7$, the difference in costs between the fastest and slowest vehicles is equal to 14. An interesting anomaly can be observed in graph $G8$ where UAV4 unnecessarily deadheads the edge between nodes 2 and 5 right before it finishes conducting the inspection. Such an anomaly is possible when the solver finds this solution before it finds the solution without unnecessary deadheading and when a certain UAV path is not the objective of the optimization.

Table 5. Computation times and resulting costs for each vehicle involved in the inspection obtained through simulation of the Eulerian trail constraint model for both single-objective as well as multi-objective optimization. Two vehicles D1 and D2 conduct the inspection. Corresponding graphs and path solutions are shown in Figure 5.

Graph	Single-Objective Optimization				Multi-Objective Optimization
	Time [s]		Cost		Time [s]		Cost
	Solution	Execution	D1	D2	Solution	Execution	D1	D2
$G1$	0.35	0.36	24	20	0.35	0.38	24	16
$G2$	0.46	2.12	58	56	0.63	2.38	56	58
$G3$	0.39	1.89	88	82	0.59	2.48	88	80
$G4$	0.53	8.47	60	60	0.87	122.00	60	60
$G5$	0.64	6.77	62	64	1.27	47.41	64	60

and

Table 6. Computation times and resulting costs for each vehicle involved in the inspection obtained through simulation of the Eulerian train constraint model for both single-objective as well as multi-objective optimization. Four vehicles, D1, D2, D3, and D4, conduct the inspection. Corresponding graphs and path solutions are shown in Figure 6. S and E represent solution and execution time, respectively.

Graph	Single-Objective Optimization						Multi-Objective Optimization
	Time [s]		Cost				Time [s]		Cost
	S	E	D1	D2	D3	D4	S	E	D1	D2	D3	D4
$G6$	4.23	56.12	34	42	40	38	3.58	1215.00	34	34	42	42
$G7$	2.66	32.52	40	34	38	26	9.40	33.92	34	26	38	40
$G8$	1.36	11.34	28	26	28	22	16.86	146.00	20	28	26	28

present computational results for both single-objective and multi-objective optimization, and it can be seen that this issue is eliminated by applying multi-objective optimization in Table 6, where the lowest cost of 22 is reduced to 20. The presented results confirm our hypothesis that multi-objective optimization eliminates the risk of unnecessary actions taken by vehicles that do not traverse paths with maximum cost but increases the computational time. As can be seen, the minimum of all costs for both vehicles is lower for graphs $G1$, $G3$, and $G5$ when multi-objective optimization is applied. Nonetheless, the improvement is not substantial and sometimes not even necessary, as in the case of graphs $G2$ and $G4$. Although the time to find a solution is not substantially increased, the total execution time is highly impacted. Therefore, we proceeded with testing without multi-objective optimization and with the same graphs we tested the Eulerian trail constraint model. Optimal solutions for all graphs are reached quickly, for graphs with two-vehicle inspection in under 2 s and for four-vehicle inspection in under 5 s. We can guarantee that the solutions found are optimal because the simulation execution reached its end for each instance, meaning that all possible options are tested. However, our experiments showed that solution time can vary if executed multiple times. Such variations, although in most cases not significant, are caused by the solving process of an underlying solver, in this case, OR-Tools CP-SAT. Moreover, the solution time depends on the arrangement of constraints as the solver searches for the solution by eliminating unsatisfying options.

For purposes of continuous autonomous UAV infrastructure inspection, this solution proves suitable, as the optimal results for graph instances resembling a transmission network could be obtained quickly. The main trade-off to discuss is whether to apply multi-objective optimization and attempt to find the lowest cost for each UAV or to focus solely on the maximum cost. As previously mentioned, the choice of the optimization objective will not impact the resulting total inspection time. However, it can potentially decrease the total distance traversed by sacrificing fast execution time. Note that for multi-objective optimization, the time when the optimal solution was found is quick, with the maximum time being 16.86 s for graph $G8$. This suggests that a time limit could be applied, guaranteeing that the execution time will not exceed the specified time limit. However, by applying a time limit, we can only assume that the final solution is optimal, as optimality, in that case, cannot be guaranteed. It is up to the mission operator to choose the most suitable approach depending on the mission objectives. In this work, we focus on minimizing the total inspection time.

6.2. Multi-Weight Model Simulations

We conduct experiments using the same graphs as previously, with the difference being in the deadheading flights. When an edge is traversed without inspection, the cost is reduced two times compared to when the inspection is conducted. As UAVs conduct the inspection, they have to cover structures in detail using sensors, which prolongs the inspection flight. When deadheading, the inspection is not necessary, and UAVs can fly at maximum speed. We take that into account in an attempt to lower the total inspection time. The resulting paths for two-vehicle inspection are shown in Figure 7 and for four-vehicle inspection in Figure 8. The solutions are similar to the Eulerian model simulation but slightly improved regarding the total inspection time. A similar anomaly as in the experiment with Eulerian trail model simulation can be observed on graph $G8$ where an UAV deadheads two edges before finalizing its inspection, substantially and unnecessarily adding to its cost. Applying multi-objective optimization would further increase execution time, but it would resolve the issue.

Table 7. Computation times and resulting costs for each vehicle involved in the inspection obtained through simulation of the multi-weight constraint model. Two vehicles D1 and D2 conduct the inspection. Corresponding graphs and path solutions are shown in Figure 7.

Graph	Time [s]		Cost
	Solution	Execution	D1	D2
$G1$	0.39	0.48	20	22
$G2$	0.81	26.76	56	56
$G3$	1.51	9.61	77	72
$G4$	49.45	754.77	60	60
$G5$	1.40	375.00	60	58

and

Table 8. Computation times and resulting costs for each vehicle involved in the inspection obtained through simulation of the multi-weight constraint model. Four vehicles, D1, D2, D3, and D4, conduct the inspection. Corresponding graphs and path solutions are shown in Figure 8.

Graph	Time [s]		Cost
	Solution	Execution	D1	D2	D3	D4
$G6$	10.26	81.00	40	40	40	41
$G7$	8.77	296.00	40	40	40	39
$G8$	16.26	36.99	28	27	26	28

present computational results. Compared to the Eulerian trail model, the total cost, defined as the maximum cost of all UAV costs, decreased in five out of eight cases, with graph $G3$ demonstrating the highest improvement in the decrease in total cost from 88 to 77. However, computational time substantially increased, raising a discussion about the suitability of the multi-weight model. As global inspection path planning is not conducted in real-time but precedes the inspection, we can argue that it is more important to have shorter inspections than it is to obtain the calculations quickly. As previously observed for Eulerian trail model simulation, the optimal solutions in this case are also reached relatively quickly, with the longest being 50 s for graph $G4$. This insinuates that applying a limit to the execution time would shorten the execution time without impacting the results. We tested this hypothesis by setting up an experiment to compare solutions for the Eulerian trail model and multi-weight model simulations for two-vehicle inspection on graph instances $G6$, $G7$, and $G8$. The results are presented in

Table 9. Comparison of computation times and resulting costs obtained through simulations of the Eulerian trail model and multi-weight model for two vehicles D1 and D2 involved in the inspection. Variable $timelimit$ is set to 300 s.

Graph	Eulerian Trail				Multi-Weight
	Time [s]		Cost		Time [s]		Cost
	Solution	Execution	D1	D2	Solution	Execution	D1	D2
$G6$	15.56	47.54	76	78	149.00	$timelimit$	77	77
$G7$	1.20	25.49	80	80	13.58	240.00	73	72
$G8$	1.41	14.22	52	52	2.32	$timelimit$	52	50

. By applying a short time limit of 300 s, we were able to obtain either equally good or better results. For graph $G7$, we obtained the optimal solution, which is a significant improvement when compared to the result of the Eulerian trail simulation. In cases where the time limit is applied, we cannot guarantee that the solutions are optimal, as the entire search space is not explored. However, as long as the obtained results are equal to or better compared to the results obtained with the Eulerian trail model, applying the time limit is a valid technique for reducing the execution time. Another argument in favor of the multi-weight model is that the impact of multi-weight edges is demonstrated when the costs of edges are higher, as the time saved by deadheading those edges is higher as well. Graphs created using the locations and distances of real linear infrastructure would involve many kilometers of traversal, meaning that edge weights would be higher than in our approximated graphs. Even a one-point increase in total cost could signify multiple kilometers of traversal, depending on the scale of the cost approximation, and consequently significantly higher total inspection time.

Comparing results of two-vehicle inspection shown in Table 9 with results presented in Table 6 and Table 8 where the number of vehicles is increased to four, we observe a significant increase in total inspection cost as expected. Inspired by the observations of execution times, we further investigate how the increase in the number of vehicles relates to not only a reduction in total inspection costs, but also to computation times. We simulate a multi-weight model for graphs $G1$–$G5$ with different numbers of vehicles and present solutions in

Table 10. Computation times for graphs $G1$–$G5$ with respect to the number of UAVs employed for inspection.

Graph	Vehicles	Time [s]		Total Cost
		Solution	Execution
	2	0.39	0.48	22
G1	3	0.45	0.53	16
	4	0.48	0.62	14
	2	0.81	26.76	56
G2	3	3.85	17.46	38
	4	4.37	13.47	32
	2	1.51	9.61	77
G3	3	1.21	7.33	49
	4	1.11	5.56	36
	2	49.45	754.77	60
G4	3	8.23	674.58	40
	4	5.54	151.99	30
	2	1.40	375.00	60
G5	3	3.45	81.00	40
	4	9.76	40.30	30

. Regarding the total inspection cost, we can observe that employing twice as many vehicles approximately reduces the inspection time in half. Intuitively, adding more vehicles for the inspection will have the most impact on reducing the total inspection time. According to this experiment, the computational performance is also improved when more vehicles are chosen. In most cases, except for the simple $G1$ graph, the execution time decreases and optimal solutions are obtained quicker as the number of vehicles increases. The same could not be concluded for the time when the final solution is found, as there are no straightforward patterns observed.

6.3. Fixed Start Model Simulations

We conducted experiments with the multi-weight constraint model and fixed positions at the start of the inspection. Assuming that it will not always be possible to carry UAVs to the positions determined by the algorithm due to inaccessible terrain, we experiment with fixing starting positions. We propose two different scenarios depending on whether UAVs are released at the same location or start from different locations. In the first scenario, we fixed all the UAVs to the first element in the array E. In the second scenario, we fixed each UAV’s starting position to the position where it ended when conducting the experiment from the first scenario. As seen in

Table 11. Computation times for graph $G5$ with all starting positions fixed to the first element in E.

Vehicles	Time [s]		Total Cost
	Solution	Execution
2	1.53	3.97	67
3	3.93	5.25	50
4	3.59	3.91	41

and

Table 12. Computation times for graph $G5$ with starting positions fixed to different elements from E.

Vehicles	Time [s]		Total Cost
	Solution	Execution
2	1.14	3.84	67
3	1.49	2.59	47
4	2.57	2.65	38

, computations were performed quickly, especially when compared to the scenario with unrestricted beginnings. However, the total inspection cost has significantly increased. When deciding which locations to choose as starting positions, it would be very difficult to guess the exact locations that would guarantee the lowest total inspection cost. Depending on the shape of the graph, we can attempt to choose locations that would obtain a lower total cost with a higher probability. In graph $G5$, by establishing node 1 as the initial location, all UAVs would have to traverse a few common edges, which would have an impact on the total cost. As seen from Table 12, by randomly choosing different starting positions for each UAV, the total cost can be lowered, especially for a higher number of UAVs. However, this approach is not the rule and highly depends on graph shape and dedicated costs. To evaluate if this solution is overall preferable over the one with an unrestricted beginning, one would need to know if it is more efficient to manually take the UAVs to the position determined in the unrestricted scenario or to let UAVs fly the additional time proportional to an increase in total cost. Our assumption is that it would be more efficient to take UAVs to any position determined by the solver if it decreased the total time of inspection for multiple reasons. As we previously mentioned, even a slight increase in the total cost may result in a significant increase in time. Furthermore, the more UAVs fly, the more they are required to charge, which would additionally increase total inspection time. Last but not least, more flight time during the prolonged period would signify more maintenance work on sophisticated UAV technology, which would in the long term increase the financial costs of autonomous inspection. For continuous inspection for maintenance purposes, the best approach would be to run the algorithm with unrestricted positions for the first time and bring UAVs to the determined starting locations manually. When UAVs are finished inspecting, they can stay idle or charge while they wait to receive the next flight instructions. We can take their finishing locations as starting locations for the next round of maintenance inspection. The algorithm would determine paths with the same optimal total cost but with lower execution time as the problem with fixed locations is less general.

7. Conclusions

In this article, we present a solution to the global coverage path planning problem for linear infrastructure inspection using multiple UAVs. The objective was to achieve the fastest inspection by decomposing the inspection path into segments such that each UAV covers one segment and that it is accomplished in minimal total time. We formulated the problem as a variant of MM K-CPP, conceptually investigated the suitability of multiple problem variants, and implemented constraint models. Initially, we tested the model that solves MM K-CPP with the variation in starting positions. The original MM K-CPP attempts to find K closed walks, meaning that each UAV would have to start and end at the same fixed depot. In our case, the depots are unrestricted as we aim to achieve the quickest possible inspection for available graph instances. The model performed quickly and obtained good solutions. As our optimization objective was to minimize the highest cost, we noted that routes with lower costs can involve unnecessary traversals, and we proposed a multi-objective optimization approach to resolve this issue. However, we proceeded with single-objective optimization, as involving multiple optimization objectives is not always necessary and does not impact the total inspection cost but increases the computation time. To further minimize the inspection time, we proposed a multi-weight model where edges have different costs depending on the type of flight that UAVs are conducting. When an edge is serviced, the flight cost is higher as we assume that the UAV’s speed is lower and it takes longer to traverse it. On the other side, if an edge has already been serviced, an UAV can traverse it with maximum speed, which would make the cost of traversal lower. We successfully lowered the total inspection time compared to the previous formulation, but at the cost of higher computation time. A valid approach to decreasing the execution time was to introduce a time limit. Most of the optimal solutions were found in a short time, under 1 minute. We applied the time limit of 5 minutes and obtained better or equal results compared to the unrestricted MM K-CPP formulation. Intuitively, increasing the number of UAVs had the most impact on lowering the total inspection time. We noticed that, for our graph instances, increasing the number of UAVs also lowered the execution time. For continuous linear infrastructure inspection, we assume UAVs would be constantly operating. Therefore, it is important to conduct inspections quickly, as UAVs could be available to continue inspecting quicker. We proposed an approach for the fastest continuous inspection with the quickest computations by experimenting with fixed starting positions. Fixing the starting depot makes the problem less general and lowers the computation time. However, fixing starts to random positions would most probably not lead to the fastest inspection. Therefore, we proposed to employ an unrestricted approach that will produce optimal paths, after which the finishing depots can be used as starting depots for continuing the inspection.

We modeled all problem variants using the constraint programming language, which is solver-independent. Experiments confirmed that the OR-Tools solver outperformed other solvers. Therefore, we proceeded with it in all experiments. Although the computation time to some extent depended on the number of vertices and edges, what was shown to be a substantially more significant factor was the shape of the graph. Vertices with higher degrees provide more different combinations that the solver needs to search through in order to evaluate the solutions. As expected, the execution time for graphs with vertices of higher degrees was longer. However, if the graph complexity is further increased, the execution time will increase exponentially, as we know that this problem is NP-hard. Even in these cases, the solver is able to find valid solutions in a reasonable time, but as the execution would not be finalized, we cannot guarantee the optimality of the results. One of the limitations of exact solutions is that they do not scale when the test instances are enlarged and more complex. In order to overcome that, a heuristic solution could be developed. That would enable the calculation of near-optimal inspection paths for the whole transmission network in a country or even larger. Another limitation of our approach is that we assume all positions in a graph are good candidates for starting positions at the initialization of the continuous inspection. Although Denmark is a rather flat country and it would be possible to bring UAVs anywhere, that is not the case for some other countries where the transmission network crosses terrain that is not easily available. To overcome that limitation, we would have to develop an approach to evaluating which nodes should be excluded as starting positions. To fully enable BVLOS continuous inspections, there are certain challenges that need to be tackled, such as UAV resistance to harsh weather conditions (e.g., wind, rain, etc.), the establishment of technologies for uninterrupted connection over long distances between UAVs and ground stations or cloud systems, the maturity of charging technologies, the development of regulations regarding such operations, and the commercialization of complete solutions for large-scale autonomous UAV operations.

A future improvement would focus on attempts to speed up computations by trying out different solving approaches, such as the development of mixed integer programming (MIP) solutions, the development of heuristics models or adaptation of existing heuristics to our specific problem, as well as the development of a neural network solution, as it could potentially resolve the problem of exponential run time depending on the graph complexity. Future work also involves the integration of the obtained solution into our previously developed cloud system for mission planning presented in Section 3 in the attempt to develop a complete cloud system for planning autonomous UAV inspections.