WO2021135336A1 - Cluster job task assignment method and device for plant-protection unmanned aerial vehicles - Google Patents

Abstract

A cluster job task assignment method for plant-protection unmanned aerial vehicles, comprising: dividing an job field into N sub-fields; assigning all the sub-fields to all plant-protection unmanned aerial vehicles participating in operation according to a preset assignment principle; using a MOSFLA algorithm to find an optimal job assignment matrix; determining a job time matrix of the sub-fields according to the optimal job assignment matrix and an aircraft job time matrix to define a job sequence matrix of the sub-fields in combination with a preset assembly rule; and optimizing the job sequence matrix of the sub-fields by using a genetic algorithm. The method can integrate two constraint conditions, i.e., time and energy consumption, while ensuring full coverage of air routes, to establish a double-layer decision-making method having the shortest flight distance and optimal time allocation, thereby reducing time conflicts and improving the operation efficiency.

Description

A method and device for distributing tasks for planting and protecting unmanned aircraft cluster operation Technical field

The invention relates to the technical field of plant protection unmanned aerial vehicle cluster operation, in particular to a plant protection unmanned aerial vehicle cluster operation task allocation method and device.

Background technique

Plant protection drones are characterized by fast, high efficiency, and wide adaptability. They are flexible in operation and do not require take-off and landing tracks. They can adapt to complex terrain such as hills, mountains, slopes, and paddy fields. In recent years, they have developed rapidly in China and have accumulated annual operating area. It has exceeded 500 million mu times.

However, the plant protection drone is limited by the load of the machine (less than 20kg). The operating area of a single sortie is generally not more than 30 acres. In the actual operation process, the machine needs to waste 40% of the operating time for frequent take-off and landing, battery replacement and Add pesticides. In order to improve operational efficiency, some companies and scientific research teams have carried out research on the operation technology of one control and multiple machines. The current research work is mainly concentrated on network communication and system hardware development. The most representative one is Guangzhou Jifei Technology Co., Ltd. in 2019. The P-30XP plant protection drone was launched, and the T-20 plant protection drone launched by DJI in 2019 supports one person to control two or more machines at the same time. However, its operation path planning method is relatively simple, and the fields are simply divided according to the operating capabilities of the equipment, and each equipment uses its own independent route for sorting operations. It only considers full coverage path planning, and rarely considers coordination and cooperation between machines and tools. In actual operations, it is easy to cause take-off and landing conflicts and unreasonable task assignments.

Summary of the invention

The purpose of the present invention is to provide a method and device for planting and protecting unmanned aircraft cluster operation task allocation. On the basis of ensuring full coverage of the route, the two constraints of time and energy consumption are integrated to establish a two-layer decision of the shortest flight distance and optimal time allocation. Methods to reduce time conflicts and improve work efficiency.

In order to achieve the above-mentioned purpose, in conjunction with Fig. 1, the present invention proposes a planting protection unmanned aerial vehicle cluster task assignment method. The assignment method includes the following steps:

S1, according to the input field parameters and plant protection drone parameters, the operation field is divided into N subfields. Each subfield has the same operation requirements and corresponds to only one drone. Define the set of N subfields as H _j , j=1,2,3,...,N;

S2. All subfields are allocated to all plant protection drones participating in the operation according to a preset allocation principle. The preset allocation principle is: a single plant protection drone is allocated at least one subfield, and each subfield Can only be allocated once and all subfields are allocated;

S3, given the number of plant protection drones, the number of fields K, the number of subfields N, and the operation time matrix (T) _K×N and the distance matrix of entering/exiting the fields are (L ¹ ) _K×N , On the basis of (L ² ) _K×N , use the MOSFLA algorithm to find the optimal assignment matrix (X) _{K ×N} ;

