CN107169608B - Distribution method and device for multiple unmanned aerial vehicles to execute multiple tasks - Google Patents

Abstract

The embodiment of the invention discloses a method and a device for distributing multiple tasks executed by multiple unmanned aerial vehicles. The method comprises the following steps: acquiring position information of a plurality of unmanned aerial vehicles and target points and motion parameters of the unmanned aerial vehicles and a wind field; constructing an initial population according to the position information and a preset genetic algorithm, wherein each chromosome in the initial population comprises European flight paths of the number of the unmanned aerial vehicles; determining the flight state of the unmanned aerial vehicle and the flight time for completing the European-type path flight path segment according to the initial population and the motion parameters, and acquiring the task completion time of all unmanned aerial vehicles corresponding to each chromosome according to the flight time and an MUAV-VS-EVRP model; and (3) crossing and mutating chromosomes in the population based on a genetic algorithm, and selecting the chromosome with the shortest task completion time of the unmanned aerial vehicle as a task allocation scheme of the unmanned aerial vehicle after a preset iteration number is reached. The embodiment of the invention combines the unmanned aerial vehicle flight path planning problem with the actual flight environment of the unmanned aerial vehicle, so that the optimal flight path scheme obtained by planning is superior to the scheme of constant speed of the unmanned aerial vehicle.

Description

Method and device for assigning multiple UAVs to perform multiple tasks

technical field

Embodiments of the present invention relate to the technical field of unmanned aerial vehicles, and in particular, to a method and device for assigning multiple unmanned aerial vehicles to perform multiple tasks.

Background technique

At present, UAV (Unmanned Aerial Vehicle) has a wide range of applications in the military and civilian fields, and can complete various types of tasks such as target reconnaissance, target tracking, intelligence collection, post-earthquake rescue and geological exploration. For example, when multiple UAVs cooperate to reconnaissance targets, it is necessary to allocate each UAV the target it needs to reconnaissance most reasonably, and to plan the optimal flight path for it. The problem is a joint optimization problem of task assignment and trajectory planning constrained by multiple factors, and it is also a non-deterministic problem.

With the deepening of UAV research, environmental factors have been gradually incorporated into the study of problems, especially in UAV task assignment, trajectory planning and flight control. Under the influence of environmental factors, how to reduce energy consumption and control the flight state of UAV so UAV consumes the least fuel to perform the most tasks, has better task execution status and higher safety is the main work of current UAV research. Currently, the models commonly used to solve UAV task assignment and task planning problems are: TSP model, TOP model and VRP model. Among them, the TSP model is to make the traveler pass all the given target points under the condition of only a single traveler. Therefore, the model with the smallest path cost; the TOP model is a model that makes each member visit as many target points as possible under the condition of multiple members, so that the total benefit of all members is maximized; the VRP model is a model in which the vehicle Under the condition of a fixed number, the vehicle can visit a certain number of target points, and each target point can only be visited once in the process, and finally the model with the shortest total distance or total time of UAV navigation.

In the process of implementing the embodiments of the present invention, the inventor finds that the existing technical solutions generally assume that the speed of the UAV in the model is constant in a constant time in actual operation. However, this assumption is obviously unrealistic, so that the model cannot accurately simulate the actual motion state of the UAV, and thus cannot perform optimal trajectory planning.

SUMMARY OF THE INVENTION

One purpose of the embodiments of the present invention is to solve the problem that in the prior art, since the speed of the UAV is set to be constant during the track planning, the model cannot accurately simulate the actual motion state of the UAV, and thus cannot provide the most Excellent track planning.

An embodiment of the present invention provides a method for assigning multiple UAVs to perform multiple tasks, including:

S1. Obtain position information of multiple drones and multiple target points, and motion parameters of the multiple drones and wind farms;

S2. According to the position information of the multiple drones and the multiple target points and the preset genetic algorithm, construct an initial population, and each chromosome in the initial population includes the European flight path of the number of drones and Each European flight path is completed by different drones;

S3, according to the motion parameters of the initial population, the UAV and the wind field, determine the UAV flight state and the flight time of the UAV to complete the track segment of the European flight path, according to the flight time of the track segment and the MUAV- The VS-EVRP model obtains the completion time of all UAVs corresponding to the chromosomes in the initial population;

S4. Based on the genetic algorithm, the chromosomes in the initial population are crossed and mutated, and after reaching a predetermined number of iterations, the chromosome with the shortest time to complete the task of all UAVs is selected as the optimal task allocation scheme of the UAV.

Optionally, according to the position information of the multiple unmanned aerial vehicles and the multiple target points and the preset genetic algorithm, constructing the initial population includes:

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；Perform chromosome coding according to the coding method of the preset genetic algorithm to generate an initial population of a predetermined scale; the chromosome is composed of target point information and UAV information; wherein the target point belongs to the set

T ₀ represents the starting point of UAVs, N _T represents the number of target points, and the UAV belongs to the set

N _U represents the number of drones;

The first behavior of the chromosome is a random full arrangement of the target points, and the second behavior is to randomly select the corresponding UAV for each target point according to the UAV set, and it is necessary to ensure that all UAVs in the UAV set are at least is selected once.

Optionally, determine the flight state of the drone and the flight time of the track segment in which the drone completes the European flight path according to the motion parameters of the initial population, the drone and the wind field, and determine the flight time of the track segment and The MUAV-VS-EVRP model obtains the completion time of all UAVs corresponding to the chromosomes in the initial population, including:

The Euclidean flight path corresponding to each chromosome divides the flight path into a plurality of track segments according to the order in which its target points are visited;

According to the coordinates of the starting point and the coordinates of the ending point corresponding to each track segment, combined with the wind field parameters, the UAV flight status is determined, and then the task completion time of all UAVs in the track segment is obtained. ;

According to the flight time corresponding to each track segment, the task completion time of all UAVs corresponding to the chromosome is obtained.

Optionally, according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track segment, combined with the wind field parameters to determine the flying state of the drone, and then obtaining the flight time of the drone to complete the track segment includes: :

The following formula is used to calculate and obtain the flight time of the U _i from the target point T _j to the target point T _k track segment:

Among them, U _i represents the unmanned aerial vehicle performing the above tasks, U represents the set of unmanned aerial vehicles, T _j is the starting point, _Tk is the ending point, T represents the set of target points, and V _g ⁱ is the unmanned aerial vehicle U _i in the above two ground speed between target points;

Use the following formula to calculate and obtain the ground speed of the UAV U _i :

表示风速大小，

表示风向；Among them, V _a ⁱ represents the airspeed, β _a ⁱ represents the airspeed heading angle, V _g ⁱ represents the ground speed, β _g ⁱ represents the ground speed heading angle,

represents the wind speed,

indicates wind direction;

The Euclidean distance between the two points T _j and T _k of the UAV U _i is calculated and obtained by the following formula:

Among them, X and Y represent the horizontal and vertical coordinates of the corresponding target point, respectively.

