优化多智能体任务分配与路径规划，确保任务按序完成且效率更高。
Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints
- 基于大邻域搜索，动态重分配任务以提升整体效率。
- 在89.1%的实例中优于固定分配方案，显著降低路径成本。
- 适合需严格任务顺序的多机器人协同场景，如工厂调度。
许多多机器人应用要求任务高效且按正确顺序完成，以确保后续操作按时进行。多智能体路径规划带优先级约束（MAPF-PC）是一种成熟框架，可在任务序列预先确定时计算无碰撞的可行路径。然而，在许多实际场景中，解的质量不仅取决于路径选择，还依赖于由哪个智能体执行哪项任务。这引出了任务分配与路径规划带优先级约束（TAPF-PC）这一提升问题，它联合优化任务分配、优先级满足和路径成本。为应对由此产生的耦合搜索空间，本文提出一种大邻域搜索方法：从一个可行的MAPF-PC解出发，通过基于重分配的邻域修复迭代改进，每次均在选定邻域内恢复可行性。在多个基准数据集和不同规模下的实验表明，最佳配置在89.1%的实例中优于固定分配的种子解，证明了大邻域搜索能有效利用灵活重分配带来的收益。
原文摘要 · Abstract (English)
Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy ordering relations when task sequences are fixed in advance. In many applications, however, solution quality depends not only on how agents move, but also on which agent performs which task. This motivates the lifted problem of task assignment and path finding with precedence constraints (TAPF-PC), which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost. To address the resulting coupled TAPF-PC search space, we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibility within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。