# Deep Reinforcement Learning for the Agile Earth Observation Satellite Scheduling Problem
## 2 Problem Description
### Attitude Transition Time Constraint  
For each target, the satellite observation attitude is determined. When observing two consecutive targets, a specific attitude transition time is required and can be calculated using Equations (12) and (13), where \(b_{0}=11.66\), \(b_{1}=5\), \(b_{2}=10\), \(b_{3}=16\), \(b_{4}=22\), \(a_{1}=1.5\), \(a_{2}=2\), \(a_{3}=2.5\), \(a_{4}=3\), \(z_{0}=10\), \(z_{1}=30\), \(z_{2}=60\), and \(z_{3}=90\). The length of the transition  
Figure 1: Time-attitude adjacency graph of AEOSSP. The number indicates the task number, the black arrow indicates the task that can be selected in the current state, and the red arrow indicates the task that is actually selected. Figure 2: Solution construction process. The numbers in the green squares represent the solution. time depends on the ending attitude of the former task and the starting attitude of the latter task, both of which are time-dependent. \[\text{trans}\big{(}ea_{i},ba_{j}\big{)}=\left\{ \begin{array}{rl}b_{0},&\rho_{ ij}\leq z_{0}\\ b_{1}+\rho_{ij}/a_{1},&z_{0}<\rho_{ij}\leq z_{1}\\ b_{2}+\rho_{ij}/a_{2},&z_{1}<\rho_{ij}\leq z_{2}\\ b_{3}+\rho_{ij}/a_{3},&z_{2}<\rho_{ij}\leq z_{3}\\ b_{4}+\rho_{ij}/a_{4},&\rho_{ij}>z_{3}\end{array} \right.,\forall x_{ij}=1 \tag{12}\]  
\[\rho_{ij}=\Big{|}\theta_{i,te_{i}}-\theta_{j,tb_{j}}\Big{|}+\Big{|}\varphi_{i, te_{i}}-\varphi_{j,tb_{j}}\Big{|}+\Big{|}\psi_{i,te_{i}}-\psi_{j,tb_{j}}\Big{|}, \forall x_{ij}=1 \tag{13}\]  
To analyze the characteristics of this constraint, we propose a method to determine the earliest observation start time for the next task based on the current task. First, we define a time delay function using the same method as in [28]. **Definition 1**. : _Time delay function: For consecutive task\({}_{i}\) and task\({}_{j}\), the time delay function under the time-dependent attitude transition time constraint \(\left(te_{i},tb_{j}\right)\), \(\text{trans}\big{(}ea_{i},ba_{j}\big{)}\) can be defined as Equation (14)._  
\[\text{tidy}\big{(}te_{i},tb_{j}\big{)}=te_{i}+\text{trans}\big{(}ea_{i},ba_{j} \big{)}-tb_{j} \tag{14}\]  
The satellite completes the observation of the former task at \(te_{i}\) and then begins the attitude transition. After \(\text{trans}\big{(}ea_{i},ba_{j}\big{)}\), the satellite ends the transition and waits until \(tb_{j}\) for the latter task observation. When \(\text{tidy}\big{(}te_{i},tb_{j}\big{)}<0\), the satellite has finished the attitude transition before observation, which satisfies the shortest attitude transition time. When \(\text{tidy}\big{(}te_{i},tb_{j}\big{)}>0\), the transition time is insufficient, and the constraint is violated. When \(\text{tidy}\big{(}te_{i},tb_{j}\big{)}=0\), the transition time is just sufficient. [PERSON] et al. [28] proved that for agile satellites, the delay function \(\text{tidy}\big{(}te_{i},tb_{j}\big{)}\) monotonically increases with \(te_{i}\) and decreases with \(tb_{j}\). This property shows that determining the earliest observation start time for the latter task can help compress the attitude transition time between two tasks and increase the availability of OWs. We designed the EarliestImageCal algorithm to obtain the earliest observation start time of the latter task. The core idea is to calculate it by the linear approximation iterative method. The pseudo-code of the algorithm is shown in Algorithm 1. The EarliestImageCal algorithm divides the solution into three situations: (1) when the start time of the latter task VTW meets the attitude transition constraint, the task OW is satisfied with the constraint, as shown in Figure 3a; (2) when the end time of the latter task VTW does not meet the attitude transition constraint, the task OW is not satisfied with the constraint, as shown in Figure 3b; (3) when the start time of the latter task VTW does not meet but the end time meets, we use the linear approximation method to replace the delay function, as shown in Figure 3c. Figure 3: Three situations of EarliestImageCal.