Many applications of path planning in time-varying flow fields, particularly in areas such as marine robotics and ship routing, can be modelled as instances of the time-varying shortest path (TDSP) problem. Although there are no known polynomial-time solutions to TDSP in general, our recent work has identified a tractable case where the flow is modelled as piecewise constant. Extending this method to allow for computational reuse in larger multi-query problems, however, requires additional thought. This paper shows that the piecewise-linear form of the cost function employed in previously work can be used to build an analogy of a shortest path tree, thereby enabling optimal concatenation of sub-problem solutions in the absence of an optimal substructure, and without uniform time discretisation. We present a framework for multi-query TDSP that finds an optimal path that passes through a defined sequence of waypoints and is computationally efficient. Performance comparison is provided in simulation that shows large (up to 100x) speedup compared to a naive approach. This result is significant for applications such as ship routing, where route evaluation is a desirable capability.

We propose an algorithm for solving the time-dependent shortest path problem in flow fields where the FIFO (first-in-first-out) assumption is violated. This problem variant is important for autonomous vehicles in the ocean, for example, that cannot arbitrarily hover in a fixed position and that are strongly influenced by time-varying ocean currents. Although polynomial-time solutions are available for discrete-time problems, the continuous-time non-FIFO case is NP-hard with no known relevant special cases. Our main result is to show that this problem can be solved in polynomial time if the edge travel time functions are piecewise-constant, agreeing with existing worst-case bounds for FIFO problems with restricted slopes. We present a minimum-time algorithm for graphs that allows for paths with finite-length cycles, and then embed this algorithm within an asymptotically optimal sampling-based framework to find time-optimal paths in flows. The algorithm relies on an efficient data structure to represent and manipulate piecewise-constant functions and is straightforward to implement. We illustrate the behaviour of the algorithm in an example based on a common ocean vortex model.

Systems of multiple low-cost, underactuated floats combined with fully actuated surface vessels can improve the scalability and cost-effectiveness of autonomous systems for marine science and environmental monitoring. Here, we consider a coordination problem where surface vessels must drop off floats at locations such that they are likely to drift to observe given points of interest, and later must pick up the floats for redeployment. We define the Multi-Vessel Multi-Float (MVMF) problem and present a hierarchical solution based on the Dec-MCTS algorithm. Our solution defines customised sampling, rollout, and action generation algorithms to accommodate the problem’s large search space and provide computational performance sufficient for practical application. We report analytical and simulation results that demonstrate the computational efficiency of our method and validate its behaviour in practical problems. These results immediately enable field experiments to progress the development of this exciting concept in multi-robot marine systems.

We present a path planning framework for marine robots subject to uncertain ocean currents that exploits data from ensemble forecasting, which is a technique for current prediction used in oceanography. Ensemble forecasts represent a distribution of predicted currents as a set of flow fields that are considered to be equally likely. We show that the typical approach of computing the vector-wise mean and variance over this set can yield meaningless results, and propose an alternative approach that considers each flow field in the ensemble simultaneously. Our framework finds a sequence of vehicle controls that minimises the root-mean-square error distance (RMSE) over the full set of ensemble-induced trajectories. The key to achieving computational efficiency in this approach is our use of Monte Carlo tree search (MCTS) with a specialised heuristic that improves convergence rate while preserving asymptotic optimality and the anytime property. We demonstrate our results using real ensemble forecasts provided by the Australian Bureau of Meteorology, and provide comparisons with the deterministic mean-based approach where we observe RMSE reductions of 92% and 43% in two example scenarios. Further, we argue that the framework can be used in a plan-as-you-go manner where ensemble forecasts change over time. These results help to introduce ensemble forecasts as a viable source of data to improve path planning in marine robotics.

We present an efficient approach for finding shortest paths in flow fields that vary as a sequence of flow predictions over time. This approach is applicable to motion planning for slow marine robots that are subject to dynamic ocean currents. Although the problem is NP-hard in general form, we incorporate recent results from the theory of finding shortest paths in time-dependent graphs to construct a polynomial-time algorithm that finds continuous trajectories in time-dependent flow fields. The algorithm has a hierarchical structure where a graph is constructed with time-varying edge costs that are derived from sets of continuous trajectories in the underlying flow field. We show that the continuous algorithm retains the time complexity and path quality properties of the discrete graph solution, and demonstrate its application to surface and underwater vehicles including a traversal along the East Australian Current with an autonomous marine vehicle. Results show that the algorithm performs efficiently in practice and can find paths that adapt to changing ocean currents. These results are significant to marine robotics because they allow for efficient use of time-varying ocean predictions for motion planning.