Construction of fastest curvature-constrained paths in direction-dependent media

This paper presents an algorithm that constructs a fastest curvature-constrained path in a direction-dependent environment for given initial and target locations and heading angles. The problem studied here is a generalization of the classical Dubins car problem, where the vehicle speed and minimum turning radius are assumed to be constant. This assumption is relaxed and the settings where the two parameters are arbitrary functions of the agent's heading angle are considered, such as a maneuvering sailboat for example. This paper is concerned with the extension and implementation of the authors' earlier results that establish the fastest path between two positions in the plane for a Dubins-like vehicle in a (possibly) anisotropic medium to be of the form CSCSC (or any subset of this word) where C denotes a sharpest turn and S denotes a straight line segment. While the authors' preceding work has derived the structure of a fastest path, the actual implementation of the results presents a significant challenge and remained unsolved. The main contribution of this paper is an algorithm that implements those results and illustrates several specific instances in which the results developed here can be applied. This work is particularly relevant for vehicles whose interaction with their surrounding environment creates direction-dependent dynamics, such as aerial or surface vehicles in wind or strong currents.