CN111813144B - Multi-unmanned aerial vehicle collaborative route planning method based on improved flocks of sheep algorithm - Google Patents

Abstract

The invention provides a multi-unmanned aerial vehicle collaborative route planning method based on an improved herd algorithm, which is characterized in that under the condition that a plurality of unmanned aerial vehicles are used for carrying out collaborative attack on a known target, mathematical modeling is firstly carried out on the collaborative route planning of the plurality of unmanned aerial vehicles; then, an improved herd optimization algorithm is provided and used for solving the problem of route planning, and a three-dimensional cooperative route meeting the planning requirement is obtained; finally, by comparing with other algorithms, a benchmark function test and a simulation experiment are carried out, and the effectiveness of the method is verified. The method can obviously improve the optimal solution quality and the convergence speed, has simple principle, and is not limited by the space size and the potential parallelism.

Description

A multi-UAV cooperative route planning method based on improved flock algorithm

technical field

The invention relates to the field of UAV route planning, in particular to a multi-UAV cooperative route planning method based on an improved flock algorithm.

Background technique

With the development and maturity of UAV technology and the continuous improvement of intelligence level, UAV will become the leader of the future sky and the main equipment of the armed forces of all countries in the world, and has huge combat potential in the future battlefield. In the modern war of informationization, networking and systemization, in the face of rapid development, relying on a single UAV to perform intelligence reconnaissance, battlefield strikes and other tasks are far from meeting the current mission requirements, and multiple UAVs are used to perform intelligence reconnaissance. Combat missions against multiple targets have become an inevitable trend.

Multi-UAV cooperative route planning is a key technology for multiple UAVs to achieve cooperative operations. The multi-UAV cooperative route planning problem has the characteristics of high-dimensional, multi-constraint and space-time coordination, which is a very challenging problem. To solve this problem, researchers have proposed a variety of methods, including some route planning algorithms, obstacle avoidance techniques, and route adjustment strategies. The current research methods on route planning problems can be divided into several categories: methods based on potential energy fields, such as artificial potential energy field method (APF), have simple principles and fast calculation speed, and are suitable for solving route planning problems with high real-time requirements, but , in some cases it is easy to fall into a stagnation state, resulting in the failure of the plan; the method based on random sampling can quickly search for a route in a complex environment with known or unknown dynamics, but this method is costly , the planned route is not always the optimal route; the search algorithm based on heuristic information is simple and efficient, but it is easy to fall into an infinite loop, and there are many planned route folding points.

SUMMARY OF THE INVENTION

Aiming at the problems of unreliable optimal solution quality and unsatisfactory convergence speed of the traditional swarm intelligence algorithm, the invention establishes a route planning model with multiple constraints according to the characteristics of multi-UAV cooperative route planning, and proposes a multi-constraint algorithm based on the improved herd algorithm. The UAV cooperative route planning method has the advantages of simple algorithm principle, fast planning speed, and no limitation of space size and potential parallelism.

In order to solve the above problems, the present invention now adopts the following technical solutions:

A multi-UAV cooperative route planning method based on an improved flock algorithm, the method includes the following steps:

Step 1: Establish a 3D environment for multi-UAV route planning;

In trajectory planning, an appropriate planning space must be established according to the flight environment and mission requirements. In the current mission environment with mountains as the backdrop, random functions are used to build numerical models to simulate peaks and other threatening obstacles. The mountain model function consists of raw data and a threat-equivalent terrain model. The former is expressed as:

Among them, x and y refer to the point coordinates on the horizontal projection plane; z ₁ refers to the height coordinates corresponding to the coordinate points on the horizontal plane; a, b, c, d, e, f, g are coefficients, which can be obtained by Change parameters to get terrain models for other terrains.

The threat equivalent terrain model is:

where x and y refer to the point coordinates on the horizontal projection plane; z ₂ refers to the peak height; h(i) refers to the height of the highest point of peak i on the basic terrain; x _0i and y _0i refer to the height of the highest point of peak i Coordinates; x _si and y _si refer to variables related to the slope of peak i along the x,y axis. If x _si and y _si are large, the slope of the peak is flat and steep.

The final mountain threat model is obtained by integrating the original digital terrain model into the threat-equivalent terrain model:

z( _x ,y)= _max (z1(x,y),z2(x,y)) (3)

Models for different terrains can be obtained by changing the parameters in the function. In the planning space, the flight path of the drone can be represented by many waypoints. Thus, waypoints are connected to form multiple flight paths, which are linked with origin and destination points to form flight paths. We set the starting point of a drone as S(x ₀ , y ₀ , z ₀ ) and the target point as E(x _e , y _e , z _e ). The number of waypoints is n, and the searched waypoints can be represented by {S, P ₁ , P ₂ ,...,P _n ,E}; in these variables, the coordinates of the trajectory nodes are P _i =(xi _i , y _i , z _i ).

Step 2: Establish a multi-machine collaborative route planning model and determine the route cost function;

