Scalable Robust Multi-Agent Path Finding (Student Abstract)

Abstract

Multi-Agent Path Finding (MAPF) algorithms face significant scaling challenges when extended to robust variants like k-Robust MAPF (kRMAPF), where agents may experience execution delays. While optimal solvers like kRCBS struggle to scale to larger problem instances, this work introduces kRLaCAM*, an adaptation of the eventually optimal anytime solver LaCAM* for robust environments. We propose a novelty called Cardinality Reduction (CR), which dynamically prunes conflicting actions from the low-level search and configuration generator based on the agents' recent history. Our preliminary empirical results demonstrate that kRLaCAM*-CR dramatically improves scalability, achieving a 100% success rate on dense benchmarks where state-of-the-art optimal robust solvers fail, while maintaining a reasonable solution cost.