Optionally, according to the voyage time of the track segment and the MUAV-VS-EVRP model, the task completion times of all UAVs corresponding to chromosomes in the initial population are obtained, including:

Get the sailing time according to the MUAV-VS-EVRP model:

Its constraints are:

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。in.

represents the flight time of the UAV from the target point T _j to the target point T _k ,

is a binary decision variable, and

When UAVU _i flies to T _k via T _j , then

is 1, otherwise

The value of is 0, N _T represents the number of target points, and N _U represents the number of UAVs.

Optionally, based on a genetic algorithm, crossover and mutation processing is performed on the chromosomes in the initial population, and after reaching a predetermined number of iterations, the chromosome with the shortest time to complete the task of all UAVs is selected as the optimal task allocation scheme for the UAV. include:

Step 1. Use the coding method to generate an initial solution, generate an initial population of a predetermined scale, and calculate its fitness according to the completion time of all UAVs corresponding to each chromosome in the population;

Step 2. Use the roulette method to select two individuals (A, B) in the parent population for crossover. The crossover rule is to randomly select the crossover position in individual A, and then find the first row of the crossover position between individual B and individual A. For the same genes, replace the genes at the crossover positions in chromosomes A and B to obtain new chromosomes C and D, and judge whether chromosomes C and D meet the constraints of the MUAV-VS-EVRP model. If so, use chromosomes C and D to replace the population If the number of drones in chromosomes A and B does not meet the constraints, randomly select a locus and judge the chromosomes that do not meet the constraints. Whether there are two or more UAV codes on the locus, if so, put the missing UAV codes into the locus, otherwise reselect the locus to generate chromosome A in the chromosome replacement population that satisfies the constraints and B, and then iteratively update the population in step 1 to obtain a new subpopulation;

Step 3. Use the roulette method to select a chromosome in the population of step 2 to mutate, and the method of mutating the chromosome is at least one of the following mutation methods, including: performing target point mutation on the first row of the chromosome; The second line of chromosomes is subjected to drone mutation;

The steps of the entire chromosome mutation include: first, if the first row of the chromosome mutates in sequence, randomly select two loci of the current chromosome and exchange the target code of the corresponding locus; then select whether the second row is mutated and the position of the mutation, if The mutation is randomly generated to replace the original value with the value coded by the UAV at the current position, and after the mutation, it is judged whether the chromosome satisfies the constraints of the MUAV-VS-EVRP model. If it is satisfied, the chromosome in the population is replaced. The chromosomes that meet the constraints are checked for constraints, that is, when the number of drones in the chromosome does not meet the constraints, randomly select a locus for the chromosomes that do not meet the constraints, and determine whether the drone code on the locus has two If there are two or more, if it is, put the missing drone code into the locus, otherwise reselect the locus, generate chromosomes that meet the constraints to replace the chromosomes in the population, and iteratively update the population in step 2 to obtain a new subpopulation. generation population;

Step 4. Calculate the fitness of the offspring population and select the optimal solution among all solutions in this iteration;

Step 5. Determine whether the current number of iterations reaches the preset value. If it is determined to be no, then combine the child population and the parent population in step 3 according to a certain proportion to form a new parent population and return to step 2; if it is determined to be yes, Then the iteration ends, and the final optimal solution is used as the task assignment result of the UAV.

The embodiment of the present invention proposes a multi-unmanned aerial vehicle to perform multi-task distribution device, including:

an acquisition module for acquiring the position information of multiple drones and multiple target points, as well as the motion parameters of the multiple drones and the wind farm;

The first processing module is used for constructing an initial population according to the position information of the multiple drones and the multiple target points and a preset genetic algorithm, and each chromosome in the initial population includes the number of drones The European-style flight path of each European-style flight path is completed by different drones;

The second processing module is used to determine the UAV flight state and the flight time of the UAV to complete the track segment of the European flight path according to the motion parameters of the initial population, the UAV and the wind field, and according to the Navigation time and MUAV-VS-EVRP model to obtain the completion time of all UAVs corresponding to chromosomes in the initial population;

The third processing module is used to perform crossover and mutation processing on the chromosomes in the initial population based on the genetic algorithm, and after reaching a predetermined number of iterations, select the chromosome with the shortest time to complete the task of all drones as the optimal number of the drones task assignment plan.

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。Optionally, the first processing module is configured to perform chromosome encoding according to a preset genetic algorithm encoding method to generate an initial population of a predetermined scale; the chromosome is composed of target point information and UAV information; wherein the target point belong to the set

T ₀ represents the starting point of UAVs, N _T represents the number of target points, and the UAV belongs to the set

N _U represents the number of UAVs; the first line of the chromosome is a random full arrangement of the target points, and the second line is to randomly select the corresponding UAV for each target point according to the UAV set, and it is necessary to ensure that the UAV All drones in the set are selected at least once.

Optionally, the second processing module is used to divide the Euclidean flight path corresponding to each chromosome into multiple track segments according to the order in which the target points are accessed; The coordinates of the starting point and the coordinates of the ending point, combined with the wind field parameters, determine the flight state of the UAV, and then obtain the flight time of the UAV to complete the track segment; obtain the flight time corresponding to each track segment. The completion time of all drone missions corresponding to chromosomes.

Optionally, the second processing module is used to determine the flying state of the UAV according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track segment, combined with the wind field parameters, and then obtain the UAV completion. The sailing time of the track segment includes:

The following formula is used to calculate and obtain the flight time of the U _i from the target point T _j to the target point T _k track segment:

Among them, U _i represents the unmanned aerial vehicle performing the above tasks, U represents the set of unmanned aerial vehicles, T _j is the starting point, T _k is the ending point, T represents the set of target points, and V _g ⁱ is the unmanned aerial vehicle U _i in the above Ground speed between two target points;

Use the following formula to calculate and obtain the ground speed of the UAV U _i :

表示风速大小，

表示风向；Among them, V _a ⁱ represents the airspeed, β _a ⁱ represents the airspeed heading angle, V _g ⁱ represents the ground speed, β _g ⁱ represents the ground speed heading angle,

represents the wind speed,

indicates wind direction;

The Euclidean distance between the two points T _j and T _k of the UAV U _i is calculated and obtained by the following formula:

Among them, X and Y represent the horizontal and vertical coordinates of the corresponding target point, respectively.

It can be seen from the above technical solutions that the method and device for trajectory planning for multiple UAVs visiting multiple target points proposed in the embodiment of the present invention first analyze the wind field and the motion parameters of the UAVs to obtain the UAVs in the wind. The actual flight state in the field, and then the flight path planning is carried out based on the actual flight state. Compared with the solution of setting the speed of the UAV to be constant in the prior art, it can accurately calculate the speed of the UAV according to the state of the wind field in the uncertain environment. Travel time on all possible flight paths, and then select the optimal flight path.

Description of drawings

The features and advantages of the present invention will be more clearly understood by reference to the accompanying drawings, which are schematic and should not be construed as limiting the invention in any way, in which:

