CN112016812A  Multiunmanned aerial vehicle task scheduling method, system and storage medium  Google Patents
Multiunmanned aerial vehicle task scheduling method, system and storage medium Download PDFInfo
 Publication number
 CN112016812A CN112016812A CN202010782126.4A CN202010782126A CN112016812A CN 112016812 A CN112016812 A CN 112016812A CN 202010782126 A CN202010782126 A CN 202010782126A CN 112016812 A CN112016812 A CN 112016812A
 Authority
 CN
 China
 Prior art keywords
 task
 scheduling
 unmanned aerial
 aerial vehicle
 tasks
 Prior art date
 Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
 Pending
Links
 238000000034 methods Methods 0.000 claims description 17
 238000003780 insertion Methods 0.000 claims description 10
 230000000875 corresponding Effects 0.000 claims description 5
 230000001965 increased Effects 0.000 claims description 4
 238000009499 grossing Methods 0.000 claims description 3
 241001481659 Syrphidae Species 0.000 claims description 2
 230000037010 Beta Effects 0.000 claims 1
 241000212893 Chelon labrosus Species 0.000 claims 1
 238000005457 optimization Methods 0.000 abstract description 18
 238000004088 simulation Methods 0.000 abstract description 14
 108010074506 Transfer Factor Proteins 0.000 abstract description 9
 238000002922 simulated annealing Methods 0.000 abstract description 7
 238000002474 experimental method Methods 0.000 abstract description 6
 238000010845 search algorithm Methods 0.000 description 5
 238000010586 diagram Methods 0.000 description 4
 238000004458 analytical method Methods 0.000 description 3
 230000000694 effects Effects 0.000 description 3
 230000002028 premature Effects 0.000 description 3
 230000005540 biological transmission Effects 0.000 description 2
 230000000052 comparative effect Effects 0.000 description 2
 238000000354 decomposition reaction Methods 0.000 description 2
 238000011156 evaluation Methods 0.000 description 2
 239000002245 particle Substances 0.000 description 2
 241000282941 Rangifer tarandus Species 0.000 description 1
 230000032683 aging Effects 0.000 description 1
 238000000137 annealing Methods 0.000 description 1
 230000015556 catabolic process Effects 0.000 description 1
 238000006243 chemical reaction Methods 0.000 description 1
 238000004891 communication Methods 0.000 description 1
 230000004059 degradation Effects 0.000 description 1
 238000006731 degradation reaction Methods 0.000 description 1
 238000005516 engineering process Methods 0.000 description 1
 230000002708 enhancing Effects 0.000 description 1
 238000004880 explosion Methods 0.000 description 1
 230000002068 genetic Effects 0.000 description 1
 230000001537 neural Effects 0.000 description 1
 238000005192 partition Methods 0.000 description 1
 238000007639 printing Methods 0.000 description 1
 230000004044 response Effects 0.000 description 1
 239000004576 sand Substances 0.000 description 1
Classifications

 G—PHYSICS
 G06—COMPUTING; CALCULATING; COUNTING
 G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
 G06Q10/00—Administration; Management
 G06Q10/06—Resources, workflows, human or project management, e.g. organising, planning, scheduling or allocating time, human or machine resources; Enterprise planning; Organisational models
 G06Q10/063—Operations research or analysis
 G06Q10/0631—Resource planning, allocation or scheduling for a business operation

 G—PHYSICS
 G06—COMPUTING; CALCULATING; COUNTING
 G06K—RECOGNITION OF DATA; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
 G06K9/00—Methods or arrangements for reading or recognising printed or written characters or for recognising patterns, e.g. fingerprints
 G06K9/62—Methods or arrangements for recognition using electronic means
 G06K9/6217—Design or setup of recognition systems and techniques; Extraction of features in feature space; Clustering techniques; Blind source separation
 G06K9/6218—Clustering techniques
 G06K9/622—Nonhierarchical partitioning techniques
 G06K9/6221—Nonhierarchical partitioning techniques based on statistics
 G06K9/6223—Nonhierarchical partitioning techniques based on statistics with a fixed number of clusters, e.g. Kmeans clustering
