A Novel Improved Bat Algorithm in UAV Path Planning

Na Lin,Jiacheng Tang,Xianwei Li and Liang Zhao,

Abstract:Path planning algorithm is the key point to UAV path planning scenario.Many traditional path planning methods still suffer from low convergence rate and insufficient robustness.In this paper,three main methods are contributed to solving these problems.First,the improved artificial potential field(APF)method is adopted to accelerate the convergence process of the bat's position update.Second,the optimal success rate strategy is proposed to improve the adaptive inertia weight of bat algorithm.Third chaos strategy is proposed to avoid falling into a local optimum.Compared with standard APF and chaos strategy in UAV path planning scenarios,the improved algorithm CPFIBA(The improved artificial potential field method combined with chaotic bat algorithm,CPFIBA)significantly increases the success rate of finding suitable planning path and decrease the convergence time.Simulation results show that the proposed algorithm also has great robustness for processing with path planning problems.Meanwhile,it overcomes the shortcomings of the traditional meta-heuristic algorithms,as their convergence process is the potential to fall into a local optimum.From the simulation,we can see also obverse that the proposed CPFIBA provides better performance than BA and DEBA in problems of UAV path planning.

Keywords:UAV path planning,bat algorithm,the optimal success rate strategy,the APF method,chaos strategy.

1 Introduction

For the last few decades,UAV(unmanned aerial vehicles)has been widely used in commercial[Adarsh,Raghunathan,Jayabarathi et al.(2016)],military[Anderson,Beard and McLain(2005)],delivery[Dorling,Heinrichs,Messier et al.(2016)],etc.The main advantages of UAV[Kulkarni and Venayagamoorthy(2010)]can be summarized as its small size,light weight,low fuel cost,and the strong suitability to the environment.The UAV path planning problem[Pehlivanoglu,Baysal and Hacioglu(2007)]directly determines the efficiency and QoS(Quality of Service)of the mission that UAV carries out[Al-Dubai,Zhao,Zomaya et al.(2015)].As to reduce fuel consumption and subside the mission execution time,it is with significant demand to design an adaptable UAV flight path.

The problem of UAV path planning generally refers to the process to search a flight path track from the starting point to the target point,which satisfies with the UAV performance criteria under certain constraints[Jiang and Liang(2018)].Obstacle avoidance[Wu,Li,Zuo et al.(2018)]is a considerable process in path planning.Obstacle avoidance is divided into static obstacle avoidance[Conde,Alejo,Cobano et al.(2012);Razzaq,Xydeas,Everett et al.(2018)]and dynamic obstacle avoidance[Alejo,Cobano,Heredia et al.(2014);Chen,Chang and Agate(2013)].Static obstacle avoidance mainly targets on terrain and nonflyable area.Dynamic obstacle avoidance deal with the mobile threat and other moving UAVs in the mission.Path planning algorithm is a key part of the UAV path planning problem.The original path planning algorithms are followed as Dubins path[Shanmugavel,Tsourdos,White et al.(2010)],reactive path selection[Hall and Anderson(2011)]and vision-based navigation[Courbon,Mezouar,Guénard et al.(2010)],etc.These methods require terrain information fully and usually cannot get the optimal path to guarantee convergence of the path planning algorithm.To overcome these shortcomings,the heuristic algorithm is proposed.The representative heuristic algorithms are followed as A*algorithm[Fan,Liang,Lee et al.(2014)],RRT algorithm[Tahir,Qureshi,Ayaz et al.(2018)]and simulated annealing algorithm[Zhao,Zeng and Liu(2018)].These heuristic algorithms still have shortcomings in the execution efficiency and stability.With the progress of random search theory,meta-heuristic algorithm[Portas,Torre,Moreno et al.(2018)]is proposed to make up the disadvantages of standard heuristic algorithms.By proposing randomization strategy and biological intelligence,swarm intelligence algorithm[Osaba,Yang,Diaz et al.(2016)]is proposed to solve optimization problems under certain constraints.The swarm intelligence algorithms highly fit the problems of UAV path planning.The representative applications of meta-heuristic algorithm for UAV path planning are Particle Swarm Optimization(PSO)[Tang,Gao,Kurths et al.(2012)],Artificial Bee Colony Algorithm(ABC)[Yan(2018)],Ant Colony Optimization(ACO)[Shang,Karungaru,Feng et al.(2014)],Genetic Algorithm(GA)[Kuroki,Young and Haupt(2010)],Bat Algorithm(BA)[Tharakeshwar,Seetharamu and Prasad(2017)],Grey Wolf Algorithm(GWA)[Zhou,Li and Pan(2016)],etc.Meta-heuristic algorithms utilize the valid information in search space.Also,the convergence rate and solution stability improve a lot than previous heuristic algorithms.However,it has been proved that most meta-heuristic algorithms focus on problems of UAV path planning still have performance shortcomings,which mainly reflected on solution accuracy[Fu,Ding,Zhou et al.(2013)],path track smoothing[Ghosh,Panigrahi and Parhi(2017)]and occasionally falling into local optimum.The standard meta-heuristic algorithms commonly have particle velocity update equation to control the swarm movements.The velocity in the next generation is related to the velocity in the last generation and several special velocity-changing strategies.The velocity of swarm influences the global search and local search process.To balance the global search and the local search,the inertia weight is added into the particle velocity update equation.Higher inertia weight focuses on global search,allowing the particle to traverse the whole searching space to move closer to the global optimum.Lower inertia weight focuses on local search while particles search around the optimal solution to accurately locate the global optimum and calculate the fitness value.Inertia weight has many forms as fixed value weight[Portas,Torre,Moreno et al.(2018)],linear-increasing weight[Duan,Luo,Shi et al.(2013)],linear-decreasing weight[Huang,Wang,Hu et al.(2011)],roulette strategy-based weight[Zhai,Jia and Wang(2018)],etc.These inertia weight strategies improve the search efficiency but cannot precisely discriminate the boundary conditions of the global search process and local search process so that it may fall into local optimum and get lower convergence accuracy and lower proceeding rate.To overcome these shortcomings,the adaptive inertia weight is raised to make the particle velocity related to the solution success rate during the whole search process.Adaptive inertia weight based on the solution success rate effectively balances the global search process and the local search process,which makes the swarm get much higher solution speed and maximally avoid falling into a local minimum.

In the UAV path planning problem,to make full use of the terrain information and the UAV flight parameter is with great significance.By applying chaos method and potential field strategy,we choose chaos strategy[Li,Wu,Yu et al.(2016)]and the APF method[Wang,Zhu,Wang et al.(2016)]to improve our path planning algorithm.Meanwhile,the improved swarm intelligence algorithms satisfy the planned flight path,confirming the terrain constraints and the UAV flight characteristics.We can conclude an appropriate method solving the UAV path planning problem and improve the solution speed and accuracy is to combine chaos strategy and APF method with the improved swarm intelligence algorithm.Inspired by these previous studies,this paper proposes an improved bat algorithm CPFIBA(The improved artificial potential field method combined with chaotic bat algorithm)to generate a better solution performance in problems of UAV path planning.This paper also compares the proposed combined algorithm with the standard bat algorithm(BA)and the bat algorithm based on differential evolution(DEBA).The experimental results demonstrate that the proposed algorithm CPFIBA produce a more feasible solution in 2D and 3D problems of UAV path planning than BA and DEBA in various considerations under the same constraints.

The main contributions of this paper are proposed as follows:

1)The improved artificial potential field(APF)method is adopted to accelerate the convergence of the bat's position update process.

2)The optimal success rate strategy is proposed to improve the adaptive inertia weight of bat algorithm.It also balances the global search and the local search and makes the algorithm with great robustness.

3)The chaos strategy is adopted in the initial contribution of bat swarms.It makes the search process avoid from local optimum and updates the convergence rate.

The remainder of the paper is organized as follows.In Section 2,the related work about the research area is detailed.Section 3 mainly analyzes the modelling and constraints setting of UAV path planning tasks.Section 4 is about the details of CPFIBA.Section 5 is the experimental results and analysis.In Section 6 we conclude this research and give a vision for future work.

2 Related works

The meta-heuristic algorithm is widely used by researchers to solve the UAV path planning problem.Previous research focuses on performance on comparing the performance of different meta-heuristic algorithms at standard test functions.As the optimal process aims to find the global minimum of standard test functions which have the same property compared with the problems of UAV path planning after flight cost function modelling and constraints setting.The capability of the specific meta-heuristic algorithm is the prime factor in choosing a kernel algorithm in UAV path planning process.According to these theories,it is essential to select a good performance meta-heuristic algorithm to be the kernel algorithm in our proposed method.

BA is firstly proposed by Yang[Yang(2010)].Yang proves that BA performs much better than PSO and GA regarding to their convergence accuracy and proceeding efficiency.BA also has the advantage of faster execution speed,less operating parameters and more potential to combine with other swarm intelligence algorithm dealing with multidimensional optimal search problems.BA and its enhanced algorithms have been widely applied in problems of UAV path planning.

Wang et al.[Wang,Chu and Mirjalili(2016)]proposes a combined algorithm the bat algorithm based on differential evolution(DEBA).The mutation process of DE is used to improve the original bat swarm distribution with a probability 1-r originally by using random walk strategy.By applying these strategies,the population information of the bat population is fully exploited,and the exploration ability is relatively raised.In Wang's research,a mathematical model of UAV path planning task is proposed.This model makes equivalent conversion between flight cost and fitness function under constraints.The 2D and 3D simulating environment experiments certificate that the proposed DEBA is more effective and feasible in UAV path planning tasks than other swarm intelligence algorithms such as ACO[Shang,Karungaru,Feng et al.(2014)],BBO[Osaba,Yang,Diaz et al.(2016)],DE[Kuroki,Young and Haupt(2010)],ES[Fan,Liang,Lee et al.(2014)]and PSO[Tang,Gao,Kurths et al.(2012)].DEBA is a quite effective path planning method compared with BA and other standard swarm intelligence algorithms.DEBA has great performance on multi-objective optimization problems,while UAV path planning problem is one of the multi-objective optimization problems.Hence after extensive research,we choose DEBA(Differential Evolution Bat Algorithm)as our kernel algorithm in our proposed combined algorithm CPFIBA.However,the success rate of completing the path planning mission is not high enough.The detailed orographic environment information is not fully used.The standard BA should be proved,while the efficient search strategy of path planning should be combined for further algorithm performance improvement.

Based on the studies above,this paper proposes the success rate inspired by Chakri et al.[Chakri,Khelif,Benouaret et al.(2017)]to change the velocity updating equation of bat individuals.Meanwhile,chaos strategy[Li,Wu,Yu et al.(2016)]is used to initialize the distribution of bat individuals in the search space,and the APF method[George and Ghose(2012)]is used to accelerate the swarm individual's movements and raise the convergence rate of the global search process.The starting point initiates the gravitational field while terrain and obstacles initiate the repulsion field.Finally,an improved bat algorithm based on APF method and chaos strategy(CPFIBA)is proposed to solve and improve the 2D and 3D problems of UAV path planning under certain flight constraints.The standard BA and DEBA are used for comparative analysis,in order to verify the excellent performance of our proposed combined algorithm CPFIBA.

3 The problem modeling of UAV path planning

UAV path planning is defined as the process of finding a path from the start point to the end point while meeting with the performance requirements of the UAV under some specific UAV flight constraints.It aims to search the extreme value of multi-objective function under the condition of multiple constraints.The mathematical model of the UAV path planning problem is proposed as follows.

3.1 Flight cost function

The cost function[Wan,Wang,Ye et al.(2016)]in problems of UAV path planning can be divided into three parts:the path length cost,the threat cost,and the fuel consumption cost.The total cost function is denoted by J.The minimization objective function J is defined in Eq.(1).

JLrefers to the length of the flight path cost,JTrefers to the threat cost,JFrefers to the cost of fuel consumption to keep UAV's height.k1,k2are positive and meet with the following formula 0≤k1≤1,0≤k2≤1.

The path length cost JLis defined in Eq.(2).L is the length of the total flight path and lijis the length of the track segments.

The threat cost JTare defined in Eq.(3).tkis the threat factor.It is also a measure of threat level between threat source and the UAV node.Ntrepresents for the total number of threat sources,and the coordinate of UAV is(x,y,z).The coordinate of the threat source center is(xk,yk,zk).

The definition of fuel consumption cost JFis defined in Eq.(4).K represents for the cost of fuel consumption that UAV travels per unit length during the flight mission.H is the altitude of the UAV flight safety loop and,the flight altitude of a UAV should not exceed this height.W0indicates the energy cost of UAV to maintain in the certain altitude,where? is the current height of UAV and H is the height of flight safety circle.

3.2 UAV flight constraints

UAV needs to obey its dynamic constraints during the flight mission,so the planning path should meet with several constraints[Wang,Chu and Mirjalili(2016)].In order to explain these constraints intuitively,we select some standard waypoints as a model to illustrate the flight constraints.We assume A(xi-1,yi-1,zi-1)as the previous waypoint and B(xi,yi,zi)as the current waypoint.C(xi+1,yi+1,zi+1)is the forward waypoint,and a→=[xi-xi-1,yi-yi-1]Tis recorded as the track point migration vector.

