Complexity of Coalition Formation for Multi-Robot Task Allocation with Subtasks

Allocating tasks to robots is a common problem in multiple domains such as robotics and operations research. The problem is further complicated when it is expected or required of robots to form coalitions prior to task execution. We present a general version of the coalition formation problem in which both, multi-robot tasks and multi-task robots are permitted. Robots forming a coalition can cooperate on task completion, however, no two coalitions are allowed to operate on a single task. The tasks themselves are divided into non-divisible subtasks and those are allocated to executors within a single coalition. We show that the problem is NP-hard to solve which encourages development of approximate or heuristic algorithms.