  The multiple-path orienteering problem asks for paths for a team of robots
that maximize the total reward collected while satisfying budget constraints on
the path length. This problem models many multi-robot routing tasks such as
exploring unknown environments and information gathering for environmental
monitoring. In this paper, we focus on how to make the robot team robust to
failures when operating in adversarial environments. We introduce the Robust
Multiple-path Orienteering Problem (RMOP) where we seek worst-case guarantees
against an adversary that is capable of attacking at most $\alpha$ robots. We
consider two versions of this problem: RMOP offline and RMOP online. In the
offline version, there is no communication or replanning when robots execute
their plans and our main contribution is a general approximation scheme with a
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-factor approximation when the cost function is modular;
(ii) $\log$ factor approximation when the cost function is submodular; and
(iii) constant-factor approximation when the cost function is submodular but
the robots are allowed to exceed their path budgets by a bounded amount. In the
online version, RMOP is modeled as a two-player sequential game and solved
adaptively in a receding horizon fashion based on Monte Carlo Tree Search
(MCTS). In addition to theoretical analysis, we perform simulation studies for
ocean monitoring and tunnel information-gathering applications to demonstrate
the efficacy of our approach.
