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

翻译：本文提出了一种适用于动态场景下异构机器人团队执行长续航任务的多机器人任务分配框架。考虑到机器人（尤其是飞行器）的有限电池续航能力，我们允许机器人进行充电，并支持对特定任务进行分割和/或接力执行。同时，我们处理了需要多个机器人以协同方式共同完成的任务。基于这些特性，我们引入了一类新的异构多机器人任务分配问题，从理论上对其进行分析，并将其最优形式化为混合整数线性规划模型。随后，我们提出了一种启发式算法以计算近似解，并将其集成到具备在线修复或重规划能力的任务规划与执行架构中，以应对突发事件的干扰。实验结果表明，新提出的问题在无人机巡检的现实应用场景中具有重要价值。我们通过与小规模场景下的精确最优解及其他算法变体对比，评估了启发式求解器的性能。此外，我们还验证了重规划框架在线修复任务方案的有效性。