# Navigation Resource Allocation Algorithm for LEO Constellations Based on Dynamic Programming
## 3 Navigation Resource Allocation Algorithm Based on Dynamic Programming  
### Algorithm Principle  
Dynamic Programming, as an operational research method, is adept at resolving complex decision processes across multiple stages [26; 27; 28]. Central to this method is [PERSON]'s principle of optimality, which simplifies the problem-solving process by breaking down a multi-stage Decision problem into manageable, single-stage problems. This is achieved through a fundamental recursive relationship that allows for the continuous transformation of the Decision process. Each stage builds upon the previous one, enabling a systematic approach to solving each segment in sequence. As illustrated in Figure 7, [PERSON] emphasized that the optimal strategy for a multi-level Decision process possesses a critical characteristic: irrespective of the initial state and decision, if any stage and state are considered the initial point, the subsequent decisions must align to form an overall optimal strategy. Specifically, if there is a Decision process whose initial state is \(K\) level, and its optimal strategy is \(\{w(0),w(1),\cdots,w(K-1)\}\), then, for \(w(0)K-1\) the level-level Decision process whose initial state is, the decision set \(\{w(1),\cdots,w(K-1)\}\) must be the optimal strategy. The principle of optimality provides a simple and effective method for solving optimization problems in multi-level Decision processes and provides a theoretical basis for deriving recursive equations. Next, we outline the parameters commonly employed in dynamic programming algorithms [29]:  
1. Stage: Decompose the given optimization problem into several interconnected stages according to spatial or temporal characteristics, and stage variables are often used \(k\) to represent them;
2. Status: used to describe the characteristics of the stage. A state is a single variable or vector. In this algorithm, it is assumed that the subjects under study exhibit'memorylessness', which is the Markov property. This means that future states depend  
Figure 7: Dynamic programming algorithm schematic diagram. only on the current state and are independent of past states and decisions. \(s_{k}\) is commonly used to represent the state variables of the \(k\)-th stage;
3. State space: The set of values of state variables \(s_{k}\) becomes a state set, which is represented by \(S_{k}\);
4. Decision: Upon a given state in a particular stage, various decisions can be made to derive the state of the subsequent stage. Such decisions are termed Decision. The variables used to describe these decisions are called decision variables, commonly denoted as \(\mu_{k}(s_{k})\) to represent the decision variable at stage \(k\) when the state is \(s_{k}\);
5. State transition: In dynamic programming, the state of the current stage results from the combined effect of the state and the decision of the previous stage. If the state at stage \(k\) is given as \(s_{k}\), and the decision made is \(\mu_{k}(s_{k})\), then the state at stage \(k+1\), denoted as \(s_{k+1}\), is fully determined. The state transition in the context of satellites involves moving from one configuration of resource allocation to another, considering the visibility and isolation constraints of the satellites involved. Their relationship can be expressed by \(s_{k+1}=T_{k}(s_{k},\mu_{k})\) where \(T_{k}(s_{k},\mu_{k})\) is called the state transition function, illustrating the evolutionary relationship between successive stages;
6. Strategy: In real-world problems, the values of decision variables are often confined within a certain range, known as the permissible decision set. This range is typically denoted as \(D_{k}(s_{k})\), representing the permissible decision set starting from state \(s_{k}\) at stage \(k\), thus \(\mu_{k}(s_{k})\in D_{k}(s_{k})\);
7. Stage indicator function: The benefit measure of a decision made from a given state in a particular stage is called the stage utility function, denoted as \(v_{k}(s_{k},\mu_{k})\);
8.