Title: Supermodular Optimization for Redundant Robot Assignment under Travel-Time Uncertainty,
Abstract: This paper considers the assignment of multiple mobile robots to goal
locations under uncertain travel time estimates. Our aim is to produce optimal
assignments, such that the average waiting time at destinations is minimized.
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. Since
solving the redundant assignment problem is strongly NP-hard, we exploit
structural properties of our problem 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. A
comparison with the baseline non-redundant assignment shows that redundant
assignment reduces the waiting time at goals, and that this performance gap
increases as noise increases. Finally, we evaluate our method on a mobility
data set (specifying vehicle availability and passenger requests), recorded in
the area of Manhattan, New York. Our algorithm performs in real-time, and
reduces passenger waiting times when travel times are uncertain.