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)
关键词: 多机器人任务分配 异构机器人 动态联盟 模仿学习 图注意力网络
📋 核心要点
- 现有方法在异构多机器人任务分配中难以兼顾实时性、动态联盟形成和任务优先级约束。
- Sadcher利用模仿学习训练图注意力网络和Transformer，预测机器人与任务间的奖励，指导高效的任务分配。
- 实验表明，Sadcher在实时性、可扩展性和任务完成质量上优于其他学习和启发式方法。
📝 摘要（中文）
本文提出了一种名为Sadcher的实时任务分配框架，用于异构多机器人团队，该框架结合了动态联盟形成和任务优先级约束。Sadcher通过模仿学习进行训练，并结合图注意力机制和Transformer来预测机器人和任务之间的分配奖励。基于预测的奖励，一个松弛的二分图匹配步骤生成具有可行性保证的高质量调度方案。我们显式地建模了机器人和任务的位置、任务持续时间和机器人的剩余处理时间，从而实现了高级的时间和空间推理，并泛化到与训练相比具有不同时空分布的环境。在最优解决的小规模实例上训练后，我们的方法可以扩展到更大的任务集和团队规模。Sadcher在随机的、未见的问题上优于其他基于学习和启发式的基线方法，其计算时间适合实时操作。我们还探索了基于采样的变体，并评估了跨机器人和任务数量的可扩展性。此外，我们发布了包含250,000个最优调度方案的数据集。
🔬 方法详解
问题定义：论文旨在解决异构多机器人团队在具有任务优先级约束下的实时任务分配问题。现有方法通常难以同时满足实时性要求、处理动态联盟形成以及考虑任务之间的依赖关系。这些方法在面对大规模任务和机器人团队时，计算复杂度高，难以保证实时性，并且泛化能力有限。
核心思路：论文的核心思路是利用模仿学习训练一个能够预测机器人和任务之间分配奖励的模型。该模型基于图注意力机制和Transformer，能够有效地捕捉机器人和任务之间的复杂关系，并考虑到任务的优先级约束。通过预测奖励，可以将任务分配问题转化为一个二分图匹配问题，从而利用高效的算法生成高质量的调度方案。
技术框架：Sadcher框架主要包含以下几个阶段：1) 数据生成：通过最优求解器生成小规模问题的最优调度方案，作为训练数据。2) 模型训练：使用模仿学习训练基于图注意力机制和Transformer的模型，使其能够预测机器人和任务之间的分配奖励。3) 任务分配：基于预测的奖励，使用松弛的二分图匹配算法生成调度方案。4) 调度执行：机器人按照生成的调度方案执行任务。
关键创新：论文的关键创新在于：1) 提出了基于图注意力机制和Transformer的任务分配奖励预测模型，能够有效地捕捉机器人和任务之间的复杂关系。2) 结合动态联盟形成和任务优先级约束，实现了更灵活和高效的任务分配。3) 通过模仿学习，将最优求解器生成的知识迁移到大规模问题上，提高了算法的可扩展性。
关键设计：模型输入包括机器人和任务的位置、任务持续时间以及机器人的剩余处理时间。图注意力网络用于学习机器人和任务之间的关系，Transformer用于捕捉任务之间的优先级约束。损失函数采用均方误差损失，用于衡量预测奖励与最优奖励之间的差距。松弛的二分图匹配算法采用匈牙利算法的变体，以保证调度方案的可行性。
🖼️ 关键图片
📊 实验亮点
Sadcher在随机生成的测试环境中，针对不同规模的机器人和任务数量进行了评估。实验结果表明，Sadcher在任务完成时间、任务完成率等方面均优于其他学习和启发式基线方法。例如，在中小规模团队中，Sadcher的任务完成时间平均缩短了15%-20%。此外，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/