# On the 3D Track Planning for Electric Power Inspection Based on the Improved Ant Colony Optimization andA∗ Algorithm

Authors: Zheng Huang; Xuefeng Zhai; Hongxing Wang; Hang Zhou; Hongwei Zhao; Mingduan Feng
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

At present, multirotor drones are restricted by the control accuracy and cannot position accurately according to the accuracy of point cloud data. Also, track planning in three-dimensional space is much more complicated than that in two-dimensional space, which means that existing track planning methods cannot achieve fast planning. Meanwhile, most existing researches were implemented in quasi-three-dimensional space with the shortest route length as the objective function and omitted environmental impacts. To overcome these, this paper uses the grid method to segment point cloud data of the flying space via ArcGIS software according to the drone’s controlling accuracy. It also extracts the grid coordinate information and maps it to a three-dimensional matrix to build the model accurately. This paper sets the minimal energy consumption as the objective function and builds a track planning model based on the drone’s performance and natural wind constraints. The improved ant colony optimization andA∗ (ACO-A∗) algorithm are utilized to design this algorithm for a faster solution. That is, we use the improved ant colony optimization to quickly find a near-optimal track covering all viewpoints with the minimal energy consumption. The improved A∗ algorithm will be used for local planning for adjacent tracks passing through obstacles. In the designed simulation environment, the simulation results show that, to ensure that the same components are shot, the improved algorithm in this paper can save 62.88% energy compared to that of the Shooting Manual of Drone Inspection Images for Overhead Transmission Lines. Also, it can save 9.33% energy compared to a track with the shortest route length. Besides, the ACO-A∗ algorithm saves 96.6% time than the A∗ algorithm.


---

## Body

## 1. Introduction

China’s power lines are widely distributed, and most of them are built-in hostile environments. These power lines and towers are exposed to the external environment for a long time. Their performance is influenced by complex weather and their characteristics, which can cause significant safety threats to the transmission network [1]. Multirotor drones are more and more popular because they have low cost, high flexibility, and high controllability, in contrast to low efficiency and poor reliability of traditionally manned inspections [2]. Existing multirotor drones’ power pole tower inspections are mainly operated by people. The pilots control the multirotor drone based on their intuition and experiences, but there are plenty of shortcomings of manned inspections. Firstly, due to the limits of human vision, it is difficult to visually measure the distance between the drone and the power pole tower or the transmission line, which poses operational risks. Secondly, the manually operated track route has strong randomness, and it is not optimal. It took extra time to find the shooting point. As a result, the inspection efficiency is decreased.To overcome this, people have proposed an automatic inspection method for multirotor drones. Many researchers have done a lot of research on 3D track planning. Literature [3] simulated underwater obstacles into the shape of a mountain peak and proposed an improved wolf pack algorithm to plan the track. Literature [4] divides irregular obstacles into four categories and designs obstacle avoidance rules accordingly. Literature [5] proposed MCFO to solve the 3D track planning between two points and verified the feasibility of the track through simulated obstacles. Literature [6] proposes a method for solving the optimal track of two-point energy consumption based on a three-dimensional map with fewer obstacles and smaller course changes. Literature [7] proposed an improved ant colony optimization for generating the 3D track solution of an autonomous underwater vehicle (AUV). Studies [8, 9] use differential evolution (DE) and predator-prey optimization to implement three-dimensional track planning. Studies [10, 11] used ant colony optimization to solve the track planning problem. Literature [12] proposed ACO-A∗ algorithm to implement the three-dimensional track planning of AUV. Literature [13] carried out a simulation test of the whole process of the rotorcraft drone flight and recorded the real-time voltage (current) and power. Energy consumption can be calculated by E=∫0tp. By fitting the simulated multiple sets of data, the functions which show the relationship between energy consumption and variables can be obtained. Literature [14] proposed the track planning problem of rotor drones based on the genetic algorithm and ant colony optimization. This paper collects data by making rotorcraft carrying IoT (Internet of Things) sensors onboard, considering factors including performance constraints, energy consumption, time, and risk costs of the rotor drone. By optimizing the genetic algorithm, each chromosome is encoded as a complete piece of information, and cross-mutation operations are performed on the collection points to find the optimal sequence. Ant colony optimization is applied to gather the track information of neighboring points. Literature [15] built a resource allocation model based on multisorties multirotor drone delivery. Dorling et al. derived a multirotor drone energy consumption model through mathematical derivation and found that the energy consumption changes in a linear trend with the change in payload and has been verified through experiments. Hebecker et al. proposed a model-based local track planning method, which can detect the surrounding static obstacles via the environment-aware sensors established by the flying robot and plan a collision-free track accordingly [16]. Chen and other researchers from George Mason University, U.S., proposed a track planning method based on tangent-plus Lyapunov vector field [17]. Acar et al. from Carnegie Mellon University followed the concept of regional unit segmentation and proposed a sensor-based coverage track planning method [18]. Literature [19] introduced a reliable online track planning method that allows multirotor drones to safely fly in a GPS-constrained and obstacle-surrounding environment with limited power onboard. Literature [20] proposed a method based on Lyapunov’s guided vector field (LGVF) and improved interference fluid dynamic system (IIFDS) to avoid the obstacle in multirotor drone 3D track planning.However, problems still exist for the current practice of multirotor drones and related track planning algorithms. Firstly, the modeling of obstacles is generated by geometric simulation. If the power tower is modeled in this way, the pictures taken by the drone will be blurred or some original components will not be captured. Meanwhile, the hovering accuracy of the multirotor drone is lower than that of the 3D point cloud, and it cannot position accurately according to the accuracy of the point clouds. Then, the track planning in the 3D space is more complicated compared to that in two-dimensional space, and existing track planning methods cannot get fast solutions. Last but not least, the existing multirotor drone track planning method cannot effectively integrate the safety constraints of the tower and the performance of the drone with the natural wind constraints to achieve the optimal track planning.To overcome those mentioned above, this paper proposes a three-dimensional track planning method for multirotor drone power inspection based on improved ACO-A∗ algorithm. This method will achieve the following effects.Firstly, it completes the raster modeling of 3D point cloud data based on the drone hovering accuracy. It is to solve the problem of refined modeling of power pole towers and existing multirotor drones that cannot position and fly accurately according to point cloud accuracy. Secondly, it optimizes the ACO-A∗ algorithm. It searches the pretracking route through the improved ant colony optimization and then uses the A∗ algorithm for local track planning. Also, it meets the need for real-time planning of electric power inspection under different wind direction conditions at different times. Lastly, it builds the model based on the objective of the minimal energy consumption, with drone performance constraints and natural wind constraints. It can provide a safe inspection track with the lowest energy consumption for the multirotor drone inspection, corresponding to different wind direction information with the constraints of the tower, drone performance, and natural wind.The rest of this paper is organized as follows: in Section2, the minimal energy consumption model is established. Also, the performance constraints of multirotor drones and the impact of natural wind on energy consumption are analyzed. And the energy consumption calculation formulas for cruising and hovering are given. Section 2.2 is the principle of the algorithm, including the raster modeling of the 3D point cloud data and the improvement of the ACO-A∗ algorithm; Section 3 describes the simulation analysis, and Section 4 is the summary of this paper and the prospect of the future work.


## 2. Model and Methods

### 2.1. Model Building

#### 2.1.1. Objective Function

The flight time of multirotor drones is affected by the natural environment, especially by the wind. The flight time varies greatly in different environments, and the flight time generally ranges from 20 to 45 minutes. Therefore, flight track planning should not be based on the drone flight duration as the track planning standard. Therefore, it is necessary to ensure that each inspection can be completed safely with minimal battery energy consumption in a limited time. Based on this, this paper establishes the objective function of minimal power consumption, which is given as(1)min∑i=1nσi+∑j=1n−1wj,where σi is the energy consumption while hovering and wj is the energy consumption between route segments.


#### 2.1.2. Constraints