S4, according to the optimal assignment matrix (X) _K×N and the aircraft operation time matrix (T) _K×N , determine the operation time matrix (T') _{N×1 of the} subfield; combine the preset assembly rules to define The operation sequence matrix (SE) _N×1 of the subfield block. The preset assembly rule is that after each UAV landed, assembly tasks including battery replacement and medicine box replacement are performed, but there is only one assembly task at the same time. An unmanned aircraft performs assembly tasks;

S5, using genetic algorithm to optimize the operation sequence matrix (SE) _{N×1 of the subfield block.}

As a preferred example, in step S1, the process of dividing the operation field into N subfields according to the input field parameters and plant protection drone parameters includes the following steps:

S11, put the fields required by the same operation into the same set, a total of M sets;

S12, according to the operation area of the plant protection unmanned aircraft for one take-off/landing, further field processing is performed on all the fields in the M sets, including the merging of adjacent small fields and the division of large fields;

S13, extract all subfields in the M sets, set the number of subfields as N, and define the set of N subfields as H _j , j=1, 2, 3,...,N.

As a preferred example, in step S1, in step S2, the allocation of all subfields to all plant protection drones participating in the operation according to the preset allocation principle refers to:

The assignment matrix of plant protection UAV is defined as (X) _K×N , where the assignment parameter x _{ij is} defined as:

Among them, j=1, 2, 3,...,N.

As a preferred example, in step S1, in step S3, the process of using the MOSELA algorithm to find the optimal job allocation matrix (X) _K×N includes the following steps:

S31, input the population size S, the number of subgroups s, the frog individual num of the group, the number of total group iterations D, and the number of group iterations I;

S32, initialize the total group of frogs P={X ¹ ,X ² ,...,X ^S };

S33: Calculate the fitness value and sort it in descending order for ethnic group division;

S34, evolution within the ethnic group: According to the following formula, each sub-group makes the first jump:

Among them: X ^b and X ^w are the best individual and the worst individual of the sub-group, respectively;

S35, the first ethnic group merger: sort in descending order according to fitness value, combined with the following formula, the entire ethnic group jumps for the second time:

Among them: X ^g and X ^w are the best individual and the worst individual of the entire ethnic group, respectively;

S36, the second ethnic group merger: sort in descending order according to fitness value, and combine the following formula to make the third jump for the weakest individual in the ethnic group:

(X ^w )′=rand(X),X∈Q ^M×N

Among them: rand(X) means that a decision matrix is randomly generated in the feasible solution space;

S37: Judge whether the current cycle number is less than the total group iteration number D, if it is less, go to step S33, otherwise, output the optimal individual X ¹ ;

Among them, the related parameters of population update are defined as follows:

表示X ²与X ¹间的差异矩阵，

表示矩阵间的按异位或操作符； Suppose the matrix X ¹ ∈Q ^M×N and X ² ∈Q ^M×N , where Q ^M×N is the feasible solution space, define the matrix

Represents the difference matrix between ^{X 2} and X ^1,

Represents the ectopic OR operator between matrices;

The meaning of z'=cut(z,k) is: intercept the first k columns of the one-dimensional array z and save it to the new one-dimensional array z’;

The meaning of (X ¹ )′=F(B,φ) is: update matrix X to approximate matrix B according to difference matrix B, count the element sum of each column of B, and if the element sum is greater than 0, save the column number to In the one-dimensional array z, the operator φ is defined as:

φ=～(B,X ¹ ,cut(z,ri(n)))

Among them: n is the length of the array z, ri(n) represents any integer in the interval [1,n]; "～" represents the column number ri(n) specified by z'to modify the element of ^{X 1 in the column} Keep consistent with the arrangement of B elements;

的含义为：对矩阵X ¹按照操作符

进行变异操作，操作符

的定义为：

The meaning of is: according to the operator ^{for the matrix X 1}

Perform mutation operation, operator

Is defined as:

In the formula: switch (r ₁ , r _{2 ) represents the r 1} row and r ₂ row in the switching matrix, and swicth (c ₁ , c ₂ ) represents the c ₁ column and c ₂ column in the switching matrix.

As a preferred example, in step S1, in step S33, the process of group division includes the following steps:

S331, define the fitness function FV _{1 of the} individual t as follows,

Among them, wd ₁ is the relative parameter of flying operation distance; wd ₂ is the operation time difference parameter; f ₁ , f ₂ and f ₃ represent the UAV allocation, operation distance and operation time adaptation value respectively;

In S332, the fitness value of the individual is used as a reference for the division of the ethnic group, and the individuals in _{the i-th subgroup are arranged in descending order according to the size of FV 1} ^t . The individuals in the i-th subgroup are:

{FV ₁ ^k |k∈[(i-1)×num+1,i×num]}

Among them, i=1, 2, 3,...,s.

As a preferred example, in step S1, in step S34, the process of internal evolution of the ethnic group includes the following steps:

S341: Jump to the best individual in the subgroup according to the following formula:

S342. Introduce a mutation operator for detecting whether there is a plant protection unmanned aircraft that is not allocated to the field, and use the mutation operator to perform mutation detection and processing:

(X ^w )″=F((X ^w )′,switch([r ₀ ,r _m ],c))

In the formula: r ₀ represents the row number of matrix (X ^w )′ row element sum is 0; r _m represents matrix (X ^w )′ row element sum is the largest row number; c represents _{any column of r m} whose value is 1 Number; switch([r ₀ ,r _m ],c) means that in the c-th column of the ^{matrix (X w} )′, the elements of _{r 0} and r _{m are exchanged. When the value of r 0} is not unique, the first The jump formula corresponding to the jump has been mutated many times;

S343, update the best and worst individuals;

S344: Repeat steps S341 to S343 until the number of cycles reaches 1.

As a preferred example, in step S1, in step S35, the process of the first ethnic merging includes the following steps:

S351, using the following formula to jump to the best individual in the ethnic group:

S352. Introduce a mutation operator for detecting whether there is a plant protection unmanned aircraft that is not allocated to the field, and use the mutation operator to perform mutation detection and processing:

(X ^w )″=F((X ^w )′,switch([r ₀ ,r _m ],c))

In the formula: r ₀ represents the row number of matrix (X ^w )′ row element sum is 0; r _m represents matrix (X ^w )′ row element sum is the largest row number; c represents _{any column of r m} whose value is 1 Number; switch([r ₀ ,r _m ],c) means that in the c-th column of the ^{matrix (X w} )′, the elements of _{r 0} and r _{m are exchanged. When the value of r 0} is not unique, the first The jump formula corresponding to the jump has been mutated many times;

S353: Update the best and worst individuals.

As a preferred example, in step S4, the process of defining the operation sequence matrix (SE) _N×1 of the subfield includes the following steps:

S41, according to the aircraft operation time matrix (T) _K×N , determine the field operation time matrix (T') _N×1 , and t _j'is :

Among them, j = 1, 2, 3,..., N;

S42: Define the operation sequence matrix of the field as (SE) _N×1 , and se _j is a set of non-repeated integers in the interval [1,N];

其

为： S43, according to the work order (SE) _N×1 work time, define the sorted time matrix as

its

for:

定义植保无人飞机-田块的作业时间为(TA) _K×N’，ta _ij′表示第i架飞机的第j′次作业的时间，j′＝1,2,3,…,N’，N′＝max{sum[x(i,:)]}；(TA) _K×N’每一列未赋值项用0补全； S44, based on (SE) _N×1 and

Define the operation time of the plant protection unmanned aircraft-field as (TA) _K×N' , ta _ij ′ represents the time of the j′th operation of the i-th aircraft, j′=1, 2, 3,...,N' , N'=max{sum[x(i,:)]}; (TA) _K×N' each column of unassigned items is filled with 0;

S45, without considering the overlapping time of multiple plant protection drones at the same time assembling batteries and medicine boxes, define the landing time matrix of the drone as (TL)K×N', and the takeoff time matrix as (TR) _{K ×N'} , tl _ij' and tr _ij' are respectively:

Among them, ts _ij' is the time required for the aircraft to be assembled to the next take-off after landing, here is set as a fixed length, ts _ij' = c.

As a preferred example, in step S5, the process of using genetic algorithm _{to optimize the operation sequence matrix (SE) N×1} of the subfield includes the following steps:

S51, evaluate the fitness of subfield operations:

Taking the operating sequence (SE) _N×1 as the chromosome, and in the case of determining (SE) _N×1 , determine the final landing time of different plant protection drones as tl _KN' , and define the fitness value selection function FV ₂ of the chromosome as:

Among them, g(SE ^t )=max[tl _KN′ (SE ^t ,c)]; t represents the position of the chromosome in the population; wt is the time fitness parameter, the unit is min, and the value range is [300,600];

S52, definition of genetic operator:

a. Chromosome selection operation

The roulette method is used to select the initial population. If the fitness of an individual t is f _t , the probability of the individual being selected is expressed as P _t :

Among them, N represents the size of the chromosome;

b. Chromosome crossover operation

Partial matching crossover method is adopted for crossover operation of chromosomes: two crossover points are randomly generated, and a matching segment is determined; two child individuals are generated according to the mapping relationship between the matching segment and the non-matching segment in the parent body;

c. Chromosome mutation operation

Randomly select N positions, exchange their corresponding genes, and N is greater than 1;

S53, the chromosome is updated based on the GA algorithm to obtain the optimal subfield operation sequence matrix (SE) _N×1 , including the following sub-steps:

S531, input the population size N, the maximum number of evolutionary iterations max (Gen), the crossover rate p _c , and the mutation rate p _m ;

S532, generate an initial group {SE} _P , and the total group size is P;

S533: Calculate the fitness value of individuals in the population;

S534: Judge the following conditions for stopping genetic calculation: (1) The number of iterations reaches max(Gen), (2) the fitness value requirement is met, and (3) the best chromosome is maintained for 10 consecutive generations; if any one of the conditions is met, Terminate the iterative process, and output the optimal individual {SE} _max(f) |, otherwise, go to step S535;

S535, in addition to the optimal chromosome, perform selection calculations on the remaining chromosomes;

S536, except for the optimal chromosome, perform crossover operation on other chromosomes;

S537: In addition to the optimal chromosome, perform mutation operation on other chromosomes, and return to step S533.

Based on the foregoing allocation method, the present invention also mentions a planting protection unmanned aircraft cluster task allocation device. The allocation device includes an ARM embedded system, and a GPS positioning system, a temperature and humidity sensor, and a computer connected to the ARM embedded system. Transmission module, power supply module, LCD touch screen and cache module;

The temperature and humidity sensor is used to detect the real-time temperature and real-time humidity of the work area, and feedback the detection result to the ARM embedded system;

The LCD touch screen is used to input field parameters and plant protection drone parameters to the ARM embedded system, and the field parameters include the boundary coordinates of each field;

The ARM embedded system combines the input field parameters and plant protection UAV parameters, as well as the environmental information fed back by the temperature and humidity sensor, and uses the aforementioned distribution method to jointly settle out all plant protection UAV coordinated task assignment models and corresponding The plant protection unmanned aircraft cluster operation scheduling plan, the scheduling method is sent to the flight control system of each plant protection unmanned aircraft through the data transmission module, and the input parameters and the corresponding scheduling method are stored in the buffer module;

The power supply module is used to provide the power required for normal operation of the ARM embedded system, GPS positioning system, temperature and humidity sensor, data transmission module, power supply module, LCD touch screen and cache module;

The GPS positioning system is used to obtain the position information of each plant protection unmanned aircraft, and display the obtained position information to the user through the LCD touch screen.

Compared with the prior art, the above technical solutions of the present invention have significant beneficial effects as follows:

(1) On the basis of ensuring full coverage of the route, the two constraints of time and energy consumption are integrated, and a two-layer decision-making method for the shortest flight distance and optimal time allocation is established to reduce time conflicts and improve operational efficiency.

(2) Automatically plan the entire operation process of all plant protection drones to reduce manpower loss. Only one staff member can complete the maintenance and monitoring of all drones, realizing one control for multiple drones.

It should be understood that all combinations of the aforementioned concepts and the additional concepts described in more detail below can be regarded as part of the inventive subject matter of the present disclosure as long as such concepts are not mutually contradictory. In addition, all combinations of the claimed subject matter are regarded as part of the inventive subject matter of the present disclosure.

The foregoing and other aspects, embodiments and features of the teachings of the present invention can be more fully understood from the following description with reference to the accompanying drawings. Other additional aspects of the present invention, such as the features and/or beneficial effects of the exemplary embodiments, will be apparent in the following description, or learned from the practice of the specific embodiments taught in accordance with the present invention.

Description of the drawings

The drawings are not intended to be drawn to scale. In the drawings, each identical or nearly identical component shown in each figure may be represented by the same reference numeral. For the sake of clarity, not every component is labeled in every figure. Now, embodiments of various aspects of the present invention will be described by way of examples and with reference to the accompanying drawings, in which:

Fig. 1 is a flow chart of the task allocation method for plant protection unmanned aircraft cluster operations according to the present invention.

Fig. 2 is a flow chart of the allocation method according to the first embodiment of the present invention.

Fig. 3 is a schematic diagram of the process of dividing the work field according to the present invention.

Figure 4 is a flowchart of finding the optimal job allocation matrix (X) _K×N based on MOSFLA.

Figure 5 is a schematic diagram of chromosome crossover preparation.

Figure 6 is a schematic diagram of the completion of chromosome crossover.

Figure 7 is a schematic diagram of the chromosome mutation process.

Fig. 8 is a flowchart of optimizing the operation sequence matrix (SE) _{N×1 of the subfield block using genetic algorithm.}

Figure 9 is a schematic structural diagram of a plant protection unmanned aircraft cluster operation task allocation device.

Fig. 10 is a schematic diagram of the target operation field of the plant protection unmanned aircraft in the third embodiment.

Fig. 11 is a schematic diagram of the preprocessing method of the target operation field in the third embodiment.

FIG. 12 is a schematic diagram of the comparison of the operation results of the third embodiment.

Detailed ways

In order to better understand the technical content of the present invention, specific embodiments are described in conjunction with the accompanying drawings as follows.

Specific embodiment one

With reference to Fig. 1, the present invention proposes a method for distributing tasks for planting protection unmanned aircraft cluster operations. The distributing method includes the following steps:

S1, according to the input field parameters and plant protection drone parameters, the operation field is divided into N subfields. Each subfield has the same operation requirements and corresponds to only one drone. Define the set of N subfields as H _j , j=1, 2, 3,...,N.

S2. All subfields are allocated to all plant protection drones participating in the operation according to a preset allocation principle. The preset allocation principle is: a single plant protection drone is allocated at least one subfield, and each subfield It can only be allocated once and all subfields are allocated.

S3, given the number of plant protection drones, the number of fields K, the number of subfields N, and the operation time matrix (T) _K×N and the distance matrix of entering/exiting the fields are (L ¹ ) _K×N , On the basis of (L ² ) _K×N , the MOSFLA algorithm is used to find the optimal assignment matrix (X) _K×N .

S4, according to the optimal assignment matrix (X) _K×N and the aircraft operation time matrix (T) _K×N , determine the operation time matrix (T') _{N×1 of the} subfield; combine the preset assembly rules to define The operation sequence matrix (SE) _N×1 of the subfield block. The preset assembly rule is that after each UAV landed, assembly tasks including battery replacement and medicine box replacement are performed, but there is only one assembly task at the same time. An unmanned aircraft performs assembly tasks.

S5, using genetic algorithm to optimize the operation sequence matrix (SE) _{N×1 of the subfield block.}

Please refer to Figure 1 and Figure 2, assuming that the known conditions are: ①The position of the field, the number of plant protection drones and the take-off and landing positions; ②The flight and operation performance of the aircraft, and the drone aircraft in each field are known Operational parameters; ③There is only one labor force (one control for multiple aircraft) when the unmanned aircraft is landing for the assembly of the medicine box and the battery. Under the coordination of multiple plant protection unmanned aircraft, the process of unmanned aircraft allocation and field operations sequencing of operation fields includes the following steps:

1. Re-division of operation fields

Assuming that there are a total of n blocks of target operation fields, the steps for dividing them are as follows: (1) Put fields with the same operation requirements (pesticide types and liquid concentration, aircraft operation parameters, etc.) into the same set, a total of M sets; (II) According to the operation area of one take-off/landing of the plant protection drone, further field division is performed on all fields in the M sets-adjacent small field blocks are merged, and large field blocks are divided; (III) M sets are extracted All the subfields within are counted as N, and the set of N fields is redefined as H _j , (j = 1, 2, 3,..., N). The division steps are shown in Figure 3 below.

2. Field allocation for unmanned aircraft operations based on MOSFLA

A single plant protection drone can be allocated to multiple fields (<N), but each field can only be allocated once.

The assignment matrix of plant protection UAV operation is defined as (X) _K×N , where the assignment parameter x _{ij is} defined as

Among them, j=1, 2, 3,...,N. The allocation parameters of unmanned aircraft follow the constraints: each field can only be operated once and all fields are allocated to the plant protection unmanned aircraft.

3. Job allocation optimization based on MOSFLA

Given the number of planes and fields K, N, and the operation time matrix (T) _K×N , the distance matrix for entering/exiting the field is (L ¹ ) _K×N , (L ² ) _K×N , using MOSFLA The algorithm finds the optimal assignment matrix for (X) _K×N .

Through multi-ethnic co-evolution, the hybrid leapfrog algorithm can realize the update of the population. In order to optimize the allocation parameter X in equation (1), the definition of the way of population update is as follows.

表示X ²与X ¹间的差异矩阵，

表示矩阵间的按异位或操作符。 Definition 1 Suppose matrix X ¹ ∈Q ^M×N , X ² ∈Q ^M×N , where Q ^M×N is the feasible solution space, define matrix

Represents the difference matrix between ^{X 2} and X ^1,

Represents the ectopic OR operator between matrices.

Definition 2z'=cut(z,k) is defined as: intercept the first k columns of the one-dimensional array z, and save it in the new one-dimensional array z'.

)，对矩阵X进行逼近矩阵B的更新。统计B各列的元素和，若元素和＞0则将该列号保存至一维数组z中。操作符φ的定义为： Definition 3(X ¹ )′=F(B,φ), which is based on the difference matrix B (ie

), update the matrix X to the matrix B. Count the element sum of each column of B, if the element sum>0, save the column number in the one-dimensional array z. The operator φ is defined as:

φ=～(B,X ¹ ,cut(z,ri(n))). (2)

Among them: n is the length of the array z, ri(n) represents any integer in the interval [1,n]; "～" represents: the column number ri(n) specified by z'(ie cut(z,ri(n))) ), ^{the element correction of X 1} in this column is consistent with the arrangement of B elements.

为对矩阵X ¹按照操作符

进行变异操作，操作符

的定义为： Definition 4

According to the operator for the pair matrix X ¹

Perform mutation operation, operator

Is defined as:

In the formula: switch (r ₁ , r _{2 ) represents the r 1} row and r ₂ row in the switching matrix, and swicth (c ₁ , c ₂ ) represents the c ₁ column and c ₂ column in the switching matrix.

Fourth, MOSFLA's Leapfrog Rules

The relevant leapfrog rules designed in the present invention are as follows

The first jump,

Among them: X ^b and X ^w are the best individual and the worst individual of the sub-group, respectively.

The second jump,

Among them: X ^g and X ^w are the best individual and the worst individual of the entire ethnic group, respectively.

The third jump,

(X ^w )′=rand(X),X∈Q ^M×N . (6)

Among them: rand(X) means that a decision matrix is randomly generated in the feasible solution space.

In summary, it reflects the ability of the sub-ethnic group and the worst individual in the overall ethnic group to optimize to the best individual of the ethnic group, and the overall update process of the overall ethnic group.

)。本发明引入变异算子如下，对部分解进行变异处理： The resulting new entity may have the problem of aircraft not being allocated to the field (i.e.

). The present invention introduces mutation operators as follows to perform mutation processing on partial solutions:

