Wake-Informed 3D Path Planning for Autonomous Underwater Vehicles Using A* and Neural Network Approximations

Node-based methods, such as the A* algorithm, are widely used due to their ability to find optimal paths in discretized environments [13]. Node based methods typically operate on a grid or graph representation of the environment and consider factors such as travel time, energy consumption and obstacle avoidance. Sampling-based methods, like Rapidly-exploring Random Trees (RRT) and Probabilistic Roadmaps (PRM), are particularly useful in high-dimensional spaces and can handle complex constraints [14, 15]. The sampling-based methods are effective in real-time applications due to their probabilistic completeness and ability to find feasible paths quickly, which some computationally intensive methods, such as bioinspired methods, can struggle with. The bioinspired algorithms, such Ant Colony Optimization and Genetic Algorithms, mimic natural processes to find efficient paths [16, 17]. These methods are advantageous in handling dynamic environments and optimizing multiple objectives simultaneously, but are not guaranteed to provide the optimal path in all cases.

Within each path planner, multiple effects can be modeled or accounted for. For the operation of underwater vehicles, environmental effects are important. The environment that an AUV exists in can affect its ability to safely or effectively navigate. Previous works have incorporated a range of effects, seeking to produce an informed planner. These have included the inclusion of ocean currents to help identify optimal time and energy optimal routes [18, 4, 19]. However, the dynamic current effects are often incorporated using simplified or 2D representations of flow fields. Garau et al. [13] presented an A* path planning algorithm that considers spatially variable current fields, but this field was limited to 2D, neglecting the 3D complexity of real flow structures. Similarly, Petres et al. [12] proposed a method that incorporates ocean currents into path planning but relies on simplified 2D current models.

Some research has extended the 2D effects in path planning to 3D. This has primarily been to account for depth variations and 3D obstacles [20, 21]. Zadeh et al. [20] developed a 3D path planning method based on ocean currents and differential evolution algorithms but did not fully incorporate complex hydrodynamic effects directly. Zeng et al. [22] sought to extend 2D current data to three dimensions, undertaking this by simplified linear approximations of the 2D current-only flow surface, extended into the depth axis. Li and Yu [21] proposed a significantly more detailed approach that included current structures, travel distance and object constraints in a 3D underwater environment with ocean currents, yet it again assumed a simplified current flow field and did not include wake structures from the objects or vehicles in the field.

For underwater applications, and specifically those with two or more interacting vehicles, an understanding of the best path through a fully realized 3D field is important. These operations are common and include, but are not limited to launch and recovery, formation flying and multi-vehicle cable/pipe inspection underwater. In these applications, the 3D flow field, wake structures and shed hydrodynamics from vehicles may pose control, safety and energy efficiency effects that are important to account for [23].

To date, limited research has sought to account for these effects within a path planner that incorporates full 3D hydrodynamic models, including the wake structures of nearby vessels. Existing methods either simplify the flow field in relation to its dimensionality (3D to 2D), include only the current, avoiding turbulent regions altogether, or use approximated hydrodynamic models [24, 25]. These simplifications may not accurately account for dynamics of importance in close proximity operations, such as berthing. Research focusing on UAV navigation in turbulent 3D aerial domains using the A* algorithm opted to completely avoid turbulent regions to ensure flight safety [26]. When conducting close proximity operations between vehicles, such as docking or formation keeping, avoiding these regions is not always a practical option as it can limit the possible safe approach trajectories that the vehicle can employ.

Building on these gaps, it is theorized that a machine learning-based planner, trained on trajectories generated by a high-fidelity A* planner, could learn to replicate or closely approximate the performance of optimal solutions. Such an approach would enable the rapid prediction of feasible, energy-efficient paths without the need for computationally expensive online searches, potentially bringing real-time 3D wake-informed navigation within reach.

This paper makes three primary contributions, namely it:

1. 1.

   proposes a wake-informed A* path planning algorithm that integrates full 3D hydrodynamic data, including complex wake structures, to achieve more energy-efficient and safer AUV navigation. Bridging the gap between simplified flow models and the complex realities of 3D underwater environments is crucial for operations involving significant wake effects [1, 2].

2. 2.

   introduces a machine learning framework trained on wake- and current-informed A* solutions, enabling rapid trajectory generation that approximates near-optimal paths in real-time, levering existing techniques for ML informed planning [27, 28].

