# Robotics: Science and Systems II

### On the Dubins Traveling Salesperson Problems: novel approximation algorithms

*K. Savla, E. Frazzoli, F. Bullo*

**Abstract:** 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.

**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} }