Paper 1: Online Multirobot Coordination and Cooperation With Task Precedence Relationships
用Task Graph和流方法解决同构机器人集群任务分配问题。其中Task Graph的表现力很强
论文信息
- 标题：Online Multirobot Coordination and Cooperation With Task Precedence Relationships
- 作者 / 单位：Walker Gosrich , Saurav Agarwal , Kashish Garg, Siddharth Mayya , Matthew Malencia , Mark Yim , and Vijay Kumar
- 来源：IEEE TRANSACTIONS ON ROBOTICS, VOL. 41, 2025
背景和贡献
- 面向存在任务先后依赖与“前序完成质量影响后续收益”的多机器人任务分配问题，提出用有向无环的 Task Graph 统一建模。
- 引入联盟函数与影响函数，统一表达多机协同增益与合作阈值需求，并把这些机制嵌入任务链路的收益传播。
方法
- 将原问题转写为“人口流（robot fraction flow）”在 Task Graph 上的非线性网络流优化（NLP），得到离线全局近似解。
- 给出 Greedy one-step lookahead 的快速基线：在每个节点局部优化下一跳分流。
- 在线迭代重规划：任务完成/失败后更新图与 reward model；对进行中任务加专属源点锁定联盟，保证计划连续与剩余时间计入。
结果和评价
- 随机任务图实验表明 flow-based 方法可扩展性显著优于 MINLP；NLP flow 通常优于贪心且计算更快。
- 在线方案在完美模型与存在失败/扰动时都显著优于离线，并在小规模对照中接近近最优解。
- 优势在于闭环鲁棒与可扩展；代价是在线需多次求解，计算开销随任务规模增长，需要结合任务时长与重规划频率权衡