We present a Reinforcement Learning (RL) based framework for computing a dynamically adaptable policy that minimizes expected travel time of autonomous vehicles between two points in stochastic dynamic flows. This framework consists of three key components-

1. The data-driven dynamically orthogonal (DO) equations to obtain a reduced-order stochastic velocity field in the form of realizations.

2. The Hamilton-Jacobi level set partial differential equations that enables us to compute an exact time-optimal path for a given realisation.

3. Reinforcement Learning- a framework that allows an agent to learn good decision sequences through experiences.

The data-driven dynamically orthogonal (DO) equations are utilized to forecast the stochastic dynamic environment. For planning, a novel physics-driven online Q-learning is developed. First, the distribution of exact time optimal paths predicted by stochastic DO Hamilton-Jacobi level set partial differential equations. These paths are treated as good experiences for a Q-learning agent and are utilized to initialize the action value function (Q-value) and estimate a good initial policy. Next, the computed policy is adaptively refined as the agent encounters flow during a mission. For the adaptation, a simple Bayesian estimate of the environment is performed and the inferred environment is used to update the Q-values in an ε−greedy exploration approach. We showcase the new algorithm and elucidate its computational advantages by planning paths in a stochastic quasi-geostrophic double gyre circulation.

The figures on the left show a distribution of paths obtained by following two different policies in a stochastic, dynamic, double-gyre flow. In figure A, the policy was obtained using Dynamic Programming (used as a benchmark). In figure B, the policy was computed and updated using our proposed algorithm.

This work has been published in the DDDAS 2020 conference proceedings. Please find the complete paper here: "Physics-Driven Machine Learning for Time-Optimal Path Planning in Stochastic Dynamic Flows".

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 of 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.

The work has been published in the IEEE Journal of Oceanic Engineering and can be viewed here: "Optimal Path Planning of Autonomous Marine Vehicles in Stochastic Dynamic Ocean Flows Using a GPU-Accelerated Algorithm". A preprint of the same may be accessed here.

The importance of autonomous marine vehicles is increasing in a wide range of ocean science and engineering applications. Multi-objective optimization, where trade-offs between multiple conflicting objectives are achieved (such as minimizing expected mission time, energy consumption, and environmental energy harvesting), is crucial for planning optimal routes in stochastic dynamic ocean environments. The present paper extends our end-to-end GPU-accelerated single-objective Markov Decision Process path planner to compute optimal operating curves for multi-objective optimal planning. MDPs with scalarized rewards for multiple objectives are formulated and solved in idealized stochastic dynamic ocean environments with dynamic obstacles. Two simulated mission scenarios are completed to elucidate our approach and capabilities: (i) an agent moving from a start to target by minimizing travel time and net-energy consumption when harvesting solar energy in an uncertain flow; (ii) an agent attempting to cross a shipping channel with uncertain ship movement and flow. Optimal operating curves are computed in a fraction of the time that would be required for existing solvers and algorithms.

This work has been published in the MDPI Journal of Marine Science and Engineering and can be accessed here: "GPU-Accelerated Multi-Objective Optimal Planning in Stochastic Dynamic Environments"