The purpose of multi-UAV cooperative route planning is that under the premise of meeting the requirements of safe flight and space-time cooperation, each UAV can search for the corresponding route, and the comprehensive route cost of the UAV fleet must be minimized. Therefore, route planning requires the establishment of the route cost function as an indicator for evaluating the quality of the route. It is necessary to satisfy the multi-UAV space and time coordination constraints by considering the dynamics and threat constraints of a single UAV in the multi-UAV cooperative route planning. . Therefore, given the planning objective, the following cost metrics are considered in the current work: The performance metrics of a single UAV include fuel consumption, maximum climb/slip angle, flight altitude, peak threat and multi-UAV time cooperation. Space collaboration is embodied in multi-UAV route avoidance conflict, setting different flight altitudes that each UAV must avoid. The comprehensive cost function is established as:

Among them, w ₁ , w ₂ , w ₃ , w ₄ and w ₅ respectively refer to the weights of different cost indicators, and the sum of the weights is 1. Routes that meet different requirements can be obtained by adjusting the weights. To ensure that all cost metrics are included in the route planning, the functions are normalized according to the range of function values, and then a weighted summation is performed.

The cost of fuel consumption is related to the length and speed of the flight path. Assuming the drone is always flying at a certain speed, the fuel cost can be replaced by the route length:

where (x _i+1 , y _i+1 , z _i+1 ) and ( _xi , y _i , z _i ) correspond to the coordinates of adjacent waypoints.

J _angle refers to the cost of the maximum climb/slip angle, expressed as:

Among them, θ _i refers to the climb/slip angle of the adjacent point of a certain route.

In order to meet the requirements of flight safety and concealment, the flight altitude cannot be too low or too high. The height cost can be expressed as

Among them, hi refers to the height of route _{i on a certain route, and safth i refers} to the minimum safe height of each UAV.

Collision with the mountains during the flight of the drone must be avoided. The peak model is represented by a conic approximation, the route is divided into m equal parts, and m-1 sampling points are obtained at the center. The threat cost of the entire route is expressed as

where n represents the number of waypoints, K represents the number of peaks, threat(j,k) is the threat cost of sampling points (x _i , y _i , z _i ) and a certain peak in the current interval, expressed as:

R _T (h)=(H(k)-h)/tanθ(10)

Among them, n refers to the number of waypoints, K refers to the number of peaks, _H (k) refers to the height of peak k, and RT refers to the maximum extension radius. In addition, h _j is the current flying height of the drone, d _T refers to the distance from the drone to the peak symmetry axis, d _Tmin represents the minimum distance allowed on the terrain, and θ refers to the slope of the terrain. Terrain threats are shown in Figure 2.

同样，假设无人机j的飞行时间在

的范围内，如果两个无人机的飞行时间相交，则时间上的合作是可行的，即The cooperative cost function implies temporal cooperation, requiring all drones to reach the target point at the same time as possible. If the route of a route cannot satisfy the time coordination constraints, the route must be corrected. Assuming that the flight speed of UAV _i is within the range of [v _min ,v _max ] and the heading is within the range of Li, its flight time is

Similarly, suppose the flight time of drone j is

Within the range of , if the flight times of the two UAVs intersect, the cooperation in time is feasible, that is,

According to the time cooperation evaluation formula between routes, the time cooperation cost function is obtained based on the planning model of the current work:

Among them, T _min refers to a time period in which the flight distance of a certain route is small in the flight time period, and T _inter indicates the intersection of the flight times of two routes.

Step 3: Propose an improved flock optimization algorithm;

The flock optimization algorithm achieves fast global exploration by simulating the leader, and makes the flock quickly approach the known global optimal solution. The local development is achieved through the interaction of the herd, which further accelerates the convergence speed, and the herd supervision mechanism is used to judge whether the local optimal solution has been entered and quickly jumped out of the local optimal solution.

3.1 Leaders

The leader refers to the flock with the best fitness function value in the flock, and the leader refers to the behavior of each flock moving towards the leader. The corresponding global exploration mechanism of the algorithm is to ensure the search performance. The position of the new flock is updated only if the fitness function value of the new flock is better than that of the old flock. Figure 3 is a flowchart of an algorithm for guiding a flock.

When the flock moves to the leader, the position of the corresponding flock is updated:

代表第i个羊群的更新位置，

代表第i个羊群尚未更新的位置，x_bellwether代表领头羊。in,

represents the updated position of the ith flock,

Represents the position of the ith flock that has not been updated yet, and x _bellwether represents the leader.

3.2 Herd interaction

The herd interaction behavior corresponds to the local development mechanism of the algorithm. Each flock _xi in the flock randomly selects another random flock x _j as the flock interaction strategy. If the fitness value of the selected flock x _i is better than that of the random flock x _j , then update to a position far from x _j , update to a position near x _i , and vice versa:

Equation (14) indicates that x _i is updated to the position of x _j , and Equation (15) indicates that x _j is updated to the position of x _i .

Also, to ensure the performance of the search, the position of the new flock is updated only when the fitness function value of the new flock is better than that of the old flock. Figure 4 is a flow chart of the herd interaction algorithm.

