Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
DOI:
https://doi.org/10.1609/aaai.v38i18.30054Keywords:
SO: Heuristic Search, ROB: Motion and Path Planning, MAS: Multiagent Planning, SO: Combinatorial OptimizationAbstract
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.Downloads
Published
2024-03-24
How to Cite
Chen, Z., Harabor, D., Li, J., & Stuckey, P. J. (2024). Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18), 20674-20682. https://doi.org/10.1609/aaai.v38i18.30054
Issue
Section
AAAI Technical Track on Search and Optimization