Multi-agent sensor data collection with attrition risk

We introduce a multi-agent route planning problem for collecting sensor data in hostile or dangerous environments when communication is unavailable. Solutions must consider the risk of losing robots as they travel through the environment, maximizing the expected value of a plan. This requires plans that balance the number of agents used with the risk of losing them and the data they have collected so far. While there are existing approaches that mitigate risk during task assignment, they do not explicitly account for the loss of robots as part of the planning process. We analyze the unique properties of the problem and provide a hierarchical agglomerative clustering algorithm that finds high value solutions with low computational overhead. We show that our solution is highly scalable, exhibiting performance gains on large problem instances with thousands of tasks.