# A Satellite Task Planning Algorithm Based on a Symmetric Recurrent Neural Network
## 5 Heuristic Search Algorithm Based on a Symmetric Recurrent Neural Network  
### Algorithm Design  
Due to the limitations of computing resources on the star, researchers mainly use a heuristic search algorithm with a fast calculation speed to solve them. The main idea is to sort the observation tasks according to the set rules and then determine whether the task can be inserted into the observation plan. It can be seen that the optimization performance of these heuristic search algorithms largely depends on the collation designed by the researchers. Because the empirical knowledge is difficult to express, or the information is not comprehensive enough, the rule-based heuristic search algorithm is usually worse than the exact search algorithm and intelligent optimization algorithm.  
In order to improve the optimization performance of the heuristic search algorithm, the paper proposed a heuristic search algorithm. The main difference between the algorithm and the existing heuristic algorithm is that the ranking rules of the observation tasks are no longer designed based on the experience of researchers, but are rather learned from the planning results of the precise search algorithm using the deep neural network algorithm, so that the ranking rules can be expressed more accurately. Specifically, the workflow of the heuristic search algorithm is shown in Figure 3:  
**Step 1:** Select all the observation tasks in the planning period and record them as the set, TSet;  
**Step 2:** Align the observation tasks in the set, TSet, in chronological order and use the deep neural network to sequentially calculate the schedulable probability of each observation task in the TSet (that is, the probability that the task will be executed);  
**Step 3:** Sort the observation tasks in the TSet in descending order of schedulable probability values;  
**Step 4:** Select the first observation task of the TSet (denoted as FTask), insert it into the observation plan, and delete the FTask from the TSet; check whether the observation plan violates resource constraints, such as energy and storage, and task switching constraints. If a constraint is violated, the task FTask is removed from the scenario.  
**Step 5:** Repeat step 4 until the TSet is empty; then, a complete observation plan is obtained.  
The Algorithm 1 shown as follow:  
Figure 3: Algorithm flowchart.  
In the above process, the schedulable probability of the observation task determines the ordering of the task, which is the key to affecting the performance of the heuristic algorithm. However, the historical planning result data only tell us which tasks were executed or not and does not directly give the schedulable probability of the observed task. It is not difficult to understand that the higher the schedulable probability value of the observation task, the more likely it is that the task will be executed. Then, we can use the historical planning data to train a task classification model, whose output contains two states, execution and non-execution. We can use the probability that the task will be executed as the schedulable probability of the observed task. Next, we can elaborate on the calculation method of the schedulable probability.  
In order to calculate the schedulable probability of the observation task, we designed a symmetric neural network model to calculate the schedulable probability of the observation task. The network structure is shown in the following figure. In the graph, the first recurrent neural network reads the task sequence on the left side of the observation task, and the second recurrent neural network reads the task sequence on the right side of the observation task. Finally, the executed probability, \(P_{s}\), and the non-execution probability, \(P_{n}=(P_{s}+P_{n}=1)\), of the observation task are given by the fully connected neural network; then, \(P_{s}\) is the schedulable probability value of the observation task. The symmetric recurrent neural network model is shown in Figure 4.