1 shows a schematic flowchart of a method for assigning multiple UAVs to perform multiple tasks according to an embodiment of the present invention;

FIG. 2 shows a schematic flowchart of calculating the flight time of the Dubins flight path provided by an embodiment of the present invention;

3 shows a schematic flowchart of a genetic algorithm provided by an embodiment of the present invention;

4a-4c show schematic diagrams of operators in a genetic algorithm provided by an embodiment of the present invention;

FIG. 5 shows a schematic diagram of a wind direction provided by an embodiment of the present invention;

FIG. 6 shows a schematic diagram of a velocity vector relationship provided by an embodiment of the present invention;

FIG. 7 shows a schematic diagram of the analysis provided by an embodiment of the present invention that the UAV travels from point A to point C and is affected by the wind field;

FIG. 8 shows a schematic diagram of segmenting a flight path according to an embodiment of the present invention;

FIG. 9 shows a schematic structural diagram of a distribution device for multi-UAVs to perform multi-tasking provided by an embodiment of the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present invention.

FIG. 1 shows a schematic flowchart of a trajectory planning for multiple drones accessing multiple target points according to an embodiment of the present invention. Referring to FIG. 1 , the method can be implemented by a processor, and specifically includes the following steps:

110. Acquire position information of multiple UAVs and multiple target points, and motion parameters of the multiple UAVs and wind farms;

It should be noted that before task assignment and track planning, technicians can set or measure the position information of the UAV and multiple target points according to the actual situation, and then input it into the processor.

In addition, the motion parameters of the UAV can be set by the technicians according to the actual flight needs, and the motion parameters of the wind field can be measured by the technicians or set according to the actual situation.

120. According to the position information and preset genetic algorithm of the plurality of UAVs and the plurality of target points, construct an initial population, each chromosome in the initial population includes the European flight path of the number of UAVs and Each European flight path is completed by different drones;

130. Determine the flight state of the drone and the flight time of the track segment where the drone completes the European flight path according to the initial population, the motion parameters of the drone and the wind field, and the flight time of the track segment and the MUAV- The VS-EVRP model obtains the completion time of all UAVs corresponding to the chromosomes in the initial population;

140. Based on the genetic algorithm, perform crossover and mutation processing on the chromosomes in the initial population, and after reaching a predetermined number of iterations, select the chromosome with the shortest time to complete the task of all UAVs as the optimal task allocation scheme of the UAV.

It is not difficult to understand that new individuals may appear in each iteration of crossover and mutation, and then based on the calculation of the flight time for the new chromosome in step 130, each Euclidean flight path corresponds to a flight time.

It can be seen that in this embodiment, the actual flight state of the UAV in the wind field is obtained by analyzing the motion parameters of the wind field and the UAV, and then the flight path is planned based on the actual flight state. Compared with the prior art In this embodiment, the UAV trajectory planning problem is combined with the actual flight environment of the UAV, so that the optimal flight path scheme obtained by planning is better than the scheme with a constant speed of the UAV, so as to achieve accurate calculation of the UAV's flight path. Travel time on all possible flight paths, and then select the optimal flight path.

Each step in the embodiment of the present invention is described in detail below:

First, step 120 is described in detail:

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；Perform chromosome coding according to the coding method of the preset genetic algorithm to generate an initial population of a predetermined scale; the chromosome is composed of target point information and UAV information; wherein the target point belongs to the set

T ₀ represents the starting point of UAVs, N _T represents the number of target points, and the UAV belongs to the set

N _U represents the number of drones;

The first behavior of the chromosome is a random full arrangement of the target points, and the second behavior is to randomly select the corresponding UAV for each target point according to the UAV set, and it is necessary to ensure that all UAVs in the UAV set are at least is selected once.

Then, referring to FIG. 2 , step 130 will be described in detail below:

210. The Euclidean flight path corresponding to each chromosome divides the flight path into a plurality of track segments according to the order in which its target points are accessed;

220. According to the coordinates of the starting point and the coordinates of the ending point corresponding to each track segment, combined with the wind field parameters, determine the flying state of the UAV, and then obtain the sailing time of the UAV to complete the track segment;

230. Acquire the task completion time of all UAVs corresponding to the chromosome according to the flight time corresponding to each track segment.

Wherein, step 220 includes:

The following formula is used to calculate and obtain the flight time of the U _i from the target point T _j to the target point T _k track segment:

Among them, U _i represents the unmanned aerial vehicle performing the above tasks, U represents the set of unmanned aerial vehicles, T _j is the starting point, T _k is the ending point, T represents the set of target points, and V _g ⁱ is the unmanned aerial vehicle U _i in the above Ground speed between two target points;

Use the following formula to calculate and obtain the ground speed of the UAV U _i :

表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；where V _a ⁱ represents the airspeed,

represents the airspeed heading angle, V _g ⁱ represents the size of the ground speed, β _g ⁱ represents the ground speed heading angle,

represents the wind speed,

indicates wind direction;

The Euclidean distance between the two points T _j and T _k of the UAV U _i is calculated and obtained by the following formula:

Among them, X and Y represent the horizontal and vertical coordinates of the corresponding target point, respectively.

In addition, the steps of calculating the task completion time of the drones corresponding to the chromosomes in the initial population include:

According to the MUAV-VS-EVRP model to obtain the completion time of the UAV mission:

Its constraints are:

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。in.

represents the flight time of the UAV from the target point T _j to the target point T _k ,

is a binary decision variable, and

When UAVU _i flies to T _k via T _j , then

is 1, otherwise

The value of is 0, N _T represents the number of target points, and N _U represents the number of UAVs.

Step 140 is described in detail below:

Step 1. Use the coding method to generate an initial solution, generate an initial population of a predetermined scale, and calculate its fitness according to the completion time of the drone corresponding to each chromosome in the population;

Step 2. Use the roulette method to select two individuals (A, B) in the parent population for crossover. The crossover rule is to randomly select the crossover position in individual A, and then find the first row of the crossover position between individual B and individual A. For the same genes, replace the genes at the crossover positions in chromosomes A and B to obtain new chromosomes C and D, and judge whether chromosomes C and D meet the constraints of the MUAV-VS-EVRP model. If so, use chromosomes C and D to replace the population Chromosomes A and B in the middle, otherwise, the constraint check is performed on the chromosomes that do not meet the constraints, and the chromosomes A and B in the chromosome replacement population that meet the constraints are generated, and then the population in step 1 is iteratively updated to obtain a new subpopulation;

Step 3. Use the roulette method to select a chromosome in the population of step 2 to mutate, and the method of mutating the chromosome is at least one of the following mutation methods, including: performing target point mutation on the first row of the chromosome; The second line of chromosomes is subjected to drone mutation;

