多机器人协作新算法，能处理任务依赖并动态调整分工。
Online Multi-Robot Coordination and Cooperation with Task Precedence Relationships
- 构建任务图与奖励函数，用网络流近似求解复杂任务分配。
- 在线迭代重分配提升抗失败能力，性能优于离线方法。
- 适合需要动态协调的复杂真实场景，如救援或物流任务。
我们提出一种新的多机器人任务分配框架，包含任务间的复杂依赖关系、任务内高效协调以及通过机器人联盟实现合作。任务图定义了任务及其关系，一组奖励函数建模联盟规模和前序任务完成情况的影响。最大化任务奖励是NP难问题，因此我们设计基于网络流的算法以高效近似求解。提出一种新颖的在线算法，通过迭代重分配增强对任务失败和模型误差的鲁棒性，性能优于离线方法。我们在随机任务与奖励函数的测试平台上全面评估算法，并与混合整数规划求解器及贪心启发式进行对比。此外，在高级仿真环境中验证整体方法，基于真实物理现象建模奖励函数，并使用真实机器人动力学执行任务。结果表明该方法在建模复杂任务方面有效，且能高效生成高保真度任务计划，充分挖掘任务间关系。
原文摘要 · Abstract (English)
We propose a new formulation for the multi-robot task allocation problem that incorporates (a) complex precedence relationships between tasks, (b) efficient intra-task coordination, and (c) cooperation through the formation of robot coalitions. A task graph specifies the tasks and their relationships, and a set of reward functions models the effects of coalition size and preceding task performance. Maximizing task rewards is NP-hard; hence, we propose network flow-based algorithms to approximate solutions efficiently. A novel online algorithm performs iterative re-allocation, providing robustness to task failures and model inaccuracies to achieve higher performance than offline approaches. We comprehensively evaluate the algorithms in a testbed with random missions and reward functions and compare them to a mixed-integer solver and a greedy heuristic. Additionally, we validate the overall approach in an advanced simulator, modeling reward functions based on realistic physical phenomena and executing the tasks with realistic robot dynamics. Results establish efficacy in modeling complex missions and efficiency in generating high-fidelity task plans while leveraging task relationships.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。