Multi-query TDSP for Path Planning in Time-varying Flow Fields
- Publisher:
- IEEE
- Publication Type:
- Conference Proceeding
- Citation:
- 2024 IEEE International Conference on Robotics and Automation (ICRA), 2024, 00, pp. 7005-7011
- Issue Date:
- 2024-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 1745300.pdf | Published version | 1.67 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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
Please use this identifier to cite or link to this item: