Complex task planning method of space-aeronautics cooperative observation based on multi-layer interaction

LIU Jinming, CHEN Yingguo, WANG Rui, and CHEN Yingwu

College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Abstract: With the new development trend of multi-resource coordinated Earth observation and the new goal of Earth observation application of “short response time, high observation accuracy, and wide coverage”, space-aeronautics cooperative complex task planning problem has become an urgent problem to be solved.The focus of this problem is to use multiple resources to perform collaborative observations on complex tasks.By analyzing the process from task assignment to receiving task observation results, we propose a multi-layer interactive task planning framework which is composed of a preprocessing method for complex tasks, a task allocation layer, a task planning layer, and a task coordination layer.According to the characteristics of the framework, a hybrid genetic parallel tabu(HGPT) algorithm is proposed on this basis.The algorithm uses genetic annealing algorithm (GAA), parallel tabu (PT) algorithm,and heuristic rules to achieve task allocation, task planning, and task coordination.At the same time, coding improvements,operator design, annealing operations, and parallel calculations are added to the algorithm.In order to verify the effectiveness of the algorithm, simulation experiments under complex task scenarios of different scales are carried out.Experimental results show that this method can effectively solve the problems of observing complex tasks.Meanwhile, the optimization effect and convergence speed of the HGPT is better than that of the related algorithms.

Keywords: complex task, space-aeronautics cooperative, task planning framework, hybrid genetic parallel tabu (HGPT) algorithm.

1.Introduction

With the rapid development of various platform technologies, the types of observation tasks issued by users have gradually diversified, forming complex tasks based on point targets, regional targets, and collaborative target tasks.At the same time, the number of tasks issued by users is increasing.It is difficult for the task processing center to arrange observation plans for each type of task separately, and each platform has difficulties in simultaneously observing various types of tasks in the complex task set during the observation period.A single type of observation platform is used in disaster area search and rescue, surveying and mapping, anti-terrorism and antiriot, military reconnaissance, and other fields [1].It can well meet the observation needs of users.However, when various observation platforms independently perform complex tasks, due to the limitations of operation mode and energy storage characteristics, their observation efficiency and image quality cannot be guaranteed to meet user requirements.In addition, there is a lack of coordination and interaction between resources, and repeated observations may occur, which wastes existing resources[2].Therefore, how to realize the collaborative application of overall resources based on the characteristics of satellite and unmanned aerial vehicle (UAV) platforms and user needs, so as to achieve the effect of “1+1>2”, is an urgent problem to be solved.

In response to the above problems, many researchers have also conducted related research.In terms of models,Morris et al.[3,4] and Herold et al.[5] proposed a distributed framework by constructing a collaborative task allocation method.They divided the multi-platform collaborative task planning problem into multiple singleplatform task planning problems, and then formed multiple sub-planning centers.Each sub-planning center processes the assigned tasks according to certain rules.Although the task planning framework has received more recognition, this method is not suitable for large-scale and complex tasks.Liang et al.[6] built an aerospace coordinated continuous observation model for moving targets on the sea, and proposed an aerospace coordinated continuous observation strategy to solve the UAV aircraft plan.According to the resource characteristics of satellites and airship platforms and the characteristics of user requirements, Yu [7] designed a collaborative task planning framework for space-to-Earth observation resources,and proposed a task allocation method based on the idea of contract network.Li et al.[8,9] analyzed and summarized the sensor web enablement (SWE) standard in order to solve the existing aerospace resource planning and scheduling problems, and on this basis, proposed a space and space resource-to-Earth observation collaborative mission planning service model.Li et al.[10] designed a two-stage iterative planning framework to construct fitness functions based on Earth observation opportunities and conflict degrees and a task allocation method combined with tabu table strategies to improve the task profitability of the aerospace Earth observation system.Using event-driven time-expanded graph to consider observation resources, Wang et al.[11] studied the multiresource collaborative scheduling problem in space information network and established an integer linear programming optimization model.

In terms of algorithms, Hou [12] used centralized and hierarchical methods to deal with the problem of aerospace collaborative task planning, but the application type of tasks is relatively single, and it is difficult to handle complex tasks.Bai et al.[13] analyzed the characteristic differences in resource scheduling and execution observations of satellites and UAVs, and established a multi-platform co-evolutionary algorithm.Wu et al.[14]used the total utility value as the evaluation function of the task allocation method, and designed a high-weight priority allocation algorithm and a simulated annealing(SA) planning algorithm combined with a tabu table.At present, the main research focus in this field is multisatellite coordination [15] and UAV swarm coordination[16].Du et al.[17] proposed a data-driven parallel scheduling algorithm for the large-scale and time-consuming scheduling of multiple agile observation satellites.Wu et al.[18] studied the multi-satellite scheduling algorithm for emergency tasks and common tasks, and designed a hybrid ant colony optimization method based on local iteration.He et al.[19] designed an improved adaptive large neighborhood search algorithm, which continuously and iteratively optimizes the solution by designing destruction operators and repair operators.This research decomposes the multi-satellite scheduling problem into two sub-problems of task allocation plus single-satellite scheduling.The hierarchical planning idea is adopted to reduce the difficulty of solving, but it will also affect the quality of the solution to a certain extent.The problem of multi-satellite cooperative observation is studied using data-driven, evolutionary algorithms or precise solving methods to solve various new problems based on this problem [20-24].In addition, Zhao et al.[25] proposed a hybrid intelligent optimization algorithm for multi-UAV collaborative search.By combining differential evolution with tilt control technology, the hybrid optimization algorithm proposed in the research can effectively solve the problem of collaborative planning of multiple UAVs.The coordination problem of UAV clusters is explored,and the task allocation and path planning problems of UAV clusters are solved through evolutionary algorithms[26,27].

In addition, in the scheduling problem of heterogeneous machines, researchers have proposed models and methods related to the space-aeronautics collaborative scheduling problem.Yunusoglu et al.[28] studied the scheduling problem of multi-resource constraint-independent parallel machines, and proposed an accurate solution method based on constraint programming constraints.Nattaf et al.[29] constructed a constraint programming model for the scheduling problem of different workpiece families on parallel machines, and designed a heuristic algorithm, which verified the feasibility of modeling methods by experiment.Shahvari et al.[30] developed the mixed-integer linear programming (MILP)model into two integrated batch processing and scheduling stages.An efficient meta-heuristic algorithm based on tabu search is proposed.The algorithm has multi-level diversification and multi-tabu structure, moving back and forth between batch processing and scheduling stages.

Through the analysis of the above research, from the perspective of resource collaboration, although many researches have adopted a distributed framework to solve the complexity of space-aeronautics collaboration, there is a lack of information exchange between various levels,resulting in slow model solution optimization and nonideal planning results.From the perspective of processing tasks, most studies only consider a single task, and there is a lack of research on complex tasks composed of multiple task types.In this regard, this paper mainly studies the observation problems of complex tasks (point targets, regional targets, and coordinated targets) under coordinated observation of space-aeronautics resources(UAV and satellites).The main contributions and innovations are as follows:

(i) Based on operating characteristics of different platforms and the differences in requirements between different tasks, we propose a multi-layer interactive task planning framework to solve the problem.

(ii) In order to better model and design algorithms, we unify different task types by designing task preprocessing methods to process multi-type task sets into meta-task sets.At the same time, the problem is analyzed from the mathematical level, then the aerospace collaborative task planning model is constructed.

(iii) The hybrid genetic parallel tabu (HGPT) algorithm is devised in relation to the characteristics of “multilayer interaction ” in the framework.The algorithm mainly includes the upper, the middle, and the lower layers.The upper and middle layers of the algorithm are mainly designed to solve the problem of task allocation and task planning, and the lower level is mainly used to increase the degree of information sharing of different resources.Further, the algorithm integrates the SA selection method, parallel search mechanism, incremental constraint checking, and the neighborhood search operator.Finally, a simulation experiment is carried out to verify the performance of the algorithm.

2.Problem description

2.1 Definitions and assumptions

Complex tasks: It mainly refers to the set of all types of tasks collected by the platform within a certain period of time, which perform unified preprocessing, planning,coordination, and execution observations, as shown in Table 1.This paper mainly studies the complex task set consisting of point targets, regional targets and collaborative targets.

Table 1 Types of collaborative resource observation tasks

The complex task planning problem of coordinated space-aeronautics observation is defined as using satellite and UAV observation resources, according to the load characteristics, maneuverability, operation mode of each platform, etc., to deal with complex tasks through the relevant methods of collaborative planning.The planning goal is to reasonably allocate observation resources,determine the execution time of each task, and maximize the sum of the priorities of the scheduled tasks under constraints.

The space-aeronautics collaborative task planning problem has the characteristics of related non-deterministic polynominal (NP)-hard problems.In order to focus on the main problems and determine the boundary of the research problem to ensure reasonable collaborative task planning, this paper proposes the related assumptions to simplify the model as follows:

(i) The satellite can maintain a certain charging rate,and the battery is restored to the original for the next lap of work;

(ii) According to the existing inter-satellite link transmission scheme, the satellite downloads the observed data to the domestic ground station within 7 s [31], which can be regarded as a real-time transmission, and solid storage is no longer a constraint to be considered;

(iii) Satellite power consumption is proportional to the time of imaging and attitude maneuvering;

(iv) The flight mileage of the UAV platform is only related to the flight time;

(v) The data transmission constraints of UAVs are not considered.

2.2 Complex task preprocessing method

This paper studies the complex task set including point targets, regional targets and cooperative target tasks,according to the characteristics of each type of task, user require, and the loading of different types of resources,observation field of view, etc.We consider the selection of meshing methods to solve the task division problem.At the same time, to ensure the effect of task division, the following principles are designed:

(i) Grid division granularity principle.Target positioning accuracy, task solving time, and effective range of sensors need to be considered in the grid division granularity process.High positioning accuracy requires small grid granularity, but the corresponding solution time is long.The granularity is too large, although the solution time is short, the accuracy is not enough, and the platform with a low field of view cannot obtain the coverage of the grid.Therefore, we consider the use of the smallest load unit in the multi-platform for area decomposition.According to the comparison of the width of the smallest load unit of the UAV and the satellite platform,that is,d1>d2.Selectd2as the side length of the grid.The schematic process of grid division is shown in Fig.1.

Fig.1 Schematic diagram of meshing

(ii) Grid division trend principle.In order to ensure the consistency of grid maintenance for different platforms and to facilitate calculation, the search area can be divided by equal longitude and equal latitude.

(iii) Point target task clustering principle.Clustering is carried out on the basis of grid division, and there are two cases.The first case is that because the grid is divided according to the minimum coverage of resources, all tasks in a grid can be considered as a meta-task, as shown in ① and ② of Fig.2.The second case is that the smallest observation resource in this paper is UAV, which has the characteristics of high mobility.Suppose another point is closer to the current observed point target, but not in the same grid, and the UAV can observe another point target with only small adjustments (satellite resources have a large observation field of view and can simultaneously cover two closer distances’ point goals).Therefore based on this feature, we taked2as the diameter and the point target task as the center of the circle to get a circular area.If two point target tasks are in each other’s circular area, they can be regarded as a meta-task, as shown in③ of Fig.2.The remaining point target tasks are treated as a meta task, as shown in ④ of Fig.2.

Fig.2 Schematic diagram of point target clustering

3.Planning framework and model

3.1 Multi-layer interactive task planning framework

According to the working principle of the space-aeronautics coordinated implementation of the Earth observation task, this paper divides it into two parts: the task processing part and the task planning part.Task processing mainly processes complex tasks into a unified and standardized meta-task set based on the observational capabilities of each platform through preprocessing methods,and assigns tasks in the meta-task set to each platform according to certain rules.Task planning is used for each platform to receive the task set issued in the previous stage and arrange the task observation plan reasonably.

In this regard, we propose a multi-layer interactive task planning framework.As shown in Fig.3, the first stage is the task processing layer.That is, the set of tasks assigned by the user is initially screened to obtain complex tasks including regional target tasks, collaborative target tasks,and point target tasks.The framework uses preprocessing methods to obtain meta-tasks set, and then assign the set of meta-tasks to be observed to each platform.The second stage is the task planning layer, which arranges the planning scheme for the task set obtained by each platform through the designed algorithm.The third stage is the task coordination layer.The remaining resources,unobserved tasks, and the existing planning schemes of each platform are obtained through upper-layer calculations, and the unobserved tasks are rearranged according to heuristic rules.Then we collect the observation plans of each platform, the planned income value, and the set of unscheduled tasks to the task allocation stage.In the task allocation stage, the task grouping is adjusted according to the feedback information.An interactive optimization process is formed between the task processing layer, the task planning layer and the task coordination layer to find a satisfactory system observation benefit.In addition, this paper designs the HGPT algorithm based on the multilayer interactive task planning framework to solve this problem.

Fig.3 Complex task planning framework for coordinated space-aeronautics observation

3.2 Task planning decision model

The variables used in the model established in this paper are as follows.

The model established in this paper is as follows.

(i) Input.The model input is a set of meta-tasks generated after task preprocessing, which mainly includes task location information, the shortest duration of the platform to execute task, the task’s observation quality requirements, the task priority, the effective observation time of the task, and the sensor type and the resolution size of task matching.

(ii) Output.The model output is mainly the observation mark situation of thejth meta-task of theith task, the platform and resource type of the application, and the start and end observation time of the platform for the meta-task.The output model is represented by

(iii) Decision variable.One of the decision variables of the problem is whether thejth meta-task of theith task is observed by platformk.If it is observed, the variable is 1;otherwise, the variable is 0.The other is whether platformkis used.The variable is 1, if it is used; otherwise,the variable is 0, shown as

(iv) Objective function.It means maximizing the net income value.Part of it is the benefits obtained by observing the target.The other part is due to the cost of moving out the observation platform.If the resources are less, the cost is not calculated.Otherwise, the task revenue is not calculated, shown as

(v) Constraints are defined as follows:

Among the constraints, constraint (5) indicates the ratio of the number of planned meta-tasks to the total number of meta-tasks in any task.That is, the task coverage prob must be greater than the system set value prob.This paper sets prob=0.9.Constraint (6) indicates that any planned meta-task can only be executed by one platform.Constraint (7) indicates that for any platform, the period of time before and after the execution of the two metatasks should not be less than the conversion time required for the two meta-tasks, which is the attitude conversion time for the satellite platform, and the movement time for the UAV platform.Constraints (8) and (9) define that the observation window must be within the visible window range and the effective time window of the task.Constraint (10) defines that the observation time must be greater than the minimum continuous observation time.Constraint (11) requires that the sensor types be the same,and the spatial resolution must meet the requirements.Constraint (12) describes that the resources (power, solid storage, etc.) consumed by any platform to perform tasks in a cycle cannot exceed the maximum value of its platform resources.

4.HGPT algorithm

The complex tasks of aerospace cooperative observation have the characteristics of large scale, timeliness, and platform heterogeneity.As the number of tasks and platforms increases, the number of feasible solutions of the model increases exponentially.We conclude that this problem is a typical combinatorial optimization problem,which needs to be solved by a heuristic algorithm.Combining the above planning framework, an HGPT is designed.

4.1 HGPT algorithm conception and process

The HGPT algorithm is designed and improved on the basis of the genetic algorithm.Compared with the genetic algorithm, the HGPT algorithm possesses many comparative advantages.In solving problems, the HGPT algorithm can handle this similar “allocation plus planning”multi-stage problem.For algorithm efficiency, the HGPT algorithm adds the SA selection method, parallel search mechanism, and incremental constraint checking, and the neighborhood search operator is also designed according to the characteristics of the problem.Therefore, for such problems, the HGPT algorithm is better than the genetic algorithm in an all-round way.The content of the HGPT algorithm is as follows: task allocation, task planning,and task coordination.The upper layer uses the GAA to solve the task allocation plan of each platform, the middle layer uses the PT algorithm to solve the task observation sequence of each platform, and the results of the upper layer allocation are used as the input of the initial planning of each platform task in the middle layer.After that, the middle-level optimized results are used as the planning scheme for each platform, and the remaining resources, the remaining unobserved tasks, and the planning scheme of each platform are used as the input of the lower layer.The lower layer coordinates according to heuristic rules and gives the final planning scheme.Then all the obtained information is sent to the upper layer, and the upper layer redistributes tasks based on the feedback,thus forming a multi-layer interactive processing approach to obtain optimal solution, as shown in Fig.4.

Fig.4 HGPT algorithm flow

4.2 Task assignment-GAA

GAA is an intelligent optimization algorithm composed of genetic algorithm and SA algorithm, drawing on some ideas of the algorithm in [32].The algorithm generates a set of initial solutions (initial population) according to certain rules, and then obtains a set of new individuals through roulette selection, crossover, mutation, and other processes, and finally uses the SA mechanism for further selection.Since the SA algorithm calculates a single individual, this mechanism mainly enables the individuals in the population to be compared longitudinally, select one by one, and then form the next generation of the population.This process is repeated until the termination condition is met.

(i) Initial population generation

This paper adopts the method of constraint restriction,specifically considering that as the number of platforms and the number of tasks increase, the length of individual chromosomes becomes longer, and all chromosomes need to be checked for constraints, which will greatly increase the running time of the algorithm and reduce the timeliness of the algorithm.To this end, this paper increases the constraint limit when generating the initial solution to reduce the running time of the algorithm.As shown in Fig.5, each chromosome represents the observation platform used by the task.For a taskiin the setTof all metatasks, theith position of its corresponding chromosome takesthevaluewi.According tothe sensor type,resolutionvalue andrequiredplatformtypeconstraints inthe demand constraints of taski, a total ofniqualified platforms are selected from all platforms, and the valuewiof the chromosome at this position is one of theniset, and it also means that the observation platform used for taskiiswi, so that the mapping relationship between the chromosome and the search space point of the problem is established.Thus, according to the above scheme, multiple initial solution individuals are generated to form a set of initial task allocation schemes to form an initial population.

Fig.5 Initial solution generation method

(ii) Crossover and mutation

The crossover method adopted in this paper is designed to randomly select a segment of genes from the two chromosomes in the task allocation planSand recombine them.The mutation method is to perform this task by randomly replacing some nodes in theSset with a certain platform in the set of feasible platforms with a small probability.In addition, individuals who have not undergone crossover and mutation operations are directly added to the new task allocation plan set.

(iii) Selection

This paper first uses the roulette selection method in the genetic algorithm, and then uses the SA individual scheme to select again after the crossover and mutation of the population.In this process, only the individuals in the population are compared vertically, that is, each individual is compared with its parent.The purpose is to improve the overall performance of the new population and ensure that the population evolves in a better direction.There are two options for the SA selection process.One is that the offspring that is better than the parent is selected, and the other is that the offspring that is inferior to the parent but whose fitness value is close to the parent is likely to be selected.This selection method makes the comprehensive level of the newly generated offspring set higher than that of the parent.The ending criterion of the algorithm is that the temperature is equal to a certain set value, or the iteration process does not produce a better solution for multiple consecutive generations.

(iv) Algorithm flow

Step 1 Algorithm initialization.Set the input task observation platform numberm, and meta-task numbern.Platform and task related information are respectively

Step 2 Generate an initial population based on input information and initial solution generation rules.

Step 3 Enter the task planning layer to obtain the fitness of the individual population, mainly taking the sum of the priorities of the observed tasks as the fitness.However, if all tasks can be observed, the time required to complete all tasks is used as the fitness.

Step 4 Perform roulette selection, crossover and mutation operations.

Step 5 Enter the task planning layer and obtain the individual fitness calculation of populationA.

Step 6 The SA individual selection scheme performs individual selecting, generates a new population, and records the fitness of the new populationB.

Step 7 Determine whether the final annealing temperature is met or the termination condition is met.If yes,output the task allocation plan; if not, continue to reduce the temperature, increase the iteration algebra, and execute Step 4.

4.3 Task planning-PT algorithm

For large-scale, multi-platform task scheduling problems,the application of accurate solving algorithms to solve them is time-consuming and generally cannot give a better solution in a short and reasonable time.In order to overcome this shortcoming, this paper adopts the tabu search algorithm widely used in the combinatorial optimization problem to solve it in this stage of task planning.In the solution process, in order to ensure the efficiency of the solution and give full play to the computing power of the computer without affecting the quality of the solution, a parallel search mechanism is added on the basis of the tabu search algorithm.The mechanism is that after each platform gets the allocation plan, the algorithm allocates a thread for each platform to make task planning synchronously.This subsection first introduces the initial solution generation method of the algorithm, and then introduces specific contents such as operator construction and tabu table design.

(i) Initial solution

This paper introduces the nearest neighbor algorithm based on the greedy idea to generate the initial solution.When constructing the task observation sequence, the resources mainly start observation activities from a fixed starting point.The initial observation point of the satellite platform is the starting point of the first observation mission, and the initial observation point of the UAV platform is the target location of the airport.This paper sets (0,0) as the coordinates of the airport location.For satellites, when constructing the initial solution, only the task that consumes the least resources and meets the constraints in the relevant neighborhood of the current observation task is taken as the next observation task.For the UAV platform, the current observation task is used as the starting point, and the next task is to find the smallest Euclidean distance from the current position.The specific process is shown in Algorithm 1.

Algorithm 1 Initial solution generation algorithm Input: the set of meta-tasks to be observed, the total resource of the platform , and related known information;Output: feasible scheduling plan σ;Begin u0 pi Arrange the initial execution task of platform ;J ri pi do Update U to all unscheduled tasks;f Calculating the resource consumption of each task in U relative to the currently executed task (satellite: switching time,switching machine, etc., UAV: moving time, etc.), ; at the same time, checking the set of tasks that meet the constraints;unow f ∈F Ufea Finding out from the task u* that consumes the least platform resources to complete, adding it to the scheduling plan, and removing it from ;ri pi unow Ufea pi σ U Update the remaining resources of the platform and the current task , and check the number of remaining unfinished tasks in the set;U ≠∅∩u∗exists∩ri ≥0 while ( )End U

(ii) Neighborhood search and incremental feasibility check

For the satellite or UAV scheduling problem, the neighborhood will determine the execution status of a task (whether the observation task is scheduled or unscheduled) and execution order (in which visible window the task is executed in the satellite) of a task, and whether resources are used.This paper considers five kinds of neighborhood movement operators in the algorithm according to the characteristics of resources, and the specific usage is shown in Fig.6.

Fig.6 Neighborhood operators of the PT algorithm

In the task planning algorithm, the neighborhood solution is obtained by moving the neighborhood operator,and different neighborhood operators have a great influence on the quality of the neighborhood solution set obtained.According to the characteristics of the problem,the setting of the observation scene and the analysis of the satellite’s own performance, each satellite has two to three orbits that can completely see the scene area when performing the observation task.Therefore, in general,each meta task has multiple time window (that is, the satellite has an orbit that is visible to multiple missions).Therefore, in order to study how to match the satellite’s orbit with the mission to ensure higher system revenue,we select a task randomly on the basis of the current scheme and select a time window in the collection of the task time windows, which is defined as an operator as shown in Fig.6(a).

In addition, considering the task may not be observed by satellites, a null virtual window is added.For the UAV task planning problem, operators are designed as shown in Fig.6(b)-Fig.6(e), and one operator is randomly selected each time to perform neighborhood operations.Meanwhile, according to the characteristics of the problem, this paper knows that in the neighborhood search process, only the transformed neighborhood solution needs to be checked for feasibility, that is, there is no need to operate on the part of the solution that has not changed.This can greatly reduce the execution time of the algorithm and improve the efficiency of the algorithm.

(iii) Tabu list

The purpose of the tabu table is to prevent solution shock.In this paper, the most commonly used fixedlength tabu list is used, and mobile operations are selected as the tabu object.For satellite planning, {task_number, position_now, position_next} is used for recording,which respectively represent the selected task number,the current lap of the task, and the lap of the next step of the task.For UAV planning, the two-tuple {Add_edge,Delete_edge} is used for recording, which are represented as the set of added edges and the set of deleted edges, respectively.For example, when performing an insert operation, delete three edges, add three edges, use the add edge set, and delete edge set to save.Whether an operation is tabu or not, the rules are as follows: calculating the number of adding edges in the set of deleted edges, and calculating the number of adding edges in the set of deleted edges.If the sum of the two is greater than a certain threshold, the operation is considered to be tabu.If an operation results in a better solution than the historical optimal solution, the amnesty rule is executed and no tabu are made.

(iv) Algorithm flow

Step 1 Algorithm initialization: input the population list and all the information of the task and platform.

Step 2 Extract an individual from the population in order, and generate a set of tasks to be performed by each platform.

Step 3 According to the nearest neighbor algorithm based on the greedy strategy, the initial solution of each platform is obtained.

Step 4 Execute the PT algorithm, get the proposed planning scheme of each platform, enter the task coordination layer, and get the final planning scheme.

Step 5 Determine whether all individuals in the population have completed the planning.If not, return to Step 2; otherwise, execute Step 6.

