A Lightweight Traffic Map for Efficient Anytime LaCAM*
This work provides an incremental improvement for researchers and practitioners working with LaCAM* in Multi-Agent Path Finding by enhancing solution quality and efficiency.
This paper addresses the computational overhead and static nature of guidance paths in LaCAM*, a state-of-the-art Multi-Agent Path Finding (MAPF) solver. The authors propose a new approach that uses LaCAM*'s ability to construct a dynamic, lightweight traffic map during its search, leading to higher solution quality compared to existing guidance-path methods across two MAPF variants.
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.