(1) Hovering Accuracy (λ). Different models of multirotor drones have different hovering accuracies. The hovering accuracy will influence the value of the grid side length. If the side length is shorter than the hovering accuracy of the drone, the 3D model will be meaningless.(2) Speed Limit (see [21]). The speed limit mainly includes the following aspects: the maximum ascent (descent) speed, the maximum horizontal flight speed, and the maximum tolerable wind speed. Different models of drones have different performance parameters:(2)s.t.v≤Vhmax,v≤Vlmax,v≤Vwmax,where v is the speed of each drone, Vhmax is the maximum indicated airspeed, Vlmax is the maximum horizontal flight speed, and Vwmax is the maximum wind speed.(3) Safety Distance Constraint (s′) (see [22]). The safety distance constraint considers the safety of the drone inspection system, including the safety of the drone’s flight and the safety of the power pole tower. The safety distance is to ensure that the electronic equipment on board is not affected by the electric and magnetic fields of the power tower. It has been found that the safety distances vary greatly depending on voltage levels, which is given as(3)s′=s+λ,where λ is the hovering accuracy and s is the safety distance of the electronic power pole, which is dependent on voltage. The constraints will be illustrated in the form of obstacles.(4) Wind Speed (see [23]). Multirotor drones often need to deal with a variety of complex interferences while executing missions. In the natural environment, the wind is one of the most common factors that have the greatest impact and interference on the state of multirotor drones. Therefore, the energy consumption of the drone’s battery is not only affected by its speed but also by the wind speed. For the hovering and cruising state of the drone, the following analysis is performed:(1)
Hover phaseThe multirotor drone is stable when hovering in the air. When the wind is affected, the drone automatically adjusts the tilt angle through the PID controller to restore the drone to the original stable state. In the end, the adjusted inclination angle and wind direction are collinear, as well as the drone’s speed is equivalent to the wind speed. However, normally, the time for the multirotor drone to adjust the attitude angle of the drone is 3 s [24]. The power consumption of the battery hovering at a certain viewpoint can be calculated as(4)σi=pVW⋅t1,wherepVW is the rated power and t1 is the sum of shooting time and adjusting the time when hovering.(2)
Cruise phaseThe wind speed has an insignificant effect on the yaw angle of the multirotor drone [22]. Therefore, when the multirotor drone is affected by the external wind, it needs to adjust the corresponding pitch and roll angle to ensure that the multirotor drone can fly according to the scheduled route. Meanwhile, each motor needs to adjust the corresponding power to ensure that the drone not only is flying at the set speed but also does not deviate from the scheduled route.The effect of wind on the flying drone can be described by the flight speed triangle, as shown in Figure1, where the ground speed VI is the vector sum of V∞, airspeed, and VW, wind speed. We suppose that the drift angle is zero, which means the airspeed is equivalent to wind speed.Figure 1
Vector illustration of speed triangle.The energy consumption during the cruise phase is composed of two parts for calculation: one part is the energy consumption on the direct flight route of the multirotor drone, and the other part is the energy consumption against the wind. We suppose that the multirotor drone’s wind disturbance during the cruise phase comes from the 2D plane wind. And the value and direction of the wind do not change. At this moment, the vector diagram of ground speed and wind speed is shown in Figure2, where the coordinate origin is the current viewpoint i. The ground speed is set before the drone takes off, so it can be considered as a constant, and the direction is correspondent with the straight line determined by the two viewpoints. The value and direction of the wind speed are measured before the multirotor drone takes off which can also be considered constants.Figure 2
Speed vector diagram of quadrotor drone under wind disturbance.Since the wind that multirotor drone receives at any point comes from the two-dimensional plane, the ground speed is projected onto the planeXIOYI, and the horizontal projection is VI′. VI′ can be calculated by the following equations, where γ is the gradient angle:(5)γ=arccosxj−xi2+yj−yi2xj−xi2+yj−yi2+zj−zi2,(6)VI′=VI⋅cosγ,(7)VI″=VI⋅sinγ.The illustration of projection is shown in Figure3, where χ is the angle between the horizontal projection of ground speed on the plane XIOYI and the x-axis and δ is the wind direction angle measured before inspection, whose range is [0, 2π]. χ and δ are the angles formed with the positive direction of the axis. VI″ is the projection of ground speed in the vertical direction.Figure 3
Two-dimensional plane vector exploded view of ground speed and wind speed.χ can be obtained as follows, where xj and yj are the coordinates of the viewpoint:(8)χ=arctanyjxj.To ensure the constant speed and course of multirotor drone, it is necessary to resist the interference of wind speed, that is, to increase (decrease) the size of the horizontal component of ground speed. In this paper, we referV to updated V1′, which is given as(9)V=V1′−cosδ−χ⋅VW.The energy consumption on a direct flight is the product of power and time. The energy consumption corresponding to airspeed can be obtained according to the performance parameters of the drone. The flight of the drone between two viewpoints can be regarded as uniform motion, and the flying timet2 can be calculated as follows:(10)D=xj−xi2+yj−yi2+zj−zi2,(11)t2=DV1,where D is the distance between neighboring viewpoints.Overall, the energy consumption between the two viewpoints can be obtained by(12)wj=PVW″+PV+PVI″⋅t2,where PVW″ is the energy consumption for resisting crosswind, PV is the energy consumption corresponding to the actual speed level on the direct flight track of the drone, and PVI″ is the energy consumption corresponding to the vertical direction of the actual speed.


### 2.2. Algorithm Principle

#### 2.2.1. 3D Point Cloud Raster Modeling

The accuracy of the traditional high-volume 3D point cloud data is higher than the hovering accuracy of the multirotor drone. Hence, the multirotor drone cannot fly according to the accuracy of the point cloud. Based on ArcGIS software, this paper utilized the grid method to extract the 3D point cloud data and maps them into the 3D matrix. The grid method is to segment the search space into a certain number of grids, and each grid represents a searchable space. The flyable spaces are marked as 0, and unflyable spaces are marked as 1, which is shown in Figure4. The key of the grid method is to set as the length of the side of each square properly. To meet the refined requirements of track planning, the area of each grid should be as small as possible, but the impact of the hovering accuracy of the multirotor drone itself should also be considered. The modeling process of applying the grid method to 3D point cloud data is shown in Figure 5. Then, we load the 3D point cloud data that needs to be processed, use the hovering accuracy of the drone as the grid side length, and use the grid method to divide the loaded point cloud data into different grids. The original point cloud data should be included in the corresponding grids. Among the grids, each grid stores the coordinate information of the corresponding point cloud. Finally, according to the planning requirements, the corresponding coordinate information is extracted, and the obtained data are mapped into a 0-1 grid matrix, as shown in Figure 4.Figure 4
0-1 grid matrix.Figure 5
3D point cloud modeling flowchart.


#### 2.2.2. Ant Colony Optimization andA∗ Algorithm

