Asymptotic Constant-Factor Approximation Algorithm for the Traveling Salesperson Problem for Dubins Vehicle

Abstract

This article 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 n2/3.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 02, 2006
Accession Number
AD1005734

Entities

People

  • Emilio Frazzoli
  • Francesco Bullo
  • Ketan Savla

Organizations

  • University of California, Santa Barbara

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Binomials
  • California
  • Computations
  • Computer Science
  • Construction
  • Curvature
  • Engineering
  • Geometry
  • Motion Planning
  • Operations Research
  • Polynomials
  • Probability
  • Random Variables
  • Sequences
  • Vehicles

Readers

  • Aerial Unmanned Vehicle Swarm Micro Periodontal Dentistry.
  • Operations Research