Coalition formation games for dynamic multirobot tasks

In this paper we study the problem of forming coalitions for dynamic tasks in multirobot systems. As robots, either individually or in groups, encounter new tasks for which individual or group resources do not suffice, robot coalitions that are collectively capable of meeting these requirements need to be formed. We propose a hybrid approach to this problem where coalitions proceed with the task if they have sufficient resources after liberating redundant members while they report it to a task coordinator in cases where their resources do not suffice. In turn, the task coordinator forms capable coalitions based on coalition formation games in which groups of robots are evaluated together in regards to each task’s required resources and cost of forming a coalition. The resulting coalitions are such that no group of robots has a viable alternative to staying within their assigned coalition. Thus, as new tasks are confronted, coalitions merge and split so that the resulting coalitions are capable of the newly encountered tasks. Simulations and experiments performed on groups of heterogeneous mobile robots demonstrate the effectiveness of the proposed approach.