  This paper considers the problem of assigning multiple mobile robots to goals
on transport networks with uncertain information about travel times. Our aim is
to produce optimal assignments, such that the average waiting time at
destinations is minimized. Since noisy travel time estimates result in
sub-optimal assignments, we propose a method that offers resilience to
uncertainty by making use of redundant robots. However, solving the redundant
assignment problem optimally is strongly NP-hard. Hence, we exploit structural
properties of our mathematical problem formulation to propose a
polynomial-time, near-optimal solution. We demonstrate that our problem can be
reduced to minimizing a supermodular cost function subject to a matroid
constraint. This allows us to develop a greedy algorithm, for which we derive
sub-optimality bounds. We demonstrate the effectiveness of our approach with
simulations on transport networks, where uncertain edge costs and uncertain
node positions lead to noisy travel time estimates. Comparisons to benchmark
algorithms show that our method performs near-optimally and significantly
better than non-redundant assignment. Finally, our findings include results on
the benefit of diversity and complementarity in redundant robot coalitions;
these insights contribute towards providing resilience to uncertainty through
targeted robot team compositions.