3.3 Sheepdog supervision

When the fitness function difference between the previous generation and the previous generation is less than the threshold ε, a shepherd supervision mechanism is introduced to jump out of the local optimization. The shepherd will herd each flock with a certain probability p, that is, the flock will be reinitialized with a certain probability p. Figure 5 is a flow chart of the shepherd supervision algorithm.

3.4 Improved flock algorithm

The original flock algorithm needs to calculate the fitness function value of the population for many times. The movement mode of the population is too simple, the supervision of sheep herding is too complicated, and the parameter selection in the actual project is difficult, so it is not easy to realize this project. Aiming at the problem of flock algorithm, an improved flock algorithm is proposed.

In the flock algorithm, the position can be updated when it is better to use the fitness function multiple times. The value of the fitness function of the flock needs to be calculated multiple times. In practical engineering problems, the complexity of the fitness function may increase the calculation time of the algorithm, and the operation may make the algorithm converge too fast and fall into local optimization. Therefore, the improved flock algorithm proposed in this paper removes the position update operation with better fitness, thereby reducing the complexity of the algorithm.

In order to solve the problem of the movement mode of a single population in the original flock algorithm, the present invention improves the population position update mode of the leader interacting with the flock. Equation (16) (17) shows the mathematical model of leader leader position update in the improved sheep algorithm:

和

是系数矢量，

是领头羊的位置矢量，并且

表示羊群的位置矢量。

和

向量和的计算如下：where t represents the current iteration, and

and

is the coefficient vector,

is the position vector of the leader, and

The position vector representing the flock.

and

The vector sum is calculated as follows:

的分量在迭代过程中从2线性减少到0，并且r₁,r₂是[0，1]中的随机向量。in

The components of are linearly reduced from 2 to 0 during the iteration, and r ₁ , r ₂ are random vectors in [0, 1].

In the flock interaction mechanism, when the fitness value of the randomly selected flock is good, the update model of the current flock migration to the random flock is as follows:

是第i个羊和随机羊之间的距离，l是[-1，1]中的随机值，b是用于定义对数螺旋形状的常数。

是随机羊群的位置向量。相反，随机羊群向当前羊群移动的数学模型如下所示：in,

is the distance between the ith sheep and a random sheep, l is a random value in [-1, 1], and b is a constant used to define the shape of the logarithmic spiral.

is the position vector of random flocks. Instead, the mathematical model for the movement of a random flock to the current flock looks like this:

Due to the complexity of the shepherd supervision mechanism, different thresholds and probabilities have a great impact on the performance of the algorithm, so it is difficult to select appropriate parameters in practical projects. In this article, the supervision of the shepherd is simplified and replaced with the Levi flight strategy. The mathematical model is shown in formula (22):

表示逐项相乘。式(20)本质上是一个随机游走方程，可以防止羊群算法陷入局部最优解，并确保算法在搜索空间中得到有效开发，分布方程如公式(23)所示：in

Indicates item-by-item multiplication. Equation (20) is essentially a random walk equation, which can prevent the flock algorithm from falling into a local optimal solution and ensure that the algorithm is effectively developed in the search space. The distribution equation is shown in Equation (23):

Levy～u=t ^-λ , 1<λ≤3 (23)

A Levi flight is a special kind of random flight in which the step size has a heavy-tailed probability distribution. Mantegna's algorithm simulates a λ-stable distribution by generating random step sizes s with the same behavior as Levi's flights, as follows:

和

均为正态随机分布where s is the step size of the Levy flight, namely Levy(λ), in the equation λ(21) obeys the following formula: λ=1+β, β=1.5,

and

normal random distribution

The general steps of the improved flock algorithm can be summarized as the pseudocode shown in Table 1.

Table 1 Improved flock algorithm (ISO) algorithm steps

Step 4: Multi-UAV collaborative route planning process;

Since the swarm algorithm has the potential parallel capability, the present invention constructs the UAV cooperative route set based on the original algorithm and multiple swarm ideas. All routes of the drone are represented by multiple subgroups. The number of subpopulations is determined by the number of drones, each subpopulation evolves independently, and the exchange of information occurs only during the en-route assessment. When evaluating the individuals of a subpopulation, the representative individuals selected from other subpopulations are combined with the individuals in the current population to form a cooperative route, and the route cost function is used as the fitness value of the population for evaluation. Then, the fitness of individuals in other subpopulations is calculated in turn. Individuals with small synergistic functions in the evolution process indicate that the route has good synergistic properties. Individuals in each subpopulation interact with other subpopulations through synergistic functions. and route assessment, and finally obtained multiple collaborative routes.

In route planning, the fitness value of each route includes not only the information of its own route cost, but also the information of cooperative interaction with other UAVs. In other words, each UAV will refer to the information when planning its route. Route information for other drones. By choosing a route with a lower comprehensive cost, a more coordinated route can be obtained on the basis of satisfying the single-aircraft flight cost index, and the planned route can meet the collision avoidance and time constraints between multiple UAVs. The flow chart of multi-UAV route planning based on the improved flock algorithm is shown in Figure 5.

