用闭环路径压缩优化多智能体路径，提升真实场景可用性
Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing
- 通过压缩轨迹中的闭合环路去除冗余移动
- 实验显示方案成本平均降低约20%
- 特别适合需要高质量路径的机器人部署场景
多智能体路径规划（MAPF）是具有广泛应用的NP难问题，如仓库自动化和多机器人协同。基于学习的MAPF求解器虽能快速、可扩展地生成可行路径，但常包含不必要的或振荡性移动。本文提出Judgelight，一种后处理优化模块，在生成可行调度后提升轨迹质量。Judgelight通过折叠代理轨迹中的闭合子路径来消除冗余运动，同时保持所有可行性约束。我们将其形式化为MAPF-Collapse问题，证明其为NP难，并通过整数线性规划（ILP）构建精确求解方法。实验表明，Judgelight在各类场景下稳定降低约20%的解成本，尤其对基于学习的求解器效果显著，生成的轨迹更适用于实际部署。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) is an NP-hard problem with applications in warehouse automation and multi-robot coordination. Learning-based MAPF solvers offer fast and scalable planning but often produce feasible trajectories that contain unnecessary or oscillatory movements. We propose Judgelight, a post-optimization layer that improves trajectory quality after a MAPF solver generates a feasible schedule. Judgelight collapses closed subwalks in agents' trajectories to remove redundant movements while preserving all feasibility constraints. We formalize this process as MAPF-Collapse, prove that it is NP-hard, and present an exact optimization approach by formulating it as integer linear programming (ILP) problem. Experimental results show Judgelight consistently reduces solution cost by around 20%, particularly for learning-based solvers, producing trajectories that are better suited for real-world deployment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。