GPU-accelerated Optimal Path Planning in Stochastic Dynamic Environments

Rohit Chowdhury, Deepak Subramani

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.

Conceptual overview of path planning in stochastic environments (A) and the discretized MDP transition model (B).

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:

  1. 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.
  2. Neighboring Sub-grids: We limit transition calculations to a small sub-grid reachable within a single time step, drastically reducing the search space.
  3. 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

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{chowdhury2021gpu,
  author = {Rohit Chowdhury and Deepak Subramani},
  title = {{GPU-accelerated Optimal Path Planning in Stochastic Dynamic Environments}},
  journal = {IEEE Journal of Oceanic Engineering},
  year = {2021},
  url = {https://openreview.net/forum?id=jtuwPFHMYv},
}
Figure