CN118036849A - An improved swarm algorithm for UAV trajectory planning - Google Patents

Abstract

The invention discloses an unmanned aerial vehicle flight path planning method for improving a bee colony algorithm, which comprises the steps of randomly dispatching N bees to find a honey source x _ij, obtaining a honey source profitability value, removing N/2 groups of solutions after the honey source quality is poor according to the honey source profitability value, hiring the bee to search, searching by adopting an adaptive searching strategy, searching by following the bee, adopting a probability selecting strategy, fully utilizing information contained in relatively poor honey sources to keep population diversity and the like.

Description

An improved swarm algorithm for UAV trajectory planning

Technical Field

The present invention relates to the technical field of unmanned aerial vehicle (UAV) trajectory planning, and in particular to an unmanned aerial vehicle (UAV) trajectory planning method using an improved bee colony algorithm.

Background technique

As one of the key technologies for autonomous flight of UAVs, trajectory planning has always been a hot topic for scholars at home and abroad. Trajectory planning is a high-dimensional optimization problem with multiple constraints.

Currently, the ABC algorithm is mostly used to solve the three-dimensional trajectory planning of drones and the local trajectory replanning problems when facing sudden threats. However, the current ABC algorithm has some inherent defects, such as: a high probability of drones being discovered and low robustness.

Summary of the invention

The purpose of this section is to summarize some aspects of the embodiments of the present invention and briefly introduce some preferred embodiments. Some simplifications or omissions may be made in this section and the specification abstract and the invention title of this application to avoid blurring the purpose of this section, the specification abstract and the invention title, and such simplifications or omissions cannot be used to limit the scope of the present invention.

Therefore, the purpose of the present invention is to provide a UAV trajectory planning method based on an improved swarm algorithm, which introduces an adaptive search strategy, a new probability selection strategy and a Logistic chaos search operator to strengthen the original algorithm, an improved ABC algorithm, so that the probability of the UAV being discovered is reduced and the robustness is improved.

To solve the above technical problems, according to one aspect of the present invention, the present invention provides the following technical solutions:

A UAV trajectory planning method based on an improved bee swarm algorithm, comprising:

S1, population initialization - randomly send N bees to find the nectar source x _ij ;

S2, nectar source benefit evaluation - obtain the nectar source benefit value, and remove the last N/2 groups of solutions with poor nectar source quality according to the nectar source benefit value;

Among them, _Si is the objective function value corresponding to the honey source;

S3, hired bee search - uses an adaptive search strategy to search, namely:

in, For the current T generation honey source/> New nectar source in the neighborhood, Φ _ij is a random variable between -1 and 1, T _max is the maximum number of iterations, ω is the weight factor, ω _max and ω _min are the maximum and minimum weight values respectively;

S4, follow the bee search - adopt a probabilistic selection strategy to make full use of the information contained in relatively poor nectar sources to maintain population diversity, that is:

S5. Scout bee search - When an employed bee transforms into a scout bee, a D-dimensional random vector y ₀ = [y ₀₁ , y ₀₂ , …, y _0D ] (y ₀ ∈ [0, 1]) is generated. The vector y ₀ is used as the initial value of the iteration. The Logistic equation is used for chaotic iteration to obtain the sequence y _nj ; according to the formula The potential unknown solutions near the local optimal value are mined, processed by the chaos operator, and added to the individuals to be searched x _ij , thereby generating new individuals;

S6. Record the current optimal solution. Record the optimal solution obtained in the current iteration and return to step S3 to allow the population to evolve to the next generation and search in a loop until a termination condition is encountered.

As a preferred solution of the unmanned aerial vehicle trajectory planning method of the improved bee colony algorithm described in the present invention, the types of bees are divided into three types: employed bees, follower bees and scout bees;

The total population of the bee colony is N, and the number of employed bees and follower bees each accounts for half of the total population; each nectar source is a D-dimensional vector, where D represents the number of solutions that need to be optimized.

As a preferred solution of the unmanned aerial vehicle trajectory planning method of the improved bee swarm algorithm described in the present invention, in the step S2, ω _max =0.9 and ω _min =0.2.

As a preferred solution of the unmanned aerial vehicle trajectory planning method of the improved bee swarm algorithm described in the present invention, in step S1,

in, and/> are the lower limit and upper limit of the value of x _ij , i＝1,2,…,N, j＝1,2,…,D.