The inspection of the power pole tower can be simplified as follows: in a three-dimensional environment with obstacles, the drone passes through multiple viewpoints that need to be inspected and finally finds a track with the minimal flight energy consumption. Ant colony optimization [10–12] is a heuristic random search algorithm proposed by simulating the collective patrol behavior of ants in nature. The algorithm is robust and has a strong global ability of searching. When an ant looks for a food source, it will release a pheromone on the track it went along. The ant tends to preferentially choose a track with a higher pheromone concentration until it can find the optimal track from its nest to the food source. The A∗ algorithm [25, 26] combines the characteristics of Dijkstra and BFS algorithms. It considers both the points close to the starting point and the points close to the target point so that it can find the shortest route length between any two points when there are obstacles.In this problem, only utilizingA∗ algorithm or ant colony optimization cannot solve the track planning problem properly. When A∗ algorithm is utilized to solve multiobjective problems, it is very complicated to calculate the heuristic function. Also, in the 3D environment with obstacles, with the expansion of the search range, the accuracy of the ant colony optimization will greatly decrease, and the optimal solution cannot be found. Therefore, based on the advantages of the two algorithms, a track planning algorithm model combining ant colony optimization and A∗ algorithm is designed.(1) Improved Global Ant Colony Optimization Algorithm Based on Consumption. The problem of 3D track planning based on the minimal energy consumption proposed in this paper takes into account the influence of natural wind. Therefore, after measuring the natural wind parameters, the real-time trajectory planning should be carried out quickly to cope with the changes in natural wind. Studies [10–12, 27] verify that the efficiency of ant colony optimization in solving track planning problems is better than other intelligent optimization algorithms. Therefore, in the global planning of viewpoint, this paper adopts ant colony optimization.To further simplify the algorithm and improve efficiency, according to the analysis of the characteristics of the power tower and the viewpoint between the tower, when the viewpoint is on the same side of the power tower, the viewpoint can mostly fly at a straight distance, but when the viewpoint is on both sides of the power tower, pole tower inspection is prohibited to fly from the lower end of the wire, so this paper proposes the following equation:(13)D=xi−xj2+yi−yj2+zi−zj2,i−j≤W,xi−xj2+yi−yj2+zi−zj2+2H−zi−zj,i−j>W,where W is the width of the tower and H is the height of the tower.Aiming at the first stage of power inspection global track planning, the lowest energy consumption is used as the objective function. And the ant colony optimization, genetic algorithm, and particle swarm algorithm are compared, respectively. The algorithms’ convergence effect is shown in Figure6. Through comparison, we can find that the ant colony optimization can find the optimal solution in the minimal number of iterations. It is more in line with the needs of real-time planning of electric power inspection.Figure 6
Algorithm convergence effect diagram.The basic steps of the ant colony optimization are described in detail in the studies [10–12], and this paper makes the following improvements:(1)
Viewpoint selection strategyDifferent from traditional ant colony optimization, the heuristic information is the energy consumption between viewpoints instead of the route length when calculating the probability that thekth ant chooses the next viewpoint j from the current viewpoint i. They can be calculated as follows:(14)pijk=τijα⋅ηijβ∑S∈Jkiτisα⋅ηisβ,ifj∈Jki,0,else,whereηij represents the energy consumption from viewpoint i to viewpoint j, obtained by equations (4)–(12). And Jki represents the set of viewpoints that the ant is allowed to traverse in the next step. Also, α and β are the heuristic factors, where the value range of α is (1, 4) and the value range of β is (3, 5).(2)
Pheromone updateAfter each ant has traversed all the viewpoints, the pheromone is updated as(15)τijn=1−ρτijn−1+Δτij,Δτij=∑k=1mΔτijk,Δτijk=QLk,if the ant passes the edgeij,0,else,Lk=∑j=1n−1wj,where Lk represents all the energy consumption after the kth ant finishing its inspections and wj is the consumption of the jth flight segment. Since the hovering durations at all viewpoints are the same at global planning, there is no need to calculate hovering consumption. τijn represents the pheromone on each track after the nth iteration, ρ (0 < ρ < 1) represents the evaporation coefficient, Δτij represents the increment of pheromone, Δτijk represents the increment of pheromone, while the kth ant is on the edge ij, and Q is a positive constant.(2) ImprovedA∗ Algorithm Based on Consumption. The A∗ algorithm can find the shortest track between any two points in the 3D environment by setting the heuristic function properly. Before applying the A∗ algorithm to solve the track with the constraints of minimal energy consumption between any two points, you need to set the heuristic function reasonably:(16)fn=gn+hn,gn=10∗ws,i,hn=10∗wi,d.In order to shorten the solution time of theA∗ algorithm, when calculating gn and hn, the paper adopts the method of enlargement and rounding and replaces the floating-point numbers with integers. If the distance is directly rounded, the accuracy of the algorithm is lost, which will reduce the efficiency of the algorithm and even fail to find the optimal solution. If the magnification is too high, although the accuracy of the algorithm can be improved, it will increase the solution time of the algorithm. At the cost, we enlarge the distance by 10 times, not only to ensure the accuracy of the algorithm but also to avoid the value being too large and increasing the algorithm solution time. In the equation, fn is the total energy consumption of any two viewpoints, gn is the energy consumption from the starting point to the current point i, and hn is the energy consumption of the current point flying directly to the target point.In order to verify the correctness and effectiveness of the improved algorithm, the following comparative test is performed. That is, the drone is flying at4m/s from point (9, 1, 0) to the destination point (10, 17, 5) with a grid length of 1 m. And in the meantime, the drone is affected by the natural east wind at 2m/s. The track planned by the traditional A∗ algorithm and the improved A∗ algorithm in this paper is shown in Figure 7. The traditional A∗ algorithm chooses to follow the red line in the picture, and the power consumed at this time is 4.998J. However, this track is not optimal when affected by natural wind. The improved A∗ algorithm plans a track with the lowest energy consumption, and the power consumed is 4.950J, which is 0.96% lower than the traditional A∗ algorithm.Figure 7
Comparison of traditionalA∗ algorithms and improved A∗ algorithms.The heuristic probability search method of the ant colony optimization is not easy to focus on the local optimum and easy to find the global optimal solution. Based on that, we can obtain the safety-oriented near-optimal track for power pole tower inspection in 3D space. Then, we use the corresponding algorithm judge whether any obstacle exists in the track of random neighboring viewpoints. If it does, theA∗ algorithm is called for local track planning. The ACO-A∗ algorithm process is shown in Figure 8.Figure 8
Algorithm flowchart of multirotor drone track planning.


## 2.1. Model Building

### 2.1.1. Objective Function

The flight time of multirotor drones is affected by the natural environment, especially by the wind. The flight time varies greatly in different environments, and the flight time generally ranges from 20 to 45 minutes. Therefore, flight track planning should not be based on the drone flight duration as the track planning standard. Therefore, it is necessary to ensure that each inspection can be completed safely with minimal battery energy consumption in a limited time. Based on this, this paper establishes the objective function of minimal power consumption, which is given as(1)min∑i=1nσi+∑j=1n−1wj,where σi is the energy consumption while hovering and wj is the energy consumption between route segments.


### 2.1.2. Constraints

(1) Hovering Accuracy (λ). Different models of multirotor drones have different hovering accuracies. The hovering accuracy will influence the value of the grid side length. If the side length is shorter than the hovering accuracy of the drone, the 3D model will be meaningless.(2) Speed Limit (see [21]). The speed limit mainly includes the following aspects: the maximum ascent (descent) speed, the maximum horizontal flight speed, and the maximum tolerable wind speed. Different models of drones have different performance parameters:(2)s.t.v≤Vhmax,v≤Vlmax,v≤Vwmax,where v is the speed of each drone, Vhmax is the maximum indicated airspeed, Vlmax is the maximum horizontal flight speed, and Vwmax is the maximum wind speed.(3) Safety Distance Constraint (s′) (see [22]). The safety distance constraint considers the safety of the drone inspection system, including the safety of the drone’s flight and the safety of the power pole tower. The safety distance is to ensure that the electronic equipment on board is not affected by the electric and magnetic fields of the power tower. It has been found that the safety distances vary greatly depending on voltage levels, which is given as(3)s′=s+λ,where λ is the hovering accuracy and s is the safety distance of the electronic power pole, which is dependent on voltage. The constraints will be illustrated in the form of obstacles.(4) Wind Speed (see [23]). Multirotor drones often need to deal with a variety of complex interferences while executing missions. In the natural environment, the wind is one of the most common factors that have the greatest impact and interference on the state of multirotor drones. Therefore, the energy consumption of the drone’s battery is not only affected by its speed but also by the wind speed. For the hovering and cruising state of the drone, the following analysis is performed:(1)
Hover phaseThe multirotor drone is stable when hovering in the air. When the wind is affected, the drone automatically adjusts the tilt angle through the PID controller to restore the drone to the original stable state. In the end, the adjusted inclination angle and wind direction are collinear, as well as the drone’s speed is equivalent to the wind speed. However, normally, the time for the multirotor drone to adjust the attitude angle of the drone is 3 s [24]. The power consumption of the battery hovering at a certain viewpoint can be calculated as(4)σi=pVW⋅t1,wherepVW is the rated power and t1 is the sum of shooting time and adjusting the time when hovering.(2)
Cruise phaseThe wind speed has an insignificant effect on the yaw angle of the multirotor drone [22]. Therefore, when the multirotor drone is affected by the external wind, it needs to adjust the corresponding pitch and roll angle to ensure that the multirotor drone can fly according to the scheduled route. Meanwhile, each motor needs to adjust the corresponding power to ensure that the drone not only is flying at the set speed but also does not deviate from the scheduled route.The effect of wind on the flying drone can be described by the flight speed triangle, as shown in Figure1, where the ground speed VI is the vector sum of V∞, airspeed, and VW, wind speed. We suppose that the drift angle is zero, which means the airspeed is equivalent to wind speed.Figure 1
Vector illustration of speed triangle.The energy consumption during the cruise phase is composed of two parts for calculation: one part is the energy consumption on the direct flight route of the multirotor drone, and the other part is the energy consumption against the wind. We suppose that the multirotor drone’s wind disturbance during the cruise phase comes from the 2D plane wind. And the value and direction of the wind do not change. At this moment, the vector diagram of ground speed and wind speed is shown in Figure2, where the coordinate origin is the current viewpoint i. The ground speed is set before the drone takes off, so it can be considered as a constant, and the direction is correspondent with the straight line determined by the two viewpoints. The value and direction of the wind speed are measured before the multirotor drone takes off which can also be considered constants.Figure 2
Speed vector diagram of quadrotor drone under wind disturbance.Since the wind that multirotor drone receives at any point comes from the two-dimensional plane, the ground speed is projected onto the planeXIOYI, and the horizontal projection is VI′. VI′ can be calculated by the following equations, where γ is the gradient angle:(5)γ=arccosxj−xi2+yj−yi2xj−xi2+yj−yi2+zj−zi2,(6)VI′=VI⋅cosγ,(7)VI″=VI⋅sinγ.The illustration of projection is shown in Figure3, where χ is the angle between the horizontal projection of ground speed on the plane XIOYI and the x-axis and δ is the wind direction angle measured before inspection, whose range is [0, 2π]. χ and δ are the angles formed with the positive direction of the axis. VI″ is the projection of ground speed in the vertical direction.Figure 3
Two-dimensional plane vector exploded view of ground speed and wind speed.χ can be obtained as follows, where xj and yj are the coordinates of the viewpoint:(8)χ=arctanyjxj.To ensure the constant speed and course of multirotor drone, it is necessary to resist the interference of wind speed, that is, to increase (decrease) the size of the horizontal component of ground speed. In this paper, we referV to updated V1′, which is given as(9)V=V1′−cosδ−χ⋅VW.The energy consumption on a direct flight is the product of power and time. The energy consumption corresponding to airspeed can be obtained according to the performance parameters of the drone. The flight of the drone between two viewpoints can be regarded as uniform motion, and the flying timet2 can be calculated as follows:(10)D=xj−xi2+yj−yi2+zj−zi2,(11)t2=DV1,where D is the distance between neighboring viewpoints.Overall, the energy consumption between the two viewpoints can be obtained by(12)wj=PVW″+PV+PVI″⋅t2,where PVW″ is the energy consumption for resisting crosswind, PV is the energy consumption corresponding to the actual speed level on the direct flight track of the drone, and PVI″ is the energy consumption corresponding to the vertical direction of the actual speed.


