WU Jian,CHEN Yuning,HE Yongming,XING Lining,and HU Yangrui

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

Abstract:How to make use of limited onboard resources for complex and heavy space tasks has attracted much attention.With the continuous improvement on satellite payload capacity and the increasing complexity of observation requirements,the importance of satellite autonomous task scheduling research has gradually increased.This article first gives the problem description and mathematical model for the satellite autonomous task scheduling and then follows the steps of “satellite autonomous task scheduling,centralized autonomous collaborative task scheduling architecture,distributed autonomous collaborative task scheduling architecture,solution algorithm".Finally,facing the complex and changeable environment situation,this article proposes the future direction of satellite autonomous task scheduling.

Keywords:satellite autonomous task scheduling,centralized architecture,distributed architecture.

1.Introduction

As an advanced space-based information acquisition tool,earth observation satellites have played a vital role in the fields of industry,national defense,and livelihood [1-4].The continuous improvement of ability and quantity speeds up the popularization of earth observation satellites,which lead to increasingly higher demand for reliability,timeliness and image quality of satellites.The traditional task scheduling mode is that the ground control centers receive the users ’ requirements,and the task scheduling plan is obtained through optimization method,which meets the operational constraints satellites.Then the plan is compiled into instruction that satellites can execute,and released through the satellite-to-ground link[5].The satellites work based on these instructions,collect the images and downlink them to the ground stations[6].Obviously,the efficiency of satellites in the traditional mode is affected by many factors including the organization process and computing capability of the ground control centers,the frequency of satellite measurement and control links,the accuracy of satellite capability prediction,and the work environment (cloud thickness and air quality).On the other hand,due to the continuous improvement of timeliness and reliability for images,the drawbacks of the traditional task scheduling mode have gradually emerged,which are as follows [7]:

(i) Fail to respond to emergencies in time.In the traditional mode,the instructions are released through the satellite-to-ground link,which ranges from one day to several days.The satellites are offline while executing these instructions.Once an emergency tasks arrive,the established plan is adjusted.This period is usually relatively long,and it is likely that the emergency tasks cannot be responded in time.

(ii) Depend on the ground control centers strongly.The traditional satellite task scheduling mode is time-stamped.The ground control centers need to consider the operational constraints of each satellite when making the plan.As the number and constraints increase,the traditional task scheduling mode not only increases the workload of the ground control centers,but also increases the risk of errors in the satellite control process.

(iii) The reliability of the satellites cannot be guaranteed.Due to the limitation of communication arc,the ground control centers cannot obtain the satellite resource status in real time,the utilization of onboard resources is simulated based on the previous test data.In order to ensure the safety and reliability of the satellite,the design of the resource model is very conservative.As a result,some tasks are abandoned that could have been completed,which affect the work efficiency of the satellite.

The above-mentioned factors together cause the actual output efficiency of satellites to be low under the traditional mode.Therefore,both industry and academia hope that satellites can transform from simple instructions executors to intelligent agents,which can complete complex tasks and reduce the pressure of the ground control centers.

On the other hand,the improvement of satellite hardware has enhanced the ability of satellites to deal with complex emergency tasks,and provide favorable conditions for the development of onboard autonomous systems [8-10].With the increased complexity for future space missions,autonomous systems will have more competences than before.In the task Deep Space-1(DS-1),the first autonomous system Remote Agent (RA) [11,12]was developed and verified on Earth Observation-1 (EO-1)[6,13,14].The U.S.Air Force has designed Autonomous Sciencecraft Constellation (ASC) to control the TechSat-21 satellites,including burton system,continuous activity scheduling planning execution and replanning(CASPER) system and multi-agent cluster management system [15,16].

Autonomous task scheduling technology needs to be implemented in a system with high overall autonomy.It is a complicated system engineering to make satellites have autonomy as a whole,which includes a series of scientific problems [7,8,17].This article starts from the mathematical model of satellite autonomous task scheduling,and focuses on the satellite autonomous task scheduling method,multi-satellites autonomous task scheduling architecture,solution algorithm and so on,and points out the future research direction.

2.Problem description and modeling method

Autonomous task scheduling is the “brain ” of the autonomous system.Its core idea is to autonomously generate effective action sequences for the onboard dynamic environment and meet the constraints.

2.1 Task type

