SADCHER: Scheduling using Attention-based Dynamic Coalitions of Heterogeneous Robots in Real-Time
作者: Jakob Bichler, Andreu Matoses Gimenez, Javier Alonso-Mora
分类: cs.RO, cs.MA
发布日期: 2025-10-16
备注: 7 pages, 5 figures. 2025 IEEE Int. Symposium on Multi-Robot and Multi-Agent Systems (MRS 2025). Website and Code: https://autonomousrobots.nl/paper_websites/sadcher_MRTA/
💡 一句话要点
SADCHER：基于注意力机制的异构多机器人实时动态联盟调度
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱八：物理动画 (Physics-based Animation)
关键词: 多机器人任务分配 动态联盟形成 模仿学习 图注意力网络 Transformer 实时调度 异构机器人
📋 核心要点
- 现有方法难以在异构多机器人系统中实时处理复杂的任务分配和调度问题，尤其是在考虑任务优先级和动态联盟形成时。
- Sadcher利用模仿学习训练图注意力网络和Transformer，预测机器人与任务间的奖励，指导动态联盟形成和任务分配，实现高效调度。
- 实验表明，Sadcher在小规模和中等规模的异构机器人团队中，优于其他学习和启发式方法，并具有良好的实时性和可扩展性。
📝 摘要（中文）
本文提出了一种名为Sadcher的实时任务分配框架，用于异构多机器人团队，该框架结合了动态联盟形成和任务优先级约束。Sadcher通过模仿学习进行训练，并结合图注意力机制和Transformer来预测机器人和任务之间的分配奖励。基于预测的奖励，一个松弛的二分图匹配步骤生成具有可行性保证的高质量调度方案。我们显式地建模了机器人和任务的位置、任务持续时间以及机器人剩余处理时间，从而实现了高级的时间和空间推理，并能够泛化到与训练环境具有不同时空分布的环境。在最优求解的小规模实例上训练后，我们的方法可以扩展到更大的任务集和团队规模。在随机的、未见的问题上，Sadcher优于其他基于学习的和启发式的基线方法，其计算时间适合实时操作。我们还探索了基于采样的变体，并评估了跨机器人和任务数量的可扩展性。此外，我们发布了包含250,000个最优调度方案的数据集。
🔬 方法详解
问题定义：论文旨在解决异构多机器人团队中的实时任务分配问题，该问题需要考虑任务之间的优先级约束以及机器人之间的动态联盟形成。现有方法在处理大规模、异构的机器人团队以及复杂的任务依赖关系时，计算复杂度高，难以满足实时性要求。此外，现有方法泛化能力有限，难以适应新的环境和任务分布。
核心思路：论文的核心思路是利用模仿学习训练一个能够预测机器人和任务之间分配奖励的模型。该模型基于图注意力机制和Transformer，能够有效地捕捉机器人和任务之间的复杂关系，并考虑到任务的优先级约束和机器人的异构性。通过预测分配奖励，可以将任务分配问题转化为一个二分图匹配问题，从而利用高效的算法求解。
技术框架：Sadcher框架主要包含以下几个模块：1) 数据生成模块：生成小规模问题的最优解作为训练数据；2) 模型训练模块：使用模仿学习训练基于图注意力机制和Transformer的模型，用于预测机器人和任务之间的分配奖励；3) 任务分配模块：基于预测的奖励，利用松弛的二分图匹配算法生成任务调度方案；4) 评估模块：评估调度方案的性能，包括任务完成时间、资源利用率等。
关键创新：论文的关键创新在于：1) 提出了基于图注意力机制和Transformer的任务分配奖励预测模型，能够有效地处理异构机器人和复杂任务依赖关系；2) 利用模仿学习训练模型，避免了强化学习训练过程中的探索问题，提高了训练效率；3) 提出了松弛的二分图匹配算法，能够在保证可行性的前提下，生成高质量的调度方案。
关键设计：模型输入包括机器人和任务的位置、任务持续时间、机器人剩余处理时间等信息。图注意力网络用于学习机器人和任务之间的关系，Transformer用于捕捉任务之间的优先级约束。损失函数采用均方误差损失，用于衡量预测奖励和真实奖励之间的差距。二分图匹配算法采用匈牙利算法或KM算法的松弛版本，以提高计算效率。
📊 实验亮点
SADCHER在随机生成的、未见的问题上，优于其他基于学习的和启发式的基线方法。实验结果表明，SADCHER在小规模和中等规模的机器人团队中，能够生成高质量的调度方案，并且计算时间满足实时性要求。此外，论文还探索了基于采样的变体，并评估了跨机器人和任务数量的可扩展性，证明了SADCHER具有良好的泛化能力。
🎯 应用场景
该研究成果可应用于各种需要多机器人协同完成任务的场景，例如：仓库自动化、物流配送、灾难救援、农业生产等。通过优化任务分配和调度，可以提高资源利用率、缩短任务完成时间、降低运营成本，并提升系统的鲁棒性和适应性。未来，该方法有望扩展到更复杂的环境和任务，实现更高级别的自主化和智能化。
📄 摘要（原文）
We present Sadcher, a real-time task assignment framework for heterogeneous multi-robot teams that incorporates dynamic coalition formation and task precedence constraints. Sadcher is trained through Imitation Learning and combines graph attention and transformers to predict assignment rewards between robots and tasks. Based on the predicted rewards, a relaxed bipartite matching step generates high-quality schedules with feasibility guarantees. We explicitly model robot and task positions, task durations, and robots' remaining processing times, enabling advanced temporal and spatial reasoning and generalization to environments with different spatiotemporal distributions compared to training. Trained on optimally solved small-scale instances, our method can scale to larger task sets and team sizes. Sadcher outperforms other learning-based and heuristic baselines on randomized, unseen problems for small and medium-sized teams with computation times suitable for real-time operation. We also explore sampling-based variants and evaluate scalability across robot and task counts. In addition, we release our dataset of 250,000 optimal schedules: https://autonomousrobots.nl/paper_websites/sadcher_MRTA/