×

zbMATH — the first resource for mathematics

QUEST – a new quadratic decision model for the multi-satellite scheduling problem. (English) Zbl 07157798
Summary: Demand for earth observation satellite imagery is pervasive and increasing rapidly across multiple domains, highlighting the key problem to optimally schedule satellite image acquisition/collection, subject to ground and on-board constraints. Despite the variety of reported approaches to solving the NP-hard multi-satellite scheduling problem (m-SatSP), serious limitations still prevail, largely overlooking problem structure exploitation and/or domain knowledge. Assuming a few constraints, problem modelling – or scope – is often confined to a simple trailing satellite constellation composition perspective and tends to conveniently oversimplify footprint coverage intricacies. As a result, adequate problem task decomposition properly reflecting complex kinematic behaviour for an ad hoc satellite constellation remains elusive. Known approaches also fail to provide valuable solution optimality gap estimations to objectively qualify best computed solution and/or to control run-time execution in solving hard problem instances. In this paper, a novel approach to solving the single objective static m-SatSP is proposed. It is based on network flow optimization using mathematical programming. Unlike previous methods, QUEST (QUadratically constrainEd program Solver Technology) relies on a sound alternative approximate objective function and, the exploitation of exact problem-solving techniques. Derived from domain knowledge and problem structure considerations, QUEST generalizes problem modelling to successfully handle virtual constellation, avoiding unsuitable utilization of traditional area coverage decomposition scheme. The proposed decision model concurrently captures coverage approximation, imaging success uncertainty and quality for a variety of tasks. It also includes new and optional constraints while embracing an acceptable upper bound on collection value. A QUEST variant alternatively relying on “delayed reward” to bridge promising search regions on move selection, further shows optimality gap reduction and provides additional speedup. Computational results prove QUEST to be cost-effective and to outperform some recent baseline methods derived from best-known m-SatSP procedures. It comparatively demonstrates measurable collection and run-time gains, and provides a tight upper bound on the optimal solution of hard problems.
MSC:
90B Operations research and management science
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Vazquez Alvarez, A. J.; Erwin, R. S., An Introduction to Optimal Satellite Range Scheduling (2015), Springer · Zbl 1333.49002
[2] Wu, G.; Liu, J.; Ma, M.; Dishan, Q., A two-phase scheduling method with the consideration of task clustering for earth observing satellites, Comput. Oper. Res., 40, 7, 1884-1894 (2013) · Zbl 1348.90457
[3] Wang, J.; Demeulemeester, E.; Hu, X.; Qiu, D.; Liu, J., Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds, IEEE Syst. J., 1-12 (2018)
[4] Verfaillie, G., Planning and scheduling activities for earth surveillance and observation satellites: a constraint-based perspective, (ICAPS 2013 Summer School, Perugia, Italy (2013))
[5] Verfaillie, G.; Lemaître, M., Tutorial on planning activities for earth watching and observation satellites and constellations: from off-line ground planning to on-line on-board planning, (ICAPS 2006, The English Lake District, Cumbria, UK (2006))
[6] Lemaître, M., Selecting and scheduling observations of agile satellites, Aerosp. Sci. Technol., 367-381 (2002)
[7] Niu, X.; Tang, H.; Wu, L., Multi-satellite observation scheduling for large area disaster emergency response, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., 1327-1331 (2018), China
[8] Chu, X.; Chen, Y.; Lining, X., A branch and bound algorithm for agile earth observation satellite scheduling, Discret. Dyn. Nat. Soc., 2017 (2017), Article ID 7345941
[9] Nelson, F., Scheduling Optimization for Imagery Satellite Constellations Using Column Generation (2012), George Mason University, Department of Systems Engineering and Operations Research, Volgenau School of Engineering, PhD Thesis
[10] Wang, J.; Demeulemeester, E.; Qiu, D., A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds, Comput. Oper. Res., 74, 1-13 (2016) · Zbl 1349.90895
[11] Luo, K., High-performance technique for satellite range scheduling, Comput. Oper. Res., 85, 12-21 (2017) · Zbl 06901445
[12] Spangelo, S.; Cutler, J.; Gilson, K.; Cohn, A., Optimization-based scheduling for the single-satellite, multi-ground station communication problem, Comput. Oper. Res., 57, 1-16 (2015) · Zbl 1348.90314
[13] Marinelli, F.; Nocella, S.; Rossi, F.; Smriglio, S., A Lagrangian heuristic for satellite range scheduling with resource constraints, Comput. Oper. Res., 38, 11, 1572-1583 (2011) · Zbl 1210.90045
[14] Pinto, M.; Barros, A.; Noomen, R.; Gelder, P.; Tessensohn, T., A new model proposal for integrated satellite constellation scheduling within a planning horizon given operational constraints, (Proceedings of the 7th International Conference on Operations Research and Enterprise Systems (2018)), 312-319
[15] Augenstein, S., Optimal scheduling of a constellation of earth-imaging satellites, for maximal data throughput and efficient human management, (Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (2016)), 345-352
[16] Wang, Y., Multi-resource coordinate scheduling for earth observation in space information networks, IEEE J. Sel. Areas Commun., 36, 2, 268-279 (2018)
[17] Song, Y.; Huang, D.; Zhou, Z., An emergency task autonomous planning method of agile imaging satellite, EURASIP J. Image Video Proc., 29, 2-11 (2018)
[18] Chu, X.; Chen, Y.; Tan, Y., An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling, Adv. Space Res., 1, 1-15 (2017)
[19] Maillard, A.; Verfaillie, G.; Pralet, C.; Jaubert, J.; Lhermitte, J., Adaptable data download schedules for agile earth-observing satellites, J. Aerosp. Comput. Inf. Commun., 13, 3, 1-21 (2016)
[20] Niu, X.; Tang, H.; Wu, L.; Deng, R.; Zhai, X., Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events, Math. Probl. Eng., 2015, 1-31 (2015), Article ID 731734 · Zbl 1394.90296
[21] Wang, J.; Zhu, X.; Yang, T.; Zhu, J.; Ma, M., Towards dynamic real-time scheduling for multiple earth observation satellites, J. Comput. Syst. Sci., 81, 110-124 (2015)
[22] Zhai, X., Robust satellite scheduling approach for dynamic emergency tasks, Math. Probl. Eng., 2015, 9, 1-20 (2015)
[23] Qiu, D.; He, C.; Liu, J.; Ma, M., A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy, Sci. World J., 2013 (2013)
[24] Galceran, E.; Carreras, E., A survey on coverage path planning for robotics, Robot. Auton. Syst., 61, 12, 1258-1276 (2013)
[25] Vasquez, M.; Hao, J., A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite, Comput. Optim. Appl., 20, 2, 137-157 (2001) · Zbl 0983.90082
[26] Vasquez, M.; Hao, J., Upper bounds for the SPOT 5 daily photograph scheduling problem, J. Comb. Optim., 7, 1, 87-103 (2003) · Zbl 1046.90030
[27] Wolfe, J.; Stephen, S. E., Three scheduling algorithms applied to the earth observing systems domain, Manag. Sci., 46, 1, 148-168 (2000) · Zbl 1231.90286
[28] Lemaître, M.; Verfaillie, G.; Jouhaud, F.; Lachiver, J. M.; Bataille, N., How to manage the new generation of agile earth observation satellites, (Proceeding of the International Symposium on Artificial Intelligence, Robotics and Automation in Space (ISAIRAS’00) (2000))
[29] Verfaillie, G.; Schiex, T., Solution reuse in dynamic constraint satisfaction problems, (Proceeding of the Twelfth National Conference on Artificial Intelligence (AAAI’94) (1994)), 307-312
[30] Gabrel, V.; Moulet, A.; Murat, C.; Paschos, V. T., A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts, Ann. Oper. Res., 69, 115-134 (1997) · Zbl 0880.90092
[31] Gabrel, V.; Vanderpooten, D., Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite, Eur. J. Oper. Res., 139, 3, 533-542 (2002) · Zbl 0995.90047
[32] Sarkheyli, A.; Vaghei, B. G.; Bagheri, A., New tabu search heuristic in scheduling earth observation satellites, (Proceeding of the Second International Conference on Software Technology and Engineering (ICSTE’10) (2010))
[33] Zufferey, N.; Amstutz, P.; Giaccari, P., Graph colouring approaches for a satellite range scheduling problem, J. Sched., 11, 4, 263-277 (2008) · Zbl 1168.90481
[34] Wang, J.; Jing, N.; Li, J.; Chen, Z. H., A multi-objective imaging scheduling approach for earth observing satellites, (Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO ’07) (2007)), 2211-2218
[35] Benoist, T.; Rottembourg, B., Upper bounds for revenue maximization in a satellite scheduling problem, 4OR-Q. J. Oper. Res., 2, 3, 235-249 (2004) · Zbl 1136.90538
[36] Habet, D.; Vasquez, M., Solving the selecting and scheduling satellite photographs problem with a consistent neighborhood heuristic, (Proceeding of the Sixteenth IEEE International Conference on Tools With Artificial Intelligence (ICTAI’04) (2004))
[37] Habet, D., Tabu search to solve real-life combinatorial optimization problems: a case of study, (Abraham, A.; Hassanien, AE; Carvalho, AP, Foundations of Computational Intelligence, 3 (2009), Springer), 129-151
[38] Habet, D.; Vasquez, M.; Vimont, Y., Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite, Comput. Optim. Appl., 47, 2, 307-333 (2010) · Zbl 1200.90075
[39] Liao, D.; Tang, Y., Satellite imaging order scheduling with stochastic weather condition forecast, (Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, 3 (2005)), 2524-2529
[40] Liao, D.; Tang, Y., Imaging order scheduling of an earth observation satellite, IEEE Trans. Syst. Man Cybern., 37, 5, 794-802 (2007)
[41] Lin, W.; Liu, C.; Liao, D.; Lee, Y., Daily imaging scheduling of an earth observation satellite, (Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, 2 (2003)), 1886-1891
[42] Lin, W.; Liao, D., A tabu search algorithm for satellite imaging scheduling, (Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, 2 (2004)), 1601-1606
[43] Lin, W.; Chang, S., Hybrid algorithms for satellite imaging scheduling, (Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, 3 (2005)), 2518-2523
[44] Lin, W.; Liao, D.; Liu, C.; Lee, Y., Daily imaging scheduling of an earth observation satellite, IEEE Trans. Syst. Man Cybern. A, 35, 2, 213-223 (2005)
[45] Bianchessi, N.; Righini, G., A mathematical programming algorithm for planning and scheduling an earth observing SAR constellation, (Proceeding of the Fifth International Workshop on Planning and Scheduling for Space (IWPSS’06) (2006))
[46] Bianchessi, N.; Laporte, G., A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites, Eur. J. Oper. Res., 177, 2, 750-762 (2007) · Zbl 1102.90327
[47] Gabrel, V.; Murat, C., Mathematical programming for earth observation satellite mission planning, (Ciriani, TA; Fasano, G.; Gliozzi, S.; Tadei, R., Operations Research in Space and Air (2003), Springer), 103-122 · Zbl 1051.90533
[48] Gabrel, V., Strengthened 0-1 linear formulation for the daily satellite mission planning, J. Comb. Optim., 11, 3, 341-346 (2006) · Zbl 1255.90138
[49] Hall, N. G., Magazine MJ. Maximizing the value of a space mission, Eur. J. Oper. Res., 78, 2, 224-241 (1994) · Zbl 0813.90078
[50] Bensana, E.; Verfaillie, G.; Agnese, J. C.; Bataille, N.; Blumestein, D., Exact and inexact methods for the daily management of an earth observation satellite, (Proceeding of the international Symposium on Space Mission Operations and Ground Data System, 4 (1996)), 507-514
[51] Tangpattanakul, P.; Jozefowiez, N.; Lopez, P., Multi-objective optimization for selecting and scheduling observations, (Coello, CA; Cutello, V.; Deb, K.; Forrest, S.; Nicosia, G.; Pavone, M., Lecture Notes in Computer Science (2012), Springer)
[52] Mansour, M. A.A.; Dessouky, M. M., A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite, Comput. Ind. Eng., 58, 3, 509-520 (2010)
[53] Barbulescu, L.; Watson, J.-P.; Whitley, L. D.; Howe, A. E., Scheduling space-ground communications for the air force satellite control network, J. Sched., 7, 1, 7-34 (2004) · Zbl 1306.90046
[54] Li, Y.; Xu, M.; Wang, R., Scheduling observations of agile satellites with combined genetic algorithm, (Proceedings of the 3rd International Conference on Natural Computation (ICNC 2007), 3 (2007)), 29-33
[55] Baek, S.-W.; Han, S.-M.; Cho, K.-R., Development of a scheduling algorithm and GUI for autonomous satellite missions, Acta Astron., 68, 7-8, 1396-1402 (2011)
[56] Soma, P.; Venkateswarlu, S.; Santhalakshmi, S.; Bagchi, T.; Kumar, S., Multi-satellite scheduling using genetic algorithms, (Proceeding of the Eighth International Conference on Space Operations (SpaceOps’04) (2004))
[57] Globus, A.; Crawford, J.; Lohn, J.; Pryor, A., A comparison of techniques for scheduling fleets of earth-observing, J. Oper. Res. Soc., 56, 8, 962-968 (2003)
[58] Li, Y.; Wang, R.; Xu, M., Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm, Chin. J. Aeronaut. (2014)
[59] Wang, H.; Xu, M.; Wang, R.; Li, Y., Scheduling earth observing satellites with hybrid ant colony optimization algorithm, (Proceeding of the International Conference on Artificial Intelligence and Computational Intelligence (AICI’09) (2009))
[60] Globus, A.; Crawford, J.; Lohn, J.; Morris, R., Scheduling earth observing fleets using evolutionary algorithms: problem description and approach, (Proceeding of the Third International NASA Workshop on Planning and Scheduling for Space (2002))
[61] Agnese, J. C.; Bensana, E., Exact and approximate methods for the daily management of an earth observation satellite, (Proceeding of the Fifth ESA Workshop on Artificial Intelligence and Knowledge Based Systems for Space (1995))
[62] Bensana, E.; Verfaillie, G.; Agnese, J. C.; Bataille, N.; Blumestein, D., Exact and inexact methods for the daily management of an earth observation satellite, (Proceeding of the International Symposium on Space Mission Operations and Ground Data Systems, 4 (1996)), 507-514
[63] Bianchessi, N.; Piuoi, V.; Righini, G.; Roveri, M.; Laneve, G.; Zigrino, A., An optimization approach to the planning of earth observing satellites, (Proceeding of the Fourth International Workshop on Planning and Scheduling for Space (IWPSS’04) (2004))
[64] Bianchessi, N.; Righini, G., Planning and scheduling algorithms for the COSMOSkyMed constellation, Aerosp Sci Technol, 12, 7, 535-544 (2008)
[65] Chen, X., Priority-based and conflict-avoidance heuristics for multi-satellite scheduling, Appl. Soft Comput., 69, 177-191 (2018)
[66] Verfaillie, G.; Lemaître, M.; Schiex, T., Russian doll search for solving constraint optimization problems, (Proceeding of the Thirteenth National Conference on Artificial Intelligence (AAAI’96) (1996)), 181-187
[67] IBM ILOG CPLEX Optimization Studio V12.7.0 https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html.
[68] Butler, P. J., Project polar epsilon: joint space-based wide area surveillance and support capability, (Proceedings of the 2005 IEEE International Geoscience and Remote Sensing, Symposium (IGARSS), 2 (2005)), 1194-1197
[69] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge university press · Zbl 1058.90049
[70] IBM ILOG CPLEXOptimization Studio CPLEX User’s Manual, version 12 Release 6 (2015).https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.6.2/ilog.odms.studio.help/pdf/usrcplex.pdf.
[71] Berger, J.; Giasson, E., A graph-based genetic algorithm to solve the virtual constellation multi-satellite collection scheduling problem, (IEEE Congress on Evolutionary Computation. IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil (2018))
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.