Satellite autonomous task scheduling is divided into imaging task scheduling and data transmission task scheduling,and they are generally independent.However,in order to further improve the execution efficiency of imaging task and data transmission task,the integrated task scheduling combining imaging task and data transmission task has gradually attracted scholars’ attention.

2.1.1 Imaging task

Imaging task scheduling is the process of obtaining the maximum imaging task benefits,which is to reasonably arrange satellites,sensors,data storage,electricity and other load resources,and effectively eliminate the conflict between tasks [18-20].In autonomous situation,the imaging task is highly time-effective and multi-batch.At the same time,the sources of task are diversified,including the task stored in advance,the task temporarily uploaded from the ground,the task generated in operation and the task that needs to be rescheduled.The data structure and types of these tasks are not necessarily the same.For example,the emergency task proposed by user only contain the geographic location information and deadline,which requires the satellite autonomous task scheduling system to have the ability to process data,schedule task and generate instructions.

2.1.2 Data transmission task

The data transmission task is to transmit the data acquired by satellites to ground stations through satellite-to-ground link [21-23].Data can only be transmitted if the satellites are only visible to the ground stations.In order to maximize the amount of data,it is necessary to schedule the visible time window between satellites and ground stations.Originally,the ground centers are responsible for making the data transmission plan and coordinating the measurement and control center and the ground station.In autonomous situations,the satellites independently complete the data transmission task.Therefore,the entire process is changed.

2.1.3 Integrated task

The imaging task and the data transmission task are complementary and closely related.The purpose of the imaging task is to transmit data to the ground stations through the satellite-to-ground link,and the data transmission task closely depends on the performance of the imaging task.Usually imaging tasks and data transmission tasks are considered independently,but with the continuous development of onboard storage devices and satellites autonomous technology,as well as the actual request for space-ground integration,more and more attention has been paid to the integrated task combining the imaging task and the data transmission task [24-26].In conclusion,the autonomous scheduling of the imaging task,the data transmission task,and the integrated task is different from the traditional mode in data processing,task scheduling,and instruction generation,which puts forward higher request for the design of onboard autonomous task scheduling system.

2.2 Modeling method

2.2.1 Mixed integer programming model

Since the 1990s,the U.S.Air Force Institute of Technology had begun to study the scheduling problems of the Air Force Satellite Control Network (AFSCN) through the mixed-integer programming model [21].In China,He from the National University of Defense Technology was the first to use a mixed integer programming model to solve the earth observation satellite scheduling problem[27].A mixed integer programming model was proposed in [28],in which the continuous observation angle of agile satellites was decomposed into three angles.A twostage mixed integer linear programming model was proposed by Liu et al.,however,the complexity of this method is too high to solve the problem involving more than 15 tasks [29].In order to improve the total time of satellite observation,Abramson et al.described the multisatellites task scheduling problem as a mixed integer programming model,and the classical algorithms were proposed to solve it [30].She et al.investigated a new Agile Earth Observation Satellite (AEOS) mission planning algorithm [31].This new developed algorithm is based on Modified Mixed-Integer Linear Programming (MILP)approach,which takes the minimum slew angle and highest priority criterion.He et al.established a mixed integer linear programming model for the scheduling of multi-satellites [32].This model avoided enumerating the combinations of all visible time windows and has lower complexity.At the same time,The electricity constraint with time dependence was considered in the model,which was more in line with the actual situation [32].

However,the mixed integer programming model has low extensibility,and has more accurate requirements for the expression of model elements.Due to the high complexity of satellite autonomous task scheduling,it is difficult to use the mixed integer programming model to solve large-scale problems within an acceptable time period.Therefore,few scholars described the satellite autonomous task scheduling problem as an integer programming model.

2.2.2 Constraint satisfaction model

The function expression of the decision variable is used as constraint in the constraint satisfaction model,which plays an important role in the simplification and description of large-scale multi-constraints problems [2].For the satellite autonomous task scheduling problem,Liu et al.established a problem model based on time line constraint network after analyzing the main constraints [33].Ackermann et al.considered the visible time window constraints and established a constraint satisfaction model for multiple remote satellites [34].Song et al.established the constraint satisfaction model for the problem of the onboard autonomous task under emergency situation,and the number and urgency degree of tasks were taken into account [35].A constraint satisfaction model for multisatellite task scheduling problem was established from the perspective of task priority and the equipment constraint,but lacked storage capacity [36,37].

