On the Stochastic TSP for the Dubins Vehicle

In this paper, we study the stochastic travelling salesperson problem for a vehicle that is constrained to move forwards with a bound on the minimum turning radius. For n uniformly distributed targets, it is known that the expected length of the optimal tour has a lower bound that is kn^2/3 (where k is a constant that depends on the geometry of the area). We design a novel algorithm that performs within a constant factor of that lower bound. This proves that the expected length of the optimal tour of the Stochastic Dubins Travelling Salesperson Problem (SDTSP) is of the order of exactly n^2/3.