We present a framework for Multi-Robot Task Allocation (MRTA) in heterogeneous teams performing long-endurance missions in dynamic scenarios. Given the limited battery of robots, especially for aerial vehicles, we allow for robot recharges and the possibility of fragmenting and/or relaying certain tasks. We also address tasks that must be performed by a coalition of robots in a coordinated manner. Given these features, we introduce a new class of heterogeneous MRTA problems which we analyze theoretically and optimally formulate as a Mixed Integer Linear Program (MILP). We then contribute a heuristic algorithm to compute approximate solutions and integrate it into a mission planning and execution architecture capable of reacting to unexpected events by repairing or recomputing plans online. Our experimental results show the relevance of our newly formulated problem in a realistic use case for inspection with aerial robots. We assess the performance of our heuristic solver in comparison with other variants and with exact optimal solutions in small-scale scenarios. In addition, we evaluate the ability of our replanning framework to repair plans online.

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, computing 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.