Search papers, labs, and topics across Lattice.
This paper addresses the incompleteness of Continuous-time Conflict-Based Search (CCBS) for Multi-Agent Path Finding with Asynchronous Actions (MAPF-AA) due to its continuous state space. They introduce Conflict-Based Search with Asynchronous Actions (CBS-AA), which guarantees completeness and optimality for MAPF-AA by discretizing the action space. Experimental results demonstrate that CBS-AA, enhanced with conflict resolution techniques, significantly reduces the search space, achieving up to a 90% reduction in the number of branches.
Optimal multi-agent path planning with asynchronous actions is now provably complete, sidestepping the theoretical incompleteness of prior continuous-time approaches.
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. Most existing MAPF algorithms 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 use of MAPF planners in practice. To get rid of this assumption, Continuous-time Conflict-Based Search (CCBS) is a popular approach that can find optimal solutions for MAPF with asynchronous actions (MAPF-AA). However, CCBS has recently been identified to be incomplete due to an uncountably infinite state space created by continuous wait durations. This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue and can solve MAPF-AA with completeness and solution optimality guarantees. Based on CBS-AA, we also develop conflict resolution techniques to improve the scalability of CBS-AA further. Our test results show that our method can reduce the number of branches by up to 90%.
