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. • In monitoring tasks, a fast vehicle is followed by a support vehicle within a given distance. • We introduce a modified TSP, called TSchP, to derive the minimum-time trajectories. • We devise a heuristic for the case of many target points and derive optimality gaps. • We assess the strategy for a marine surveillance task involving a ship and a UAV.