On the whole,the constraint satisfaction model can design relevant constraints according to the specific scenarios of the satellite autonomous task scheduling problem,these constraints are easy to describe,and have strong high extensibility.

2.2.3 Classic problem model

The classical problem models that are widely used include vehicle routing problem (VRP),job shop scheduling problem (JSP),knapsack problem (KP),and assignment problem models.In terms of the satellite autonomous task scheduling problem,Vasquez et al.abstracted it as a KP model and solved it [38].Wang et al.established a mathematical model based on dynamic topology loop free digraph [39].Bai et al.established a minimum path scheduling model for the complex tasks scheduling problem [40].In terms of the multi-satellite autonomous task scheduling problem,it was transformed into VRP with a time window.The satellites were regarded as multiple vehicles in the VRP,imaging task and data transmission task were regarded as pickup and delivery,the transition time between tasks was regarded as the travel time from one node to another node,the earliest and latest execution time corresponds to the earliest and the latest access time of the node.Other scholars regarded multiple satellites and multiple ground stations as two types of machines for JSP,and the imaging task and the data transmission task were regarded as two operations,and the transition time between the imaging task and the data transmission task was regarded as the time from one operation to another [41,42].The onboard autonomous task scheduling problem was regarded as the dynamic KP[43].The satellites were regarded as a knapsack with limited loading capacity,and observation requirements were regarded as goods with different weights and values.These goods arrived with time.Once the goods were loaded into the backpack,they cannot be taken out and thrown away.If they were refused to be loaded,they would be lost.The goal was to maximize the total value of goods in this backpack [43].These classic problem models are combinatorial optimization problems with a wide range of applications,and they are widely studied in the fields of operations research and artificial intelligence.At present,there are many methods to solve these problems,which provides a good way for satellite autonomous task scheduling.

The satellite task scheduling model has not always been paid enough attention.In fact,the scheduling model is the key factor that affects the coding,neighborhood structure,and search space of the scheduling algorithm.Therefore,in the future research,it is necessary to design a scientific scheduling model to reduce the size of the problem,reduce the coding complexity and improve the efficiency of the algorithm.

3.Satellite autonomous task scheduling method

According to [8],the autonomous task scheduling method was divided into response-based autonomous task scheduling method and rolling scheduling method with different diving mechanisms.

3.1 Task scheduling method based on response

There are two sources of autonomous response.The first is from autonomous perception.After receiving the information,the satellite will carry out different degrees of autonomous response based on the mission requirements.Taking cloud perception as an example,Beaumet et al.used cloud detector to assess meteorological conditions over the target in real time,calculated the appropriate imaging angle for the target,and guided the agile satellite to orbit maneuvers [44].The second is from the emergency tasks.In order to avoid the impact of priority scheduling of emergency tasks on the total profit of tasks,a satellite imaging scheduling method was proposed to optimize the response time of emergency tasks while considering the total profit of the tasks [45].Li et al.optimized the global delay time caused by the insertion of emergency tasks,and realized the effective scheduling of satellite autonomous emergency tasks [46].

3.2 Rolling scheduling method

The rolling scheduling method (see Fig.1) not only provides the opportunity to adjust the plan periodically,but also reduces the scale of the onboard one-time decision-making problem,which shows good applicability under the limited decision-making ability of agile satellites.The diving mechanism can be further divided into time-driven,event-driven and hybrid driven modes [47].Liu et al.proposed a rolling scheduling method based on task axis,and designed an autonomous task scheduling framework including scheduling,decision,execution and information feedback [33].For high-dynamic and time-efficient observation tasks such as disaster monitoring and early warning,Xi et al.constructed a dynamic rolling rescheduling framework based on the time window [48].

Fig.1 Rolling scheduling method

4.Multi-satellites autonomous collaborative task scheduling architecture

With the development of space activities,users put forward more stringent requirements for the real-time observation task,the extensibility of observation space and the dynamic observation target.Due to the influence of orbit,observation payload and observation target characteristics,a satellite is difficult to meet the increasingly complex observation requirements,and multi-satellites must be used to complete more complex tasks.