Compared with the prior art, the present invention has the following beneficial effects: the present invention introduces an adaptive search strategy, a new probability selection strategy and a Logistic chaos search operator to strengthen the original algorithm, an improved ABC algorithm, so that the probability of the drone being discovered is reduced and the robustness is improved.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the present invention will be described in detail below in combination with the accompanying drawings and detailed embodiments. Obviously, the drawings described below are only some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without creative labor. Among them:

FIG1 is a schematic diagram of the UAV track obtained by the algorithm of the embodiment of the present invention and the comparative algorithms: the ABC algorithm and the GA algorithm;

FIG2 is a schematic diagram of iterative curves obtained by the algorithm of the embodiment of the present invention and the comparative algorithms: the ABC algorithm and the GA algorithm;

FIG3 is a schematic diagram of the trajectory planning results under different dimensions of the present invention;

FIG4 is a schematic diagram of the trajectory re-planning result of the present invention in response to sudden threats.

Detailed ways

In order to make the above-mentioned objects, features and advantages of the present invention more obvious and easy to understand, the specific embodiments of the present invention are described in detail below with reference to the accompanying drawings.

Secondly, the present invention is described in detail with reference to schematic diagrams. When describing the embodiments of the present invention in detail, for the sake of convenience, the cross-sectional diagrams showing the device structure will not be partially enlarged according to the general scale, and the schematic diagrams are only examples, which should not limit the scope of protection of the present invention. In addition, in actual production, the three-dimensional dimensions of length, width and depth should be included.

In order to make the objectives, technical solutions and advantages of the present invention more clear, the embodiments of the present invention will be further described in detail below with reference to the accompanying drawings.

In military applications, there are various enemy threats hidden in the flight space, and these threats will also change constantly, so it is difficult to obtain accurate information about the threats in the planning space in advance. On the other hand, the fuel consumption of the UAV is related to the fuel consumption rate of the engine, the propeller speed and the engine output power, and the relationship is nonlinear. In order to simplify the trajectory planning problem, the following assumptions are made: (1) All threat information and terrain information in the planning space are known; (2) The fuel consumption of the UAV is only related to the range; (3) The dynamics and aerodynamic characteristics of the UAV body are ignored; (4) Atmospheric interference, gust interference, etc. are ignored; (5) The flight speed of the UAV remains unchanged.

Assume (x _α , y _α , z _α ) is a point in the planning space, x _α and y _α are the longitude and latitude information, and z _α is the altitude information. Therefore, the three-dimensional space of trajectory planning can be described as ^[8] :

Among them, x _max and y _max are the maximum longitude and latitude of the drone battlefield terrain; h and H are the minimum and maximum altitudes of the map; z _min and z _max are the minimum and maximum safe distances of the drone from the ground.

The terrain model can be composed of the superposition of mountains with different central positions, so it can be described by an exponential function with e as the base, that is:

Among them, (x, y) represents the coordinates of the mountain, ( _ak , _bk ) is the coordinates of the central symmetry axis of the mountain, and _hk is the highest point of the mountain.

Track cost model

The track cost model consists of a threat cost model and a fuel consumption cost model. The threat cost mainly considers the anti-aircraft gun threat and radar threat ^[9] .

(1) Radar threat. Usually the detection range of radar is circular, so the threat probability of radar to UAV is:

_PR = 1/ ^d2 , _d≤dmax (3)

Where d is the distance from the radar center to the UAV; d _max is the maximum radius of the radar detection area.

(2) Anti-aircraft gun threat. Similar to radar threat, the range of anti-aircraft gun threat is also circular, so the threat probability of anti-aircraft gun to UAV is:

P _g =1/d ² ,d≤d _max (4)

(3) Fuel consumption cost. Fuel consumption is related to the voyage, so the fuel consumption cost is considered to be the total voyage.

In addition, other constraints need to be considered, namely:

(1) Maximum turning angle. The change of the UAV's flight heading is achieved by controlling the yaw channel. Due to inertia, changing the heading requires a turning radius and a turning time. Let the projection of the track segment l _i on the horizontal plane be _mi = ( _xi -xi _-1 , _yi -yi _-1 ), and let the maximum allowable turning angle of the UAV be _θt , then the constraint can be described as:

(2) Maximum dive angle/climb angle. The dive angle and climb angle of the UAV are determined by the maneuverability of the UAV, which limits the maximum dive and climb angle of the planned trajectory in the height direction (z direction). Assuming the maximum dive angle/climb angle of the UAV is θ _p , the constraint can be expressed as:

(3) Shortest track length. In actual flight, the UAV must maintain a certain distance in order to change its current flight attitude. This limitation is not only determined by its maneuverability, but is also often related to its navigation requirements. During long-distance flight, if the UAV frequently turns or flies in a roundabout way, it will increase the navigation error, so the track length should be reduced as much as possible. Assuming that the shortest track length of the UAV is l _min , the mathematical description of this constraint is:

l _i ≥l _min (7)

In summary, the track cost model is mainly composed of the above factors, so the three-dimensional track cost model of the UAV can be expressed as:

In the formula, J ₁ ~ J ₅ represent the threat cost, fuel consumption cost, turning cost, dive angle/climb angle cost and shortest track segment length cost of the UAV track, respectively, and w _k is the corresponding weight factor.

The present invention provides a UAV trajectory planning method based on an improved bee swarm algorithm, which introduces an adaptive search strategy, a new probability selection strategy and a Logistic chaos search operator to strengthen the original algorithm, an improved ABC algorithm, so that the probability of the UAV being discovered is reduced and the robustness is improved.

The specific steps of the UAV trajectory planning method based on the improved bee swarm algorithm are as follows:

(1) Population initialization. Randomly send N bees to find the nectar source x _ij (i = 1, 2, ..., N, j = 1, 2, ..., D), and the solution is feasible. The nectar source is generated by formula (9):

in, and/> are the lower and upper limits of the value of x _ij respectively.

(2) Evaluation of nectar source profitability. The profitability _fi is obtained by formula (10), and the last N/2 groups of solutions with poor nectar source quality are removed according to the value of the nectar source profitability.

Among them, _Si is the objective function value corresponding to the nectar source.

(3) Hired bee search stage. The traditional ABC algorithm will slow down the convergence speed of the algorithm due to excessive exploitation of nectar sources during hired bee search ^[11] . This paper adopts an adaptive search strategy to improve the original search method, namely:

in, For the current T generation honey source/> New honey sources in the neighborhood, Φ _ij is a random variable between -1 and 1, T _max is the maximum number of iterations, and ω is a weight factor. The larger the ω is, the more potential solutions should be explored in the early stage of the algorithm; the smaller the ω is, the better the solution quality should be in the later stage of the algorithm. ω _max and ω _min are the maximum and minimum weight values, respectively. In this problem, through repeated attempts, the best results can be achieved when ω _max = 0.9 and ω _min = 0.2.

(4) Follow-the-bee search phase. As the number of algorithm iterations increases, individuals in the population will continue to evolve in the same direction due to the attenuation of population diversity, and premature convergence is likely to occur. Maintaining population diversity is one of the important indicators for improving the performance of the ABC algorithm. Through analysis, it is found that after multiple iterations, the currently eliminated nectar sources also contain useful information ^[12] . Therefore, this paper adopts a novel probabilistic selection strategy to make full use of the information contained in relatively poor nectar sources to maintain population diversity, namely:

(5) Scout bee search phase. When the number of trials exceeds a certain threshold limit, if the optimal solution has not been found, the current food source is abandoned. The corresponding employed bees also become scout bees to search for nectar sources again. The traditional ABC algorithm is prone to fall into the local optimum at this stage ^[13] . This paper uses the Logistic chaotic search operator to complete the initialization of the scout bees, that is, when the employed bees are transformed into scout bees, a D-dimensional random vector y ₀ = [y ₀₁ , y ₀₂ , …, y _0D ] (y ₀ ∈ [0,1]) is generated. The vector y ₀ is used as the initial value of the iteration, and the Logistic equation is used for chaotic iteration to obtain the sequence y _nj . According to formula (13), potential unknown solutions near the local optimum can be mined, and then added to the individuals to be searched x _ij after being processed by the chaotic operator, thereby generating new individuals:

(6) Record the current optimal solution. Record the optimal solution obtained in the current iteration and return to step (3) to allow the population to evolve to the next generation and search repeatedly until the termination condition is met.

In order to verify the effect of the present invention, the method of the present invention is used as an example, and the ABC algorithm and the GA algorithm are used as comparative examples for analysis, as follows:

The starting point of the drone trajectory planning is (0,0,0), the target point is (90,80,0), and the planning dimension D=10. The PAC-ABC algorithm, ABC algorithm and GA algorithm are used to search for the optimal trajectory at the same time. The initial conditions of the first two algorithms are set to: N=20, limit=15. The conditions of the GA algorithm are set to: the number of antibodies M=20, the crossover factor and the mutation factor are 0.8 and 0.2 respectively. The three algorithms are run 10 times each, 500 iterations each time, and then the best solution is recorded. The results of trajectory planning are shown in Figure 1. As can be seen from the figure, all three algorithms can generate flyable trajectories, but the ABC algorithm and the GA algorithm have to cross the ridge to obtain the trajectory, which will increase the probability of the drone being discovered. The trajectory obtained by the PAC-ABC algorithm flies along the valley and shortens the range compared with the other two algorithms, which is conducive to avoiding threats and achieving low-altitude penetration.