(X ^w )″=F((Xw)′,switch([r ₀ ,r _m ],c)). (7)

In the formula: r ₀ represents the row number of matrix (X ^w )′ row element sum is 0; r _m represents matrix (X ^w )′ row element sum is the largest row number; c represents _{any column of r m} whose value is 1 Number; switch([r ₀ ,r _m ],c) means that in the c-th column of the ^{matrix (X w} )′, the elements of _{r 0} and r _{m are exchanged. When the value of r 0} is not unique, it can be based on (4) The formula undergoes multiple mutations.

Five, the ethnic division of individuals

Suppose the total number of leapfrogging populations is S, the number of sub-populations is s, and the number of sub-populations is num (satisfying S=s×num). Based on formula (6), the fitness value function FV _{1 of} an individual t is defined as follows,

Among them, wd ₁ is the relative parameter of the flying operation distance; wd ₂ is the operation time difference parameter; f ₁ , f ₂ and f ₃ represent the UAV allocation, the operation distance and the operation time adaptation value respectively, and each is defined as follows,

Where a=round(N/K).

Where w represents the ratio of energy loss during load flight and non-load flight.

和t _ij分别是矩阵(X) _K×N、(L ¹) _K×N、(L ²) _K×N和(T) _K×N的元素。 x _ij ,

