On the Stochastic TSP for the Dubins Vehicle

Abstract

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2/3</sup> (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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2/3</sup> .