{'fraction_non_alphanumeric': 0.03574943895428954, 'fraction_numerical': 0.008622386708138115, 'mean_word_length': 4.537388271201221, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimized Path Planning for Inspection by Unmanned Aerial Vehicles Swarm with Energy Constraints

Autonomous inspection of large geographical areas is a central requirement for efficient hazard detection and disaster management in future cyber-physical systems such as smart cities. In this regard, exploiting unmanned aerial vehicle (UAV) swarms is a promising solution to inspect vast areas efficiently and with low cost. In fact, UAVs can easily fly and reach inspection points, record surveillance data, and send this information to a wireless base station (BS). Nonetheless, in many cases, such as operations at remote areas, the UAVs cannot be guided directly by the BS in real-time to find their path. Moreover, another key challenge of inspection by UAVs is the limited battery capacity. Thus, realizing the vision of autonomous inspection via UAVs requires energy-efficient path planning that takes into account the energy constraint of each individual UAV. In this paper, a novel path planning algorithm is proposed for performing energy-efficient inspection, under stringent energy availability constraints for each UAV. The developed framework takes into account all aspects of energy consumption for a UAV swarm during the inspection operations, including energy required for flying, hovering, and data transmission. It is shown that the proposed algorithm can address the path planning problem efficiently in polynomial time. Simulation results show that the proposed algorithm can yield substantial performance gains in terms of minimizing the overall inspection time and energy. Moreover, the results provide guidelines to determine parameters such as the number of required UAVs and amount of energy, while designing an autonomous inspection system.


I. INTRODUCTION
Autonomous inspection of large geographical areas is a key requirement to increase safety and optimize the operation of future cyber-physical systems, such as smart cities, smart farms [1], and smart oil fields [2]. In smart farms, for example, there is a need to inspect large farm lands for signs of pest attacks and to spray pesticide locally over vulnerable regions. Meanwhile, smart oil fields require constant monitoring of the fields for detecting signs of oil spills. Another prominent application of autonomous inspection is in post-disaster management, after natural calamities like hurricanes or floods, to perform search-and-rescue operations.
In this regard, inspection by unmanned aerial vehicles (UAVs) [3] is seen as an attractive solution due to the following reasons: 1) UAVs can fly and bypass obstacles which can result in reducing the inspection time; 2) UAVs are relatively cheaper than dispatching human personnel; and 3) UAVs can easily operate in adverse location that can be dangerous to human workers. For instance, a byproduct of oil extraction is Hydrogen Sulphide (H2S), a colorless and odorless toxic gas that makes oil spill inspection challenging. In such scenarios, a group of UAVs, also known as a UAV swarm, can perform coordinated inspection and manage the inspection tasks more efficiently with a low cost and within a limited time.
Nonetheless, several challenges must be addressed to realize practical autonomous inspection by a UAV swarm. First, each UAV has a limited battery capacity that can support a limited flight time. Thus, UAVs must work collaboratively to inspect a large geographical area. Second, a UAV swarm may include heterogeneous types of UAVs with different flying capabilities and energy efficiency. Third, in many scenarios, UAVs cannot be fully controlled by a wireless base station (BS) to find their path, e.g., in post-disaster situations where the communication infrastructure is damaged. Fourth, as the UAV's distance from the BS increases, more transmission power is required by the UAV to maintain a minimum data transmission rate. Finally, in most applications, the inspection must be performed in a limited time. For example, in oil spill detection, a few minutes saving in the inspection time can prevent drastic oil spill incidents. Therefore, reaping the full benefits of UAV swarms for autonomous inspection mandates efficient path planning for each UAV to minimize the overall energy consumption, while accounting for the limited energy of each UAV.
Recently, several works have been proposed in the literature to address path planning for autonomous inspection by a UAV swarm [4]- [10]. The authors in [4] propose an age-optimal trajectory planning for UAVs to collect data from ground sensor nodes. In [5], a framework is developed to exploit UAVs, serving as relay nodes, to minimize the peak ageof-information for a pair of nodes in an Internet-of-Things (IoT) network. The authors in [6] find an energy-efficient path planning scheme for a fixed-wing UAV that communicates with a ground user. Moreover, the work in [7] studies an energy-efficient cooperative relaying by a set of UAVs, while considering circular flight trajectories. Meanwhile, [8] proposes a scheme to jointly optimizing the UAV's trajectory and transmit power allocation. The work in [9] presents a tutorial on the applications of UAVs in wireless communications and studies fundamental tradeoffs in UAV-enabled wireless networks. With regard to optimizing UAV deployments for inspection applications, [10] presents a path planning scheme for the inspection of photovoltaic farms by a UAV swarm.
Although interesting, the body of work in [4], [5], [7]- [9] mainly focuses on communications aspects of UAVs, without considering specific constraints that affect inspection operations, such as the impact of UAV's weight, energy requirements for hovering, and flight conditions. Moreover, some of the existing works consider path planning for specific scenarios, such as the works in [6] and [7], that solely focus on circular trajectory for the UAVs. In addition, [10] does not consider communications constraints such as minimum required data rate. Meanwhile, several works in the literature, such as [4], [5], [7] and [8], primarily focus on minimizing the time that a wireless user is visited by the UAV swarm. While this metric is important in sensor networks and IoT, for inspection operations, energy-efficient path planning is more critical. Additionally, missing from the prior art, there is a need for performance analysis to determine parameters such as the number of required UAVs and energy requirements for inspection operations by a UAV swarm.
The main contribution of this work is a novel path planning algorithm to minimize the overall energy consumption for inspection by a UAV swarm, while accounting for the heterogeneous features of UAVs and their unique energy constraints. In particular, we first propose an energy consumption model that jointly captures the required energy for flying, hovering, and transmission of recorded inspection data by a UAV to the wireless BS. To solve the autonomous inspection problem, we model the area as an undirected, weighted graph with critical inspection points as the vertices of the graph and the required energy for monitoring an inspection point as the weight of the edge. Using the graph-based model, we develop a novel path planning algorithm that exploits the analogies between autonomous inspection and the K-traveling repairmen problem [11], while considering the limited energy budget of each UAV. In particular, the proposed algorithm jointly optimizes the trajectory of all energy-constrained UAVs in a swarm, in order to minimize the overall average inspection energy. Simulation results show that the proposed algorithm outperforms the distance-based path planning, both in terms of required time and energy for inspection of an area. The results also shed light on design and performance analysis of the autonomous inspection by a UAV swarm, in terms of the number of required UAVs, average inspection time, and energy consumption.
The rest of paper is organized as follows. Section II presents the system model and problem formulation. Section III presents the proposed solution. Simulation results are provided in Section IV. Section V concludes the paper.

II. SYSTEM MODEL
Consider a swarm of K heterogeneous UAVs -with different energy efficiency and battery size -in a set K that are used to perform autonomous inspection of a square area. Fig. 1 shows an example scenario of autonomous inspection by a UAV swarm. A wireless BS, located at the origin x o = (0, 0) ∈ R 2 , also serves as the UAVs' base where the UAVs start their travel. Each UAV k ∈ K is constrained with an energy budget E k . In addition, let N be the set of N inspection points that must be visited by at least one UAV during a time window, determined by the actual inspection application. For example, for post-disaster rescue operations,

Remaining Energy
Fire Incident the inspection time may not exceed few minutes. Next, we find the energy consumption of each UAV as a function of different parameters, such as the location, energy efficiency, and traversed distance. Without loss of generality, we focus on quadrotor UAVs, while other types of UAVs can also be taken into account. Energy consumption for monitoring of an inspection point by a UAV includes three components: 1) Flight energy: the required energy to fly to the point of interest from another location; 2) Transmission energy: the required energy to transmit the recorded data (photo or video) from the inspection point to the BS; and 3) Hovering energy: the energy consumption for remaining still on the air during the time that takes for a UAV to record and transmit a data. Next, we characterize each energy consumption component.

A. Flying and Hovering Energy Consumption
The energy consumption by a flying UAV is mainly spent to overcome the gravity for staying in the air, as well as drag forces due to wind and forward motions. Building on the model in [12], the minimum power with forward motion for a UAV is given by wherev is the induced velocity required for a given thrust T , v is the average ground speed of the UAV, and β denotes the pitch angle. For a UAV with mass m, including the mass of the UAV body and battery, the required thrust T is: where g is the gravitational constant and f d is the drag force that depends on the air speed, density of air ρ, and the drag coefficient. Given a thrust T , the induced velocity can be calculated by solving the following nonlinear equation [12]: where r and q represent, respectively, the diameter and number of UAV rotors. The theoretical power consumption in (1) can be used to find the actual power consumption by a UAV k ∈ K as: where η k is the power efficiency of the UAV k, known empirically. With that in mind, the total flying energy that an arbitrary UAV k consumes to traverse distance d is: Furthermore, the actual power consumption for hovering of UAV k is [12]: where p min h is the theoretical minimum power for hovering.

