# Optimized Dynamic Deployment of UAVs in Maritime Networks with Route Prediction
## 4 Proposed Algorithm
### UAV Dynamic Deployment Algorithm  
Traditional UAV-deployment methods only consider the limitations of the UAV's energy consumption and latency, without taking into account the mobility of the user nodes and the UAV's computational resources. Therefore, in this section, a deep reinforcement learning algorithm is used to deploy drones dynamically. Trajectory prediction is used to understand the user distribution in advance so that decision-makers can make better decisions to maximize the coverage with less delay and energy consumption. At each time slot, the agent collects ship prediction data, dynamically assigns drones, and develops deployment strategies based on predicted device locations as well as task volumes. We convert the UAV-deployment problem into a Markov Decision Process (MDP) problem, defined by the tuple \((S,A,p,r)\), where the state space \(S\) and action space \(A\) are continuous. Specifically, the Markov chain is denoted by \((s_{t},a_{t},s_{(t+1)},r_{t})\), where each parameter consists of an output state \(s_{t}\in S\) at moment \(t\), an action \(a_{t}\in A\), an output state \(s_{(t+1)}\in S\) at moment \(t+1\), and a reward \(r_{t}\in r\). The output state \(s_{t}\) is received from the environment to the intelligent agent at moment \(t\). The intelligent agent uses an internal policy function to compute the probabilities of each action and selects an action \(a_{t}\) based on these probabilities. Applying action \(a_{t}\) to the environment yields state \(s_{(t+1)}\). Finally, the environment will combine the action \(a_{t}\), the state transitions, and the reward function to compute the reward value \(r_{t}\) under action \(a_{t}\) and return it to the intelligent agent so that the agent can optimize its future action strategy based on the reward situation. The complete trajectory of the interaction process with the environment can be represented by Equation (39):  
\[\tau=\left\{s_{0},a_{0},s_{1},a_{1},\ldots,s_{t},a_{t}\right\} \tag{39}\]  
The state space \(S\) consists of \((3M+6)\) states, where \(M\) represents the number of available drones. Based on the trajectory-prediction algorithm described in Section 4.1, we can predict the movement trajectories of uncovered users over some time. At the moment \(t\), by performing K-means clustering analysis on the user coordinates, we can determine the location of the user's aggregation center point at that moment, whose 3D coordinates correspond to three states in the state space. In addition, the other three states describe the decision effects at moment \(t\), including the total number of covered users, the accumulated delay, and the overall energy consumption, respectively. Meanwhile, \(3M\) represents the remaining battery capacity, available computing resources, and the distance of the UAVs relative to the center point of the user distribution at moment \(t\), respectively, for \(M\) UAVs. The action space \(A\) consists of \(3M\) consecutive action variables, each of which represents the amount of adjustment of the coordinates of the \(M\) UAVs in the 3D space at the moment \(t\). Together, these action variables determine the change of the UAV's position at the next moment, thus enabling efficient optimization of user coverage. The reward function is designed as:  
\[r_{\text{total}}(t)=\sigma\sum_{n=1}^{N}X_{n}+\varsigma\frac{\sum_{n=1}^{N}X_{n }}{\sum_{m=1}^{M}\Bigl{(}E_{\text{fly,m}}(t)+E_{\text{hover m,n}}(t)\Bigr{)}}+ \tau\frac{\sum_{n=1}^{N}X_{n}}{d_{\text{total}}(t)} \tag{40}\]  
where \(\sigma\), \(\varsigma\), and \(\tau\) are the moderating factors used to regulate the reward weights of each component. As the number of covered users increases, the inverse of the average energy consumption and the inverse of the average delay decrease with the increase in users. To achieve the reduction of delay and energy consumption while maximizing the number of covered users, the larger this reward function, the better the performance of the algorithm.