The steps of the entire chromosome mutation include: first, if the first row of the chromosome mutates in sequence, randomly select two loci of the current chromosome and exchange the target code of the corresponding locus; then select whether the second row is mutated and the position of the mutation, if The mutation is randomly generated to replace the original value with the value coded by the UAV at the current position, and after the mutation, it is judged whether the chromosome satisfies the constraints of the MUAV-VS-EVRP model. If it is satisfied, the chromosome in the population is replaced. The chromosomes that meet the constraints are checked for constraints, the chromosomes in the chromosomes that meet the constraints are generated to replace the chromosomes in the population, and the population in step 2 is iteratively updated to obtain a new subpopulation;

Step 4. Calculate the fitness of the offspring population and select the optimal solution among all solutions in this iteration;

Step 5. Determine whether the current number of iterations reaches the preset value. If it is determined to be no, then combine the child population and the parent population in step 3 according to a certain proportion to form a new parent population and return to step 2; if it is determined to be yes, Then the iteration ends, and the final optimal solution is used as the task assignment result of the UAV.

Below with reference to Fig. 3, the principle of the genetic algorithm adopted in the present invention is described in detail:

1. Turn on;

2. Based on the settings of technicians, generate a population including a specified number of chromosomes, and the specified number can be specifically 100;

As shown in Figure 4a, chromosome A represents a feasible solution for two UAVs to visit three target points in a stable wind field, that is, UAV No. 1 starts from the starting point S(0,0) and visits the target points in turn 3 and target point 1 and return, UAV No. 2 starts from the starting point S(0,0), visits target point 2 and returns. The second line in the encoding represents the encoding of the UAV accessing the corresponding target point.

Among them, chromosome A includes two European-style flight paths, and each European-style flight path is completed by different UAVs No. 1 and No. 2.

3. Calculate the fitness of each chromosome;

It should be noted that the calculation method of step 140 in the corresponding embodiment of FIG. 1 is used to calculate the sailing time of the UAV to complete each European flight path, and the fitness of chromosomes is calculated based on the time when the UAV completes the task, for example: no Human-machine task completion time is inversely proportional to fitness.

It is not difficult to understand that after generating a predetermined number of populations according to the coding method in the above step 2, the fitness is calculated. The calculation of the fitness in this invention is based on the objective function, and the calculation process is as follows:

4. Select an action

According to J', the selection operation is performed by the method of roulette.

5. Cross operation

By crossing over the chromosomes of the parent, the better genes in the parent can be inherited and better offspring can be obtained. Aiming at the problem of MUAV-VS-EVRP, this paper adopts a single-point mapping method for the current coding method, that is, randomly generating the locus of the crossover of parent chromosome A, finding the locus corresponding to the same target point in the parent chromosome B, and crossing over to generate offspring Chromosomes A and B, and check the constraints of the child chromosomes A and B.

Referring to Figure 4b, there are parents Parent A and Parent B, the gene locus that is randomly generated on Parent A for crossover is 3, and the locus corresponding to the same target point on Parent B is found, and after crossover, the offspring chromosomes OffSpring A and OffSpringB are generated, Constraints verification was performed on OffSpring A and OffSpringB, and it was found that OffSpring A’s drone code represented the same drone, which did not meet the constraints. Therefore, OffSpring A’s drone code was randomly generated again to generate the locus with the third of Parent A’s drone code. The loci are mapped and crossed, and OffSpring A satisfies the constraints after crossover.

6. Mutation operation

Mutation is to prevent the genetic algorithm from falling into a local optimum. For the genetic algorithm to solve the sUav-DVS-VRP model, there are two cases of chromosome variation: target point coding variation and heading angle coding variation. Depending on the mutation probability, multiple mutations may or may not occur in a chromosome. Among them, the target point coding mutation adopts double locus mutation, that is, two mutated loci are randomly generated in the first row of the chromosome, and the values of the two loci are exchanged. This method satisfies each target in the model. The constraint that the point is visited only once ensures the feasibility of the daughter chromosome, and the heading angle encoding adopts uniform variation.

Example of mutation operation:

As shown in Figure 4c, there is a parent parent A, and the target point mutation and UAV mutation are carried out on Parent A respectively. Before the mutation is performed, it is first judged whether the two kinds of mutations have occurred. When it is judged that the target point mutation has occurred, it is randomly selected. The loci to be compiled, the loci selected in this example are 1 and 3, and then the target values on the selected loci are exchanged to obtain a new target point access order; when it is judged that the UAV mutation occurs, Randomly select the locus for mutation, in this example, the selected locus is 3, and randomly generate a UAV code different from the current UAV to replace the current value to obtain a new Parent A. Check the constraints of Parent A and find that the UAV codes of Parent A all represent the same UAV, which does not meet the constraints. Therefore, the mutation operation is performed on the UAV code of Parent A again, and the mutation locus is selected as 2. Randomly generate a UAV code different from the current UAV to replace the current value, and get OffSpring A to satisfy the constraints.

7. Update operation

8. Select the optimal allocation plan

9. Determine whether to terminate

10. Obtain the optimal allocation plan

11. End

It should be noted that the above steps correspond to some steps in the embodiment corresponding to FIG. 1 , so the similarities will not be repeated here. For details, please refer to the relevant content in the embodiment corresponding to FIG. 1 .

The design principle of the present invention is described in detail below in conjunction with the above-mentioned genetic algorithm:

Step 1, in order to avoid the problem being too complicated, the present invention adopts a regional fixed wind field for wind field modeling, that is, in a specified area, the wind speed and wind direction of the wind field are unchanged.

The state of the wind field in a known area can be expressed as:

Among them, V _w represents the wind speed in the wind field, and β _w represents the wind direction.

Wind speed V _w refers to the distance the wind moves relative to the ground in unit time, the unit is m/s; wind direction β _w refers to the direction from which the wind blows, and the measurement unit of the wind direction is generally expressed by azimuth. 36 azimuths are used to represent the sea, and angles are used to represent the high altitude, that is, the circumference is divided into 360 degrees. This article stipulates that the west wind (W) is 0 degrees (ie 360 degrees), and the south wind (S) is 90 degrees. East wind (E) is 180 degrees and north wind (N) is 270 degrees, as shown in Figure 5.

Step 2, configure UAV

use

Indicates the quadrotor mUAV, the configuration of the mUAV in the air is defined as:

q=(x, y, β _g ) (4)

in,

和

表示的是一架UAV在笛卡尔惯性参考系中的坐标；V_g表示UAV的地速β_g是指mUAV的航向角。in,

and

Represents the coordinates of a UAV in the Cartesian inertial reference system; V _g represents the ground speed of the UAV β _g refers to the heading angle of the mUAV.

In order to simplify the problem, this paper proposes the following assumptions about the motion constraints that UAVs need to meet in the process of performing tasks:

(1) mUAVs are all isomorphic multi-rotor UAVs;

(2) The collision of the mUAV is not considered, and the mUAV is considered to have an obstacle avoidance function;

(3) Consider that the mUAVs all fly at a fixed altitude;

V_{a_min}和V_{a_max}分别表示在某高度下mUAV空速的最小值和最大值；(4) According to the flight envelope of the mUAV, there are upper and lower bounds for the flight speed of the mUAV under a fixed load at a specified altitude, namely

V _{a_min} and V _{a_max} represent the minimum and maximum values of the mUAV airspeed at a certain altitude, respectively;

(5) Multiple mUAVs all start from the starting point and return to the starting point after completing the mission.

Step 3: Calculate the actual flight state of the UAV

将不考虑风影响的UAV理论速度定义为UAV的空速大小为V_a，此时UAV的航向角为β_a，UAV空速矢量

UAV空速

地速

与风场中风速

的矢量关系如图6所示。The actual speed of the UAV considering the influence of wind is defined as the ground speed of the UAV as V _g , the heading angle of the UAV at this time is β _g , and the UAV ground speed vector

The theoretical speed of the UAV without considering the influence of wind is defined as the airspeed of the UAV as V _a , the heading angle of the UAV is β _a at this time, and the UAV airspeed vector

UAV airspeed

ground speed

wind speed in wind field

The vector relationship is shown in Figure 6.

The relationship between the above speed and angle is:

即UAV空速与地速相等。When there is no wind,

That is, the UAV airspeed is equal to the ground speed.

An example is described below in conjunction with Figure 7:

The UAV flies from S(0,0) to A(50,300) with an airspeed of 8m/s. The environment where the UAV is located is a wind speed of 5m/s and a southerly wind direction (Vw=5m/s, βw=90° ), according to formula (7), the airspeed and ground speed of Uav in this process can be obtained as shown in Table 4-1.

Table 4-1 Airspeed and ground speed comparison table of quad-rotor Uav in no wind and south wind environment

airspeed ground speed south wind environment 28.80km/h, 35.5° 23.49km/h, 80.5° windless environment 28.80km/h, 80.5° 28.80km/h, 80.5°

Step 4, target point configuration

The set of N _T target points can be expressed as:

Among them, the positions and tasks of all target points in the set are known. In the present invention, there may be different types of tasks that need to be performed by the UAV on each target point, and during this process, each UAV can only perform one task on one target point, that is, each target point must be performed differently. UAV access, each UAV can only visit a certain target point once.

Step 5, Calculate the sailing time

In the problem of UAV task assignment and track planning with flight time as the goal, the UAV task assignment plan determines the sequence of UAV access to the target points, the track planning is performed according to the UAV target point access sequence, and the UAV flight is calculated based on the results of the track planning. The time in turn determines whether the current UAV task assignment and trajectory planning scheme is better than the known scheme by the UAV flight time.

Since the navigation trajectory of Uav between two points is the Euclidean distance, the navigation direction of Uav between two points is fixed, and the ground speed of Uav between two points in a fixed wind field is unchanged, but in a fixed wind field Uav is determined by The ground speed of the target point departure varies in multiple target point scenarios, and its flight time is calculated as follows:

in,

由公式(7)求得。Represents the Euclidean distance of Uav between T _j and T _k , and the ground speed of Uav between the two points

It is obtained by formula (7).

Thus, the task completion time of the mUAV can be calculated according to formula (8).

表示UAVU_i在T_j、T_k两点的航行时间；in,

represents the sailing time of UAVU _i at T _j and T _k ;

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0；

is a binary decision variable, and

When UAVU _i flies to T _k via T _j , then

is 1, otherwise

is 0;

The value of j and k in J is 0, indicating that the UAV starts from the starting point or the end of the path points to the starting point.

In the solution process, the following constraints need to be met:

The above conditions guarantee that all target points can be visited and can only be visited once.

The above conditions ensure that UAV routes with the number of UAVs start from the starting point, and UAV paths with the number of UAVs point to the same point.

The above conditions ensure that there are routes for the number of UAVs on the basis of other constraints, and the path of each UAV is a closed loop, that is, the navigation trajectory of the UAV is an orderly route and eventually returns to the starting point.

It can be seen that based on the above formula, the task completion time corresponding to each chromosome can be obtained, and then the task assignment scheme with the shortest task completion time can be selected from it.

The present invention is described in detail below with specific examples:

First of all, all simulation experiments are run on the hardware of 4G memory and 3.4GHz CPU, in the environment of MatlabR2014a. The specific instructions are as follows:

The UAV model is based on the mathematical model of the UAV. Its airspeed is 8 m/s. Both UAVs take off from the starting point S(0,0) and return to the point S(0,0) after completing the visit task; the wind field environment is fixed The wind field, that is, the wind speed and wind direction are unchanged during an experiment, and in order to ensure that the UAV can fly safely, the wind speed is 5 m/s, and the wind direction is 180° to the east. The three target points that the UAV needs to visit The coordinates are: A(100,300), B(200,150), C(350,50), D(500,150), E(650,100), F(400,200), G(50,250), H(250 , 350) and I (50, 450).

According to the model and algorithm proposed by the present invention, this paper conducts experiments under the Dongfeng wind farm environment and test scenario, and obtains the task assignment with the shortest UAV task completion time under each wind farm environment as shown in Table 3-1 (see Figure 3-1). 8).

For the method implementation, for the sake of simple description, it is expressed as a series of action combinations, but those skilled in the art should know that the implementation of the present invention is not limited by the described action sequence, because according to the implementation of the present invention , certain steps may be performed in other orders or simultaneously. Secondly, those skilled in the art should also know that the embodiments described in the specification are all preferred embodiments, and the actions involved are not necessarily necessary for the embodiments of the present invention.

FIG. 9 shows a schematic structural diagram of a trajectory planning device for a drone to access multiple target points according to an embodiment of the present invention. Referring to FIG. 9 , the device includes: an acquisition module 101 , a first processing module 102 , a second The processing module 103 and the third processing module 104, wherein:

an acquisition module 101, configured to acquire the position information of multiple unmanned aerial vehicles and multiple target points, as well as the motion parameters of the multiple unmanned aerial vehicles and the wind farm;

The first processing module 102 is configured to construct an initial population according to the position information of the multiple unmanned aerial vehicles and the multiple target points and the preset genetic algorithm, and each chromosome in the initial population includes unmanned and unmanned aerial vehicles. A number of European-style paths and each European-style flight path is completed by different drones;

The second processing module 103 is configured to determine, according to the initial population, the motion parameters of the UAV and the wind field, the flight state of the UAV and the voyage time of the UAV to complete the track segment of the European flight path, according to the track segment and the MUAV-VS-EVRP model to obtain the task completion time corresponding to the chromosomes in the initial population;

The third processing module 104 is configured to perform crossover and mutation processing on the chromosomes in the initial population based on the genetic algorithm, and after reaching a predetermined number of iterations, select the chromosome with the shortest task completion time as the optimal task allocation scheme of the UAV .