UAV need to climb or dive across terrain and obstacles.This paper assumes that the maximum climb or dive angle is θ,then the climb or dive angle constraint of UAV is defined in Eq.(5).When UAV try to avoid terrain and obstacles,its flight characteristics should be satisfied.And the planning path should be under the turning radius constraints to guarantee the planning path able to fly.The minimum turning radius is proposed in Fig.1.

Figure 1:Turn radius constraints

Path angle φ=2φ.The minimum corner can be defined in Eq.(6).rminin the formula is the radius of the minimum turning circle while rdis the shortest distance between the turning node Vjand the edge point B of the obstacle.Flight height constraint depends on the specific characteristics of the UAV flight mission.

In order to reduce fuel consumption and ensure the planning path is flexible as much as possible,there should be a maximum height limit ? ≤ H.In this formula,? is the absolute height that UAV to the ground while H is the height the off-light safety circle.In order to make promptly feedback to the terrain changes,the relative height of the terrain surface should satisfy ? ≥ ?min,while ?minis the current terrain altitude and ? is the absolute height that UAV to the ground.

3.3 Obstacle detection and avoidance

UAV uses its sensors to detect stationary obstacles and dynamic obstacles[Jiang and Liang(2018)].After obstacles are identified,the obstacle avoidance mechanism is one of the key factors that affect the effectiveness of the path planning route.The schematic diagram of UAV obstacle avoidance is proposed in Fig.2.

In order to satisfy the constraints of UAV flight direction and yaw angle limits,this paper use path track of motions in a Polar coordinate to illustrate the obstacle avoidance mechanism.In Fig.2,O is the starting point of the track and G is the ending point of the track.The track segment between L1and Lkis participated into several adjacent segments.The starting point of each sub-track segment is marked with square nodes.

Figure 2:UAV obstacles avoidance

The mechanism of measuring and avoiding threats between every two track points is visualized in Fig.3.Sub-path lijwill be further segmented to calculate the threat costaccording to the number of threat sources.Generally,the threat cost is expressed in Eq.(7).

NTrepresents for the number of the threat sources.tjrepresents for the threat weight factor.dk(i,j)represents for the straight-line distance between the start points i and the end point j of thek-th sub-path segment.

Figure 3:Threat cost calculation

The obstacle avoidance process is aimed to avoid collisions between the flying UAV and obstacles.The minimization of the threat cost under limited conditions is a proper way to ensure the UAV away from the obstacles.

By using the proposed algorithm CPFIBA to solve the obstacle avoidance problems,the planned flight path can effectively avoid the static obstacle in search space.For the avoidance of dynamic obstacles,it needs the sensors of UAV to recognize and urgently evade the dynamic obstacles.After these processes,UAV returns to the flight path which is also called path follow-up operation.

3.4 Flight path smooth strategy

The result of the planning path needs to be tested for the flying ability under the flight constraints.The planned flight path has the feature of the Levy flight track with irregular turning.Therefore,an effective path smoothing method is needed for flight path smooth strategy.

In this paper,we use the b-spline curves method[Nikolas,Valavanis,Tsourveloudis et al.(2003)]for the flight path smooth process.Suppose the flight path curve needed to be smoothed a line segment from A to B to C in the Cartesian system,as shown in Fig.4.

Figure 4:The b-spline curves smooth

After b-spline curves smooth process,the line segment ABC with an arc-segment will be replaced by the smooth curvewhich can be directly used as a flight planning path.This path smooth strategy effectively solves the path smoothing problem.

4 The improved artificial potential field method combined with chaotic bat algorithm(CPFIBA)

4.1 Introduce to bat algorithm

The bat algorithm is inspired by bats in nature avoiding natural enemies and capture prey by echolocation.For a virtual bat in thed-dimensional search space,the updating formula for the location xiand the velocity viof the bat individual at time node t is shown as follows.

For the update of the vocal frequency of Eq.(8),β follows a uniformly distributed variable and satisfies β∈[0,1].fmaxand fminare the maximum and minimum values for the initial setting for bat vocalize frequency.x*in Eq.(9)is the current global optimal solution,this solution is the optimal fitness value of all individuals in the bat population.The individual bat measures its acceleration to the optimal solution according to its proximity locationto the global optimal solution x*.The speed of the bat individual in the next moment is related with its approximation to the global optimal solution.In addition to the acceleration process,the bat individual inertia is also taken into consideration.The speed at the next moment is,which is affected by the speed of the previous moment.Eq.(10)describes the process of how the bat swarms migrate as their position and velocity changed(See line 5 in Algorithm 1).

The above is the iterative process that bats population follows in the global search,while the bat individual near the optimal global solution uses the random walking rule to generate a partial new solution as shown in Eq.(11).In Eq.(11),ε∈[-1,1]is a random number whileis the average volume of bats population at time node t.

The updating formula of the vocalize frequency and loudness at this time node is described in Eqs.(12)to(13).α and γ are both constants real numbers and are usually set as α=γ=0.9(See line 13-15 in Algorithm 1).From the equation,we can see that while the bat approaches the optimal solution infinitely,the vocalization emission decays continuously and finally pauses.Meanwhile,the vocalize frequency asymptotically closes to the initial pulse frequencywith iteration gradually raising.

4.2 Details of the proposed algorithm

The standard bat algorithm has the advantages of fast convergence speed,high robustness,easy to implement,etc.However,it is proved that the standard BA has defects of convergence accuracy and quickly falling into the local optimal.Under these considerations,we make three main improvements toward to the standard bat algorithm and combine the characteristics of the UAV path planning problem.The firstly is to combine the APF method in the global search process.The second is to update the inertia weight of the velocity iteration formula in the standard bat algorithm,in which the optimal success rate strategy is firstly proposed to control the inertia weight.This proposed strategy successfully balances the global search process and the local search process.Thirdly,chaos strategy is introduced to randomize the initial distribution of the bat's population to accelerate the proceeding speed of the searching process.These three improvements are discussed in details in Sections 4.2.1 to 4.2.3.The pseudo code of CPFIBA is illustrated in detail in Algorithm 1.

4.2.1 The improved APF method

The APF method(Artificial Potential Field,APF)was first proposed by Khatib[Khatib(2003)]and applied in mobile robot path planning and obstacle avoidance problems.The APF method is inspired by the principle of the gravity force and the repulsive force.The gravity force is commonly generated by the heterogeneous charge with the different type of electrostatic charge between the target point and UAV.Moreover,the repulsive force is generated by the homogeneous charge between the barrier or obstacle and UAV.The stress analysis of UAV in the APF is proposed in Fig.5.

Figure 5:The stress analysis of UAV in the APF method

The standard APF method has shortcomings as follows:First,when UAV is far from the target point,the attractive force will be far more than the repulsive force.Hence the UAV may neglect the barrier and produce a collision with the obstacle.Second,when UAV is on some certain point where the attractive force and the repulsive force have the same value but the opposite direction,UAV will fall into shock and finally become static.To overcome these shortcomings,we propose the improved APF method.The attractive and the repulsive potential field function is redefined,and the attractive and the repulsive force function is calculated correspondingly as follows.

According to the gradient descent strategy of APF method,the attractive potential field function UG(n)and the repulsive potential field function UO(n)can be expressed in Eqs.(14)and(15).ρGis the distance between UAV and the target point while ρOis the distance between UAV and the barrier.dgoalis the threshold value of the distance between UAV and the target point while dobis the threshold value of the distance between UAV and the barrier.ε is the scale factor of the attractive force potential function while σ is the scale factor of the repulsive force potential function.In our research,we set the scale factor as ε=σ=0.2.

The attractive force function FG(n)and the repulsive force function FO(n)can be expressed in Eqs.(16)to(17)(See line 6 in Algorithm 1).The attractive force function is the derivative of the attractive potential field function to the distance.The repulsive force function is the derivative of the repulsive potential field function to the distance.

In our research,the improved APF method accelerates the convergence rate of the path planning process.Compared with the standard APF method,we redefine the attractive potential field function and the repulsive potential field function.After the derivation process,we get the attractive force function and the repulsive force function,which mainly influence the movement of UAV in the potential field.The standard APF method has shortcomings as low robustness and easy to fall into local optimum.Our proposed APF method set the threshold value to modify the attractive force and the repulsive force,which makes the fight of UAV with high-efficiency and matching with reality.Hence the improved APF method that we propose overcome the shortcomings of the standard APF method and have advantages to applied in the UAV path planning problems.

4.2.2 Adaptive inertia weight based on the optimal success rate

Similar with the exploration process and the exploit process in the standard heuristic search algorithm,the swarm intelligent algorithm has the process of global search,and local search in the whole optimize the process.Global search is aimed to determine the approximate range of the optimal solution,and local search is aimed to calculate the optimization fitness.

The conversion opportunity between global search and local search directly influences the search process efficiency and the optimal accuracy.In order to control the global search process of bat individuals,adaptive inertia weight is introduced to update the bat individual velocity updating strategy in Eq.(9)as shown in the following Eq.(18).

We propose the concept of the success rate(See line 10 in Algorithm 1)for the optimal search optimization,which makes the inertia weight related to the optimal success rate of the bat's population.The adaptive inertia weight based on the optimal success rate is defined as follows:

The optimal success rate strategy successfully balances the global optimal search and the local optimal search.is the precise measurement of the optimal value.Only if the optimal value of the t-generation is smaller than the t-1-generation,will be set as a non-zero constant.During a certain iteration process,the sum of the optimal value change of the whole bat population will be taken into consideration as the optimal success rate.Finally,the optimal success rate linearly influences the inertia weight.

The adaptive inertia weight based on optimal success rate transform the occasion of global search and local search.It reflects on the development of a globally optimal solution.Compared with other linear inertia weight,our proposed method has great robustness.Simulation and experiment results will prove our views.

4.2.3 Chaos strategy

In order to traverse the solution space completely,it requires that the initial bat's population should be distributed randomly.Chaos strategy satisfies this demand and can be combined with the improved bat algorithms to reallocate the initial distribution of the bat's population.Chaos strategy is a pseudo-random phenomenon with the feature of random distribution.

However,we can use the deterministic method to make the contribution truly random.We choose one of the deterministic methods called logistic mapping to be our chaos strategy used in our proposed algorithm CPFIBA.The logistic function formulation of logistic mapping is proposed in Eq.(22)as follows.

Logistic factor μ determines the contribution of variable xnin the interval.When 0 ≤μ≤3,the distribution of xnmeets the linear relationship,which is a non-random distribution in the interval.When 3≤μ≤4,the distribution of xnchanges greatly and gradually become a random distribution in the interval.We use the Logistic Mapping to illustrate the relationship between μ and xn,as shown in Fig.6.

Figure 6:Logistic mapping

In particular,for the situation μ=4,the logistic mapping(See line 7 in Algorithm 1)becomes a full distribution in the interval[0,1].In our research,the Logistic mapping of chaos strategy is proposed to make the distribution of bat population randomly.Hence the bat individuals can make thorough exploitation of the solution space according to Eq.(9)and Eq.(22).The chaos strategy makes the bat algorithm getting rid of local minimum and having much higher solution speed under the circumstances.Hence,it is necessary to combine the chaos strategy with our proposed UAV path planning algorithm CPFIBA.

5 Simulation experiment and results analyses

We use a PC with 64-bit Windows 10 operating system for simulation experiments,and the processing parameters are Intel 3.35 GHz Core i5-3470 CPU 8 GB ROM.Simulation experiments for problems of UAV path planning in 2D and 3D environment are programmed in MATLAB R2016a[Zhao,Zeng and Liu(2018)].

This paper compares the proposed CPFIBA with DEBA and BA.The iteration formula parameters setting for DEBA are proposed as NP=30,A=0.95,Q=r=F=0.5.Population size N=90 and iteration number NC=30.The iteration formula parameter settings for standard BA are proposed as=0.6,=0.95,β=0.9,population size N=90 and number of iterations NC=30.In the CPFIBA,iteration formula parameters setting of chaos strategy and the APF method parts are proposed as μ=4，k=1,m=1,ρ0=0.5.The other parameter settings[Wang,Guo,Hong et al.(2012)]of bat algorithm in DEBA and CPFIBA stay the same with the standard bat algorithm.

5.1 2D environment simulation experiment and results analyses

In the 2D environment simulation experiment,the 2D rectangular coordinates of the start point are(0,0),and the coordinates of the target point are(80,100).The parameters of each obstacle are illustrated in Tab.1.

Table 1:Threat source options in 2D simulation experiment

In Tab.1,two main factors are taken into consideration.The first factor is the threat source uniformly distributed in the 2D simulation environment.The second factor is the radius of threat source should be various and reasonable.Threat factor is the evaluation of the influence of barriers.We formulate these threat sources to simulate the problems of UAV path planning as realistic as possible.

The simulation flight paths of BA,DEBA,and CPFIBA in 2D complex environment are shown in Fig.7.From the simulation results of UAV path planning in a 2D environment,we can make some further analysis.The dotted line with hollow blue circle represents for planning path of BA.The dotted line with red symbol cross represents for planning path of DEBA.The dotted line with solid black circle represents for planning path of CPFIBA.All these three algorithms guarantee UAV avoid the collision and obstacle.The path length of BA is much longer than DEBA and CPFIBA.Under the consideration of flight path smooth,CPFIBA generates the smoothest planning path among these three algorithms.Meanwhile,DEBA ranks the second with several obtuse turning angles.BA generates an unsatisfied flight path with many sharp turn angles,which cannot be used directly as the UAV flight path.According to this analysis,an intuitive deduction is constructed that CPFIBA is with better performance than DEBA and BA on flight path simulation and path smoothing effect.The subsequent experiment data and results will prove our viewpoint in detail.

