The Stochastic Traveling Salesman Problem and Orienteering for kinodynamic vehicles

Abstract

In the classic Traveling Salesman Problem (TSP), the objective is to find the shortest path that visits a set of target locations. This problem is embedded and essential in many planning problems that arise in robotics, particularly in the domains of exploration, monitoring, surveillance, and reconnaissance. In this paper we consider the Stochastic TSP for Dynamical Systems, where a vehicle with complex dynamics is tasked with visiting n random target locations. By borrowing techniques from the applied probability literature, which were used to study the related stochastic Orienteering problem (where the vehicle has to visit as many of the n points as possible with a path of fixed length), we simplify and extend the existing results for both the TSP and the stochastic Orienteering problems to cases where the target points can be picked up only when the vehicle is in a certain configuration (i.e. it is not enough simply to be on the target point). Specifically, we show that there is a special parameter γ of the dynamics of the vehicle, which governs the length of the TSP tour. The length of the shortest path will then be Θ(n(γ-1)/γ) with very high probability. For stochastic Orienteering, if the path must have length at most λ, the vehicle can pick up Θ(λn1/γ) with very high probability. We also provide simple and efficient path planning algorithms which achieve these bounds, and are therefore within a constant factor of the length of the optimal path with very high probability.