Efficient unmanned aerial vehicle paths design for post‐disaster damage assessment of overhead transmission lines

Abstract

The widespread distribution of overhead transmission lines increases the vulnerability of power grids to failures. Thus, power lines need to be timely inspected, especially before or during emergency‐related situations to ensure stable operation of the power grid. Traditional methods of visual inspection (satellites and helicopters) are inconvenient, often cannot be deployed and if they are deployed present a slow response time and high cost, which is very critical for fast post‐disaster damage identification. On the other hand, employing an unmanned aerial vehicle (UAV) offers a more efficient, reliable, and faster means for the assessment process. This article proposes a novel approach for the post‐disaster UAV‐based damage assessment of overhead power lines. In the proposed approach, the UAVs paths over the most critical loads are formulated as an optimisation problem with the objective of minimising the total inspection time while considering the recharging of the UAVs' batteries. To solve the problem, an efficient framework that optimises the UAVs flight paths is proposed to inspect the critical loads in an efficient order, while accounting for the UAV recharging. This guarantees that the UAVs complete the assessment tasks unlike existing benchmarks.

INTRODUCTION AND MOTIVATION

Transmitting power over large distances via long overhead transmission lines increases the power grid vulnerability to failures. These lines can be perturbed by natural disasters (e.g. hurricanes, tornadoes, earthquakes), weather conditions (e.g. lightning strikes, snowstorms, wind/rain), and other damaging sources (bird nests and droppings) [1]. These eventually lead to partial or complete blackouts, resulting in huge economic losses. An analysis conducted by Hines et al. ([2], Table 2) over 933 event outages from 1984 to 2006 in the United States found that more than 49% of the events were caused by natural disasters with a huge impact on many customers.

To ensure reliable operation of the power grid, the overhead transmission lines need to be constantly inspected and tested for maintenance. Onsite testing can include the usage of (i) punctured insulator detectors which identify punctures in wires insulation for potential electricity leakage; (ii) distributed temperature sensors which monitor the condition of the insulations and the cable capacity; and (iii) capacitive coupling sensors which detect discharge signals [3].

In failure scenarios related to short circuit faults (three phase faults, line-to-ground, line-to-line etc.), faulty lines are usually diagnosed and disconnected by protective devices, such as distance relays, supervisory control, and data acquisition (SCADA) systems etc. However, in the case of multiple failures as in the case of natural disasters, especially those related to open circuit faults, these devices become useless. Moreover, while metering equipment can be useful to monitor the power grid state via three phase voltages, flowing currents, and active and reactive powers, they are considered inadequate in detecting faults in overhead transmission lines. This is because natural disasters can de-energise parts of the power grid by bringing down some power stations, resulting in zero current readings at the corresponding power lines. Therefore, even though some transmission lines are healthy, they cannot be detected as such when monitored by metering equipment. For these reasons, visual inspection of the lines is required. However, during times of natural disasters, fast and efficient visual inspection of lines for fault identification is of paramount importance to reduce electricity disruptions and losses. Traditional ways include visual inspection by an on-ground operational staff [4] or by a helicopter [5, 6]. Besides being inconvenient and having a slow response, sending an onground crew to damaged areas can be dangerous (road conditions, car accidents, night visibility etc.). Moreover, some locations can be remote and difficult to access. As for the helicopter-aided inspection, several problems can arise besides costs such as the collected data may be sparse and/or inadequately recorded due to the residual sightline motion and instability, as well as the limited time for target inspection (around 10 s) [5, 6].

A promising solution to inspect the overhead transmission lines is the use of unmanned aerial vehicles (UAVs). In fact, several utility companies have adopted UAVs for a variety of applications. For example, the American utility company, Duke Energy, has started employing UAVs since 2015 to assess the damage and inspect power lines, solar panels, and wind turbines following natural disasters such as Hurricane Maria in Puerto Rico in 2017, where the company helped restring the damaged transmission lines [7]. Before the UAV is flown, a team sets the flight path using GPS plot points [8]. UAVs offer multiple advantages over traditional methods:

• UAVs are low-cost, environmentally friendly (use batteries), and less intrusive than helicopters (noise-free operation) [9].

• UAVs are equipped with advanced imaging technology that captures real-time high-definition large-scale footage of power lines in a short time [9, 10]. The spatial resolution of images ranges from a few cm per pixel for UAVs to 20–50 cm per pixel for satellites [11].

• UAVs reduce the outage time by offering an extensive identification of the components that need to be repaired or replaced [10].

• UAVs offer inspection efficiency by flying to hard-to-reach locations [10].

In this paper, we aim to optimise the multi-UAVs flying paths to inspect all critical loads after some disaster in the shortest possible time. Unlike the approach adopted by Duke Energy, the framework we are proposing is fully automated and provides the UAVs with efficient flying paths to inspect the most critical loads in the system first. This in turn minimises the time needed to identify faulty lines.

Related work

UAVs find usage in a myriad of applications in power grids; however, for the scope of this paper, we discuss the related works that optimised the UAVs' flying paths.

For fast response and autonomous monitoring of power substations, the authors in ref. [12] proposed a UAV inspection system, where reliable and efficient navigation paths were obtained using deep Q-learning and edge computing techniques. In ref. [13], the authors optimised the UAV route for the detection of transmission lines by using the filtering method of the sphere unit limit and Beidou precision positioning service. The sequential UAV inspection path was optimised in ref. [14] using a segmented 3D map and sampling-based sequential optimisation under sensor, efficiency, and safety constraints. Autonomous power lines tracking and inspection by a UAV (quadrotor helicopter) was simulated in a real environment in ref. [15] using classic proportional–integral–derivative (PID) controllers. A power line inspection system using a combination of a ground vehicle and a UAV was investigated in ref. [16]. The routes of the vehicle and the UAV were jointly optimised along the power line network using the Travelling Salesman problem and the arc routing problem. In ref. [17], the authors proposed a cooperative human-UAV fault inspection for transmission networks to efficiently restore the damaged power grid. Using the cooperative evolutionary algorithm, both the human and UAV scheduling solutions were jointly optimised. In ref. [18], a multi-UAV power grid damage assessment was investigated using a two-stage solution. In the first stage, the locations of UAVs were optimised when extreme weather is anticipated, and in the second stage, the UAVs were re-positioned with the arrival of the predicted weather, and the UAVs paths were optimised to minimise operation costs and inspection time. In ref. [19], power grid inspection paths for tower monitoring and line corridor monitoring were obtained using genetic algorithm and genetic simulated annealing.

A UAV path planning method for post-disaster emergency response was proposed in ref. [20], which considers waypoint planning to improve the reliability of uplink and downlink data transmission, as well as motion planning which enables the UAV to traverse all waypoints faster. A deep-reinforcement three-dimensional UAV path planning method was proposed in ref. [21] based on local information and relative distance, where the problem was formulated as a partially observable Markov decision process. In ref. [22], a UAV flight path solution based on an improved bat algorithm showed a faster convergence with shorter, safer, and collisions-free paths than standard bat algorithm due to the improved local search. Energy-efficient multi-UAVs trajectory planning problem was formulated as two-coupled stochastic games (flight planning and recharging scheduling) in ref. [23], where the objective was to minimise paths length under quality-of service constraints. In ref. [24], the authors used mixed-integer non-linear programming model to minimise the inspection path length of UAVs for oil and gas pipeline networks. An energy efficient path planning algorithm for UAVs was proposed in ref. [25], which minimises energy and inspection time by accounting for the energy consumption during flying, hovering, and data transmission.

Energy-aware path planning for UAVs was solved in ref. [26] by partitioning the flying area into multiple sub-areas depending on the number of UAVs employed, and by accounting for the non-flying zones. UAV path planning problem was formulated as a Travelling Salesman problem in ref. [27], where the objective was to minimise the energy consumption to complete a mission by minimising the number of turns. The solutions of UAV path planning in the presence of obstacles for pre-disaster assessment were compared in ref. [28] using different metaheuristic algorithms. A UAV planning was proposed in ref. [29] based on a combination of sparrow search algorithm and particle swarm algorithm, which improved the path search efficiency as well as the path smoothness by reducing the turning points. Multilevel constraints evolutionary algorithm was used in ref. [30] to obtain the UAV shortest collision-free paths in a three-dimensional terrain. In ref. [31], the authors solved the trajectory planning for multi-UAVs for military applications using coordinated evolutionary algorithms.

In ref. [32], the authors addressed the challenge of autonomous UAV navigation in complex environments using a deep reinforcement learning algorithm that awards UAV only upon completing the navigation tasks. In ref. [33], the authors introduced a solution for the resource allocation problem in UAV networks, considering the interference caused by space-air-ground heterogeneous networks. In ref. [34], the authors developed a power line extraction algorithm to address the along-line inspection problem in UAV power inspection. A method for intelligent inspection of overhead power lines using LTE was proposed in ref. [35]. In ref. [36], the authors addressed the challenges of route declaration and identification of no-fly zones for transmission line patrol inspection in the power industry. A federated learning approach was introduced in [37] to detect insulators in power line inspection images captured by UAVs. In ref. [38], the authors proposed an integrated drone system for autonomous power line inspection, which utilises energy harvesting for operation time extension, artificial intelligence for fault detection, and navigational algorithms for system autonomy. In ref. [39], the authors presented an approach for automatically generating efficient trajectories for a swarm of UAVs with the objective of ensuring that the necessary data points were visited while satisfying resilience, data freshness, fuel usage, and coverage requirements. In ref. [40], the authors introduced a framework to verify if a given set of UAVs can effectively conduct continuous surveillance of the critical transmission lines, meeting resilience requirements with refuelling schedules. However, unlike our work, they did not minimise the total inspection time.

In ref. [41], the authors solved the 3D military path planning for UAVs using evolutionary algorithms. In ref. [42], the authors proposed an autonomous inspection of power pylons by allowing UAVs to utilise the geo-location data by the cloud services to define their flying path. In ref. [43], the authors proposed a solution to improve the efficiency of UAVs-based inspection, while reducing the inspection time and energy consumption by moving the post-inspection calculations from workers to the UAVs through edge computing. In ref. [44], the authors jointly optimised the UAV trajectory and transmit power control to maximise the minimum throughput in the downlink transmission from UAVs to ground users. Multi-rechargeable UAVs were considered in ref. [45] to provide support to ground Internet of Things (IoT) nodes. The authors maximised the system energy efficiency by jointly optimising the node assignment scheduling, the UAV trajectory planning, and the transmit power control.

Next, we briefly summarise specific UAVs applications in smart grid. In ref. [46], the authors introduced a novel approach where a UAV is used as a physical courier to transport secret key bits from the control centre to remote control devices (sensors, actuators, smart metres etc.) in smart grid. An optimisation problem was formulated to determine the flight route with the lowest risk of attack while considering key deficiency and battery capacity. In ref. [47], the authors provided an overview of the potential applications of commercially available Unmanned Aircraft Systems (UAS) in smart grids for British Columbia Transmission Corporation. In ref. [48], the authors discussed the results of over-the-air civil GPS spoofing tests that targeted two systems reliant on civil GPS: a civilian UAV and a GPS time-reference receiver used in smart grid measurement devices. The experiments revealed that the UAV could be hijacked by a GPS spoofer, manipulating its perceived location. In ref. [49], the authors introduced an innovative solution for the evolution of the smart metering system utilising Low Power Wide Area Network, a set of IoT communication technologies and UAVs to collect energy consumption data at regular intervals.

The existing literature is limited to the following aspects:

• Existing research fail to provide a fully automated system to assess power grid's damage after some disaster. Such a system should not depend on on-ground human crew to visit the loads and inspect the lines. Using a combination of a vehicle and a UAV as in ref. [16] can be impractical in many situations due to road conditions, accidents as well as hard-to-reach remote areas.

• The absence of battery recharging such as in refs. [18, 19], which is important to guarantee that the deployed number of UAVs would complete the inspection before battery depletion.

It is worth noting that even though the multi-UAVs paths optimisation is not a new problem in literature; however, it is novel for the power grid lines inspection. In specific, existing UAV flying path design [20–33, 39, 41, 44, 45] cannot be directly applied to power grid inspection, since the latter should ensure loads are connected to a healthy substation, and should consider load prioritisation, where inspecting the most critical loads first is of utmost importance for fast power restoration. Unfortunately, all the existing works related to UAVs path design for power inspection [12–19, 36, 38, 42] do not consider these important aspects.

To further highlight the main limitations of the related works with respect to the proposed method, we provide Table 1, which shows that, in addition to considering battery recharging, the proposed method applies to a single UAV and multiple UAVs.

TABLE 1 Comparison of the related works and the proposed method in terms of different criteria.

Work	Objective	Method used	Application	Automated	Human-controlled	Single UAV	Multi-UAVs	UAV-centric	Human-UAV	Battery recharging
Proposed	Minimise inspection time of critical loads	Two-stage framework	Overhead transmission lines	√		√	√	√		√
[12]	Autonomous monitoring of power substations	Deep Q-learning	Power substations	√		√	√	√
[13]	Autonomous transmission line detection	Beidou high-precision positioning technology	Transmission lines	√		√		√		√
[14]	Optimised inspection path planning in terms of distance and path smoothness	Sampling-based sequential optimisation	Power pylon inspection	√		√		√
[15]	Autonomous power lines tracking	Simulation using proportional integral derivative (PID) controllers	Power lines inspection	√		√		√
[16]	Joint vehicle-UAV route optimisation	Travelling salesman problem and arc routing problem	Power lines inspection		√	√			√	√
[17]	Joint human-UAV fault scheduling inspections	Cooperative evolutionary algorithm	Fault inspection for transmission networks		√	√	√		√
[18]	UAVs paths optimisation in terms of operation costs and inspection time	Two-stage solution	Power grid damage assessment	√			√	√
[19]	Optimisation of UAV inspection paths	Genetic algorithm and genetic simulated annealing	Tower and line corridor monitoring	√		√		√
[20]	UAV path planning method	Multivariable optimisation	Post-disaster emergency response	√			√	√
[21]	UAV path planning method	Deep reinforcement learning	Three-dimensional path planning	√		√		√
[22]	UAV path planning method	Swarm optimisation	Complex three-dimensional battlefield environment	√		√	√	√
[23]	Minimise paths length under quality-of-service constraints	Decentralised reinforcement learning algorithm	Energy-efficient multi-UAVs trajectory planning	√			√	√		√
[24]	Minimise inspection path length of UAVs	Mixed-integer non-linear programming	Oil and gas pipeline networks	√			√	√
[25]	Minimises energy and inspection time	Efficient approximation algorithm	Autonomous inspection	√			√	√
[26]	Minimise energy consumption, number of turns and completion time, and increase coverage	Partitioning method	Path planning for UAVs in the presence of non-flying zones	√		√	√	√
[27]	Minimise energy consumption	Genetic algorithm	Energy efficient path planning	√		√		√
[28]	Collision-free and time efficient path planning	Metaheuristic algorithms	Pre-disaster assessment	√		√		√
[29]	Optimising UAV flight path in terms of smoothness and distance	Sparrow search algorithm and particle swarm algorithm	UAV path planning in presence of environmental constraints	√		√		√
[30]	Obtain UAV shortest collision-free paths	Evolutionary algorithm	Three-dimensional terrain	√		√		√
[31]	Optimising UAVs paths in terms of fitness and feasibility	Coordinated evolutionary algorithm	Military applications	√			√	√
[32]	Modelling UAV navigation in large-scale complex environments	Deep reinforcement learning with non-expert helpers	IoT applications	√		√		√
[33]	Resource allocation	Lagrange dual decomposition and concave-convex procedure	Heterogeneous networks	√		√	√		√
[34]	Power lines detection	Canny algorithm	Power lines inspection	√		√		√
[35]	Increasing analysis accuracy of inspection	Hybrid networking	Overhead lines inspection	√		√		√
[36]	Design a flight monitoring system of transmission line patrol	Jordan curve theorem	Transmission lines inspection	√		√		√
[37]	Detect the insulators in power line inspection images	Federated learning	Power lines images detection	√		√	√	√
[38]	Designing an integrated drone system for power inspection,	Energy harvesting, artificial intelligent, and system autonomy	Autonomous power line inspection	√		√		√		√
[39]	Modelling efficient trajectories for a UAV swarm	Satisfiability modulo theories	Trajectory planning	√			√	√		√
[40]	Modelling UAV navigation for critical transmission lines	Satisfiability modulo theories	Inspection of critical power lines	√			√	√		√
[41]	3D navigation path planning	Evolutionary algorithms	Military applications	√		√		√
[42]	A drone framework for autonomous power line inspection	Cloud service, localisation system, and planning algorithms	Power inspection	√		√		√		√
[43]	Increase calculation resources on the inspection data	Edge computing method	Transmission lines inspection	√		√		√
[44]	Optimising user scheduling and association, UAV trajectory, and transmit power	Convex optimisation	UAV trajectory design	√			√	√	√
[45]	Node assignment scheduling, UAV trajectory planning, and transmit power control to support IoT nodes	Sequential convex optimisation and block coordinate iterative algorithm	IoT applications	√			√	√	√	√

Contributions and organisation

The contributions of this paper are summarised next. We optimise the navigation and flying paths of multi-UAVs in power grids with the objective of achieving a short inspection time for all critical loads. The problem formulation gives high priority to certain loads that are considered critical for power delivery and connectivity. The flying paths of the multi-UAVs are formulated by considering the battery recharging and by partitioning the power grid into multiple clusters, each corresponding to the flying zone of a single UAV.

Due to the problem complexity, a two-stage low-complexity efficient framework consisting of a set of functions is developed, where in the first stage, the framework provides a solution that determines the next best set of n_c critical load(s) to visit and their corresponding planned paths, and in the second stage, it provides the actual paths to the determined critical load(s), which may differ from the first stage solution due to failed power lines. For a given graph cluster, the computational complexity scales as $$O\left({\vert {I}_{P}\vert }^{2}\cdot \,\vert {I}_{P}\vert !/\left(\vert {I}_{P}\vert -{n}_{c}\right)!\right)$$, where |I_P| is the set of critical loads to inspect.

Our simulations present the planned paths, the navigation paths, and the flying time (excluding recharging time) for each critical load when different power lines fail and when single and multiple UAVs are employed. Our results show the merits of our proposed framework as it accounts for: (i) UAV recharging events, (ii) restricting the UAV to visit each power line only once, and (iii) the ability to adapt the framework to multiple UAVs. Such merits highly impact the practicality of the proposed framework.

It should be emphasised that when inspecting the path health status, other factors such as the capacity and reliability of the facilities on that path are not considered, since we mainly focus only on the power grid assessment using UAVs, and not on the maintenance and repair stage. In real-world scenarios, the power grid assessment stage (whether using UAVs or not) is followed by maintenance and restoration crews dispatch. The maintenance crews will check and repair the damaged equipment while the restoration crews will separate the damaged parts with manual switching to operate the healthy part and provide power to critical loads. In this process, the capacity of the lines must be checked, and necessary load shedding should be implemented. Moreover, the load shedding is done on low priority loads, while the main focus of this work is the assessment of highly critical loads. For instance, papers [50–53] investigated the dispatch of the restoration crews, however, they assumed that the damaged lines were already known, which is the main outcome of this paper that updates the topology after detecting the damaged lines.

The remainder of this paper is organised as follows. In Section 2, the power system model and the UAV parameters are presented. Section 2 also presents the formulation of the optimisation problem of UAVs critical load inspection. Section 3 presents an efficient framework to solve the problem. Simulation results and discussions are given in Section 4. Finally, the paper is concluded in Section 5.

SYSTEM MODEL AND PROBLEM FORMULATION

In this section, we present the system model of the power grid and the UAV specifications. Also, we mathematically formulate the UAVs flying paths as an optimisation problem.

Power grid model

The power system is described as a graph that consists of u_i buses (nodes) connected by power lines (edges), where index i ∈ N = {1,2,…,N}, and N denotes the total number of buses. Some of the buses act as substations, while the rest act as loads. Let A be the weighted binary adjacency matrix whose elements a_b,v denote the (b,v)^th element of A∈ {0,1}^N×N. If A (b,v) = 1, then (b,v) is an edge in the power grid graph. Then, the number of edges in the system, Γ, is the total number of 1's in matrix A. For each edge (b,v), w_b,v corresponds to the weight of the edge, representing the edge length. Let G be the set of substations. A certain percentage of loads are defined to be critical loads. We would like to point out that critical loads are usually known before a disaster occurs. These are the loads that would experience maximum damage (economic, health, or social) due to a power outage. Examples include hospitals, street lighting, water stations, and other critical infrastructures. Papers [51, 53–55] assumed predefined critical loads, which is usually the case in real-world scenarios. Denote by I_P the set of critical loads. These loads have a high priority of inspection as they serve a large number of customers and/or serve emergency responders.

In this work, we use the stochastic geometry-based power grid model that we previously developed in refs. [56–58]. Stochastic geometry allows to distribute the power elements spatially in a geographical region using a doubly stochastic process: (i) Poisson line process to model the spatial locations of roads and (ii) 1D homogeneous Poisson point process (HPPP) to model the spatial locations of buses on each Poisson line. The advantage of using such a model is the availability of spatial topological information of buses, which can be exploited for the planning of UAVs flying paths. In summary, the model is generated using five main steps: (i) define a geographical area representing a region; (ii) generate Poisson lines in that area representing roads; (iii) distribute bus nodes on each line; (iv) connect buses together; and (v) statistically assign electrical parameters.

UAV model

The UAV used for inspection contains components, such as a flight computer, video cameras for image processing, an inertial measurement unit for measuring the angular rate and orientation of the rotorcraft in relation to the overhead power lines, a battery power pack, and a sensor, which supplies data for advanced functionalities like obstacle detection and path planning [6]. The UAV utilises a map database to retrieve the GPS coordinates of the affected areas. Subsequently, a flight path is generated specifically for these damaged areas. The UAV then autonomously navigates to the designated area, gathering necessary data such as live feeds, panoramic images, and, in some cases, 3D scans. The flight path determines when the UAV should return to the recharging station to recharge itself, ensuring continuous flight. Simultaneously, the captured data is uploaded to the server, enabling system operators to remotely access the information. By swiftly reviewing the data, the system operators can make informed decisions to restore power to the affected regions. Additionally, the UAV periodically transmits data during the mission, allowing system operators to view real-time information through their mobile applications or desktop computers [59].

We consider multiple UAVs that scan the damaged area of the power grid to detect faulty lines and assess the overall damage of the power grid elements. The UAVs initially inspect the most critical loads in the system. These loads require immediate repair and maintenance in the case of failures. Usually, the utility would know about the supply outage of these critical loads. However, the cause of the outage is unknown, and could be due to multiple failures as in the case of natural disasters. The UAVs move at a constant speed ν m/s with a maximum flying range of D, before it requires recharging to continue operating. To employ multiple UAVs, we partition the power grid graph into multiple clusters, where each cluster corresponds to the flying zone of a single UAV. Let J = {J₁,···,J_K} be the set of K graph partitions, and $${J}_{m}\cap {J}_{{m}^{\prime }}=\varnothing $$ for m ≠ m′. To prevent potential issues such as an unfinished trip or complete failure of the UAV, the implemented inspection path guides the UAV to the closest recharging station when its battery is low. This ensures that the UAV avoids unnecessary travel and the risk of a total breakdown. Let $${c}_{m}^{\ast }$$ denote the recharging node in cluster J_m, defined as $${c}_{m}^{\ast }$$ = $${\mathrm{argmin}}_{{u}_{i}\in {N}_{{J}_{m}}}\left({M}_{{u}_{i}}=\min \left\{\Vert {u}_{i},{u}_{j}\Vert ,{u}_{j}\in {N}_{{J}_{m}},{u}_{j}\ne {u}_{i}\right\}\right)$$, where $${N}_{{J}_{m}}$$ is the total number of nodes in cluster J_m; ‖u_i,u_j‖ is the distance between nodes u_i and u_j; and $${M}_{{u}_{i}}$$ is the minimum distance from node u_i to each node in the cluster, that is, $${c}_{m}^{\ast }$$ is the node with the shortest total flying distance to all the other nodes in cluster J_m [60–62].

Each time a UAV needs to move from one node to the next, its battery capacity is first checked. If the UAV can fly to the next node and has sufficient battery charge to fly from that node to the recharging node, then the UAV can proceed. Otherwise, the UAV needs to return to the recharging node to fully recharge before it can proceed. The longer the transmission lines and distances between nodes are, the higher the chance the UAV would require multiple stops at the recharging node along the way. Our proposed framework is generally applicable to any number of recharging nodes. In this case, the UAV flies to the nearest recharging point. For simplicity of presentation, we assume a single recharging location in each cluster.

Optimal design of UAV's flying path

The objective of the problem is minimising the completion time for inspecting all critical loads in the system by all the UAVs for fast power restoration. While deploying a large number of UAVs can accelerate the inspection time due to their low costs, however this seemingly attractive solution can be impractical since it causes collisions with other UAVs flying in the same area and inspecting along the installed transmission lines. Therefore, as mentioned in Section 2.2, a single UAV will be limited to a single flying zone.

We define the following parameters: u_k,m is the kth critical load in cluster J_m ∈ J; P_k,m is the candidate path from UAV's current node position to critical load u_k,m in cluster J_m ∈ J; F (P_k,m) is the total path length traversed by UAV m to reach critical load u_k,m; n_k,m is the total number of nodes to visit on path P_k,m to reach critical load u_k,m; $${\vert H}_{{u}_{i}}\vert $$ is the 1-hop neighbour set of node u_i; and D_f,i,m is the total distance flown before recharging for the first time or after each recharge by UAV m.

Moreover, we define the following decision variable: x_j,m is a binary decision variable such that $${x}_{j,m}=\left\{\begin{array}{@{}c@{}}1,\mathrm{i}\mathrm{f}\,\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\,{u}_{j}\,\mathrm{i}\mathrm{s}\,\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{d}\,\mathrm{b}\mathrm{y}\,\mathrm{t}\mathrm{h}\mathrm{e}\,\mathrm{U}\mathrm{A}\mathrm{V}\,\mathrm{i}\mathrm{n}\,\mathrm{c}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\,{J}_{m}\\ 0,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.$$

The total path length, F (P_k,m), can be expressed as follows: 1 $$F\left({P}_{k,m}\right)=\sum\limits _{i=1}^{{n}_{k,m}}\sum\limits _{j=1}^{\vert {H}_{{u}_{i}}\vert }{w}_{{u}_{i},{u}_{j}{x}_{j,m}}\mathbb{1}\left({a}_{{u}_{i},{u}_{j}}=1\right),$$ where $${w}_{{u}_{i},{u}_{j}{x}_{j,m}}$$ is the path length between nodes u_i and u_j, and $$\mathbb{1}\left({a}_{{u}_{i},{u}_{j}}=1\right)$$ is the indicator function that there is an edge connecting node u_i to node u_j. In Equation (1), the decision variable x_j,m indicates which of the immediate neighbours, $${\vert H}_{{u}_{i}}\vert $$, of node u_i is selected as the next visiting node on path P_k,m. Figure 1 illustrates a small network (single cluster) with a single substation and a single critical load. There exist multiple paths {P₁} from substation labelled 1 to critical load labelled 7, mainly {P₁} = {[1−2−4−7], [1−2−4−5−6−7], [1−3−5−6−7], [1−3−5−4−7]}, with corresponding total paths' length {F(P₁)} = {7.5,12,10,9.5}. The path with the lowest cost is [1−2−4−7]; however, it should be noted that if the UAV flies directly from substation 1 to critical load 7, it will not know whether a healthy connection exists between the substation and the critical load. For instance, the line 2−4 can be damaged, and if the UAV skips this line, it will not realise that substation 1 is no longer capable of feeding critical load 7. Therefore, we need to ensure a healthy connection between a critical load and a substation through all of its intermediate nodes.

[IMAGE OMITTED. SEE PDF]

The optimisation objective is equivalent to minimising the total distance cruised by K UAVs to visit all the critical loads. The problem can be formulated as follows: 2a $${f=\min }_{{x}_{j},j\in N}\sum\limits _{m\in J}\sum\limits _{k\in {I}_{P}}F\left({P}_{k,m}\right),\forall k\in {I}_{P},$$ 2b $$\mathrm{s}.\mathrm{t}.\,\sum\limits _{{g}_{m}\in \left\{G\right\}}\sum\limits _{v\in {P}_{k,m}{\backslash}{g}_{m}}{a}_{v,{g}_{m}}\ge 1\forall k\in {I}_{P},m\in J,$$ 2c $${u}_{k,m}={\mathrm{argmin}}_{k\in {\Lambda }}F\left({P}_{k,m}\right),\forall m\in J,{\Lambda }=\left\{{I}_{P,m}\mathbb{1}(k=1){\increment}{I}_{P,m}{\backslash}\left\{1,\text{\ldots },k-1\right\}\mathbb{1}(k > 1)\right\},$$ 2d $${D}_{f,i,m}+{w}_{{u}_{i},{u}_{j}{x}_{j,m}}+{w}_{{u}_{j},{c}_{m}^{\ast }{x}_{{c}_{m}^{\ast }}}< D,\forall m,$$ The objective function in Equation (2a) minimises the path length for each critical load, u_k,m, among all of the potential candidate paths, {P_k,m}, over all clusters. For instance, in Figure 1, the path that minimises the total distance to critical load 7 is [1−2−4−7]. Constraint (2b) ensures that there is at least a single edge in the path P_k,m that connects the target critical load u_k,m directly or indirectly to a substation g_m in cluster J_m ∈ J. For instance, in Figure 1, edges 2−4 and 4−7 on path [1−2−4−7] connect indirectly to substation 1. In other words, constraint (2b) checks for healthy power lines, which makes the optimisation problem specific to the inspection of overhead transmission lines. Constraint (2c) determines the next critical load to inspect in cluster J_m ∈ J based on the closest distance to the current position of UAV m. In other words, the total flying distance for each path, P_k,m, to a critical load u_k,m ∈ I_P,m is calculated, and the critical load corresponding to the path with the minimum distance is initially selected for inspection among all the critical loads. Next, the critical load that was inspected is removed from I_P,m, and the critical load with the second minimum flying path is selected for inspection among the remaining critical loads, and so on. For instance, if we assume that node 5 is a critical load in Figure 1, then starting from substation 1, node 5 will be inspected prior to node 7, since the length of the shortest path to 5 ( [1−3−5]) is smaller than that to node 7. Constraint (2d) ensures that the flying distance by each UAV m to the next node is less than the remaining distance before a recharge is required. This allows the path planning function to handle insufficient battery energy.

The formulated optimisation problem is a binary linear program, which is proven to be an NP-hard problem that is not solvable in polynomial time [63]. In addition, the complexity of the problem makes it challenging to obtain an optimal solution, especially that the optimal path can only be obtained after the K UAVs acquire knowledge of failed lines during their cruise. This means that the formulated problem requires a central entity to collect information from the entire power grid to obtain the optimal paths. This makes it a complex and an inflexible problem. Therefore, we turn to a lower complexity more flexible approach that can solve the problem on the fly by adapting the found optimal paths to the available (local) learnt information about the failed lines. We propose a two-stage optimisation framework that is carried out over a number of rounds for each cluster. In the first stage, the framework determines the next best set of n_c critical load(s) to visit along with the corresponding planned paths, and in the second stage, the UAV cruises along the planned paths to the determined critical load(s). In the first round, the power grid topology is assumed to be healthy (no failed lines) by the solution obtained from the first stage. Then, the second stage solution updates the topology information as the UAV encounters failed lines along the planned path, which is updated accordingly to specify the navigated path. The updated topology is used in the next round by the first stage to determine the next set of n_c critical load(s) to inspect, and so on. This two-stage framework is proposed in Section 3 to obtain the optimal paths to all of the critical loads.

EFFICIENT FRAMEWORK FOR PATH DESIGN

In this section, we present an efficient framework consisting of a set of functions to solve the optimisation problem of Section 2.3. Table 2 lists the parameters used in the proposed framework along with their definitions. In what follows, the proposed framework is described in a single cluster. The proposed framework attempts to obtain the best paths to all critical loads via a two-stage solution. The first stage consists of finding the set of n_c critical load(s) to inspect based on the ones that minimise the total flying distance. Initially, the power grid topology is assumed to be healthy and optimal planned paths are obtained to reach the determined set of n_c critical load(s). In the second stage, the planned paths by the first stage solution are provided as inputs to the UAV. As the UAV cruises over these pre-planned routes, it might encounter some failed lines, which incites the UAV to use an alternative shortest route to the destination. When the UAV completes its navigation path to the target critical loads, the power grid topology information is updated, and then used by the first stage solution in the second round of the program to determine the next set of n_c critical loads, and so on. The number of rounds continues until all critical nodes are covered. The proposed framework works in a serial forward fashion since the optimal path to the next critical load can only be obtained after the local power grid topology information about the status of transmission lines has been learnt. This highlights the two main characteristics of this problem. First, the UAV path design problem cannot be solved in a single shot unless the status of all of the overhead transmission lines are known in advance, which is impractical. This also means that the problem cannot be formulated as a Travelling Salesman Problem. Second, the problem cannot be solved backwards in time, such as using the dynamic programming approach, since this would require the global knowledge of the post-disaster topological information. Moreover, if the problem is solved starting at the last stage, and in the case that an optimal path is not found due to some failed lines, the optimal paths for the other interrelated stages cannot be obtained, even though they might exist.

TABLE 2 List of parameters and their definitions.

Parameter	Definition
c∗	Recharging location
Df	Total distance flown before recharging for the first time or after each recharge
dest	Destination node of the path
gen	Nearest substation list
IP	A list containing the critical loads
nc	Number of critical loads in a set
nextOpts	Next route options
nextPaths	Next paths that will be followed
nextS	Next best set of critical loads to inspect
obtainedPath	Resulting paths to follow
s	Matrix containing all sets combinations
setN	Total number of sets
src	Source node of the path
T	Power grid topology
visited	Lines that are already inspected

A flowchart illustrating how the framework works is given in Figure 2. The main function takes as input parameters: the power grid topology, the set of critical loads, the number of critical loads in a set, the recharging node, the substations list, the total distance flown, and the visited lines set. First, the main program provides in each round all the possible sets of n_c critical load combinations that have not been inspected. Initially, the program assumes there are no failed lines. In each round k, the main program calls the first stage solution consisting of three different functions: ‘nextCritical’, ‘option’, and ‘recharge’. The function ‘nextCritical’ attempts to find the shortest path among all the possible combinations by comparing three different routing options: ‘A’, ‘B’, and ‘C’ provided by function ‘option’, which will be explained later in details. Each of these routing options calls function ‘recharge’, which checks whether the UAV requires recharging given a certain path. The resulting planned paths and options used are then provided to the second stage of the framework. The second stage consists of functions ‘route’, ‘checkFailed’, and ‘recharge’. In function ‘route’, the UAV flies over the planned path and might encounter failed lines along the way. The path is checked for failed lines via function ‘checkFailed’. In the case of failed lines, the UAV attempts an alternative shortest path to the target critical load. With a new alternative path, function ‘recharge’ must be called again to check whether a recharge is needed. These two stages are called over a number of rounds until all critical nodes are covered.

[IMAGE OMITTED. SEE PDF]

Next, we provide theoretical analysis on UAVs' battery recharging, state of charge, and energy consumption. Each UAV m consumes flying and hovering power P_m(v) as follows [64]: 3 $${P}_{m}(v)={P}_{b}\left(1+\frac{3{v}^{2}}{{\kappa }_{tip}^{2}}\right)+{P}_{h}{\left(\sqrt{1+\frac{{v}^{4}}{4{\kappa }_{o}^{4}}}-\frac{{v}^{2}}{2{\kappa }_{o}^{2}}\right)}^{1/2}+\frac{1}{2}{d}_{o}\rho {\mu }_{o}Z{v}^{3},$$ where P_b and P_h denote the blade profile power and derived power when hovering, respectively; κ_tip denotes the tip speed of the blade; κ_o is the mean rotor induced velocity when hovering; d_o is the fuselage drag radio; ρ is the air density; μ_o is the rotor solidity; and Z is the area of the rotor disk.

The maximum energy of UAV m when hovering and flying should satisfy 4 $${E}_{\max ,m}\ge \frac{2{w}_{{u}_{i},{c}_{m}^{\ast }{x}_{{c}_{m}^{\ast }}}}{v}{P}_{m}(v),$$ where $$2{w}_{{u}_{i},{c}_{m}^{\ast }{x}_{{c}_{m}^{\ast }}}$$ is the round-trip distance travelled by UAV m from node u_i to recharging station $${c}_{m}^{\ast }$$.

Let $${{\epsilon}}_{{u}_{i,m}}$$ denote the state of charge of UAV $$m$$ at node $${u}_{i};$$ and let $${\varphi }_{\max ,m}$$ and $${\varphi }_{re,t,m}$$ denote the maximum energy storage and the remaining energy before recharging at time $$t$$, then $${\varphi }_{\max ,m}$$−$${\varphi }_{re,t,m}$$ ≤ $${E}_{\max ,m}$$ [65].

The state of charge of each UAV should remain within permissible limits to ensure sufficient energy for the UAV to return to the recharging station to prevent total failure. The UAV state of charge evolution can be described as follows [66]: $${{\epsilon}}_{{u}_{i,m}}=\left\{\begin{array}{@{}c@{}}{{\epsilon}}_{{u}_{i-1,m}}-{E}_{{u}_{i},{u}_{i+1},m}\ \mathrm{i}\mathrm{f}\,{u}_{i+1}\ne {u}_{{c}_{m}^{\ast }}\\ {{\epsilon}}_{{u}_{i-1,m}}-{E}_{{u}_{i},{u}_{i+1},m}+b\left({u}_{i+1}\right),\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\end{array}\right.$$ where $${E}_{{u}_{i},{u}_{i+1},m}={P}_{m}(v){w}_{{u}_{i},{u}_{i+1}{x}_{{u}_{i+1},m}}/v$$ is the energy consumed by UAV m to fly from node u_i to node u_i+1; and b(.) is the charging function that maps the recharging station to an amount of energy to be recharged [66].

Main program

The main program defined below starts by constructing a set matrix s containing all of the possible set combinations of n_c critical load(s) in different orders. For instance, when n_c = 1 and the total number of critical loads is 4, the main program operates over 4 rounds (SetN = 4) to cover all the four critical loads. However, if n_c is 2, the main program needs to have only two rounds, with each round covering a set of 2 critical loads. In this case, the set matrix would consist of 12 rows and two columns corresponding to the first and second critical loads to be inspected in each round. That is, the total number of sets, SetN, is 2 for all the rounds. In the first round, the program selects the first two critical loads to inspect in a particular order before deciding in the second round the inspection order of the remaining two critical loads. Note that if we select n_c = 3, the set matrix size increases from 12 × 2 to 24 × 3, where in the first round, 3 nodes out of the total 4 are selected, and the remaining single node is selected in the second round. This in turn increases the computational time to finding an efficient path. In each round, functions ‘nextCritical’ (first stage solution) and ‘route’ (second stage solution) are called. The first function determines the best set of critical loads to inspect and their corresponding planned paths. This function satisfies constraint (2c). The second function ‘route’ takes as input the planned paths and provides the navigation routes. The planned paths and navigation paths differ only in the case when the UAV encounters failed lines along the way. In this case, function ‘route’ updates the topology information, which is then used in the next round by function ‘nextCritical’ when planning the paths of the next set of critical loads. The function ‘route’ finds a near-optimal solution to the objective function in Equation (2a). The main program ends when all the critical loads have been inspected (Algorithm 1).

1

Algorithm

Main program finding an efficient flying path.

2

Algorithm

Finding the next n_c critical loads to inspect.

First stage solution

In this subsection, we present the first stage solution provided by function ‘nextCritical’ in Algorithm 2. This function provides the first stage solution by finding which is the best set of n_c critical load(s) to inspect among all the combinations in matrix s, based on the ones minimising the total cruised distance. The function also provides as output the planned paths to reach these two critical loads based on three different path options: ‘A’, ‘B’, and ‘C’. The three options allow to achieve the goal of having a healthy path to the critical loads by checking all of the routing possibilities. In option ‘A’, the UAV flies on the shortest path from the source substation to the critical node. In option ‘B’, the UAV flies directly from the source node to the critical node, and then from the critical node to either the nearest substation or to a known connection to a substation. In option ‘C’, the UAV flies directly from the source node to node p, then from p, it finds the shortest path to the destination node, where p is the nearest point to the destination node that has been inspected.

3

Algorithm

Option function definitions.

Figure 3 illustrates the three different routing options to critical loads 4, 6 and 7. Starting from substation 1, the UAV flies to load 4 using option ‘A’. From load 4, the UAV uses option ‘B’ to fly directly to node 7, and then to node 3 via node 8. Here, the UAV does not need to continue flying to substation 1, since the line 2–3 has already been inspected. Finally, the UAV uses option ‘C’, where it flies to node 4, which is the nearest destination node that has been inspected. Then, it finds a shortest path to critical load 6 (path 4-5-6). Choosing the best option based on the visited nodes and the power grid topology minimises the overall flying distance. These option definitions are further explained by Algorithm 3.

[IMAGE OMITTED. SEE PDF]

As shown in Algorithm 2, we start by working over the set combinations of critical loads. For a given set, we obtain the planned paths and the total distances of the paths using the three options: ‘A’, ‘B’ and ‘C’. For each of these options, we check at lines 7, 12 and 17 whether the obtained paths require intermediate recharging by calling the function ‘recharge’, as described by Algorithm 6. If the parameter ‘possible’ is 0, then the algorithm could not find a path using the specified option. Then, at line 21 we obtain the minimum distance among the three options. We check to which option the minimum distance corresponds to and we save the paths and options obtained at lines 23–24, 27–28, and 30–31. Finally, we obtain the best set combination, option, and optimal paths that minimise the total cost among all the possible set combinations (line 41). The computational complexity of Algorithm 2 is O((Γ + NlogN).S.setN), where S is the row size of matrix s.

Next, we explain in detail in Algorithm 3 the three options for obtaining the planned paths. These options find the optimal paths to the critical loads by comparing the total flying distance using the three different routing strategies, as previously explained. Option ‘A’ is straightforward and does not need further clarification. In option ‘B’, the direct distance from the source to the destination node is calculated at line 7, then at line 8 we obtain the shortest path from the destination node to the nearest substation. Then, at lines 9–12, we check for any common links in the obtained path with previously inspected links, and if found, we remove them from the path. Finally, we calculate the total distance of the path at lines 13–16, and we add it to the direct distance from source node to the destination node at line 17. In option ‘C’, the UAV flies directly from the source node to the nearest node to the destination node that has been inspected, referred to as node p. Then, the UAV cruises on the shortest path from p to the critical load (lines 21–23). Here again, we first calculate at line 22 the direct distance to fly from the source node to node p, then at line 23, we obtain the shortest path from node p to the destination node. Lines 24–27 calculate the total distance of this path, which is then added to the direct distance at line 28. Finally, the resulting path is the concatenation of the initial source node with the shortest path from p to the destination node (line 29). The computational complexity of Algorithm 3 is O(Γ+NlogN). Note that all the mentioned options ensure an indirect or direct connection of the critical load to a healthy substation, which satisfies constraint (2b).

Second stage solution

Here, we define the navigation path of the UAV given by function ‘route’ in Algorithm 4. This function defines the second-stage solution of the framework, where the UAV cruises along the planned path to reach the destined critical load. Along its path, the UAV might encounter some failed lines. In this case, it attempts to find an alternative route to the destination node based on the shortest path. That is why the planned and navigation paths may be different.

First, the function ‘route’ takes as input from the first stage the best set of critical loads, the planned paths, the routing options, the updated power grid topology information, the recharging node, and the flown distance of the UAV and outputs the navigated paths, the updated topology, and the flown distance. The function starts by checking whether there are any failed lines along the path provided by the first stage at line 6. The ‘checkFailed’ function is defined in Algorithm 5. Line 7 checks whether a path cannot be found to the destination node. In this case, we attempt to find a route from a different nearest substation to the critical load as specified at line 10. Then, we check for any failed lines along the new path at line 11. Line 12 updates the path with any required recharging. In the case of not finding another alternative substation, we return an empty path at line 14. The computational complexity is O(Γ + NlogN).

Algorithm 5 defines ‘checkFailed’, which checks for any failed lines along a path. This function first scans the planned path provided by the first stage solution (given by function ‘nextCritical’). Then, it updates the power grid topology information as it finds failed lines (line 6). In the case of found failed lines, the start of the path will be the source of the failed segment. From this start node, we attempt to find a new shortest path to the destination node at line 9. Line 10 concatenates the path from the initial source node up to the start node of the failed line, and the path from the start node to the destination node. The computational complexity is O(Γ + NlogN).

UAV battery recharging

In this subsection, we define the function ‘recharge’ as defined by Algorithm 6. This function is used in both the first and the second stages. It checks whether the UAV requires recharging as it cruises along its path. In the case of a need for a recharge, the function updates the path by inserting at the desired nodes a round- trip to the recharging location. First, the function checks at line 5 whether the UAV can move from the current node to the next node on the path by checking if the total flown distance including the distance to fly to the recharging node location is greater than D. This ensures that at anytime the UAV has enough recharging battery to fly to the recharging location. This satisfies constraint (2d). If the UAV requires its battery to be recharged, then we add the recharging node in the path nextPaths (line 8), and we reset the flown distance to the direct distance from the recharging location back to the node where it flew from (line 9). Then, we check at line 11 if after a recharge, the UAV can cruise to the next node. If this is not possible, then the UAV cannot continue the inspection process as it will be stuck at the current position. The computational complexity of Algorithm 6 is O(N).

4

Algorithm

Route navigation function definition.

5

Algorithm

‘checkFailed’ function definition.

6

Algorithm

Recharging function definition.

On the computational complexity of the framework

The computational complexity of the whole framework is O(K.(Γ_m + N_m logN_m). S_m.(setN_m)²) or O(K.(Γ_m + N_mlog N_m).S_m.(|I_P|_m/n_c,m)²), where the subscript m refers to cluster J_m ∈ J. The computational complexity increases linearithmically with the number of clusters and power grid size. However, due to their inherent nature, power grids graphs are sparse [67], that is, the total number of edges is much less than the square of the number of nodes (Γ ≪ N²). This means that when obtaining the shortest path, some of the adjacent nodes might be revisited. Since in the proposed framework, nodes are visited only once, the UAV skips the already-visited nodes by flying directly to the next unvisited node. This leads to an overall shorter flying time. The main disadvantage is that alternative paths might not be found in the case of failed lines.

For a single cluster and a fixed N and n_c, as the total number of critical loads in the system, |I_P|, increases, the row dimension size, S, of the set combinations matrix increases as |I_P|!/(|I_P| −n_c)!). This means that the computational complexity of the whole framework scales as $$O\left({\vert {I}_{P}\vert }^{2}\cdot \,\vert {I}_{P}\vert !/\left(\vert {I}_{P}\vert -{n}_{c}\right)!\right)$$. This gives insights on the selection of n_c, where increasing n_c, that is, considering more critical loads per round, can increase the computational time. For instance, if n_c = |I_P|, then the optimal paths are obtained through a brute-force search of all the possible ordered combinations of critical loads. Even though this leads to an optimal solution in terms of the total flying distance, due to the uncertainty of the system condition and the number of failed lines, this solution may become infeasible.

SIMULATIONS RESULTS AND DISCUSSIONS

In this section, we present the simulation results using MATLAB environment. Figure 4 shows a sample realisation of the power grid model defined in ref. [56] with N = 33 buses, and G = {1,30}. The model of refs. [56–58] provides the spatial distribution (geographical X-Y coordinates) of the buses, which is needed for designing the UAV flying path as explained in Section 2.1. Designing the UAV path on this model does not affect the generality of the proposed methodology as it can be applied on any other power grid as long as the geographical coordinates of the nodes in the power system are provided. The graph tree of the power system, shown in Figure 5, can be constructed according to Algorithms 1 and 2 in ref. [56], based on the physical connections between each bus and its immediate and non-immediate neighbouring buses. Moreover, Figure 5 shows the distances between the nodes in km, four different critical loads (I_P = {12,27,31,33}), as well as three tie lines between nodes 5 and 7, 14 and 15, 21 and 31.

[IMAGE OMITTED. SEE PDF]

[IMAGE OMITTED. SEE PDF]

In the proposed functions of Section 3, we use the Z-shortest path algorithm [68] that attempts to find Z candidate paths with the shortest length from a source node to a critical node. An example of a candidate path, P_k, to critical load u_k = 12 would be: P_k = {1,5,7,6,8,12}, with the total number of nodes to visit on this path is n_k = 6. As for the UAV, we use a long-range surveillance UAV, such as the DeltaQuad Pro UAV, with a cruise speed of ν = 18 m/s (65 km/h) and a maximum range of D = 150 km [69].

Finally, the system configuration is a 64-bit Microsoft Windows 10 Home with an Intel® Core™ i9-10980HK CPU @ 2.4 GHz, along with an installed Physical Memory (RAM) of 32 GB.

Results and insights

In what follows, we consider a single UAV and we select 10% of loads to be critical for illustration purposes, mainly I_P = {12,27,31,33}, and we select node 4 as the UAV's recharging station. We set n_c to 2 so that the computational time does not become large. This means that the main program would be called twice over two different sets, each consisting of two critical loads. Choosing a large number for n_c may result in additional computational effort that can go wasted once a failed line is found.

Table 3 shows the obtained results for the UAV inspection solution applied to the power grid system of Figure 5 in the case of failed lines between nodes 6−7, 22−23, and 21−31. The selection of the best two nodes consists of 12 possibilities: (12,27); (12,31); (12,33); (27,12); (27,31); (27,33); (31,12); (31,27); (31,33); (33,12); (33,27); and (33,31). The selection among these different combinations is based on the one providing the lowest total cost calculated as the total cruised distance including any required intermediate recharging. The main program initially selects the combination (33,27), where both nodes 33 and 27 are visited using option ‘B’, then the combination (31,12) is selected, where both nodes are visited using options ‘A’ and ‘C’ respectively. The planned paths consist of the expected paths that the UAV will follow based on the selected combinations and options. This initially assumes that the power grid topology does not have any failed lines. As the UAV navigates through the planned paths and encounters failed lines, the power grid topology is updated so it can be used in the planning phase of the next combination of nodes. In what follows, we use the term ‘planned path’ to denote the path obtained in the first-stage solution, and the term ‘navigation path’ to denote the path obtained in the second-stage solution. The table shows the cruised distance for each navigated path as well as the total cruised distance from the initial navigated path up to the current navigated path. We can see from Table 3 that the UAV has to take a longer path trying to reach critical load 31 from generator 30. This is because it could not find a healthy connection between 21 and 31. Due to this longer path, the UAV has to recharge as soon as it reaches load 20.

TABLE 3 Case of the failed 6–7, 22–23, and 21–31 lines.

Next critical loads	Option	Planned paths	Navigation path	Flying time (min)	Cruised distance (km)	Total cruised distance (km)
33 and 27	B	1-33-28-29-26-27-30	1-33-28-29-26-27-30	24.76	26.74	26.74
31 and 12	A	30-27-26-24-23-21-31	30-27-26-24-23-21-31-21-11-9-17-18-19-20-4-20-32-31	145	156.6	183.34
C	31-21-11-9-16-12	31-9-16-12	21.75	23.49	206.83

To get a good sense of the selection of the parameter n_c, we compare in Table 4 between ‘optimal’ and ‘suboptimal’ solutions in the case of no failed lines, where ‘optimal’ means that the program attempts to find the optimal critical loads sequence order to visit, that is, n_c = 4, as opposed to n_c = 2 in the ‘suboptimal’ solution. We clearly see a close performance between the two solutions where the optimal solution is 12.12% of flying time less than the suboptimal at the expense of a calculation time of 167.23 s to obtain the optimal sequence order using an 8-core CPU. In addition, to obtain the optimal solution, global knowledge (i.e. central server to solve the problem) might be needed, while the proposed low-complexity suboptimal solution requires only local knowledge, making it more convenient to be implemented at the UAVs rather than at the cloud.

TABLE 4 Comparison between optimal and suboptimal selection of critical loads.

Metric	Optimal	Suboptimal
Navigation paths	1-5-7-6-8-12	1-5-7-6-8-12
12-33-28-29-26-27-30	12-27-30
30-31-21-23-24-26	30-27-26-29-28-33
33-26-24-23-21-31
Flying time (min)	92.67	105.45

Simulation settings and benchmark

The traditional methods, as previously discussed in Section 1, consist of visual inspection by an on-ground operational staff or by a helicopter. There are several factors involved in these methods that are difficult to simulate, such as weather conditions, road conditions, varying vehicle speed, and vehicles accidents that make the damaged areas difficult to reach. All this leads to a difficulty in taking into account the safety of the crew. That, in addition to the remote areas that are not easily accessible on foot or by a vehicle. Because we cannot capture these factors in the simulation, we cannot provide a fair comparison between the traditional methods of inspection and the UAV. However, in this section, we compare the proposed framework to several related works including the benchmark solution proposed in ref. [18]. The work of Lim et al. [18] has a similar objective to ours in that it attempts to optimise UAV flying path in the event of extreme weather conditions, as was presented in Section 1.1. In ref. [18], multiple UAVs were initially positioned around the perimeter of the predicted impacted area. Then they were optimally re-positioned after the damage occurred. Based on the locations of UAVs, optimal paths were generated from depots to target edges. The main differences between ref. [18] and our proposed solution are as follows:

• In ref. [18], the UAVs did not recharge along their paths. Instead in the optimisation problem, the authors forced a constraint where a UAV completes the path before it runs out of battery. The UAV's flight path was bounded by the maximum flying time. Whereas our work considers UAV battery recharging as defined by function ‘recharge’.

• In ref. [18], a target edge can be visited by the same or multiple UAVs. If a target edge is inspected, then a UAV can still visit it to reach to other edges but without visually inspecting it again. However, the authors imposed a limit on the number of UAVs that visit the same edge. In our work, we do not revisit an edge that a UAV has inspected or has cruised over according to Algorithm 3.

• Unlike our work, the authors in ref. [18] did not consider load prioritisation, which is an important aspect of the power grid for fast power restoration. Rather, the authors considered that the UAVs need to inspect all of the target edges in the affected area.

Moreover, we compare our proposed framework to the works in refs. [38–40, 42, 70]. In ref. [38], when the battery is getting depleted, the UAV would autonomously land on a power line to recharge using an inductive harvester; however, the UAV would require 2.4 h to recharge its battery from 20% to 100%, which significantly increases the inspection time during an emergency. In our work, the UAV uses a recharging station to complete the inspection of critical loads faster. In ref. [39], the navigation paths are subject to several constraints: (i) resilience, where multiple UAVs inspect the same targets to reliably collect data from the necessary points; (ii) data freshness which specifies the time within which a specific number of UAVs must visit a point to ensure no data discrepancy; and (iii) fuel cost which should remain within a budget so that the UAV can reach the destination within a certain time limit. However, our approach does not focus on resiliency and data freshness, but on minimising the total inspection time for emergency-critical events. Moreover, the planned navigation paths should minimise the time to reach the critical loads, and thus no upper bound limit is imposed on the total flying time. In ref. [40], the UAVs navigation paths consider battery recharging and critical loads inspection; however, unlike our approach, the planned paths did not minimise the total inspection time to inspect all critical loads. In ref. [42], the UAV autonomously recharges its battery after landing on the power line it is inspecting to be capable of long-distance inspections. In our work, the UAV flies towards the recharging station only if the flying distance to the next node is less than the remaining distance before a recharge is required. This would eliminate unnecessary recharging stops that would increase the total inspection time. In ref. [70], the UAV uses an inductive harvester device to harvest enough power from power lines to recharge its battery. However, there is no navigation path planning for UAVs.

Table 5 shows the case when the UAV does not recharge along the path when the maximum range is D = 100 km. We can clearly see that without recharging the UAV, the UAV cannot complete the whole path and is forced to stop at some intermediary node. For instance, the UAV fails to inspect critical load 12 due to running out of battery and exceeding the maximum flying range after reaching critical load 31. This leads to 31.58% of nodes not being visited and inspected. Hence, it is important to take into account in the flying path design the recharging of the battery; otherwise, the battery might not be guaranteed to last for all UAVs for the completion of all inspection tasks as in ref. [18]. Note that we limit our comparison to the case of no failed lines since the benchmark method could not reach all of the critical loads despite the considered best case scenario when the power grid topology is completely healthy.

TABLE 5 Case of no recharging and no failed lines.

Next critical loads	Option	Planned paths	Navigation path	Last node reached	Total cruised distance (km)
33 and 27	B	1-33-28-29-26-27-30	1-33-28-29-26-27-30	30	26.74
31 and 12	A	30-27-26-24-23-21-31	30-27-26-24-23-21-31	31	87.14
B	31-12-8-6-7-5-1

Next, we compare the case of multi-UAVs flown together to inspect critical loads: I_P = {6,12,27,31,33}. The following is assumed: the failed lines are: 12−16; 21−23; and 28−33; D = 150 km; n_c = 1; G = {1,8,30}; we assume the recharging nodes in the flying zone to be 4 in the case of a single UAV, 4 and 23 in the case of 2 UAVs, and 4, 14, and 23 in the case of 3 UAVs. To employ multiple UAVs, we partition the graph tree of Figure 5 into multiple clusters, where each cluster corresponds to the flying zone of a single UAV. This approach makes our method scalable to a larger number of UAVs depending on the size of the partition chosen. Table 6 shows the planned, navigation paths, and the total flying time (excluding recharging time) for the case of 1, 2, and 3 UAVs flown simultaneously. From Table 6, it is clear that a single UAV was able to scan the whole zone by requiring a single stop to recharge its battery at node 4 1

In this paper, we do not consider the unlikely events of UAVs' technical failures.

. Moreover, as the number of UAVs increases, the total inspection time decreases. In specific, the total inspection time decreases by 67.11% and 76% in the case of 2 and 3 UAVs respectively.

TABLE 6 Flying time comparison for different number of unmanned aerial vehicles.

Number of UAVs	Planned paths	Navigation paths	Flying time (min)
1	1-5-7-6	1-5-7-6	201.75
6-12-8	6-12-8
8-27-30	8-27-30
30-27-26-29-28-33	30-27-26-29-28-33
33-26-24-23-21-31	33-26-24-23-21-23-22-4-22-14-15-16-9-11-21-31
2	1-5-7-6	1-5-7-6	66.35
6-12-8	6-12-8
8-31-32-20-19-18-17-9-16-12	8-31-32-20-19-18-17-9-16-12
30-27	30-27
27-26-29-28-33	27-26-29-28-33
3	1-5-7-6	1-5-7-6	48.43
8-12	8-12
12-31-32-20-19-18-17-9-16-12	12-31-32-20-19-18-17-9-16-12
30-27	30-27
27-26-29-28-33	27-26-29-28-33

To get insights on the effect of the number of predefined critical loads on the total inspection time, we plot in Figure 6 the total flying time in min for 1,…,10 critical loads, where 10 represents 30% of the total number of buses. We can see that when one UAV is employed, the total flying time increases with the number of critical loads until the number reaches 7, after which the total flying time decreases and remains stable. This is due to some critical loads being on the flying paths of other critical loads, which allows the UAV to inspect them along the way. Moreover, Figure 6 shows that the flying time of the multi-UAVs case is significantly reduced compared to the case of a single UAV. An average of 58.67% and 74.98% of time savings were found in the case of 2 and 3 UAVs, respectively, compared to the case of a single UAV. However, it should be noted that when multiple UAVs are flying simultaneously, some paths to critical loads might not be reachable since each UAV operates in its own flying zone to prevent collision with other UAVs, therefore limiting its search space for alternative paths. This explains why the curves gets flat for the multi-UAVs case after inspecting a certain number of critical loads. Finally, we note that the flying time savings of the multi-UAVs cases are due to the simultaneous inspection of each UAV in its own flying zone; however, optimising the starting flying origin of each UAV is out of scope of this paper.

[IMAGE OMITTED. SEE PDF]

Finally, we compare the computational complexity of our proposed approach with the works that design UAV paths for power inspection. In ref. [14], the computational time for the optimal path is linear with the number of sampled points representing the structure of the inspection target. However, the number of sample points can be large depending on the voxel size. In ref. [16], the computational time for the optimal path using a ground vehicle and a UAV grows exponentially from the small-case to the medium-case and the large-case, which correspond to different scales of road networks and power lines segments. In ref. [17], the solution space for the human-UAV scheduling to inspect faults in transmission networks increases exponentially with increasing network size. In ref. [18], the two-phase framework for efficient power damage assessment required 1.82 × 10⁸ iterations for convergence. The computational cost for generating trajectories in ref. [39] increases exponentially with the number of waypoints. In ref. [40], as the criticality coverage requirement increases, the time required to solve the model also increases. This is because a larger coverage requirement implies a larger area that needs to be covered, resulting in longer execution times. Additionally, when a larger number of UAVs is employed for surveillance, the size of the model expands accordingly. Consequently, solving a larger model typically demands significantly more time, often increasing exponentially. Furthermore, the execution time tends to grow rapidly as the surveillance period lengthens. The mentioned works consume significant computational resources to obtain their optimal UAVs flight paths, while our approach has a low computational complexity, which we showed in Section 3.5 that it increases linearithmically with the number of clusters and power grid size.

CONCLUSIONS

In this paper, we have optimised the multi-UAVs flying paths over the critical loads such that the total inspection time is minimised. First, to account for multiple UAVs, we partitioned the power grid into multiple clusters, each corresponding to the flying zone of a single UAV. Then, we formulated the optimisation problem, which i) gives high priority to critical loads for power delivery and connectivity, and ii) considers the recharging of the UAVs. Because of the NP-complexity of the problem, we proposed a two-stage low-complexity efficient framework, where in the first stage, the framework provides a solution that determines the next best set of critical load(s) to visit and their corresponding planned paths, and in the second stage, it provides the actual paths to the determined critical load(s). We have shown the planned paths, the navigation paths, and the total flying time in the case of a single UAV and multiple UAVs. Furthermore, we have shown the importance of including the UAV recharging in the path optimisation, where we have shown that when no recharging is considered, 31.58% of the nodes were not inspected. This means that our proposed framework was able to reach all of the critical loads due to taking into account the recharging aspect of the UAV, unlike other works that failed to complete the planned paths due to running out of battery.

For future research, the locations of multiple recharging points and the start flying locations of each UAV can be jointly optimised to minimise the inspection time. Moreover, the flying coordination of multiple UAVs in a single zone can be considered to further minimise the inspection time of critical loads. Finally, the complexity of the flying terrain (e.g. non-flying zones) can be modelled as constraints in the optimisation problem.

AUTHOR CONTRIBUTIONS

Rachad Atat: Investigation; software; validation; visualisation; writing – original draft; writing – review and editing. Mostafa F. Shaaban: Conceptualisation; formal analysis; methodology; resources; supervision; validation. Muhammad Ismail: Conceptualisation; formal analysis; methodology; resources; supervision; writing – review and editing. Erchin Serpedin: Project administration; resources; supervision; visualisation; writing – review and editing.

ACKNOWLEDGEMENTS

This publication was made possible by NPRP grant # NPRP12S-0221-190127 from the Qatar National Research Fund (a member of Qatar Foundation). The statements made herein are solely the responsibility of the authors.

CONFLICT OF INTEREST STATEMENT

The authors declare no conflicts of interest.

DATA AVAILABILITY STATEMENT

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

Fan, L., et al.: Fault identification technology for overhead transmission lines. In: 2018 3rd International Conference on Smart City and Systems Engineering (ICSCSE), pp. 443–447. IEEE (2018)

Hines, P., Apt, J., Talukdar, S.: Trends in the history of large blackouts in the United States. In: 2008 IEEE Power and Energy Society General Meeting ‐ Conversion and Delivery of Electrical Energy in the 21st Century, pp. 1–8 (2008)

PowerLine, P.L. (ed.) Finding Faults ‐ Testing Transmission Lines and Cables for a Robust Power System (2019). [posted April 2019]. https://powerline.net.in/2019/04/28/finding‐faults/

Yang, S., et al.: Failure probability estimation of overhead transmission lines considering the spatial and temporal variation in severe weather. J. Modern Power Syst. Clean Ener. 7(1), 131–138 (2019). [DOI: https://dx.doi.org/10.1007/s40565-017-0370-4]. Accessed: 23 May 2023

vom Bögel, G., et al.: Drones for inspection of overhead power lines with recharge function. In: 2020 23rd Euromicro Conference on Digital System Design (DSD), pp. 497–502 (2020)