Figure 2 shows the iteration curves of the three algorithms. It can be seen from the figure that the proposed algorithm has the fastest convergence speed, which can converge to the extreme value in about 100 generations, and the track cost is 51.2312, while the track costs of the ABC algorithm and the GA algorithm are 54.9980 and 60.6214 respectively. Under the effect of the improved strategy, the PAC-ABC algorithm can better avoid local optimal values and quickly find the optimal solution.

In order to further verify the robustness of the PAC-ABC algorithm, the effect of this algorithm on solving the UAV trajectory planning problem is evaluated when D is 20 and 30 respectively. The simulation results are shown in Figure 3. As can be seen from the figure, with the increase of the dimension, the PAC-ABC algorithm can still find a better trajectory. This shows that the algorithm proposed in this paper has good robustness.

Sometimes, there are undetected sudden threats hidden in the planning space. When the UAV encounters these sudden threats, the algorithm needs to have the ability to re-plan to avoid these threats. Suppose the UAV suddenly detects an anti-aircraft gun at the coordinate position (40,40,13) from the starting point (0,0,0) to the target point (90,80,0), as shown in Figure 4(a). If the UAV flies according to the original track, the probability of being destroyed is very high. Therefore, local track re-planning is required. The UAV needs to re-plan the track through the PAC-ABC algorithm to avoid sudden threats. Figure 4(b) shows the re-planned local track with a planning time of 1.254s. The corrected track can quickly and effectively avoid sudden threats, thereby ensuring the flight safety of the UAV.

Although the present invention has been described above with reference to the embodiments, various modifications may be made thereto and parts thereof may be replaced with equivalents without departing from the scope of the present invention. In particular, as long as there is no structural conflict, the various features in the embodiments disclosed in the present invention may be used in combination with each other in any manner, and the fact that these combinations are not exhaustively described in this specification is only for the sake of omitting space and saving resources. Therefore, the present invention is not limited to the specific embodiments disclosed herein, but includes all technical solutions falling within the scope of the claims.

Claims (4)

1. An unmanned aerial vehicle track planning method for improving a bee colony algorithm is characterized by comprising the following steps of:

S1, initializing a population, namely randomly dispatching N bees to find honey sources x _ij;

S2, evaluating the honey source yield, obtaining a honey source yield value, and removing N/2 groups of solutions with poor honey source quality according to the honey source yield value;

wherein S _i is the objective function value corresponding to the honey source;

S3, hiring bee search-searching by adopting an adaptive search strategy, namely:

Wherein, For the current generation T of honey source/>The new honey source in the neighborhood, phi _ij is a random variable in-1 to 1, T _max is the maximum iteration frequency omega is a weight factor, and omega _max and omega _min are the maximum weight value and the minimum weight value respectively;

S4, following bee search-adopting a probability selection strategy, so that the information contained in relatively worse honey sources can be fully utilized to keep population diversity, namely:

s5, searching for a scout bee, namely when the hiring bee is converted into the scout bee, generating a D-dimensional random vector y ₀＝[y₀₁,y₀₂,…,y_0D](y₀ E [0,1 ]), taking the vector y ₀ as an iteration initial value, and performing chaotic iteration by a Logistic equation to obtain a sequence y _nj; according to the formula Extracting potential unknown solutions near a local optimal value, processing the potential unknown solutions by a chaos operator, and adding the potential unknown solutions into an individual x _ij to be searched, thereby generating a new individual;

S6, recording the current optimal solution, recording the optimal solution obtained by the current iteration, and returning to the step S3 to enable the population to evolve to the next generation and circularly search until the termination condition is met.

2. The unmanned aerial vehicle flight path planning method of claim 1, wherein the bee species are classified into employment bees, following bees and reconnaissance bees;

wherein the total number of the bee colony is N, and the number of hired bees and following bees is half of the total number of the bee colony; each honey source is a D-dimensional vector, where D represents the number of solutions that need to be optimized.

3. The unmanned aerial vehicle trajectory planning method of claim 1, wherein in step S2, ω _max =0.9 and ω _min =0.2.

4. The unmanned aerial vehicle path planning method of claim 1, wherein in step S1,

Wherein,And/>The lower limit and the upper limit of the value of x _ij are respectively, i=1, 2, …, N, j=1, 2, … and D.