Accession Number:

AD1004470

Title:

Approximation Algorithms for the Dubins Traveling Salesman Problem

Descriptive Note:

Technical Report

Corporate Author:

Massachusetts Institute of Technology Cambridge United States

Personal Author(s):

• Le Ny,Jerome
• Feron,Eric

Report Date:

2005-06-01

Pagination or Media Count:

11.0

Abstract:

Computing good TSP tours efficiently is of interest in the area of aerial surveillance. As we are increasingly interested in developing autonomous vehicles, the question of how these vehicles should behave usually leads to optimizing a given objective function, for example minimizing the distance traveled when the task is to explore a set of locations. An important difficulty arises, however, when the problem involves planes, underwater vehicles, cars and other vehicles with significant dynamics the paths obtained from algorithms solving the Euclidean TSP are infeasible. Kinodynamic planning refers to the path planning problem when the kinematic constraints of the vehicle are taken into account. The methods developed in this field aim at finding a trajectory from an initial position and configuration to a final position and configuration, usually while avoiding potential obstacles. In this paper, we study a different problem. We want to optimize trajectories visiting a specified set of points, but the configuration of the vehicle at these points is free as long as the kinematic constraints are satisfied.

Descriptors:

• APPROXIMATION(MATHEMATICS)
• REMOTELY PILOTED VEHICLES
• MATHEMATICAL PROGRAMMING
• algorithms
• TURNING FLIGHT
• robots

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE