# AUV Trajectory Planning for Optimized Sensor Data Collection in Internet of Underwater Things
## 2 Materials and Methods
### Proposed Solution
#### 2.3.1 AUV Trajectory Optimization Algorithm
The corresponding residual VoI is:  
\[V_{r_{s(1)}}\big{(}t_{q}\big{)}=\mathcal{V}_{int_{s(1)}}\big{(}1-\beta\, \mathcal{I}_{s(1)}\big{)}^{t_{q}}. \tag{14}\]  
This initializes the DP table as:  
\[J(1,\,q):=V_{r_{s(1)}}\big{(}t_{q}\big{)}, \tag{15}\]  
and the backtracking information is initialized as \(\text{Prev}(1,q)\ :=S_{s}\). For each subsequent stage \(i=2,\ldots M\), and for every candidate waypoint \(q\in\mathcal{Q}_{s(i)}\), the algorithm iteratively evaluates all possible transitions from all previous waypoints \(\hat{q}\in\mathcal{Q}_{s(i-1)}\). The travel time between the two waypoints is denoted by \(t_{q\to q}\), indicating the time required to move from \(\hat{q}\) to \(q\). The updated arrival time at \(q\) is then calculated as:  
\[t_{q}=t_{\hat{q}}+t_{q\to q}, \tag{16}\]where \(t_{q}\) is the stored arrival time at the previous waypoint \(q\). The residual VoI collected at CH \(s(i)\) upon arriving at \(q\) is evaluated as:  
\[V_{\tau_{s(i)}}\big{(}t_{q}\big{)}=\mathcal{V}_{int_{s(i)}}\big{(}1-\beta\; \mathcal{I}_{s(i)}\big{)}^{t_{q}}. \tag{17}\]  
The DP table is subsequently updated by selecting the transition from \(q\) that results in the maximum total residual VoI:  
\[J(i,\;q)\;:=\max_{q\in\mathcal{Q}_{s(i-1)}}[\;J(i-1,\;q)+V_{\tau_{s(i)}}(t_{q})]. \tag{18}\]  
During each step, the algorithm updates \(\mathrm{Prev}(i,q)\) with the previous waypoint \(q\) that results in the maximum value, i.e., \(\mathrm{Prev}(i,q)\;:=q\). This enables recovery of the optimal waypoint sequence via backtracking once the process is complete. At the final stage, the optimal value corresponding to the current permutation \(\Phi\) is determined as:  
\[V_{\mathrm{rotolab}}=\max_{q\in\mathcal{Q}_{s(i)}}J(M,q). \tag{19}\]  
Following this step, the optimal waypoint sequence is recovered by backtracking through the stored transitions starting from the final waypoint. This procedure is repeated for each permutation \(\Phi\in\Phi\), and the optimal path is determined as:  
\[(\Phi_{\mathrm{opt}},\mathcal{P}_{\mathrm{opt}})=\underset{\Phi\in\hat{\Phi} }{\mathrm{argmax}}V_{\mathrm{rotolab}_{\Phi}}. \tag{20}\]  
Here, \(\Phi_{\mathrm{opt}}\) denotes the optimal CH visiting sequence, and \(\mathcal{P}_{\mathrm{opt}}\) represents the corresponding set of selected waypoints. The AUV's surface start and end positions, \(S_{s}\) and \(S_{f}\), which align with the USV's start and end positions, are determined from the first and last waypoints in \(\mathcal{P}_{\mathrm{opt}}\), respectively. These surface positions are obtained by setting the \(z\)-coordinates of the respective waypoints to zero, ensuring they lie on the water surface. Consequently, the USV is positioned directly above the AUV's initial waypoint at mission start and above the final waypoint at mission end, thereby completing the construction of the optimal trajectory. It is important to note that, while the ascent segment does not influence the optimization outcome, a post-processing correction may be applied if the residual VoI is to be evaluated over the entire mission duration, from the USV's start to end positions. The decay incurred during this final vertical segment can then be incorporated by adjusting the residual VoI based on the arrival time at the last waypoint and the known ascent duration. To address the high complexity of exploring all CH visit permutations and waypoint combinations, this paper applies a pruning approach based on an estimated upper bound of the remaining residual VoI. The idea follows the principles presented in [40; 41] and enables the forward DP algorithm to discard unpromising solutions early in the recursion. As a result, the computational burden is significantly reduced without compromising optimality. At stage \(i\), \(J(i,\;q)\) is defined as the total residual VoI accumulated after the AUV has visited CHs \(s(1),s(2),\ldots,s(i)\) and is currently located at waypoint \(q\in\mathcal{Q}_{s(i)}\).