On the Dubins Traveling Salesperson Problems: novel approximation algorithms

This paper proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins vehicle through n points on the plane. By Dubins vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order n 2/3. Additionally, we consider the following dynamic scenario: given a stochastic process that generates target points over time, how does one steer the Dubins vehicle to stabilize the system, in the sense that the number of unvisited targets does not diverge over time? For this scenario, we propose the first known receding-horizon strategy which is indeed stabilizing and whose performance is within a constant factor from the optimum, for all target generation rates. Download: Bibtex: @INPROCEEDINGS{ Savla-RSS-06, AUTHOR = {K. Savla and E. Frazzoli and F. Bullo}, TITLE = {Constant-factor approximation algorithms for the Traveling Salesperson Problem for Dubins' vehicle}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2006}, ADDRESS = {Philadelphia, USA}, MONTH = {August}, DOI = {10.15607/RSS.2006.II.038} }