Robust Multi-robot Task Assignment in Surveillance

A market based approach for the assignment of tasks in a multi-robot system is presented in this paper. The mobile robots are organized in groups, where tasks are locally assigned using an auction. The performance of the groups is evaluated with a measure similar to the concept of economic prices. The robots use this information at run-time, to switch to groups with higher prices. A theoretical analysis is presented and it is shown that under reasonably mild assumptions: (i) tasks are always assigned if there are idle robots, (ii) it is possible to detect the occurrence of failures which prevent the assignment of tasks and (iii) the approach is robust to the breakdown of any individual component. The range of possible choices for dividing the robots in groups is quantified with an entropy based measure. It is shown that the entropy value decreases if the components suffer severe failures of if the operating conditions deteriorate.