# Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions

arXiv: https://arxiv.org/abs/2603.18866 · HTML: https://mlsanity.com/paper/2603.18866/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 19 Mar 2026.

## Builds on (most cited first, 5 of 5)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Time-Independent Planning for Multiple Moving Agents](https://mlsanity.com/paper/2005.13187/) (2020)
- [Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2103.04516/) (2021)
- [Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2412.11678/) (2024)
- [Optimal Multi-Agent Path Finding in Continuous Time](https://mlsanity.com/paper/2508.16410/) (2025)

## Abstract (arXiv)

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%.