Scalable hedonic coalition formation for task allocation with heterogeneous robots

Tasks in the real world are complex and often require multiple robots to collaborate to be serviced. In many cases, a task might require different sensory inputs and actuation outputs. However, allocating a large variety of sensors and/or actuators on a single robot is not a cost-effective solution—robots with different attributes must be considered. In this paper, we study coalition formation for such a set of heterogeneous robots to be allocated instantaneously to a set of tasks. Our proposed solution employs a hedonic coalition formation strategy based on a weighted bipartite matching algorithm. In our setting, a hedonic coalition game, a topic rooted in game theory, is used to form coalitions by minimizing the total cost of the formation and maximizing the overlap between required and allocated types of robots for each of the tasks. This approach guarantees a polynomial time complexity and Nash-stability. Numerical results show that our approach finds similar quality near-optimal solutions to existing approaches while significantly reducing the time to find them. Moreover, it easily scales to large numbers of robots and tasks in negligible time (1.57 sec. with 2000 robots and 400 tasks).