3. 3.

   develops a robust set of metrics to holistically evaluate energy consumption, path length, turbulence exposure, and computational efficiency, advancing the understanding of AUV path planning performance in complex 3D flows.

The environment is first discretized into a three-dimensional grid $G\subset\mathbb{Z}^{3}$, where each cell (voxel) represents a discrete location in 3D space. The grid dimensions are defined to be ($[1,128],\ [1,128],\ [1,128]$) representing the 3D $128^{3}$ grid structure. Each individual cell in the grid corresponds to a node $n\subset G$. These nodes are connected to their neighbors based on a 26-connected grid. This considers movement in all directions: up, down, left, right, forward, backward and diagonals. For a node $n$, its set of neighbors $N(n)$ includes all adjacent nodes that are within the grid bounds and are traversable (not occupied by obstacles). The Euclidean distance (as denoted in Eq. (1)) is used to determine the distance between the current node n and the next node $n^{\prime}$.

The cost of moving from node n to the next node n’ is defined based on the energy required to overcome drag forces $F_{D}$, in addition to the distance traveled $d$. This can be determined, as the velocity throughout the local environment is known across all cells, and an approximation of the force of drag ($F_{D}$) can be made via Eq. (2).

Subsequently, $E_{D}$ is used to define the movement cost $c$ between two nodes $n$ and $n^{\prime}$ as seen below in $c(n,n^{\prime})$. A weighting term $\omega_{1}$ has also been introduced, which can be used to weight the importance of drag, which may be important, depending on the application.

Two variants of this path planner are used, where the velocity (v) from the drag equation has different levels of fidelity. In the uninformed path planner, only the current field velocity ($v_{C}$) is known. In the informed path planner, the wake structure and current field ($v_{T}$) of the velocity is known. The $A^{*}$ algorithm is then used to plan the path through the grid $G\subset\mathbb{Z}^{3}$ in accordance with Eq. (7) between a starting node and goal node within a traversable graph space. The heuristic function estimates the cost to reach the goal from the starting node using the average drag energy per unit distance and the aforementioned Euclidean distance. This heuristic is defined to be the sum of the average drag energy per unit distance ($\overline{E_{D}}$) within the grid $G\subset\mathbb{Z}^{3}$ and distance such that:

The heuristic is admissible as it will not overestimate the true minimum cost to reach the goal. This is ensured by the use of the average drag energy, which provides a reasonable estimate to guide the search within the domain, without comprising optimality. For each neighbor $n^{\prime}$ of the current node n, the algorithm calculates the tentative cost to reach $n^{\prime}$ via n and updates the scores accordingly. The nodes are stored in a priority queue order, sorted by their $f(n)=g(n)+h(n)$ values to ensure that the most promising nodes are explored first.

To assess the importance of knowing the wake structures, two variants of the planner will be assessed. The first variant, $P^{*}_{C}$ will only be informed of the current within the computational domain. The second variant, $P^{*}_{W}$, will be informed of both the current and the vehicle’s wake structure. $P^{*}_{W}$ will be applied to the flow field across a range of wake fields behind a large underwater vehicle. The current and wake dataset was generated from prior work by the authors and is comprised of high fidelity computational fluid dynamics (CFD) data interpolated onto the discrete grid $G\subset\mathbb{Z}^{3}$ [1] [2]. The data contains a local current from 0.10 m/s to 5.00 m/s in increments of 0.10 m/s. Additionally, a strong propeller wake is included, with wake structures at 0° to 60° degrees of separation, simulating a turn of the vehicle in question. This was done via the simulation of an INSEAN E1619 propeller. The wake free velocity field ($v_{C}$) containing only the current, will be the same field, with the wake structure’s components filtered out and only global current retained.

For the wake structure dataset, with local current from 0.10 m/s to 5.00 m/s in increments of 0.10 m/s and angles of incidence from 0° to 60° degrees of separation in increments of 5°, there are a total of 500 distinct flow conditions. For each flow condition, 36 trajectories are generated with starting positions that are uniformly disturbed on the aft face of the domain, behind the XLUUV. An example of this is provided in Fig. 3. This image shows how the uniformly distributed start locations are initialized in the domain, before trajectory determination. This process occurs 36 times for each 500 distinct flow conditions, resulting in a total of 18,000 paths being generated for each planner. The same start positions are used for both the wake-informed and current-informed planners, allowing for direct comparison across relevant metrics.

Energy capacity onboard AUVs remains a constant challenge, where small hull structures limit the physical size of battery systems, resulting in tightly constrained vehicles. It is important that the trajectories generated are assessed from an energy cost perspective, as well as the variance in energy cost, as these factors can have a significant effect on the viability of a given path. Additionally, when approaching a larger vessel, the wake structure shed by it can cause significant approach challenges, particularly with respect to effective control of the smaller vehicle [1] [2]. It is for this reason that the hydrodynamic effects should be assessed to determine the proportion of the trajectory where a control risk exists. We define this control risk to be both regions on the trajectory where there is a higher than expected flow speed, and where the velocity is fluctuating in the x, y or z direction.

To make this assessment, each generated path, $P$, is decomposed into a set of $N$ nodes such that:

Each node $n_{i}$ in the set corresponds to a 3-dimensional coordinate $(x_{i},y_{i},z_{i})$ in the grid. The velocity at node $n_{i}$ is $V(n_{i})$. $\tilde{v}$ denotes the median velocity of the entire grid, and $\sigma_{v}$ denotes the standard deviation of the velocities in the grid. These values are used to identify high velocity cells, where we define the high velocity cell threshold $v_{\text{threshold}}$ to be a function of the velocity field’s standard deviation $\sigma_{v}$:

After the velocity threshold for these cells is identified, the path $P$ is used to determine the number of cells along the trajectory that exceed this threshold. The number of high velocity cells is then summed over the trajectory, denoted by $N_{\text{high-velocity}}(P)$ and calculated via Eq. (11), where the cutoff threshold for a high velocity cell is denoted by the indicator function in Eq. (12) and given via $\delta_{\text{HV}}$.

To assess the fluctuations in velocity, or the turbulence along the path $P$, a similar method is applied. $D(n_{i})$ denotes the velocity disparity at a given node $n_{i}$. At any node where the disparity value is non zero, it is summed. This keeps track of the number of disparity cells along the path $P$, denoted by $N_{\text{disparity}}(P)$. This is determined via the application of Eq. (13). Again, the cutoff threshold for a velocity fluctuation cell is denoted by the indicator function $\delta_{\text{D}}$ defined as follows, using a non-zero offset $(\varepsilon=0.005)$ to ensure calculation robustness. This is provided in Eq. (14)

To determine the energy cost of a path, the drag force $F_{D}(n_{i})$ at a given node $n_{i}$, is obtained from the cost array. Then, for each segment between nodes $n_{i}$ and $n_{i+1}$, the Euclidean distance $d_{i}$ is calculated via the application of Eq. (1) and the force of drag determined via Eq. (2). These are then combined and determined for each cell along the trajectory, allowing for a path energy, denoted by $E(P)$, calculation via Eq. (15).

The total Euclidean distance (path length) along path $P$, denoted $L(P)$, is the sum of the distances between consecutive nodes where $d_{i}$ is as previously defined:

The path length in cells, denoted by $N_{\text{cells}}(P)$, is simply the number of nodes ($n$) on each given path:

To train the networks to predict the trajectories of the current and wake-informed A* planners, a dataset of their trajectories will be used. Each dataset consists of 18,000 trajectories generated by the wake-informed and current-informed A* planners counterparts, as described in Section 4.2. Each trajectory comprises up to 130 waypoints, with each waypoint represented by its three-dimensional coordinates $(x_{i},y_{i},z_{i})$. The input features for the neural network include the vehicle’s starting position $(x_{\text{start}},y_{\text{start}},z_{\text{start}})$, goal position $(x_{\text{goal}},y_{\text{goal}},z_{\text{goal}})$, flow speed $v\in[0.1,5.0]$ m/s, and flow angle $\theta\in[0^{\circ},60^{\circ}]$. The network output is a vector of sequential waypoint coordinates representing the predicted trajectory. Due to varying path lengths, all trajectories were padded to a fixed length of 130 waypoints, and a mask was applied during training to handle the variable lengths, that may be shorter than this length of 130 cells.

Both neural network architectures are fully connected feedforward networks, designed to regress the sequence of waypoint coordinates directly from the input features. The architecture consists of an input layer, two hidden layers and an output layer as detailed below:

• •

  Input Layer: Accepts an 8-dimensional input vector comprising the normalized starting position, goal position, flow speed, and flow angle.

• •

  $1^{st}$ Hidden Layer: 128 neurons with ReLU activation.

• •

  $2^{nd}$ Hidden Layer: 256 neurons with ReLU activation.

• •

  Output Layer: Outputs a 390-dimensional vector representing the flattened sequence of waypoint coordinates $(x_{i},y_{i},z_{i})$ for $i=1,\dots,130$.

The choice of layer sizes was determined empirically to balance model capacity and computational efficiency. ReLU activation functions were used to introduce non-linearity and mitigate the vanishing gradient problem [30]. A fully connected architecture was chosen for its simplicity and to serve as a baseline, ensuring that future studies can easily compare advanced architectures (e.g., RNNs, Transformers) against this initial model.

Both input features and output waypoint coordinates were normalized using the standard score as represented by Eq. (18).

The network was trained using the Adam optimizer [31] with a learning rate of $1\times 10^{-4}$. Adam was chosen for its adaptive learning rate capabilities and robustness in training deep neural networks. The batch size was set to 64, and the model was trained for 50 epochs. Weight initialization was performed using the Xavier initialization method to ensure stable gradients at the start of training [32].

To prevent overfitting, three regularization techniques were implemented:

• •

  Early Stopping: The validation loss was monitored, and training was halted if the loss did not improve for a set number of epochs (10).

• •

  Dropout: Although not included in the final model, dropout layers were experimented with during hyperparameter tuning but did not yield significant improvements.

• •

  L2 Regularization: L2 weight decay was applied implicitly via the Adam optimizer’s default settings.

The model’s performance was evaluated using the root mean squared error (RMSE) between the predicted and true waypoint coordinates on the validation set only. Additionally, the trajectories generated by the neural network were assessed using the same metrics as the A* planners, including total energy consumption, path length, number of high-velocity cells, and number of disparity cells, as defined in Section 4.3 and presented in Section 6.

The neural network was implemented using PyTorch [33], a widely used deep learning framework that provides dynamic computation graphs and efficient GPU acceleration. Training was performed on a workstation equipped with an NVIDIA RTX2070 GPU to expedite the computational process.

While the neural network provides rapid trajectory predictions, it inherently relies on the quality and diversity of the training data. As the model is trained on trajectories generated by the A* planners, its performance is directly tied to the scenarios represented in the training set. Extrapolation to unseen flow conditions or starting positions not represented in the training data may result in decreased accuracy, and will be assessed within this analysis.

Our approach aligns with recent trends in leveraging deep learning for path planning tasks [27, 28]. Unlike methods that use convolutional neural networks (CNNs) to process occupancy grids or reinforcement learning to learn navigation policies, our model directly predicts the sequence of waypoints, simplifying the integration into existing navigation systems.

Energy efficiency is critical in AUV operation due to their limited onboard energy resources. The wake-informed A* planner ($W.I._{A*}$) consistently demonstrates the lowest total energy expenditure across all speed ranges, as shown in Table 1. At the lowest speed range of 0.1–0.5m/s, $W.I._{A*}$ achieves an average energy expenditure of 51.49 joules with a standard deviation of 52.82 joules, outperforming the current-informed A* planner ($C.I._{A*}$) by approximately 11.3%. This persists at higher speeds, with $W.I._{A*}$ maintaining lower energy consumption compared to the other models. At the maximum tested speed range of 4.0–5.0m/s, $W.I._{A*}$ records an average energy expenditure of 11,952.30 joules, 7.2% less than $C.I._{A*}$.

The neural network models, $C.I._{NN}$ and $W.I._{NN}$, based on their counterpart A* implementations, exhibit higher energy expenditures compared to their calculated A* trajectories. $W.I._{NN}$ performs better than $C.I.{NN}$, but does not match the energy efficiency of the wake-informed A* planner. The increased energy expenditure (ranging between 10.03–13.12%) in the neural network counterparts may be attributed to approximation errors inherent in learning-based approaches, where it remains challenging to capture the optimality of the A* algorithm in path planning, especially in the presence of complex wake structures. Provided in Fig. 4 is a depiction of the variation in standard deviation against speed and angle for both planners and networks. It can be seen that the current-informed NN has significant variation in path energy, indicating it may struggle to understand how best to traverse the domain, particularly at high speeds.

