Robust Assignment Using Redundant Robots on Transport Networks With Uncertain Travel Time

Abstract

This article considers the problem of assigning mobile robots to goals on transport networks with uncertain and potentially correlated 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 suboptimal assignments, we propose a method that offers robustness to uncertainty by making use of redundant robot assignments. However, solving the redundant assignment problem optimally is strongly NP-hard. Hence, we exploit the 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 assignment algorithm, for which we derive suboptimality bounds. We demonstrate the effectiveness of our approach with simulations on transport networks with correlated uncertain edge costs and uncertain node positions that lead to noisy travel time estimates. Comparisons to benchmark algorithms show that our method performs near-optimally and significantly better than the nonredundant assignment. Finally, our findings include results on the benefit of diversity and complementarity in redundant robot coalitions; these insights contribute toward providing resilience to uncertainty through the targeted composition of robot coalitions. Note to Practitioners—This article is motivated by the problem of assigning mobile robots (e.g., vehicles and drones) to goals when travel times from robot origins to goal locations are uncertain. Existing robust assignment methods deal with uncertainty by minimizing risk or by predefining acceptable risk thresholds. In this article, we propose a complementary method that offers robustness to uncertainty by making use of robot redundancy. In other words, we assign more robots than necessary to a given goal, in the expectation that one of the redundant robots will reach the goal faster (than the originally assigned robot). However, solving this redundant assignment problem is computationally intractable for large systems. By characterizing the mathematical problem, we show how the redundant assignment problem can be solved efficiently. We apply our assignment algorithm to transport network problems to reduce the average waiting times at goal locations when travel times from vehicle origins to destinations are uncertain and potentially also correlated. Our results show that exploiting robot redundancy is an effective approach to reducing waiting times. In this work, we build on the premise that time is the primary commodity, and we do not explicitly model the additional cost of utilizing redundant robots. Future work should more explicitly address the tradeoff between the cost of providing redundancy (e.g., travel costs and robot costs) and performance gains.