Compared with the traditional swarm intelligence algorithm and the basic sheep flock algorithm, the quality of the optimal solution obtained in the multi-UAV cooperative route planning is more reliable, the algorithm has the ability to jump out of the local optimal solution, the convergence speed is faster and the stability is more stable. high.

Description of drawings

Figure 1 is a flow chart of multi-UAV route planning based on the improved flock algorithm.

Figure 2 shows the terrain threat map.

Figure 3 is the flow chart of the leading sheep leading algorithm.

Figure 4 is a flow chart of the herd interaction algorithm.

Figure 5 is a flow chart of the sheepdog supervision algorithm.

FIG. 6 is a convergence curve based on the reference function f1.

FIG. 7 is a convergence curve based on the reference function f2.

FIG. 8 is a convergence curve based on the reference function f3.

FIG. 9 is a convergence curve based on the reference function f4.

Fig. 10 is a three-dimensional UAV cooperative route diagram in the multi-dimensional and multi-UAV cooperative route planning in case 1.

FIG. 11 is a contour map of the cooperating route in case 1. FIG.

Figure 12 is the ISO-based route cost convergence curve for each UAV in Case 1.

Figure 13 is the ISO-based route cost convergence curve in Case 1.

Fig. 14 is a three-dimensional UAV cooperative route diagram in the multi-dimensional and multi-UAV cooperative route planning in case 2.

FIG. 15 is a contour map of the cooperating route in case 2. FIG.

Figure 16 shows the ISO-based route cost convergence curve for each UAV in Case 2.

Figure 17 is the ISO-based route cost convergence curve in Case 2.

Figure 18 is the 3D UAV cooperative route map in the multi-dimensional and multi-UAV cooperative route planning in case 3

FIG. 19 is a contour map of the cooperating route in case 3. FIG.

Figure 20 is the ISO-based route cost convergence curve for each UAV in Case 3.

Figure 21 is the ISO-based route cost convergence curve in Case 3.

Figure 22 shows the average route cost convergence curve (30 times).

Figure 23 is a distribution diagram of the minimum route cost value.

Detailed ways

The technical solutions of the present invention will be described in detail below in conjunction with the accompanying drawings.

As shown in Figure 1, a multi-UAV cooperative route planning method based on the improved flock algorithm includes the following steps:

Step 1: Establish a 3D environment for multi-UAV route planning;

A digital model is established by using random functions to simulate the mountain peak threat model function; the mountain peak threat model function is composed of the original digital terrain model and the threat equivalent terrain model;

The original digital terrain model is:

Among them, x and y refer to the point coordinates on the horizontal projection plane; z ₁ refers to the height coordinates corresponding to the coordinate points on the horizontal plane; a, b, c, d, e, f, g are terrain model coefficients;

The threat equivalent terrain model is:

where x and y refer to the point coordinates on the horizontal projection plane; z ₂ refers to the peak height; h(i) refers to the height of the highest point of peak i on the basic terrain; x _0i and y _0i refer to the height of the highest point of peak i Coordinates; x _si and y _si refer to variables related to the slope of peak i along the x, y axis;

Integrating the original digital terrain model into the threat equivalent terrain model, the final mountain threat model obtained is:

z( _x ,y)= _max (z1(x,y),z2(x,y)) (3)

Set the starting point of a drone as S(x ₀ , y ₀ , z ₀ ), and set the target point as E(x _e , y _e , z _e ); the number of waypoints is n, the searched waypoint It can be represented by {S, P ₁ , P ₂ ,...,P _n ,E}; in these variables, the coordinates of the trajectory nodes are P _i =(x _i ,y _i ,z _i );

Step 2: Establish a multi-machine collaborative route planning model and determine the route cost function;

Establish the route cost function as an index to evaluate the quality of the route, and consider the performance indicators of a single UAV including fuel consumption, maximum climb/slip angle, flight height, peak threat and multi-UAV time cooperation; set each UAV must different flight altitudes to be avoided;

Build a comprehensive cost function:

Among them, w ₁ , w ₂ , w ₃ , w ₄ and w ₅ respectively refer to the weights of different cost indicators, and the sum of the weights is 1;

Assuming that the drone always flies at a certain speed, the fuel cost J _fuel is replaced by the length of the route, which is expressed as:

where (x _i+1 , y _i+1 , z _i+1 ) and (x _i , y _i , z _i ) correspond to the coordinates of adjacent waypoints;

J _angle refers to the cost of the maximum climb/slip angle, expressed as:

Among them, θ _i refers to the climb/slip angle of the adjacent point of a certain route;

The height cost is expressed as:

Among them, hi refers to the height of route _{i on a certain route, and safth i refers} to the minimum safe height of each UAV;

The threat cost of the entire route is expressed as:

where n represents the number of waypoints, K represents the number of peaks, threat(j,k) is the threat cost of sampling points (x _i , y _i , z _i ) and a certain peak in the current interval, expressed as:

R _T (h)=(H(k)-h)/tanθ(10)

Among them, n refers to the number of waypoints, K refers to the number of peaks, H(k) refers to the height of peak k, and R _T refers to the maximum extension radius; in addition, h _j refers to the current flying height of the UAV, and d _T refers to the distance from The distance from the drone to the peak symmetry axis, d _Tmin represents the minimum distance allowed on the terrain, θ refers to the slope of the terrain;

同样，假设无人机j的飞行时间在

的范围内，如果两个无人机的飞行时间相交，则时间上的合作是可行的，即Assuming that the flight speed of UAV _i is within the range of [v _min ,v _max ] and the heading is within the range of Li, its flight time is

Similarly, suppose the flight time of drone j is

Within the range of , if the flight times of the two UAVs intersect, the cooperation in time is feasible, that is,

The time cooperation cost function obtained according to the time cooperation evaluation formula between routes is:

Among them, T _min refers to the time period in which the flight distance of a certain route is small in the flight time period, and T _inter indicates the intersection of the flight times of the two routes;

Step 3: Propose an improved flock optimization algorithm;

The flock optimization algorithm realizes fast global exploration by simulating the leader, and makes the flock quickly approach the known global optimal solution; realizes local development through flock interaction, further accelerates the convergence speed, and adopts flock supervision Mechanism to judge whether it has entered the local optimal solution and quickly jumped out of the local optimal solution;

3.1 Leaders

The leader refers to the flock with the best adaptive function value in the flock, and the leader refers to the behavior of each flock moving to the leader; the corresponding global exploration mechanism of the algorithm is to ensure the search performance; The position of the new flock is updated only when the fitness function value is better than that of the old flock;

When the flock moves to the leader, the position of the corresponding flock is updated to:

代表第i个羊群的更新位置，

代表第i个羊群尚未更新的位置，x_bellwether代表领头羊；in,

represents the updated position of the ith flock,

Represents the position of the ith flock that has not been updated, and x _bellwether represents the leader;

3.2 Herd interaction

The flock interaction behavior corresponds to the local development mechanism of the algorithm; each flock _xi in the flock will randomly select another random flock x _j as the flock interaction strategy; if the fitness of the selected flock _xi If the value is better than the fitness value of the random flock x _j , it is updated to a position far from x _j , updated to a position near x _i , and vice versa:

Equation (14) indicates that x _i is updated to the position of x _j , and Equation (15) indicates that x _j is updated to the position of x _i ;

Similarly, in order to ensure the performance of the search, the position of the new flock is updated only when the fitness function value of the new flock is better than that of the old flock;

3.3 Sheepdog supervision

When the fitness function difference between the previous generation and the previous generation is less than the threshold ε, the shepherd supervision mechanism is introduced to jump out of the local optimization; the shepherd will graze each sheep with a certain probability p, that is, the sheep will graze with a certain probability p reinitialize;

3.4 Improved flock algorithm

An improved flock algorithm is proposed, in which the mathematical model of leader position update is as follows:

和

是系数矢量，

是领头羊的位置矢量，并且

表示羊群的位置矢量；where t represents the current iteration, and

and

is the coefficient vector,

is the position vector of the leader, and

represents the position vector of the flock;

和

向量和的计算如下：

and

The vector sum is calculated as follows:

的分量在迭代过程中从2线性减少到0，并且r₁,r₂是[0，1]中的随机向量；in

The components of is linearly reduced from 2 to 0 in the iterative process, and r ₁ , r ₂ are random vectors in [0, 1];

In the flock interaction mechanism, when the fitness value of the randomly selected flock is good, the update model of the current flock migration to the random flock is as follows:

是第i个羊和随机羊之间的距离，l是[-1，1]中的随机值，b是用于定义对数螺旋形状的常数；

是随机羊群的位置向量；相反，随机羊群向当前羊群移动的数学模型如下所示：in,

is the distance between the ith sheep and a random sheep, l is a random value in [-1, 1], and b is a constant used to define the shape of the logarithmic spiral;

is the position vector of the random flock; instead, the mathematical model for the movement of the random flock to the current flock is as follows:

Simplify and replace the supervision of the shepherd with the Levi flight strategy; the mathematical model looks like this:

表示逐项相乘；in

means multiply item by item;

The distribution equation of formula (20) is as follows:

Levy～u=t ^-λ , 1<λ≤3 (23)

A Levi flight is a special kind of random flight in which the step size has a heavy-tailed probability distribution; Mantegna's algorithm simulates a λ-stable distribution by generating a random step size s with the same behavior as a Levi flight, as follows

和

均为正态随机分布where s is the step size of the Levy flight, namely Levy(λ), in the equation λ obeys the following formula: λ=1+β, β=1.5,

and

normal random distribution

Step 4: Multi-UAV collaborative route planning process;