It can be seen that in this embodiment, the actual flight state of the UAV in the wind field is obtained by analyzing the motion parameters of the wind field and the UAV, and then the flight path is planned based on the actual flight state. Compared with the prior art In this embodiment, the UAV trajectory planning problem is combined with the actual flight environment of the UAV, so that the optimal flight path scheme obtained by planning is better than the scheme with a constant speed of the UAV, so as to achieve accurate calculation of the UAV's flight path. Travel time on all possible flight paths, and then select the optimal flight path.

Each functional module of the device is described in detail below:

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。The first processing module 102 is configured to perform chromosome coding according to the coding method of the preset genetic algorithm to generate an initial population of a predetermined scale; the chromosome is composed of target point information and UAV information; wherein the target point belongs to a set

T ₀ represents the starting point of UAVs, N _T represents the number of target points, and the UAV belongs to the set

N _U represents the number of UAVs; the first line of the chromosome is a random full arrangement of the target points, and the second line is to randomly select the corresponding UAV for each target point according to the UAV set, and it is necessary to ensure that the UAV All drones in the set are selected at least once.

The second processing module 103 is used to divide the Euclidean flight path corresponding to each chromosome into a plurality of track segments according to the order in which the target points are accessed; according to the coordinates of the starting point corresponding to each track segment and the termination The coordinates of the point, combined with the wind field parameters to determine the flight state of the UAV, and then obtain the flight time of the UAV to complete the track segment; obtain the task completion corresponding to the chromosome according to the flight time corresponding to each track segment time.

Further, the second processing module 103 is used to determine the flying state of the UAV according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track segment, combined with the wind field parameters, and then obtain the UAV to complete the described process. The flight time of the track segment includes:

The following formula is used to calculate and obtain the flight time of the U _i from the target point T _j to the target point T _k track segment:

Among them, U _i represents the unmanned aerial vehicle performing the above tasks, U represents the set of unmanned aerial vehicles, T _j is the starting point, T _k is the ending point, T represents the set of target points, and V _g ⁱ is the unmanned aerial vehicle U _i in the above Ground speed between two target points;

Use the following formula to calculate and obtain the ground speed of the UAV U _i :

表示风速大小，

表示风向；Among them, V _a ⁱ represents the airspeed, β _a ⁱ represents the airspeed heading angle, V _g ⁱ represents the ground speed, β _g ⁱ represents the ground speed heading angle,

represents the wind speed,

indicates wind direction;

The Euclidean distance between the two points T _j and T _k of the UAV U _i is calculated and obtained by the following formula:

Among them, X and Y represent the horizontal and vertical coordinates of the corresponding target point, respectively.

In addition, the steps of calculating the task completion time of the drones corresponding to the chromosomes in the initial population include:

According to the MUAV-VS-EVRP model to obtain the completion time of the UAV mission:

Its constraints are:

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。in.

represents the flight time of the UAV from the target point T _j to the target point T _k ,

is a binary decision variable, and

When UAVU _i flies to T _k via T _j , then

is 1, otherwise

The value of is 0, N _T represents the number of target points, and N _U represents the number of UAVs.

The third processing module 104 is configured to perform the following steps: Step 1. Use the encoding method to generate an initial solution, generate an initial population of a predetermined scale, and calculate its fitness according to the task completion time corresponding to each chromosome in the population; Step 2 . Use the roulette method to select two individuals (A, B) in the parent population for crossover. The crossover rule is to randomly select the crossover position in individual A, and then find the same crossover position in individual B as the first row of individual A. Genes, replace the genes at the crossover positions in chromosomes A and B to obtain new chromosomes C and D, and judge whether chromosomes C and D meet the constraints of the MUAV-VS-EVRP model. If so, use chromosomes C and D to replace the chromosomes in the population. A and B, otherwise, the constraint check is performed on the chromosomes that do not meet the constraints, that is, when the number of drones in chromosomes A and B does not meet the constraints, randomly select a locus for the chromosomes that do not meet the constraints and judge the gene Whether there are two or more UAV codes on the locus, if so, put the missing UAV codes into the locus, otherwise re-select the locus to generate chromosomes A and B in the chromosome replacement population that meet the constraints , and then iteratively update the population in step 1 to obtain a new subpopulation; in step 3, use the roulette method to select a chromosome in the population in step 2 to mutate, and the method of mutating the chromosome is at least one of the following mutation methods One, including: performing target point mutation on the first row of the chromosome; performing drone mutation on the second row of the chromosome; the steps of the entire chromosome mutation include: first, if the first row of the chromosome mutates in sequence, randomly select the current chromosome Two gene loci and exchange the target point code of the corresponding locus; then select the second line whether to mutate and the mutated position, if mutated, the mutated value that is different from the current position of the drone code will be randomly generated to replace the original value, and in the mutated Then judge whether the chromosomes meet the constraints of the MUAV-VS-EVRP model. If so, replace the chromosomes in the population. Otherwise, check the chromosomes that do not meet the constraints, that is, check that the number of drones in chromosomes A and B does not meet the constraints. When conditions are met, for the chromosomes that do not meet the conditions, randomly select a locus and judge whether there are two or more drone codes on the locus, if so, put the missing drone codes into the locus, Otherwise, re-select the locus, generate the chromosomes in the chromosome replacement population that meet the constraints, and iteratively update the population in step 2 to obtain a new offspring population; step 4, calculate the fitness of the offspring population and select all solutions in this iteration. Step 5, judge whether the current iteration times reach the preset value, if judged no, then combine the child population and parent population in step 3 according to a certain proportion to form a new parent population and return to step 2; If it is judged to be yes, the iteration is ended, and the final optimal solution is used as the task assignment result of the UAV.

As for the apparatus implementation, since it is basically similar to the method implementation, the description is relatively simple, and for related parts, please refer to the partial description of the method implementation.

It should be noted that, in each component of the device of the present invention, the components are logically divided according to the functions to be implemented, but the present invention is not limited to this, and each component can be re-divided as required or a combination.

Various component embodiments of the present invention may be implemented in hardware, or in software modules running on one or more processors, or in a combination thereof. In this device, the PC controls the device or device remotely through the Internet, and precisely controls each operation step of the device or device. The present invention can also be implemented as apparatus or apparatus programs (eg, computer programs and computer program products) for performing part or all of the methods described herein. The program implementing the present invention in this way can be stored on a computer readable medium, and the files or documents generated by the program can be counted, generate data reports and cpk reports, etc., and can perform batch testing and statistics on power amplifiers. It should be noted that the above-described embodiments illustrate rather than limit the invention, and that alternative embodiments may be devised by those skilled in the art without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of elements or steps not listed in a claim. The word "a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention can be implemented by means of hardware comprising several different elements and by means of a suitably programmed computer. In a unit claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The use of the words first, second, and third, etc. do not denote any order. These words can be interpreted as names.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, but not to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that it can still be The technical solutions described in the foregoing embodiments are modified, or some technical features thereof are equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (6)

1. A multi-unmanned aerial vehicle multitask execution distribution method is characterized by comprising the following steps:

