Abdullah Ali Faruq
M.Sc. Thesis Proposal
Supervisor: Dr. Antonina Kolokolova

Approximation algorithms for AUV mission planning

Department of Computer Science
Friday, October 4, 2013, 11:50 a.m., Room EN 2022

---

Abstract

An AUV is an autonomous underwater vehicle that travels without any active human assistance. For years, AUVs such as Slocum gliders have been used for ocean survey, iceberg mapping and many other types of missions. During a mission, the gliders visit a number of waypoints. These gliders are small in size and relatively slow while travelling, but they can stay in water for a long time. As the number of waypoints grows, the problem of finding an optimal mission plan, that is the order of waypoints minimizing the total time, becomes non-trivial.

We can model this problem as a directed weighted complete graph, where nodes represent the waypoints and edges represent the travelling time between the nodes. We can make use of historical ocean current data (like NetCDF) and path planning algorithms to produce this graph. The solution
to this problem is a tour that visits each node exactly once such that the total cost of the tour is minimal. In the literature, this problem is known as the Travelling Salesperson Problem (TSP) and is one of the well-studied NP-hard problems. The solution space is exponentially large and there is no known algorithm that produces an optimal solution in polynomial time. Rather, we will concentrate on approximation and look for "good enough" solution of the problem. In the worst case, even approximating TSP to within any constant factor is NP-hard. However, appropriate restrictions
on the type of the graph and weight distribution such as triangular inequality on the weights allow for better approximation algorithms.

The goal of this thesis is to analyse the “industrial” class of instances of TSP that come from the glider mission planning problem. As this is a very specific type of data, it can possess additional properties which could make them amenable to better approximation algorithms. We plan to investigate such properties and adapt available algorithms to our settings accordingly.