The invention constructs a set of UAV cooperative routes based on the original algorithm and the idea of multiple groups; all routes of the UAV are represented by multiple subgroups; the number of subgroups is determined by the number of UAVs, and each subgroup evolves independently , the information exchange is only carried out during the route evaluation; when evaluating the individuals of the subpopulation, the representative individuals selected from other subpopulations are combined with the individuals in the current population to form a cooperative route, and the route cost function is used as The fitness value of the population is evaluated; then the fitness of individuals in other subpopulations is calculated in turn. Individuals with small synergistic functions during the evolution process indicate that the route has good synergistic properties, and individuals in each subpopulation pass through The collaborative function conducts information interaction and route assessment with other subgroups, and finally obtains multiple collaborative routes;

In route planning, the fitness value of each route includes not only the information of its own route cost, but also the information of cooperation and interaction with other drones, that is, each drone will refer to other drones when planning its route. The route information of the aircraft; by selecting a route with a lower comprehensive cost, on the basis of satisfying the single aircraft flight cost index, a better coordinated route is obtained, and the planned route meets the collision avoidance and time constraints between multiple UAVs;

In order to verify the performance of the improved flock algorithm, the present invention will be tested based on four classical benchmark functions. Reference functions are shown in Table 2.

Table 2 Benchmark functions

where Dim represents the dimension of the function, Range represents the boundary of the function search space, and f _min represents the minimum value of the function. The unimodal test functions (f ₁ ~ f ₂ ) with unique global optimal solutions can test the global search ability and convergence of the algorithm, while the multimodal test functions (f ₁ ~ f ₂ ) with various local optimal solutions The ability to test the local development of the algorithm and local optimization can be avoided.

Step 1, performance analysis and discussion;

To further test the performance of the algorithm and avoid unexpected situations, the improved flock algorithm is compared with the original flock optimization algorithm (SO), particle swarm optimization algorithm (PSO) and gray wolf optimization algorithm (GWO). Each algorithm was run 30 times on each benchmark function, the number of each experimental population was set to 30, and the maximum number of iterations was set to 500. For a fair comparison, all common parameters (e.g. population) size, dimensions and maximum algebra settings of the different algorithms are the same. The relevant parameters of these algorithms are shown in Table 3.

Table 3 Parameter values for each algorithm

The test results (max, min, mean and standard deviation) are shown in Table 4.

Table 4 Test results for each benchmark function test

The convergence curves are shown in Figures 6 to 9.

The test results of the improved flock algorithm on the benchmark function are obviously better than other algorithms, which reflects the advantages of the improved flock algorithm in global search and local development, and has great potential in solving optimization problems.

Step 2. Simulation environment setting and analysis;

The planning space is set to 100km×100km×500m, including 6 peaks. The parameters of the original digital terrain model were set as a=0.1, b=0.01, c=1, d=0.1, e=0.2, f=0.4 and g=0.02. The height of the peak, the horizontal coordinates of the highest point and the slope parameters are listed in Table 5. The multi-UAV cooperative route planning is carried out under the known task assignment scheme. In the simulation experiments, the route sub-population is initialized according to the number of UAVs. The number of individuals in the population, iteration and waypoint is 50, 100 and 10, respectively. The weight coefficients of all cost functions correspond to 0.4, 0.2, 0.1, 0.2, and 0.1, respectively, and the flight speed of the UAV is in the range of 40–60m/s.

Table 5 Model parameters for peaks

Case 1: 3 The drone starts from the starting point and reaches the designated target point to perform the mission. The coordinates of the start and target points are shown in Table 6.

Table 6 Coordinates of all UAV start and target points

3D route planning and contour maps for each UAV are shown in Figures 10 and 11. The cost and composite route cost convergence curves for each UAV are plotted in Figures 12 and 13.

Figures 10 and 11 illustrate that all UAVs can effectively avoid threats and reach the target point. The cost function value of each UAV gradually converges with the increase of iteration time, which verifies the effectiveness of the algorithm. Through the simulation, the flight time interval (unit: s) and range (unit: km) of each UAV are listed in Table 7. The time intersection is [1828.9454, 2562.7885]. By setting different flight speeds for all drones, time coordination needs can be met.

Table 7 Flight time and range of each drone

Scenario 2: 4 drones fly to 2 target points. Table 8 lists the coordinates of the start and target points.

Table 8 Coordinates of the origin and destination points of all UAVs

As shown in Figures 14 and 15, the planned route map of the UAV was obtained. The en-route cost convergence and integrated cost curves for each UAV are shown in Figures 16 and 17.

Through simulation, the flight time interval (unit: s) and range (unit: km) of each UAV are listed in Table 9. The time intersection is [1936.2102, 2443.9682]. The planned routes and voyages are close enough to avoid obstacles effectively. If the drones are close to each other, collisions can be avoided by setting different flight heights.

Table 9 Flight time and range of each drone

Scenario 3: 6 drones fly to 6 target points. The coordinates of the start and target points are listed in Table 10.

Table 10 Coordinates of the origin and destination points of all UAVs

As shown in Figures 18 and 19, the planned route map of the UAV was obtained. Figures 20 and 21 plot the en-route cost convergence and composite cost curves for each UAV.