s1, acquiring position information of a plurality of unmanned aerial vehicles and a plurality of target points, and motion parameters of the unmanned aerial vehicles and a wind field;

s2, constructing an initial population according to the position information of the unmanned aerial vehicles and the target points and a preset genetic algorithm, wherein each chromosome in the initial population comprises European flight paths of the number of the unmanned aerial vehicles, and each European flight path is completed by different unmanned aerial vehicles;

s3, determining the flight state of the unmanned aerial vehicle and the flight time of the unmanned aerial vehicle for completing the track section of the European flight path according to the initial population, the unmanned aerial vehicle and the motion parameters of the wind field, and acquiring the task completion time of all the unmanned aerial vehicles corresponding to the chromosomes in the initial population according to the flight time of the track section and the MUAV-VS-EVRP model;

s4, carrying out crossover and mutation processing on chromosomes in the initial population based on a genetic algorithm, and selecting the chromosome with the shortest task completion time of all unmanned aerial vehicles as the optimal task allocation scheme of the unmanned aerial vehicles after the predetermined iteration times are reached;

wherein S3 includes:

dividing the European flight path corresponding to each chromosome into a plurality of flight path segments according to the target point visited sequence of the European flight path;

determining the flight state of the unmanned aerial vehicle by combining wind field parameters according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track section, and further acquiring the flight time of the unmanned aerial vehicle for completing the track section;

determining the flight state of the unmanned aerial vehicle by combining wind field parameters according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track section, and further acquiring the flight time of the unmanned aerial vehicle for completing the track section;

according to the coordinates of the starting point and the coordinates of the ending point corresponding to each track section, determining the flight state of the unmanned aerial vehicle by combining wind field parameters, and further acquiring the flight time of the unmanned aerial vehicle for completing the track section, the method comprises the following steps:

calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iFrom target point T_jFly to target point T_kFlight time of the track segment:

wherein, U_iRepresenting the unmanned aerial vehicle performing the above tasks, U representing the set of unmanned aerial vehicles, T_jAs a starting point, T_kTo end point, T represents the set of target points, V_g ⁱFor unmanned plane U_iThe ground speed between the two target points;

calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iThe ground speed of (2):

wherein, V_a ⁱRepresenting the magnitude of space velocity, β_a ⁱRepresenting airspeed heading angle, V_g ⁱIndicating the magnitude of the ground speed, β_g ⁱWhich represents the heading angle of the ground speed,

the size of the wind speed is shown,

represents the wind direction;

calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iAt T_jAnd T_kEuclidean distance between two points:

wherein X and Y respectively represent the horizontal and vertical coordinates of the corresponding target point;

the step of obtaining task completion time of all unmanned aerial vehicles corresponding to chromosomes in the initial population according to the flight time of the flight path segment and the MUAV-VS-EVRP model comprises the following steps:

acquiring task completion time of all unmanned aerial vehicles according to the MUAV-VS-EVRP model:

the constraint conditions are as follows:

wherein T represents a set of drone target points,

T₀indicating the start of the UAVs,

representing unmanned aerial vehicle by target point T_jFly to target point T_kThe time of flight of the vehicle,

is a binary decision variable, and

when in use

Warp beam T_jFly to T_kWhen it is, then

Is 1, otherwise

Has a value of 0, N_TRepresenting the number of target points, N_URepresenting the number of drones.

2. The method of claim 1, wherein constructing the initial population according to the location information of the plurality of drones and the plurality of target points and a preset genetic algorithm comprises:

carrying out chromosome coding according to a coding mode of a preset genetic algorithm to generate an initial population with a preset scale; the chromosome is composed of target point information and unmanned aerial vehicle information; wherein the target point belongs to a set

T₀Denotes the start of UAVs, N_TRepresenting the number of target points to which the drone belongs

N_URepresenting the number of unmanned aerial vehicles;

the first behavior of the chromosome is the random full arrangement of the target points, the second behavior randomly selects the corresponding unmanned aerial vehicle for each target point according to the unmanned aerial vehicle set, and all the unmanned aerial vehicles in the unmanned aerial vehicle set are ensured to be selected at least once.

3. The method of claim 2, wherein the steps of performing crossover and mutation processing on chromosomes in the initial population based on a genetic algorithm, and selecting the chromosome with the shortest task completion time of all the unmanned aerial vehicles as the optimal task allocation scheme of the unmanned aerial vehicles after a predetermined number of iterations are achieved comprise:

step 1, generating an initial solution by using the coding mode, generating an initial population of a preset scale, and calculating the fitness of the initial population according to the task completion time of the unmanned aerial vehicle corresponding to each chromosome in the population;

step 2, selecting two individuals A and B in a parent population to intersect by using a roulette method, wherein the intersection rule is that the intersection position in the individual A is randomly selected, then the gene in the individual B, which is the same as the first line of the intersection position of the individual A, is searched, the gene at the intersection position in the chromosomes A and B is replaced to obtain new chromosomes C and D, whether the chromosomes C and D meet the constraint condition of the MUAV-VS-EVRP model is judged, if yes, the chromosomes A and B in the population are replaced by the chromosomes C and D, otherwise, the chromosomes which do not meet the constraint condition are subjected to constraint check, namely, when the number of unmanned aerial vehicles in the chromosomes A and B does not meet the constraint condition, one gene position is randomly selected, whether two or more unmanned aerial vehicle codes on the gene position exist is judged, if yes, the missing unmanned aerial vehicle codes are put into the gene position, otherwise, reselecting the gene position, generating chromosomes A and B in a chromosome replacement population meeting constraint conditions, and then continuously iteratively updating the population in the step 1 to obtain a new offspring population;

and 3, selecting one chromosome in the population in the step 2 for mutation by using a roulette method, wherein the method for mutating the chromosome is at least one of the following mutation methods, and the method comprises the following steps: performing target point variation on the first line of the chromosome; carrying out unmanned aerial vehicle variation on the second chromosome line;

the whole chromosome variation steps include: firstly, if the first line of the chromosome is mutated, randomly selecting two gene positions of the current chromosome and exchanging target point codes of the corresponding gene positions; selecting whether a second row is mutated or not and a mutation position, if so, randomly generating a value of the unmanned aerial vehicle code which is mutated and is different from the current position to replace an original value, judging whether the chromosome meets the constraint condition of the MUAV-VS-EVRP model or not, if so, replacing the chromosome in the population, otherwise, carrying out constraint check on the chromosome which does not meet the constraint condition, namely, randomly selecting a gene position and judging whether two or more unmanned aerial vehicle codes on the gene position exist or not aiming at the chromosome which does not meet the constraint condition when the number of the unmanned aerial vehicles in the chromosome is not met with the constraint condition, if so, putting the missing unmanned aerial vehicle code into the gene position, otherwise, reselecting the gene position, generating the chromosome which meets the constraint condition to replace the chromosome in the population, and continuously iterating and updating the population in the step 2 to obtain a new offspring population;

