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.
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.
The pipeline consists of two primary phases:
- 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.
- 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