Research On The Scheduling Of Optical Earth Observation Satellites Under Uncertainties Of Clouds

Optical earth observation satellites(OEOSs)equipped with optical sensors are platforms obtaining image data of the earth surface from space,playing a nontrivial role in military and commercial reconnaissance.With the development of space technology,OEOSs have been more and more extensively employed in military reconnaissance,disaster monitoring,urban planning and other fields,resulting in the earth observation requests from different users increasing fast.Hence,planning and scheduling the limited earth observation resources,as well as making optimized observation schedule,are critical issues in satisfying the requests of users,improving the observation efficiency of satellites,and giving full play to the performance of satellite observation system.Optical earth observation satellites take the advantages of high spatial resolution,accurate information access,etc.However,OEOSs also have some shortages,one of which is that they cannot see through clouds.Hence,earth observation is highly affected by cloud cover.Currently,most of observations of OEOSs fail because of cloud cover.In order to obtain high-quality image data of ground,earth observations of optical satellites should avoid being obscured by clouds.Note that,the status of clouds is not static but provided with uncertainties,thus it is impossible and impractical to forecast the status of clouds exactly.Hence,it is essential to analyze the impact of uncertainties of clouds on earth observations,and it is also important to study the scheduling of optical earth observation satellites under uncertainties of clouds,because they are critical in satisfying the requests of users and improving the observation efficiency of OEOSs.Towards the scheduling problem of OEOSs under uncertainties of clouds,we studied the problem from modeling and solving.The main work and contributions of this study are outlined as below:(1)A “proactive+reactive” scheduling framework of optical earth observation satellites under uncertainties of clouds was presented.We analyzed the impact of uncertainties of clouds on optical satellite observations in depth,and studied the characteristics of OEOS scheduling under uncertainties of clouds.Considering the phases of scheduling,such as planning and execution,we proposed a “proactive+reactive” scheduling framework.Based on the prior information of cloud forecast,we model and solve the scheduling problem of optical satellites in the proactive scheduling,making a baseline schedule.With the implementation of the baseline schedule,we repair and adjust the observation schedule to deal with the disturbances resulting from uncertainties of clouds in the reactive scheduling.Note that,the reactive scheduling can both improve observation profits and keep the observation schedule feasible.In the scheduling framework,we combine the static proactive scheduling on ground and the onboard autonomous reactive scheduling,which can improve observation efficiency of satellites,satisfying users' requirements.Besides,this scheduling framework can also keep the schedule stable,supporting users' decisions effectively.(2)A stochastic expectation model of proactive scheduling and a branch and price algorithm for solving were designed.With respect to the proactive scheduling of OEOSs under uncertainties of clouds,a stochastic expectation model was constructed,maximizing the expected value of the earth observation profit.Because the stochastic expectation model is characterized by a block diagonal structure,the problem was decomposed into a set packing master problem and multiple constrained longest path programming subproblems based on Dantzig-Wolfe decomposition.Afterwards,a branch and price algorithm was proposed to solve the problem.By simulation,we compared the performances of the branch and price algorithm and CPLEX,and verified the effectiveness of the algorithm.(3)A chance constraint programming model of proactive scheduling and two algorithms,i.e.the branch and cut algorithm and the column generation heuristic algorithm were studied.With regard to the shortage of the stochastic expectation model that it cannot evade risk effectively,a chance constraint programming model was proposed for proactive scheduling,which maximizes the lower bound of observation profit under the condition of satisfying a certain confidence level.Refer to the fact that the probability of the chance constraint is difficult to calculate,the chance constraint programming model was transformed into a mixed integer programming model by sample approximation.With respect to the assignment model that is based on forbidden sequence,a branch and cut algorithm based on lazy constraint was developed to solve the problem optimally.In addition,towards the “flow variable” model,a column generation heuristic algorithm was suggested on the basis of Dantzig-Wolfe decomposition to obtain close-to-optimal solutions of large-scale problems.Finally,numerous simulation experiments were designed to evaluate the performances of the algorithms,verifying the effectiveness.(4)A robust model of satellite observation proactive scheduling and exact & heuristic algorithms were proposed.With respect to the proactive scheduling of OEOSs under uncertainties of clouds,the stochastic expectation model and the chance constraint programming model both schedule a task to at most one observation resource,without taking into account that scheduling a task to multiple resources can improve the possibility of successful observation.Hence,considering scheduling an observation task to multiple resources,we proposed a robust model of satellite observation scheduling.Because the proposed robust model is non-linear and difficult to solve,we decomposed the complicated problem into a master problem of schedule selection and multiple subproblems of path programming,and proposed an exact algorithm for solving.With respect to the exact algorithm,the subproblems were solved by a dynamic programming algorithm based on label updating.Afterwards,on the basis of all the feasible solutions of the subproblems,the master problem was solved by an enumeration algorithm.Due to its large space complexity,the exact algorithm cannot solve some large-scale problems,thus five multi-pass heuristic algorithms based on sampling were designed for solving.By simulation,we validated the superiority of the robust model and the effectiveness of the algorithms.Finally,we evaluate the performances of different algorithms on problems of different sizes.(5)A multi-objective optimization model of reactive scheduling and a heuristic algorithm were developed.With respect to the disturbances resulting from uncertainties of clouds,considering the scheduling profit and stability simultaneously,we suggested a multi-objective optimization model of reactive scheduling.Refer to the characteristics of the reactive scheduling that the available solving time is very short and the computing resources are limited,an efficient heuristic algorithm was designed based on task insertion,task retraction and task swapping,.Simulation results reveal that the reactive scheduling can not only improve the scheduling efficiency and increase the observation profit,but also decrease the disturbances resulting from uncertainties of clouds.