Online and Decentralized Algorithms for "Horsefly" Problems
Abstract
Short Work Statement:The proposed research will develop efficient algorithms for a class of vehicle-routing problems.ObjectiveThe objective of this project is to develop new algorithms for solving what we call a type of vehicle-routing problem with online and decentralized characteristics. The problems of interest are those in which a large vehicle serves as a mobile base for a fleet of small vehicles, and the objective is to determine a coordinated routing strategy for the large and small vehicles. As a unifying theme throughout this project, the PI will focus on problems in which the problem parameters change over time as new information is collected.ApproachThese routing problems are, in general, at least as hard as the Traveling Salesman Problem (TSP), and include it as a special case. Because of this resemblance, the PI expects that many existing algorithms for the TSP will have natural counterparts for these type of routing problems. A few examples of such heuristics include the classes of k-OPT local search algorithms, the Lin-Kernighan algorithm, simulated annealing, and the Christofides algorithm. The proposed research will attempt to extend these TSP algorithms to the more general case. The research will include asymptoticanalysis of the algorithms. The PI will also look at special cases, such as the Euclidean version of the problem, and attempt to develop polynomial-time approximation schemes for these problems.Overall Merits and ONR Mission RelevanceThe PI has formulated a new class of optimization problems that has direct relevance to mission planning for UxVs. The PI will develop new innovative and efficient algorithms for this new class of problems.The primary application of the proposed research is in designing control policies for routing unmanned aerial vehicles (UAVs), micro air vehicles (MAVs), unmanned underwater vehicles (UUVs), or sensors in a geographic region.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141612724
Entities
People
- John Gunnar Carlsson
Organizations
- Office of Naval Research
- United States Navy
- University of Southern California