B. Transmission Energy Consumption
The energy consumption for transmission of recorded data from the inspection point cannot be ignored in many cases where: 1) The distance between the UAV and the BS is large; and 2) The size of the recorded content is large (such as highdefinition videos). Considering the inspection of a point at the path loss of the wireless link in dB is given by: where L 0 is the path loss at a reference distance, α is the path loss exponent, and ξ represents the shadowing effect in dB scale. Using (7), we can find the achievable data rate of the uplink between a UAV k and the BS as follows 1 : where w k , p t (k), and N 0 denote, respectively, the bandwidth, the transmit power of UAV, and the noise power spectral density. In (8), orthogonal bandwidth allocation is considered across UAVs, thus, there is no interference between simultaneous UAV transmissions. To find the transmission energy consumption, let R th be the minimum required uplink data rate for successful transmission of the recorded content. From (8) and subject to the data rate requirement R th , one can easily find the minimum required transmit power p min t (k) for a UAV k. Meanwhile, the energy consumption for transmission of a data packet with size B bits will be: where τ is the over-the-air transmission latency. From (5)- (9), we can conclude that the overall energy consumption by a UAV k ∈ K to fly from the base, located at n 0 , to inspect a destination point n ∈ N is: where n shows the inspection point visited immediately before n. In (10), d is the distance between points n and n and p min t (k) depends on the location of inspection point n. In 1 Although we consider log-distance path loss channel model, small-scale fading can also be easily accommodated in (8). fact, given that E total k (n 0 ) = 0, (10) allows to recursively find the overall inspection energy consumption for any arbitrary point.