The path length metric ($L$) reflects the total distance traveled by the AUV along the planned trajectory. Shorter paths generally result in quicker LAR missions, for a given speed, but may traverse more hazardous areas. The current-informed A* planner ($C.I._{A*}$) achieves the shortest average path lengths across all speed ranges, with consistent trajectory lengths of 104.22–104.31m and a standard deviation of approximately 9.5m. This suggests that $C.I._{A*}$ is able to generate the most direct paths, but without considering wake structures and associated hazards. In contrast, the wake-informed A* planner ($W.I._{A*}$) shows slightly longer path lengths, averaging around 107 m, indicating that it deliberately avoids certain areas to minimize energy expenditure and exposure to high-velocity regions. The neural network models, particularly $C.I._{NN}$, exhibit significantly longer path lengths with higher variability. For example, $C.I._{NN}$ records an average path length of 133.27m in the 4.0–5.0m/s speed range, approximately 27% longer than $C.I._{A*}$. This suggests that the neural networks may not approximate the optimal path lengths as effectively, potentially leading to suboptimal routing. Fig. 5 provides an assessment of the median path length of the models against speed and angle. It can be seen that the A* current-informed method is the most consistent, with the A* wake-informed method also exhibiting similar performance. The neural networks result in a higher median path length, with suboptimal path generation at low speed and angles for the wake-informed NN.

Navigating through high-velocity cells poses increased risk and potential for energy expenditure, due to increased drag and control challenges associated with traversing the larger vehicle’s wake structure. The wake-informed A* planner ($W.I._{A*}$) exhibits the lowest average number of high-velocity cells encountered ($n{H,vel}$) across all speed ranges, as it has knowledge of the structures. At speeds between 0.5–1.0 m/s, $W.I._{A*}$ encounters an average of 2.73 high-velocity cells, significantly lower than $C.I._{A*}$ (7.32) on average. This indicates that $W.I._{A*}$ sufficiently avoids the high-velocity regions it is informed of, enhancing operational safety. Both neural network models exhibit less consistent performance in this metric. $C.I._{NN}$ is observed to reduce high-velocity cell encounters compared to $C.I._{A*}$, whilst $W.I._{NN}$ generally encounters more high-velocity cells than $W.I._{A*}$. This suggests that the neural networks may not fully capture the nuances of avoiding hazardous regions, possibly due to limitations in the training data or model capacity. Fig. 6 details the median number of high velocity cells encountered by each method. Similar performance is observed for the current-informed A* and NN, and the wake-informed NN. The wake-informed A* planner exhibits beneficial performance in comparison to the other models, with typically 0 - 5 cells encountered irrespective of speed and angle.

The turbulent cell count ($n_{turb.}$) reflects the number of cells along the trajectory where any velocity fluctuation occurs, which would pose an additional control challenge for the AUV. It should be noted that no thresholding is applied to this, so small and large fluctuations are treated equally. The current-informed A* planner ($C.I._{A*}$) records the lowest turbulent cell counts across all speed ranges, with an average of 31.29 cells in the 0.5–1.0 m/s range. The wake-informed models, both $W.I._{A*}$ and $W.I._{NN}$, exhibit higher turbulent cell counts. This suggests that while the wake-informed planners effectively avoid high-velocity cells, they may traverse areas with higher turbulence. One possible explanation is that in avoiding high-velocity wake regions, the wake-informed planners route the AUV through areas with greater velocity disparities. The neural network models again display higher turbulent cell counts compared to their A* counterparts, indicating a potential area for improvement in modeling turbulence avoidance.

Computational efficiency is critical for real-time path planning on resource-constrained AUVs. As shown in Table 1, the neural network models offer a significant advantage in computational time. The neural networks compute trajectories in approximately 0.30 milliseconds, whereas the A* planners require 37 to 43 seconds on average, depending on the method. This is a compute time reduction of approximately 5 orders of magnitude - a significant decrease. The wake-informed NN, $W.I._{NN}$, achieves the shortest computation time across all speed ranges, with an average of 0.29 milliseconds. The substantial reduction in computation time makes the neural network models highly optimal for real-time applications. This speed, however, comes at the cost of reduced path optimality compared to direct computation via A*, as evidenced by the higher energy expenditures and longer path lengths compared to both A* planners.