Abstract
The invention discloses a multiunmanned aerial vehicle task scheduling method, a multiunmanned aerial vehicle task scheduling system and a storage medium, wherein the first stage is a multiunmanned aerial vehicle task allocation stage, the multiunmanned aerial vehicle task scheduling problem is divided into a plurality of single unmanned aerial vehicle scheduling subproblems, and a simulated annealing algorithm embedded with a tabu table is provided for realizing multiunmanned aerial vehicle task allocation; and the second stage is a single unmanned aerial vehicle task scheduling stage, and according to the task allocation scheme of the first stage, a variable neighborhood search descent algorithm is designed by considering the observation capability of the unmanned aerial vehicle platform and the requirements of tasks, so that an effective and feasible task scheduling scheme is provided. And in the first stage, according to the feedback result of the second stage, combining the tabu factor, the transfer factor and the exchange factor, and iteratively adjusting and updating the task allocation scheme until the stopping criterion is met. In conclusion, a twostage iterative optimization method is provided for the problem of multiunmanned aerial vehicle cooperative task scheduling. Simulation experiments prove the superiority and efficiency of the invention.
Description
Technical Field
The invention relates to an unmanned aerial vehicle task scheduling technology, in particular to a multiunmanned aerial vehicle task scheduling method, a multiunmanned aerial vehicle task scheduling system and a storage medium.
Background
In recent years, Unmanned Aerial Vehicles (UAVs) have become more popular and widely usedApplications in several fields, e.g. traffic patrol^{[1,2]}Earthquakeresistant and disasterrelief device^{[3]}Logistics distribution^{[4,5]}Object reconnaissance^{[6]}And the like. Wherein, unmanned aerial vehicle traffic data gathers^{[7]}Is an emerging application and is the focus of the research of the invention. The traffic data acquisition refers to acquiring traffic flow data of each road in cities in different time periods. Traditional manual data collection undoubtedly consumes a lot of manpower and vehicle resources. Worse still, during peak hours, traffic congestion can cause significant bias in the collected data. In contrast, unmanned aerial vehicles have greater flexibility and mobility, can reach the destination fast. The intersections that need data acquisition at present distribute in the region of difference, and the task has the ageing, and many unmanned aerial vehicle executive capability is strong, work efficiency is high, therefore many unmanned aerial vehicle traffic data acquisition becomes a potential data acquisition mode.
The core of multiunmanned aerial vehicle traffic data acquisition lies in multiunmanned aerial vehicle cooperative task scheduling, namely how to plan an effective multiunmanned aerial vehicle cooperative task scheduling scheme in reasonable time under the constraint conditions of observation capability, task demand and the like of an unmanned aerial vehicle platform. The multiunmanned aerial vehicle cooperative task scheduling is essentially an NPdifficult combination optimization problem^{[8]}. The precise algorithm is difficult to solve the largescale problem of the multiple unmanned aerial vehicles in a reasonable time, so that an effective and feasible heuristic algorithm is designed for the largescale task scheduling problem of the multiple unmanned aerial vehicles, and the problem to be solved urgently is solved.
The current research on the task scheduling of multiple unmanned aerial vehicles mainly adopts an intelligent optimization algorithm. For improving the quality of the protocol, Jia^{[9]}Et al and Bai^{[10]}Et al embed tabu search mechanisms or improve crossmutation factors in Genetic Algorithms (GA). ZHen^{[11]}The inventor provides an improved distributed ant colony search Algorithm (ACO), realizes task scheduling of a scouting and printing integrated cluster unmanned aerial vehicle, and verifies the robustness of the algorithm through a large number of simulation experiments. Zhu (Zhu)^{[12]}The task scheduling problem of the unmanned aerial vehicles is regarded as a deformation of the problem of team directional movement by the people, and an efficient simulated annealing algorithm is providedA mixed Particle Swarm Optimization (PSO) (HPSOSA) of (multiplexed analysis, SA) solves this problem. Chen^{[13]}The patent refers to the field of 'transmission of digital information'. Wang (Wang)^{[14]}And (3) designing a multiobjective reduction neighborhood search algorithm for improving a task scheduling scheme. In multiUAV task scheduling, selforganizing maps (SOM) based Artificial Neural Network (ANN)^{[15]}Also becomes an effective solution. In addition, with good flexibility, strong fault tolerance capability and quick response capability, the market mechanismbased distributed algorithm is also applied to dynamic task scheduling of multiple unmanned aerial vehicles, such as an auction algorithm^{[16,17]}Contract net^{[18]}。
According to the current research situation, it can be found that most of researches solve the multiunmanned aerial vehicle task scheduling problem as a whole, so that the solving efficiency is low, and especially when the largescale task scheduling problem is solved, a feasible scheme is probably not obtained. Currently, some scholars strive to innovate in the solution framework in solving the largescale task scheduling problem. Deng^{[19]}The patent refers to the field of 'transmission of digital information'. Ren^{[20]}The people establish a layered framework consisting of a single robot at the bottom layer and a planning center at the high layer, and verify the effectiveness of the layered framework through comparison experiments. Similarly, a small number of scholars^{[21][22]}The layering thought is applied to multiunmanned aerial vehicle task scheduling, and experimental results show that the layering thought can effectively balance timeliness and optimality. However, the current multiunmanned aerial vehicle task scheduling framework based on the layering idea mainly emphasizes the idea of dividing and treating, the connection between each layer is not strong, and the ideas of layerbylayer feedback and iterative optimization are lacked, so that the solving speed is greatly reduced and the solving quality is greatly reduced when a largescale task scheduling problem is faced.
Disclosure of Invention
The invention aims to solve the technical problem that aiming at the defects of the prior art, the invention provides a multiunmanned aerial vehicle task scheduling method, a multiunmanned aerial vehicle task scheduling system and a storage medium, so that the complexity of the multiunmanned aerial vehicle largescale task scheduling problem is effectively reduced, and the quality of a scheduling scheme is ensured.
In order to solve the technical problems, the technical scheme adopted by the invention is as follows: a multiunmanned aerial vehicle task scheduling method comprises the following steps:
s1, initializing a task allocation plan a of multiple drones, a ═ a_{1},…,a_{k},…,a_{m}}；a_{1},…,a_{k},…,a_{m}The task allocation schemes respectively correspond to the 1 st to the mth unmanned aerial vehicles; k is an element of [1, m ]]；
S2, according to the task allocation scheme a of the kth unmanned aerial vehicle_{k}Generating a scheduling scheme s of the kth unmanned aerial vehicle_{k}；
S3, merging scheduling schemes S of 1 st to mth unmanned aerial vehicles_{1},s_{2},…,s_{m}Obtaining a complete scheduling scheme S, and calculating the total benefit value of the scheduling scheme S;
s4, according to the scheduling scheme S, the task which can not be scheduled is redistributed to generate a new task allocation scheme A ', A ═ a'_{1},…,a′_{k},…,a′_{m}}；
S5, New task Allocation scheme a 'according to kth unmanned aerial vehicle'_{k}Generating a new scheduling scheme s'_{k}；
S6, combining the new scheduling schemes of the 1 st to the mth unmanned aerial vehicles to obtain a new scheduling scheme S ', and calculating the total benefit value of the new scheduling scheme S';
s7, judging whether the total benefit value of the new scheduling scheme S 'is greater than that of the scheduling scheme S, and if so, replacing the scheduling scheme S with the new scheduling scheme S';
and S8, returning to the step S4 until the set stop condition is reached, and outputting the final scheduling scheme.
The invention divides the task scheduling problem of the multiunmanned aerial vehicle into a plurality of subtask scheduling problems of the single unmanned aerial vehicle, including a task allocation stage of the multiunmanned aerial vehicle and a task scheduling stage of the single unmanned aerial vehicle, and the twostage iterative optimization method (namely, the iterative optimization is carried out on the task allocation scheme and the task scheduling scheme) can realize the maximization of the overall profit, and solves the problems of low solving speed and low solving quality when the largescale task scheduling problem of the prior art is solved.
The specific implementation process of step S1 includes:
1) random initialized membership degree beta_{k,j}J belongs to T, and T is a task set; t ═ 1,2,. and n, where n is the number of tasks;
2) calculating the clustering center mu of the kth unmanned plane by using the following formula_{k}And using said cluster center mu_{k}Evaluating the quality E of each clustering, and updating the membership: wherein b is a smoothing factor; x is the number of_{j}Is the coordinate of task j; mu.s_{s}Is the center coordinate of cluster s, i.e. the cluster center of cluster s; cluster s is the sth unmanned aerial vehicle;
3) judging whether the clustering quality E meets the precision error requirement, and if so, entering the step 4); otherwise, returning to the step 2);
4) initializing k to 1, and scheduling the task of the kth unmanned aerial vehicle according to the scheme a_{k}Setting the task number gamma as a null set, setting the selected task number gamma as a minimum integer greater than or equal to  T /m, and initializing the set AT to T;
5) arranging the tasks of the set AT in a descending order according to the membership degree of the tasks and the kth unmanned aerial vehicle;
6) adding the first gamma tasks after descending sorting to a_{k}And deleting the first gamma tasks from the AT; let γ be min { ceil ( T /m),  AT  }, the value of k plus 1; wherein ceil () represents the smallest integer greater than or equal to the specified expression that is returned; the  T  and the  AT  respectively refer to the number of elements in the set T, AT;
7) judging whether the set AT is an empty set, if so, executing a step 8); otherwise, returning to the step 5);
8) merging a_{1},…,a_{k},…,a_{m}And obtaining a task allocation scheme A.
The method can quickly generate an initial multiunmanned aerial vehicle task allocation scheme, and realize that the difference of the number of tasks among the unmanned aerial vehicles is as small as possible, thereby effectively reducing the time consumed by later iterative optimization.
The specific implementation process of step S2 includes:
I) initializing a set of scheduled tasks z_{k}And a set of unscheduled tasks u_{k}Is an empty set;
II) the following indices for each task: evaluating the distance from the task to the base, the duration of a time window, the urgency of the task, the geographic position of the task and the profit value by adopting a formulaObtaining the score of each task and obtaining the score conditions r of all tasks; alpha is alpha_{q}Is thatThe weight of (a) is determined, indicating the distance of task i from the base,indicating the duration of the time window for task i,indicating the degree of urgency of the task i,indicating the geographical position advantage of task i,evaluating the profit value of the task i; g_{i}A score representing task i;
III) selecting the task c with the highest score from the r; judging whether the highest task c meets the constraint conditions of the unmanned aerial vehicle task scheduling model; if yes, adding the task c into a scheduling task set z_{k}Performing the following steps; otherwise, add task c to unscheduled task set u_{k}；
IV) removing task c from r;
v) returning to the step III) until r is an empty set, and obtaining an updated scheduling task set and an unscheduled task set;
VI) merging the updated scheduling task set and the unscheduled task set to obtain the scheduling scheme s of the kth unmanned aerial vehicle_{k}。
Through the process, an initial feasible single unmanned aerial vehicle scheduling scheme can be quickly obtained, and an initial feasible solution is provided for later single unmanned aerial vehicle scheduling scheme optimization.
After step S2, and before step S3, scheduling plan S for the kth drone_{k}Optimizing, wherein the specific optimizing steps comprise:
A) scheduling scheme s for kth unmanned aerial vehicle_{k}Using interpolation operatorsOptimizing if finding a specific scheduling scheme s_{k}The more optimal solution is to update the task solution s_{k}Go to step C); otherwise, go to step
B) (ii) a Wherein the insertion operatorThe method comprises the following steps: selecting an unscheduled task with the highest profit value, judging whether a task with the earliest starting time later than the earliest starting time of the selected unscheduled task exists in a task scheduling scheme, if so, screening out the task with the earliest starting time later than the earliest starting time of the selected unscheduled task, and putting the task into an insertion position candidate set; randomly selecting insertion positions from the insertion position candidate set, judging whether a scheduling scheme after the selected tasks are inserted meets constraint conditions of an unmanned aerial vehicle task scheduling model or not, and if so, considering that the selected tasks are inserted and screenedThe scheduling scheme after the coming task is better than the task scheduling scheme;
B) for scheduling scheme s_{k}Using commutative operatorsOptimizing if finding a specific scheduling scheme s_{k}The more optimal scheme is to update the scheduling scheme s_{k}Go to step C); otherwise, directly turning to the step C); wherein the operators are exchangedThe method comprises the following steps: selecting an unscheduled task with the highest profit value, determining a scheduling task with the profit value lower than the profit value of the selected task, considering the maximization of the constraint condition and the total scheduling profit value, and selecting the scheduling task meeting the constraint condition of the unmanned aerial vehicle task scheduling model as an updated scheduling scheme;
C) returning to the step A), and obtaining the optimized unmanned aerial vehicle scheduling task scheme s until the set maximum iteration times are met_{k}。
Based on the single unmanned aerial vehicle task scheduling scheme of the step S2, the variable neighborhood search descent algorithm is adopted for optimization, and the benefit value maximization of the single unmanned aerial vehicle for executing the tasks can be realized.
The specific implementation process of step S4 includes:
i) set the maximum temperature T_{f}Maximum number of iterations l_{max}Initializing a tabu table as an empty set, and initializing iteration times q and temperature T of an optimal solution which are continuously kept unchanged_{l}；
ii) determination of T_{l}＞T_{f}And q < l_{max}If yes, executing step iii); otherwise, ending;
and iii) redistributing the unscheduled tasks to the unmanned aerial vehicles through the tabu table, and randomly using the transfer factors or the exchange factors to scramble the scheduling scheme S to generate a new task allocation scheme A'. The specific implementation process of the step S7 includes;
iv) initializing the global optimum S_{g}I.e. replacing the global optimum scheme S by the scheduling scheme S_{g}(ii) a If ΔIf f is more than or equal to 0, replacing the scheduling scheme S with a new scheduling scheme S'; if the current scheme is better than the global optimal scheme S_{g}Then the global optimum scheme S is replaced by the new scheduling scheme S_{g}(ii) a Otherwise, judging exp (delta f/T)_{l}) If yes, replacing the scheduling scheme S with a new scheduling scheme S'; wherein Δ f is the difference between the total benefit value of the new scheduling scheme S' and the total benefit value of the scheduling scheme S.
The method adopts Metropolis criterion to accept the degradation solution, is beneficial to the algorithm to jump out of the local optimal solution, and improves the optimization capability and exploration capability of the algorithm.
The specific implementation process of step S8 includes:
v) recording the corresponding relation between the unscheduled tasks and the unmanned aerial vehicles, namely if a certain unmanned aerial vehicle cannot execute a certain task, performing taboo at a position corresponding to a taboo table so as to avoid repeated allocation of the unscheduled tasks to the same unmanned aerial vehicle in a short time, and adding 1 to the value of the iteration times h at the same temperature; wherein the initial value of the iteration times h at the same temperature is 1;
vi) judging that h is less than or equal to h_{max}If yes, returning to the step iii); otherwise, the value of the iteration number l is added with 1, and the temperature T is increased_{l}Is updated to T_{l}X σ, return to step ii); wherein h is_{max}Is the Markov chain length; sigma is an attenuation factor;
outputting a final scheduling scheme when one of the following stop conditions is satisfied; the stop condition includes: the updated temperature is lower than the initial temperature T_{o}(ii) a Or the iteration number q of the optimal solution continuously keeping unchanged is equal to the maximum iteration number l_{max}(ii) a Wherein, the optimal solution refers to the scheduling scheme output in step iv).
By continuously iterating and optimizing the multiunmanned aerial vehicle task scheduling scheme in the step S8, the complexity of the original largescale task scheduling problem can be effectively reduced, and the quality of the task scheduling scheme is improved.
Calculating the profit value of each scheduling scheme by using a multiunmanned aerial vehicle task scheduling model; the multiunmanned aerial vehicle task scheduling model expression is as follows:
C1:
C2:
C3:
C4:
st_{i}≤at_{i} ^{k}≤et_{i},k∈U；
C5:
C6:
C7:
wherein f represents the total benefit of the scheduling task; u is a set of drones, U ═ 1, 2.., m }; omega_{i}Is the profit value for task i; [ st ] A_{i},et_{i}]Indicating task i allowedA permissible earliest start time and latest end time; dt_{i}Representing the service time of task i; t is t_{i,j}Representing the flight times of task i to task j; d_{i,j}Represents the distance from task i to task j; l is_{k},E_{k},N_{k}Respectively representing the maximum range, energy constraint and memory capacity of the kth unmanned aerial vehicle; m is a constant;a binary variable indicating whether the kth drone flies from task i to task j; at (a)_{i} ^{k}Representing the time when the kth drone arrives at task i; 0, n +1 respectively represents the first virtual task and the last virtual task of each unmanned aerial vehicle; i, j denote the task index.
The multiunmanned aerial vehicle task scheduling model is constructed, the largescale multiunmanned aerial vehicle task scheduling problem is deeply analyzed, the largescale multiunmanned aerial vehicle task scheduling problem to be solved by the method can be more visually shown, the problem analysis direction is accurate, and the problem of unmanned aerial vehicle task scheduling is better solved.
The invention also provides a multiunmanned aerial vehicle task scheduling system, which comprises computer equipment; the computer device is configured or programmed for performing the steps of the abovedescribed method.
As an inventive concept, the present invention also provides a computerreadable storage medium storing a program; the program is configured for performing the steps of the abovedescribed method.
Compared with the prior art, the invention has the beneficial effects that:
1. the multiunmanned aerial vehicle task scheduling problem is divided into a plurality of singleunmanned aerial vehicle task scheduling subproblems, the multiunmanned aerial vehicle task scheduling subproblems comprise a multiunmanned aerial vehicle task allocation stage and a singleunmanned aerial vehicle task scheduling stage, and the twostage iterative optimization method (namely, the task allocation scheme and the task scheduling scheme are subjected to iterative optimization) can achieve the maximization of the overall benefit;
2. the method can effectively balance timeliness and optimality, a better scheduling scheme can be obtained only by consuming 2.36s, and the yield is as high as 84.5%.
Drawings
FIG. 1 is a flow chart of the method of the present invention;
FIG. 2(a) shows an operator inserted in the neighborhood structure of the VND algorithmSchematic diagram of (1); FIG. 2(b) is a diagram of crossover operators in a VND algorithm neighborhood structureSchematic diagram of (1);
FIG. 3 is a diagram of a simulation scenario in accordance with an embodiment of the present invention;
FIG. 4(a) is a graph of the profitability of various cases of embodiments of the present invention; FIG. 4(b) the number of scheduled tasks for different cases of embodiments of the present invention;
FIG. 5 is a SATLVND convergence curve in a simulation experiment of the present invention.
Detailed Description
The state space of multiunmanned aerial vehicle cooperative task scheduling exponentially increases with the number of unmanned aerial vehicles and tasks, so that the solution space of the problem faces a serious combined explosion problem. Traditional task scheduling algorithms have difficulty in generating high quality solutions within a reasonable run time. To solve the problem, the invention provides a cluster unmanned aerial vehicle task scheduling framework (DCF) based on a divideandconquer strategy. The framework reduces the complex problem into a plurality of single machine scheduling subproblems, each of which is to be solved independently. Considering that the decomposition of the problem may affect the global optimality of the final solution result, in the process of solving the multiunmanned aerial vehicle cooperative task scheduling problem, the two processes of the decomposition of the complex problem and the solution result of the subproblem are interactively performed. The frame comprises two stages: the first stage is a multiunmanned aerial vehicle task allocation stage, and original problem division is achieved; the second phase is a task scheduling phase of the single unmanned aerial vehicle and is a solving process of the subproblem. The scheduling framework based on dividebyconquer strategy is shown in figure 1.
In the task allocation stage, only the geographic position of the task is considered, and the initialization of the task allocation scheme is realized by adopting a fuzzy Cmeans clustering algorithm based on the equilibrium principle. Thus, the tasks in the assignment scheme are not in the order in which they are performed, nor can the drone determine whether the task can be completed. According to the scheduling result of each unmanned aerial vehicle, three adjustment factors (tabu factor, transfer factor and exchange factor) are designed to adjust and improve the allocation scheme, so that a better scheduling scheme is obtained. The taboo factor adopts a taboo table to record the distribution relation between the unscheduled task and the multiple unmanned aerial vehicles, and can effectively avoid distributing the same unscheduled task to the same UAV (unmanned aerial vehicle) in a short time. The transfer factor refers to one UAV transferring one scheduling task in its scheduling scheme to another UAV. The exchange factor refers to the task of two UAVs exchanging each other in one scheduling scheme.
In the single UAV scheduling stage, a VND algorithm is designed according to the task allocation scheme of the single UAV to realize the scheduling task scheme of each UAV. The tasks in the scheduling scheme follow the execution sequence and can be executed and completed by the unmanned aerial vehicle. Wherein, the scheduling result of the single UAV may be regarded as a scheduling subscheme. The overall scheduling scheme for all drones can be obtained by merging all subschemes.
In the multiunmanned aerial vehicle task scheduling process, the two stages are iteratively and interactively carried out until a stopping criterion is met. There are two stopping criteria: (1) the minimum temperature of the simulated annealing algorithm, and (2) the maximum number of iterations for which the solution is continuously held constant. In each iteration, the unscheduled tasks in the second phase will be redistributed in the next first phase by the tabu factor. In order to be able to jump out of the local optimum, the algorithm destroys in certain iterations some two single drone feasible scheduling schemes by transfer factors or exchange factors. The divideandconquer scheduling framework converts the multiUAV task scheduling problem into a plurality of singleUAV scheduling problems, thereby effectively reducing the complexity of the original problem. The scheduling framework based on the divideandconquer strategy mainly comprises the following steps:
step 1: constructing a multiunmanned aerial vehicle task scheduling model taking the maximized task benefits as an objective function;
step 2: adopts a fuzzy Cmeans clustering algorithm (F) based on the equilibrium principleCME) initialization task allocation scheme a, a ═ a_{1},…,a_{k},…,a_{m}}；
Step 3: based on a multiunmanned aerial vehicle task scheduling model, according to a task allocation scheme a of an unmanned aerial vehicle k_{k}And adopting a VND algorithm to generate a scheduling scheme s of the unmanned aerial vehicle k_{k}；
Step 4: merging all standalone scheduling schemes s_{1},s_{2},…,s_{m}Therefore, a multiunmanned aerial vehicle scheduling scheme S is obtained, and the income values of the scheduling tasks in the scheduling scheme are accumulated one by one to obtain the total income value of the multiunmanned aerial vehicle scheduling scheme S;
step 5: according to the multiunmanned aerial vehicle scheduling scheme S, the nonschedulable tasks are redistributed through a SATL (simulated annealing algorithm based on a tabu table) algorithm to generate a new task allocation scheme A ', A ═ a'_{1},…,a′_{k},…,a′_{m}}；
Step 6: allocating scheme a 'according to new task of unmanned aerial vehicle k'_{k}Generating scheduling scheme s 'by using VND algorithm'_{k}；
Step 7: merging all standalone scheduling schemes s'_{1},…,s′_{m}Thus, a multiunmanned aerial vehicle scheduling scheme S 'is obtained, and the income values of the scheduling tasks in the scheduling scheme are accumulated one by one to obtain the total income value of the multiunmanned aerial vehicle scheduling scheme S';
step 8: judging whether the total benefit value of the scheme S ' is greater than that of the S, and if so, replacing the scheme S by the scheme S ', and S ← S ';
step 9: returning to Step 5, repeating the steps until a stopping criterion is met, wherein the stopping criterion comprises two types: (1) the minimum temperature of the simulated annealing algorithm, and (2) the maximum number of iterations for which the solution is continuously held constant. And finally realizing the maximization of the profit value and completing the solution of the multiunmanned aerial vehicle task scheduling model.
The multidrone task scheduling problem can be viewed approximately as a vehicle path problem with time window (VRPTW)^{[23,24]}. And constructing a multiunmanned aerial vehicle cooperative task scheduling model by referring to a classical VRPTW model and combining unique characteristics of a multiunmanned aerial vehicle scheduling problem. Assume that tasks are independent of each other and assignedA specific profit value, an earliest start time and a latest end time are given. Table 1 lists all symbols used in the task scheduling model.
TABLE 1 symbol definitions
Let 0, n +1 denote the first and last virtual task of each UAV, respectively. Two types of decision variables are defined. A flag indicating whether the drone k flies from task i to task j, which is defined by a binary variableIf UAV k flies from task i to task j, thenIf not, then,at_{i} ^{k}indicating the time at which the drone arrived at the mission. If the drone is not performing a task, at_{i} ^{k}Equal to infinity; otherwise, at_{i} ^{k}Equal to the actual arrival time. The multidrone task scheduling model may be represented as follows.
C1:
C2:
C3:
C4:
st_{i}≤at_{i} ^{k}≤et_{i},k∈U (8)
C5:
C6:
C7:
In the scheduling model, the objective function f is to maximize the total benefit of the scheduling task. Constraint C1 indicates that each drone must start at base (i.e., task 0) and return to base (i.e., task n +1) after the task is completed. Constraint C2 indicates that each real task has at most one predecessor and one successor. C3 means that the number of preceding tasks equals the number of subsequent tasks for each actual task and each UAV. Constraints C4C7 represent time window constraints, maximum range constraints, energy constraints, and memory capacity constraints, respectively. C1C7 are constraints of the multidrone task scheduling model.
The largescale task scheduling problem faces the challenge of computational complexity, and in order to solve the problem, the invention adopts an FCME clustering algorithm^{[26]}And dividing the largescale task into several clusters, thereby obtaining an initial task allocation scheme of each unmanned aerial vehicle. Different from the traditional clustering algorithm based on division, FCME sets the index beta of membership_{k,j}To represent the relationship between drone k and task j. Degree of membership beta_{k,j}A larger size indicates that drone k and task j are more closely related. Firstly, initializing the membership degree randomly, then continuously calculating the clustering center by using a correlation formula, evaluating the quality E of each clustering and updating the membership degree until E meets the error requirement. In order to reduce the variance of the number of tasks assigned to different drones, the invention sets the maximum number of tasks assigned to each drone. And finally, distributing the tasks according to the membership degree and the maximum task number.
The FCME clustering algorithm mainly comprises the following steps:
step 1: random initialized membership degree beta_{k,j},k∈[1,m]J belongs to T (task set T, number m of unmanned aerial vehicles);
step 2: continuously calculating the clustering center mu according to the following formula_{k}And evaluating the quality E of each clustering and updating the membership degree.
Where b is a smoothing factor, typically set to 2; x is the number of_{j}Is the coordinate of task j.
Step 3: judging whether the E meets the precision error requirement (the error requirement can be set according to actual use requirements), and if so, turning to Step 4; otherwise, turning to Step 2;
step 4: scheduling scheme a of task of initial unmanned aerial vehicle k_{k}Arranged as an empty set, i.e.The number of tasks gamma selected is set to be the smallest integer greater than or equal to  T /m; collectionInitializing the joint to be T; unmanned aerial vehicle index k ← 1;
step 5: according to the membership degree of the tasks and the cluster k, the tasks of the set AT are arranged according to a descending order;
step 6: adding the first gamma tasks after descending order to a_{k}And delete these tasks from the AT;
Step 7：γ←min{ceil(T/m),AT},k←k+1；
step 8: judging whether the set AT is an empty set or not, if not, turning to Step 5; otherwise, Step9 is executed;
Step 9：A←{a_{1},a_{2},…,a_{m}and obtaining an initial task scheduling scheme A.
Variable Neighborhood Descent (VND) is a metaheuristic algorithm, originally developed by Mladenovic and Hansen^{[25]}The method solves the problem of combination optimization. Given an initial solution x, the VND algorithm optimizes the initial solution by using multiple neighborhood structures in turn.Representing the pth neighborhood structure of the initial solution x. If a better solution can be found in the pth neighborhood structure, the VND algorithm receives the better solution and returns to the first neighborhood structure for further searching. Otherwise, the VND algorithm searches the current solution using the p +1 th neighborhood structure. It is worth noting that only improved solutions will be accepted.
(1) Initial solution generation
To produce an initial feasible scheduling scheme, a greedy algorithm, i.e., a highestscorefirstassigned algorithm (HSFA), is proposed. All tasks are scored according to the evaluation index, and the task with the highest score is preferentially allocated each time. In the HSFA algorithm, the invention selects 5 indexes to evaluate the value of each task, namely Indicating the distance of task i from the base,indicating the duration of the time window for task i,indicating the degree of urgency of the task i,indicating the geographical position advantage of task i,and evaluating the profit value of the task i. All indices will be normalized, then task i's score (g)_{i}) The following were used:
wherein alpha is_{q}Is thatThe weight of (a) is determined,
all tasks are sorted in descending order according to their relevance scores, and the task with the highest score is scheduled preferentially each time. The HSFA algorithm comprises the following main steps:
step 1: initializing a scheduled set of tasks and an unscheduled set of tasks
Step 2: evaluating 5 indexes of the distance from each task to the base, the duration time of a time window, the urgency degree of the task, the geographic position of the task and the profit value, weighting the indexes by adopting a formula (12) to obtain the score of each task, and obtaining the score condition r of all the tasks;
step 3: selecting a task c with the highest score from r;
step 4: judging whether the task C with the highest score meets all constraint conditions C1C7 in the multiunmanned aerial vehicle task scheduling model, if so, adding the task C into a scheduling task set z_{k}Performing the following steps;
otherwise, add task c to unscheduled task set u_{k}；
Step 5: removing task c from r;
step 6: turning to Step 3, the steps are repeated until r is an empty set.
Step 7: merging z_{k}And u_{k}Obtaining an initial scheduling task scheme s of the unmanned aerial vehicle_{k}。
(2) Neighborhood structure
The tasks to be allocated are divided into scheduled tasks and unscheduled tasks. The neighborhood structure in the VND algorithm is designed for unscheduled tasks. Before solution improvement, unscheduled tasks are sequenced according to income values of the unscheduled tasks, and the tasks with high income values are scheduled preferentially as far as possible. The invention constructs two neighborhood structures, as follows:
1) interpolation operatorAn unscheduled task is selected and inserted into a complete task scheduling scheme. More specifically, the operator can be described as: first, the unscheduled task with the highest benefit value is selected. Then, whether the earliest starting time of the task is later than that of the selected unscheduled task exists in the task scheduling scheme or not is judged, and the scheduling tasks meeting the requirements are screened out to serve as an insertion position candidate set. Finally, randomly selecting an insertion position from the candidate set and judging whether all constraint conditions are met. The specific meaning of this operator is shown in fig. 2 (a).
2) Crossover operatorSelecting one unscheduled task, on the premise of satisfying the constraint condition,to be exchanged with a task in the task scheduling scheme.
As shown in FIG. 2(b), first, an unscheduled task with the highest profit value is selected. Scheduling tasks having a profit value lower than the selected task profit value are then determined. And finally, considering the maximization of the constraint conditions and the total scheduling profit value, and selecting the exchanged scheduling tasks.
The method comprises the following specific steps:
step 1: initial scheduling task plan s for unmanned aerial vehicle k_{k}Using interpolation operatorsOptimizing, if a better scheme than the initial task scheme can be found, updating the task scheme s_{k}Go to Step 3; otherwise, turning to Step 2;
step 2: for scheme s_{k}Using commutative operatorsOptimizing, if a better scheme than the initial task scheme can be found, updating the task scheme s_{k}And go to Step 3; otherwise, directly turning to Step 3;
step 3: turning to Step 1 until the maximum iteration number is met, and finally obtaining the optimized unmanned aerial vehicle scheduling task scheme s_{k}。
Based on a divideandconquer scheduling framework, the invention provides a simulated annealing algorithm (SATL) embedded with a tabu table to complete task redistribution among multiple unmanned aerial vehicles. After task reallocation is completed, the VND algorithm generates a task scheduling scheme for each drone. In summary, a SATL algorithm (SATLVND) based on a VND algorithm is proposed for the multidrone task scheduling problem. The SATLVND algorithm mainly comprises the following steps:
step 1: according to the initial task allocation scheme a, a ═ a_{1},…,a_{k},…,a_{m}Obtaining a singlemachine scheduling scheme s of each unmanned aerial vehicle by adopting a VND algorithm_{k},k∈[1,m]；
Step 2: merging single machine scheduling scheme s_{1},s_{2},…,s_{m}Acquiring a complete scheduling scheme S, and accumulating the income values of the scheduling tasks in the scheduling scheme one by one to obtain the total income value of the multiunmanned aerial vehicle scheduling scheme S;
step 3: setting the initial temperature T manually_{o}Maximum temperature T_{f}Maximum number of iterations l_{max}Markov chain length h_{max}An attenuation factor sigma, initializing a tabu table as an empty set, initializing iteration count l and a global optimal scheme S_{g}The number of iterations q and the temperature T for which the optimal solution remains continuously constant_{l}，l←1,S_{g}←S,q←1,T_{l}←T_{o}；
Step 4: judging whether T is satisfied_{l}＞T_{f}And q is less than l_{max}If yes, executing Step 5; otherwise, the process is ended.
Step 5：h←1；
Step 6: redistributing the tasks which cannot be dispatched to other unmanned aerial vehicles through a taboo factor (taboo table), randomly using a transfer factor or an exchange factor to disturb the singlemachine dispatching scheme, and finally generating a new task allocation scheme A';
step 7: according to the initial task allocation scheme A ', A ' ═ a '_{1},…,a′_{k},…,a′_{m}Obtaining the standalone scheduling schemes s 'of all unmanned aerial vehicles by adopting a VND algorithm'_{k},k＝1,2,…,m,；
Step 8: merging all standalone scheduling schemes s'_{1},…,s′_{m}Obtaining a complete scheduling scheme S ', and accumulating the income values of the scheduling tasks in the scheduling scheme one by one to obtain the total income value of the multiunmanned aerial vehicle scheduling scheme S';
step 9: calculating a profit value difference, Δ F ═ F (S') F (S);
step 10: if Δ f is greater than or equal to 0, replacing S with a scheme S ', S ← S', if the current scheme is better than the global optimal scheme, S_{g}(vii) S'; otherwise, judging exp (delta f/T)_{l}) ξ (ξ is an arbitrary value between 0 and 1), if satisfied, S ← S';
step 11: updating a taboo table, h ← h + 1;
step 12: h is judged to be less than or equal to h_{max}If yes, turning to Step 6; otherwise, l ← l +1, T_{l}←T_{l}And (5) multiplying the sigma, and turning to Step 4 to finally obtain the multiunmanned aerial vehicle scheduling task scheme S with the maximized income value.
In the task reallocation stage, three adjustment factors are designed to guide the task allocation process, including a tabu factor, a transfer factor and an exchange factor, as shown in fig. 1. All unscheduled tasks are randomly allocated to the multiple drones according to the taboo factor. The taboo factor refers to a taboo table for recording the latest task allocation operation to determine which tasks are allocated to which drone, thereby avoiding frequently allocating the same unscheduled task to the same drone in each iteration, and thus preventing premature convergence of the SA algorithm. The transfer factor and the swap factor redistribute tasks between two feasible scheduling schemes to diversify the scheduling schemes. The transfer and exchange factors will randomly select an operation in certain iterations. The transfer factor refers to that one unmanned aerial vehicle transfers one task in the scheduling scheme to another unmanned aerial vehicle. The exchange factor means that two drones exchange tasks in one scheduling scheme with each other.
The simulation experiment of the embodiment of the invention compares the method with other three clustering algorithms and verifies the effectiveness of the FCME on the initial task allocation scheme. In addition, in order to effectively evaluate the performance of the SATLVND algorithm, a comparative simulation experiment is carried out with a branchandbound algorithm and 7 heuristic algorithms. The experiment is mainly carried out on a Dell PC which is configured as a Core i 584002.80 GHz CPU and an 8G memory, the following algorithms are all realized by MatlabR2016b software programming, and CPLEX12.5 is selected as an accurate MIP solver.
As shown in fig. 3, the simulation scene has an application range of 100km × 100km, and an ellipse and a pentagram represent an obstacle and a drone base, respectively. The distance between any two points in the scene can be calculated by the APPATT algorithm^{[27]}And (4) obtaining. Tasks are randomly distributed in a simulation scene, the scheduling period is the morning peak on duty, from 7 to 9 in the morning, and the time window duration of the tasks is any time period between 10s and 45 s. The present invention assumes that all drones are of the same type. Phase of unmanned aerial vehicleThe parameters for the offparameters and SATLVND calculations are shown in tables 2 and 3, respectively.
The index λ indicates that when the number of iterations is a multiple of λ, the allocation scheme is diversified with a transfer factor or an exchange factor. Maximum number of iterations l_{max}Indicating that the optimal solution continues to remain unchanged for a constant number of iterations. The taboo length tau is determined by a repeated experiment method: the effect of the tabu table on the algorithm performance was investigated experimentally using 6 cases (number of tasks 40, 60, 80, 100, 200 and 300). According to experiments, when the number of tasks is lower than 100, the length of a tabu table is 2, and the SATLVND algorithm can achieve the best performance; when the number of tasks exceeds 100, the length of the tabu table is 4, and the SATLVND algorithm can achieve the best performance. The configuration method of other parameters of the SATLVND is also obtained by a large amount of simulation experiment analysis based on the method.
TABLE 2 UAV parameters
TABLE 3 parameter settings for SATLVND
In order to embody the superiority of the FCME algorithm, the present embodiment selects the Kmeans algorithm, the FCM algorithm, and the CURE algorithm as comparison algorithms. There are 10 existing groups of observation tasks, 8 of which (C1C8) are randomly distributed, while the rest 2 (C9, C10) are nonconvex in their distribution. Because the evaluation of the initial task allocation scheme has difficulty, the embodiment of the invention evaluates the performance of the clustering algorithm from two aspects of the final scheduling result and the running time. The results of the comparative experiments are shown in table 4. Wherein Num _ T and Num _ U represent the number of tasks and the number of drones, respectively. The profitability is the ratio of the profitability value obtained by scheduling the task to the total task profitability value. From Table 4, it can be seen that FCME generates the best objective function values for C1C8, compared to Kmeans, FCM, and CURE algorithms. When solving for C9 and C10, the solving performance of the partitionbased clustering algorithm (Kmeans, FCM, and FCME) is inferior to that of the hierarchybased clustering algorithm CURE, but it is worth noting that a relatively poor initial allocation scheme can still obtain a better scheduling scheme through continuous iterative optimization. Moreover, the scheduling schemes obtained by the three initial allocation schemes through iterative optimization have little difference and similar running time, which shows that the conventional clustering algorithm based on division can basically meet the requirements of the initial task allocation schemes.
Table 4 solving results of each case by each clustering algorithm
In order to test the effectiveness of the SATLVND algorithm, an accurate algorithm in a CPLEX solver, namely a branch and bound algorithm, is selected as a comparison algorithm, and the difference between the solution of the SATLVND algorithm and the optimal solution can be intuitively sensed. The embodiment of the present invention designs 9 groups of cases, the number of tasks of which is 40, 60, 80, 100, 120, 140, 160, 180 and 200, respectively. The results of the calculations for the 9 cases are shown in table 5, including run time, profitability, number of scheduled tasks, and the gap from the optimal solution. The SATLVND algorithm is a stochastic algorithm that runs 20 times when solving the task assignment problem.
TABLE 5 comparison of branchandbound Algorithm
As can be seen from table 5, CPLEX generated the optimal average objective function value for each case, but it is undeniable that a large amount of computational resources were consumed. For example, in solving case C16, CPLEX needs to run for more than 4 hours to obtain the optimal solution, and thus CPLEX is not suitable for solving the largescale task scheduling problem. However, SATLVND can achieve suboptimal solutions in a short time. When solving the cases C17C19, the SATLVND obtained solution only differs from the optimal solution by 4%, while the runtime does not exceed 6 s. In addition, compared with the yield, the scheduling task quantity in the scheme obtained by the two algorithms is slightly different, which shows that the SATLVND preferentially selects the tasks with high yield under the condition of limited capacity.
Because CPLEX is very timeconsuming in solving the largescale task scheduling problem, the performance of the SATLVND algorithm in solving the largescale task scheduling problem cannot be further verified. Therefore, the invention selects 7 heuristic algorithms as a comparison algorithm for solving the largescale task scheduling problem. The experimental purposes are mainly two points:
(1) verifying the effectiveness of the divideandconquer scheduling framework. (2) And verifying the feasibility of taboo factors, transfer factors and exchange factors in the SATLVND algorithm.
At present, the multiunmanned aerial vehicle scheduling research aiming at the maximized income is less, so that the invention designs four comparison algorithms, namely tabu search algorithm (TS), by referring to the traditional multiunmanned aerial vehicle scheduling method and considering the problem of multiunmanned aerial vehicle largescale task scheduling as a whole idea^{[28]}Discrete Particle Swarm Optimization (ADPSO) based on selfadaptive inertial weight^{[29]}Large scale neighborhood search algorithm (large neighbor search LNS)^{[30]}And the HSFA algorithm.
Besides, different scheduling algorithms based on a divideandconquer framework are also used as comparison algorithms, including SATLH algorithm, SAVND algorithm and SATLVNDI algorithm without transfer factors and exchange factors, and the series of algorithms are collectively called SA series algorithms. The HSFA is a deterministic algorithm, so that the HSFA only needs to be operated once to solve the task allocation problem corresponding to each case. While the remaining 7 algorithms are stochastic algorithms, and the 7 algorithms are run 20 times each when solving the task scheduling problem. The simulation test results are shown in table 6, fig. 4(a), and fig. 4 (b). The last column in table 6 represents the coefficient of variation of the benefit values, i.e., the ratio of the standard deviation of the benefit values of the scheduling task to the mean.
As can be seen from fig. 4(a), in the conventional four task scheduling algorithms, the LNS algorithm is better than the other three algorithms, but is less effective than the SA series algorithm. Both LNS and SA series algorithms use destruction and repair strategies to jump out the optimal solution, while searching for the optimal solution to the problem by adjusting the current solution in iterative fashion. However, they differ in framework and desearch strategies. In the aspect of a framework, SA series algorithms adopt a divideandconquer framework, namely, a largescale task scheduling problem of a plurality of unmanned aerial vehicles is divided into a plurality of singlemachine smallscale task scheduling subproblems. However, the LNS algorithm considers the problem of scheduling largescale tasks by multiple drones as a whole. Unlike the solution search strategy where the LNS algorithm randomly selects the removal task, the SA series algorithm replans the unscheduled task every time and destroys the viable solution in some iterations. Furthermore, the SATLVND algorithm diversifies the solution by means of transfer factors and exchange factors, thereby obtaining a better quality solution than the SATLVNDI algorithm. It can be seen from table 6 that the HSFA has a solution time as low as milliseconds due to its simple greedy rule. The SATLVNDI algorithm only needs to replan the nondispatchable tasks each time, leaving out the perturbation operations of the solution, thereby saving most of the time. However, the ADPSO algorithm employs a groupintelligent search strategy, resulting in extended runtime as the task scale expands. It also consumes a significant amount of time due to the LNS algorithm repeatedly breaking and repairing the scheme.
Although both the SATLVND algorithm and the SAVND algorithm adopt a divideandconquer framework, the SATLVND is superior to the SAVND algorithm in the quality of the solution. Primarily because the tabutable embedded in the SATLVND may enhance the prospecting capabilities of the SA. While it has been theoretically demonstrated that SA can converge to a globally optimal solution with sufficient run time and proper annealing strategy. But there is increasing evidence that SA is generally prone to converge to a locally optimal solution in practical applications. Therefore, when SA is used, it is important to ensure the diversification of solutions. The tabu table strategy is inspired by tabu search, and shortterm circulation and revisit can be prohibited through the tabu table, so that premature convergence of the SA is prevented. The time required for the SAVND and SATLVND to obtain the task scheduling solution is close, which indicates that the SATL can generate a better task scheduling solution without significantly increasing the time consumption compared to the SA. Furthermore, from the variation coefficients in Table 6, SATLVND is found to be more stable than the SAVND algorithm in solving the largescale scheduling problem.
In a word, the divideandconquer scheduling framework can effectively solve the problem of largescale task scheduling of multiple unmanned aerial vehicles. The SATLVND algorithm can balance timeliness and solution quality, and is a preferred method for solving the problem of multiunmanned aerial vehicle largescale task scheduling. Under certain conditions with high realtime requirements, the HSFA algorithm or the SATLVNDI algorithm can be selected to perform time conversion.
Table 6 solving results of various cases by various task scheduling algorithms
For further testing, the simulation experiment scenario of this example selects the chinese sand rainflower area (N2802 ', E11257'). And selecting 100 crossroads as traffic data acquisition task points in a simulation experiment scene, and using the traffic command center of Changsha city as the base of the unmanned aerial vehicle. Assuming that the scene has 6 big Jiang unmanned planes in total, the flight range is 18km, and the flight speed is 50 km/h. The scheduling period is from 7 am to 9 am, and the duration of the time window of each task is any value between 10s and 45 s. The scheduling scheme is shown in table 7 and the convergence of the profitability is shown in fig. 5. The SATLVND algorithm yielded an yield of 84.5% and run time of 2.36 s.
As shown in FIG. 5, SATLVND found a satisfactory solution at generation 20, indicating that the SATLVND algorithm has strong prospecting power. Solution diversification strategies (i.e., exchange factors and transfer factors) and Metropolis guidelines avoid premature convergence of the SATLVND algorithm to a locally optimal solution. Finally, SATLVND searched for the optimal solution at generation 63. And (3) continuously keeping the unchanged maximum iteration times according to the stopping criterion (2), wherein the algorithm is converged in the 93 rd generation, and the optimal yield is 84.5%.
TABLE 7 task scheduling scheme in sandy raining areas
The invention provides a twostage iterative optimization method based on a divideandconquer framework to solve the problem of multiunmanned aerial vehicle largescale task scheduling. The framework divides multiunmanned aerial vehicle task scheduling into a multiunmanned aerial vehicle task allocation stage and a single unmanned aerial vehicle task scheduling stage. In the task allocation stage, a simulated annealing algorithm (SATL) based on a tabu table is provided based on a tabu factor, a transfer factor and an exchange factor, communication among a plurality of single unmanned aerial vehicle task scheduling schemes can be effectively enhanced, and the profit value of a multiunmanned aerial vehicle system is strived to be maximized. In the task scheduling stage of the single unmanned aerial vehicle, a variable neighborhood descent search algorithm (VND) is provided to realize the task scheduling of the single unmanned aerial vehicle in consideration of the platform capacity and the task requirements of the unmanned aerial vehicle. These two phases are iterated and interleaved until a stopping criterion is met. A large number of simulation experiments verify the effectiveness of the method, and the following conclusion can be obtained:
(1) compared with the branchandbound algorithm, the SATLVND algorithm can obtain an approximately optimal task scheduling scheme, and the optimal solution gap obtained by the SATLVND algorithm and the CPLEX is only 6%.
(2) In the 8 heuristic task scheduling methods designed by the invention, the SATLVND algorithm has the best effect, and the timeliness and the optimality can be effectively balanced.
(3) In a simulation experiment in a real scene, the SATLVND algorithm only takes 2.36s to obtain a better scheduling scheme, and the yield is as high as 84.5%. The SATLVND algorithm can be used as a solution algorithm for the actual task scheduling problem and has a wide application prospect.
Reference to the literature
[1]Chow J Y.Dynamic UAVbased traffic monitoring under uncertainty as a stochastic arcinventory routing policy[J].International Journal of transportation science and technology.5(3),167185(2016).
[2]Xu Y,Yu G,Wu X,et al.An enhanced ViolaJones vehicle detection method from unmanned aerial vehicles imagery[J].IEEE Transactions on Intelligent Transportation Systems.18(7),18451856(2016).
[3]Wu G,Pedrycz W,Li H,et al.Coordinated planning of heterogeneous earth observation resources[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems.46(1),109125(2015).
[4]Sawadsitang S,Niyato D,Tan P,et al.Joint ground and aerial package delivery services:A stochastic optimization approach[J].IEEE Transactions on Intelligent Transportation Systems.20(6),22412254(2018).
[5]Sacramento D,Pisinger D,Ropke S.An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J].Transportation Research Part C:Emerging Technologies.102,289315(2019).
[6]Pokhrel S R,Jin J,Le Vu H.Mobilityaware multipath communication for unmanned aerial surveillance systems[J].IEEE Transactions on Vehicular Technology.68(6),60886098(2019).
[7]Ke R,Li Z,Tang J,et al.Realtime traffic flow parameter estimation from UAV video based on ensemble classifier and optical flow[J].IEEE Transactions on Intelligent Transportation Systems.20(1),5464(2018).
[8]Shima T,Rasmussen S J,Sparks A G,et al.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J].Computers&Operations Research.33(11),32523269(2006).
[9]Jia Z,Yu J,Ai X,et al.Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm[J].Aerospace Science and Technology.76,112125(2018).
[10]Bai X,Yan W,Ge S S,et al.An integrated multipopulation genetic algorithm for multivehicle task assignment in a drift field[J].Information Sciences.453,227238(2018).
[11]Zhen Z,Xing D,Gao C.Cooperative searchattack mission planning for multiUAV based on intelligent selforganized algorithm[J].Aerospace Science and Technology.76,402411(2018).
[12]Zhu M,Du X,Zhang X,et al.MultiUAV rapidassessment taskassignment problem in a postearthquake scenario[J].IEEE Access.7,7454274557(2019).
[13]Chen Y,Yang D,Yu J.MultiUAV Task Assignment With Parameter and TimeSensitive Uncertainties Using Modified TwoPart Wolf Pack Search Algorithm[J].IEEE Transactions on Aerospace and Electronic Systems.54(6),28532872(2018).
[14]Wang J,Guo J,Zheng M,et al.Uncertain multiobjective orienteering problem and its application to UAV reconnaissance mission planning[J].Journal of Intelligent&Fuzzy Systems.34(4),22872299(2018).
[15]Liu Y,Song R,Bucknall R,et al.Intelligent multitask allocation and planning for multiple unmanned surface vehicles(USVs)using selforganising maps and fast marching method[J].Information Sciences.496,180197(2019).
[16]Zhao W,Meng Q,Chung P W.A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario[J].IEEE transactions on cybernetics.46(4),902915(2015).
[17]Yao W,Qi N,Wan N,et al.An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles[J].Aerospace Science and Technology.86,455464(2019).
[18]Smith R G.The contract net protocol:Highlevel communication and control in a distributed problem solver[J].IEEE Transactions on computers.(12),11041113(1980).
[19]Deng M,Liu B,Li S,et al.A TwoPhase Coordinated Planning Approach for Heterogeneous EarthObservation Resources to Monitor Area Targets[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems.2020).
[20]Ren L,Yu Y,Cao Z,et al.An optimal task allocation approach for largescale multiple robotic systems with hierarchical framework and resource constraints[J].IEEE Systems Journal.12(4),38773880(2017).
[21]Cao L,Shun Tan H,Peng H,et al.Multiple UAVs hierarchical dynamic task allocation based on PSOFSA and decentralized auction[C].IEEE,23682373(2014).
[22]Hu X,Ma H,Ye Q,et al.Hierarchical method of task assignment for multiple cooperating UAV teams[J].Journal of Systems Engineering and Electronics.26(5),10001009(2015).
[23]Desrochers M,Desrosiers J,Solomon M.A new optimization algorithm for the vehicle routing problem with time windows[J].Operations research.40(2),342354(1992).
[24]Liao T W.Integrated Outbound Vehicle Routing and Scheduling Problem at a MultiDoor CrossDock Terminal[J].IEEE Transactions on Intelligent Transportation Systems.2020).
[25]N,Hansen P.Variable neighborhood search[J].Computers&operations research.24(11),10971100(1997).
[26]Bezdek J C,Ehrlich R,Full W.FCM:The fuzzy cmeans clustering algorithm[J].Computers&Geosciences.10(23),191203(1984).
[27]Liu H,Li X,Fan M.An autonomous path planning method for unmanned aerial vehicle based on a tangent intersection and target guidance strategy[Z].2020).
[28]Gmira M,Gendreau M,Lodi A,et al.Tabu Search for the TimeDependent Vehicle Routing Problem with Time Windows on a Road Network[J].European Journal of Operational Research.2020).
[29]Gong Y,Zhang J,Liu O,et al.Optimizing the vehicle routing problem with time windows:a discrete particle swarm optimization approach[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C(Applications and Reviews).42(2),254267(2011).
[30]Bent R,Van Hentenryck P.A twostage hybrid local search for the vehicle routing problem with time windows[J].Transportation Science.38(4),515530(2004).
Claims (10)
1. A multiunmanned aerial vehicle task scheduling method is characterized by comprising the following steps:
s1, initializing a task allocation plan a of multiple drones, a ═ a_{1},…,a_{k},…,a_{m}}；a_{1},…,a_{k},…,a_{m}The task allocation schemes respectively correspond to the 1 st to the mth unmanned aerial vehicles; k is an element of [1, m ]]；
S2, according to the task allocation scheme a of the kth unmanned aerial vehicle_{k}Generating a scheduling scheme s of the kth unmanned aerial vehicle_{k}；
S3, merging scheduling schemes S of 1 st to mth unmanned aerial vehicles_{1},s_{2},…,s_{m}Obtaining a complete scheduling scheme S, and calculating the total benefit value of the scheduling scheme S;
s4, according to the scheduling scheme S, the task which can not be scheduled is redistributed to generate a new task allocation scheme A ', A ═ a'_{1},…,a′_{k},…,a′_{m}}；
S5, New task Allocation scheme a 'according to kth unmanned aerial vehicle'_{k}Generating a new scheduling scheme s'_{k}；
S6, combining the new scheduling schemes of the 1 st to the mth unmanned aerial vehicles to obtain a new scheduling scheme S ', and calculating the total benefit value of the new scheduling scheme S';
s7, judging whether the total benefit value of the new scheduling scheme S 'is greater than that of the scheduling scheme S, and if so, replacing the scheduling scheme S with the new scheduling scheme S';
and S8, returning to the step S4 until the set stop condition is reached, and outputting the final scheduling scheme.
2. The method for task scheduling of multiple unmanned aerial vehicles according to claim 1, wherein the specific implementation process of step S1 includes:
1) random initialized membership degree beta_{k,j}J belongs to T, and T is a task set; t ═ 1,2,. and n, where n is the number of tasks;
2) calculating the kth drone using the following equationCluster center mu of_{k}And using said cluster center mu_{k}Evaluating the quality E of each clustering, and updating the membership: wherein b is a smoothing factor; x is the number of_{j}Is the coordinate of task j; mu.s_{s}Is the center coordinate of cluster s, i.e. the cluster center of cluster s; cluster s is the sth unmanned aerial vehicle;
3) judging whether the clustering quality E meets the precision error requirement, and if so, entering the step 4); otherwise, returning to the step 2);
4) initializing k to 1, and scheduling the task of the kth unmanned aerial vehicle according to the scheme a_{k}Setting the task number gamma as a null set, setting the selected task number gamma as a minimum integer greater than or equal to  T /m, and initializing the set AT to T;
5) arranging the tasks of the set AT in a descending order according to the membership degree of the tasks and the kth unmanned aerial vehicle;
6) adding the first gamma tasks after descending order to a_{k}And deleting the first gamma tasks from the AT; let γ be min { ceil ( T /m),  AT  }, the value of k plus 1; wherein ceil () represents the smallest integer greater than or equal to the specified expression that is returned; the  T  and the  AT  respectively refer to the number of elements in the set T, AT;
7) judging whether the set AT is an empty set, if so, executing a step 8); otherwise, returning to the step 5);
8) merging a_{1},…,a_{k},…,a_{m}And obtaining a task allocation scheme A.
3. The method for task scheduling of multiple unmanned aerial vehicles according to claim 1, wherein the specific implementation process of step S2 includes:
I) initializing a set of scheduled tasks z_{k}And a set of unscheduled tasks u_{k}Is an empty set;
II) the following indices for each task: distance and time from task to baseEvaluating the window duration, the task urgency, the task geographic location and the profit value by using a formulaObtaining the score of each task and obtaining the score conditions r of all tasks; alpha is alpha_{q}Is thatThe weight of (a) is determined,q＝1,2,…,5,i∈T，indicating the distance of task i from the base,indicating the duration of the time window for task i,indicating the degree of urgency of the task i,indicating the geographical position advantage of task i,evaluating the profit value of the task i; g_{i}A score representing task i;
III) selecting the task c with the highest score from the r; judging whether the task c with the highest score meets the constraint condition of the unmanned aerial vehicle task scheduling model, if so, adding the task c into a scheduling task set z_{k}Performing the following steps; otherwise, add task c to unscheduled task set u_{k}；
IV) removing task c from r;
v) returning to the step III) until r is an empty set, and obtaining an updated scheduling task set and an unscheduled task set;
VI) merging the updated scheduling task set and the unscheduled task set to obtain the scheduling scheme s of the kth unmanned aerial vehicle_{k}。
4. The method of claim 1, wherein after step S2 and before step S3, the scheduling scheme S for the kth drone is further defined_{k}Optimizing, wherein the specific optimizing steps comprise:
A) scheduling scheme s for kth unmanned aerial vehicle_{k}Using interpolation operatorsOptimizing if finding a specific scheduling scheme s_{k}The more optimal solution is to update the task solution s_{k}Go to step C); otherwise, turning to the step B); wherein the insertion operatorThe method comprises the following steps: selecting an unscheduled task with the highest profit value, judging whether a task with the earliest starting time later than the earliest starting time of the selected unscheduled task exists in a task scheduling scheme, if so, screening out the task with the earliest starting time later than the earliest starting time of the selected unscheduled task, and putting the task into an insertion position candidate set; randomly selecting an insertion position from the insertion position candidate set, judging whether a scheduling scheme after inserting the screened task meets the constraint condition of the unmanned aerial vehicle task scheduling model, and if so, considering that the scheduling scheme after inserting the screened task is superior to the task scheduling scheme;
B) for scheduling scheme s_{k}Using commutative operatorsOptimizing if finding a specific scheduling scheme s_{k}The more optimal scheme is to update the scheduling scheme s_{k}Go to step C); otherwise, directly turning to the step C); wherein the operators are exchangedThe method comprises the following steps: selecting an unscheduled task with the highest profit value, determining a scheduling task with the profit value lower than the profit value of the selected task, considering the maximization of the constraint condition and the total scheduling profit value, and selecting the scheduling task meeting the constraint condition of the unmanned aerial vehicle task scheduling model as an updated scheduling scheme;
C) returning to the step A), and obtaining the optimized unmanned aerial vehicle scheduling task scheme s until the set maximum iteration times are met_{k}。
5. The method for task scheduling of multiple unmanned aerial vehicles according to claim 1, wherein the specific implementation process of step S4 includes:
i) set the maximum temperature T_{f}Maximum number of iterations l_{max}Initializing a tabu table as an empty set, and initializing iteration times q and temperature T of an optimal solution which are continuously kept unchanged_{l}；
ii) determination of T_{l}＞T_{f}And q < l_{max}If yes, executing step iii); otherwise, ending;
and iii) redistributing the unscheduled tasks to the unmanned aerial vehicles through the tabu table, and randomly using the transfer factors or the exchange factors to scramble the scheduling scheme S to generate a new task allocation scheme A'.
6. The method for task scheduling of multiple drones according to claim 5, wherein the specific implementation procedure of step S7 includes;
iv) initializing the global optimum S_{g}I.e. replacing the global optimum scheme S by the scheduling scheme S_{g}(ii) a If delta f is more than or equal to 0, replacing the scheduling scheme S with a new scheduling scheme S'; if the current scheme is better than the global optimal scheme S_{g}Then the global optimum scheme S is replaced by the new scheduling scheme S_{g}(ii) a Otherwise, judging exp (delta f/T)_{l}) If yes, replacing the scheduling scheme S with a new scheduling scheme S'; wherein Δ f is the difference between the total benefit value of the new scheduling scheme S' and the total benefit value of the scheduling scheme S。
7. The method for task scheduling of multiple unmanned aerial vehicles according to claim 6, wherein the specific implementation process of step S8 includes:
v) recording the corresponding relation between the unscheduled task and the unmanned aerial vehicle, namely if a certain unmanned aerial vehicle cannot execute a certain task, performing taboo at a corresponding position of a taboo table, and adding 1 to the value of the iteration times h at the same temperature; wherein the initial value of the iteration times h at the same temperature is 1;
vi) judging that h is less than or equal to h_{max}If yes, returning to the step iii); otherwise, the value of the iteration number l is added with 1, and the temperature T is increased_{l}Is updated to T_{l}X σ, return to step ii); wherein h is_{max}Is the Markov chain length; sigma is an attenuation factor;
outputting a final scheduling scheme when one of the following stop conditions is satisfied; the stop condition includes: the updated temperature is lower than the initial temperature T_{o}(ii) a Or the iteration number q of the optimal solution continuously keeping unchanged is equal to the maximum iteration number l_{max}(ii) a Wherein, the optimal solution refers to the scheduling scheme output in step iv).
8. The multiunmannedaerialvehicle task scheduling method according to any one of claims 1 to 7, wherein a profit value of each scheduling scheme is calculated by using a multiunmannedvehicle task scheduling model; the multiunmanned aerial vehicle task scheduling model expression is as follows:
C1:
C2:
C3:
C4:
st_{i}≤at_{i} ^{k}≤et_{i},k∈U；
C5:
C6:
C7:
wherein f represents the total benefit of the scheduling task; u is a set of drones, U ═ 1, 2.., m }; omega_{i}Is the profit value for task i; [ st ] A_{i},et_{i}]Representing the earliest starting time and the latest ending time allowed by the task i; dt_{i}Representing the service time of task i; t is t_{i,j}Representing the flight times of task i to task j; d_{i,j}Represents the distance from task i to task j; l is_{k},E_{k},N_{k}Respectively representing the maximum range, energy constraint and memory capacity of the kth unmanned aerial vehicle; m is a constant;a binary variable indicating whether the kth drone flies from task i to task j; at (a)_{i} ^{k}Representing the time when the kth drone arrives at task i; 0, n +1 respectively represents the first virtual task and the last virtual task of each unmanned aerial vehicle; i, j denote the task index.
9. A multiunmanned aerial vehicle task scheduling system is characterized by comprising computer equipment; the computer device is configured or programmed for carrying out the steps of the method according to one of claims 1 to 8.
10. A computerreadable storage medium characterized by storing a program; the program is configured for carrying out the steps of the method according to one of claims 1 to 8.
Priority Applications (1)
Application Number  Priority Date  Filing Date  Title 

