Search

In this paper we describe several approaches to the AUV (glider) mission planning problem and investigate their complexity. At the heart of such mission planning are variants of an NP-hard (Non-deterministic Polynominal-time) Asymmetric Travelling Salesman Problem (ATSP); however, some modern-day heuristics can solve this problem optimally in a reasonable amount of time (although providing a proof of optimality slows down the computation). A glider mission plan often has to accommodate a variety of other constraints such as scheduling restrictions, specific time windows or order to visit selected points and so on. Here we consider a general AUV mission planning problem which, although based on ATSP, can incorporate other constraints. Thus, the use of general-purpose solvers such as Integer Linear Programming or Satisfiability-based solvers may be desired. With this goal, we have developed a software package for the glider mission planning problem that utilizes a variety of existing solvers to compute an optimal order of goal points to visit, subject to travel time as well as userprovided additional constraints. Then, to evaluate feasibility of this setting using state-of-the-art solvers, we analyze the performance of a variety of solvers on the core ATSP problem. [ABSTRACT FROM AUTHOR]