C. Problem Formulation
To study the path planning problem, we model the inspection area as an undirected, weighted graph G k (N , E k ), corresponding to the UAV k, where the vertices are inspection points and the weight of each edge between points (n , n) is E total k (n) − E total k (n ) and can be found from (10). The goal here is to find the best trajectory for each UAV across the inspection points (i.e., path planning) in order to minimize the overall inspection time. The union of these trajectories must cover all the inspection points in the set N . Prior to formulating the problem, we use the following definitions: Definition 1. The trajectory of a UAV k is defined as a tree T k , inside the graph G k (N , E), with the root starting at the location of the BS, n 0 .
The main reason to define each UAV's trajectory as a tree is to avoid cycles within the inspection path. Associated with each trajectory, we can define a cost in terms of energy consumption as follows: Definition 2. The cost of a trajectory that visits inspection points T = {n 0 , n 1 , n 2 , · · · , n j }, for UAV k is defined as the total energy required to inspect the vertices of T . That is, Even though other energy cost functions can be defined here, the advantage of the cost function in (11) is to yield a unique cost for each tree, irrespective of the order that UAV may visit vertices. With this in mind, we aim to find K trajectories T k , for k = 1, 2, · · · , K, that minimize the overall inspection energy consumption. That is, s.t., where constraint (13) ensures that all inspection points are visited. Particularly, (13) implies that the trajectories of UAVs are interdependent, thus, path planning must be done jointly for all UAVs in the swarm. Constraint (14) indicates that trajectories of UAVs do not overlap, except at the starting point n 0 . In addition, (15) ensures that the total energy consumption by a UAV k does not exceed the energy budget E th (k). Prior to solving this problem, we make the following observation with regard to the complexity of the problem: Proposition 1. The proposed path planning problem in (12)-(15) is NP-hard and cannot be solved optimally within polynomial time.
Step1: Find the MST for i vertices, using Prim algorithm. This yield an approximation for the i-MST problem. Denote the MST as Y (i). Step2: Proof. To show this, we note that if constraint (15) is relaxed, i.e., E th (k) → ∞, for all k ∈ K, then the proposed problem will be analogous to the K-traveling repairmen problem which is known to be NP-hard [11]. Thus, with finite energy budget, the proposed problem is reducible to the K-traveling repairmen problem, and thus, it is also NP-hard.
Here, we note that classic solutions, such as Dijkstra's method, for solving the traveling salesman problem cannot be used to solve (12)-(15), as these approaches consider only one agent (UAV) and in addition, cannot capture constrains in (15). With this in mind, next, we will propose an efficient path planning algorithm that aims to minimize the overall energy consumption, while taking into account the energy constraint for each UAV.
III. PROPOSED PATH PLANNING ALGORITHM Prior to developing an efficient approximation algorithm for the proposed problem in (12)-(15), lets consider the following simple scenario which we will use as a subroutine for our algorithm.
Assume that there is only one UAV k . Given the graph G k (N , E k ), and starting the trajectory from n 0 , we aim to find the least expensive tree T k (cost is calculated from (11)) that has exactly j vertices. This problem is known as jminimum spanning tree (j-MST) which is also NP-hard [11]. Although approximation algorithms are available to find j-MST efficiently, we need to modify this problem to accommodate the limited energy budget of the UAV (as presented in (15)). In this regard, we consider the subroutine algorithm presented in Table. I, which is originally proposed in [11] and allows to convert the cardinality constraint of covering exactly j vertices into an energy budget constraint. From the definition of MST, we can immediately conclude the following: Remark 1. If there exists a tree of cost E th (k) that spans i vertices, the algorithm in Table I always returns a tree with a cost less than λE th (k) that covers i vertices.
Using the algorithm adopted in Table I, we propose a new algorithm in Table II that yields an efficient solution for the path planning problem of a UAV swarm with energy constraints. The proposed algorithm proceeds as follows. Initially, the algorithm sorts all UAVs with respect to their available energy E th in an ascending order. Starting from the minimum energy E 0 , at each round, the algorithm aims to cover all  (N , E k ), Eth(k), for all k = 1, 2, · · · , K, ∆E.
Initialize: Let T k = ∅, for all k = 1, 2, · · · , K, E0 = ∆E. Sort the UAVs, based on Eth(k), in ascending order in a list K. LetN = ∅. whileÑ = {n0} dõ N ← N Step1: Remove vertices inN fromÑ . for k = 1 to |K| do Step2: Let k be the index of k -th UAV from the sorted listK. Using the algorithm in Table. I, find the tree T k (Ei) in G k (Ñ , E). Step3 Add vertices of T k (Ei) to the setN . Remove k from the listK. Return T k . end Step5: Remove the vertices of T k (Ei), except n0, fromÑ . end Ei+1 ← Ei + ∆E end Output: T k , for k = 1, 2, · · · , K. inspection points in N by finding K trees. If such set of trees do no exist for the given energy constraint, in the next round, the energy is increased by ∆E. Given a certain energy budget E i at round i, in step 2, the algorithm uses the subroutine in Table I to find T k (E i ). In step 3, the algorithm tentatively assigns T k (E i ) as the path for the UAV k. If the further increase in the energy budget E i exceeds the available energy of the UAV E th (k), the algorithm returns T k in step 4 and removes the UAV k and the subset of assigned vertices from the graph. Otherwise, in step 5, the vertices of T k (E i ) are tentatively removed fromÑ . Table II converges  in polynomial time. Proof. Lets consider E th (k) = ∞, for all UAVs. Clearly, this case provides an upper bound for the number of iterations in our algorithm, since with infinite energy, the condition in step 4 is never satisfied and no UAV is permanently removed from the algorithm. In this case, given that at each round of the algorithm in Table II the energy budget increases (equivalent to increasing j in the j-MST), the proposed algorithm with converge after maximum N iterations. Moreover, within each round of the proposed algorithm, there are K recalls of the subroutine algorithm in Table I. Meanwhile, we note that this algorithm solves the j-MST problem and runs in polynomial time. Therefore, the algorithm is guaranteed to converge in polynomial time.

