Agile Earth Observation Satellites Coordinating And Scheduling: Models And Algorithms

As the main platform of space image acquisition,the main task of the Earth observation satellite is to acquire the observation information of the Earth surface according to the requests of users.Because of its advantages of wide coverage,long imaging time and no limit of the national border,the Earth observation satellite plays an increasingly important role in economic development,disaster rescue and emergency monitoring.In recent years,with the continuous development of satellite capabilities and new application requirements,new challenges have been put forward for the current satellite observation scheduling system: compared with the traditional satellite,the new generation of agile Earth observation satellite has time-dependent characteristics,making its planning and scheduling problems much more complex;complex tasks,such as largearea monitoring,ocean moving target tracking,etc.require the cooperation of multiple satellites;the uncertain weather,such as cloud cover,has a great impact on satellite imaging,which reduces the efficiency of the satellite;the observation demand of emergent tasks requires the satellite to have fast response ability.This paper focuses on coordinating and scheduling agile satellites from the following aspects:First,the scheduling problem of a single agile satellite with time dependence is studied.Having a highly efficient single-satellite scheduling method is the key to solve the multi-satellite coordinating and scheduling problem and the scheduling problem in the uncertain environment.A hybrid algorithm combining the adaptive large neighborhood search algorithm and the tabu search algorithm is proposed.The algorithm includes multiple tabu types,multiple general randomized neighborhood operators,a partial sequence domination strategy,and a fast task insertion strategy for scheduling problems with sequence dependence and time dependence.This scheduling method has good generality and has achieved better results than state-of-the-art algorithms on three different kinds of problems,including the single agile satellite scheduling problem.At the same time,the performance of the algorithm on instances with different characteristics is analyzed,and some general conclusions are obtained to guide the parameter setting of the algorithm.Finally,considering that there are few test data and source code in the field of agile satellite scheduling with time dependence,the test data and source code used in this paper are published to promote the research in this field.Second,the coordinating and scheduling problem of multiple agile satellites with time dependence is studied.One of the main difficulties of multi-satellite scheduling is the sharp increase of the solution space caused by the increase of the number of satellites.In order to solve this problem,the necessity of task allocation for multi-satellite coordinating and scheduling is analyzed.An adaptive task assignment strategy is proposed,which extends the proposed adaptive large neighborhood search algorithm to the case of scheduling multiple satellites.The algorithm can automatically adjust the weight of each task assignment operator according to the characteristics of different instances,so as to achieve adaptive task assignment.Extensive experiment results show that the proposed adaptive task assignment mechanism is more effective than state-ofthe-art multi-satellite coordinating methods.In the simulation experiment,the influence of parameters on the performance of the algorithm is studied,different instances are compared,and some general conclusions are obtained.Third,the coordinating and scheduling problem of multiple agile satellites considering real-time changing cloud cover is studied.In view of the predictable uncertainties such as the cloud cover,a hierarchical coordinating and scheduling method for real-time scheduling problems is proposed,which is between online and offline.This method starts from a simple task assignment and a rough scheduling process and improves the precision of scheduling gradually as the task observation start time approaches and the accuracy of cloud prediction increases.This method can effectively reduce the influence of cloud cover on observation by postponing the scheduling time.At the same time,compared with the traditional two-stage scheduling method which includes off-line scheduling and on-line adjustment,the fine scheduling of determining the specific observation start time in this method is only executed once,thus achieving a higher resource utilization.The simulation results show that,for all the instances with different task distribution modes,scheduling ranges,task numbers and satellite numbers,the algorithm can reduce the computation time and improve the solution quality,especially for large-scale cases.The hierarchical framework can also be applied to other large-scale optimization problems with real-time changing environment.Last but not least,the multi-satellite distributed coordinating and scheduling problem considering emergent tasks is studied.Emergent task is a kind of uncertain events that satellite system often encounter in the application process,such as natural disasters,hot-spot emergencies and so on.Because of the large uncertainty of time and space,it is difficult to predict these emergent tasks.To solve this problem,a multisolution integration framework is proposed,which changes the complex onboard scheduling problem to a simple solution selection problem and can quickly generate a high-quality solution under the constraints of limited computing resources and computing time.At the same time,a variety of distributed coordinating methods for multi-satellite coordination in uncertain environment are proposed,including a greedy selection strategy,an optimal coordinating strategy based on multi-agent Markov decision process,and an optimal selection strategy based on mixed integer programming.The proposed multisatellite coordinating method enables the satellite to make independent decisions quickly according to the strategy,so that it can obtain high profits quickly without on-orbit communication.The effectiveness of the multi-solution integration framework and the distributed coordinating strategies proposed for the on-board rescheduling problem is proved by multiple simulation experiments.At the same time,the adaptability of the different coordinating methods to the problem instances with different characteristics is studied.