# Improved Anonymous Multi-Agent Path Finding Algorithm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 17 Dec 2023.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2110.14891/) (2021)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution](https://mlsanity.com/paper/2109.04264/) (2021)

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

- [Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses](https://mlsanity.com/paper/2408.14527/) (2024)
- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)
- [Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT)](https://mlsanity.com/paper/2508.21205/) (2025)
- [Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schr"odinger Bridges](https://mlsanity.com/paper/2605.10917/) (2026)

## Abstract (arXiv)

We consider an Anonymous Multi-Agent Path-Finding (AMAPF) problem where the set of agents is confined to a graph, a set of goal vertices is given and each of these vertices has to be reached by some agent. The problem is to find an assignment of the goals to the agents as well as the collision-free paths, and we are interested in finding the solution with the optimal makespan. A well-established approach to solve this problem is to reduce it to a special type of a graph search problem, i.e. to the problem of finding a maximum flow on an auxiliary graph induced by the input one. The size of the former graph may be very large and the search on it may become a bottleneck. To this end, we suggest a specific search algorithm that leverages the idea of exploring the search space not through considering separate search states but rather bulks of them simultaneously. That is, we implicitly compress, store and expand bulks of the search states as single states, which results in high reduction in runtime and memory. Empirically, the resultant AMAPF solver demonstrates superior performance compared to the state-of-the-art competitor and is able to solve all publicly available MAPF instances from the well-known MovingAI benchmark in less than 30 seconds.