The risk-sensitive coverage problem: Multi-robot routing under uncertainty with service level and survival constraints
Stefan Jorgensen, Robert H. Chen, Mark B. Milam, Marco Pavone · 2017
Consider a scenario where robots traverse a graph, but crossing each edge bears a risk of failure. A team operator seeks a set of paths for the smallest team which guarantee the probabilities that at least one robot visits each node satisfy specified per-node visit thresholds, and the probabilities each robot reaches its destination satisfy a per-robot survival threshold. We present the Risk-Sensitive Coverage (RSC) problem formally as an instance of the submodular set cover problem and propose an efficient cost-benefit greedy algorithm for finding a feasible set of paths. We prove that the number of robots deployed by our algorithm is no more than (λ/ps)(1 + log(λΔκ/ps)) times the smallest team, where Δκquantifies the relative benefit of the first and last paths, psis the per-robot survival probability threshold and 1/λ ≤ 1 is the approximation factor of an oracle routine for the well-known orienteering problem. We demonstrate the quality of our solutions by comparing to optimal solutions computed for special cases of the RSC and the efficiency of our approach by applying it to a search and rescue scenario where 225 sites must be visited, each with probability at least 0.95.