טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentEpstein Chen
SubjectTraveling Salesman Problem for Dubins Vehicle
DepartmentDepartment of Industrial Engineering and Management
Supervisors Dr. Izack Cohen
Professor Tal Shima
Full Thesis textFull thesis text - English Version


Abstract

In this research, we study routing problems for a Dubins vehicle, i.e, a vehicle that is constrained to move in a constant speed along planar paths of bounded curvatures with a minimum turning radius without the ability to go backward. We are motivated by scenarios that include motion planning for unmanned aerial, marine and ground vehicles, just to name a few possible application outlets. This research deals with a variation of the traveling salesman problem (TSP)- the Dubins TSP (DTSP). In the DTSP the path length of a tour, during which a Dubins vehicle visits a set of targets in the plane once, has to be minimized. The heading angles at the targets are not constrained and can obtain any value in the range [0,2π]. This work focuses on solving the DTSP with heading discretization. We discretize the original continuous problem and constrain the number of possible heading angles at each target to be finite. We call this problem the discretized Dubins traveling salesman problem (DDTSP). We explicitly formulate it as an integer optimization problem, and use this formulation to solve DDTSP for small scenarios (small number of targets and small discretization levels). Moreover, we present an approach which solves DDTSP for large scenarios.

Then we develop performance bounds as a function of the discretization level and the number of targets. The inclusion of a discretization level provides an opportunity to achieve tighter bounds, compared to previous work. The suggested linkage between discretization level, number of targets, and performance may guide discretization level choices for the solution of motion planning scenarios. We perform a numerical study that quantifies the performance of the suggested approaches.

Furthermore, we propose novel algorithms to approximate the DTSP and conduct a numerical study. Based on our numerical results, we show that these algorithms have a better performance than other existing algorithms and run in reasonable time for practical use.