Glider mission planning using generic solvers

Avi, Tamkin Khan (2014) Glider mission planning using generic solvers. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (2MB)

Abstract

Autonomous underwater vehicles (AUVs), in particular gliders, have been used for many tasks such as underwater surveys or subsurface sampling. Gliders are small lightweight underwater vehicles, which move by varying their buoyancy. They receive a list of locations to visit at the start of a mission, and then spend most of their time under water, surfacing ocassionally to get their GPS reading and communicate with the control centre, possibly receiving updated instructions. Modern-day gliders can perform month-long missions. During a mission, several factors impact their performance: ocean currents, lack of communication and GPS while under water and weather. At present, AUV operators do not seem to do much automated mission planning, supplying a glider with a list of goals created by hand. Developing techniques for planning such missions was the goal of this project. At the heart of such mission planning problem are variants of the Asymmetric Traveling Salesman problem: as it is NP-hard, there is no known algorithm to solve it exactly in polynomial time. However, over the last decade heuristic solvers, in particular solvers based on Integer Linear Programming and Satisfiability, have been used successfully in practice to solve industrial instances of many NP-hard problems. In this thesis we will describe a glider mission planner that we developed, which is based on using such solvers. We evaluate performance of generic solvers, in particular Mixed Integer Linear Programming (MILP) solver CPLEX, several Pseudo-Boolean Optimization (PBO) solvers Sat4j, Clasp, SCIP and Satisfiability Modulo Theories (SMT) solver Z3. The performance of finding a optimal mission plan also heavily depends on the type of encoding, so in addition to different solvers, we analyzed several types of encodings, from the classic Miller, Tucker and Zemlin encoding to Fox, Gavish and Graves’ time-dependent TSP encoding. In our experiments, Mixed Integer Linear Programming solver (MILP) has been the most successful compared to other types of generic solvers. An important question in satisfiability heuristic solver research is modelling the realworld instances by a synthetic distribution. Here, we compared the performance of the solvers on instances of ATSP coming from ocean current data with their performance on crafted instances of random graphs, Euclidean graphs and Euclidean with varying amounts of noise, both symmetric and asymmetric. Developing techniques for planning such missions was the goal of this project, and in this thesis we describe and evaluate several approaches to the AUV mission planning problem.

Actions (login required)

View Item