When to do your own thing: Analysis of cost uncertainties in multi-robot task allocation at run-time

We address the problem of finding the optimal assignment of tasks to a team of robots when the associated costs may vary, which arises when robots deal with uncertain or dynamic situations. We detail how to compute a sensitivity analysis that characterizes how much costs may change before optimality is violated. Using this analysis, robots are able to avoid unnecessary re-assignment computations and reduce global communication. First, given a model of how costs may evolve, we develop an algorithm to partition the robots into independent cliques, each of which maintains global optimality by communicating only amongst themselves. Second, we propose a method for computing the worst-case sub-optimality if robots persist with the initial assignment, performing no further communication/computation. Lastly, we develop an algorithm that assesses whether cost changes affect the optimality through an escalating succession of local checks. Experiments show that the methods reduce the degree of centralization needed by a multi-robot system.