MuRoCo: A framework for capability- and situation-aware coalition formation in cooperative multi-robot systems

One problem in cooperative multi-robot systems is to reach a group agreement on the distribution of tasks among the robots, known as multi-robot task allocation problem. In case the tasks require a tight cooperation among the robots the formation of adequate subteams, so-called coalitions, is needed which is known to be a NP-complete problem. Here the MuRoCo framework is presented, which solves the coalition formation problem for cooperative heterogeneous multi-robot systems. MuRoCo yields a lower increase of the worst-case complexity compared to previous solutions, while still guaranteeing optimality for sequential multi-robot task assignments. These include also the, in related work often neglected, optimal subtask assignment. In order to reduce the average complexity, which is commonly more relevant in the practical operation, pruning strategies are used that consider system-specific characteristics to reduce the number of potential solutions already in an early phase. To ensure a robust operation in dynamic environments, MuRoCo takes potential disturbances and the environmental uncertainty explicitly into account. This way MuRoCo yields capability- and situation-aware solutions for real world systems. The framework is theoretically analyzed and is practically validated in a cooperative service scenario, showing its suitability to complex applications, its robustness to environmental changes and its ability to recover from failures. Finally a benchmark evaluation shows the realizable problem sizes of the current implementation.