CN109144102B - A UAV Route Planning Method Based on Improved Bat Algorithm - Google Patents

Abstract

A UAV route planning method based on the improved bat algorithm, the method is based on the traditional bat algorithm, introduces the optimization success rate to change the speed update method of the bat individual, and uses the chaos method to initialize the distribution of the bat individual in the search space. , and use the concept of artificial potential field to simulate the gravitational field of the end point and the repulsive force field of the starting point and obstacles to accelerate the speed of the individual bat moving to the optimal solution. Finally, an improved bat algorithm based on chaotic artificial potential field is proposed. In the UAV route planning task, compared with the traditional bat algorithm, the method has 36.56% shorter track length, 56.05% shorter planning time, and 49.53% lower obstacle avoidance fitness value; The length is 27.16% shorter, the planning time is 27.30% shorter, and the fitness value of obstacle avoidance effect is 42.46% lower. It is a route planning algorithm with practical application significance.

Description

A UAV Route Planning Method Based on Improved Bat Algorithm

technical field

The invention belongs to the technical field of intelligent control, relates to an unmanned aerial vehicle route planning method, and in particular relates to an unmanned aerial vehicle route planning method based on an improved bat algorithm.

Background technique

UAV route planning generally refers to the process of finding a flightable route from the starting point to the target point that meets the UAV performance indicators under specific constraints. The algorithm used for the UAV route planning problem directly affects the success rate and efficiency of the route planning. Swarm intelligence algorithms generally have the advantages of fast convergence, strong robustness, and potential parallelism, and are widely used in UAV route planning. However, when these swarm intelligence algorithms are used to solve the route planning problem, there are common defects such as insufficient solution accuracy, unsmooth planned trajectories, and easy to fall into local optimum. Therefore, an intelligent algorithm with excellent optimization performance should be selected and improved in a targeted manner, in order to make it have a better effect on the UAV route planning problem.

The swarm intelligence algorithm is widely used by researchers at home and abroad to solve the UAV route planning problem. The more typical algorithms are selected as follows. Shibo Li et al. used the particle swarm algorithm combined with fuzzy logic to solve the 2D UAV route planning problem for the first time, and compared and analyzed the different planning effects after changing the parameters in the particle swarm algorithm. However, there are two-dimensional experimental environment settings. It is too simple, and there is no 3D simulation experiment; Hao Meng et al. used genetic algorithm combined with digital elevation map and RBF neural network to solve 3D UAV route planning, and gave a rigorous mathematical demonstration process, and also obtained the results. Intuitive 3D route planning effect, but limited by the limitations of the genetic algorithm itself, there is still a lot of room for improvement in the solution convergence speed of 3D route planning and the route planning effect; Ioannis K. Nikolos et al. applied the differential evolution algorithm to multi-UAV cooperative routes In the planning problem, a better solution is given for the UAV formation to complete the task together, but from the experimental results, it can be seen that the route planned by the differential evolution algorithm has the characteristics of the Levy flight trajectory, and cannot be directly used as an unmanned aerial vehicle. The human-machine flight route, in addition, the algorithm itself is not fast enough to solve, and the algorithm execution stability is not high enough; Gaige Wang et al. applied the bat algorithm to optimize the flight cost function in the optimization of the UAV route planning problem, and the optimization effect of other traditional swarm intelligence algorithms A comparative analysis is carried out, which proves that the bat algorithm has the advantages of fast solution speed, high convergence accuracy and good algorithm stability in optimizing the flight cost function, but it lacks an intuitive simulation experiment of the effect of two-dimensional and three-dimensional route planning; Gai-Ge Wang In the subsequent research, the bat algorithm based on the differential evolution algorithm was applied to the UAV route planning, and the results of 2D and 3D simulation experiments were given. The route planning effect of the algorithm is compared and demonstrated, which confirms the superiority of the proposed algorithm. However, the experimental environment setting is too simple, which is not conducive to the real optimization and obstacle avoidance performance of the detection algorithm. In addition, the planned route also exists. The characteristics of Levy's flight path are not smoothed.

SUMMARY OF THE INVENTION

In view of the above deficiencies in the prior art, the present invention proposes a UAV route planning method based on the improved bat algorithm, and the algorithm flowchart is shown in FIG. 1 . The execution process of the route planning method is divided into five main steps: improving the bat algorithm for route planning, the artificial potential field method to accelerate the iterative process, the chaotic strategy Logistic function to uniformize the population distribution, the establishment of route planning constraints and objective functions, and the smoothing of the route trajectory. . The following is a detailed explanation.

1. Improve the bat algorithm

The bat algorithm is an emerging meta-heuristic intelligent algorithm published by Yang.X.S in 2010. The inspiration source of the bat algorithm is the behavior of bats in nature to capture prey, avoid obstacles and natural enemies through echolocation; the bat algorithm follows the following three rule:

1. Each individual bat in the search space only relies on ultrasonic echoes for localization, and does not involve other sensory factors such as vision; in addition, bats can judge the difference between food, prey and obstacles according to the difference in echoes.

2. Flight optimization parameter setting of individual bats: Bat i flies at speed vi, its real-time position is represented by xi, and its initial sound frequency is fmin. During the search process, the bat will dynamically adjust the frequency f and volume A ₀ of the ultrasonic wave it emits according to the degree of approaching the target.

3. Make an idealized constraint on the bat vocalization volume, that is, assume that the bat vocalization volume varies from a large positive number A ₀ to a minimum value Amin without exceeding the bounds.

For the virtual bat in the d-dimensional search space, the update formulas of the bat vocalization frequency f _i , velocity v _i and position x _i at time t are:

f _i =f _min +(f _max -f _min )×β (1)

v _i ^t =v _i ^t-1 +(x _i ^t-1 -x _* )×f (2)

x _i ^t = x _i ^t-1 +v _i ^t (3)

与全局最优解x_*的接近程度来衡量其向最优解运动的加速度(迫切程度)；而下一时刻的运动速度除了参考这个靠近全局最优解所产生的加速度以外，还考虑蝙蝠个体本身的惯性，即下一时刻的运动速度

还受到上一时刻速度

的影响。公式(3)描述了蝙蝠个体所处位置随着运动不断迁移的过程。For the update of the sound frequency in formula (1), β is a random variable that obeys a uniform distribution and satisfies β∈[0,1]; f _max and f _min are the maximum and minimum values of the initially set sound frequency range. In formula (2), x _* is the position of the current global optimal solution, and this value is the optimal value obtained by comparing the fitness values of all individuals in the bat population. Individual bats based on their previous location

The degree of proximity to the global optimal solution x _* is used to measure the acceleration (urgency) of its movement to the optimal solution; and the movement speed at the next moment not only refers to the acceleration generated by this approach to the global optimal solution, but also considers the individual bat Its own inertia, that is, the speed of movement at the next moment

Also affected by the speed of the previous moment

Impact. Equation (3) describes the process of the bat individual's position migrating with the movement.

The above is the iterative mechanism followed by the bat population in the global search in the solution space, and the bats near the global optimal solution use the random walk rule to generate local new solutions:

x _new = x _old +εA ^t (4)

是所有蝙蝠在t时刻的平均音量。In formula (4), ε∈[-1,1] is a random number;

is the average volume of all bats at time t.

At this time, the update formulas of sound frequency and loudness are described as follows:

r _i ^t+1 =r _i ⁰ [1-exp(-γt)] (6)

Both α and γ in formula (5) and formula (6) are constants, usually α=γ=0.9. From the expression, it can be analyzed that as the bat approaches the optimal solution infinitely, its vocalization loudness decreases continuously and stops vocalization when the optimal solution is reached; while the vocalization frequency keeps approaching the initial pulse rate r _i ⁰ as time goes by .

Similar to the exploration operation and mining operation in the heuristic search algorithm, the swarm intelligence algorithm has the process of global search and local search in the optimization process. The global search is to determine the approximate range where the optimal solution is located; the local search is to perform precise optimization within these ranges.

The trade-off between global search and local search directly affects search efficiency and optimization accuracy. In order to better control the global search speed of bat individuals, one of the innovations of the present invention is to introduce adaptive inertia weight w to rewrite the bat speed update formula (2), as shown in formula (7):

v _i ^t =wv _i ^t-1 +(x _i ^t-1 -x _* )×f (7)

And the concept of the optimization success rate is introduced, so that the inertia weight can be adaptively adjusted with the optimization success rate of the bat group. The adaptive inertia weight based on the optimization success rate is defined as follows:

是蝙蝠群体的寻优成功率；N代表蝙蝠种群数量；

表示蝙蝠个体i在第t次迭代过程中的寻优结果，

表示t代的适应值优于t-1代，搜索到了更优解，如若不然则

in,

is the optimization success rate of the bat population; N represents the number of bat populations;

represents the optimization result of individual bat i in the t-th iteration process,

Indicates that the fitness value of the t generation is better than that of the t-1 generation, and a better solution has been searched, if not, then

2. Artificial potential field method

The artificial potential field method was originally published by Khatib in 1994 and was applied to the obstacle avoidance motion planning of the robot manipulator, and was later applied to the path planning of mobile robots. At present, there is no fusion application of the artificial potential field method and the improved bat algorithm. A precedent in the problem of UAV routing. The artificial potential field method is inspired by the principle of electrostatic field that different kinds of charges produce gravitational force and the same kind of electric charge produces repulsion force. The force diagram of the aircraft in the artificial potential field is shown in Figure 3:

表示斥力，

表示引力，

表示飞行器所受合力，直接影响着飞行器的运动。根据人工势场的梯度下降方法，斥力和引力可以表示为式(9)与式(10)：In Figure 3,

means repulsion,

means gravitational force,

Indicates that the resultant force on the aircraft directly affects the movement of the aircraft. According to the gradient descent method of the artificial potential field, the repulsive force and the attractive force can be expressed as equations (9) and (10):

Assuming that n is any point in the search space, the gravitational force F _a (x) and the repulsive force F _r (x) on this point can be expressed as:

F _a (x)=-grad(U _a (x))=kρ _G (q)(11)

3. Chaos Strategy and Logistic Mapping

The basis of the chaotic algorithm is the logistic map:

x _n+1 = μx _n (1-x _n-1 )n=1,2,..... (13)

When μ=4, the mapping becomes a surjective on the [0, 1] interval, and the value generated iteratively is in a state of pseudo-random distribution, while for other values, after a certain number of iterations, The resulting value will converge to a specific numerical value. The random distribution of the bat population in the normalized search space will maximize the efficiency of the global search of the search population; at the same time, it is extremely difficult for the bat individual to have a large-scale position change in the process of their local search, and the initial population is evenly distributed. The random distribution of bats effectively solves the problem that the bat population is easy to fall into the local optimal solution in the later stage of search.

Therefore, while combining the artificial potential field, this patent proposes the second innovation point, that is to use the Logistic map based on the chaotic strategy to initialize the distribution of the bat population in the solution space, so as to speed up the overall convergence speed of the algorithm and greatly reduce the Reduces the possibility of getting stuck in a local optimum.

4. Constraints and Objective Functions of Route Planning Tasks

The definition of UAV route planning is the process of finding the route from the flight start point to the end point with the least cost and satisfying the performance index of the UAV under some specific constraints. Its essence is the problem of finding the extremum of multiple objective functions under multiple constraints. The analysis of the route planning problem is as follows.

The cost function during UAV flight can be divided into three parts, namely route length cost, threat cost and fuel consumption cost. The total cost function is denoted by J, and the minimization problem of J is defined as follows:

min J=k ₁ J _L +k ₂ J _T +(1-k ₁ -k ₂ )J _F (14)

Among them, J _L refers to the cost of route length, J _T refers to the cost of threats, and J _F refers to the cost of fuel consumption in flight. Both k ₁ , k ₂ are positive numbers and satisfy 0≤k ₁ ≤1, 0≤k ₂ ≤1.

For the route length cost J _L is defined as follows:

Among them, L refers to the length of the total flight path, and l _ij is the length of the track segment, which is used to calculate the length of the route that cannot be calculated by integral before the route is smoothed.

The cost J _T for a threat is defined as follows:

Among them, t _k is the threat factor, which is a measure of the threat source to the UAV; N _t represents the total number of threat sources; the current coordinate of the UAV is (x, y); the center coordinate of the threat source is ( x _k , y _k ).

The fuel consumption cost J _F is defined as follows:

中的k表示无人机行驶单位长度路径所消耗的燃料代价；

中，H是无人机飞行安全圈的高度，无人机飞行高度不应超过这个值，w₀表示无人机维持高度H时所需要消耗的燃料代价，h表示无人机当前所处的高度。in,

The k in represents the fuel cost consumed by the UAV to travel a unit-length path;

Among them, H is the height of the UAV’s flight safety circle, and the UAV’s flying height should not exceed this value, w ₀ represents the fuel cost that the UAV needs to consume when maintaining the height H, and h represents the current position of the UAV. high.

为航迹点迁移向量。The UAV needs to conform to its own dynamic characteristics during flight, so the pre-planned route needs to meet some constraints. In order to illustrate these constraints more intuitively, a part of the waypoints in the track are selected as the model to illustrate. Let A(x _i-1 ,y _i-1 ,z _i-1 ) be the previous waypoint, B(x _i ,y _i ,z _i ) be the current waypoint, C(x _i+1 ,y _{i+ 1} , z _i+1 ) is the next waypoint, and record

is the track point migration vector.

When the UAV wants to change its own height during flight, it needs to perform a climbing or diving operation. The present invention assumes that the maximum climbing and diving angle is θ, then the constraints on the climbing/diving angle of the UAV are:

When the UAV avoids obstacles, the turning radius corresponding to the inscribed circle of the planned track may be too small, which violates the UAV's own flight characteristics. Therefore, the minimum turning radius in UAV flight is limited, as shown in Figure 4 of the turning radius limitation:

则最小转弯角可以通过下式确定：route angle

Then the minimum turning angle can be determined by the following formula:

Among them, r _min is the minimum turning radius.

The flight height limit depends on the specific characteristics of the UAV's mission; in order to reduce consumption and ensure that the route is as concealed as possible, there must be a maximum limit h≤H for the absolute height h of the ground, where H is the plane where the flight safety circle is located In order to respond to terrain changes in time, the relative height of the UAV from the terrain surface is required to be h _i ≥ h _min .

UAVs use their own sensors to detect stationary obstacles and dynamic obstacles, and the avoidance mechanism for obstacles after identifying obstacles is a key factor affecting the effect of route planning. As shown in Figure 5:

In order to conform to the characteristics of the UAV's flight direction and yaw angle, the trajectory in the polar coordinate system is used to illustrate the UAV's avoidance mechanism for obstacles. In the figure, O is the start point of the track and G is the end point of the track. The track segment between each two adjacent segments from L ₁ to L _k is generated by equal division based on the polar axis, and each sub-track is marked with a square. The starting point of the segment. The mechanism of measuring and avoiding threats between each two track points is visually shown in Figure 6:

一般地，这个威胁代价可以表示为：The sub-track segments are segmented again according to the number of threat sources to calculate the threat cost

Generally, this threat cost can be expressed as:

Among them, N _T represents the number of threat sources, t _j represents the threat factor of the threat source, and d _k (i, j) represents the straight-line distance between the starting points i and j of the kth sub-track segment.

The obstacle avoidance process is the process of minimizing the threat cost under the constraints. Using the advantages of intelligent algorithms to solve the optimization problem, the optimal route pre-planned can effectively avoid the threat of static obstacles in space. For the avoidance of dynamic obstacles, the UAV needs to return to the pre-planned optimal route after identifying the dynamic obstacle and evading it urgently. This process is also called route following.

The result of the pre-planned route needs to be tested for the flightability of the route, that is, to check whether the planned route meets the flight constraints of the UAV. The planned route that meets the constraints satisfies the Levy flight trajectory, but the route may not be smooth, so an effective route smoothing method is needed.

5. Route smoothing method

This patent uses the two-point cubic Hermite interpolation method to realize the smoothing of the route. It is assumed that the curve to be smoothed is a polyline segment from A to B and then to C in the Cartesian coordinate system, as shown in Figure 7:

The function value and derivative value on the known interpolation nodes x ₀ , x ₁ are:

y _i =f(x _i ),m _i =f'(x _i ),(i=0,1) (21)

It is necessary to find a polynomial H ₃ (x) whose degree is not more than 3, so that it satisfies:

H ₃ (x _i )=y _i , H ₃ ′(x _i )=m _i , (i=0,1) (22)

Introduce interpolation basis functions α ₀ (x), α ₁ (x), β ₀ (x), β ₁ (x) to find H ₃ (x). It can be expressed as:

H ₃ (x)=y ₀ α ₀ (x)+y ₁ α ₁ (x)+m ₀ β ₀ (x)+m ₁ β ₁ (x) (23)

In order to meet the interpolation conditions, the difference basis function has the following restrictions:

The expression of each interpolation basis function is obtained by using the undetermined coefficient method:

经过两点三次Hermite插值后，将用弧段

来替代先前的折线段飞行轨迹，这样的做法实现了预规划航路平滑问题。Polyline segment of the route to be planned

After two-point cubic Hermite interpolation, the arc segment will be

To replace the previous polyline segment flight trajectory, this approach realizes the pre-planned route smoothing problem.

Beneficial effects: There have been precedents for applying artificial potential field method and chaotic strategy to UAV route planning in previous research work, but since the main method of searching and expanding the path is the heuristic A* algorithm, and the group Compared with intelligent algorithms, it is easy to fall into local optimum, and there are problems of slow convergence speed and low convergence accuracy. Therefore, on the basis of previous research, this patent introduces the optimization success rate to change the speed update method of bat individuals for the traditional bat algorithm, and at the same time adopts the chaotic method to initialize the distribution of bat individuals in the search space, and uses the concept of artificial potential field to simulate The gravitational field at the end point and the repulsion field at the starting point and obstacles accelerate the movement speed of the individual bat to the optimal solution. Finally, an improved bat algorithm based on the chaotic artificial potential field is proposed to solve the UAV route planning problem under constraints.

In the proposed improved algorithm, the introduction of the adaptive inertia weight balances the global search and the local search, avoiding the algorithm falling into the local optimal solution; combining the chaotic strategy can make the initial distribution of the bat population random and uniform, making the solution space more It is comprehensively searched and traversed; the introduction of artificial potential field refers to the characteristics of the UAV route planning problem itself, and the information of terrain, starting point and ending point is used to a large extent, and the execution efficiency of the algorithm is improved.

Description of drawings

Fig. 1 is the flow chart that utilizes the improved algorithm proposed by this patent to carry out route planning task;

Figure 2 is a pseudo-code diagram of the improved bat algorithm based on artificial potential field and chaotic strategy;

Figure 3 is the force diagram of the aircraft in the artificial potential field;

Fig. 4 is a schematic diagram of turning radius limitation;

Figure 5 is a schematic diagram of the UAV avoiding obstacles;

Fig. 6 is a schematic diagram of threat cost measurement between sub-track points;

Figure 7 is a schematic diagram of the Hermite interpolation method to achieve smooth route;

Figure 8 Comparison of route planning effects of BA, DEBA, and CPFIBA in a two-dimensional terrain environment;

Fig. 9 Convergence curve comparison of route cost function of BA, DEBA and CPFIBA in two-dimensional terrain environment;

Figure 10. Panorama view and side view of 3D terrain environment;

Figure 11 Comparison of route planning effects of BA, DEBA, and CPFIBA in a 3D terrain environment;

Fig. 12 Convergence curve comparison of cost function fitness function of BA, DEBA and CPFIBA route planning in 3D terrain environment.

Detailed ways

Implementation hardware conditions:

The implementation environment is a PC with a 64-bit Windows 7 operating system, the performance parameter is Intel(R) Core(TM) i5-3470 CPU 3.20GHz, and the ROM size is 8GB. The simulation experiments under 2D terrain and 3D terrain are both programmed under MatlabR2016a software.

Related algorithm parameter settings:

Use BA to represent the original bat algorithm; DEBA to represent the improved bat algorithm based on differential evolution algorithm; CPFIBA to represent the improved bat algorithm based on chaotic strategy and artificial potential field proposed in this patent.

The basic bat algorithm iteration formula parameter setting: r _i ⁰ =0.6, A _i ⁰ =0.95, β=0.9; population size N=90; number of iterations NC=30 in two-dimensional environment; number of iterations NC=30 in three-dimensional environment.

Differential evolution algorithm iteration formula parameter settings for comparison: NP=30, A=0.95, Q=r=F=0.5; population size N=90; number of iterations in two-dimensional environment=30; number of iterations in three-dimensional environment NC =30.

The parameters of the improved bat algorithm based on artificial potential field and chaotic strategy are set as μ=4, k=1, m=1, ρ ₀ =0.5, population size N=90; the number of iterations in the two-dimensional environment is NC=30; in the three-dimensional environment The number of lower iterations NC=30.

Example 1:

In the two-dimensional environment simulation experiment, the whole picture of the two-dimensional terrain environment can be reflected from the route planning effect map, and the topographic map is no longer presented separately. The two-dimensional rectangular coordinates of the starting point in the two-dimensional terrain environment are (0, 0), and the coordinates of the target point are (110, 100). The settings of each obstacle are shown in Table 1:

Table 1 Threat source settings of 2D environment simulation experiment

The comparison of the optimal route length, route cost fitness function value and algorithm execution time of BA, DEBA and CPFIBA in a two-dimensional environment (30 iterations of a single experiment, taking the average value of ten independent experiments) are shown in Table 2:

Table 2 Comparison of various performance indicators of the improved algorithm in a two-dimensional environment

Using the three algorithms of BA, DEBA and CPFIBA to apply the UAV route planning problem in the two-dimensional complex environment, the simulation effect of the two-dimensional route planning is obtained as shown in Figure 8, and the convergence curve of the route cost fitness function is shown in Figure 9.

For the analysis of the experimental data, simulation results and convergence curves in the two-dimensional environment, the following analysis can be made: Under the same terrain conditions, the length of the route planned by CPFIBA is 197.35km, which is 7.30% shorter than the length of the route planned by DEBA, which is 212.89km. , which is 25.73% shorter than the length of 265.73km planned by BA, that is, the route planned by CPFIBA is shorter; under the same constraints, the flight cost function converges for the same number of iterations. The route cost fitness function of CPFIBA is 273.83, which is 9.26% lower than DEBA's fitness value of 301.76, and 17.06% lower than BA's fitness value of 330.14. The final fitness convergence value reflects the optimization accuracy of each algorithm. From the route cost fitness function value, it can be concluded that the optimization accuracy of CPFIBA is higher than that of DEBA and BA. From the slope of the initial iteration of the curve, it can be concluded that CPFIBA has higher stability than DEBA and BA; from the perspective of algorithm execution time, the execution time of CPFIBA is 423.83ms, which saves 13.35% of the execution time compared to DEBA's execution time of 543.92ms. Compared with the BA execution time of 617.62ms, it saves 59.84% of the execution time. From the number of iterations when the objective function tends to be stable, it can be concluded that the convergence rate of CPFIBA is faster than that of DEBA and BA; from the comparison of the cost function convergence to the final value, it can be concluded that CPFIBA has better optimization accuracy. To sum up, the performance of CPFIBA in UAV 2D route planning is better than DEBA and BA, and it is more applicable.

Example 2:

In the three-dimensional environment simulation experiment, the coordinates of the starting point are (0, 0, 100), and the coordinates of the target point are (100, 100, 100). The concept of flight safety circle is introduced, that is, the flying height of the drone cannot be higher than the horizontal height of the flight safety circle. Here, the safety circle is set to be parallel to the plane and z=600m. Figure 10 shows the panorama and side views of the terrain model of the 3D UAV flight simulation environment using the digital elevation map.

The parameter settings for BA, DEBA and CPFIBA are consistent with the two-dimensional experiments. Three algorithms are used for route planning in three-dimensional terrain space, and the simulation results of route planning are shown in Figure 11, and the convergence curve of the route cost fitness function is shown in Figure 12.

The comparison of optimal path length, route cost fitness function value and algorithm execution time of BA, DEBA and CPFIBA in 3D environment (30 iterations of a single experiment, taking the average value of ten independent experiments), as shown in Table 3:

Table 3 Comparison of performance indicators of the improved algorithm in 3D environment

The three-dimensional simulation experiment results are also composed of three parts: experimental data, simulation renderings and flight cost convergence curve. Under the same 3D terrain setting, the length of the route planned by CPFIBA is 567.37km, which is 27.16% shorter than the 778.91km planned by DEBA, and 36.56% shorter than the length planned by BA of 894.38km. The planned route length is shorter than that of DEBA and BA; from the perspective of route cost fitness value, CPFIBA's route cost fitness function value is 110.35, which is 42.46% less than DEBA's fitness value of 153.47, and 49.53% less than BA's fitness value of 218.64. The final convergence value of CPFIBA is lower than that of DEBA and BA, that is, the convergence accuracy of CPFIBA is higher than that of DEBA and BA. From the perspective of algorithm execution time, the execution time of CPFIBA is 521.34ms, which is 27.3% less than the execution time of DEBA, which is 639.05ms. The time of 813.54ms is saved by 56.05%. The convergence time of CPFIBA is shorter than that of DEBA and BA, that is, the convergence speed is faster than both. It can be seen from the route planning effect that CPFIBA can avoid falling into local optimum, and the convergence accuracy is much better than that of DEBA and BA. The excellence of DEBA and BA. The simulation results show that in the 3D environment UAV route planning, the CPFIBA algorithm has better applicability than DEBA and BA, and it is a route planning algorithm with practical application significance.

Claims (1)

