The Travelling Schnauzer Problem: Mission planning for heterogeneous vehicles with distance constraints

In many modern tasks involving small exploration submarines or tethered drones connected to a main vehicle, the presence of physical power supply cables or the limitations of wireless communication range require consideration of distance constraints during mission planning. To solve these tasks, in this work we consider the problem where an asset has to visit a set of points of interest while remaining within a certain distance of a mobile base station. First, we consider the case where the points to visit are ordered and we derive the structural properties of the optimal policy. Exploiting the results for ordered points, we consider the general case where the points to visit are not ordered and we mathematically formalize the optimization problem in an efficient way. Since deriving the optimal solution for a high number of points is computationally challenging, we devise a heuristic and we provide the theoretical bounds on optimality gaps. The proposed solution is assessed and validated through simulations. In particular, extensive numerical results on a marine exploration task show the effectiveness of the proposed heuristic both in terms of solution optimality and computation time.