# The Team Surviving Orienteers Problem: Routing Robots in Uncertain Environments with Survival Constraints

arXiv: https://arxiv.org/abs/1612.03232 · HTML: https://mlsanity.com/paper/1612.03232/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2016.

## Built on by (most cited first, 4 of 4)

- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2402.10816/) (2024)
- [Competitive Facility Location under Random Utilities and Routing Constraints](https://mlsanity.com/paper/2403.04264/) (2024)
- [No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts](https://mlsanity.com/paper/2502.11483/) (2025)

## Abstract (arXiv)

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-ps/λ of the optimum where ps is the per-robot survival probability threshold, and 1/λ ≤ 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.