  In this paper we study the following multi-robot coordination problem: given
a graph, where each edge is weighted by the probability of surviving while
traversing it, find a set of paths for $K$ robots that maximizes the expected
number of nodes collectively visited, subject to constraints on the probability
that each robot survives to its destination. We call this problem the Team
Surviving Orienteers (TSO) problem. The TSO problem is motivated by scenarios
where a team of robots must traverse a dangerous, uncertain environment, such
as aid delivery in disaster or war zones. We present the TSO problem formally
along with several variants, which represent "survivability-aware" counterparts
for a wide range of multi-robot coordination problems such as vehicle routing,
patrolling, and informative path planning. We propose an approximate greedy
approach for selecting paths, and prove that the value of its output is bounded
within a factor $1-e^{-p_s/\lambda}$ of the optimum where $p_s$ is the
per-robot survival probability threshold, and $1/\lambda \le 1$ is the
approximation factor of an oracle routine for the well-known orienteering
problem. Our approach has linear time complexity in the team size and
polynomial complexity in the graph size. Using numerical simulations, we verify
that our approach is close to the optimum in practice and that it scales to
problems with hundreds of nodes and tens of robots.
