The multiple-path orienteering problem asks forpaths for a team of robots that maximize the total rewardcollected while satisfying budget constraints on the path length.This problem models many multi-robot routing tasks such asexploring unknown environments and information gathering forenvironmental monitoring. In this paper, we focus on how tomake the robot team robust to failures when operating inadversarial environments. We introduce the Robust Multiple pathOrienteering Problem (RMOP) where we seek worst-caseguarantees against an adversary that is capable of attacking atmost \alpha robots. Our main contribution is a general approximationscheme with bounded approximation guarantee that depends on\alpha and the approximation factor for single robot orienteering.In particular, we show that the algorithm yields a (i) constant factorapproximation when the cost function is modular; (ii)log factor approximation when the cost function is submodular;and (iii) constant-factor approximation when the cost functionis submodular but the robots are allowed to exceed their pathbudgets by a bounded amount. In addition to theoretical analysis,we perform simulation study for an ocean monitoring applicationto demonstrate the efficacy of our approach.