Compared with a satellite,multi-satellites have many advantages: (i) it can improve the efficiency of earth observation in time and space;(ii) multi-satellites with different payloads can achieve more complete functions;(iii) the robustness of multi-satellites is stronger than a satellite.

Meanwhile,multi-satellites autonomous cooperative tasks scheduling presents new characteristics and difficulties.

(i) More objective functions and constraints result in higher model complexity.

Agile satellite task scheduling is a complex combinatorial optimization problem,which has been proved to be NP-hard [1].Accurate description of objective function and constraints is the key to solve the problem of multisatellites autonomous cooperative task scheduling.In terms of objective function,in addition to the common objective functions such as profit,quantity and duration of scheduled tasks,there is also a special objective function of communication gap between satellites [49].In terms of constraints,in addition to the common constraints such as time window,resource capacity (electricity,storage) and task logic,there are some special constraints such as behavior synchronization constraint,communication constraint and so on.

Behavior synchronous constraint: Different tasks need different strategies for providing behavior synchronization,which means that certain behaviors on different satellites need to be done at the same time.In this case,the data observing behavior for each satellite needs to be correlated in time and bandwidth with other satellite for further signal processing,expressed by

Communication constraint: For the distributed architecture,the communication channels could be jammed due to the bandwidth limitation.The constraint on communication can be expressed by

(ii) It is difficult to design coordinated control strategy.

Different from the traditional periodic scheduling mode,autonomous tasks scheduling is an online mode without pre-plan.When faced with large-scale dynamic emergency tasks,if the long-term scheduling mode is adopted,not only the timeliness requirements of emergency tasks cannot be met,but also it is difficult to obtain a feasible solution in a short time depending on the limited computing capacity of the satellite.If the period is too short,a large number of time windows will be frequently occupied,which leads to a large number of tasks that cannot be executed.It is particularly important to balance emergency response speed and solution quality,grasp scheduling time,and control the input scale in the scheduling process.

(iii) The order of onboard observation tasks is more uncertain and the solution space is larger.

The process of satellite tasks is complicated,including orientation to the sun,attitude maneuvering,ground observation,and data return.There are complex sequence restrictions between these actions,which are flexible coupling and need to reduce adjustments to achieve smaller resource consumption.Multi-satellites autonomous coordination also includes the process of task allocation,which makes scheduling more difficult and the solution space is larger.

As shown in Fig.2 and Fig.3,according to the different communication modes between satellites,the multisatellites autonomous collaborative task scheduling architecture is divided into the centralized architecture and the distributed architecture.

Fig.2 Centralized architecture

Fig.3 Distributed architecture

4.1 Centralized architecture

As shown in Fig.4,a mother satellite (MS) is usually used to replace the traditional ground control center in the centralized architecture.The MS is responsible for receiving tasks from ground control center and determining the task scheduling method [50-52].The tasks are allocated to the corresponding daughter satellites (DS)through the inter-satellite communication link.In the aeronautical source environment,a spacecraft in the satellite formation was used as the MS,and the operation of the companion spacecraft is scheduled through inter-satellite communication,the others were scheduled through inter-satellite communication link [53,54].Truszkowski et al.proposed a completely centralized architecture scenario with high-orbit satellites as the MS and low-orbit satellites as the DS [55].The high-orbit satellites are equipped with onboard computers,which are responsible for the management of the entire constellation and interacted with the ground control center.The low-orbit satellites are relatively simple.They receive target tasks from high-orbit satellites and send their own resource status information to high-orbit satellites [55].An onboard autonomous task rescheduling system for multi-satellites system was proposed in emergency situations.Zheng et al.used multi-objective hybrid dynamic mutation genetic algorithm (MO-HDMGA) combined with rescheduling techniques as the core algorithm.The cyclically re-planning method (CRM) and the near real-time re-planning method (NRRM) are developed to meet different task requirements.In order to verify the effectiveness of the proposed method,three emergency experiment scenarios including eight satellites and the normal scenario are designed.Scenario A shows that one or more satellites are unable to work,Scenario B shows partial failure of satellite payload,and Scenario C shows partial failure of communication equipment between satellites.Some conclusions are obtained.(i) For each emergency scenario,the average profit of NRRM is at least 3.91% more than the CRM.(ii) For each emergency scenario,the NRRM costs 16.45% more time than the CRM,but for the normal scenario,the NRRM costs 26.63% less time than the CRM [56].Aiming at the heterogeneous low-orbit small satellite network,Qin et al.adopted a fully centralized architecture and proposed a resource-balanced task allocation algorithm based on deadline [57].The MS maintained the latest status of each MS,and selected candidate to execute the tasks based on the remaining resources [57].The centralized architecture generally consists of the following modules [56].