## 2.1.1. Objective Function

The flight time of multirotor drones is affected by the natural environment, especially by the wind. The flight time varies greatly in different environments, and the flight time generally ranges from 20 to 45 minutes. Therefore, flight track planning should not be based on the drone flight duration as the track planning standard. Therefore, it is necessary to ensure that each inspection can be completed safely with minimal battery energy consumption in a limited time. Based on this, this paper establishes the objective function of minimal power consumption, which is given as(1)min∑i=1nσi+∑j=1n−1wj,where σi is the energy consumption while hovering and wj is the energy consumption between route segments.


## 2.1.2. Constraints

(1) Hovering Accuracy (λ). Different models of multirotor drones have different hovering accuracies. The hovering accuracy will influence the value of the grid side length. If the side length is shorter than the hovering accuracy of the drone, the 3D model will be meaningless.(2) Speed Limit (see [21]). The speed limit mainly includes the following aspects: the maximum ascent (descent) speed, the maximum horizontal flight speed, and the maximum tolerable wind speed. Different models of drones have different performance parameters:(2)s.t.v≤Vhmax,v≤Vlmax,v≤Vwmax,where v is the speed of each drone, Vhmax is the maximum indicated airspeed, Vlmax is the maximum horizontal flight speed, and Vwmax is the maximum wind speed.(3) Safety Distance Constraint (s′) (see [22]). The safety distance constraint considers the safety of the drone inspection system, including the safety of the drone’s flight and the safety of the power pole tower. The safety distance is to ensure that the electronic equipment on board is not affected by the electric and magnetic fields of the power tower. It has been found that the safety distances vary greatly depending on voltage levels, which is given as(3)s′=s+λ,where λ is the hovering accuracy and s is the safety distance of the electronic power pole, which is dependent on voltage. The constraints will be illustrated in the form of obstacles.(4) Wind Speed (see [23]). Multirotor drones often need to deal with a variety of complex interferences while executing missions. In the natural environment, the wind is one of the most common factors that have the greatest impact and interference on the state of multirotor drones. Therefore, the energy consumption of the drone’s battery is not only affected by its speed but also by the wind speed. For the hovering and cruising state of the drone, the following analysis is performed:(1)
Hover phaseThe multirotor drone is stable when hovering in the air. When the wind is affected, the drone automatically adjusts the tilt angle through the PID controller to restore the drone to the original stable state. In the end, the adjusted inclination angle and wind direction are collinear, as well as the drone’s speed is equivalent to the wind speed. However, normally, the time for the multirotor drone to adjust the attitude angle of the drone is 3 s [24]. The power consumption of the battery hovering at a certain viewpoint can be calculated as(4)σi=pVW⋅t1,wherepVW is the rated power and t1 is the sum of shooting time and adjusting the time when hovering.(2)
Cruise phaseThe wind speed has an insignificant effect on the yaw angle of the multirotor drone [22]. Therefore, when the multirotor drone is affected by the external wind, it needs to adjust the corresponding pitch and roll angle to ensure that the multirotor drone can fly according to the scheduled route. Meanwhile, each motor needs to adjust the corresponding power to ensure that the drone not only is flying at the set speed but also does not deviate from the scheduled route.The effect of wind on the flying drone can be described by the flight speed triangle, as shown in Figure1, where the ground speed VI is the vector sum of V∞, airspeed, and VW, wind speed. We suppose that the drift angle is zero, which means the airspeed is equivalent to wind speed.Figure 1
Vector illustration of speed triangle.The energy consumption during the cruise phase is composed of two parts for calculation: one part is the energy consumption on the direct flight route of the multirotor drone, and the other part is the energy consumption against the wind. We suppose that the multirotor drone’s wind disturbance during the cruise phase comes from the 2D plane wind. And the value and direction of the wind do not change. At this moment, the vector diagram of ground speed and wind speed is shown in Figure2, where the coordinate origin is the current viewpoint i. The ground speed is set before the drone takes off, so it can be considered as a constant, and the direction is correspondent with the straight line determined by the two viewpoints. The value and direction of the wind speed are measured before the multirotor drone takes off which can also be considered constants.Figure 2
Speed vector diagram of quadrotor drone under wind disturbance.Since the wind that multirotor drone receives at any point comes from the two-dimensional plane, the ground speed is projected onto the planeXIOYI, and the horizontal projection is VI′. VI′ can be calculated by the following equations, where γ is the gradient angle:(5)γ=arccosxj−xi2+yj−yi2xj−xi2+yj−yi2+zj−zi2,(6)VI′=VI⋅cosγ,(7)VI″=VI⋅sinγ.The illustration of projection is shown in Figure3, where χ is the angle between the horizontal projection of ground speed on the plane XIOYI and the x-axis and δ is the wind direction angle measured before inspection, whose range is [0, 2π]. χ and δ are the angles formed with the positive direction of the axis. VI″ is the projection of ground speed in the vertical direction.Figure 3
Two-dimensional plane vector exploded view of ground speed and wind speed.χ can be obtained as follows, where xj and yj are the coordinates of the viewpoint:(8)χ=arctanyjxj.To ensure the constant speed and course of multirotor drone, it is necessary to resist the interference of wind speed, that is, to increase (decrease) the size of the horizontal component of ground speed. In this paper, we referV to updated V1′, which is given as(9)V=V1′−cosδ−χ⋅VW.The energy consumption on a direct flight is the product of power and time. The energy consumption corresponding to airspeed can be obtained according to the performance parameters of the drone. The flight of the drone between two viewpoints can be regarded as uniform motion, and the flying timet2 can be calculated as follows:(10)D=xj−xi2+yj−yi2+zj−zi2,(11)t2=DV1,where D is the distance between neighboring viewpoints.Overall, the energy consumption between the two viewpoints can be obtained by(12)wj=PVW″+PV+PVI″⋅t2,where PVW″ is the energy consumption for resisting crosswind, PV is the energy consumption corresponding to the actual speed level on the direct flight track of the drone, and PVI″ is the energy consumption corresponding to the vertical direction of the actual speed.


## 2.2. Algorithm Principle

### 2.2.1. 3D Point Cloud Raster Modeling

The accuracy of the traditional high-volume 3D point cloud data is higher than the hovering accuracy of the multirotor drone. Hence, the multirotor drone cannot fly according to the accuracy of the point cloud. Based on ArcGIS software, this paper utilized the grid method to extract the 3D point cloud data and maps them into the 3D matrix. The grid method is to segment the search space into a certain number of grids, and each grid represents a searchable space. The flyable spaces are marked as 0, and unflyable spaces are marked as 1, which is shown in Figure4. The key of the grid method is to set as the length of the side of each square properly. To meet the refined requirements of track planning, the area of each grid should be as small as possible, but the impact of the hovering accuracy of the multirotor drone itself should also be considered. The modeling process of applying the grid method to 3D point cloud data is shown in Figure 5. Then, we load the 3D point cloud data that needs to be processed, use the hovering accuracy of the drone as the grid side length, and use the grid method to divide the loaded point cloud data into different grids. The original point cloud data should be included in the corresponding grids. Among the grids, each grid stores the coordinate information of the corresponding point cloud. Finally, according to the planning requirements, the corresponding coordinate information is extracted, and the obtained data are mapped into a 0-1 grid matrix, as shown in Figure 4.Figure 4
0-1 grid matrix.Figure 5
3D point cloud modeling flowchart.


### 2.2.2. Ant Colony Optimization andA∗ Algorithm

The inspection of the power pole tower can be simplified as follows: in a three-dimensional environment with obstacles, the drone passes through multiple viewpoints that need to be inspected and finally finds a track with the minimal flight energy consumption. Ant colony optimization [10–12] is a heuristic random search algorithm proposed by simulating the collective patrol behavior of ants in nature. The algorithm is robust and has a strong global ability of searching. When an ant looks for a food source, it will release a pheromone on the track it went along. The ant tends to preferentially choose a track with a higher pheromone concentration until it can find the optimal track from its nest to the food source. The A∗ algorithm [25, 26] combines the characteristics of Dijkstra and BFS algorithms. It considers both the points close to the starting point and the points close to the target point so that it can find the shortest route length between any two points when there are obstacles.In this problem, only utilizingA∗ algorithm or ant colony optimization cannot solve the track planning problem properly. When A∗ algorithm is utilized to solve multiobjective problems, it is very complicated to calculate the heuristic function. Also, in the 3D environment with obstacles, with the expansion of the search range, the accuracy of the ant colony optimization will greatly decrease, and the optimal solution cannot be found. Therefore, based on the advantages of the two algorithms, a track planning algorithm model combining ant colony optimization and A∗ algorithm is designed.(1) Improved Global Ant Colony Optimization Algorithm Based on Consumption. The problem of 3D track planning based on the minimal energy consumption proposed in this paper takes into account the influence of natural wind. Therefore, after measuring the natural wind parameters, the real-time trajectory planning should be carried out quickly to cope with the changes in natural wind. Studies [10–12, 27] verify that the efficiency of ant colony optimization in solving track planning problems is better than other intelligent optimization algorithms. Therefore, in the global planning of viewpoint, this paper adopts ant colony optimization.To further simplify the algorithm and improve efficiency, according to the analysis of the characteristics of the power tower and the viewpoint between the tower, when the viewpoint is on the same side of the power tower, the viewpoint can mostly fly at a straight distance, but when the viewpoint is on both sides of the power tower, pole tower inspection is prohibited to fly from the lower end of the wire, so this paper proposes the following equation:(13)D=xi−xj2+yi−yj2+zi−zj2,i−j≤W,xi−xj2+yi−yj2+zi−zj2+2H−zi−zj,i−j>W,where W is the width of the tower and H is the height of the tower.Aiming at the first stage of power inspection global track planning, the lowest energy consumption is used as the objective function. And the ant colony optimization, genetic algorithm, and particle swarm algorithm are compared, respectively. The algorithms’ convergence effect is shown in Figure6. Through comparison, we can find that the ant colony optimization can find the optimal solution in the minimal number of iterations. It is more in line with the needs of real-time planning of electric power inspection.Figure 6
Algorithm convergence effect diagram.The basic steps of the ant colony optimization are described in detail in the studies [10–12], and this paper makes the following improvements:(1)
Viewpoint selection strategyDifferent from traditional ant colony optimization, the heuristic information is the energy consumption between viewpoints instead of the route length when calculating the probability that thekth ant chooses the next viewpoint j from the current viewpoint i. They can be calculated as follows:(14)pijk=τijα⋅ηijβ∑S∈Jkiτisα⋅ηisβ,ifj∈Jki,0,else,whereηij represents the energy consumption from viewpoint i to viewpoint j, obtained by equations (4)–(12). And Jki represents the set of viewpoints that the ant is allowed to traverse in the next step. Also, α and β are the heuristic factors, where the value range of α is (1, 4) and the value range of β is (3, 5).(2)
Pheromone updateAfter each ant has traversed all the viewpoints, the pheromone is updated as(15)τijn=1−ρτijn−1+Δτij,Δτij=∑k=1mΔτijk,Δτijk=QLk,if the ant passes the edgeij,0,else,Lk=∑j=1n−1wj,where Lk represents all the energy consumption after the kth ant finishing its inspections and wj is the consumption of the jth flight segment. Since the hovering durations at all viewpoints are the same at global planning, there is no need to calculate hovering consumption. τijn represents the pheromone on each track after the nth iteration, ρ (0 < ρ < 1) represents the evaporation coefficient, Δτij represents the increment of pheromone, Δτijk represents the increment of pheromone, while the kth ant is on the edge ij, and Q is a positive constant.(2) ImprovedA∗ Algorithm Based on Consumption. The A∗ algorithm can find the shortest track between any two points in the 3D environment by setting the heuristic function properly. Before applying the A∗ algorithm to solve the track with the constraints of minimal energy consumption between any two points, you need to set the heuristic function reasonably:(16)fn=gn+hn,gn=10∗ws,i,hn=10∗wi,d.In order to shorten the solution time of theA∗ algorithm, when calculating gn and hn, the paper adopts the method of enlargement and rounding and replaces the floating-point numbers with integers. If the distance is directly rounded, the accuracy of the algorithm is lost, which will reduce the efficiency of the algorithm and even fail to find the optimal solution. If the magnification is too high, although the accuracy of the algorithm can be improved, it will increase the solution time of the algorithm. At the cost, we enlarge the distance by 10 times, not only to ensure the accuracy of the algorithm but also to avoid the value being too large and increasing the algorithm solution time. In the equation, fn is the total energy consumption of any two viewpoints, gn is the energy consumption from the starting point to the current point i, and hn is the energy consumption of the current point flying directly to the target point.In order to verify the correctness and effectiveness of the improved algorithm, the following comparative test is performed. That is, the drone is flying at4m/s from point (9, 1, 0) to the destination point (10, 17, 5) with a grid length of 1 m. And in the meantime, the drone is affected by the natural east wind at 2m/s. The track planned by the traditional A∗ algorithm and the improved A∗ algorithm in this paper is shown in Figure 7. The traditional A∗ algorithm chooses to follow the red line in the picture, and the power consumed at this time is 4.998J. However, this track is not optimal when affected by natural wind. The improved A∗ algorithm plans a track with the lowest energy consumption, and the power consumed is 4.950J, which is 0.96% lower than the traditional A∗ algorithm.Figure 7
Comparison of traditionalA∗ algorithms and improved A∗ algorithms.The heuristic probability search method of the ant colony optimization is not easy to focus on the local optimum and easy to find the global optimal solution. Based on that, we can obtain the safety-oriented near-optimal track for power pole tower inspection in 3D space. Then, we use the corresponding algorithm judge whether any obstacle exists in the track of random neighboring viewpoints. If it does, theA∗ algorithm is called for local track planning. The ACO-A∗ algorithm process is shown in Figure 8.Figure 8
Algorithm flowchart of multirotor drone track planning.


## 2.2.1. 3D Point Cloud Raster Modeling

The accuracy of the traditional high-volume 3D point cloud data is higher than the hovering accuracy of the multirotor drone. Hence, the multirotor drone cannot fly according to the accuracy of the point cloud. Based on ArcGIS software, this paper utilized the grid method to extract the 3D point cloud data and maps them into the 3D matrix. The grid method is to segment the search space into a certain number of grids, and each grid represents a searchable space. The flyable spaces are marked as 0, and unflyable spaces are marked as 1, which is shown in Figure4. The key of the grid method is to set as the length of the side of each square properly. To meet the refined requirements of track planning, the area of each grid should be as small as possible, but the impact of the hovering accuracy of the multirotor drone itself should also be considered. The modeling process of applying the grid method to 3D point cloud data is shown in Figure 5. Then, we load the 3D point cloud data that needs to be processed, use the hovering accuracy of the drone as the grid side length, and use the grid method to divide the loaded point cloud data into different grids. The original point cloud data should be included in the corresponding grids. Among the grids, each grid stores the coordinate information of the corresponding point cloud. Finally, according to the planning requirements, the corresponding coordinate information is extracted, and the obtained data are mapped into a 0-1 grid matrix, as shown in Figure 4.Figure 4
0-1 grid matrix.Figure 5
3D point cloud modeling flowchart.


## 2.2.2. Ant Colony Optimization andA∗ Algorithm

