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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
References
Arbor A, Holland J (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, USA.
Chen Y, Xu M, Shen X, Zhang G, Lu Z, Xu J (2020). A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping. Remote Sensing 12(3): 344.
Dorigo M, Gambardella LM (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1): 53–66.
El Garouani A, Mulla DJ, El Garouani S, Knight J (2017). Analysis of urban growth and sprawl from remote sensing data: Case of Fez, Morocco. International Journal of Sustainable Built Environment 6(1): 160–169.
Gabrel V, Moulet A, Murat C, Paschos VT (1997). A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts. Annals of Operations Research 69(0): 115–134.
Gabrel V, Vanderpooten D (2002). Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. European Journal of Operational Research 139(3): 533–542.
Hu X, Zhu W, An B, Jin P, Xia W (2019). A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem. Computers & Operations Research 104: 74–89.
Hu X, Zhu W, Ma H, An B, Zhi Y, Wu Y (2021). Orientational variable-length strip covering problem: A branch-and-price-based algorithm. European Journal of Operational Research 289(1): 254–269.
Karaboga D, Basturk B (2007). A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization 39: 459–471.
Karthikeyan L, Chawla I, Mishra AK (2020). A review of remote sensing applications in agriculture for food security: Crop growth and yield, irrigation, and crop losses. Journal of Hydrology 586: 124905
Lemaître M, Verfaillie G, Jouhaud F, Lachiver J, Bataille, N (2002). Selecting and scheduling observations of agile satellites. Aerospace Science and Technology 6(5): 367–381.
Li S, Shen X, Yao H, Zhang G, Liu Y (2019). Optimization of lateral swing angles of lunar satellite for region multiple strip imaging task planning. Geomatics and Information Science of Wuhan University 44(4): 593–600.
Li X, Zhu J, Mao C (2006). Efficiency optimization of area target observation using earth observation satellites. Computer Simulation 12: 24–27.
Luo K (2020). A hybrid binary artificial bee colony algorithm for the satellite photograph scheduling problem. Engineering Optimization 52(8): 1421–1440.
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.
Perea F, Vazquez R, Galan-Viogue J (2015). Swath-acquisition planning in multiple-satellite missions: An exact and heuristic approach. IEEE Transactions on Aerospace and Electronic Systems 51(3): 1717–1725.
Sarkheyli A, Bagheri A, Ghorbani-Vaghei B, Askari-Moghadam R (2013). Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions. Aerospace Science and Technology 29(1): 287–295.
Song Y, Zhang Z, Sun K, Yao F, Chen Y (2019). A heuristic genetic algorithm for regional targets’ small satellite image downlink scheduling problem. International Journal of Aerospace Engineering 2019(PT.1): 1–13.
Srinivas M, Patnaik LM (1994). Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics 24(4): 656–667.
Sun H, Xia W, Wang Z, Hu X (2021). Agile earth observation satellite scheduling algorithm for emergency tasks based on multiple strategies. Journal of Systems Science and Systems Engineering 30(5): 626–646.
Vatti BR (1992). A generic solution to polygon clipping. Communications of the ACM 35(7): 56–63.
Wang J, Zhu X, Yang LT, Zhu J, Ma M (2015). Towards dynamic real-time scheduling for multiple earth observation satellites. Journal of Computer and System Sciences 81(1): 110–124.
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.
Wolfe WJ, Sorensen SE (2000). Three scheduling algorithms applied to the earth observing systems domain. Management Science 46(1): 148–166.
Yuan Z, He Y, Cai F (2011). Fast algorithm for maneuvering target detection in SAR imagery based on gridding and fusion of texture features. Geo-spatial Information Science 14(3): 169–176.
Zhang X, Zhang H, Feng X (2012). The landsat framing algorithm based on WRS-2. Remote Sensing Information 27(6): 39–44.
Zhang Z, Zhang N, Feng Z (2014). Multi-satellite control resource scheduling based on ant colony optimization. Expert Systems with Applications 41(6): 2816–2823.
Zhou Y, Yan Y, Huang X, Yang Y, Zhang H (2015). Mission planning optimization for the visual inspection of multiple geosynchronous satellites. Engineering Optimization 47(11): 1543–1563.
Zhu W, Hu X, Xia W, Jin P (2019a). A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing 23: 181–196.
Zhu W, Hu X, Xia W, Sun H (2019b). A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests. Computers & Industrial Engineering 130: 97–107.
Acknowledgments
The authors express their gratitude to the editors and the anonymous referees for their valuable input, which greatly contributed to enhancing the quality of this paper. This work has been supported in part by the National Natural Science Foundation of China (NSFC), under Grant Nos. 72271074 and 72071064.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The authors declare no conflict of interest.
Additional information
Ligang Xing is now pursuing his doctoral degree in management science and engineering at Hefei University of Technology. His research interests include the operations research and optimization.
Wei Xia is currently an associate professor in Hefei University of Technology. His research interests include satellite intelligent scheduling and controlling.
Xiaoxuan Hu is currently a professor at Hefei University of Technology. His research interests include satellites scheduling and UAV path planning.
Waiming Zhu is currently working in Hefei University of Technology as a lecturer. His research interests include operations research and satellites scheduling.
Yi Wu is now working for her master degree in management science and engineering at Hefei University of Technology. Her research interests include satellite scheduling.
Rights and permissions
About this article
Cite this article
Xing, L., Xia, W., Hu, X. et al. An Adaptive Local Grid Nesting-based Genetic Algorithm for Multi-earth Observation Satellites’ Area Target Observation. J. Syst. Sci. Syst. Eng. 33, 232–258 (2024). https://doi.org/10.1007/s11518-024-5591-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11518-024-5591-2