Through simulation, flight time interval (unit: s) and range (unit: s) Table 11 lists the kilometers of each UAV. The time intersection is [1779.3519, 2475.9175]. The planned route and range are close enough to avoid obstacles effectively. If the drones are close to each other, collisions can be avoided by setting different flight heights.

Table 11 Flight time and range of each drone

Step 3: Compare and verify;

Based on Case 3, Grey Wolf Optimizer (GWO), Particle Swarm Optimization (PSO), Differential Evolution (DE) PSO, DE and GWO algorithms are used for multi-UAV collaboration route planning. In addition, the improved flock algorithm is compared with the latest improved gray wolf algorithm (IGWO) and hybrid gray wolf algorithm (HGWO). The simulation results are compared with the proposed algorithm to verify the effectiveness of the improved strategy. Among these factors, the PSO algorithm parameters include the number of particles being 50, the learning factor c1=c2=2 and the inertia factor decreasing linearly from 0.96 to 0.2; the DE algorithm parameters include the number of chromosomes 50, the upper limit of the scaling factor (0.6) and Lower bound (0.2), mutation rate (0.5) and crossover probability (0.6). The GWO, IGWO and HGWO algorithms are consistent with the SO algorithm, the number of individuals in the subpopulation, the number of iterations and the number of waypoints are 50, 150 and 10, respectively, and the algorithm is executed 30 times each time. As shown in Figure 22 and Figure 23, the average convergence curve after 100 iterations of each algorithm and the distribution of the minimum cost result after each iteration are obtained.

Compared with PSO, DE, GWO, HGWO and IGWO algorithms, the final stable value of the improved flock algorithm is significantly better than other algorithms, and the convergence speed is faster. The results show that the improved flock optimization algorithm is superior to other algorithms in terms of convergence speed and convergence accuracy, and can effectively solve the multi-UAV cooperative route planning problem.

There are many specific application ways of the present invention, the above are only the preferred embodiments of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the principles of the present invention, several improvements can also be made, These improvements should also be regarded as the protection scope of the present invention.

Claims (1)

1. a multi-unmanned aerial vehicle collaborative route planning method based on improved flock algorithm, is characterized in that, comprises the steps: Step 1: Establish a 3D environment for multi-UAV route planning; The mountain threat model function consists of the original digital terrain model and the threat equivalent terrain model; The original digital terrain model is:

Among them, x and y refer to the point coordinates on the horizontal projection plane; z ₁ refers to the height coordinates corresponding to the coordinate points on the horizontal plane; a, b, c, d, e, f, g are terrain model coefficients; The threat equivalent terrain model is:

where x and y refer to the point coordinates on the horizontal projection plane; z ₂ refers to the peak height; h(p) refers to the height of the highest point of peak p on the basic terrain; x _0p and y _0p refer to the height of the highest point of peak p coordinates; x _sp and y _sp refer to variables related to the slope of the peak p along the x, y axis; Integrating the original digital terrain model into the threat equivalent terrain model, the final mountain threat model obtained is: z( _x ,y)= _max (z1(x,y),z2(x,y)) (3) Set the starting point of a drone as S(x ₀ , y ₀ , z ₀ ), and set the target point as E(x _e , y _e , z _e ); the number of waypoints is n, the searched waypoint It can be represented by {S, P ₁ , P ₂ ,...,P _n ,E}; in these variables, the coordinates of the trajectory nodes are P _s =(x _s ,y _s ,z _s ); s refers to the first s waypoints, (x _s , y _s , z _s ) are the corresponding three-dimensional coordinates; Step 2: Establish a multi-machine collaborative route planning model and determine the route cost function; Establish the route cost function as an index to evaluate the quality of the route, and consider the performance indicators of a single UAV including fuel consumption, maximum climb/slip angle, flight height, peak threat and multi-UAV time cooperation; set each UAV must different flight altitudes to be avoided; Build a comprehensive cost function:

Among them, w ₁ , w ₂ , w ₃ , w ₄ and w ₅ respectively refer to the weights of different cost indicators, and the sum of the weights is 1; Assuming that the drone always flies at a certain speed, the fuel cost J _fuel is replaced by the length of the route, which is expressed as:

where (x _s+1 , y _s+1 , z _s+1 ) and (x _s , y _s , z _s ) correspond to the coordinates of adjacent waypoints; J _angle refers to the cost of the maximum climb/slip angle, expressed as:

Among them, θ _s refers to the climb/slip angle of the adjacent point of a certain route; The height cost is expressed as:

Among them, h _t refers to the height of the route t on a certain route, and safety _t refers to the minimum safe height of each UAV; the threat cost of the entire route is expressed as:

where n represents the number of waypoints, K represents the number of peaks, and threat(j,k) is the threat cost of the jth sampling point of the current route segment about the kth peak, expressed as:

R _T (h)=(H(k)-h)/tanθ(10) Among them, n is the number of waypoints, K is the number of peaks, H(k) is the height of peak k, in addition, h _j is the current flying height of the drone, d _T is the symmetry axis from the drone to the peak distance, d _Tmin represents the minimum distance allowed on the terrain, θ refers to the slope of the terrain; [v _min ,v _max ] is the flight speed range of the drone, v _min is the minimum flight speed of the drone, and v _max is the maximum flight speed of the drone; assuming that the flight speed of the drone u is in [v _min ,v _max ] range, and the _heading is within the range of Lu, its flight time is

Likewise, suppose the flight time of the drone v is

Within the range of , if the flight times of the two UAVs intersect, the cooperation in time is feasible, that is,

The time cooperation cost function obtained according to the time cooperation evaluation formula between routes is:

Among them, T _min refers to the time period in which the flight distance of a certain route is small in the flight time period, and T _inter indicates the intersection of the flight times of the two routes; Step 3: Propose an improved flock optimization algorithm; The flock optimization algorithm realizes fast global exploration by simulating the leader, and makes the flock quickly approach the known global optimal solution; realizes local development through flock interaction, further accelerates the convergence speed, and adopts flock supervision Mechanism to judge whether to enter the local optimal solution and quickly jump out of the local optimal solution; 3.1 Leaders The leader refers to the flock with the best adaptive function value in the flock, and the leader refers to the behavior of each flock moving to the leader; the corresponding global exploration mechanism of the algorithm is to ensure the search performance; The position of the new flock is updated only when the fitness function value is better than that of the old flock; When the flock moves to the leader, the position of the corresponding flock is updated to:

in,

represents the updated position of the ith flock,

Represents the position of the ith flock that has not been updated, and x _bellwether represents the leader; 3.2 Herd interaction The flock interaction behavior corresponds to the local development mechanism of the algorithm; each flock _xi in the flock will randomly select another random flock x _j as the flock interaction strategy; if the fitness of the selected flock _xi If the value is better than the fitness value of the random flock x _j , it is updated to a position far from x _j , updated to a position near x _i , and vice versa:

Equation (14) indicates that x _i is updated to the position of x _j , and Equation (15) indicates that x _j is updated to the position of x _i ; Similarly, in order to ensure the performance of the search, the position of the new flock is updated only when the fitness function value of the new flock is better than that of the old flock; 3.3 Sheepdog supervision When the fitness function difference between the previous generation and the previous generation is less than the threshold ε, the shepherd supervision mechanism is introduced to jump out of the local optimization; the shepherd will graze each sheep with a certain probability, that is, the sheep will be regenerated with a certain probability. initialization; 3.4 Improved flock algorithm An improved flock algorithm is proposed, in which the mathematical model of leader position update is as follows:

where t represents the current iteration, and

and

is the coefficient vector,

is the position vector of the leader, and

represents the position vector of the flock;

and

The vector sum is calculated as follows:

in

The component of is linearly reduced from 2 to 0 during the iteration, and

is a random vector in [0, 1]; in the flock interaction mechanism, when the fitness value of the randomly selected flock is good, the update model for the migration of the current flock to the random flock is as follows:

in,

is the distance between the ith sheep and a random sheep, l is a random value in [-1, 1], and r is a constant used to define the shape of the logarithmic spiral;

is the position vector of the random flock; instead, the mathematical model for the movement of the random flock to the current flock is as follows:

Simplify and replace the supervision of the shepherd with the Levi flight strategy; the mathematical model looks like this:

in

means multiply item by item; The distribution equation of formula (20) is as follows: Levy～u=t ^-λ , 1<λ≤3 (23) A Levy flight is a special kind of random flight in which the step size has a heavy-tailed probability distribution; Mantegna's algorithm simulates a λ-stable distribution by generating a random step size _slevy with the same behavior as a Levi flight, as follows

where _slevy is the step size of the Levi flight, namely Levy(λ), in the equation λ obeys the following formula: λ=1+β, β=1.5,

and

normal random distribution

The Γ() function, the gamma function in probability theory, is defined as

Step 4: Multi-UAV collaborative route planning process; Based on the original algorithm and multi-swarm thinking, a set of UAV cooperative routes is constructed; all routes of UAVs are represented by multiple sub-populations; the number of sub-populations is determined by the number of UAVs, each sub-population evolves independently, and the information Swapping is only performed during route assessment; when assessing individuals in a subpopulation, representative individuals selected from other subpopulations are combined with individuals in the current population to form a collaborative route, and the route cost function is used as the population Then, the fitness of individuals in other subpopulations is calculated in turn. Individuals with small cooperative functions during the evolution process indicate that the route has good cooperative properties. Individuals in each subpopulation pass the cooperative function. Conduct information interaction and route assessment with other subpopulations, and finally obtain multiple collaborative routes; In route planning, the fitness value of each route includes not only the information of its own route cost, but also the information of cooperation and interaction with other drones, that is, each drone will refer to other drones when planning its route. The route information of the aircraft is obtained; by selecting a route with a lower comprehensive cost, a route with better coordination is obtained on the basis of satisfying the single-aircraft flight cost index, and the planned route meets the collision avoidance and time constraints between multiple UAVs.

Images