CN202010782126.4A CN112016812A (en)  20200806  20200806  Multiunmanned aerial vehicle task scheduling method, system and storage medium 
Applications Claiming Priority (1)
Application Number  Priority Date  Filing Date  Title 

CN202010782126.4A CN112016812A (en)  20200806  20200806  Multiunmanned aerial vehicle task scheduling method, system and storage medium 
Publications (1)
Publication Number  Publication Date 

CN112016812A true CN112016812A (en)  20201201 
Family
ID=73498558
Family Applications (1)
Application Number  Title  Priority Date  Filing Date 

CN202010782126.4A Pending CN112016812A (en)  20200806  20200806  Multiunmanned aerial vehicle task scheduling method, system and storage medium 
Country Status (1)
Country  Link 

CN (1)  CN112016812A (en) 
Cited By (1)
Publication number  Priority date  Publication date  Assignee  Title 

CN113159519A (en) *  20210325  20210723  重庆大学  City sensing transportation cooperative scheduling method for multiplexing transportation unmanned aerial vehicle 

2020
 20200806 CN CN202010782126.4A patent/CN112016812A/en active Pending
Cited By (1)
Publication number  Priority date  Publication date  Assignee  Title 

CN113159519A (en) *  20210325  20210723  重庆大学  City sensing transportation cooperative scheduling method for multiplexing transportation unmanned aerial vehicle 
Similar Documents
Publication  Publication Date  Title 

Huang et al.  Large scale realtime ridesharing with service guarantee on road networks  
US8620510B1 (en)  Adaptive multivehicle area coverage optimization system and method  
CN103345504A (en)  Operator construction method of singlestar scheduling  
CN112016812A (en)  Multiunmanned aerial vehicle task scheduling method, system and storage medium  
Tran et al.  Using Fuzzy Clustering Chaoticbased Differential Evolution to solve multiple resources leveling in the multiple projects scheduling problem  
He et al.  Scheduling multiple agile earth observation satellites with an edge computing framework and a constructive heuristic algorithm  
Zhang et al.  A novel ant colony optimization algorithm for large scale QoSbased service selection problem  
Hu et al.  Application of distributed auction to multiUAV task assignment in agriculture  
CN107807665B (en)  Unmanned aerial vehicle formation detection task cooperative allocation method and device  
Guan et al.  Doubleant colony based UAV path planning algorithm  
Li et al.  An adaptive whale optimization algorithm using Gaussian distribution strategies and its application in heterogeneous UCAVs task allocation  
Zhang et al.  Intelligent Electric Vehicle Charging Recommendation Based on MultiAgent Reinforcement Learning  
CN111862579B (en)  Taxi scheduling method and system based on deep reinforcement learning  
Chen et al.  Multiconstrained network intensive vehicle routing adaptive ant colony algorithm in the context of neural network analysis  
Ayoubi et al.  An autonomous IoT service placement methodology in fog computing  
Zhou et al.  Multidepot UAV routing problem with weapon configuration and time window  
Gaowei et al.  Using multilayer coding genetic algorithm to solve timecritical task assignment of heterogeneous UAV teaming  
Liu et al.  An Iterative TwoPhase Optimization Method Based on Divide and Conquer Framework for Integrated Scheduling of Multiple UAVs  
Han et al.  Dynamic Collaborative Charging Algorithm for Mobile and Static Nodes in Industrial Internet of Things  
Ryan et al.  Unmanned aerial vehicle (UAV) route selection using reactive tabu search  
Xu et al.  Task allocation for unmanned aerial vehicles in mobile crowdsensing  
Cai et al.  A BiObjective Constrained Robust Gate Assignment Problem: Formulation, Instances and Algorithm  
Ghorpade  Airspace configuration model using swarm intelligence based graph partitioning  
Cai et al.  Multivehicles dynamic navigating method for largescale event crowd evacuations  
Xun et al.  Distributed tasksplatforms scheduling method to holonicC2 organization 
Legal Events
Date  Code  Title  Description 

PB01  Publication  
PB01  Publication  
SE01  Entry into force of request for substantive examination  
SE01  Entry into force of request for substantive examination 