BCBS-AA: Bounded Sub-Optimal Conflict-Based Search for Multi-Agent Path Finding with Asynchronous Actions

Abstract

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs. Many MAPF studies rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the applicability of MAPF planners in practice. To bypass this assumption, various algorithms have been developed to handle asynchronous, non-unit-time actions, ranging from optimal to unbounded sub-optimal algorithms. This paper focuses on bounded sub-optimal algorithms for MAPF with asynchronous actions (MAPF-AA) due to their ability to balance solution quality and runtime efficiency. For MAPF, the recent bounded sub-optimal algorithms can intelligently distribute the sub-optimality bound among the agents based on agent-agent collision to achieve fast planning even with tight bounds. We find that directly adapting these techniques to MAPF-AA can degrade their performance due to asynchronous actions. This paper thus develops new techniques to consider asynchronous actions when distributing the sub-optimality bound among the agents and when selecting nodes for expansion during planning. Results show that our approach achieves up to 60% higher success rates and reduces the number of expansions during planning by up to an order of magnitude compared to existing methods.