The optimal scheduling of earth observation satellite is NP-complete. Most of the existing scheduling algorithms regard requests as the observations of point objects and adopt preprocessing methods, such as simple clustering, so as to decrease the problem size. There are also some algorithms in which requests are regarded as the observations of rectangular regions. However, actual requests are often the observation of irregular regions. Therefore, existing methods cannot decrease the problem size effectively. In this paper, the reward rate of each observation request region is sampled at specified space resolution. Then a fast computational method, which is "row accumulations followed by column accumulations", is employed to acquire reward values of all the candidate imaging windows in the satellite's covering of land belt in the given time slot. The method has linear computational complexity on the discrete point count of all the request regions. At last, the imaging windows corresponding to the local maxima of reward values are chosen as candidate imaging windows. Experiments with random inputs show that the methods in this paper can effectively deal with the observation requests with irregular region, those with multi-intersections of covering regions, and those with nonlinear relationship between reward rate and the region covering rate.
展开▼
