k-Survivability: Diversity and Survival of Expendable Robots

Abstract

We define the k-survivability of a set of n paths as the probability that at least k out of n robots following those paths through a stochastic threat environment reach goals. High k-survivability sets tend to contain short and diverse paths.Finding sets of paths with maximum k-survivability is NP-hard. We design two algorithms: a complete algorithm that finds an optimal list of paths, and a heuristic method that finds paths with high k-survivability. Although computing k-survivability is expensive and this work is still preliminary, we believe that understanding the relationship between diversity and survival will yield new insights into multirobot motion planning.