Multi-robot coalition formation in real-time scenarios

Abstract

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.

Introduction

Multi-robot systems can provide several advantages compared to single-robot systems, for example: robustness, flexibility and efficiency. To make the most of these potential benefits, several problems have to be solved, specially when two or more robots can constitute coalitions to execute tasks. Of all the issues reported in the specialized literature, this paper focuses on the methods to select the best robot or set of robots to execute a task, which is commonly referred to as the ‘Multi-Robot Task Allocation’ (MRTA) problem.

In [1] Gerkey and Mataric, broke down the MRTA problem in three orthogonal axes: Multi-task robots (MT) vs. Single-task robots (ST) depending on whether multiple tasks can be assigned to the same robot or not; Single-robot tasks (SR) vs. Multi-robot tasks (MR), where SR means that only one robot can be assigned to a task, while MR means that several robots (a coalition) can concurrently execute a task; and finally, Instantaneous assignment (IA) vs. Time-extended assignment (TE) where in IA the allocation is made by not taking into account the future incoming tasks. In terms of this taxonomy, the present work is concentrated on the ST-MR-IA problem. Moreover, special attention is paid to the tasks that have to be fulfilled before a deadline, in which case the knowledge of how long the coalition will take to finish a task is essential in order to determine the proper alliances. The time needed to finish a task is frequently unknown. Thus, in general, anticipating if certain coalitions can meet the task’s deadline or estimate their utility can be quite difficult. In this context, it is very arduous to accurately model the execution time of a task because it depends on many complex and dynamic factors, among which this paper will center its attention on the physical interference. Interference appears when some individuals of a community compete for a shared resource. In Multi-robot systems, a frequent situation occurs when two or more robots need to access the same point simultaneously. It has been demonstrated in different studies [2], [3], that physical interference has an important impact on the system performance. This effect can be dramatic when the system has to address tasks with deadlines because interference increases the time needed by the coalition to finish the task and, therefore, diminishes the coalition utility. This paper proposes a new MRTA method for creating coalitions of mobile robots in real time scenarios, that is, in environments where the tasks must be executed before a deadline. When a coalition finishes a task before its deadline, the system obtains the maximum utility associated with that task. Otherwise, the utility decreases following some time function. The goal of the proposed method is to maximize the total utility obtained by the system. Auction methods have been thoroughly studied and they are frequently used as a task allocation solution. Furthermore, the current MR auction methods cannot predict the expected execution time of a task nor the coalition size, thus, they are unsuitable for real time situations. To solve the stated problem, this work presents a new auction method, called Double Round auction (DR). The DR auction is used together with a model of the physical interference, based on Support Vector Regression (SVR) [4], to predict how long the task execution will last. This paper also analyzes the effect of the task progress’ monitoring on the system performance. The experimental results presented here show that, using a correct interference model, the task execution time can be predicted and, therefore, the monitoring processes and their sensorial and communication resources, are not necessary. To test the proposed system a foraging-like task is used, where multiple robots can cooperate to transport the same object. The experiments have been obtained using both a simulator and a set of four real robots (Pioneer 3DX). The results prove that the new proposed method clearly outperforms those obtained with classical auction mechanisms. The main goals of this paper are:

• To present a new MRTA method that takes into account physical interference and uses this information to estimate the tasks’ execution time.

• To describe a coalition formation procedure that can determine on-line the size of the workgroup required to meet the tasks’ deadlines.

• To develop a new auction method, called Double Round auction, that improves the classical auction approaches in terms of total utility achieved in environments with deadlines.

This paper extends and analyzes in greater detail our previous work on MRTA algorithms explained in [5]. Although the double round concept was preliminarily introduced in [6], here we include a detailed description and analysis of the algorithm, an error recovery strategy and new experimental results, including tests on real robots.

The paper is organized as follows: Section 2 reviews the relevant work in MRTA with special attention paid to auction methods; Section 3 presents a formal definition of the problem to solve and details the real time foraging task; Section 4 explains the techniques used to predict the execution time; Section 5 introduces the Double Round auction task allocation algorithm; the experimental results are shown and analyzed in Section 6 and, finally, the conclusions and future work are presented in Section 8.