1. A UAV route planning method based on an improved bat algorithm, the improved bat algorithm: one is based on the traditional bat algorithm, and the optimization success rate is introduced to change the bat individual speed update method; the other is to use chaos The method initializes the distribution of bat individuals in the search space and improves the search efficiency; the third uses the concept of artificial potential field to simulate the gravitational field of the end point and the repulsion field of the starting point and obstacles to accelerate the speed of the bat individual moving to the optimal solution; comprehensively The above three points propose an improved bat algorithm based on chaotic artificial potential field; its characteristics are as follows: It is applied to UAV route planning, which specifically includes the following steps: Step 1: Set the necessary parameters in the execution process of the bat algorithm. The necessary parameters include the number of iterations, initial speed, initial position, initial sound frequency, and initial loudness; set the parameters of the chaos strategy, uniform distribution; set the artificial potential field, define the starting point and the target point , the gravitational and repulsive potential functions of the obstacle; Step 2: Establish a UAV flight model according to the UAV flight cost function and constraints, and determine the performance evaluation mechanism for the UAV route planning task; Step 3: Use the improved bat algorithm based on artificial potential field and chaotic strategy to optimize the cost function of UAV route planning, and finally obtain the flight trajectory of UAV route planning; The specific steps of the step 1 are: Step 1.1 For the virtual bat in the d-dimensional search space, the update formulas of the bat vocalization frequency f _i , velocity v _i and position x _i at time t are: f _i =f _min +(f _max -f _min )×β v _i ^t =v _i ^t-1 +(x _i ^t-1 -x _* )×f x _i ^t = x _i ^t-1 +v _i ^t For the update of the sound frequency, β is a random variable that obeys a uniform distribution and satisfies β∈[0,1]; f _max and f _min are the maximum and minimum values of the initially set sound frequency range; in the formula x _* is the position of the current global optimal solution, and this value is the optimal value obtained by comparing the fitness values of all individuals in the bat population; the individual bats are based on their position at the last moment.

The closeness to the global optimal solution x _* is used to measure the acceleration of its movement towards the optimal solution; the speed of movement at the next moment

Also affected by the speed of the previous moment

Impact; The above is the iterative mechanism followed by the bat population in the global search in the solution space, and the bats near the global optimal solution use the random walk rule to generate local new solutions: x _new = x _old +εA ^t In the formula, ε∈[-1,1] is a random number;

is the average loudness of all bats at time t; r ^t =<r _i ^t > is the average sound frequency of all bats at time t; The update formulas of the individual bat individual vocalization frequency and loudness at time t are described as follows:

r _i ^t+1 =r _i ⁰ [1-exp(-γt)] Both α and γ are constants, usually α=γ=0.9; Step 1.2: The artificial potential field method is inspired by the principle that the electrostatic field generates gravitational force from different charges and the same charge generates repulsion. The force between the obstacle and the aircraft in the search space is defined as the repulsion force. The force is defined as gravitational force; the artificial potential field method is applied to the route planning problem, the obstacles and threat sources are set as the repulsive force field, and the target point is set as the gravitational field, this strategy accelerates the convergence speed of the entire route planning algorithm;

means repulsion,

means gravitational force,

Represents the resultant force on the aircraft, which directly affects the movement of the aircraft; according to the gradient descent method of the artificial potential field, the repulsive force and the gravitational force can be expressed as:

Assuming that n is any point in the search space, the gravitational force F _a (x) and the repulsive force F _r (x) on this point can be expressed as:

Step 1.3: The basis of the chaotic algorithm is the logistic map: x _n+1 = μ x _n (1-x _n-1 ), n=1,2,..... When μ=4, the mapping becomes a surjective on the [0, 1] interval, and the value generated iteratively is in a state of pseudo-random distribution, while for other values, after a certain number of iterations, The generated value will converge to a specific value, and the bat population will be randomly distributed in the normalized search space, which will greatly improve the efficiency of the global search of the population. The large-scale position changes and the uniform and random distribution of the initial population effectively solve the problem that the bat population is easy to fall into the local optimal solution in the later stage of the search; Therefore, while combining the artificial potential field, the Logistic map based on the chaotic strategy is used to initialize the distribution of the bat population in the solution space, so that the overall convergence speed of the algorithm is accelerated, and the possibility of falling into the local optimal solution is greatly reduced; The specific steps of the step 2 are: Step 2.1: The swarm intelligence algorithm has a process of global search and local search in the optimization process. The global search is to determine the approximate range of the optimal solution; the local search is to perform precise optimization within these ranges; The trade-off between global search and local search directly affects the search efficiency and optimization accuracy. The adaptive inertia weight w is used to rewrite the bat speed update formula, as shown below: v _i ^t =wv _i ^t-1 +(x _i ^t-1 -x _* )×f And the concept of the optimization success rate is introduced, so that the inertia weight is adaptively adjusted with the optimization success rate of the bat group. The adaptive inertia weight based on the optimization success rate is defined as follows:

in,

is the optimization success rate of the bat population; N represents the number of bat populations;

represents the optimization result of individual bat i in the t-th iteration process,

Indicates that the fitness value of the t generation is better than that of the t-1 generation, and a better solution has been searched, if not, then

