CN110058613B - A multi-UAV and multi-ant colony collaborative search target method - Google Patents

Abstract

The invention discloses a multi-UAV and multi-ant colony collaborative search target method, comprising the following steps: S1: using a grid method to divide and label the search sea area, and establish a target probability graph model; S2: establish an objective function, The man-machine steering cost, UAV collision threat cost, and search probability are weighted and summed; S3: The multi-ant colony algorithm is used to carry out a collaborative path optimization design for multiple UAVs. By setting the maximum number of iterations N _max , execute S32 and S33 until The optimal search path is output until the maximum number of iterations is satisfied. This method makes full use of the probability map characteristics of targets in the sea area to design new ant colony pheromone, including local and global initialization and update rules, so that the ant algorithm can quickly complete the trajectory planning of the UAV, avoiding the problem of repeated search, without Human-machine search paths intersect to improve search efficiency.

Description

A multi-UAV and multi-ant colony collaborative search target method

technical field

The invention relates to the technical field of unmanned aerial vehicles (UAVs) searching for targets, in particular to a multi-UAV and multi-ant colony collaborative method for searching targets.

Background technique

In recent years, thanks to the rapid development of sensors, microprocessors, information processing and other technologies, the functions of unmanned swarm systems have increased rapidly, and their application scope has also been expanding. Due to its flexibility, scalability and strong cooperative operation ability, the theoretical and applied research of UAV swarms has attracted more and more attention from academia, industry and national defense. The multi-UAV cooperative search system can effectively improve the search efficiency, especially in the complex sea conditions such as uncertainty and strong interference in the search area. one of the important directions.

At present, the ant colony algorithm mainly solves the problem of finding a path with less threat from the starting point to the end point under the condition of the threat of a single UAV, and it is not suitable for the sea area search problem. First, a single UAV has a long search time and low search efficiency; secondly, when multiple UAVs perform search tasks, the flight safety of the UAV needs to be considered, but the current research aims to find the target with the greatest probability, and does not consider the search The navigation cost in the process, the UAV will turn frequently, and the paths between UAVs will have overlapping and overlapping problems.

SUMMARY OF THE INVENTION

According to the problems existing in the prior art, the present invention discloses a multi-UAV multi-ant colony collaborative search target method, which specifically includes the following steps:

S1: Use the grid method to divide and label the search sea area, and establish a target probability graph model;

S2: establish an objective function, and perform a weighted summation of the UAV steering cost, UAV collision threat cost, and search probability;

S3: Multi-ant colony algorithm is used to optimize the design of cooperative paths for multiple UAVs:

S31: Initialize the pheromone concentration of each ant colony according to the target probability graph model, wherein each ant colony corresponds to a UAV, and constructs a search path for the UAV;

S32: Design a state transition rule according to the path heuristic information, the pheromone concentration of this population and the pheromone concentration of other populations, in which the ants of each population select the next grid according to the state transition rule, and save the search path when the maximum step size is reached ;

S33: When the ants of various groups complete a path planning, save the search path, select the search path corresponding to the one with the largest objective function according to the objective function value, and update the pheromone concentration information according to the pheromone update rule;

S34: Set the maximum number of iterations N _max , and execute S32 and S33 until the maximum number of iterations is satisfied, then output the best search path.

Further, where the UAV steering cost is expressed as:

表示第m无人机的第n_θ次转向时的转向角度的绝对值，C_θ为系数，N_θ为总的转向次数。

Represents the absolute value of the steering angle of the mth UAV at the n θth turn, C _θ is the coefficient, and N _{θ is} the total number of turns.

Further, the UAV collision threat cost is expressed as:

lapped为无人机m,v重复搜索栅格的数目，C_c为系数；in

lapped is the number of repeated search grids for the drone m, v, and C _c is the coefficient;

The objective function is:

为无人机m的航行代价，

主要考虑无人机的转向代价和无人机之间的避碰代价，

计算如下：K is the coefficient, N is the number of search path grids, _pi is the search probability,

is the sailing cost of the UAV m,

Mainly consider the steering cost of the UAV and the collision avoidance cost between UAVs,

The calculation is as follows:

Further, in S3, the multi-ant colony algorithm is used to optimize the collaborative path design of multiple UAVs in the following ways:

Each ant selects the next grid from the starting point according to the state transition rule. The state transition rule for the lth ant to transfer from grid i to grid j at time t is designed as follows:

k₁和k₂为常数；φ_jk(t)表示其余蚂蚁子群信息素在栅格j处的值，α表示在栅格选择中信息素的重要程度，β表示启发信息在蚂蚁选路决策中的重要程度，γ表示其他种群的信息素对航路点选择的影响；where U _K represents the selected grid set, U _K =N-Tabuk, where Tabuk represents the visited grid set; η _ij (t) is the heuristic information of the path, and

k ₁ and k ₂ are constants; φ _jk (t) represents the value of the remaining ant subgroup pheromone at grid j, α represents the importance of the pheromone in grid selection, and β represents the heuristic information used in ant routing decisions The importance degree in , γ represents the influence of pheromone of other populations on waypoint selection;

In each iteration process, the pheromone is updated on the grids passed by the ants, and the pheromone at grid j is updated as follows:

τ _jk (t+1)=(1-ρ)τ _jk (t)+ρΔτ _jk (t+1)

Among them, τ _jk (t+1) and τ _jk (t) are the values of the k-th population pheromone in grid j before and after the update, respectively, ρ is the pheromone volatility coefficient, and Δτ _jk (t+1) is the pheromone To update the value, the pheromone is updated according to the following expression:

为第t次搜索后，第k个种群的第l只蚂蚁在栅格j内留下的信息素，定义为：in,

After the t-th search, the pheromone left by the l-th ant of the k-th population in grid j is defined as:

u_kl是第k个种群的蚂蚁l在第t次搜后经过网格中的第k个种群的信息素总量，

表示其他种群信息素总量；J_kl为第k个种群中的第l只蚂蚁在完成一次搜索后的搜索收益，

并对蚁群中所有蚂蚁的收益值进行排序

k₁和k₂分别为搜索收益权值系数；当

时，增强前u只蚂蚁信息素浓度；当m∈[u+1,M]，减弱m-u只蚂蚁信息素浓度；in

u _kl is the total amount of pheromone of the kth population in the kth population after the tth search by the ant l of the kth population,

represents the total amount of pheromone in other populations; J _kl is the search income of the lth ant in the kth population after completing a search,

And sort the income value of all ants in the ant colony

k ₁ and k ₂ are the search revenue weight coefficients respectively; when

When , the pheromone concentration of u ants before is enhanced; when m∈[u+1,M], the pheromone concentration of mu ants is weakened;

When the entire ant colony completes one iteration, the ants with the best solution for this iteration in each population are selected, and the pheromone is updated according to the following formula:

为迭代过程中种群k中的最优蚂蚁l_best在栅格j处产生的信息素增量，按照下式进行计算，in,

is the pheromone increment generated by the optimal ant l _best in the population k at the grid j in the iterative process, calculated according to the following formula,

Among them, k ^* is the weight value, and f(J _klbest ) is the optimal search profit function in the population k;

Constrain the pheromone concentration of each population k within the grid to [τ _min ,τ _max ],

Due to the adoption of the above technical solutions, this method makes full use of the probability map characteristics of targets in the sea area to design new ant colony pheromone (including local and global) initialization and update rules, so that the ant algorithm can quickly complete the UAV trajectory planning, The problem of repeated search is avoided, and the search efficiency is improved. By using the method disclosed in the invention, the prior information can be fully utilized, and the prior information can be effectively and quickly updated, thereby improving the efficiency of the unmanned aerial vehicle group in searching for a large number of targets in the sea area.

Description of drawings

In order to more clearly illustrate the embodiments of the present application or the technical solutions in the prior art, the following briefly introduces the accompanying drawings required for the description of the embodiments or the prior art. Obviously, the drawings in the following description are only These are some embodiments described in this application. For those of ordinary skill in the art, other drawings can also be obtained based on these drawings without any creative effort.

Fig. 1 is the flow chart of the method of the present invention;

Fig. 2 is the schematic diagram of the feasible flight direction of UAV in the present invention;

Fig. 3 is the target distribution probability diagram in the present invention;

Fig. 4 is the structure diagram of multi-ant colony cooperative search in the present invention

Detailed ways

In order to make the technical solutions and advantages of the present invention clearer, the technical solutions in the embodiments of the present invention will be described clearly and completely below with reference to the accompanying drawings in the embodiments of the present invention:

As shown in Figure 1, a multi-UAV multi-ant colony collaborative search target method includes the following steps:

S1: Model the search environment in the unknown sea area, use the grid method to search the area and number the grid, and establish the target probability map model based on the feasible flight direction of the current position of the UAV.

S2: Establish an objective function, and perform a weighted summation of the UAV steering cost, UAV collision threat cost, and search probability. In the multi-UAV cooperative target search problem, the optimized search path should be as low as possible at the minimum cost. Maximum probability of finding the target.

S3: The multi-ant colony algorithm is used to optimize the collaborative path design of multiple UAVs. Since the problem of searching targets for multiple UAVs is very similar to the foraging behavior of ant colonies, the present invention uses a multi-ant colony algorithm to optimize the design of collaborative paths for multiple UAVs.

S31: Initialize the pheromone concentration of each ant colony according to the target probability graph model, wherein each ant colony corresponds to a UAV, and constructs a search path for the UAV;

S32: Design a state transition rule according to the path heuristic information, the pheromone concentration of this population and the pheromone concentration of other populations. The ants of each population select the next grid according to the state transition rule, and save the search path when the maximum search step size is reached. ;

S33: When the ants of various groups complete a path planning, save the search path, select the search path corresponding to the one with the largest objective function according to the value of the objective function, and perform pheromone update according to the pheromone update rule;

S34: Set the maximum number of iterations N _max , and execute S32 and S33 until the maximum number of iterations is satisfied to output the optimal search path.

Further, the modeling of the unknown sea area in S1 is as follows:

As shown in Figure 2, the search sea area is divided into L _x ×L _y square grids. Label each grid as (x,y), where x∈{1,2,...,L _x }, y∈{1,2,...,L _y }, and number the grids Z∈{1,2,...,L _x ×L _y },

Z=x+(y-1)×L _x (1)

则目标m的初始位置的联合概率密度函数可表示为：Constrained by the steering angle, there are only three options for the drone to fly from the current position to the next position. Establish a normal distribution target probability graph model to describe the existence state of _NT targets, that is, the position of each target has the same probability distribution as shown in Figure 3, the initial position of target m is known according to prior information

Then the joint probability density function of the initial position of the target m can be expressed as:

Further, where the UAV steering cost is expressed as:

表示第m无人机的第n_θ次转向时的转向角度的绝对值，C_θ为系数，N_θ为总的转向次数。

Represents the absolute value of the steering angle of the mth UAV at the n θth turn, C _θ is the coefficient, and N _{θ is} the total number of turns.

Further, the UAV collision threat cost is expressed as:

lapped为无人机m,v重复搜索栅格的数目，C_c为系数。in

lapped is the number of repeated search grids for UAV m,v, and C _c is the coefficient.

The further objective function is:

为无人机m的航行代价，

主要考虑无人机的转向代价和无人机之间的避碰代价，

计算如下：K is the coefficient, N is the number of search path grids, _pi is the search probability,

is the sailing cost of UAV m,