The inspection of the power pole tower can be simplified as follows: in a three-dimensional environment with obstacles, the drone passes through multiple viewpoints that need to be inspected and finally finds a track with the minimal flight energy consumption. Ant colony optimization [10–12] is a heuristic random search algorithm proposed by simulating the collective patrol behavior of ants in nature. The algorithm is robust and has a strong global ability of searching. When an ant looks for a food source, it will release a pheromone on the track it went along. The ant tends to preferentially choose a track with a higher pheromone concentration until it can find the optimal track from its nest to the food source. The A∗ algorithm [25, 26] combines the characteristics of Dijkstra and BFS algorithms. It considers both the points close to the starting point and the points close to the target point so that it can find the shortest route length between any two points when there are obstacles.In this problem, only utilizingA∗ algorithm or ant colony optimization cannot solve the track planning problem properly. When A∗ algorithm is utilized to solve multiobjective problems, it is very complicated to calculate the heuristic function. Also, in the 3D environment with obstacles, with the expansion of the search range, the accuracy of the ant colony optimization will greatly decrease, and the optimal solution cannot be found. Therefore, based on the advantages of the two algorithms, a track planning algorithm model combining ant colony optimization and A∗ algorithm is designed.(1) Improved Global Ant Colony Optimization Algorithm Based on Consumption. The problem of 3D track planning based on the minimal energy consumption proposed in this paper takes into account the influence of natural wind. Therefore, after measuring the natural wind parameters, the real-time trajectory planning should be carried out quickly to cope with the changes in natural wind. Studies [10–12, 27] verify that the efficiency of ant colony optimization in solving track planning problems is better than other intelligent optimization algorithms. Therefore, in the global planning of viewpoint, this paper adopts ant colony optimization.To further simplify the algorithm and improve efficiency, according to the analysis of the characteristics of the power tower and the viewpoint between the tower, when the viewpoint is on the same side of the power tower, the viewpoint can mostly fly at a straight distance, but when the viewpoint is on both sides of the power tower, pole tower inspection is prohibited to fly from the lower end of the wire, so this paper proposes the following equation:(13)D=xi−xj2+yi−yj2+zi−zj2,i−j≤W,xi−xj2+yi−yj2+zi−zj2+2H−zi−zj,i−j>W,where W is the width of the tower and H is the height of the tower.Aiming at the first stage of power inspection global track planning, the lowest energy consumption is used as the objective function. And the ant colony optimization, genetic algorithm, and particle swarm algorithm are compared, respectively. The algorithms’ convergence effect is shown in Figure6. Through comparison, we can find that the ant colony optimization can find the optimal solution in the minimal number of iterations. It is more in line with the needs of real-time planning of electric power inspection.Figure 6
Algorithm convergence effect diagram.The basic steps of the ant colony optimization are described in detail in the studies [10–12], and this paper makes the following improvements:(1)
Viewpoint selection strategyDifferent from traditional ant colony optimization, the heuristic information is the energy consumption between viewpoints instead of the route length when calculating the probability that thekth ant chooses the next viewpoint j from the current viewpoint i. They can be calculated as follows:(14)pijk=τijα⋅ηijβ∑S∈Jkiτisα⋅ηisβ,ifj∈Jki,0,else,whereηij represents the energy consumption from viewpoint i to viewpoint j, obtained by equations (4)–(12). And Jki represents the set of viewpoints that the ant is allowed to traverse in the next step. Also, α and β are the heuristic factors, where the value range of α is (1, 4) and the value range of β is (3, 5).(2)
Pheromone updateAfter each ant has traversed all the viewpoints, the pheromone is updated as(15)τijn=1−ρτijn−1+Δτij,Δτij=∑k=1mΔτijk,Δτijk=QLk,if the ant passes the edgeij,0,else,Lk=∑j=1n−1wj,where Lk represents all the energy consumption after the kth ant finishing its inspections and wj is the consumption of the jth flight segment. Since the hovering durations at all viewpoints are the same at global planning, there is no need to calculate hovering consumption. τijn represents the pheromone on each track after the nth iteration, ρ (0 < ρ < 1) represents the evaporation coefficient, Δτij represents the increment of pheromone, Δτijk represents the increment of pheromone, while the kth ant is on the edge ij, and Q is a positive constant.(2) ImprovedA∗ Algorithm Based on Consumption. The A∗ algorithm can find the shortest track between any two points in the 3D environment by setting the heuristic function properly. Before applying the A∗ algorithm to solve the track with the constraints of minimal energy consumption between any two points, you need to set the heuristic function reasonably:(16)fn=gn+hn,gn=10∗ws,i,hn=10∗wi,d.In order to shorten the solution time of theA∗ algorithm, when calculating gn and hn, the paper adopts the method of enlargement and rounding and replaces the floating-point numbers with integers. If the distance is directly rounded, the accuracy of the algorithm is lost, which will reduce the efficiency of the algorithm and even fail to find the optimal solution. If the magnification is too high, although the accuracy of the algorithm can be improved, it will increase the solution time of the algorithm. At the cost, we enlarge the distance by 10 times, not only to ensure the accuracy of the algorithm but also to avoid the value being too large and increasing the algorithm solution time. In the equation, fn is the total energy consumption of any two viewpoints, gn is the energy consumption from the starting point to the current point i, and hn is the energy consumption of the current point flying directly to the target point.In order to verify the correctness and effectiveness of the improved algorithm, the following comparative test is performed. That is, the drone is flying at4m/s from point (9, 1, 0) to the destination point (10, 17, 5) with a grid length of 1 m. And in the meantime, the drone is affected by the natural east wind at 2m/s. The track planned by the traditional A∗ algorithm and the improved A∗ algorithm in this paper is shown in Figure 7. The traditional A∗ algorithm chooses to follow the red line in the picture, and the power consumed at this time is 4.998J. However, this track is not optimal when affected by natural wind. The improved A∗ algorithm plans a track with the lowest energy consumption, and the power consumed is 4.950J, which is 0.96% lower than the traditional A∗ algorithm.Figure 7
Comparison of traditionalA∗ algorithms and improved A∗ algorithms.The heuristic probability search method of the ant colony optimization is not easy to focus on the local optimum and easy to find the global optimal solution. Based on that, we can obtain the safety-oriented near-optimal track for power pole tower inspection in 3D space. Then, we use the corresponding algorithm judge whether any obstacle exists in the track of random neighboring viewpoints. If it does, theA∗ algorithm is called for local track planning. The ACO-A∗ algorithm process is shown in Figure 8.Figure 8
Algorithm flowchart of multirotor drone track planning.


## 3. Simulation and Analysis

### 3.1. Simulation Environment Settings

In order to verify the correctness and effectiveness of the improved algorithm in this paper, the simulation experiment was performed on a Core (TM) i7 (3.40 GHz) Personal Computer, and the operating environment was Windows 7. In this paper, the Goblet Single Circuit Tangent Tower is the main research object, and the 3D point cloud data of the tower are visualized to obtain the model in Figure8. The scale of the entire planning space is 32.31m×56.24m×52.81m, and the number of point clouds is 190,845. According to the “Guidebook for Shooting Images of UAV Patrol Inspection for Overhead Transmission Lines” (hereinafter referred to as the manual), the patrol inspection the power pole tower includes inspection of the tower body and various components (Figure 9, A–K).Figure 9
Model of power pole tower.According to the above tower information, we follow the steps below to complete the spatial modeling and simulation of the point cloud data:(1)
Via ArcGIS software, project 3D point cloud data to a 2D plane. The grid accuracy is equal to the hovering accuracy of the multirotor drone (λm=0.3). Since multirotor drones are prohibited from flying at the lower end of the wire, each grid extracts the maximum elevation value of the included point cloud and obtains the two-dimensional grid schematic diagram shown in Figure 10. At this time, the number of point clouds is 18,408. The maximum elevation value of each grid point cloud is visualized to obtain a three-dimensional grid schematic diagram, as shown in Figure 11, and each cuboid represents a nonflyable space.(2)
Convert the grid information obtained by ArcGIS into a 3D array and store the flyable space and obstacles with 0 and 1, respectively.(3)
According to the built 3D model, we implement the improved ACO-A∗ algorithm. The values of corresponding parameters in the algorithm such as α, β, ρ, and wind speed are shown in Table 1.Figure 10
Schematic diagram of 2D grid.Figure 11
Schematic diagram of 3D grid.Figure 12
Track planning of ant colony optimization andA∗ algorithm.Table 1
Parameters values.
αβρcHmWmVm⋅s−1Vhmaxm⋅s−1Vlmaxm⋅s−1Vwmaxm⋅s−1VWm⋅s−1smδ°140.5143244531225270The result is shown in Figure12. That is, at the wind angle χ=270°, the drone changed its take-off and landing points, and the energy consumption is reduced by 62.88% compared with the patrol track specified in the manual.


### 3.2. Analysis of Simulation Results

#### 3.2.1. Comparative Analysis of Track Optimization

When the wind direction angleχ=270°, the track regulated by the manual (red line) and the track planned with the shortest route length as the objective function (green line) are shown in Figure 13. In order to further verify the correctness and effectiveness of the algorithm in this paper, we change the wind direction angle and let χ=90°. The energy consumption of the three tracks (unit: J) is shown in Figure 14.Figure 13
Track comparison diagram.Figure 14
Comparison of energy consumption of different tracks.Through comparison, when the wind direction angleχ=90°, since take-off and landing points are the same, the energy consumption of the track planned with the shortest route length is equivalent to that of the track planned by the improved algorithm in this paper. However, when the wind direction angle χ=270°, the energy consumption of the track consumed by the improved algorithm in this paper is 62.88% lower than the regulated track and 9.33% lower than the energy consumption of the track planned by the shortest route length. On the basis of ensuring that the drone is shooting the same components, the path planning algorithm proposed in this paper adjusts the inspection take-off and landing points according to different wind speeds and directions. It effectively uses natural wind and reduces the battery’s energy consumption.By recording the convergence time of the above three algorithms and visualizing them, the results are shown in Figure15. Through comparison, the convergence time of the algorithm in this paper is higher than the convergence time of the other two algorithms. However, the entire planning time is around 10min, which fully meets the needs of real-time planning of electric power inspection tracks.Figure 15
Comparison of convergence time by different algorithms.Literature [12] proposed a 3D track planning for autonomous underwater vehicles based on the ACO-A∗ algorithm. Although it is similar to the algorithm used in this paper, it does not consider the influence of the external environment on the 3D track planning, especially when the flow of water is large, which will make the planned track infeasible. In addition, in order to further improve the efficiency of the algorithm, the heuristic function of the ACO-A∗ algorithm is enlarged and rounded. In the same environment, the efficiency of the improved algorithm in this paper is higher than that of the literature [12]. In order to solve the problem that the current UAV has a short range and cannot meet the automatic inspection of multiple power poles, literature [2] presents a solution that uses the “hangar” as a connection point. That is, select several “hangars” among multiple inspection power pole towers, as a starting point for inspection, to complete automatic inspection of multiple power pole towers. Due to the short flight time of the UAV and the multitarget inspection, if the influence of natural wind and other factors is not considered, only the shortest path or the shortest flight time is used as the target function. The actual output energy consumption of the aircraft is greater than the planned energy consumption, which will affect the safety of inspection.


#### 3.2.2. Comparative Analysis of Algorithm Convergence Time

In this paper, track planning is based on the minimal energy consumption. Since neighboring viewpoints are affected by the wind direction, we set the time complexity of the algorithm when calculating the cost of neighboring viewpoints isOn2. And the entire planning time does not meet the actual power inspection requirements because the A∗ algorithm explores the surrounding 26 grids whenever finding the optimal solution in 3D space. In order to reduce this complexity, global planning and local planning are introduced to reduce the time complexity of the algorithm from On2 to On. In other words, we will use the ant colony optimization algorithm first to find the global near-optimal solution with the minimal energy consumption and then determine whether the track passes through obstacles. If it does, the optimal local path planning for energy consumption will be performed based on the A∗ algorithm. In order to verify the effectiveness of the improved algorithm in this paper, we, respectively, select 3 viewpoints (F, G, and H), 5 viewpoints (B, C, F, G, and H), and 7 viewpoints (A, B, F, G, H, I, and J) in the point cloud data of the Goblet Tower to be compared and verified. The comparison result is shown in Figure 16. Through comparison, it is found that when there are only 3 viewpoints, the running time (in minutes) of the improved ACO-A∗ algorithm and A∗ algorithm is 2.89 and 31.403, respectively. In other words, the improved ACO-A∗ algorithm reduced the time consumption by 98.54%. When there are 5 viewpoints, the runtime of the improved ACO-A∗ algorithm and A∗ algorithm is 4.69 and 121.85, respectively, and the former algorithm reduced the time consumption by 96.1%. When there are 7 viewpoints, the solution time of the improved ACO-A∗ algorithm and A∗ algorithm is 12.58 and 365.32, respectively, and the improved ACO-A∗ algorithm reduced the time consumption by 96.6%. That is, with the increase in inspection points, the A∗ algorithm no longer meets the needs of real-time planning.Figure 16
Time comparison of improved algorithm andA∗ algorithm.


## 3.1. Simulation Environment Settings

In order to verify the correctness and effectiveness of the improved algorithm in this paper, the simulation experiment was performed on a Core (TM) i7 (3.40 GHz) Personal Computer, and the operating environment was Windows 7. In this paper, the Goblet Single Circuit Tangent Tower is the main research object, and the 3D point cloud data of the tower are visualized to obtain the model in Figure8. The scale of the entire planning space is 32.31m×56.24m×52.81m, and the number of point clouds is 190,845. According to the “Guidebook for Shooting Images of UAV Patrol Inspection for Overhead Transmission Lines” (hereinafter referred to as the manual), the patrol inspection the power pole tower includes inspection of the tower body and various components (Figure 9, A–K).Figure 9
Model of power pole tower.According to the above tower information, we follow the steps below to complete the spatial modeling and simulation of the point cloud data:(1)
Via ArcGIS software, project 3D point cloud data to a 2D plane. The grid accuracy is equal to the hovering accuracy of the multirotor drone (λm=0.3). Since multirotor drones are prohibited from flying at the lower end of the wire, each grid extracts the maximum elevation value of the included point cloud and obtains the two-dimensional grid schematic diagram shown in Figure 10. At this time, the number of point clouds is 18,408. The maximum elevation value of each grid point cloud is visualized to obtain a three-dimensional grid schematic diagram, as shown in Figure 11, and each cuboid represents a nonflyable space.(2)
Convert the grid information obtained by ArcGIS into a 3D array and store the flyable space and obstacles with 0 and 1, respectively.(3)
According to the built 3D model, we implement the improved ACO-A∗ algorithm. The values of corresponding parameters in the algorithm such as α, β, ρ, and wind speed are shown in Table 1.Figure 10
Schematic diagram of 2D grid.Figure 11
Schematic diagram of 3D grid.Figure 12
Track planning of ant colony optimization andA∗ algorithm.Table 1
Parameters values.
αβρcHmWmVm⋅s−1Vhmaxm⋅s−1Vlmaxm⋅s−1Vwmaxm⋅s−1VWm⋅s−1smδ°140.5143244531225270The result is shown in Figure12. That is, at the wind angle χ=270°, the drone changed its take-off and landing points, and the energy consumption is reduced by 62.88% compared with the patrol track specified in the manual.


## 3.2. Analysis of Simulation Results

### 3.2.1. Comparative Analysis of Track Optimization

When the wind direction angleχ=270°, the track regulated by the manual (red line) and the track planned with the shortest route length as the objective function (green line) are shown in Figure 13. In order to further verify the correctness and effectiveness of the algorithm in this paper, we change the wind direction angle and let χ=90°. The energy consumption of the three tracks (unit: J) is shown in Figure 14.Figure 13
Track comparison diagram.Figure 14
Comparison of energy consumption of different tracks.Through comparison, when the wind direction angleχ=90°, since take-off and landing points are the same, the energy consumption of the track planned with the shortest route length is equivalent to that of the track planned by the improved algorithm in this paper. However, when the wind direction angle χ=270°, the energy consumption of the track consumed by the improved algorithm in this paper is 62.88% lower than the regulated track and 9.33% lower than the energy consumption of the track planned by the shortest route length. On the basis of ensuring that the drone is shooting the same components, the path planning algorithm proposed in this paper adjusts the inspection take-off and landing points according to different wind speeds and directions. It effectively uses natural wind and reduces the battery’s energy consumption.By recording the convergence time of the above three algorithms and visualizing them, the results are shown in Figure15. Through comparison, the convergence time of the algorithm in this paper is higher than the convergence time of the other two algorithms. However, the entire planning time is around 10min, which fully meets the needs of real-time planning of electric power inspection tracks.Figure 15
Comparison of convergence time by different algorithms.Literature [12] proposed a 3D track planning for autonomous underwater vehicles based on the ACO-A∗ algorithm. Although it is similar to the algorithm used in this paper, it does not consider the influence of the external environment on the 3D track planning, especially when the flow of water is large, which will make the planned track infeasible. In addition, in order to further improve the efficiency of the algorithm, the heuristic function of the ACO-A∗ algorithm is enlarged and rounded. In the same environment, the efficiency of the improved algorithm in this paper is higher than that of the literature [12]. In order to solve the problem that the current UAV has a short range and cannot meet the automatic inspection of multiple power poles, literature [2] presents a solution that uses the “hangar” as a connection point. That is, select several “hangars” among multiple inspection power pole towers, as a starting point for inspection, to complete automatic inspection of multiple power pole towers. Due to the short flight time of the UAV and the multitarget inspection, if the influence of natural wind and other factors is not considered, only the shortest path or the shortest flight time is used as the target function. The actual output energy consumption of the aircraft is greater than the planned energy consumption, which will affect the safety of inspection.


### 3.2.2. Comparative Analysis of Algorithm Convergence Time

