Abstract
Autonomous marine vehicles are increasingly vital for oceanographic research and defense. However, planning time- and energy-optimal paths in stochastic, dynamic ocean environments is computationally intensive. This paper presents an end-to-end GPU-accelerated framework that models and solves Markov Decision Processes (MDPs) for path planning. By leveraging reduced-order modeling, sparse matrix optimizations, and a novel neighboring sub-grid concept, the proposed algorithm achieves a 600–1000x speedup over traditional CPU implementations. This performance allows for high-fidelity, real-time path planning in complex, uncertain environments.
Introduction: The Challenge of Ocean Navigation
Autonomous Underwater Vehicles (AUVs) must navigate environments where strong, unpredictable currents can significantly impact mission success and energy consumption. To operate effectively, these vehicles require path-planning algorithms that can account for environmental uncertainty. The Markov Decision Process (MDP) provides a robust framework for such sequential decision-making. However, the "curse of dimensionality" often makes MDPs computationally prohibitive for large-scale, real-time ocean missions. Traditional CPU-based solvers can take over 13 hours to compute a single optimal policy, rendering them impractical for on-board adjustments.
Methodology: GPU-Accelerated MDP Modeling
To overcome these computational barriers, we developed a framework using NVIDIA’s CUDA platform to parallelize both the model-building and solving phases of the MDP.
Model Building and Solving
The algorithm first computes the transition probabilities—the likelihood of a vehicle moving from one state to another given uncertain currents—and expected rewards. It then solves the MDP using Value Iteration to find the optimal policy.
As shown in the figure above, the problem involves navigating a continuous field (A) while harvesting energy from stochastic scalar fields (e.g., solar radiation). This is discretized into a grid (B) where transitions between cells $s$ and $s'$ are calculated based on vehicle velocity $u$ and environmental current $v$.
Technical Innovations for Memory Efficiency
GPUs offer massive parallelization but have limited global memory. We implemented several strategies to manage this:
- Reduced-Order Representation: Instead of storing thousands of full-resolution ocean flow realizations, we use Dynamically Orthogonal (DO) field equations to represent the environment using a mean field and dominant modes.
- Neighboring Sub-grids: We limit transition calculations to a small sub-grid reachable within a single time step, drastically reducing the search space.
- Sparse Matrix Optimization: The state transition matrix is highly sparse; our algorithm leverages this to minimize memory footprint and accelerate the solver.
Key Insights: The "Mean" Shortcut
A significant theoretical contribution of this work is the proof that for energy-harvesting missions, the expected one-step reward can be calculated using only the mean of the stochastic scalar field. This eliminates the need to process thousands of individual energy-field samples, providing a massive reduction in both computational effort and memory usage without sacrificing accuracy.
Results and Performance
The framework was tested on a simulated Stochastic Double-Gyre Ocean Flow, a standard benchmark for chaotic fluid dynamics.
- Speedup: The GPU implementation achieved a 600x to 1000x speedup compared to CPU versions. Missions that previously required hours of computation were completed in approximately one minute.
- Scalability: The system successfully managed spatio-temporal grids with up to 10 million states.
- Versatility: The planner effectively optimized for multiple objectives, including time-minimization, energy-minimization, and net-energy-optimal paths (balancing consumption with harvesting).
Conclusion and Future Directions
This GPU-accelerated framework represents a significant step toward real-time, autonomous decision-making in the ocean. By reducing planning latency from hours to seconds, it enables AUVs to adapt to changing conditions dynamically. Future work will focus on integrating this "offline" planner into a fully closed-loop system and incorporating more complex vehicle dynamics to handle highly turbulent flows.
Summary updated