# 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  
To solve the trajectory planning problem defined in (13), this work proposes a forward DP approach that maximizes the total residual VoI collected during the mission. The method simultaneously determines the optimal sequence for visiting the \(M\) CHs and selects one waypoint per CH from a candidate set located along its horizontal communication circle of radius \(\rho_{i}\). It systematically explores all feasible combinations of CH visiting orders and waypoint assignments while accounting for travel time, data degradation, and AUV motion constraints. A complete summary of the algorithm is provided in Algorithm 1. Given each combination \((\Phi,\mathcal{P})\), the travel time between consecutive waypoints is computed using the kinematic model in (3) and the path design strategy described in the next section. In this work, the residual VoI is evaluated over the time interval beginning with the AUV's arrival at the first CH and ending upon its return to the USV at the end of the mission. Accordingly, the forward DP algorithm searches for the optimal waypoint sequence and selection that maximizes the total residual VoI over this operational window. The core of the proposed solution is the forward DP approach that incrementally constructs the optimal trajectory. The use of a forward DP formulation is essential in this context, as the residual VoI associated with each CH progressively decays over time. Since the reward collected at each waypoint directly depends on its visitation time, the algorithm must traverse the decision space in the same direction as time progresses. This forward traversal enables accurate tracking of elapsed time and proper application of the corresponding VoI decay at each stage. A similar forward DP approach has also been employed in [24]. In this paper, the aim is to evaluate the residual VoI collected from the first CH to the USV's final position. However, the forward DP procedure is initiated from the AUV's surface start location \(S_{s}\) and progresses through the visitation sequence, terminating at the final CH. This modeling choice is justified by the symmetry in vertical travel time between the descent from \(S_{s}\) and the ascent to \(S_{f}\). Specifically, these segments are represented as vertical motions at a constant heave speed between the surface \(z=0\) and the operational depth \(z=z_{d}\), starting from and ending at waypoints that share the same horizontal coordinates as \(S_{s}\) and \(S_{f}\), respectively. As this vertical traversal time remains constant across all trajectory candidates, it results in a uniform decay period for this portion of the mission. This symmetry ensures a consistent basis for evaluating and comparing all candidate trajectories. Given the permutation \(\Phi=(s(1),s(2),\ldots,s(M))\), which defines the order of visiting the \(M\) CHs, the algorithm constructs a DP table \(J\left(i,\ q_{l_{s(i)}}\right)\). Here, \(i\in\{1,2,\ldots,\ M\}\) denotes the current stage, and \(q_{l_{s(i)}}\) is a candidate waypoint on \(\mathcal{C}_{s(i)}\) around CH \(s(i)\). The value \(J\left(i,\ q_{l_{s(i)}}\right)\) stores the maximum cumulative residual VoI collected up to CH \(s(i)\) when the AUV arrives at waypoint \(q_{l_{s(i)}}\). To keep the notation simpler, we use \(J(i,\ q)\) to represent \(J\left(i,\ q_{l_{s(i)}}\right)\), where \(q\in\mathcal{Q}_{s(i)}\). At stage \(i=1\), the residual VoI for each candidate waypoint \(q\in\mathcal{Q}_{s(1)}\) is determined based on the travel time from the initial point \(S_{s}\). Note that if \(q=\left(x_{q_{s(1)}},y_{q_{t(1)}},z_{d}\right)\), then the corresponding surface starting point is \(S_{s}=\left(x_{q_{s(1)}},y_{q_{t(1)}},0\right)\). The arrival time at \(q\), denoted by \(t_{q}\), is computed as the time taken to travel from \(S_{s}\) to \(q\), i.e., \(t_{q}=t_{s\to q}\). This arrival time is then used to evaluate the residual VoI at \(q\).