Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 3, No. 1, 2023 113 UAV 3D path planning based on improved grey wolf optimization algorithm Qunjie Liu*, Hongxing Wang School of Physics and Electronic Information Engineering, Henan Polytechnic University, Jiaozuo 454003, China * Corresponding author: Qunjie Liu (Email: emmaliusun@foxmail.com) Abstract: In this paper, an improved grey wolf optimization algorithm is proposed for the research of UAV path planning in a complex 3D environment. Firstly, a new nonlinear convergence factor is proposed to balance the performance of global search and local development. Secondly, a cubic chaotic mapping is adopted to initialize the wolf population, diversifying the population while improving the uniformity of the population distribution. Finally, a mutation operation is introduced to mutate the individual gray wolf, which enhances the ability of the algorithm to jump out of the local optimum. Three-dimensional environment model is established by elevation data. The simulation results show that the optimal fitness of the improved algorithm is improved by 2.34% compared with that before the improvement, which proves the effectiveness of the algorithm in this paper. Keywords: UAV; Path planning; Grey wolf optimization algorithm; Cubic chaotic; Mutation operator. 1. Introduction In recent years UAVs have been widely used in many fields such as military[2], wireless communication[3], maritime target search[4], logistics[5], and agricultural plant protection[6]by virtue of their low cost and high operability[1].Path planning algorithms are one of the key points of UAV technology, and intelligent optimization algorithms are robust, simple to implement and easy to combine with other algorithms[7],and have been applied by many scholars to research in complex environments such as high latitudes and multiple constraints. Grey Wolf Optimizer (GWO) is an emerging intelligent optimization algorithm proposed in 2014 with the advantages of simple structure and few parameters[8], which is gradually applied in the research of UAV path planning. The literature[9]first applied the grey wolf optimization algorithm to UAV path planning and verified its feasibility and effectiveness in a two-dimensional simulation environment. In a subsequent study, a hybrid discrete intelligence algorithm based on the grey wolf optimization algorithm was proposed in the literature[10]by introducing a central position and stagnation compensated grey wolf update operation. It is used to solve a multi-UAV path planning problem with energy constraints. The literature[11]combines an efficient Bayesian form of grey wolf optimization to propose an algorithm for finding the optimal trajectory in the presence of motion obstacles to solve UAV path planning in uncertain environments. In the literature[12], a grey wolf-based algorithm for constrained optimization problems was proposed in combination with communication mechanisms and horizontal comparison strategies, and applied to path finding and collision avoidance of UAVs in 3D environments. In the literature[13], an improved adaptive grey wolf optimization algorithm is proposed for 3D path planning of UAVs under earthquake disaster areas. The convergence of the algorithm is improved by adaptively adjusting the convergence factor and weight factor to update the individual positions. The literature[14]divides the search space into multiple dimensionality-reduced subspaces and proposes a parallel co-evolutionary grey wolf optimization algorithm to overcome the local optimality problem of the grey wolf optimization algorithm due to the increase in the dimensionality of the search space. Although the Grey Wolf optimization algorithm is simple in structure, it has some problems such as premature convergence in dealing with large-scale complex optimization problems[15], which directly affects the quality of path planning results. Therefore, for path planning in complex 3D environments, an improved algorithm is proposed in this paper. A new non-linear convergence factor is used to slow down the convergence speed in the later period of the algorithm, and a cubic chaotic mapping with both randomness and regularity is used to improve the initialization of the algorithm. Combined with genetic algorithm, mutation operation is introduced to balance the global search and local optimization ability. 2. Environment Modeling The establishment of the environment model is the basis for path planning. The digital elevation model has the characteristics of high accuracy and real-time display, so this paper uses the digital elevation information as the basis to establish a 3D environment model based on real terrain, as shown in Figure 1. Figure 1. Environment Modelling 114 3. Improved Grey Wolf Optimization Algorithm The grey wolf optimization algorithm is a bionic algorithm derived from the hunting pattern of the grey wolf. Grey wolves are divided into four classes, from high to low, namely ∂, β, γ and ω. Grey wolves hunt under the leadership of ∂ wolves, which mainly consists of the following three processes. (1) Encircling | ( ) ( ) |pD C X t X t= − (1) ( 1) ( )pX t X t A D+ = − (2) 1 2 2 2 ( ) 2*(1 / ) A a r a C r a t t T  = −  =  = − (3) The Equation (1) represents the distance between the prey and the grey wolf, and the grey wolf updates its position according to Equation (2). where ( )X t and ( )pX t represents the positions of the grey wolf and the prey respectively; A and C in Equation (3) are the coefficient vectors, a is the convergence factor; t and T denote the current number of iterations and the total number of iterations respectively, 1r and 2r are random vectors between [0,1]. Hunting After the above process, the updated positions of the three grey wolves ∂, β and γ are regarded respectively as the optimal, sub-optimal and sub-optimal solutions for the current location of the prey. The other grey wolve individuals β, γ and ω update their positions according to the optimal solution ∂ wolf, as shown in Equation (4). 1 2 3 | | | | | | D C X X D C X X D C X X              = − = − = − (4) where , ,aD D D  represent the distance between ∂, β, γ wolves and other individuals , ,aX X X  represent the current position of ∂, β, γ wolves, 1 2 3, ,C C C are random vectors, and X is the current position of the grey wolf. 1 2 3 ( 1) 3 X X X X t + + + = (5) 1 1 2 2 3 3 ( ) ( ) ( ) X X A D X X A D X X A D        = −  = −  = − (6) where the Equation (5) represents the final position of the grey wolf, 1 2 3, ,X X X represents the direction and step size of ω wolves advancing towards ∂, β, γ, as defined by Equation (6). (2) Attacking and Searching The grey wolf algorithm simulates the process of approaching the prey by gradually decreasing the value of a ,and the corresponding value of A in Equation (3) also fluctuates between the interval [-a, a]. During the iteration, the grey wolves gather and attack the prey when 1A ,which expressed as exploitation, and may fall into local optimum. When 1A ,the grey wolves spread out and expand their search in order to find more suitable prey, and achieve global optimum which expressed as exploration. 3.1. Improved Convergence Factor From the above, it can be seen that the development and exploration performance of the grey wolf optimization algorithm depends on A ,while A depends on the convergence factor a .In practice, as ∂ wolf does not necessarily represent the optimal solution, the algorithm is required to have stronger exploration ability at a later stage to enhance the diversity of solutions, thus ensuring the global optimality of the solution. However, a linearly decreasing convergence factor cannot satisfy this requirement, so a new non-linear convergence factor is proposed in this paper, as shown in Equation (7).Comparing the convergence factor of this paper with that of the original Grey Wolf optimization algorithm, the result is shown in Figure2, indicating that the convergence factor of this paper decays slowly in the early stage and converges quickly in the later stage, giving the algorithm the ability to fully search the solution space in the early stage and quickly converge to the optimal solution in the later stage, thus satisfying the requirement of balancing global exploration and local exploitation. 1 ( / ) 31 (exp )*(exp 1)t ma −= − − (7) where t and m are the number of current iterations and total iterations respectively. Figure 2. Comparison of convergence factor curves before and after improvement 3.2. Improved Initialization For grey wolf optimization algorithm, the better the uniformity the easier it is to find the optimal solution[16]. The traditional grey wolf optimization algorithm uses a random way to initialize the wolf pack, which is prone to produce individuals with low adaptability and is not conducive to UAV path planning, while the cubic chaos mapping just satisfies the uniformity and randomness of the distribution. Therefore, the cubic chaos mapping is used for initialization in this paper, as shown in Equation (8). 3 1 4* 3*i i iy y y+ = − (8) 115 where 1 1, 1, 0,1,...,i iy y i N−    = ,and N is the total number of populations. The steps of the cubic chaos initialization applied to the Grey Wolf optimization algorithm are shown below: (1) Randomly generate individual grey wolves 1 2 3( , , ,..., )dH h h h h= , d represents the dimension of the solution space , each dimension taking values in the range [-1,1]. (2) Each individual grey wolf generated above is iterated N-1 times according to Equation (8), resulting in a total of N individual grey wolves. (3) Map into the solution space according to Equation (9). 0.5*( )* ( 1)i lb ub lbX X X X y i= + − + (9) where iX represents the position of the individual grey wolf, ubX and lbX represent the upper and lower boundaries of the solution space. 3.3. Mutation Operation In order to enhance the ability of the grey wolf optimization algorithm to jump out of the local optimum, a mutation operation inspired by genetic algorithm is introduced into the algorithm , in which the optimal solution represented by wolf  is used as a guide and some grey wolf individuals are randomly selected and subjected to partial random mutation according to Equation (10). 1 2 *i i i i mut r rX X K X X= + − (10) where i mutX represents the location of the mutated grey wolf, iX  stands for the current position of  wolf', 1 i rX and 2 i rX are random vectors of individual wolves’ locations, and K is a random number between 0 and 1. The flow of the improved Grey Wolf optimization algorithm is shown in Figure 3. Figure 3. The Flow of the Improved Grey Wolf Optimization Algorithm 4. Experimental simulation and analysis To verify the feasibility of the improved algorithm, simulation experiments were set up on the Matlab2021a platform. Elevation data of 35 degrees north latitude and 50 degrees east longitude were selected to construct a realistic 3D environment model, and additional obstacles were simulated by adding cylinders and cubes on top of this. The starting coordinates of the path planning were set as (200, 100, 500) and the ending coordinates as (2500, 2300, 450). The improved algorithm in this paper was compared with the original algorithm GWO, the SPSO algorithm in the literature[17]and the grey wolf optimization algorithm using the Cauchy mutation operator, the results are shown in Figure 4 and Figure 5. Figure 4. Path Planning Result under View 1 Figure 5. Path Planning Result under View 2 Figure 6. Iteration Curve Graph As can be seen from the iteration curves in Figure 6, the improved algorithm in this paper is able to converge rapidly 116 in the early stages, improving the upfront efficiency of the algorithm and not falling into a local optimum in the later stages when convergence is slower, achieving the best fitness value among the four algorithms. Table 1. Simulation experimental data of the four algorithms Path length cost Obstacle cost Algorithm in this paper 3698.9884 0.0000 GWO algorithm 3784.3128 3.2740 SPSO algorithm 3768.2688 0.0000 GWO algorithm using Cauchy mutation 3979.2679 0.9017 Table 1records the path length cost and obstacle cost data for 100 iterations of the four algorithms. From the table, it can be seen that, compared with the other two algorithms, the path obstacle cost planned by the improved algorithm in this paper and SPSO algorithm is zero, which proves to be able to meet the obstacle avoidance requirements. Moreover, the algorithm in this paper is able to plan shorter paths, and the path length cost is improved by 2.25%, 1.84% and 7.04% compared to the GWO algorithm, the SPSO algorithm and the GWO algorithm using Cauchy mutation respectively. 5. Conclusion For the UAV path planning problem in complex 3D environment, an improved grey wolf optimization algorithm is proposed in this paper. Improvements are made to the convergence factor and the initialization method of the algorithm, and the mutation operation in genetic algorithm is introduced. An environmental model is established using elevation data for experimental simulation, and the four algorithms are compared experimentally. The simulation results prove that the algorithm in this paper can achieve sufficient search in the early stage, and the introduced mutation operation empowers the algorithm to jump out of the local optimum in the late stage, improves the premature problem of the traditional Grey Wolf optimization algorithm in the face of high dimensional complexity, balances the global search and local exploitation ability, and proves the feasibility of the improved algorithm in this paper. In this study, the problem of algorithm running time was not taken into account, and further research will be conducted subsequently to address the planning efficiency of the algorithm. References [1] LIU Q J, SHU L S, LIU G, et al. A Survey of Low Altitude UAV Path Planning Algorithms[J/OL]. Advances in Aeronautical Science and Engineering. 2023:1-11. [2] TAN S G. Research on UAV Path Planning in Simulated Battlefield Environment[D]. Dalian University of Technology, 2021. [3] ZHANG T, ZHANG J, TANG H Y, et al. Energy minimization communication in UAV-aided wireless powered communication network*[J]. Transducer and Microsystem Technologies. 2021,40(12):44-48 [4] WANG K Z, ZHOU X L, LIN M T, et al. Cooperative search algorithm of multi-UAV for sea targets in limited communication range*[J]. Transducer and Microsystem Technologies, 2022,41(12):143-146+157. [5] XU W H, LIAO S C, ZHANG G R, et al. 3D Path Planning of Logistics UAV Based on Improved Theta* Algorithm in Metropolitan Area[J/OL]. Computer Engineering and Applications. 2023:1-9. [6] SUN K, WU K H, WANG Y T, et al. Research on obstacle avoidance system of plant protection UAV based on millimeter wave radar[J]. Transducer and Microsystem Technologies, 2020,39(06):73-76.. [7] WANG P F. Research on Multi-UAVs Path Planning Based on Novel Swarm Intelligence Algorithm[D]. Nanjing University of Aeronautics and Astronautics, 2021. [8] ZHANG X F, WANG X Y. Comprehensive Review of Grey Wolf Optimization Algorithm[J]. Computer Science, 2019,46(03):30-38. [9] ZHANG, SEN, ZHOU, et al. Grey wolf optimizer for unmanned combat aerial vehicle path planning[J]. Advances in Engineering Software, 2016, 99:121-136. [10] HUANG G, CAI Y, LIU J, et al. A Novel Hybrid Discrete Grey Wolf Optimizer Algorithm for Multi-UAV Path Planning[J]. Journal of Intelligent & Robotic Systems, 2021, 103(3):1-18. [11] RADMANESH M, KUMAR M, SARIM M. Grey wolf optimization based sense and avoid algorithm in a Bayesian framework for multiple UAV path planning in an uncertain environment[J]. Aerospace Science and Technology, 2018, 77:168-179.. [12] JIANG W, LYU Y, LI Y, et al. UAV path planning and collision avoidance in 3D environments based on POMPD and improved grey wolf optimizer[J]. Aerospace science and technology, 2022(Feb.):121. [13] ZHANG W, ZHANG S, WU F, et al. Path Planning of UAV based on Improved Adaptive Grey Wolf Optimization Algorithm[J]. IEEE Access, 2021, PP(99):1-1. [14] JARRAY R, Al-DHAIFALLAH M, REZK H, et al. Parallel Cooperative Coevolutionary Grey Wolf Optimizer for Path Planning Problem of Unmanned Aerial Vehicles. Sensors. 2022; 22(5):1826. [15] GAI W D, QU C Z, LIU J, et al. An Improved Grey Wolf Algorithm for Global Optimization[C]. Proceedings of the 30th China Conference on Control and Decision Making (2)(CCDC),2018:1097-1101.2018:5. [16] OU Y, ZHOU K Q, YIN P F, et al. Improved grey wolf algorithm based on dual convergence factor strategy[J/OL]. Journal of Computer Applications. 2023:1-10. [17] MD P, HA Q P. Safety-enhanced UAV path planning with Spherical Vector based Particle Swarm Optimization[J]. Applied Soft Computing, 2021(2):107376.