  We provide a framework for the assignment of multiple robots to goal
locations, when robot travel times are uncertain. Our premise is that time is
the most valuable asset in the system. Hence, we make use of redundant robots
to counter the effect of uncertainty and minimize the average waiting time at
destinations. We apply our framework to transport networks represented as
graphs, and consider uncertainty in the edge costs (i.e., travel time). Since
solving the redundant assignment problem is strongly NP-hard, we exploit
structural properties of our problem to propose a polynomial-time solution with
provable sub-optimality bounds. Our method uses distributive aggregate
functions, which allow us to efficiently (i.e., incrementally) compute the
effective cost of assigning redundant robots. Experimental results on random
graphs show that the deployment of redundant robots through our method reduces
waiting times at goal locations, when edge traversals are uncertain.