Step 6 The algorithm ends and returns to the task distribution layer.

4.4 Task coordination-heuristic rules

Although the task planning algorithm can solve a satisfactory planning scheme, there are still some platforms with more remaining resources and uneven matching between resources and tasks.In order to increase the synergy between the platforms, improve the degree of information exchange between the platforms, and make the overall benefit of the system close to the optimal.This paper designs corresponding heuristic rules: (i) the principle of the highest overall priority; (ii) the principle of the least number of remaining tasks; (iii) the principle of maximizing platform resource utilization.The importance of each rule decreases in order.The specific steps are as follows.

Step 1 Sort out the unplanned task set Ut and the resource remaining platform set Rr, and sort the tasks in the Ut set in order of priority.

Step 2 Carry out constraint checks one by one in the order of priority to obtain a set of platforms that meet the conditions Rr′.

Step 3 If the platform set R r′is empty, execute Step 4.Otherwise, get the platform set Rrsthat matches the task of uti, and find the platform in the Rrsset with the least remaining resources after the task is scheduled.That is, a platform with nearly saturated resource utilization, assign the task utito this platform.

Step 4 Check whether the Ut set becomes empty.If so, go to Step 5; otherwise, go to Step 2.

Step 5 Under the premise of ensuring that the priority is not reduced, the tasks are exchanged so that as many tasks as possible are arranged in the task sequence.

Step 6 Check whether the coverage of the area task

meets the requirements, and the algorithm ends.

5.Computational experiments

5.1 Experimental design

In this subsection, simulation experiments are used to verifythe solutionperformanceofthe algorithm.In this experiment,therearea total of50×50 km2small-scale scenes, 100×100 km2medium-scale scenes, and 150×150 km2large-scale scenes.Fig.7 shows the distribution of various types of tasks in the initial small-scale scenario, including point targets, regional targets, and collaborative targets.Fig.7(b) is the distribution of meta-tasks obtained by the task preprocessing method.This method follows the three principles proposed in Subsection 2.2,namely, dividing regional targets according to minimum resource coverage and grid trend, decomposing and coordinating targets according to task needs, and integrating point targets according to clustering rules.Due to limited space, medium-scale and large-scale scenarios are not included.

Fig.7 Small-scale scenario task distribution

In addition, the relevant parameters of observation resources are listed in Table 2.Among them, the initial task number set and the meta-task combination list are the number of point target tasks, the number of regional target tasks, and the number of collaborative target tasks under different scales.At the same time, in order to make the experimental results have better accuracy and stability, the profit value of each experiment takes the mean value of the ten simulation optimization results.According to the background of the problem, two resource platforms, satellite and UAV, are set up in the experiment.The task types included in the complex task set include target tasks, regional target tasks, and collaborative target tasks.The operating environment is Java 15, Inter(R)Core (TM)i5-10210U CPU@2.11 GHz, RAM16 GB.

Table 2 Relevant parameters of task planning resources

5.2 HGPT algorithm validity verification

The main purpose of this subsection is to verify the effectiveness of the algorithm.In the calculation process, the population size of the GAA is 20, the number of iterations is set to 800, 1 000, and 1 200.The crossover rate and the mutation rate are 0.8 and 0.2 respectively, the initial temperature temp0=100, and the termination temperature temp∞=1e-2, the cooling coefficient ∂ = 0.98, the maximum number of iterations in the parallel taboo algorithm is set to 2 500, and the taboo list lengths for satellite and UAV planning are 20 and 40, respectively.The simulation sets up three task scenarios, sets the number of tasks in each scenario, and calculates the number of metatasks in different scenarios through complex task preprocessing methods, as shown in Table 3.According to the algorithm planning results of the small-scale scenario in Fig.8, in the process of performing the observation task according to the planning scheme, there is no “resource review” or “sub-cycle” for all resources.For the situation where multiple meta-tasks are relatively close in a certain area, the algorithm will select UAV to observe, so we can ensure that the observation of more diverse tasks is completed as much as possible while consuming less resources.In addition, in Fig.8, we can clearly see that there are still a small number of unscheduled meta-tasks.On the one hand, since the distance is too far, it is not worth consuming too much resources.On the other hand,although the distance is relatively close, the task priority is low and the observation benefit is not high.From the calculation result statistics of the algorithm in Table 4, it can be seen that in a small-scale scenario, the task completion rate and the algorithm return rate are both above 90%.In middle-scale and large-scale scenarios, the task completion rate and algorithm profit rate are relatively low, mainly because as the scenario expands, resource observation consumes too much and the completion rate decreases, but both reach more than 80%.This paper calculates reasonable results through modeling and algorithm, which shows the applicability and effectiveness of the framework, model and algorithm of this paper.

