Complexity of Multi-robot Task Allocation Problems with Multimodal Execution

The decision making problem considered in this paper consists in allocating multiple tasks to multiple machines and is a special case of the multidemand multidimensional knapsack problem (MDMKP). This problem is common in MRTA, or multi-robot task allocation, which is often considered in robotics. Partial task executions are allowed in case more than one machine is needed to complete a single task. Similarly, more than one task can be executed on a single machine. Machines can run in one of the many modes permitted for each task executed. They also run in parallel and have limited resources that cannot be exceeded. All of the tasks have to be fully executed in a way that minimizes the total resource usage. Underlying decision making problem proves difficult to solve in reasonable time. In the paper this difficulty is emphasised by showing that both, the feasibility version and the single-task version are NP-hard.