Microsoft Word - 001.docx


 CHEMICAL ENGINEERING TRANSACTIONS  
 

VOL. 66, 2018 

A publication of 

 

The Italian Association 
of Chemical Engineering 
Online at www.aidic.it/cet 

Guest Editors: Songying Zhao, Yougang Sun, Ye Zhou 
Copyright © 2018, AIDIC Servizi S.r.l. 

ISBN 978-88-95608-63-1; ISSN 2283-9216 

Study on the Path Planning Method for Oilfield Patrolling UAV 

based on Leapfrog Particle Swarm Optimization 

Xiaopeng Guoa, Zhili Zhangb 

aAeronautics and Astronautics College,Tianjin Sino-German University of Applied Sciences,Tianjin 300350, China 
bIntelligent Manufacturing College,Tianjin Sino-German University of Applied Sciences, Tianjin 300350, China 

 xiaopengguo27381@163.com 

To improve the path planning method for traditional oilfield patrolling UAV. Based on the complex network 

theory and the example for path planning, search for the rough path through Dijkstra algorithm. The results of 

simulation analysis shows that the improvement of improved particle swarm optimization can help converge to 

the minimum value faster, and can reach the theoretical minimum value of the function, showing a good 

algorithm performance. The adaptive inertial coefficient method for the algorithm in this Paper may 

automatically adjust the inertial coefficients, which accelerates the convergence speed of the algorithm, and 

enhances the convergence performance of the algorithm. 

1. Introduction 

With the continuous development of science and technology, UAV technology has become an indispensable 

part of many basic social work. This technology mainly uses UAV to replace the traditional manual operation, 

and then through the UAV, effectively optimize the efficiency, accuracy, and other aspects of related work. 

However, even the working method of UAV also fails to be defect-free, e.g. during the oilfield patrolling work, 

due to the gradual increment of the scale of modern oilfield development, traditional UAV can no longer meet 

the needs, but due to various restrictions, direct increase in the number of UAVs can't improve the situation, 

through the modern research, it is understood that it need urgently to study the path planning of the oilfield 

UAV path planning to improve this situation. 

This Paper mainly takes the oilfield UAV path planning as an example and combines the flight environment 

and mission requirements during the UAV patrolling in oilfield, determine the UAV path expression form and 

constraints. According to the UAV's flight at fixed altitude, the three-dimensional flight environment is 

abstracted as a two-dimensional space intercepted by the virtual plane; adopting the geometric description 

method, expresses the oilfield as a plane coordinate feature point and the obstacle as a planar polygon; and 

using Gauss-Kruger projection method, carries out the angular invariant treatment for the oilfield longitude-

latitude coordinate, so as to establish the environmental model. Finally, for the deficiency of traditional particle 

swarm optimization algorithm, brings forward a kind of hybrid leapfrog particle swarm optimization. 

2. Literature review 

This paper studies the basic model of the UAV track planning. As basic Particle Swarm Optimization (PSO) 

algorithm is easy to fall into local minimum and its searching accuracy is not ideal, the author puts forward an 

improved hybrid particle swarm UAV route planning method with contraction factor. This method is used to 

change algorithm in the balance of performance by introducing contraction factor and learning factor, in order 

to get a better convergence speed and convergence rate. At the same time using MATLAB as the 

development tool for simulation, the results show that this method is simple and effective and can meet the 

requirements of the UAV path planning (Geng and Zhao, 2013). An improved chaos particle swarm 

optimization algorithm is proposed on path planning for unmanned aerial vehicle to overcome the inadequacy 

of particle swarm optimization algorithm, which falls into local optimum easily and converges slowly in process 

with poor precision. Through the in-depth analysis of PSO algorithm, the chaos optimization algorithm 

                                

 
 

 

 
   

                                                  
DOI: 10.3303/CET1866161 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Please cite this article as: Guo X., Zhang Z., 2018, Study on the path planning method for oilfield patrolling uav based on leapfrog particle 
swarm optimization, Chemical Engineering Transactions, 66, 961-966  DOI:10.3303/CET1866161   

961



principle is introduced into it based on the traditional update operations on the particles’ velocity and position; 

as a result, the diversity of particles is increased, the suboptimal search on path planning is avoided and the 

