Optimal Path Planning of Autonomous Marine Vehicles in Stochastic Dynamic Ocean Flows using a GPU-Accelerated Algorithm

Rohit Chowdhury, Deepak N. Subramani

Abstract

Autonomous marine vehicles (AMVs) are critical for ocean exploration, but navigating them efficiently through stochastic, dynamic currents remains a significant computational challenge. This paper introduces a GPU-accelerated algorithm that solves Markov Decision Processes (MDPs) for path planning 600–1000 times faster than traditional CPU methods. By implementing memory-efficient techniques like reduced-order modeling and sparse matrix leveraging, the framework enables real-time, energy-optimal navigation in complex environments.

Introduction: The Challenge of Marine Navigation

Navigating an autonomous underwater vehicle (AUV) is inherently difficult due to chaotic ocean currents that often exceed the vehicle's own propulsion capabilities. To find the most efficient path—whether minimizing time or energy—planners must account for environmental uncertainty.

Conceptual diagram of an AUV path from start ($x_0$) to goal ($x_f$) through a stochastic environment.

The gold standard for decision-making under such uncertainty is the Markov Decision Process (MDP). However, the "curse of dimensionality" typically makes MDPs for 3D ocean environments computationally prohibitive, often requiring over 13 hours on a modern CPU for a single mission plan. This latency makes real-time, on-board re-planning impossible in dynamic conditions.

Methodology: GPU-Accelerated MDPs

To overcome these hurdles, we developed an end-to-end GPU-accelerated pipeline using NVIDIA’s CUDA platform. The approach discretizes the continuous ocean environment into a spatio-temporal grid, where each cell represents a state.

Discretization of the environment into cells ($s$) and the transition to a new state ($s'$) based on action ($a$) and ocean flow.

The pipeline consists of two primary phases:

  1. Model Building: Computing transition probabilities ($P$) and expected rewards ($R$) for every state-action pair. This process is "embarrassingly parallel," as each calculation is independent.
  2. MDP Solving: Finding the optimal policy using a parallelized Value Iteration algorithm.

To fit these massive computations into limited GPU memory, we introduced several innovations:

  • Reduced-Order Modeling: Using Dynamically Orthogonal (DO) equations to represent complex flows as a mean field plus dominant modes.
  • Neighboring Sub-grids: Limiting the transition search space to reachable nearby cells, drastically reducing the size of the transition matrix.
  • Sparse Matrix Leveraging: Storing only non-zero transition probabilities.
  • Mean Field Proof: Mathematically proving that the mean of a stochastic energy field is sufficient for calculating expected rewards in energy-harvesting missions, bypassing full stochastic integration.

Results and Performance

The algorithm was benchmarked using a stochastic double-gyre ocean flow simulation with 5,000 realizations. The GPU implementation achieved a staggering 600x to 1,000x speedup over serial CPU implementations. This performance shift moves MDP-based planning from an offline pre-computation task to a practical tool for real-time, on-board AUV decision-making.

The system successfully demonstrated three mission types:

  • Time-Optimal: Leveraging currents to reach goals faster.
  • Energy-Optimal: Minimizing battery consumption by avoiding resistance.
  • Net-Energy-Optimal: Actively seeking "sunny patches" (stochastic scalar fields) to recharge via solar harvesting while en route.

Conclusion

By drastically reducing computation time, this GPU-accelerated framework allows AUVs to adapt to changing ocean conditions in real-time. Future work will focus on closed-loop routing, where the vehicle updates its internal ocean model based on live sensor data to refine its path mid-mission, further enhancing the autonomy and reliability of marine robotic systems.

Summary updated

Abstract

Autonomous marine vehicles play an essential role in many ocean science and engineering applications. Planning time and energy optimal paths for these vehicles to navigate in stochastic dynamic ocean environments is essential to reduce operational costs. In some missions, they must also harvest solar, wind, or wave energy (modeled as a stochastic scalar field) and move in optimal paths that minimize net energy consumption. Markov Decision Processes (MDPs) provide a natural framework for sequential decision-making for robotic agents in such environments. However, building a realistic model and solving the modeled MDP becomes computationally expensive in large-scale real-time applications, warranting the need for parallel algorithms and efficient implementation. In the present work, we introduce an efficient end-to-end GPU-accelerated algorithm that (i) builds the MDP model (computing transition probabilities and expected one-step rewards); and (ii) solves the MDP to compute an optimal policy. We develop methodical and algorithmic solutions to overcome the limited global memory of GPUs by (i) using a dynamic reduced-order representation of the ocean flows, (ii) leveraging the sparse nature of the state transition probability matrix, (iii) introducing a neighbouring sub-grid concept and (iv) proving that it is sufficient to use only the stochastic scalar field's mean to compute the expected one-step rewards for missions involving energy harvesting from the environment; thereby saving memory and reducing the computational effort. We demonstrate the algorithm on a simulated stochastic dynamic environment and highlight that it builds the MDP model and computes the optimal policy 600-1000x faster than conventional CPU implementations, making it suitable for real-time use.
BibTeX
@article{chowdhury2021optimal,
  author = {Rohit Chowdhury and Deepak N. Subramani},
  title = {{Optimal Path Planning of Autonomous Marine Vehicles in Stochastic Dynamic Ocean Flows using a GPU-Accelerated Algorithm}},
  journal = {IEEE Journal of Oceanic Engineering},
  year = {2021},
  url = {https://openreview.net/forum?id=jtuwPFHMYv},
}
Figure