The adaptive inertia weight of the optimization success rate is introduced, which is different from the traditional linear inertia weight, and better balances the proportion of global search and local search. The introduction of the optimization success rate is a parameter adjustment method with a feedback mechanism. The optimization result of the global search will affect the value of the adaptive inertia weight, thereby changing the speed of the individual bat and the timing of its entry into the local search; Step 2.2: The cost function in the UAV flight process can be divided into three parts, namely the route length cost, the threat cost and the fuel consumption cost; the total cost function is represented by J, then the minimization problem of the total cost function J is defined. as follows: min J=k ₁ J _L +k ₂ J _T +(1-k ₁ -k ₂ )J _F Among them, J _L refers to the cost of route length, J _T refers to the cost of threats, and J _F refers to the cost of fuel consumption in flight; k ₁ , k ₂ are both normal numbers and satisfy 0≤k ₁ ≤1 ,0≤k ₂ ≤1; For the route length cost J _L is defined as follows:

Among them, L refers to the length of the total flight path, and l _ij is the length of the track segment, which is used to calculate the length of the route that cannot be calculated by integral before the smoothing of the route; The cost J _T for a threat is defined as follows:

Among them, t _k is the threat factor, which is a measure of the threat source to the UAV; N _t represents the total number of threat sources; the current coordinate of the UAV is (x, y); the center coordinate of the threat source is ( x _k ,y _k ); The fuel consumption cost J _F is defined as follows:

in,

The k in represents the fuel cost consumed by the UAV to travel a unit-length path;

Among them, H is the height of the UAV’s flight safety circle, and the UAV’s flight height does not exceed this value, w ₀ represents the fuel cost that the UAV needs to consume when maintaining the height H, and h represents the current altitude of the UAV ; The specific steps of step 3 are: Step 3.1: The UAV needs to conform to its own dynamic characteristics during the flight process, select a part of the waypoints in the track as the model to illustrate, and set A(x _i-1 , y _i-1 , z _i-1 ) as the upper A waypoint, B(x _i , y _i , z _i ) is the current waypoint, C(x _i+1 , y _i+1 , z _i+1 ) is the next waypoint, and record

is the track point migration vector; When the UAV wants to change its altitude during flight, it needs to perform a climb or dive operation. Assuming that the maximum climb and dive angle is θ, the constraints on the UAV climb/diving angle are:

In the process of avoiding obstacles, the turning radius corresponding to the inscribed circle of the planned track may be too small, which violates the flight characteristics of the drone; The turning radius is limited, the included angle of the route

Then the minimum turning angle can be determined by the following formula:

Among them, r _min is the minimum turning radius; For the absolute height h of the ground, there must be a maximum limit h≤H, where H is the height of the plane where the flight safety circle is located; and in order to respond to terrain changes in time, the relative height h of the UAV from the terrain surface is required _i ≥ h _min ; Step 3.2: UAV uses its own sensors to detect static obstacles and dynamic obstacles, and the avoidance mechanism for obstacles after identifying obstacles is a key factor affecting the effect of route planning; The sub-track segments are segmented again according to the number of threat sources to calculate the threat cost

Generally, this threat cost can be expressed as:

Among them, N _T represents the number of threat sources, t _j represents the threat factor of the threat source, d _k (i, j) represents the straight-line distance between the starting point _i and j of the kth sub-track segment; the number of trace segments; The obstacle avoidance process is the process of minimizing the threat cost under the constraints. Using the advantages of intelligent algorithms to solve the optimization problem, the pre-planned optimal route can effectively avoid the threat of static obstacles in space; Obstacle avoidance requires the UAV to return to the pre-planned optimal route after identifying the dynamic obstacle and evading it urgently. This process is also called route following; Step 3.3: Use the two-point cubic Hermite interpolation method to achieve route smoothing; The function value and derivative value on the known interpolation nodes x ₀ , x ₁ are: y _i =f(x _i ),m _i =f'(x _i ), i=0,1 It is necessary to find a polynomial H ₃ (x) whose degree is not more than 3, so that it satisfies: H ₃ (x _i )=y _i , H ₃ ′(x _i )=m _i , i=0,1 Introduce interpolation basis functions α ₀ (x), α ₁ (x), β ₀ (x), β ₁ (x) to find H ₃ (x); it can be expressed as: H ₃ (x)=y ₀ α ₀ (x)+y ₁ α ₁ (x)+m ₀ β ₀ (x)+m ₁ β ₁ (x) In order to meet the interpolation conditions, the difference basis function has the following restrictions:

β _i (x _j )=0,β _i ′(x _j )=δ _ij , i,j=0,1 The expression of each interpolation basis function is obtained by using the undetermined coefficient method:

Polyline segment of the route to be planned

After two-point cubic Hermite interpolation, the arc segment will be

To replace the previous polyline segment flight trajectory, this approach realizes the pre-planned route smoothing problem.

Images