Efficient Optimal Planning in non-FIFO Time-Dependent Flow Fields
- Publisher:
- IEEE
- Publication Type:
- Conference Proceeding
- Citation:
- 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023, 2023-May, pp. 7844-7850
- Issue Date:
- 2023-07-04
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Efficient_Optimal_Planning_in_non-FIFO_Time-Dependent_Flow_Fields.pdf | Accepted version | 922.35 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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
Please use this identifier to cite or link to this item: