Efficient Optimal Planning in non-FIFO Time-Dependent Flow Fields

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.

I. Introduction

Many minimum-time planning problems in robotics in-herently involve time-costs that are non-static. In terms of finding shortest paths on graphs, this means that edge traversal time is not a scalar value, but instead is a function that varies over time. The importance of developing shortest path algorithms for non-static travel times is well recognised, and somewhat surprisingly, has been studied for over 50 years [2]. In comparison to static shortest path problems, progress in developing a theoretical understanding of the time-dependent shortest path (TDSP) problem has proved far more elusive. Our goal is to explore relatively recent theoretical results in an effort to develop practical algorithms for robotics applications.