On the Curvature-Constrained Traveling Salesman Problem

Abstract

We study the traveling salesman problem for a Dubins car. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. In particular, the approximation ratio achievable by any algorithm that always follows the order optimal for the Euclidean metric is W(n). We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. I. INTRODUCTION In an instance of the traveling salesman problem (TSP) we are given the distances dij between any pair of n points. The problem is to find the shortest tour visiting every point exactly once. We also call this problem the tour-TSP to distinguish it from the path-TSP, where the requirement that the vehicle must start and end at the same point is removed. This famously intractable problem is often encountered in robotics and typically solved by the higher decision-making levels in the common layered controller architectures. The dynamics of the robot are usually not taken into account at this stage and the mission planner might typically chose to solve the TSP for the Euclidean metric (ETSP), i.e., the distances dij represent the Euclidean distances