# Solving Multiagent Path Finding on Highly Centralized Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 50 references that are in the map.
- First posted on arXiv 12 Dec 2024.

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

- [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)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding](https://mlsanity.com/paper/2312.15908/) (2023)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology](https://mlsanity.com/paper/2312.09646/) (2023)
- [Improved Anonymous Multi-Agent Path Finding Algorithm](https://mlsanity.com/paper/2312.10572/) (2023)
- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [The Graph Motif problem parameterized by the structure of the input graph](https://mlsanity.com/paper/1503.05110/) (2015)
- [Metric Dimension Parameterized by Max Leaf Number](https://mlsanity.com/paper/1506.01749/) (2015)

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

- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)

## Abstract (arXiv)

The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with 11 leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.