Doctoral Thesis: The Traveling Salesman Problem Under Dynamic Constraints
32-D667
Aviv Adler
Abstract:
The Traveling Salesman Problem (TSP) is a foundational problem in the fields of theoretical computer science and optimization in which an agent is tasked with visiting a set of n target locations (in any order) in the shortest amount of time, either on a graph or in a space. An important variant of the TSP is the Dynamic TSP (DTSP), in which the targets exist in a space where the agent’s trajectory must satisfy dynamic constraints (for instance, limited ability to accelerate or to turn). The DTSP arises naturally in many robotic motion planning problems, particularly in exploration, surveillance and reconnaissance, and is generally not amenable to the standard TSP approximation algorithms. An interesting and important question on this problem is the Dynamic Stochastic TSP (DSTSP): if the target points are distributed randomly, how does the length of the shortest tour (either in expectation or with high probability) grow with the number n of targets? This problem has been studied for a variety of common autonomous vehicle models, as well as certain broader classes of dynamic control systems.In this thesis, we present a novel proof that extends the known DSTSP order-of-growth results to a wider variety of dynamic systems, in particular to manifold workspaces, as well as two novel algorithms which achieve a constant-factor approximation of the optimal tour length with high probability. These new proofs and algorithms furthermore allow us to study not only the order-of-growth of the optimal tour length but also, for the important subset of ‘symmetric’ dynamics, to give explicit constant factors on both the upper and lower bounds that characterize the relationship between the dynamics, the target point distribution, and the optimal tour length. Finally, we extend these results to the non-stochastic adversarial case, in which the target points are chosen to maximize the optimal tour length.
Details
- Date: Thursday, December 15
- Time: 1:00 pm - 2:30 pm
- Category: Thesis Defense
- Location: 32-D667
Additional Location Details:
Thesis Supervisor: Professor Sertac Karaman
To attend via zoom, please contact the doctoral candidate at adlera@mit.edu