Multi-robot coalition formation in real-time scenarios

Task allocation is one of the main issues to be addressed in multi-robot systems, especially when the robots form coalitions and the tasks have to be fulfilled before a deadline. In general, it is difficult to foresee the time required by a coalition to finish a task because it depends, among other factors, on the physical interference. Interference is a phenomenon produced when two or more robots want to access the same point simultaneously. This paper presents a new model to predict the time to execute a task. Thanks to this model, the robots needed to carry out a task before a deadline can be determined. Within 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). Furthermore, the SVR model is used together with a new auction method called ’Double Round auction’ (DR). It will be demonstrated that by combining the interference model and the DR process, the total utility of the system significantly increases compared to classical auction approaches. This is the first auction method that includes the physical interference effects and that can determine the coalition size during the execution time to address tasks with deadlines. Transport like tasks run on a simulator and on real robots have been used to validate the proposed solutions.

► We propose a new MRTA method that takes into account the physical interference.
► Our method increases the tasks finished before the deadline and the total utility.
► Describing procedure to determine on-line the size of the coalition of robots.