Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
This addresses scalability issues in robotics for large teams of agents, though it appears incremental as it builds on existing MAPF methods.
The paper tackles the problem of congestion in Multi-Agent Path Finding (MAPF) by proposing congestion-avoiding paths, reporting large improvements in solution quality for one-shot MAPF and overall throughput for lifelong MAPF.
Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF.