Optimal Task Allocation for Heterogeneous Multi-Robot Teams with Battery Constraints

This paper presents a novel approach to optimal multi-robot task allocation in heterogeneous teams of robots. When robots have heterogeneous capabilities and there are diverse objectives and constraints to comply with, comput- ing optimal plans can become especially hard. Moreover, we increase the problem complexity by: 1) considering battery- limited robots that need to schedule recharges; 2) tasks that can be decomposed into multiple fragments; and 3) multi-robot tasks that need to be executed by a coalition synchronously. We define a new problem for heterogeneous multi-robot task allocation and formulate it as a Mixed-Integer Linear Program that includes all the aforementioned features. Then we use an off-the-shelf solver to show the type of optimal solutions that our planner can produce and assess its performance in random scenarios. Our method, which is released as open-source code, represents a first step to formalize and analyze a complex problem that has not been solved in the state of the art.