非FIFO時変流れ場における効率的な最適計画
Efficient Optimal Planning in non-FIFO Time-Dependent Flow Fields
FIFO仮定が成り立たない時変流れ場での時間依存最短経路問題を、辺の移動時間が区分的定数なら多項式時間で解けることを示し、サンプリングベースの枠組みに組み込んだ。
著者: James Ju Heon Lee, Chanyeol Yoo, Stuart Anstee, Robert Fitch
分類: cs.RO, cs.DS
原文アブストラクト
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 in addition to simpler graph-based examples.
