The Traveling Salesman Problem and orienteering for kinodynamic vehicles

The Traveling Salesman Problem is a major foundational problem in the fields of Computer Science, Operations Research, and Applied Mathematics, in which an agent wants to visit a set of target points with the shortest path possible. This problem is of the highest interest both theoretically in practice. When the agent is a vehicle whose trajectory must satisfy a set of dynamic constraints and the target points are distributed over a continuous space, this problem is especially relevant to robotics. Although this problem is considered computationally intractable to solve precisely, in many settings a good approximate path can be computed efficiently. We study the case where the target points are distributed independently at random and ask how the length of the optimal tour grows as the number of such target points increases, a question which has attracted interest from both the robotics and motion planning community and the applied probability community; however, there has been little interaction between the two communities on this problem. By combining the approaches developed independently by these two communities, we re-derive the most general and powerful results with a simplified method. We then demonstrate the power of our method by extending it to show novel stronger results for an important sub-class of vehicles, as well as novel results for an alternative setting in which the target points are distributed by an adversary rather than at random.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2017

Author dc:creator

• Adler, Aviv

Advisor dc:contributor.advisor

• Sertac Karaman.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/113975

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/113975