A fast scheduling method of multiple agile satellites based on neural network-guided genetic algorithm

doi:10.23919/JSEE.2024.000121

Abstract

Abstract:

Agile imaging satellites play important roles in gathering Earth surface information due to their expansive field-of-view, high-resolution observations, and flexibility in observation timing. Genetic algorithm (GA) has been one of the most commonly utilized meta-heuristic algorithms for solving multiple agile satellites (MAS) scheduling problems due to its stable and good performance. Nonetheless, the iterative convergence speed of GA is slow owing to the blindness of the preliminary search. To address this issue, this paper proposes an efficient meta-heuristic MAS scheduling method integrated with a neural network (NN). In the proposed method, an NN is applied to learn the historical scheduling experience and generate effective initial solutions, thereby improving the convergence speed of GA for MAS scheduling. Experimental results demonstrate that the proposed NN-guided GA (NN-GA) accelerates the convergence of GA by approximately 60% and exhibits higher efficiency for MAS scheduling compared to existing state-of-the-art methods.

Key words: multiple agile satellites (MAS), scheduling, neural network (NN), genetic algorithm (GA)

Lili Zhao, Yongge Ma, Xueqian Wang, Gang Li. A fast scheduling method of multiple agile satellites based on neural network-guided genetic algorithm[J]. Journal of Systems Engineering and Electronics, 2026, 37(4): 1101-1119.

Figures/Tables 34

Fig 1

Fig 2

Fig 3

Table 1

Fig 4

Fig 5

Table 2

Fig 6

Fig 7

Table 3

Fig 8

Fig 9

Table 4

Table 5

Fig 10

Fig 11

Table 6

Fig 12

Fig 13

Table 7

Fig 14

Fig 15

Table 8

Fig 16

Fig 17

Fig 18

Fig 19

Fig 20

Fig 21

Table 9

Fig 22

Table 10

Fig 23

Fig 24

References 37