In this paper, track planning is based on the minimal energy consumption. Since neighboring viewpoints are affected by the wind direction, we set the time complexity of the algorithm when calculating the cost of neighboring viewpoints isOn2. And the entire planning time does not meet the actual power inspection requirements because the A∗ algorithm explores the surrounding 26 grids whenever finding the optimal solution in 3D space. In order to reduce this complexity, global planning and local planning are introduced to reduce the time complexity of the algorithm from On2 to On. In other words, we will use the ant colony optimization algorithm first to find the global near-optimal solution with the minimal energy consumption and then determine whether the track passes through obstacles. If it does, the optimal local path planning for energy consumption will be performed based on the A∗ algorithm. In order to verify the effectiveness of the improved algorithm in this paper, we, respectively, select 3 viewpoints (F, G, and H), 5 viewpoints (B, C, F, G, and H), and 7 viewpoints (A, B, F, G, H, I, and J) in the point cloud data of the Goblet Tower to be compared and verified. The comparison result is shown in Figure 16. Through comparison, it is found that when there are only 3 viewpoints, the running time (in minutes) of the improved ACO-A∗ algorithm and A∗ algorithm is 2.89 and 31.403, respectively. In other words, the improved ACO-A∗ algorithm reduced the time consumption by 98.54%. When there are 5 viewpoints, the runtime of the improved ACO-A∗ algorithm and A∗ algorithm is 4.69 and 121.85, respectively, and the former algorithm reduced the time consumption by 96.1%. When there are 7 viewpoints, the solution time of the improved ACO-A∗ algorithm and A∗ algorithm is 12.58 and 365.32, respectively, and the improved ACO-A∗ algorithm reduced the time consumption by 96.6%. That is, with the increase in inspection points, the A∗ algorithm no longer meets the needs of real-time planning.Figure 16
Time comparison of improved algorithm andA∗ algorithm.


## 3.2.1. Comparative Analysis of Track Optimization

When the wind direction angleχ=270°, the track regulated by the manual (red line) and the track planned with the shortest route length as the objective function (green line) are shown in Figure 13. In order to further verify the correctness and effectiveness of the algorithm in this paper, we change the wind direction angle and let χ=90°. The energy consumption of the three tracks (unit: J) is shown in Figure 14.Figure 13
Track comparison diagram.Figure 14
Comparison of energy consumption of different tracks.Through comparison, when the wind direction angleχ=90°, since take-off and landing points are the same, the energy consumption of the track planned with the shortest route length is equivalent to that of the track planned by the improved algorithm in this paper. However, when the wind direction angle χ=270°, the energy consumption of the track consumed by the improved algorithm in this paper is 62.88% lower than the regulated track and 9.33% lower than the energy consumption of the track planned by the shortest route length. On the basis of ensuring that the drone is shooting the same components, the path planning algorithm proposed in this paper adjusts the inspection take-off and landing points according to different wind speeds and directions. It effectively uses natural wind and reduces the battery’s energy consumption.By recording the convergence time of the above three algorithms and visualizing them, the results are shown in Figure15. Through comparison, the convergence time of the algorithm in this paper is higher than the convergence time of the other two algorithms. However, the entire planning time is around 10min, which fully meets the needs of real-time planning of electric power inspection tracks.Figure 15
Comparison of convergence time by different algorithms.Literature [12] proposed a 3D track planning for autonomous underwater vehicles based on the ACO-A∗ algorithm. Although it is similar to the algorithm used in this paper, it does not consider the influence of the external environment on the 3D track planning, especially when the flow of water is large, which will make the planned track infeasible. In addition, in order to further improve the efficiency of the algorithm, the heuristic function of the ACO-A∗ algorithm is enlarged and rounded. In the same environment, the efficiency of the improved algorithm in this paper is higher than that of the literature [12]. In order to solve the problem that the current UAV has a short range and cannot meet the automatic inspection of multiple power poles, literature [2] presents a solution that uses the “hangar” as a connection point. That is, select several “hangars” among multiple inspection power pole towers, as a starting point for inspection, to complete automatic inspection of multiple power pole towers. Due to the short flight time of the UAV and the multitarget inspection, if the influence of natural wind and other factors is not considered, only the shortest path or the shortest flight time is used as the target function. The actual output energy consumption of the aircraft is greater than the planned energy consumption, which will affect the safety of inspection.


## 3.2.2. Comparative Analysis of Algorithm Convergence Time

In this paper, track planning is based on the minimal energy consumption. Since neighboring viewpoints are affected by the wind direction, we set the time complexity of the algorithm when calculating the cost of neighboring viewpoints isOn2. And the entire planning time does not meet the actual power inspection requirements because the A∗ algorithm explores the surrounding 26 grids whenever finding the optimal solution in 3D space. In order to reduce this complexity, global planning and local planning are introduced to reduce the time complexity of the algorithm from On2 to On. In other words, we will use the ant colony optimization algorithm first to find the global near-optimal solution with the minimal energy consumption and then determine whether the track passes through obstacles. If it does, the optimal local path planning for energy consumption will be performed based on the A∗ algorithm. In order to verify the effectiveness of the improved algorithm in this paper, we, respectively, select 3 viewpoints (F, G, and H), 5 viewpoints (B, C, F, G, and H), and 7 viewpoints (A, B, F, G, H, I, and J) in the point cloud data of the Goblet Tower to be compared and verified. The comparison result is shown in Figure 16. Through comparison, it is found that when there are only 3 viewpoints, the running time (in minutes) of the improved ACO-A∗ algorithm and A∗ algorithm is 2.89 and 31.403, respectively. In other words, the improved ACO-A∗ algorithm reduced the time consumption by 98.54%. When there are 5 viewpoints, the runtime of the improved ACO-A∗ algorithm and A∗ algorithm is 4.69 and 121.85, respectively, and the former algorithm reduced the time consumption by 96.1%. When there are 7 viewpoints, the solution time of the improved ACO-A∗ algorithm and A∗ algorithm is 12.58 and 365.32, respectively, and the improved ACO-A∗ algorithm reduced the time consumption by 96.6%. That is, with the increase in inspection points, the A∗ algorithm no longer meets the needs of real-time planning.Figure 16
Time comparison of improved algorithm andA∗ algorithm.


## 4. Conclusions

### 4.1. Summary of Work

(a)
With the objective of the minimal energy consumption, a multirotor drone performance constraint and natural wind constraint model are established. The multirotor drone inspection is divided into hovering and cruising phases, and the energy consumption calculation equations are given, respectively. ACO-A∗ algorithms to plan different tracks are based on different wind direction information. Through simulation comparison and analysis, the algorithm-planned track reduces energy consumption by 62.88% compared to the track specified in the manual and saves 9.33% compared to energy consumption planned by the optimal distance.(b)
Raster modeling of 3D point cloud data is achieved. Based on ArcGIS software, the drone hovering accuracy is used as the grid side length, and the grid method is used to complete the reextraction of the original point cloud data. This method improves the search efficiency in 3D space and realizes the automatic conversion of point cloud data into 3D 0-1 matrix.(c)
The improved ACO-A∗ algorithm reduces the solution time of 3D track planning. Based on the minimal energy consumption track planning requirements, the simulation of the Goblet Straight-Line Single-Return Tower shows that the solution time of the improved ACO-A∗ algorithm is 96.6% shorter than that of the A∗ algorithm.


### 4.2. Further Research

There is limited research work on unmanned aerial vehicle real-time track planning and multiple object patrols in emergencies. The next research will be carried out from this part.


## 4.1. Summary of Work

(a)
With the objective of the minimal energy consumption, a multirotor drone performance constraint and natural wind constraint model are established. The multirotor drone inspection is divided into hovering and cruising phases, and the energy consumption calculation equations are given, respectively. ACO-A∗ algorithms to plan different tracks are based on different wind direction information. Through simulation comparison and analysis, the algorithm-planned track reduces energy consumption by 62.88% compared to the track specified in the manual and saves 9.33% compared to energy consumption planned by the optimal distance.(b)
Raster modeling of 3D point cloud data is achieved. Based on ArcGIS software, the drone hovering accuracy is used as the grid side length, and the grid method is used to complete the reextraction of the original point cloud data. This method improves the search efficiency in 3D space and realizes the automatic conversion of point cloud data into 3D 0-1 matrix.(c)
The improved ACO-A∗ algorithm reduces the solution time of 3D track planning. Based on the minimal energy consumption track planning requirements, the simulation of the Goblet Straight-Line Single-Return Tower shows that the solution time of the improved ACO-A∗ algorithm is 96.6% shorter than that of the A∗ algorithm.


## 4.2. Further Research

There is limited research work on unmanned aerial vehicle real-time track planning and multiple object patrols in emergencies. The next research will be carried out from this part.



---

*Source: 8295362-2020-06-30.xml*