step 4, calculating the population fitness of the offspring and selecting the optimal solution of all solutions in the iteration;

step 5, judging whether the current iteration times reach a preset value or not, if not, combining the child population and the parent population in the step 3 according to a certain proportion to form a new parent population, and returning to the step 2; if so, ending the iteration, and taking the finally obtained optimal solution as a task allocation result of the unmanned aerial vehicle.

4. A multi-unmanned aerial vehicle carries out multitask distribution device which is characterized by comprising:

the acquisition module is used for acquiring the position information of a plurality of unmanned aerial vehicles and a plurality of target points, and the motion parameters of the unmanned aerial vehicles and the wind field;

the first processing module is used for constructing an initial population according to the position information of the unmanned aerial vehicles and the target points and a preset genetic algorithm, wherein each chromosome in the initial population comprises European flight paths of the number of the unmanned aerial vehicles, and each European flight path is completed by different unmanned aerial vehicles;

the second processing module is used for determining the flight state of the unmanned aerial vehicle and the flight time of a track section of a European flight path of the unmanned aerial vehicle according to the initial population, the unmanned aerial vehicle and the motion parameters of a wind field, acquiring the task completion time of all the unmanned aerial vehicles corresponding to chromosomes in the initial population according to the flight time of the track section and an MUAV-VS-EVRP model, and dividing the flight path into a plurality of track sections according to the target point visited sequence of the European flight path corresponding to each chromosome; performing the first step and the second step;

the first step comprises: calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iFrom target point T_jFly to target point T_kFlight time of the track segment:

wherein, U_iRepresenting the unmanned aerial vehicle performing the above tasks, U representing the set of unmanned aerial vehicles, T_jAs a starting point, T_kTo end point, T represents the set of target points, V_g ⁱFor unmanned aerial vehiclesU_iThe ground speed between the two target points;

calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iThe ground speed of (2):

wherein, V_a ⁱRepresenting the magnitude of space velocity, β_a ⁱRepresenting airspeed heading angle, V_g ⁱIndicating the magnitude of the ground speed, β_g ⁱWhich represents the heading angle of the ground speed,

the size of the wind speed is shown,

represents the wind direction;

calculating and acquiring unmanned aerial vehicle U by adopting the following formula_iAt T_jAnd T_kEuclidean distance between two points:

wherein X and Y respectively represent the horizontal and vertical coordinates of the corresponding target point;

the second step includes:

acquiring task completion time of all unmanned aerial vehicles according to the MUAV-VS-EVRP model:

the constraint conditions are as follows:

wherein T represents a set of drone target points,

T₀indicating the start of the UAVs,

representing unmanned aerial vehicle by target point T_jFly to target point T_kThe time of flight of the vehicle,

is a binary decision variable, and

when in use

Warp beam T_jFly to T_kWhen it is, then

Is 1, otherwise

Has a value of 0, N_TRepresenting the number of target points, N_URepresenting the number of drones; and the third processing module is used for carrying out crossing and mutation processing on chromosomes in the initial population based on a genetic algorithm, and selecting the chromosome with the shortest task completion time of all the unmanned aerial vehicles as the optimal task allocation method of the unmanned aerial vehicles after the preset iteration times are reached.

5. The apparatus according to claim 4, characterized in that said first processing module is adapted to perform a predetermined genetic algorithmCarrying out chromosome coding in a coding mode to generate an initial population with a preset scale; the chromosome is composed of target point information and unmanned aerial vehicle information; wherein the target point belongs to a set

T₀Denotes the start of UAVs, N_TRepresenting the number of target points to which the drone belongs

N_URepresenting the number of unmanned aerial vehicles; the first behavior of the chromosome is the random full arrangement of the target points, the second behavior randomly selects the corresponding unmanned aerial vehicle for each target point according to the unmanned aerial vehicle set, and all the unmanned aerial vehicles in the unmanned aerial vehicle set are ensured to be selected at least once.

6. The apparatus of claim 5, wherein the third processing module is configured to perform the following steps:

step 1, generating an initial solution by using the coding mode, generating an initial population of a preset scale, and calculating the fitness of the initial population according to the task completion time of the unmanned aerial vehicle corresponding to each chromosome in the population;

step 2, selecting two individuals A and B in a parent population to intersect by using a roulette method, wherein the intersection rule is that the intersection position in the individual A is randomly selected, then the gene in the individual B, which is the same as the first line of the intersection position of the individual A, is searched, the gene at the intersection position in the chromosomes A and B is replaced to obtain new chromosomes C and D, whether the chromosomes C and D meet the constraint condition of the MUAV-VS-EVRP model is judged, if yes, the chromosomes A and B in the population are replaced by the chromosomes C and D, otherwise, the chromosomes which do not meet the constraint condition are subjected to constraint check, namely, when the number of unmanned aerial vehicles in the chromosomes A and B does not meet the constraint condition, one gene position is randomly selected, whether two or more unmanned aerial vehicle codes on the gene position exist is judged, if yes, the missing unmanned aerial vehicle codes are put into the gene position, otherwise, reselecting the gene position, generating chromosomes A and B in a chromosome replacement population meeting constraint conditions, and then continuously iteratively updating the population in the step 1 to obtain a new offspring population;

and 3, selecting one chromosome in the population in the step 2 for mutation by using a roulette method, wherein the method for mutating the chromosome is at least one of the following mutation methods, and the method comprises the following steps: performing target point variation on the first line of the chromosome; carrying out unmanned aerial vehicle variation on the second chromosome line;

the whole chromosome variation steps include: firstly, if the first line of the chromosome is mutated, randomly selecting two gene positions of the current chromosome and exchanging target point codes of the corresponding gene positions; selecting whether a second row is mutated or not and a mutation position, if so, randomly generating a value of the unmanned aerial vehicle code which is mutated and is different from the current position to replace an original value, judging whether the chromosome meets the constraint condition of the MUAV-VS-EVRP model or not, if so, replacing the chromosome in the population, otherwise, carrying out constraint check on the chromosome which does not meet the constraint condition, namely, randomly selecting a gene position and judging whether two or more unmanned aerial vehicle codes on the gene position exist or not aiming at the chromosome which does not meet the constraint condition when the number of the unmanned aerial vehicles in the chromosome is not met with the constraint condition, if so, putting the missing unmanned aerial vehicle code into the gene position, otherwise, reselecting the gene position, generating the chromosome which meets the constraint condition to replace the chromosome in the population, and continuously iterating and updating the population in the step 2 to obtain a new offspring population;

step 4, calculating the population fitness of the offspring and selecting the optimal solution of all solutions in the iteration;

step 5, judging whether the current iteration times reach a preset value or not, if not, combining the child population and the parent population in the step 3 according to a certain proportion to form a new parent population, and returning to the step 2; if so, ending the iteration, and taking the finally obtained optimal solution as a task allocation result of the unmanned aerial vehicle.

Images