quickness accompanied with accuracy of convergence is improved. Combined with digital map for modelling 

the UAV’s flight environment, the 3-D path planning is achieved. As the simulation results demonstrated, this 

hybrid algorithm is superior to the traditional PSO algorithm on path searching, especially in the 3-D 

environment (Chang et al., 2012). 

The complex network theory was applied to the particle swarm algorithm and an improved particle swarm 

algorithm was proposed, enhancing algorithm's convergence performance by using adaptive inertia coefficient 

method automatically to adjust the inertia coefficient. Following Voronoi graph theory, feasible path network 

structure chart was used to express the distribution of known threat, Dijkstra algorithm was applied to roughly 

seek threat distribution to get rough shortest path. In this paper, according to rough shortest path, improved 

particle swarm algorithm and least squares method were used for optimizing the initial reference path. The 

mat lab simulation result demonstrates the algorithm effectiveness and UAV path planning rationality (Liu et 

al., 2013). It proposes a potential odor intensity grid-based optimization approach for unmanned aerial vehicle 

(UAV) path planning with particle swarm optimization technique. Odor intensity is created to color the area in 

the searching space with highest probability where candidate particles may locate. A potential grid 

construction operator is designed for standard PSO based on different levels of odor intensity. The potential 

grid construction operator generates two potential location grids with highest odor intensity. Then the middle 

point will be seen as the final position in current particle dimension. The global optimum solution will be solved 

as the average. In addition, solution boundaries of searching space in each particle dimension are restricted 

based on properties of threats in the flying field to avoid prematurity (Liu et al., 2016). 

As the energy problem becomes more and more serious, it is necessary to do research on energy saving. In 

order to achieve the desired height economically and quickly, the two key factors of fuel consumption and time 

cost are considered. First, the mathematical model of UAV’s climbing trajectory is established, the fuel 

consumption and time cost are considered as the performance optimization indexes. Second, the UAV’s 

performance optimization method based on the improved particle swarm algorithm is proposed, then the 

problem of UAV's performance optimization is turned into the problem of constrained multi-parameter 

optimization. Finally, the proposed method is used in a certain type of UAV, and the simulation results show, 

compared with the conventional method, the proposed method saves more operation costs and has better 

superiority (Xie et al., 2012). The development of autonomous unmanned aerial vehicles is of high interest to 

many governmental and military organizations around the world. An essential aspect of UAV autonomy is the 

ability for automatic path planning. In the paper, we use the genetic algorithm (GA) and the particle swarm 

optimization algorithm to cope with the complexity of the problem and compute feasible and quasi-optimal 

trajectories for fixed wing UAVs in a complex 3D environment, while considering the dynamic properties of the 

vehicle. The characteristics of the optimal path are represented in the form of a multiobjective cost function 

that we developed. The paths produced are composed of line segments, circular arcs and vertical helices 

(Roberge et al., 2012). 

We take advantage of parallel computing to implement the dpso in a GPU-based framework so that the 

computation time can be significantly reduced while keeping the hardware requirement unchanged. To show 

the effectiveness of the proposed algorithm, experimental results are included for datasets obtained from UAV 

inspection of an office building and a bridge (Phung et al., 2017). To meet the demand of real-time dynamic 

path planning, this paper proposes a dynamic path planning strategy of adaptive chaotic particle swarm 

optimization algorithm, which owns both good global and local search ability. The simulation shows that the 

path planning strategy this paper proposes, basically, meets the needs of real-time path planning. Moreover, it 

has better performance than other algorithms (Wang et al., 2014). 

The Unmanned Aerial Vehicle (UAV) has been widely applied to various applications, such as the enemy 

investigation in war, image transmission of military usage by satellite, and the transmission of control signal 

and image through radio frequency. The civilian UAV typically uses satellite, Global Positioning System, Wi-Fi 

or the third generation of mobile phone mobile communications technology for communications. However, the 

transmission range limits the data transmission of civilian UAV. In the paper, we utilize the 3G 

communications and consider the signal quality of base stations for path planning. We adopt the well-known a 

star search algorithm to prevent the dead end of signal during flight and plan the better flight path for civil 

UAV. The simulation results show that our proposed method acquires the 2.44 times better communication 

quality and routes with the 1.56 times longer flight only. 

The development of autonomous UASs and subsystems will continue to expand in the future. The systems 

being developed will need to be safe, reliable, and effective across multiple operational environments and 

tasks. Development of systems that can perform multiple scenarios and be adaptable to new capabilities and 

responsive to changes in environments and missions will be the key to future success. Significant research 

and development in capabilities has been performed and continues. A modular system architecture was 

962



proposed in the paper that will enable safe and trustworthy performance of multiple-scenario missions. Critical 

path-planning and safety controls which will provide underlying system capabilities for future development 

were reviewed. 

3. Method 

3.1 Complex network theory 

For complex systems that cannot be analyzed by analytical methods, the interactions and connections 

between individuals must be considered. Complex system can be regarded as a network interacting between 

units or individuals. Complex network is the basic framework that constitutes the complex systems, which 

consists of the nodes and the edges that connect the nodes, and its importance in portraying the complexity is 

due to the mutual influence of the structure and the function. As the research deepens, scholars conclude that 

they are composed of rule network, random network, small world network and scale-free network. Among 

them: the typical characteristic of small-world network is homogeneity (that is, each node has approximately 

the same number of connections), under which characteristics, the number of nodes doesn't increase, the 

average agglomeration coefficient is higher, and the shortest average path is smaller; the typical 

characteristics of scale-free network is connectivity (subject to power-law distribution), non-homogeneous (i.e., 

few nodes have many connections, and many nodes have very few connections), the number of nodes 

increases. The mathematical description of a complex network can be expressed as, Network G = (V, E), a 

graph consisting of point set "V (G)" and edge set "E(G)", which can be divided into undirected networks, 

directed networks and weighted networks. Set "eiE(G)", each edge "ei" corresponds to a pair of points "(u, 

v)" in "V(G)", and if any "(u, v)" and "(v, u)" correspond to the same edge, it is called an undirected network; 

otherwise it is called a directed network; if either "|ei|=1", then it is called unweighted network; otherwise it is 

called weighted network. In the weighted network, the definitions of the weights include similar weight and 

different weight. Similar weight refers to that the concept and the distance is opposite, the greater the edge 

weight, the closer the vertexes (0 means "no connection"), such as the number of cooperation, the chemical 

reaction rate; different weight refers that the concept and the distance is the same, i.e. the greater the edge 

weight, the farther the distance between the vertices (∞ means "no connection"), such as the mileage in air 

route. Through the study on many practical networks, it's found that they have a common feature called the 

community structure in the network. It is divided into groups according to the location of the nodes in the 

network, and each group is a community. The connections in the community is closer than the connection 

between the communities. 

3.2 The main idea of the algorithm 

As a special complex network system, the particle swarm optimization algorithm has attracted wide attention 

in the academic community, because its effectiveness in solving problems has become a research hotspot, 

but it is easy to fall into premature problems. Many scholars have also proposed the improved particle swarm 

algorithms, most of these algorithms have slow convergence speeds, and global search performance needs to 

be improved. In this Paper, the complex network theory is applied to the improvement of particle swarm 

optimization, and an improved particle swarm optimization algorithm that can achieve effective search and fast 

convergence is proposed, while through the automatic adjustment of inertial coefficient of adaptive inertial 

coefficient method, convergence performance will be enhanced. 

3.3 Path planning 

 

Figure 1: Network structure diagram of feasible path 

963



In this Paper, 22 known threat points, 1 starting point, and 1 target point are selected. According to the known 

threat distribution, a feasible path network structure diagram based on threat distribution is constructed, as 

shown in Figure 1, representing a airspace of 40 km × 40 km × 35 km. Set the maximum side length to 5 km, 

and when the distance between any two threat points is less than twice of the maximum side length, taking the 

middle point as the node of the network, and all nodes make up the network point set "V(G)"; the connection 

between the midpoints serves as the edge of the network, and all the edges constitute the network edge set 

"E(G)". It can be seen that the network structure is the weighted undirected network, and the weight is 

proportional to the distance between the two points, that is, the dissimilarity weight. 

3.4 Rough search path for dijkstra algorithm 

