A Multi-robot Auction Method to Allocate Tasks with Deadlines

Task allocation is one of the main problems in multi-robot systems, very especially when the robots form coalitions and the tasks to execute have to be carried out before a deadline. In general, the time required by a coalition to finish a task can be very difficult to find because it depends, among other factors, on the physical interference. This paper presents an extension of our previous auction method using a new concept called two round auction. In this framework the robots learn the interference and therefore, the coalition's utility, from their past experience using an on-line support vector regression method (SVR). We will show how the performance of the system can be improved if the interference impact is included in the model, and how the second round auction increases the total utility. This method has been tested using transport like tasks.