DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE