# Revising the Observation Satellite Scheduling Problem Based on Deep Reinforcement Learning
## 2 Problem Description
### Graph Clustering Model  
In contrast to task scheduling without clustering, this strategy could save a lot of energy, especially with frequent observations. In addition, task clustering enables some previously conflicting tasks to be executed at the same time. The condition for merging multiple tasks into a clustering task is that these tasks can be finished with the same slewing angle and OW [38], which constrains the task clustering process. (1) Time window-related constraint  
The longest observation duration \(\Delta T\) allowed for a sequential observation is limited because of the characteristic of the sensor. Therefore, the VTW should satisfy the following constraint:  
\[TWE_{u}^{ci}-TWS_{u}^{ci}\leq\Delta T \tag{1}\]  
Supposing that clustering task \(t_{u}^{c}\) is clustered from \(\{t_{1},t_{2},\cdots,t_{n}\}\), where:  
\[TWS_{u}^{ci}=\min\{TWS_{l}\mid l=1,2,\cdots,n\} \tag{2}\]  
\[TWE_{u}^{ci}=\max\{TWE_{l}\mid l=1,2,\cdots,n\} \tag{3}\]  
The time window of clustered tasks should allow the satellite to finish all the component tasks in a common temporal interval. (2) Slewing angle-related constraint  
Multiple clustered tasks should guarantee that they can be completed with the same slewing angle. Let \(\theta_{u}\) denote the slewing angle when observing \(t_{u}\) and \(\delta\theta_{u}\) denote the feasible slewing angle range, then Equation (4) gives:  
\[\Delta\theta_{u}^{c}=\Delta\theta_{1}\cap\Delta\theta_{2}\cdots\cap\Delta \theta_{n} \tag{4}\]  
For the clustered task \(t_{u}^{c}\), the slewing angle could be calculated by the mean value of \(\Delta\theta_{u}^{c}\):  
\[\theta_{u}^{c}=\frac{1}{2}[\sup(\Delta\theta_{u}^{c})+\inf(\Delta\theta_{u}^{ c})] \tag{5}\] \begin{table}
\begin{tabular}{c l} \hline \hline
**Symbol** & **Meaning** \\ \hline \(t_{u}\) & Observation task to target \(u\) \\ \(t_{u}^{ci}\) & Observation task to merged target \(u\) \\ \([TWS_{u}^{ci},TWE_{u}^{i}]\) & VTW of \(t_{u}\) in the \(i\)th orbit \\ \([TWS_{u}^{ci},TWE_{u}^{ci}]\) & VTW of \(t_{u}^{c}\) in the \(i\)th orbit \\ \(\theta_{u}\) & Slewing angle for observation task \(t_{u}\) \\ \(d_{u}\) & Observation duration time of \(t_{u}\) \\ \(x_{u}\) & Whether to execute \(t_{u}\) \\ \(x_{uv}\) & Whether to transform execution from \(t_{u}\) to \(t_{v}\) \\ \(v_{s}\) & Slewing maneuver velocity \\ \(s_{uv}\) & Preparation time of task switch \\ \(trantT_{uv}\) & Slewing angle maneuver time between two tasks \\ \(maxT\) & Maximum operating time in one observation \\ \(max0\) & Maximum slewing angle \\ \(c_{i}\) & Storage consumption per unit observation time \\ \(M\) & Total data storage capacity \\ \(e_{i}\) & Energy consumption per unit time of observation \\ \(\varepsilon_{uv}\) & Energy consumption per unit time of slewing maneuver \\ \(E\) & Total available energy \\ \(prio_{u}\) & Priority of observation task \(t_{u}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of notations. According to the constraints mentioned above, merged tasks need to be screened out, and the graph theory is used to build the clustering model. Firstly, we defined an undirected graph \(G=\langle V,E\rangle\), where \(V\) is the set of vertexes and \(V(G_{i})\) represents all valid observation tasks in the \(ith\) orbit, \(E\) is the set of edges and \(E(G_{i})\) denotes the links between two tasks. In the graph clustering model, any two original observation tasks with the edge connection satisfying the constraint conditions can be regarded as a clustering task. While expanding to a multiple vertex condition, multiple original tasks can be merged into one clustering task if there are edge connections between any two vertexes. The connected vertexes form a clique, where all vertexes are connected with each other, as shown in Figure 2, \(\{t_{3},t_{4},t_{5}\}\), \(\{t_{6},t_{7}\}\) and \(\{t_{8},t_{9},t_{1}0,t_{1}1\}\) can be seen as cliques and each clique is regarded as a clustering task. In this paper, an adjacency matrix is adopted to better illustrate the utility of the graph clustering model.