Resilient Assignment Using Redundant Robots on Transport Networks
with Uncertain Travel Time
This research is motivated by the problem of assigning mobile agents to goals when travel times from agent origins to goal locations are uncertain. Existing robust assignment methods deal with uncertainty by minimizing risk, or by pre-defining acceptable risk thresholds. In this work, DCIST researchers propose a complementary method by making use of agent redundancy.
The proposed framework is underpinned by the novel insight that the deployment of redundant agents under uncertain travel times is supermodular in the number of redundant agents. This insight is derived from a first-come, first-to-serve principle, which is formally introduced in the paper through an aggregate function that considers only the minimum travel time among the assigned agent coalition. These theoretical contributions enable the efficient solution of the redundant assignment problem through a near-optimal, greedy algorithm. The findings include results on the benefit of diversity and complementarity in redundant agent coalitions; these insights contribute towards providing resilience to uncertainty through targeted agent team compositions.
Source: Prorok, “Redundant Robot Assignment on Graphs with Uncertain Edge Costs”, International Symposium on Distributed Autonomous Robotic Systems (DARS), 2018; Best Paper Award
https://arxiv.org/abs/1810.04016 / https://arxiv.org/abs/1804.04986
Point of Contact: Amanda Prorok