In the constructed network structure diagram of feasible paths, the search for shortest path is converted into 

the calculation of minimum cost from the extraction point to the target point. In the UAV flight process, the path 

cost mainly contains the risk cost and the fuel cost, wherein, the risk cost refers to radar detection or fire 

threats from the enemy, which is usually inversely proportional to the fourth power of the distance from the 

center point of the threat, and the fuel cost is directly proportional to the flight distance, which is the dangerous 

price. 

According to the above theory, the Dijkstra algorithm is used to conduct a rough search of the feasible path 

network structure diagram, and draw the shortest rough search path as shown in Figure 2. 

 

Figure 2: Rough shortest path diagram 

Starting from the starting point, No. 36 point, passing through points 10, 9, 11 and 15, reaching the target point 

No. 37 point, the shortest distance is 39.328 9 km. 

4. Results and analysis 

4.1 Simulation results 

In this Paper, the nonlinear Ackley function optimization is used to compare the algorithms. The function has 

many local minimum points, wherein, the minimum point is 0, and the minimum position is (0, 0). The 

simulation results are as shown in Figure 3, 4, and 5. 

                 

Figure 3: Best individual of the basic particle swarm       Figure 4: Best individual of the improved particle  

algorithm corresponding function value curve                  swarm algorithm corresponding function value curve 

964



The simulation results show that, when the condition of population size is 50 and evolution number is 200, the 

operation result of basic particle swarm optimization algorithm is 0.001 6, and the operation result of improved 

particle swarm algorithm is 8.881 8×10-16. If the population size is changed to 100, after n200 times of 

iterations, the operation result is 0, reaching the theoretical minimum value of the function. To facilitate the 

comparison between the performance of the algorithms, the function value variation curves of Figure 3 and 

Figure 4 are put into the same graph, and at the same time, the range of Y-axis (function value axis) is taken 

as [0, 0.5]. In Figure 5, the dashed line is the function curve of the basic particle swarm algorithm, and the 

solid line is the function curve of the improved particle swarm algorithm. From the figure, the improved particle 

swarm algorithm can help realize faster convergence to the minimum value, and can reach the theoretical 

minimum value of the function, showing a good algorithm performance, while the automatic adjustment of 

inertial coefficient of adaptive inertial coefficient method speeds up the convergence speed of the algorithm, 

and enhances the convergence performance of the algorithm. 

 

Figure 5: Particle swarm algorithm best individual corresponding function value contrast 

4.2 Analysis on algorithm 

The same problem can be solved by different algorithms, and the quality of an algorithm will affect the 

efficiency of the algorithm and even the program. The purpose of algorithm analysis is to choose the 

appropriate algorithm and improve the algorithm. The evaluation on an algorithm is mainly considered from 

the time complexity and the space complexity. There are three methods for calculating the complexity of the 

algorithm, i.e. the direct calculation method, the circuitous calculation method, and the recursive calculation 

method. This Paper mainly uses the direct calculation method to analyze the algorithm from the perspective of 

time complexity. Time complexity is the time cost of the algorithm, and is the frequentness sum of all the 

statements in the algorithm. However, in the actual calculation process, it often requires to find out the 

statement with the highest frequency in the algorithm and calculate the frequentness. 

For the program written through comparison, it can be found that the statements with maximum frequency 

based on the basic particle swarm optimization algorithm and the improved particle swarm algorithm are all 

the updated statements of iteration optimization part. The frequentness is related to the number of iterations 

and the population size, equals to the product of the number of iterations and the population size, which 

shows that the time complexity of these two is in the same order of magnitude. For ease of evaluation, this 

Paper applies the notebook computer with 2G memory, 32-bit operating system and Intel(R) Core(TM) i3 CPU 

conducts the analysis on the operation time of the algorithm. After many operations, the data shown in Table 1 

was obtained. 

Table 1: the time-consuming of the improved particle swarm optimization 

Algorithm name Single run time Minimum number of iterations 

Basic particle swarm 

optimization (PSO) algorithm 

0.167 8 

 

111 

Improved particle swarm 

optimization (PSO) algorithm 

0.063 9 

 

29 

 

965



From the data in Table 1, we can see that the time-consuming of the improved particle swarm optimization 