IV. SIMULATION RESULTS
We consider an inspection area of size 200 × 200 meters with the BS located at x 0 = (0, 0) and inspection points are distributed uniformly and randomly across the inspection area. Simulation parameters and their description are summarized in Table III. The statistical results are averaged over a large number of simulation runs.  We compare the performance of our proposed approach with a heuristic path planning algorithm, called distance-based trajectory, in which each UAV starts from a random point and at each step, moves to its nearest inspection point in the graph. This approach is analogous to the "nearest neighbor algorithm" for solving the traveling salesman problem. In fact, the baseline algorithm does not incorporate the energy constraints of the UAVs while performing the path planning. In addition to the inspection energy consumption, we consider the inspection time, as another important performance metric, which is defined as follows: Given paths T k for all UAVs k = 1, 2, · · · , K, the inspection time of an area is the overall time that takes for all inspection points to be visited by at least one UAV for the first time. Figure 2 compares the total energy consumption of the UAV swarm for the proposed approach with the baseline algorithm, for N = 100 inspection points. With no energy constraint, the results in Fig. 2 show the merit of exploiting a UAV swarm. That is, as the size of swarm increases, the average total energy consumption decreases. Moreover, it is clear that the proposed algorithm substantially reduces the energy consumptions, by up to 45% for a swarm of K = 4 UAVs, compared with the baseline approach. Clearly, the performance gap decreases, as the number of UAVs increases. Figure 3 shows the overall average inspection time for the proposed algorithm, compared with the baseline approach, versus the number of UAVs and for different number of inspection points. Fig. 3 shows that as more UAVs become available to perform inspection, the required time to visit all the inspection points decreases. We note that the rate of decay for the inspection time is faster in the proposed algorithm. Moreover, the proposed approach yields substantial performance gains compared with the distance-based trajectory. For example, for a UAV swarm with K = 12 UAVs, there are 55% and 47% reduction in inspection time, respectively, for an area with N = 100 and N = 200 inspection points. This performance gain is due to the fact that the proposed approach accounts for the individual energy constraint of each UAV. As we show in Fig. 4, flying energy constitutes substantial portion of energy consumption. Hence, by minimizing the energy consumption, the proposed approach indirectly minimizes the traversed distance, and thus, the flight time for all UAVs. Such time savings are critical in inspection operations with delay constraints, such as in post-disaster management. Figures 4 and 5 compare the average energy consumption of the UAV swarm, respectively, for flying and for hovering plus data transmission, for both approaches. From the results in Figs. 4 and 5, we can observe that the required energy for flying (i.e., when UAV is mobile) dominates the other energy metrics for hovering and data transmission (i.e., when UAV is static). Comparing the performance of both approaches, we can observe that the flying energy consumption is much higher for the baseline approach. Nonetheless, as shown in Fig. 5, the performance gap is not significant when considering the energy consumption for hovering and data transmission. The main reason is that hovering energy consumption is not highly dependent on the path planning. Moreover, the energy required for data transmissions constitutes small portion of the total energy consumption. Figure 6 shows the cumulative distribution function (CDF) of the inspection time for N = 100 and N = 200 points and with K = 20 UAVs. This result can capture the reliability of the proposed scheme to perform inspection operation in scenarios with time constraints [13]. For example with a target inspection time of 500 seconds and N = 100 points, Fig. 6 shows that the proposed algorithm can meet this requirement with probability 82% while there is only 64% chance for the baseline approach to satisfy the time constraint. Similarly, for N = 200 and the target inspection time of 900 seconds, the chance of meeting this requirement is 80% in our approach, whereas 70% for the distance-based algorithm.    Finally, the average inspection time is shown in Fig. 7, versus the number of inspection points N , with K = 10 UAVs. Fig. 7 shows that as there are more inspection points (e.g., in post-disaster scenarios), the average inspection time naturally increases with a fixed number of UAVs. In fact, the results in Fig. 7 show that the proposed scheme exploits the UAV swarm more efficiently. For example, for N = 100, the performance gap between the proposed path planning algorithm and the baseline scheme is 48%. V. CONCLUSIONS In this paper, we have proposed a novel path planning algorithm that minimizes the overall energy consumption by a UAV swarm to autonomously inspect a geographical area. The proposed framework has taken into account different metrics that impact the energy consumption, including flying, hovering, and data transmission by each UAV. We have shown that the proposed algorithm solves the path planning problem in polynomial time, while taking into account the individual energy constraints of the UAVs. Simulation results have shown that the proposed approach substantially outperforms the baseline solution with distance-based path planning, both in terms of required inspection energy and time.