arXiv:2510.21738cs.MAcs.RO2025-10

多智能体协同完成任务并规划无碰撞路径,提升效率与成功率。

Collaborative Task Assignment, Sequencing and Multi-agent Path-finding

  • 交替优化任务顺序与路径,用MILP和多标签A*搜索求解
  • 在多数场景下成功率更高,且始终找到最优解
  • 适合需要高可靠性的多机器人协同作业场景

本文研究协同任务分配、排序与多智能体路径规划(TSPF)问题,要求一组智能体访问指定任务点且不发生碰撞,同时最小化流程时间。该问题包含智能体与任务的兼容性约束,并确保所有任务被完成。我们提出一种基于任务排序的冲突搜索算法(CBS-TS),该算法通过交替求解新的任务序列与解决当前序列中的路径冲突来实现最优完整求解。CBS-TS使用混合整数线性规划(MILP)优化任务排序,并采用带有多标签A*(MLA*)的冲突搜索(CBS)进行无碰撞路径规划。仅在必要时调用MILP生成次优序列,有效缩小搜索空间,提高计算效率的同时保持最优性。实验表明,相比改进后的基线方法冲突型斯坦纳搜索(CBSS),CBS-TS在大多数测试场景中表现更优,达成更高的成功概率并持续获得最优解,而CBSS仅在部分情况下接近最优。补充视频见 https://youtu.be/QT8BYgvefmU。

原文摘要 · Abstract (English)

In this article, we address the problem of collaborative task assignment, sequencing, and multi-agent pathfinding (TSPF), where a team of agents must visit a set of task locations without collisions while minimizing flowtime. TSPF incorporates agent-task compatibility constraints and ensures that all tasks are completed. We propose a Conflict-Based Search with Task Sequencing (CBS-TS), an optimal and complete algorithm that alternates between finding new task sequences and resolving conflicts in the paths of current sequences. CBS-TS uses a mixed-integer linear program (MILP) to optimize task sequencing and employs Conflict-Based Search (CBS) with Multi-Label A* (MLA*) for collision-free path planning within a search forest. By invoking MILP for the next-best sequence only when needed, CBS-TS efficiently limits the search space, enhancing computational efficiency while maintaining optimality. We compare the performance of our CBS-TS against Conflict-based Steiner Search (CBSS), a baseline method that, with minor modifications, can address the TSPF problem. Experimental results demonstrate that CBS-TS outperforms CBSS in most testing scenarios, achieving higher success rates and consistently optimal solutions, whereas CBSS achieves near-optimal solutions in some cases. The supplementary video is available at https://youtu.be/QT8BYgvefmU.

多智能体路径规划任务调度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。