How can I scale asynchronous multi-agent pathfinding?
Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions
This paper addresses the Multi-Agent Path Finding (MAPF) problem with asynchronous actions (MAPF-AA), meaning agents move at different speeds and don't act in lockstep. It introduces Loosely Synchronized Rule-Based Planning (LSRP), a new algorithm that scales to hundreds of agents by sacrificing optimality for speed. LSRP leverages a priority-based planning approach and a caching mechanism to manage agents' asynchronous actions. A key extension, LSRP-SWAP, adds a swapping mechanism for agents to navigate complex environments where simple pushing is insufficient, like tree-like graphs. Although LSRP/LSRP-SWAP generates longer plans than optimal algorithms, they are significantly faster and can handle orders of magnitude more agents, crucial for large-scale multi-agent web applications using LLMs. This is particularly relevant for developers of LLM-based multi-agent systems, as asynchronous actions are more realistic and scalable than synchronous alternatives.