Figure 7:Simulation results of CPFIBA,DEBA,and BA in 2D environment

Figure 8:Objective function convergence curve in 2D environment

The objective function convergence curves of CPFIBA,DEBA,and BA in 2D environment is shown in Fig.8.According to the objective function convergence curve,further analysis is proposed as follows.Like the path planning simulation,the black convergence line represents for the CPFIBA.Meanwhile,the red convergence line represents for the DEBA,and the blue convergence line represents for the BA.The slope of the convergence line determines the converging rate of a specific algorithm.It can be concluded that CPFIBA has the best convergence performance while DEBA ranks the second and BA takes the last place.Hence compared with DEBA and BA,CPFIBA has the highest convergence rate.After dozens of iteration operations,the flight objective function eventually converges at a relatively stable value.The final stable value is commonly used to examine the performance and convergence accuracy.After the same iteration process,CPFIBA has the lowest convergence fitness compared with DEBA and BA.The lowest convergence fitness value corresponds to the shortest flight path length and the least energy cost.CPFIBA is more adaptable for problems of UAV path planning in a 2D environment.

The evaluation index table of BA,DEBA,and CPFIBA in a 2D environment,including optimal path length,flight cost function values and algorithm execution time,is proposed in Tab.2.

Table 2:Evaluation index in 2D environment

According to the evaluation index table,some further analysis can be proposed as follows.By numeral calculation,it can be inducted that CPFIBA gets 25.73% less than BA and 7.30% less than DEBA on flight path length.For fitness value comparison,CPFIBA defeats other two algorithms with 66.18% less than BA and 45.10% less than DEBA on convergence fitness value.Considering the convergence time of each algorithm,CPFIBA executes 49.05% less than BA and 30.57% less than DEBA.The reason for CPFIBA having shorter convergence time is mainly the optimal success rate,fuzzy logistic operation,and the prerequisite of APF method.By taking less convergence time,we contributed drastically better path planning results so that it is trustworthy to utilize the proposed CPFIBA in the problems of UAV 2D flight path planning.

From the experimental results,it can be concluded that CPFIBA is more suitable for 2D path planning problems than BA and DEBA.This conclusion can be concluded from the comparison of the planned path length and the obstacle avoidance effect.It also can be obtained by analyzing the flight cost function and the convergence curve to support our viewpoint.In different aspects,CPFIBA also shows better performance than BA and DEBA on the convergence accuracy and convergence speed,and the stability of the algorithm is also excellent.CPFIBA costs more execution time than DEBA and BA relatively but gets a significant increase in algorithm performance.In summary,the conclusion can be raised that the proposed improved algorithm CPFIBA performs better than DEBA and BA in 2D problems of UAV path planning.

5.2 simulation experiments of 3D environments

In the simulation of 3D environments,the start point coordinates are(0,0,100),and the target point coordinates are(100,100,100).The concept of flight safety circle is proposed to restrict the flight height of UAV.The altitude of the UAV in flight should not be higher than the flight safety circle.According to practical application problem,the safety circle is set to be parallel to the plane.

For BA,DEBA and CPFIBA iteration formula parameter settings are consistent with 2D experiments in Section 5.1.These three algorithms are applied to the path planning problems in the 3D terrain space model respectively.The simulation results and the convergence curve of the cost function are obtained as follows.

The algorithm BA,DEBA,and CPFIBA are applied to the UAV path planning problem in 3D terrain environment for performance tests.The path planning simulation results are shown in Fig.9 as follows.

Figure 9:Simulation results of CPFIBA,DEBA,and BA in 3D environment

In the 3D UAV path planning simulation results,we stretch the observed perspective to the detailed effect of each algorithm.Among the simulation effect diagram,the black line with solid black dots represents for the planning path of CPFIBA while the blue line with solid blue dots represents for the planning path of DEBA and red line with solid red dots represent for the planning path of BA.It can be intuitively observed that the average altitude of CPFIBA planning path is lower than DEBA and BA.The lower altitude makes the UAV safer and consumes less fuel.Moreover,the length of CPFIBA planning path is shorter than DEBA and BA.CPFIBA guides UAV flying shorter flight length and lower altitude by finding the path along the valley of the mountain terrain.CPFIBA makes the best performance among these algorithms in 3D path planning problems.