Table 3 Configuration and completion of tasks in different scenarios

Fig.8 Algorithm running result

5.3 Comparison and analysis of algorithm performance

Since the research problem in this paper is an application problem in the direction of resource scheduling, there is no general Benchmark data set, and there is also a lack of general algorithms for solution.However, in order to analyze the performance of the HGPT algorithm, this paper designs a series of comparison algorithms for comparison.Considering that the HGPT algorithm is designed and constructed on the basis of the genetic algorithm, in order to ensure that the comparison algorithm can map the value of the HGPT algorithm, the comparison algorithm in this paper is also constructed on the basis of the genetic algorithm.

The comparison algorithm mainly include the basic HGPT (BHGPT) algorithm, two-stage HGPT (THGPT)algorithm, hybrid genetic tabu (HGT) algorithm, genetic PT (GPT) algorithm and multi-level nested genetic(MNG) algorithm.Among them, the BHGPT algorithm is the HGPT algorithm that lacks the initial solution generation algorithm, the THGPT algorithm is the HGPT algorithm that lacks the task coordination phase, the HGT algorithm is the HGPT algorithm that lacks the parallel mechanism, the GPT is the HGPT algorithm that lacks the SA strategy, and the MNG algorithm is a similar version of the HGPT algorithm, in which the PT process in the HGPT algorithm is replaced by using the genetic algorithm.The relevant operating parameters of the comparison algorithm remain unchanged, as shown in Fig.9.

Fig.9 Calculation results of different algorithms (small scale)

From the calculation results, the distribution and planning results of the complex task set are listed in Table 4.

Table 4 Algorithm efficiency values in different scenarios

(i) Compared with the THGPT and GPT algorithms,the algorithm in this paper increases the task coordination layer and SA mechanism, and the number of tasks completed and the profit value have been improved, indicating that the task coordination layer has achieved the purpose of improving the degree of information sharing between platforms, and the SA selection mechanism also played a role.

(ii) Compared with the HGT algorithm, the running time of the algorithm in this paper is only about a quarter of that of the HGT algorithm.At the same time, the number of iterations of the PT search algorithm is set to 3 500 generations in the BHGPT algorithm to ensure that the task planning process can converge to a stable value, but this makes the search time of the algorithm increase compared to the algorithm in this paper.It can be concluded that the HGPT algorithm integrates the parallel search mechanism and the initial solution generation method,which can effectively reduce the algorithm convergence time and enhance the stability of the algorithm iterative convergence process.

(iii) In the MNG algorithm, the use of group optimization algorithm to solve the task planning layer can guarantee the quality of its output, but its time consumption will be 8 to 9 times that of the HGPT algorithm.The HGPT algorithm designed in this paper uses local solutions to process the task planning layer, which can reduce the algorithm’s solution time and ensure the algorithm’s solution quality.In summary, the algorithm in this paper has been verified in terms of accuracy and timeliness,which is valuable in practical application.

6.Conclusions

Aiming at the complex task planning problem of aerospace cooperative observation, this paper has carried out framework, model, algorithm research and simulation experiments.

By combining multiple task types and multiple platforms and considering the working process of each platform, a multi-layer interactive task planning framework is designed, and a preprocessing method for complex tasks is proposed.

The several sub-problems formed in the task observation of each platform are unified into a mixed integer programming model to meet the needs of solving the problem of different types of tasks for collaborative observation of different resources.

Based on the framework and model, an HGPT algorithm is designed, which can efficiently and flexibly solve the complex task planning problem of aerospace collaborative observation.The solution speed and solution quality of the algorithm are far greater than those of general algorithms.

In future research, there will be more than two platforms such as satellites and UAVs, including multiple mission types such as point target missions, regional target missions, and coordinated target missions.How to improve the existing models and algorithms so that they can meet the needs of actual problems, and how to improve the timeliness of algorithms will also be the focus of future research.