Fig.4 Main functional modules of centralized architecture [56]

(i) General planner module

The general planner module is an important part of centralized architecture.This module is responsible for receiving high-level tasks from the ground stations,decomposing the tasks into multiple sub-tasks,generating an initial plan and allocating to the MS through the inter-satellite link.

(ii) Plan executor and status monitor module

This module contains two sub-modules,which is shown in Fig.5.The plan executor module receives instructions from the MS,and each DS executes the corresponding tasks independently.Before executing tasks,DS needs to start the status monitor module to check whether its own resources can meet the tasks requirements.If not,the module sends the rescheduling request to the decision-maker module.After completing the corresponding task,the DS wait to receive the next instruction from the master satellite.

Fig.5 Plan executor and status monitor module

(iii) Decision-make module

In the harsh space environment,the satellites are faced with various emergencies.For example,the satellites are destroyed by comets and asteroids,and part failures of payloads due to long term,wire aging and other unknown reasons.Once the DS cannot complete the task,the decision-maker module receives a request for rescheduling which is shown in Fig.6.The MS quickly diagnoses the fault and transmits the information to the re-scheduler module.

Fig.6 Decision-maker module

(iv) Re-scheduler module

The information transmitted by the decision-maker module can trigger the re-scheduler module.The module needs to further determine whether to consider the initial plan.In some cases,the goal can be achieved by modifying the initial plan through some operations such as inserting or deleting.Otherwise,the solution algorithm is activated to allocate resources for the tasks to generate a new plan.

The centralized architecture has the conditions to obtain the global optimum under the unified management of the MS,but the result of the plan depends too much on the computing capability of the MS and the inter satellite communication link.In general,the centralized architecture shows good efficiency in small-scale scenarios,but it has bad performance in large-scale scenarios.In order to improve the efficiency of the centralized architecture in large-scale scenario,some scholars reduce the scale of problems through layered mechanism and modular mechanism.Yao et al.used the fuzzy neural network to construct the task flow autonomous scheduling decision system,in the experiment,the system realized the autonomous scheduling of tasks,and effectively improved the autonomous and intelligent level of satellite software based on the real-time monitoring data [58].The disadvantage is that the training set and the task size are relatively small [58].Wu et al.transformed the multisatellite multi-orbit scheduling problem into single-satellite single-orbit scheduling problem by the clique partition clustering algorithm and the heuristic insertion clustering algorithm.The proposed method was verified in 100,200,300 and 400 targets respectively.The results showed that the method can effectively improve the profit of tasks,and the larger the target scale is,and the more obvious the improvement advantage is,and the highest is 4.26% [59].

4.2 Distributed architecture

In order to cope with large-scale tasks and complex communication environment,the distributed architecture has attracted more and more attention.The distributed architecture is to abstract the basic conditions and constraints of different satellites,and process each satellite into an autonomous agent to form a multi-agent system.Different from the centralized architecture,the distributed architecture allocates tasks through continuous negotiation among satellites,which is shown in Fig.7.The advantages of distributed architecture are as follows:(i) robustness,which greatly reduces the dependence on the MS;(ii) parallelism,which reduces the problem scale and response level;(iii) practicability,which improves the rationality of resource allocation and enhance the scalability of scheduling system.Bonnet et al.first defined the distributed architecture,that is,a system composed of multiple satellites in a collaborative way [60].Damiani et al.regarded the distributed satellite system as a general term of the following configurations,including satellite formation,satellite cluster and separated spacecraft module [61].

Fig.7 Main functional modules of distributed architecture [49]

The main difference between the centralized architecture and the distributed architecture is the way of task allocation.There are two main methods for multi-satellites task allocation under the distributed architecture.The first is the hierarchical structure.The coarse-grained scheduling tasks are assigned to each satellite through hierarchical negotiation,the neighborhood knowledge is used to repair in the negotiation process.Based on the characteristics of multi-agents system,Schetter et al.established several common structures and information flow mechanism of inter satellite negotiation [62].

The second is the contract network.The contract network was proposed by Smith and Davis in the 1970s[63].It is a negotiation mechanism to allocate tasks among multi-agents [64].The contract network draws on the process of “bidding ” in the market,and it includes tender,bidder and winner.Agogino et al.established a multi-agents system for small satellite clusters,when the users submitted task requirements,each agent used the specific cost function to calculate the bidding value,and allocated tasks [65].In order to improve the efficiency of multi-satellites,Cheng et al.expanded the traditional contract network to manage the earth observation satellites,and calculated the bidding value based on the remaining resources including electricity and storage [66].

Although the distributed architecture has good robustness,parallelism and execution ability,its difficulties and shortcomings are obvious.

The distributed architecture lacks MS with unified management.Each satellite cannot evaluate global situation according to its own situation,which makes it difficult to obtain the global optimal solution.To solve this problem,Yang et al.established the multi-agents model for multi-satellites autonomous cooperative task scheduling,and introduced a dynamic centralized distributed architecture [67],in which the dynamic MS was used instead of the fixed MS,the experimental results show that when the number of tasks exceeds 250,the communication times of the improved contract network will be reduced to 85% of the previous.From the reliability comparison experiment,it can be seen that when facing the damage of the MS,the dynamic contract network has obvious improvement in the profit and response compared with the traditional contract network.The proposed dynamic contract network can increase the total profit to 117.8% of the traditional contract network,and the response rate of emergency tasks is increased by about 50% [67].Zhang et al.divided the distributed satellites task scheduling into two levels: constellation task scheduling and satellite autonomous controlling,and then a highly reliable centralized-distributed architecture was proposed,including global control layer,communication layer,local-scheduler layer,and monitor and execution layer.The results show that the speed of this method is equal to the greedy algorithm [68].Zheng et al.proposed a hybrid solution framework combining the local constraint satisfaction module and the global distribution optimization module.In the local constraint satisfaction module,each DS used the local search heuristic algorithm to quickly generate a satellite observation task sequence that meets the local constraint in a short time.In the global distribution optimization module,all satellites can share their own observation task sequence,and finally generate a global feasible solution.They designed six,eight,ten and twelve satellites to verify the proposed method.The main results are as follows:

(i) For small-scale and short period tasks,the computing time of centralized architecture is shorter than the distributed architecture;for large-scale and long period tasks,the computing time of distributed architecture is shorter than the centralized architecture [49].

(ii) The centralized architecture can achieve better results than the distributed architecture,but the distributed architecture can generate a feasible solution without violating constraints in a short time.

(iii) The distributed architecture is greatly influenced by the negotiation mechanism and algorithm.The basis of multi-satellites autonomous task collaborative scheduling is to determine which satellite the task is arranged on.The allocation mechanism and algorithm determine the final task sequence.An unreasonable task allocation method may lead to that the task which should be executed cannot be arranged.

5.Satellite autonomous task scheduling algorithm

5.1 Heuristic algorithm

Due to the complex constraints and dynamic environment,the heuristic algorithm cannot find the optimal solution.However,it is fast and easy to get the feasible solution,which has basically met the requirements for the actual scheduling system.

In satellite autonomous task scheduling,Chien et al.designed a local search algorithm based on iterative repair for NASA’s EO-1 [69].The algorithm first generated an original plan that may violate constraints,and tried to solve a conflict at a time until all conflicts were solved [69].To solve the autonomous task scheduling problem for agile satellites,Liu et al.proposed a rolling rule heuristic algorithm combining the random mechanism and roulette,and each iteration included the construction phase and the local search phase [7].Xue et al.proposed a two-stage scheduling algorithm combining heuristic search and improved the program evaluation and review technique (PERT),which can quickly and effectively solve the autonomous satellite task scheduling problem under the emergency situation [70].Wang et al.designed two heuristic algorithms for dynamic task scheduling under emergency situation [71].The first heuristic algorithm arranged new tasks by inserting or deleting,and repeating the operations from low priority to high priority.The second heuristic algorithm took some steps including direct insert,shift insert,delete insert and insert deleted task.The proposed algorithms had high time efficiency under large-scale conditions,but the solution quality is not high [71].He designed three heuristic algorithms,emergency insertion,greedy search,and dynamic programming,to solve the satellite autonomous task rescheduling problem [6].