The problems of UAV path planning in the 3D environment are different from those in the 2D environment.Besides the planning path length,average flight altitude is also the key factor to evaluate the algorithm planning performance.The flying height change takes much more energy than flying steadily in the plain with fixed altitude.The better planning path in mountain terrain is aimed at avoiding flying across the mountain surface but also finding the valley or low altitude place to fly through the terrain.These factors are considered in the fitness value of the objective function for further analysis.

Figure 10:Objective function convergence curve in 3D environment

The objective function convergence curves of CPFIBA,DEBA,and BA in a 3D environment is shown in Fig.10.The following analysis can be proposed according to the objective function convergence curve graph.Similar with convergence fitness value formulation in a 2D environment and analysis process,the black convergence line represents for CPFIBA.Meanwhile,the blue convergence line represents for DEBA,and the red convergence line represents for BA.The slope of the convergence curve determines the specific algorithm.It can be concluded that CPFIBA has the best convergence performance while DEBA ranks the second and BA takes the last place.Compared with DEBA and BA,CPFIBA has the highest convergence rate.After dozens of iteration operations,the objective function eventually converges at a relatively stable value.The final stable value is generally used for performance tests,which particularly focus on the convergence rate and solution accuracy.After the same iteration operation,CPFIBA has the lowest convergence fitness compared with DEBA and BA.The lower convergence fitness value corresponds to the shorter flight path length,the lower average flight height and the less fuel cost.The evaluation index table of BA,DEBA,and CPFIBA including optimal path length,the cost fitness function values and algorithm execution time in a 3D environment is proposed in Tab.3.

Table 3:Evaluation index table in 3D experiment

According to the evaluation index table,some necessary analysis can be proposed as follows.By numeral calculation,it can be inducted that CPFIBA gets 36.56% less than BA and 27.16% less than DEBA in flight path length.For the convergence fitness value comparison,CPFIBA gets 45.10% less than BA and 21.58% less than DEBA on the convergence fitness value.Considering the convergence time of each algorithm,CPFIBA executes 49.71% less than BA and 60.09% less than DEBA.The reason for CPFIBA having shorter execution time is mainly the optimal success rate,fuzzy logistic operation and the prerequisite of APF method.By taking less execution time,CPFIBA drastically improves the path planning results so it is trustworthy to utilize the proposed CPFIBA in the problems of UAV 3D path planning.

According to the relevant experimental results,we confirm that the proposed CPFIBA performs better than BA and DEBA in 3D UAV path planning.On the other hand,it illustrates the adaptability of CPFIBA in dealing with multidimensional problems and its extraordinary solution precision and convergence rate.Compared with other standard group intelligent algorithms,the proposed CPFIBA have significant advantages in solving multidimensional problems.

6 Conclusion and future work

In this paper,the improved APF method and chaos strategy are combined with our proposed algorithm.We originally proposed the success rate of adaptive inertia weight to improve the performance of standard bat algorithm.In summary,a new improved bat algorithm is proposed based on the improved APF method and chaos strategy,named CPFIBA.The adaptive inertia weight controls the balance of the global search process and the local search process to avoid the algorithm from falling into the local minimum.Combined with the chaos strategy,the initial distribution of the bat population can be randomized and homogenized so that the solution space can be traversed thoroughly.The improved APF method satisfies with the characteristics of the UAV path planning problems,and it fully utilizes the information of topography,start-point,and end-point to a great extent.In our research,the new improved CPFIBA is applied to the 2D and 3D problems of UAV path planning.Through experimental results and objective analysis,it is concluded that in the 2D and 3D problems of UAV path planning,CPFIBA has better performance than BA,DEBA,which prove it more suitable for solving multi-objective optimal problems especially the UAV path planning problems.

This paper introduces the detailed and accurate model of the 2D and 3D problems of UAV path planning on the flight cost function and UAV constraints.However,we do not consider the dynamic threat and obstacle within the threat cost.Future work should focus on the theory and experiment of UAV dynamic threat and obstacle avoidance strategy,making the path planning method with engineering application significance.

Acknowledgement:This project is supported by National Science Foundation for Young Scientists of China(61701322),the Key Projects of Liaoning Natural Science Foundation(20170540700),the Key Projects of Liaoning Provincial Department of Education Science Foundation(L201702),Liaoning Natural Science Foundation(201502008,20102175),the Program for Liaoning Excellent Talents in University(LJQ2012011)and the Liaoning Provincial Department of Education Science Foundation(L201630).

The data and code used to support the findings of this study have been deposited in the GitHub repository(https://github.com/TellINFake/UAV-Path-Planning.git).