Discrete optimization methods to determine trajectories for Dubinsʹ vehicles

Dubinsʹ vehicles describe a twice differentiable curve of bounded curvature. In this work we present an algorithm for the Traveling Salesman Problem for Dubinsʹ vehicles. In our approach, we propose using a version of the Traveling Salesman Problem that minimizes both distance and direction change angles to determine the tour specifying the order in which the points should be visited. In order to calculate the point-to-point Dubinsʹ path we rely on a result by Dubins, and apply a shortest path algorithm on a discretized search space. Results indicate that the new algorithm obtains better solutions than the ones found in the literature in similar computation times.