And t _ij are the elements of the matrices (X) _K×N , (L ¹ ) _K×N , (L ² ) _K×N and (T) _K×N , respectively.

The present invention uses the fitness value of an individual as a reference for the classification of ethnic groups. According to _{the size of FV 1} ^t , arrange in descending order, then the individuals in the i-th subgroup are respectively,

{FV ₁ ^k |k∈[(i-1)×num+1,i×num]}. (9)

Among them, i=1, 2, 3,...,s.

According to the above algorithm design, the specific steps of the improved MOSFLA algorithm for the multi-machine cooperative allocation problem proposed by the present invention are shown in FIG. 4.

Six, field job sequencing model based on GA

Based on the MOSFLA algorithm, we have searched for a better assignment matrix of (X) _K×N . According to the aircraft operation time matrix (T) _{K ×N} , we can determine the field operation time matrix (T') _N×1 , and its t _j'is ,

其

为， Among them, j=1, 2, 3,...,N. The work sequence matrix that defines the field is (SE) _N×1 , j=1, 2, 3,..., N, se _j is a non-repeated integer set in the interval [1,N]. According to the work sequence (SE) _N×1 work time, the time matrix after sorting is defined as

its

for,

定义植保无人飞机-田块的作业时间为(TA) _K×N’，ta _ij′表示第i架飞机的第j′次作业的时间，j′＝1,2,3,…,N’，N′＝max{sum[x(i,:)]}。(TA) _K×N’每一列未赋值项用0补全。 Based on (SE) _N×1 and

Define the operation time of the plant protection drone-field as (TA) _K×N' , ta _ij′ represents the time of the j′th operation of the i-th aircraft, j′=1,2,3,...,N' , N′=max{sum[x(i,:)]}. (TA) The unassigned items in each column of _{K×N' are filled with 0.}

After the drone has landed, the battery and medicine box need to be replaced. Regardless of the overlap time of multiple plant protection drones at the same time assembling batteries and medicine boxes, the landing time matrix of the drone is defined as (TL) _K×N' , and the take-off time matrix is (TR) _K×N' , tl _ij′ and tr _ij′ are respectively:

Among them, ts _ij' is the time required for the aircraft to assemble to the next takeoff after landing, regardless of the assembly time difference of the assemblers, here can be set to a fixed length, ts _ij' = c, simplifying the calculation complexity.

Seven, GA-based field job sorting optimization

In order to reduce the overall time of simultaneous operation of multiple UAVs, it is necessary to determine the operation sequence (SE) _{N×1 of the field} . The present invention optimizes the operation sequence through the GA algorithm.

7.1 Evaluation of fitness for field operations

The present invention takes the work sequence (SE) _N×1 as the chromosome. In the case of determining (SE) _{N×1 , the final landing time tl KN' of} different plant protection drones can be determined, and the fitness value selection function FV _{2 of the chromosome can be defined.} defined as,

Where g(SE ^t )=max[tl _KN′ (SE ^t ,c)]; t represents the position of the chromosome in the population; wt is the time fitness parameter (min), with a value range of [300,600].

7.2 Definition of genetic operators

a. Chromosome selection operation

The roulette method is used to select the initial population. If the fitness of an individual t is f _t , the probability of the individual being selected can be expressed as P _t :

Where N represents the size of the chromosome.

b. Chromosome crossover operation

Combining Figure 5 and Figure 6, the partial matching crossover method (PMX, Partially Matched Crossover) is used to perform the crossover operation of chromosomes: two crossover points are randomly generated, and a matching segment is determined; according to the mapping relationship between the matching segment and the non-matching segment in the parent body Generate two sub-individuals. For example, there are two parents as follows, assuming that the randomly generated matching segment is [4,6], and the repeated numbers are marked with *. Based on the intermediate mapping relationship, the number of the repeated part can be determined. The initial value of the first * in the font A1 is 1, the cross-occurring 1 originates from 6, and the 6 participates in the cross, its initial value is 5, and 5 no longer participates in the cross , The first * appearing in A1 can be assigned the value 5; in the same way, the second * appearing in A1 can be assigned the value 4. In the same way, complete the assignment at subbody B1*.

c. Chromosome mutation operation

Randomly select N (>1) positions and exchange their corresponding genes. For chromosome A, the selected gene positions are 3, 5, and 6, then the compiled chromosome is shown in Figure 7.

8. GA-based chromosome update process

The conditions for the chromosome to stop genetic calculation in the present invention are: ① Iterate to max(Gen) times, and the algorithm is terminated; ② Meet the fitness value requirement, and the algorithm is terminated; ③ The optimal chromosome is continuously maintained for 10 generations, and the algorithm is terminated. The GA-based chromosome update process is shown in Figure 8.

In the present invention, the population size P=20-100; the number of genetic evolution iteration max(Gen)=100-500; the crossover probability p _c =0.4-0.99; the mutation probability p _m =0.0001-0.1.

Specific embodiment two

With reference to Figure 9, based on the foregoing allocation method, the present invention also mentions a planting protection unmanned aircraft cluster task allocation device. The allocation device includes an ARM embedded system, and a GPS positioning system and a temperature control system respectively connected to the ARM embedded system. Humidity sensor, data transmission module, power supply module, LCD touch screen and cache module.

The temperature and humidity sensor is used to detect the real-time temperature and real-time humidity of the work area, and feedback the detection result to the ARM embedded system.

The LCD touch screen is used to input field parameters and plant protection drone parameters to the ARM embedded system, and the field parameters include the boundary coordinates of each field.

The ARM embedded system combines the input field parameters and plant protection UAV parameters, as well as the environmental information fed back by the temperature and humidity sensor, and uses the aforementioned distribution method to jointly settle out all plant protection UAV coordinated task assignment models and corresponding The scheduling scheme of plant protection unmanned aircraft cluster operation is sent to the flight control system of each plant protection unmanned aircraft through the data transmission module, so that the flight control system controls the equipment to perform the cluster operation according to the received instructions and input parameters And the corresponding scheduling method are stored in the cache module.

The power supply module is used to provide the power required for normal operation of the ARM embedded system, GPS positioning system, temperature and humidity sensor, data transmission module, power supply module, LCD touch screen and buffer module.

The GPS positioning system is used to obtain the position information of each plant protection unmanned aircraft, and display the obtained position information to the user through the LCD touch screen.

Specific embodiment three

In order to determine the optimal performance of the operation planning of multiple plant protection UAVs based on the MOSFLA+GA collaborative task allocation algorithm, the present invention selects the target multi-field block with a total area of 330 mu as shown in Figures 10 and 11 below.

The selected plant protection UAV has a maximum flight time of 25min and a drug load of 15L. Based on the UAV re-division of the multi-field block in Figure 10, the results of the division are shown in Figure 11. The area of the 22 subfields divided is ≤15 mu to ensure that the plant protection drones can complete the spraying operation in one sortie. The take-off/landing area of the unmanned aircraft is located near the center of the field, and this area also meets the requirements of facilitating take-off and transportation of liquid medicine batteries. When there are multiple planes landing at the same time, the maximum distance between the planes is 100m to ensure that the assembly work of the liquid medicine and battery is completed within the specified time. In the present invention, the 100m position in the center of the plot is selected as the aircraft's take-off and landing assembly point, the adjacent landing points are 25m apart, the assembly time c=6min, and the number of aircraft u=3.

In order to compare the weighted distance and total flight time of the aircraft entering/exiting the field under normal conditions, the present invention compares the following two traditional multi-aircraft operation modes:

Traditional multi-aircraft operation mode①: The aircraft cannot operate on the field, but after the aircraft completes the operation on the previous field, it will proceed to the next field.

Traditional multi-aircraft operation mode ②: Unmanned aircraft have certain operating fields, and each aircraft has a fixed operating sequence.

The implementation results of the two traditional multi-machine operation modes are as follows:

Compared with the traditional mode, the MOSFAL+GA algorithm can save up to 25 minutes. The efficiency and total time of unmanned aircraft cluster operation are shown in Figure 12.

In this disclosure, various aspects of the present invention are described with reference to the accompanying drawings, in which numerous illustrated embodiments are shown. The embodiments of the present disclosure are not necessarily defined to include all aspects of the present invention. It should be understood that the various concepts and embodiments introduced above, as well as those described in more detail below, can be implemented in any of many ways, because the concepts and embodiments disclosed in the present invention are not Limited to any implementation. In addition, some aspects disclosed in the present invention can be used alone or in any appropriate combination with other aspects disclosed in the present invention.

Although the present invention has been disclosed as above in preferred embodiments, it is not intended to limit the present invention. Those with ordinary knowledge in the technical field to which the present invention belongs can make various changes and modifications without departing from the spirit and scope of the present invention. Therefore, the protection scope of the present invention shall be subject to what is defined in the claims.

Claims (10)

A method for distributing tasks for planting protection unmanned aircraft cluster operations, characterized in that the distributing method includes the following steps: S1. According to the input field parameters and plant protection drone parameters, the operation field is divided into N subfields. Each subfield has the same operation requirements and corresponds to only one drone. Define the set of N subfields as H _j , j=1,2,3,...,N; S2. All subfields are allocated to all plant protection drones participating in the operation according to a preset allocation principle. The preset allocation principle is: a single plant protection drone is allocated at least one subfield, and each subfield Can only be allocated once and all subfields are allocated; S3, given the number of plant protection drones, the number of fields K, the number of subfields N, and the operation time matrix (T) _K×N and the distance matrix of entering/exiting the fields are (L ¹ ) _K×N , On the basis of (L ² ) _K×N , use the MOSFLA algorithm to find the optimal assignment matrix (X) _{K ×N} ; S4, according to the optimal assignment matrix (X) _K×N and the aircraft operation time matrix (T) _K×N , determine the operation time matrix (T') _{N×1 of the} subfield; combine the preset assembly rules to define The operation sequence matrix (SE) _N×1 of the subfield block. The preset assembly rule is that after each UAV landed, assembly tasks including battery replacement and medicine box replacement are performed, but there is only one assembly task at the same time. An unmanned aircraft performs assembly tasks; S5, using genetic algorithm to optimize the operation sequence matrix (SE) _{N×1 of the subfield block.} The plant protection unmanned aircraft cluster operation task allocation method according to claim 1, wherein in step S1, the operation field is divided into N subfields according to the input field parameters and plant protection unmanned aircraft parameters The process includes the following steps: S11, put the fields required by the same operation into the same set, a total of M sets; S12, according to the operation area of the plant protection unmanned aircraft for one take-off/landing, further field processing is performed on all the fields in the M sets, including the merging of adjacent small fields and the division of large fields; S13, extract all subfields in the M sets, set the number of subfields as N, and define the set of N subfields as H _j , j=1, 2, 3,...,N. The plant protection unmanned aircraft cluster operation task assignment method according to claim 1, characterized in that, in step S1, in step S2, all subfields are allocated to all plant protection plants participating in the operation according to a preset allocation principle. Human plane refers to: The assignment matrix of plant protection UAV is defined as (X) _K×N , where the assignment parameter x _{ij is} defined as:

Among them, j=1, 2, 3,...,N. The plant protection unmanned aircraft cluster task assignment method according to claim 3, wherein in step S1, in step S3, the process of using the MOSELA algorithm to find the optimal assignment matrix (X) _K×N includes The following steps: S31, input the population size S, the number of subgroups s, the frog individual num of the group, the number of total group iterations D, and the number of group iterations I; S32, initialize the total group of frogs P={X ¹ ,X ² ,...,X ^S }; S33: Calculate the fitness value and sort it in descending order for ethnic group division; S34, evolution within the ethnic group: According to the following formula, each sub-group makes the first jump:

Among them: X ^b and X ^w are the best individual and the worst individual of the sub-group, respectively; S35, the first ethnic group merger: sort in descending order according to fitness value, combined with the following formula, the entire ethnic group jumps for the second time:

Among them: X ^g and X ^w are the best individual and the worst individual of the entire ethnic group, respectively; S36, the second ethnic group merger: sort in descending order according to fitness value, and combine the following formula to make the third jump for the weakest individual in the ethnic group: (X ^w )′=rand(X),X∈Q ^M×N Among them: rand(X) means that a decision matrix is randomly generated in the feasible solution space; S37: Judge whether the current cycle number is less than the total group iteration number D, if it is less, go to step S33, otherwise, output the optimal individual X ¹ ; Among them, the related parameters of population update are defined as follows: Suppose the matrix X ¹ ∈Q ^M×N and X ² ∈Q ^M×N , where Q ^M×N is the feasible solution space, define the matrix

Represents the difference matrix between ^{X 2} and X ^1,

Represents the ectopic OR operator between matrices; The meaning of z'=cut(z,k) is: intercept the first k columns of the one-dimensional array z and save it to the new one-dimensional array z’; The meaning of (X ¹ )′=F(B,φ) is: update matrix X to approximate matrix B according to difference matrix B, count the element sum of each column of B, and if the element sum is greater than 0, save the column number to In the one-dimensional array z, the operator φ is defined as: φ=～(B,X ¹ ,cut(z,ri(n))) Among them: n is the length of the array z, ri(n) represents any integer in the interval [1,n]; "～" represents the column number ri(n) specified by z'to modify the element of ^{X 1 in the column} Keep consistent with the arrangement of B elements;

The meaning of is: according to the operator ^{for the matrix X 1}

Perform mutation operation, operator

Is defined as:

In the formula: switch (r ₁ , r _{2 ) represents the r 1} row and r ₂ row in the switching matrix, and swicth (c ₁ , c ₂ ) represents the c ₁ column and c ₂ column in the switching matrix. The method for distributing plant protection unmanned aircraft cluster operation tasks according to claim 4, wherein in step S1, in step S33, the process of group division includes the following steps: S331, define the fitness function FV _{1 of} individual t as follows

Among them, wd ₁ is the relative parameter of flying operation distance; wd ₂ is the operation time difference parameter; f ₁ , f ₂ and f ₃ represent the UAV allocation, operation distance and operation time adaptation value respectively; In S332, the fitness value of the individual is used as a reference for the division of the ethnic group, and the individuals in _{the i-th subgroup are arranged in descending order according to the size of FV 1} ^t . The individuals in the i-th subgroup are: {FV ₁ ^k |k∈[(i-1)×num+1,i×num]} Among them, i=1, 2, 3,...,s. The method for distributing plant protection unmanned aircraft cluster operation tasks according to claim 4, characterized in that, in step S1, in step S34, the process of internal evolution of the group includes the following steps: S341: Jump to the best individual in the subgroup according to the following formula:

S342. Introduce a mutation operator for detecting whether there is a plant protection unmanned aircraft that is not allocated to the field, and use the mutation operator to perform mutation detection and processing: (X ^w )″=F((X ^w )′,switch([r ₀ ,r _m ],c)) In the formula: r ₀ represents the row number of matrix (X ^w )′ row element sum is 0; r _m represents matrix (X ^w )′ row element sum is the largest row number; c represents _{any column of r m} whose value is 1 Number; switch([r ₀ ,r _m ],c) means that in the c-th column of the ^{matrix (X w} )′, the elements of _{r 0} and r _{m are exchanged. When the value of r 0} is not unique, the first The jump formula corresponding to the jump has been mutated many times; S343, update the best and worst individuals; S344: Repeat steps S341 to S343 until the number of cycles reaches 1. The method for distributing plant protection unmanned aircraft cluster operation tasks according to claim 4, wherein in step S1, in step S35, the process of the first group merger includes the following steps: S351, using the following formula to jump to the best individual in the ethnic group:

S352. Introduce a mutation operator for detecting whether there is a plant protection unmanned aircraft that is not allocated to the field, and use the mutation operator to perform mutation detection and processing: (X ^w )″=F((X ^w )′,switch([r ₀ ,r _m ],c)) In the formula: r ₀ represents the row number of matrix (X ^w )′ row element sum is 0; r _m represents matrix (X ^w )′ row element sum is the largest row number; c represents _{any column of r m} whose value is 1 Number; switch([r ₀ ,r _m ],c) means that in the c-th column of the ^{matrix (X w} )′, the elements of _{r 0} and r _{m are exchanged. When the value of r 0} is not unique, the first The jump formula corresponding to the jump has been mutated many times; S353: Update the best and worst individuals. The plant protection unmanned aircraft cluster task assignment method according to claim 4, characterized in that, in step S4, the process of defining the operation sequence matrix (SE) _N×1 of the subfield includes the following steps: S41, according to the aircraft operation time matrix (T) _K×N , determine the field operation time matrix (T') _N×1 , and t _j'is :

Among them, j = 1, 2, 3,..., N; S42: Define the operation sequence matrix of the field as (SE) _N×1 , and se _j is a set of non-repeated integers in the interval [1,N]; S43, according to the work order (SE) _N×1 work time, define the sorted time matrix as

its

for:

S44, based on (SE) _N×1 and

Define the operation time of the plant protection unmanned aircraft-field as (TA) _K×N' , ta _ij ′ represents the time of the j′th operation of the i-th aircraft, j′=1, 2, 3,...,N' , N'=max{sum[x(i,:)]}; (TA) _K×N' each column of unassigned items is filled with 0; S45, without considering the overlap time of multiple plant protection drones at the same time assembling batteries and medicine boxes, define the landing time matrix of the drone as (TL) _K×N' and the takeoff time matrix as (TR) _{K ×N'} , tl _ij' and tr _ij' are respectively:

Among them, ts _ij' is the time required for the aircraft to be assembled to the next take-off after landing, here is set as a fixed length, ts _ij' = c. The plant protection unmanned aircraft cluster task assignment method according to claim 8, characterized in that, in step S5, the process of optimizing the _{operation sequence matrix (SE) N×1 of the subfield by using the genetic algorithm includes the following} step: S51, evaluate the fitness of subfield operations: Taking the operating sequence (SE) _N×1 as the chromosome, and in the case of determining (SE) _N×1 , determine the final landing time of different plant protection drones as tl _KN' , and define the fitness value selection function FV ₂ of the chromosome as:

Among them, g(SE ^t )=max[tl _KN′ (SE ^t ,c)]; t represents the position of the chromosome in the population; wt is the time fitness parameter, the unit is min, and the value range is [300,600]; S52, definition of genetic operator: a. Chromosome selection operation The roulette method is used to select the initial population. If the fitness of an individual t is f _t , the probability of the individual being selected is expressed as P _t :

Among them, N represents the size of the chromosome; b. Chromosome crossover operation Partial matching crossover method is adopted for crossover operation of chromosomes: two crossover points are randomly generated, and a matching segment is determined; two child individuals are generated according to the mapping relationship between the matching segment and the non-matching segment in the parent body; c. Chromosome mutation operation Randomly select N positions, exchange their corresponding genes, and N is greater than 1; S53, the chromosome is updated based on the GA algorithm to obtain the optimal subfield operation sequence matrix (SE) _N×1 , including the following sub-steps: S531, input the population size N, the maximum number of evolutionary iterations max (Gen), the crossover rate p _c , and the mutation rate p _m ; S532, generate an initial group {SE} _P , and the total group size is P; S533: Calculate the fitness value of individuals in the population; S534: Judge the following conditions for stopping genetic calculation: (1) The number of iterations reaches max(Gen), (2) the fitness value requirement is met, and (3) the best chromosome is maintained for 10 consecutive generations; if any one of the conditions is met, Terminate the iterative process, and output the optimal individual {SE} _max(f) |, otherwise, go to step S535; S535, in addition to the optimal chromosome, perform selection calculations on the remaining chromosomes; S536, except for the optimal chromosome, perform crossover operation on other chromosomes; S537: In addition to the optimal chromosome, perform mutation operation on other chromosomes, and return to step S533. A planting protection unmanned aircraft cluster operation task distribution device, characterized in that the distribution device includes an ARM embedded system, and a GPS positioning system, a temperature and humidity sensor, a data transmission module, a power supply module, and a GPS positioning system respectively connected to the ARM embedded system. LCD touch screen and buffer module; The temperature and humidity sensor is used to detect the real-time temperature and real-time humidity of the work area, and feedback the detection result to the ARM embedded system; The LCD touch screen is used to input field parameters and plant protection drone parameters to the ARM embedded system, and the field parameters include the boundary coordinates of each field; The ARM embedded system combines the input field parameters and plant protection drone parameters, as well as the environmental information fed back by the temperature and humidity sensor, and uses the distribution method according to any one of claims 1-9 to jointly settle all plant protection parameters. The human-aircraft cooperative task allocation model and the corresponding plant protection unmanned aircraft cluster operation scheduling plan, the scheduling method is sent to the flight control system of each plant protection unmanned aircraft through the data transmission module, and the input parameters and the corresponding scheduling method are stored in the cache Module The power supply module is used to provide the power required for normal operation of the ARM embedded system, GPS positioning system, temperature and humidity sensor, data transmission module, power supply module, LCD touch screen and cache module; The GPS positioning system is used to obtain the position information of each plant protection unmanned aircraft, and display the obtained position information to the user through the LCD touch screen.

Images