A Group Decentralized Framework for Parallel Lifelong MAPF

The paper presents a theoretical foundation for a new approach to the Lifelong Multi-Agent Path Finding (L-MAPF) problem, where multiple agents must continuously navigate to assigned destinations while avoiding obstacles and each other. Current state-of-the-art methods, notably the Rolling-Horizon Collision Resolution (RHCR) framework, produce high-quality solutions but suffer from excessive computational costs that limit scalability even with modest numbers of agents. The authors leverage advanced concepts from Locally Interdependent Multi-Agent Markov Decision Processes to formally prove that RHCR is near-optimal in a discounted MDP formulation of L-MAPF. This proof serves as the basis for an extension called Group Decentralized RHCR (GD-RHCR), which introduces a group decentralized structure. Agents are partitioned according to a transitive communication scheme, and each partition is planned separately in parallel, significantly reducing computational burden while preserving solution quality. The paper is a theoretical contribution posted on arXiv, offering a rigorous justification for decentralization in lifelong multi-agent scheduling. It does not provide experimental results but lays the groundwork for future scalable implementations. This research is relevant to robotics, autonomous vehicle coordination, warehouse logistics, and other domains requiring continuous multi-agent coordination in shared spaces.