Flexibility-Based Traffic Flow Optimisation in Lifelong Multi-Agent Path Finding

Lifelong Multi-Agent Path Finding (LMAPF) is a coordination problemwhereateamofagentsworkscontinuouslytocompletetasksin a shared environment. Recent approaches for LMAPF combine fast myopic planners with high-level congestion-aware path guidance; they can coordinate thousands of agents in real-time. A main drawback is that congestion estimates assume each agent will follow one specific, pre-computed, time-independent path. This overlooks the existence of multiple cost-equivalent paths, leading to potentially inaccurate predictions and low-quality guidance. In this paper, we propose a novel method for computing congestion-aware guidance that reasons about this ambiguity. Instead of committing to a single route, our approach calculates a probabilistic traffic flow by consideringthelikelihoodoftravellingacrossallcost-equivalentpaths. By reasoning over probability distributions to determine expected congestion we generate more robust and accurate guidance heuristics, which in turn enable planners to make more informed decisions. We conduct extensive experiments on large-scale LMAPF benchmarks with up to 16, 000 agents. Results show that our approach consistently outperforms baseline algorithms in system throughput.

Authors

• Peiqian Lin Monash University
• Zhe Chen Monash University
• David L. Dowe Monash University
• Daniel Harabor Monash University

Keywords

• Heuristic Search
• Flexibility
• Multi-Agent Path Finding
• Lifelong MAPF
• Combinatorial Optimisation