用动态轻量交通图提升多智能体路径规划效率
A Lightweight Traffic Map for Efficient Anytime LaCAM*
- 利用LaCAM*搜索时自动生成动态交通地图
- 在两种MAPF变体上优于现有最优方法
- 适合需要快速生成高质量路径的场景
多智能体路径规划（MAPF）旨在为多个智能体计算无碰撞路径，具有广泛的实际应用。LaCAM*作为当前最先进的任意时间配置求解器，已有研究尝试通过引导路径来引导其避开交通拥堵，从而提升解的质量。然而，现有方法依赖Frank-Wolfe式优化，需反复调用单智能体搜索后才执行LaCAM*，在大规模问题中带来显著计算开销；且引导路径为静态，主要对首次求解有益。为此，我们提出新方法，利用LaCAM*在搜索过程中构建动态、轻量级交通地图的能力。实验表明，该方法在两种MAPF变体上均实现比现有最优引导路径方法更高的解质量。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) aims to compute collision-free paths for multiple agents and has a wide range of practical applications. LaCAM*, an anytime configuration-based solver, currently represents the state of the art. Recent work has explored the use of guidance paths to steer LaCAM* toward configurations that avoid traffic congestion, thereby improving solution quality. However, existing approaches rely on Frank-Wolfe-style optimization that repeatedly invokes single-agent search before executing LaCAM*, resulting in substantial computational overhead for large-scale problems. Moreover, the guidance path is static and primarily beneficial for finding the first solution in LaCAM*. To address these limitations, we propose a new approach that leverages LaCAM*'s ability to construct a dynamic, lightweight traffic map during its search. Experimental results demonstrate that our method achieves higher solution quality than state-of-the-art guidance-path approaches across two MAPF variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。