Mainly consider the steering cost of the UAV and the collision avoidance cost between UAVs,

The calculation is as follows:

Further, FIG. 4 is a structural diagram of a multi-ant colony cooperative search. In S3, the multi-ant colony algorithm is used to optimize the collaborative path design of multiple UAVs in the following way: each ant selects the next grid from the starting point according to the state transition rule, and the lth ant transfers from grid i to the next grid at time t. The state transition rule of grid j is designed as follows:

k₁和k₂为常数；φ_jk(t)表示其余蚂蚁子群信息素在栅格j处的值，α表示在栅格选择中信息素的重要程度，β表示启发信息在蚂蚁选路决策中的重要程度，γ表示其他种群的信息素对航路点选择的影响；where U _K represents the selected grid set, U _K =N-Tabuk, where Tabuk represents the visited grid set; η _ij (t) is the heuristic information of the path, and

k ₁ and k ₂ are constants; φ _jk (t) represents the value of the remaining ant subgroup pheromone at grid j, α represents the importance of the pheromone in grid selection, and β represents the heuristic information used in ant routing decisions The importance degree in , γ represents the influence of pheromone of other populations on waypoint selection;

In each iteration process, the pheromone is updated on the grids passed by the ants, and the pheromone at grid j is updated as follows:

τ _jk (t+1)=(1-ρ)τ _jk (t)+ρΔτ _jk (t+1)

Among them, τ _jk (t+1) and τ _jk (t) are the values of the k-th population pheromone in grid j before and after the update, respectively, ρ is the pheromone volatility coefficient, and Δτ _jk (t+1) is the pheromone To update the value, the pheromone is updated according to the following expression:

为第t次搜索后，第k个种群的第l只蚂蚁在栅格j内留下的信息素，定义为：in,

After the t-th search, the pheromone left by the l-th ant of the k-th population in grid j is defined as:

u_kl是第k个种群的蚂蚁l在第t次搜后经过网格中的第k个种群的信息素总量，

表示其他种群信息素总量；J_kl为第k个种群中的第l只蚂蚁在完成一次搜索后的搜索收益，

并对蚁群中所有蚂蚁的收益值进行排序

k₁和k₂分别为搜索收益权值系数；当

时，增强前u只蚂蚁信息素浓度；当m∈[u+1,M]，减弱m-u只蚂蚁信息素浓度；in

u _kl is the total amount of pheromone of the kth population in the kth population after the tth search by the ant l of the kth population,

represents the total amount of pheromone in other populations; J _kl is the search income of the lth ant in the kth population after completing a search,

And sort the income value of all ants in the ant colony

k ₁ and k ₂ are the search revenue weight coefficients respectively; when

When , the pheromone concentration of u ants before is enhanced; when m∈[u+1,M], the pheromone concentration of mu ants is weakened;

When the entire ant colony completes one iteration, the ants with the best solution for this iteration in each population are selected, and the pheromone is updated according to the following formula:

为迭代过程中种群k中的最优蚂蚁l_best在栅格j处产生的信息素增量，按照下式进行计算，in,

is the pheromone increment generated by the optimal ant l _best in the population k at the grid j in the iterative process, calculated according to the following formula,

Among them, k ^* is the weight value, and f(J _klbest ) is the optimal search profit function in the population k;

Constrain the pheromone concentration of each population k within the grid to [τ _min ,τ _max ],

The above description is only a preferred embodiment of the present invention, but the protection scope of the present invention is not limited to this. The equivalent replacement or change of the inventive concept thereof shall be included within the protection scope of the present invention.

Claims (1)

1. A multi-unmanned aerial vehicle multi-ant colony collaborative target searching method is characterized by comprising the following steps:

s1, dividing and labeling the search sea area by adopting a grid method, and establishing a target probability graph model;

s2, establishing a target function, and carrying out weighted summation on the unmanned aerial vehicle steering cost, the unmanned aerial vehicle collision threat cost and the search probability;

s3, adopting a multi-ant colony algorithm to carry out collaborative path optimization design on the multiple unmanned aerial vehicles:

s31: initializing the pheromone concentration of each ant population according to a target probability graph model, wherein each ant population corresponds to an unmanned aerial vehicle respectively, and constructing a search path for the unmanned aerial vehicles;

s32: designing a state transition rule according to the path heuristic information, the concentration of the pheromone of the current population and the concentrations of other pheromones of the population, wherein ants of each population select the next grid according to the state transition rule, and storing a search path when the maximum step length is reached;

s33: after the ants of each population complete path planning, storing the search path, selecting the search path corresponding to the maximum objective function according to the objective function value, and updating pheromone concentration information according to the pheromone updating rule;

s34: setting a maximum number of iterations N_maxExecuting S32 and S33 until the maximum iteration number is met and outputting the optimal search path;

wherein the unmanned aerial vehicle steering cost is expressed as:

n-th of unmanned plane_θAbsolute value of steering angle in secondary steering, C_θIs a coefficient, N_θTotal number of turns;

wherein the unmanned aerial vehicle collision threat cost is expressed as:

wherein

lapped is the number of m, v repeated search grids of the unmanned plane, C_cIs a coefficient;

wherein the objective function is:

k is a coefficient, N represents the number of search path grids, p_iIn order to search for the probability,

for the navigation cost of the unmanned aerial vehicle m,

mainly considers the steering cost of the unmanned aerial vehicles and the collision prevention cost among the unmanned aerial vehicles,

the calculation is as follows:

in the S3, the following method is specifically adopted for performing collaborative path optimization design on multiple unmanned aerial vehicles by using the multiple ant colony algorithm:

each ant selects the next grid from the starting point according to the state transition rule, and the state transition rule that the ith ant transfers from the grid i to the grid j at the moment t is designed as follows:

wherein U is_KRepresenting a selected set of grids, U_KN-Tabuk, where Tabuk denotes the visited grid set; eta_ij(t) is heuristic information of the path, and

T₁and T₂Is a constant; phi is a_jk(t) represents the values of pheromones of other ant subgroups at grid j, alpha represents the importance degree of the pheromones in grid selection, beta represents the importance degree of heuristic information in ant routing decision, and gamma represents the influence of the pheromones of other groups on route point selection;

in each iteration process, pheromone is updated on the grid through which ants pass, and pheromone on the grid j is updated according to the following formula:

τ_jk(t+1)＝(1-ρ)τ_jk(t)+ρΔτ_jk(t+1)

wherein, tau_jk(t +1) and τ_jk(t) is the value of the kth population pheromone in the grid j before and after updating, respectively, rho is the pheromone volatility coefficient, and delta tau_jk(t +1) is a pheromone update value, and the pheromone is updated according to the following expression:

wherein,

the pheromone left by the i-th ant of the kth population in the grid j after the t-th search is defined as:

wherein

u_klIs the total pheromone amount of the kth population of the kth ant l after the t-th search in the grid,

representing the total amount of other population pheromones; j. the design is a square_klFor the search yield of the first ant in the kth population after completing one search,

and ranking the revenue values of all ants in the ant colony

s₁And s₂Respectively are search gain weight coefficients; when in use

When the concentration of pheromone of the first u ants is increased; when M is in the range of [ u +1, M]The pheromone concentration of m-u ants is weakened;

after the whole ant colony completes one iteration, selecting the ant with the optimal iteration solution in each colony, and updating pheromone according to the following formula:

wherein,

for the optimal ant l in the population k in the iterative process_bestThe pheromone increment generated at grid j is calculated as follows,

wherein k is^*As a weight, f (J)_klbest) Searching a revenue function for the optimal in the population k;

limiting the pheromone concentration of each population k in the grid to [ tau ]_min,τ_max]，

Images