# Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 8 Mar 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning](https://mlsanity.com/paper/1903.00994/) (2019)
- [Subdimensional Expansion for Multi-objective Multi-agent Path Finding](https://mlsanity.com/paper/2102.01353/) (2021)
- [Modifying Optimal SAT-based Approach to Multi-agent Path-finding Problem to Suboptimal Variants](https://mlsanity.com/paper/1707.00228/) (2017)

## Built on by (most cited first, 5 of 5)

- [Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2412.11678/) (2024)
- [Multi-objective Conflict-based Search Using Safe-interval Path Planning](https://mlsanity.com/paper/2108.00745/) (2021)
- [DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding](https://mlsanity.com/paper/2312.06314/) (2023)
- [Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2603.18866/) (2026)
- [Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization](https://mlsanity.com/paper/2604.05416/) (2026)

## Abstract (arXiv)

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspace modeled as a graph, A*-based approaches have been widely investigated due to their guarantees on completeness and solution optimality, and have demonstrated their efficiency in many scenarios. However, almost all of these A*-based methods assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions (MAPF-AA) where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Numerical results are presented to corroborate the performance of LSS and the applicability of the proposed method is verified in the Robotarium, a remotely accessible swarm robotics research platform.