# Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 16 Dec 2024.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [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)

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

- [Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.12623/) (2025)
- [The Wisdom of Agent Crowds: A Human-AI Interaction Innovation Ignition Framework](https://mlsanity.com/paper/2505.06947/) (2025)
- [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) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step, which may limit their use in practice. Only a few algorithms were developed to address asynchronous actions, and they all lie on one end of the spectrum, focusing on finding optimal solutions with limited scalability. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability, by finding an unbounded sub-optimal solution for many agents. Our method leverages both search methods (LSS) in handling asynchronous actions and rule-based planning methods (PIBT) for MAPF. We analyze the properties of our method and test it against several baselines with up to 1000 agents in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the baselines with about 25% longer makespan.