An Adaptive Local Grid Nesting-based Genetic Algorithm for Multi-earth Observation Satellites’ Area Target Observation

Abstract

The Scheduling of the Multi-EOSs Area Target Observation (SMEATO) is an EOS resource scheduling problem highly coupled with computational geometry. The advances in EOS technology and the expansion of wide-area remote sensing applications have increased the practical significance of SMEATO. In this paper, an adaptive local grid nesting-based genetic algorithm (ALGN-GA) is proposed for developing SMEATO solutions. First, a local grid nesting (LGN) strategy is designed to discretize the target area into parts, so as to avoid the explosive growth of calculations. A genetic algorithm (GA) framework is then used to share reserve information for the population during iterative evolution, which can generate high-quality solutions with low computational costs. On this basis, an adaptive technique is introduced to determine whether a local region requires nesting and whether the grid scale is sufficient. The effectiveness of the proposed model is assessed experimentally with nine randomly generated tests at different scales. The results show that the ALGN-GA offers advantages over several conventional algorithms in 88.9% of instances, especially in large-scale instances. These fully demonstrate the high efficiency and stability of the ALGN-GA.

Keywords

Multi-EOSs scheduling / area target observation / adaptive genetic algorithm / local grid nesting

References

[1] Arbor A, Holland J. Adaptation in Natural and Artificial Systems, 1975, USA: University of Michigan Press

[2] Chen Y, Xu M, Shen X, Zhang G, Lu Z, Xu J. A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping. Remote Sensing, 2020, 12(3): 344.

[3] Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

[4] El Garouani A, Mulla DJ, El Garouani S, Knight J. Analysis of urban growth and sprawl from remote sensing data: Case of Fez, Morocco. International Journal of Sustainable Built Environment, 2017, 6(1): 160-169.

[5] Gabrel V, Moulet A, Murat C, Paschos VT. A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts. Annals of Operations Research, 1997, 69(0): 115-134.

[6] Gabrel V, Vanderpooten D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. European Journal of Operational Research, 2002, 139(3): 533-542.

[7] Hu X, Zhu W, An B, Jin P, Xia W. A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem. Computers & Operations Research, 2019, 104: 74-89.

[8] Hu X, Zhu W, Ma H, An B, Zhi Y, Wu Y. Orientational variable-length strip covering problem: A branch-and-price-based algorithm. European Journal of Operational Research, 2021, 289(1): 254-269.

[9] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 2007, 39: 459-471.

[10] Karthikeyan L, Chawla I, Mishra AK. A review of remote sensing applications in agriculture for food security: Crop growth and yield, irrigation, and crop losses. Journal of Hydrology, 2020, 586: 124905.

[11] Lemaître M, Verfaillie G, Jouhaud F, Lachiver J, Bataille N. Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6(5): 367-381.

[12] Li S, Shen X, Yao H, Zhang G, Liu Y. Optimization of lateral swing angles of lunar satellite for region multiple strip imaging task planning. Geomatics and Information Science of Wuhan University, 2019, 44(4): 593-600.

[13] Li X, Zhu J, Mao C. Efficiency optimization of area target observation using earth observation satellites. Computer Simulation, 2006, 12: 24-27.

[14] Luo K. A hybrid binary artificial bee colony algorithm for the satellite photograph scheduling problem. Engineering Optimization, 2020, 52(8): 1421-1440.

[15] Peng G, Wen L, Feng Y, Bai B, Jing Y (2011). Simulated annealing algorithm for EOS scheduling problem with task merging. Proceedings of 2011 International Conference on Modelling, Identification and Control. Shanghai, China, June 26–29, 2011.

[16] Perea F, Vazquez R, Galan-Viogue J. Swath-acquisition planning in multiple-satellite missions: An exact and heuristic approach. IEEE Transactions on Aerospace and Electronic Systems, 2015, 51(3): 1717-1725.

[17] Sarkheyli A, Bagheri A, Ghorbani-Vaghei B, Askari-Moghadam R. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions. Aerospace Science and Technology, 2013, 29(1): 287-295.

[18] Song Y, Zhang Z, Sun K, Yao F, Chen Y. A heuristic genetic algorithm for regional targets’ small satellite image downlink scheduling problem. International Journal of Aerospace Engineering, 2019, 2019(PT.1): 1-13.

[19] Srinivas M, Patnaik LM. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(4): 656-667.

[20] Sun H, Xia W, Wang Z, Hu X. Agile earth observation satellite scheduling algorithm for emergency tasks based on multiple strategies. Journal of Systems Science and Systems Engineering, 2021, 30(5): 626-646.

[21] Vatti BR. A generic solution to polygon clipping. Communications of the ACM, 1992, 35(7): 56-63.

[22] Wang J, Zhu X, Yang LT, Zhu J, Ma M. Towards dynamic real-time scheduling for multiple earth observation satellites. Journal of Computer and System Sciences, 2015, 81(1): 110-124.

[23] Wang W, Jia D, Xu J, Chu H, Dong X (2020). Review of the development of global marine remote sensing satellite. Bulletin of Surveying and Mapping (5): 1.

[24] Wolfe WJ, Sorensen SE. Three scheduling algorithms applied to the earth observing systems domain. Management Science, 2000, 46(1): 148-166.

[25] Yuan Z, He Y, Cai F. Fast algorithm for maneuvering target detection in SAR imagery based on gridding and fusion of texture features. Geo-spatial Information Science, 2011, 14(3): 169-176.

[26] Zhang X, Zhang H, Feng X. The landsat framing algorithm based on WRS-2. Remote Sensing Information, 2012, 27(6): 39-44.

[27] Zhang Z, Zhang N, Feng Z. Multi-satellite control resource scheduling based on ant colony optimization. Expert Systems with Applications, 2014, 41(6): 2816-2823.

[28] Zhou Y, Yan Y, Huang X, Yang Y, Zhang H. Mission planning optimization for the visual inspection of multiple geosynchronous satellites. Engineering Optimization, 2015, 47(11): 1543-1563.

[29] Zhu W, Hu X, Xia W, Jin P. A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing, 2019, 23: 181-196.

[30] Zhu W, Hu X, Xia W, Sun H. A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests. Computers & Industrial Engineering, 2019, 130: 97-107.