algorithm is significantly lower than that of the basic particle swarm algorithm, showing the effectiveness and 

rapidity of the improved algorithm. 

4.3 Optimal path correction and optimization 

On the basis of finding the shortest rough path, for there is no significant change in the flying height of the 

vertical direction UAV, it can be assumed that the UAV fly horizontally at a certain altitude at a constant speed 

and avoid flying over the known fixed threats. Therefore, the 3D path can be projected onto the 2D plane of 

XOY. During the path optimization process, such factors as minimum turning radius and path cost of the UAV 

should be considered, and search the point with the minimum turning radius and cost around the extracted 

path points through the improved particle swarm algorithm, and finally use the least square method to fit the 

optimal path. Set the experimental parameters at "vmin = 80 km / h", "nymax = 3", the evolutionary generation 

of the improved particle swarm algorithm at "20" and the population size at "5", and conduct the simulation 

verification by MATLAB, drawing the distance to the optimal flight path is 39.350 7 km. 

5. Conclusions 

This Paper mainly conducts the research for the traditional oilfield patrolling UAV path planning based on the 

particle swarm algorithm, through which understand the deficiencies, and then, for the purpose of 

improvement, proposes a leapfrog particle swarm optimization algorithm. Firstly, after clarifying the main ideas 

of the complex network theory and algorithm, this Paper introduces the basics of path planning. After that, 

Dijkstra algorithm is used to search for rough paths, and the search results show that, starting from the 

starting point No. 36 point, passing through No. 10,9,11,15 and so on point, reach the target point, No. 37 

point, getting the shortest distance of 39.328 9 km. Afterwards, the simulation results obtained in this Paper 

show that the improved particle swarm algorithm can realize the faster convergence to the minimum, and can 

reach the theoretical minimum value of the function, showing a good algorithm performance, while the 

automatic adjustment of inertial coefficient of adaptive inertial coefficient method speeds up the convergence 

of the algorithm and enhances the convergence performance of the algorithm. In addition, this paper also 

analyzes the algorithm analysis, the optimal path correction and optimization, and then shows the 

effectiveness and rapidity of the algorithm through the data in Table 1. 

Reference 

Cheng Z., Tang Y.X., Liu Y.L., 2012, 3-D path planning for uav based on chaos particle swarm optimization. 

Applied Mechanics & Materials, 232, 625-630, DOI: 10.4028/www.scientific.net/amm.232.625 

Geng Q., Zhao Z., 2013, A Kind of Route Planning Method for UAV Based on Improved PSO Algorithm, China 

Conference on control and decision-making, 2328-2331, DOI: 10.1109/ccdc.2013.6561326 

Liu K., Zhou J.Q., Guo X.H., 2013, Path planning research for unmanned air vehicle based on improved 

particle swarm algorithm, Journal of North University of China, 34(4), 441-447, DOI: 

10.4236/oalib.1104587 

Liu Y., Zhang X., Guan X., Delahaye D., 2016, Potential odor intensity grid based uav path planning algorithm 

with particle swarm optimization approach, Mathematical Problems in Engineering, 2016(2), 1-16, DOI: 

10.1155/2016/7802798 

Phung M.D., Cong H.Q., Dinh T.H., Ha Q., 2017, Enhanced discrete particle swarm optimization path planning 

for uav vision-based surface inspection, Automation in Construction, 81, 25-33, DOI: 

10.1016/j.autcon.2017.04.013 

Roberge V., Tarbouchi M., Labonte G., 2012, Comparison of parallel genetic algorithm and particle swarm 

optimization for real-time uav path planning, IEEE Transactions on Industrial Informatics, 9(1), 132-141, 

DOI: 10.1109/tii.2012.2198665 

Wang E., Tang Y., Wang Y., 2014, Real-time path planning strategy for uav based on improved particle 

swarm optimization, Journal of Computers, 9(1), DOI: 10.4304/jcp.9.1.209-214 

Xie R., Wang X., Wang X., Wei H., 2012, UAV flight performance optimization based on improved particle 

swarm algorithm, International Conference on Intelligent Robotics and Applications, 7506, 396-403, DOI: 

10.1007/978-3-642-33509-9_39 

966