1	Union of Concerned Scientists[EB/OL].[2024-03-19]. https://www.ucsusa.org/resources/satellite-database.
2	Wang J Q, Yang L L, Zhuang C R, et al Emergency-oriented satellite mission planning[J]. Spacecraft Recovery & Remote Sensing, 2022, 43 (3): 105.
3	Chen Y, ZhanG D Y, Zhou M Q, et al Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization. Advances in Information Technology and Industry Applications, 2012, 136, 441.
4	Wang Z H, Wang X Q, Wu W, et al Continuous change detection of flood extents with multisource heterogeneous satellite image time series[J]. IEEE Trans. on Geoscience and Remote Sensing, 2023, 61, 1.
5	Zhang Q, Wang X Q, Wang Z H, et al. Heterogeneous remote sensing image fusion based on homogeneous transformation and target enhancement[C]//International Conference on Unmanned Systems, 2022: 688.
6	Ze Z H, Li G, Han J H, et al. SAR ship detection based on an improved CNN with loU-FL and attention mechanism[C]//IEEE Radar Conference, 2023. DOI: 10.1109/RadarConf2351548.2023.10149726.
7	Lemamitrea M, Verfaillie G, Jouhaud F, et al Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6 (5): 367. doi: 10.1016/S1270-9638(02)01173-2
8	Wang P, Reinelt G. Solving the Earth observing satellite constellation scheduling problem by branch-and-price[J]. Operations Research Proceedings, 2010: 491.
9	Bensana E, Verfaillie G, Bataillie N, et a1. Exact and inexact methods for the daily management of an earth observation satellite[J]. Proceedings of SpaceOPS, 1996: 507.
10	Han Q, Zhang W Y Joint imaging programming of multi-satellites. Remote Sensing Information, 2013, 28 (4): 19.
11	Han C, Gu Y, Wu G H, et al Simulated annealing based heuristic for multiple agile satellites scheduling under cloud coverage uncertainty. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2023, 53 (5): 2863. doi: 10.1109/TSMC.2022.3220534
12	Hao H C, Jiang W, Li Y J Improved algorithms to plan missions for agile earth observation satellites[J]. Journal of Systems Engineering and Electronics, 2014, 25 (5): 811. doi: 10.1109/JSEE.2014.00094
13	Zhou Z B, Chan E M, Wu F, et al Multi-satellite scheduling problem with marginal decreasing imaging duration: an improved adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2023, 176, 108890.
14	Liu J M, Chen Y G, Wang R, et al Complex task planning method of space-aeronautics cooperative observation based on multi-layer interaction[J]. Journal of Systems Engineering and Electronics, 2023, 34 (6): 1550. doi: 10.23919/JSEE.2022.000098
15	Sun H Q, Xia W, Hu X X, et al. Earth observation satellite scheduling for emergency tasks[J]. Journal of Systems Engineering and Electronics, 2019, 30(5): 931.
16	Du Y H, Wang T, Xin B, et al A data-driven parallel scheduling approach for multiple agile earth observation satellites[J]. IEEE Trans. on Evolutionary Computation, 2020, 24 (4): 679. doi: 10.1109/TEVC.2019.2934148
17	Wu J, Song B Y, Zhang G T, et al A data-driven improved genetic algorithm for agile earth observation satellite scheduling with time-dependent transition time[J]. Computers & Industrial Engineering, 2022, 174, 108823.
18	Song Y J, Wei L N, Yang Q, et al RL-GA: a reinforcement learning-based genetic algorithm for electromagnetic detection satellite scheduling problem. Swarm and Evolutionary Computation, 2023, 77, 101236. doi: 10.1016/j.swevo.2023.101236
19	Wu J, Chen Y N, He Y M, et al Survey on autonomous task scheduling technology for Earth observation satellites. Journal of Systems Engineering and Electronics, 2022, 33 (6): 1176.
20	Yang X. Nature-inspired metaheuristic algorithms[M]. Frome: Luniver Press, 2010.
21	Yang X S, Deb S, Zhao Y X, et al. Swarm intelligence: past, present and future[J]. Soft Computation, 2018, 22(18): 5923.
22	Eskandar H, Sadollah A, Ardeshir Bahreininejad B, et al Water cycle algorithm−a novel metaheuristic optimization method for solving constrained engineering optimization problems[J]. Computer & Structures, 2012, 110, 151.
23	Li Q, Liu S Y, Yang X S Influence of initialization on the performance of metaheuristic optimizers. Applied Soft Computing Journal, 2020, 91, 106193. doi: 10.1016/j.asoc.2020.106193
24	Mao T, Mihaita A S, Chen F, et al Boosted genetic algorithm using machine learning for traffic control optimization[J]. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (7): 7122.
25	Wang X W, Wu G H, Xing L N, et al Agile earth observation satellite scheduling over 20 years: formulations, methods, and future direction. IEEE Systems Journal, 2021, 15 (3): 3881. doi: 10.1109/JSYST.2020.2997050
26	Peng G S, Dewil R, Verbeeck C, et al Agile earth observation satellite scheduling: an orienteering problem with time-dependent profits and travel times[J]. Computers and Operations Research, 2019, 111, 84. doi: 10.1016/j.cor.2019.05.030
27	Tan X S, Ge C H A method for calculating solar angles and its application on remote sensing[J]. Remote Sensing for Land & Resources, 1995, (2): 48.
28	Wen J, Liu X L, He L Real-time online rescheduling for multiple agile satellites with emergent tasks[J]. Journal of Systems Engineering and Electronics, 2021, 32 (6): 1407. doi: 10.23919/JSEE.2021.000120
29	Wu J, Lu F, Zhang J W, et al Design of task priority model and algorithm for imaging observation problem[J]. Journal of Systems Engineering and Electronics, 2020, 31 (2): 321. doi: 10.23919/JSEE.2020.000010
30	Zhang C, Li Y B Planning and scheduling method for multi agile satellite coordinated mission. Science Technology and Engineering, 2017, 17 (22): 271.
31	Chatterjee A, Tharmarasa R Reward factor-based multiple agile satellites scheduling with energy and memory constraint[J]. IEEE Trans. on Aerospace and Electronic Systems, 2022, 58 (4): 3090. doi: 10.1109/TAES.2022.3146115
32	Andre D, Koza J R A parallel implementation of genetic programming that achieves super-linear performance[J]. Journal of Information Sciences, 1998, 106, 201. doi: 10.1016/S0020-0255(97)10011-1
33	Rumelhart D, Hinton G Learning representations by back-propagating errors[J]. Nature, 1986, 323, 533. doi: 10.1038/323533a0
34	CelesTrack[EB/OL].[2024-03-19]. https://celestrack.org.
35	Burke E K, Kendall G. Search methodologies[M]. New York: Springer Verlag, 2005.
36	Du F Summary of earthquake activities in 2022[J]. Earthquake Research in Sichuan, 2023, 2, 1.
37	Zhao J. Agile satellite[M]. Beijing: National Defense Industry Press, 2021. (in Chinese)

Variable	Connotation
$ I $	Total number of satellites
$ {s_i} $	The $ {i{{\mathrm{th}}}} $ satellite, $ i = \left\{ {1,2,\cdots,I} \right\} $
$ {b_i} $	Priority of satellite $ {s_i} $, $ {b_i} \leqslant \Re $, $ 1 \leqslant {b_i} \leqslant 10 $
$ {\mathrm{ID}}{s_i} $	Identification number of the satellite $ {s_i} $, $ {\mathrm{ID}}{s_i} \in \left\{ {1,2,\cdots,I} \right\} $
$ J $	Total number of tasks
$ {q_j} $	The $ {j{{\mathrm{th}}}} $ task, $ j = \left\{ {1,2,\cdots,J} \right\} $
$ {d_j} $	Priority of task $ {q_j} $, $ {d_j} \leqslant \Re $, $ 1 \leqslant {d_j} \leqslant 10 $
$ {\mathrm{ID}}{q_j} $	Identification number of the task $ {q_j} $, $ {\mathrm{ID}}{q_j} \in \left\{ {1,2,\cdots,J} \right\} $
$ {\mathrm{wt}} $	Weighting factor
$ {{\mathrm{ts}}_{ij}} $	The moment that satellite $ {s_i} $ begins the observation of task $ {q_j} $
$ {{\mathrm{te}}_{ij}} $	The moment that satellite $ {s_i} $ completes the observation of task $ {q_j} $
$ t{e_{{\mathrm{final}}}} $	The moment that the final task observation is completed
$ {{\mathrm{ob}}_j} $	Observation duration required by task $ {q_j} $
$ {{\mathrm{Ts}}_{ij}} $	Start of the visualization time window of the satellite $ {s_i} $ to the task $ {q_j} $
$ {{\mathrm{Te}}_{ij}} $	End of the visualization time window of the satellite $ {s_i} $ to the task $ {q_j} $
$ {\mathrm{trans}}{T_{{j_1}{j_2}}} $	Time needed for the satellite to adjust its attitude after observing $ {q_{{j_1}}} $, so it can observe $ {q_{{j_2}}} $
$ {\varphi _{ij}} $	Solar altitude angle at which satellite $ {s_i} $ observes task $ {q_j} $
$ {\varphi _{{\mathrm{MIN}}}} $	Minimum solar altitude angle for ensuring the quality of optical satellite observations
$ {x_{ij}} $	$ {x_{ij}} = 1 $, if satellite $ {s_i} $ observes the task $ {q_j} $; otherwise, $ {x_{ij}} = 0 $

Resource	ID	Feature	Symbolic representation
Satellite $ s_i^k $	#1	Priority	$ b_i^k $
Satellite $ s_i^k $	#2	Identification number	$ \text{ID}s_i^k $
Task $ q_j^k $	#3	Priority	$ d_j^k $
	#4	Identification number	$ {\mathrm{ID}}q_j^k $
	#5	Required observation duration	$ {\mathrm{ob}}_j^k $
VTW $ v_{ijl}^k $	#6	VTW length	$ Te_{ijl}^k - Ts_{ijl}^k $
VTW $ v_{ijl}^k $	#7	Identification number	$ {\mathrm{ID}}v_{ijl}^k $
Pre-VTW task $ q_{j\sim a}^k $	#8	Priority	$ d_{j\sim a}^k $
	#9	Identification number	$ {\mathrm{ID}}q_{j\sim a}^k $
	#10	Required observation duration	$ {\mathrm{ob}}_{j\sim a}^k $
	#11	VTW conflict	$ {\mathrm{con}}f_{j\sim a}^k $
Post-VTW task $ q_{j\sim b}^k $	#12	Priority	$ d_{j\sim b}^k $
	#13	Identification number	$ {\mathrm{ID}}q_{j\sim b}^k $
	#14	Required observation duration	$ {\mathrm{ob}}_{j\sim b}^k $
	#15	VTW conflict	$ {\mathrm{con}}f_{j\sim b}^k $

ID	Historical scheduling data	New scheduling data (for testing feature extraction)	Extra attributes in new scheduling data
ID	Historical scheduling data	New scheduling data (for testing feature extraction)	For VTW calculation	For Algorithm 3
1	$\boldsymbol{H}^k=\left(\boldsymbol{S}^k, \boldsymbol{Q}^k, \boldsymbol{V}^k\right)$	$\boldsymbol{H}=(\boldsymbol{S}, \boldsymbol{Q}, \boldsymbol{V})$	−	−
2	$\boldsymbol{S}^k=\left\{s_i^k \mid i=1,2, \cdots, I^{\varGamma}\right\}$	$\boldsymbol{S}=\left\{s_i \mid i=1,2, \cdots, I\right\}$	−	−
3	$s_i^k=\left\{b_i^k, {\mathrm{I D}} s_i^k\right\}$	$s_i=\left\{b_i, {\mathrm{I D}} s_i\right\}$	$\text {wid}_i, \text {orb}_i, \text {ang}_i$	−
4	$\boldsymbol{Q}^k=\left\{q_j^k \mid j=1,2, \cdots, J^{\varGamma}\right\}$	$\boldsymbol{Q}=\left\{q_j \mid j=1,2, \cdots, J\right\}$	−	−
5	$q_j^k=\left\{d_j^k, {\mathrm{o b}}_j^k, {\mathrm{I D}} q_j^k\right\}$	$q_j=\left\{d_j, {\mathrm{o b}}_j, {\mathrm{I D}} q_j\right\}$	${\rm{lon}}_j, {\rm{lat}}_j$	−
6	$\boldsymbol{V}^k=\left\{v_{i j l}^k \mid l=1,2, \cdots, L_{i j}^k\right\}$	$\boldsymbol{V}=\left\{v_{i j} \mid l=1,2, \cdots, L_{i j}\right\}$	−	$\operatorname{ang} T_{i j l}$
7	$v_{i j l}^k=\left\{T s_{i j l}^k, T e_{i j l}^k, {\mathrm{I D}} v_{i j l}^k\right\}$	$v_{i j l}=\left\{T s_{i j}, T e_{i j l}, {\mathrm{I D}} v_{i j l}\right\}$	−	−

ID	Reference satellite	Swath width/km	Incidence angle range/(°)	Pitch/(°)	Yaw/(°)
1	GF-3	100	10−60	30	0
2	HJ-2E	35	10−60	30	0

Number of tasks	Average convergence time/s
Number of tasks	GA [10]	SA [11]	HGPT [14]	DDPS [16]	NN-GA
20	0.69	0.93	0.80	0.40	0.29
30	2.18	2.82	2.27	1.10	0.90
40	4.16	4.70	4.42	2.11	1.86
50	7.20	8.17	7.31	3.97	3.43
60	11.01	12.41	11.42	6.19	5.40
70	16.67	17.81	15.73	9.73	7.69