Learn to Refine: Synergistic Multi-Agent Path Optimization for Lifelong Conflict-Free Navigation of Autonomous Vehicles

Lifelong Multi-Agent Path Finding (LMAPF) focuses on planning conflict-free paths for agents, like autonomous vehicles, that are continuously assigned new tasks. The synergy of search-based and learning-based methods holds promise for striking a balance in-between effectiveness and efficiency but still faces several challenges such as inferior initial paths, weak search-learning synergy and low sample utilization rate. To address these issues, this paper proposes a new synergized LMAPF approach, named Synergistic Multi-Agent Path Optimization (SMAPO), which consists of two tightly-coupled phases: Primordial Planning and Decision Refinement. In the Primordial Planning phase, we introduce a novel load-balanced A* algorithm that integrates planned and perceived congestion costs, which enhances initial solution quality by evenly distributing spatiotemporal traffic loads, thereby mitigating potential conflicts. In the Decision Refinement phase, we propose a novel Encoder-Decoder based neural network to learn a collaborative optimization policy through multi-agent reinforcement learning. In addition, we leverage dual transformations to augment trajectory samples during online learning, enhancing both the sample utilization rate and overall learning stability. Extensive experiments reveal that our SMAPO is superior to the state-of-the-art baselines in effectiveness, efficiency, and generalization capability. Source code is available at https://github.com/ByteUser-blues/SMAPO.