In multi-satellites autonomous collaborative task scheduling,Gao et al.analyzed the task allocation problem for the distributed satellite systems,on this basis,a strict heuristic optimization algorithm was proposed based on the contract network and the task allocation model,the experiment proved that the algorithm is distributed，reduced search space quickly,which is suitable for small and medium-scale task scenarios [72].Lin et al.used a dynamic load balancing heuristic strategy to complete the task allocation between multiple satellites,but did not consider the communication constraints [73].Aiming at the task scheduling problem of heterogeneous low-orbit small satellites,Qin et al.adopted a completely centralized structure and proposed a resource-balanced task allocation algorithm based on deadlines,which was configured on the main satellite of the satellite cluster [57].

5.2 Meta-heuristic algorithm

With the continuous growth of the tasks,it is difficult for traditional heuristic algorithms to obtain satisfactory solutions.Large scale task scheduling problems usually rely on intelligent optimization algorithms.The meta-heuristic algorithms include the tabu search algorithm [74,75],the simulated annealing algorithm [76,77],the genetic algorithm [78,79],the particle swarm optimization algorithm [80,81],etc.

In satellite autonomous task scheduling,Bensana et al.used the tabu search algorithm to solve the SPOT5 satellite autonomous task scheduling problem,but the algorithm can only be used in small-scale scenarios [82].To solve the micro-satellites autonomous task scheduling problem,Chitty proposed an improved genetic algorithm to solve the problem of autonomous task scheduling for micro satellites,considering the constraints of time window and dynamic resources [83].The algorithm adopted an individual encoding based on fixed length integer sequence.Compared with floating-point coding,integer coding reduces the search space due to the finiteness of integer sequence sorting [83].Sun et al.proposed a new scheduling algorithm based on the genetic algorithm to solve the satellite autonomous task scheduling problem[84].

In multi-satellites autonomous collaborative task scheduling,in order to quickly allocate multiple targets in the imaging area to multiple satellites,Miao proposed an improved genetic algorithm to quickly form the imaging sequence of each satellite [85].The target,satellite imaging sequence and satellite formation were coded into genes,strings and individuals in turn,and an initial population generation method based on the judgment of satellite continuous imaging sidesway time was designed.Then the initial population was optimized by multiple selection crossover mutation to maximize the observation profit of the multi-satellites.Finally,the simulation scene is constructed,including 10 satellites and 160 ground targets of three levels.The results showed that the algorithm can give the imaging sequence of each satellite in 30 s.Compared with the simple genetic algorithm,the total imaging profit is increased by 40%,and the number of key targets is increased by 1.6 times.It met the requirements of engineering application [85].

To solve the multi-satellites autonomous collaborative task scheduling problem,He et al.established a hybrid algorithm combining genetic algorithm and simulated annealing to improve the efficiency and quality of the algorithm [86].The genetic algorithm has strong global optimization ability,fast convergence speed and the simulated annealing algorithm has strong local optimization ability.In order to verify the rationality of the model and the effectiveness of the algorithm,the simulation experiment was carried out.The planning time was set as 24 h,seven satellites with different remote sensors and three receiving stations with relatively uniform geographical distribution were selected,and 30 tasks were set at the same time.The results indicate that the proposed algorithm has fast convergence capability and excellent global convergence capability [86].Based on the traditional nondominated sorting genetic algorithm non-dominated sorting genetic algorithm (NSGA-II) algorithm,Li added heuristic rules based on priority to solve the autonomous cooperative task scheduling problem for high and low orbit satellites [87].For random point targets,the algorithm showed good convergence in small-scale,mediumscale and large-scale scenes converging in the 20th generation,the 40th generation and the 60th generation respectively,and with the expansion of the task scale,the gap between the algorithm and the NSGA-II algorithm is also larger [87].Zheng et al.proposed an improved genetic algorithm under the centralized architecture,but this method proved not to be suitable for a distributed architecture [56].Chen et al.proposed a particle swarm algorithm based on quantum behavior,and a mutation operator was introduced to avoid the algorithm falling into the local optimal [88].In order to solve the data transmission scheduling problem in the distributed satellite system,Guo et al.added crossover operator,mutation operator and direction backtracking mechanism in particle swarm optimization algorithm,and comprehensively considered the time window,remaining resources and task attributes[89].

