Track: Operations Research

Abstract

We consider computation of deterministic shortest paths for ships in the presence of obstacles in two-dimensional terrains considering the ship’s turning dynamics. Our goal is to allow for flexible turn angles using the idea of large-adjacency grids (LAGs). Such grids are generalization of the 8-adjacency grids to 8k-adjacency grids where k is a positive integer. Due to their adjacency structure, LAGs allow for higher degrees of flexibility in modeling of turn constraints. In particular, larger k values allow for even more flexibility, though at the cost of increased computational burden. Our approach is specifically designed for resolution-independent discretization of the navigation area and it is optimal with respect to the underlying LAG discretization. Our methodology also allows for asymmetric minimum left and right turn radii as well as turn speeds that vary as a function of the turn angle which requires non-trivial changes to the underlying LAG in order to preserve optimality. We demonstrate our methodology on a ship navigation example where we compare turn-constrained/ unconstrained and optimal/ suboptimal paths for different k values. We also present a proof-of-concept in a full-mission ship handling simulator where we compare the smoothened optimal path against the actual ship path inside the simulator.