In this thesis we study high-level trajectory planning for underpowered vehicles in spatially complex, 2D, time-varying flow fields. In particular, we consider a minimum time problem and a minimum energy problem. These problems are difficult because locally optimal trajectories abound and currents stronger than the vehicle can push it far off course. Nevertheless, globally optimal trajectories can be obtained by numerical solution of a dynamic Hamilton Jacobi Bellman (HJB) partial differential equation (PDE) for the time-varying optimal cost-to-go function---the gradient of which yields an optimal feedback control law. Locally optimal trajectories are associated with shocks---discontinuities in the gradient of the cost-to-go. Strong currents are associated with discontinuities in the cost-to-go itself. Existing work is primarily concerned with the proper capturing of shocks, and is mostly limited to weak, time-invariant flows.

But strong, time-varying flows play a large role in the real-life problem. Thus the characterization of solutions for realistic flows has involved significant experimentation with novel solution approaches. A key theme has been the complementary nature of Eulerian or semi-Lagrangian finite difference methods and Lagrangian particle methods. The former methods are associated with implicit front tracking methods such as Level Set Methods and Fast Marching, and rely on shock-capturing (e.g. Godunov) schemes. The latter methods are associated with explicit front tracking methods but compute particle trajectories in a higher-dimensional state-``costate'' space using the well-known Euler Lagrange ordinary differential equations; these are variants of the so-called ``extremal field'' method. Other themes include the use of adaptive grids and the dichotomy between backward-in-time methods for closed-loop optimal trajectories and forward-in-time methods for open-loop optimal trajectories.

In all cases, the resulting trajectories are globally optimal. First, we present a forward-in-time Lagrangian method that exploits a special property of minimum time control to obtain open-loop optimal trajectories, without actually solving the dynamic HJB equation. The algorithm proved highly dependent on adaptive remeshing of the Lagrangian marker particles along the tracked front and a rather complicated trimming procedure for local optima. Examples include a numerically defined strong, time-varying flow field from a model of the Adriatic Sea. Second, we present a backward-in-time semi-Lagrangian method on an adaptive triangle grid for the fixed final time minimum energy problem. The algorithm effectively transforms the optimal control problem into a point wise optimization problem, which we choose to solve exactly by keeping the discretizations first order in space and time.

In the end, there turn out to be fundamental limitations on the performance of this algorithm, due to the computational complexity of the point wise optimization problem. Third, we briefly present an idea for a coordinate transformation based on the Jacobian of the so-called flow map---the state at the fixed final time if one were to turn the control off. This suggests a greedy heuristic control scheme, which we compare to the minimum energy control. Finally, we conclude with a 1D proof of concept for a hybrid Lagrangian-Eulerian minimum energy algorithm that combines the best of the Lagrangian minimum time algorithm and the semi-Lagrangian minimum energy algorithms.