## 3 FANET Routing Algorithms
### Reinforcement-Learning-Based Routing Algorithms  
Reinforcement learning (RL) [90] is a machine learning method that learns optimal action strategies by interacting with the environment to maximize cumulative rewards. It is a method that does not require manually labeled training data and learns through autonomous experimentation and feedback. Reinforcement learning is adaptive and can adapt to different network topologies and channel states to learn the optimal routing policy. RL is also real-time, allowing learning to take place through real-time interaction with the environment [91; 92], enabling real-time adjustment of routing policies in dynamic environments. In addition, the learning process does not depend on specific data distributions and statistical models, enabling it to handle complex environments that are non-linear, non-stationary, and non-Gaussian [93; 94], and is suitable for handling large-scale dynamic problems such as FANET under SAGIN. In the process of flying UAVs, the current state includes information about the position, speed, and remaining power of the UAV, while the future state depends only on the current state, independent of the historical flight of the UAVs, so the UAV flight process has Markovian properties (MDP). The MDP process can be represented by a triple \(<S\), \(A\), \(R>\), where state denotes the finite set of states of the agent, action denotes the set of actions available to the agent, and reward denotes the reward value of the environment. By continuously trying to take different actions in this process, the intelligent body can find the optimal policy in the state space. The Markov decision process is illustrated in Figure 6. It is because of the adaptive, efficient, robust, and real-time nature of reinforcement learning that research on the use of reinforcement learning for FANET routing algorithms has been favored by many researchers in recent years. Some researchers have focused their attention on using the classical-value-function-based reinforcement learning algorithm Q-learning, and we analyze the latest research developments below. [PERSON] et al. [95] propose a Q-learning approach to improve the QoE of video users in a cellular area by introducing rewards related to quality of experience (QoE) metrics that address the distribution of drone swarms. The algorithm defines the state space as three types of information (i.e., drone location, flight time, and residual energy). By designing a  
Figure 6: Markov decision processes. global reward associated with the QoE, the algorithm can determine the optimal location for drone signal coverage. Experimental results show that the algorithm is able to match video users' requests to drones with sufficient remaining bandwidth. As the complexity of the algorithm increases with too many constraints, this method sets constraints only for users and routing paths in order to control the complexity of the algorithm, but a real FANET environment requires a comprehensive consideration of constraints. Similarly, a method that can adaptively adjust the capability of Q-learning parameters was proposed by [PERSON] et al. [96]. This method can automatically adjust the learning rate and discount factor according to the delay of each hop during packet transmission. [PERSON] et al. also proposed discovering potentially optimal routing paths using existing knowledge. Since UAVs are highly dynamic, there is a higher probability of link breakage and topology changes occurring. The difference between this method and the traditional method is that this method does not use past topological relationships but re-estimates the UAV neighborhood relationship each time to select a reliable next hop. In addition, [PERSON] et al. [97] propose a Q-learning-based routing algorithm aimed at reducing connectivity loss and energy constraints in UAV networks, and this algorithm enables dynamic routing. The study proposes a trajectory generation method that uses a segmented linear movement model to generate node movement trajectories.