Scheduling a constellation of agile earth observation satellites with preemption

Document Type: Research Paper

Authors

Ferdowsi University of Mashhad

Abstract

In this paper, we consider a scheduling problem for a set of agile Earth observation satellites for scanning  different parts of the Earth’s surface. We assume that preemption is allowed to prevent repetitive images and develop four different preemption policies. Scheduling is done for the imaging time window and transmission time domain to the Earth stations as well. The value of each picture from different target regions and the limitations of the satellite constellation in terms of memory and energy cause high computational complexity for this problem and thus obtaining an optimum solution with a deterministic method is very time-consuming. Consequently, a genetic-based metaheuristic algorithm with a specific solution representation is developed in order to maximize the total value of the observation process by establishing heuristic rules in the initial population of this algorithm. Comparison of the results from the proposed model with the results of cases where repetition of observed areas is not ignored indicates that the proposed model can bring about a significant increase in profits in the planning horizon.

Keywords


Bianchessi, N., & Righini, G. (2008). Planning and scheduling algorithms for the COSMO-SkyMed constellation,

Aerospace Science and Technology, v12(7), 535–544.

Chen, Y., Zhang, D., Zhou, M., & Zou, H. (2012). Multi-satellite Observation Scheduling Algorithm Based on Hybrid

Genetic Particle Swarm Optimization. In D. Zeng (Ed.), Advances in Information Technology and Industry

Applications (Vol. 136). Berlin, Heidelberg: Springer Berlin Heidelberg.

Florio, S. De. (2006). Performances Optimization of Remote Sensing Satellite Constellations: a Heuristic Method, In

Proceedings of the 5th international workshop on planning and scheduling for spacev, http://www.stsci.edu/largefiles/iwpss/20069151043Paper.pdf.

Frank, J., Jónsson, A., & Morris, R. (2001). Planning and scheduling for fleets of earth observing satellites, In

Proceedings of Sixth Int. Symp. on Artificial Intelligence, Robotics, Automation & Space,

http://citeseerx.ist.psu.edu/viewdoc/summary?.

Gabrel, V., Moulet, A., Murat, C., & Paschos, V. T. (1997). A new single model and derived algorithms for the satellite

shot planning problem using graph theory concepts, Annals of Operations Research, 69, 115–134.

Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002). Selecting and scheduling observations

of agile satellites, Aerospace Science and Technology, 6(5), 367–381.

Morena, L. C., James, K. V, & Beck, J. (2014). An introduction to the RADARSAT-2 mission. Canadian Journal of

Remote Sensing, 30(3), 221–234.Wang, P., & Reinelt, G. (2010). A Heuristic for an Earth Observing Satellite

Constellation Scheduling Problem with Download Considerations, Electronic Notes in Discrete Mathematics, 36,

711–718.

Tangpattanakul, P., Jozefowiez, N., & Lopez, P. (2015). A multi-objective local search heuristic for scheduling Earth

observations taken by an agile satellite, European Journal of Operational Research, 245(2), 542–554.

Wang, P., Reinelt, G., Gao, P., & Tan, Y. (2011). A model, a heuristic and a decision support system to solve the

scheduling problem of an earth observing satellite constellation, Computers & Industrial Engineering, 61(2), 322–335.

Wang, J., Demeulemeester, E., & Qiu, D. (2016). A pure proactive scheduling algorithm for multiple earth observation

satellites under uncertainties of clouds, Computers and Operations Research, 74, 1-13.

Xu, R., Chen, H., Liang, X., & Wang, H. (2016). Priority-based constructive algorithms for scheduling agile earth

observation satellites with total priority maximization, Expert Systems with Applications, 51, 195-206.