Research Article: Multi-Robot Coalitions Formation with Deadlines: Complexity Analysis and Solutions

Date Published: January 24, 2017

Publisher: Public Library of Science

Author(s): Jose Guerrero, Gabriel Oliver, Oscar Valero, Long Wang.


Multi-robot task allocation is one of the main problems to address in order to design a multi-robot system, very especially when robots form coalitions that must carry out tasks before a deadline. A lot of factors affect the performance of these systems and among them, this paper is focused on the physical interference effect, produced when two or more robots want to access the same point simultaneously. To our best knowledge, this paper presents the first formal description of multi-robot task allocation that includes a model of interference. Thanks to this description, the complexity of the allocation problem is analyzed. Moreover, the main contribution of this paper is to provide the conditions under which the optimal solution of the aforementioned allocation problem can be obtained solving an integer linear problem. The optimal results are compared to previous allocation algorithms already proposed by the first two authors of this paper and with a new method proposed in this paper. The results obtained show how the new task allocation algorithms reach up more than an 80% of the median of the optimal solution, outperforming previous auction algorithms with a huge reduction of the execution time.

Partial Text

Systems with two or more mobile robots (multi-robot-systems) can perform tasks that with one robot would be impossible to carry out or would take much more time. Moreover, such systems are more robust, scalable and flexible than those with only one robot. However, a lot of new challenges and problems must be solved before taking advantage of the potential benefits of multi-robot systems. Among all possible issues that arise in a natural way in multi-robot systems, this paper focuses on the problem commonly referred to as “Multi-robot Task Allocation” (MRTA) which consists in selecting the best robots to execute each one of the tasks that must be performed. MRTA is still an open problem, specially when several robots (a coalition) have to execute concurrently a task before a deadline. Furthermore, in most cases, this problem is either NP or needs a very long time to provide an optimal solution. To address this problem, auction-like algorithms are widely used, where the robots negotiate between them to achieve a solution.

In this section we review the fundamental aspects of multi-robot task allocation proposed in the literature. Specially, we focus on the problem of the complexity and on the relationships with other knowledge fields such as multi-agent or task-scheduling. As will be seen, most MRTA problems for the coalition formation are NP-hard, thus, making necessary the use of heuristic functions for obtaining a solution close enough to the optimum value in a moderate time. The MRTA methods can be classified in three groups: centralized approaches, swarm-based methods and auction algorithms. The last two approaches are the most used nowadays, but as will be seen, these methods present serious limitations when the robots must form coalitions to face up tasks with deadlines.

This section focuses on the coalition formation methods that can deal with task deadlines. Depending on how the task allocation process is distributed among the robots, the coalition formation methods can be classified into the following categories: centralized systems, self-organized approaches (swarm intelligence) and auction methods. The Gerkey’s taxonomy will be applied into each one of these groups.

The MR problem with deadlines has not been properly addressed by previous task allocation approaches. Moreover, no formal analysis regarding the complexity of this problem has been proposed. This section presents a formal definition of the MRTA-ST-MR with deadlines problem from which we will propose a classification, according to the computational complexity under different situations.

In this section we first overview an auction method, called from now on Simple Double Round Auction (SDRA), that was previously proposed by the first two authors in [3]. The experimental results showed that the aforementioned method outperforms the current auction approaches. Furthermore, to our best knowledge, this is the only method that addresses coalition formation for tasks with deadlines. Then, in the light of the experimental results and motivated by the problem formalization explained in the last section, a new auction method, called Multiple Objectives Double Round Auction (MDRA), is proposed for the first time.

In this section we detail the experiments executed in order to analyze the behaviour of the auction algorithms, comparing them to the optimal solution given by the optimization problems of Section Coalition formation complexity analysis. Firstly, we will explain the experiments carried out with a realistic (physical) simulator called RoboCoT (see [3]) in order to obtain the I function parameters. From the function I, new experiments have been carried out using Matlab (Version R2014a and Optimization Toolbox version 7). The solutions for the optimization, Problems 15 and 21, have been obtained executing the optimal linear programming-based branch-and-bound algorithm together with a simplex method [48].

This paper has presented the first formal study about the interference impact on the complexity of the multi-robot coalition formation problem to allocate tasks with deadlines. The formalization of the MRTA problem shows that, on the one hand the interference can be modelled by a linear function and, on the other hand, the optimal solution can be obtained solving an integer linear problem which depends on the utility function characteristics.