Obviously,the heuristic algorithm and the meta-heuristic algorithm have their own limitations.Although the heuristic algorithm has a fast solution speed and is easy to get a satisfactory or even near-optimal scheduling solution,it is limited by the constructed heuristic rules and the task scale.The meta-heuristic algorithm is more suitable for large-scale problems,but it cannot guarantee to find the optimal solution.Therefore,on the one hand,we need to use effective heuristic rules to improve the convergence speed and the quality of the solution in a short time;on the other hand,we should make full use of the advantages of both to design hybrid algorithms,which plays a very important role in solving the satellite autonomous task scheduling problem.

5.3 Machine learning

Machine learning refers to the method of training satellite autonomous task scheduling decision models through supervised learning,reinforcement learning and other machine learning methods.At present,the application of machine learning methods in satellite autonomous task scheduling is still relatively few.

In supervised learning,Li et al.used robust decision trees,support vector machines and artificial neural networks to construct a remote sensing satellite task scheduling prediction model [90].Liu extracted the feature parameters including task priority,duration and conflict degree from the historical data,and constructed the task scheduling prediction model based on the back propagation (BP) neural network model [91].Xing et al.took uncertain factors into account,which included cloud and fog occlusion,and designed the satellite autonomous task scheduling algorithm based on a task schedulable prediction model [92].Du et al.trained the task scheduling prediction model through the evolutionary neural network algorithm,and allocated the tasks to satellites that are most likely to execute this task,which significantly improved the efficiency of the remote sensing satellite task scheduling [93].

In reinforcement learning,to solve the remote sensing satellite task scheduling problem,He et al.investigated a general solution based on reinforcement learning.The core idea of this method is to determine a value function for evaluating the long-term benefit under a certain state by training from experiences,and then apply this value function to guide decisions in unknown situations [94].Wang et al.trained the satellite task scheduling decisionmaking model through the A3C algorithm.When the new task arrived,the model would determine whether the task is to be executed or not,and allocate the longest observation time window for the task [95].

6.Future research

This paper summarizes the research on satellite autonomous task scheduling at home and abroad.With the continuous development of satellite technology,the number of satellites,the operating environment and the complexity of tasks,the research on satellite autonomous mission planning is becoming more and more complex.Future research can be carried out from the following aspects:

(i) Most researchers focus on the task scheduling architecture and solution algorithm.They assume that the input of the task scheduling model is the atomic task that can be directly scheduled.In actual engineering,the users often submit the complex tasks,how to decompose complex tasks into atomic tasks is the focus of future research.Intelligent planning algorithms based on task decomposition such as hierarchical task network (HTN) have been widely used in many practical projects.The method is to make full use of domain knowledge to search and gradually decompose goals into atomic tasks,which has high search efficiency and can handle large-scale scheduling problems.Therefore,taking the HTN and other task decomposition algorithms into the satellite autonomous task scheduling is an important research content in the future.

(ii) Discuss the autonomous task scheduling for multiple observation platforms.Since satellites can only fly along a predetermined orbit,the observation time is limited,and the targets are easily lost,satellite observation alone has great limitations and is not enough to deal with the complex and changeable environmental situation.Other observation platforms such as unmanned aircraft,ships and airships can complement satellites in terms of observation mode,coverage,and work cycle,which can significantly improve observation efficiency.It has become an important research content to discuss the multiple observation platforms autonomous task scheduling problem.

(iii) Establish the mathematical model for autonomous task scheduling that is closer to actual engineering.Most models simplify or even ignore some constraints,which leads to a large disagreement between simulation result and actual engineering.

(iv) Design the effective solution algorithms.Unlike traditional ground control centers,onboard computers have limited computing capability.Therefore,designing the algorithm should not only consider the task,but also consider the time complexity and space complexity.In recent years,artificial intelligence methods like deep learning and reinforcement learning have gradually been applied to the combinatorial optimization problem.In the future,with the increasing capacity of onboard computer and the continuous expansion of satellite autonomous task scheduling scenarios,a large number of data are generated,and solving the satellite autonomous task scheduling by artificial intelligence method has risen from theory to practice.