On the Dubins Traveling Salesperson Problems: novel approximation algorithms
Ketan Savla, Emilio Frazzoli, Francesco Bullo · 2006
In this paper we study minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction. Motivated by autonomous aerial vehicle applications, we consider the Traveling Salesperson Problem for the Dubins vehicle (DTSP): given n points on a plane, what is the shortest Dubins tour through these points and what is its length? Specifically, we study a stochastic version of the DTSP where the n targets are randomly sampled from a uniform distribution. We show that the expected length of such a tour is of order at least n 2/3 and we propose a novel algorithm yielding a solution with length of order n 2/3 with high probability. Additionally, we study a dynamic version of the DTSP: given a stochastic process that generates target points, is there a policy which guarantees that the number of unvisited points does not diverge over time? If such stable policies exist, what is the minimum expected time that a newly generated target waits before being visited by the vehicle? We propose a novel stabilizing algorithm such that the expected wait time is provably within a constant factor from the optimum.