The Computational Complexity of Multi-Agent Pathfinding

357 concepts284 papers1 proposal

Single-agent pathfinding is a foundational, well-solved problem in computer science. Algorithms like A* find optimal paths in polynomial time because the search space is strictly bounded by the size of the environment. However, as noted by Nathan R. Sturtevant et al. in Heuristic Search Comes of Age, adding multiple agents transforms pathfinding from a simple reachability problem into a complex combinatorial challenge.

To understand why, consider $k$ agents navigating a graph with $V$ vertices. The joint state space containing all possible agent configurations grows exponentially as $V^k$. Every step an agent takes creates a potential spatio-temporal conflict with every other agent. Finding a globally optimal, collision-free path configuration across time is inherently NP-hard, a fundamental bottleneck emphasized by Jiaoyang Li et al. in Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search.

The Drivers of Intractability

What makes multi-agent pathfinding (MAPF) so computationally brutal? The complexity is driven by several interacting dimensions:

  • Agent Density and Interdependence: In sparse environments, agents rarely cross paths and can be planned for individually. Trevor Scott Standley in Finding Optimal Solutions to Cooperative Pathfinding Problems introduced Independence Detection to isolate independent agents or groups. However, Standley demonstrated that in highly congested environments, agents become deeply interdependent. The computational complexity reverts to exponential because the size of the largest coupled group approaches the total number of agents, forcing solvers to search the joint space.
  • Environmental Topology: The structure of the map dictates the difficulty of avoiding collisions. Duncan Adamson et al. in Collision-Free Robot Scheduling show that in complex layouts like lattice or planar graphs, the number of alternative paths grows exponentially, making scheduling NP-complete. Conversely, Mokhtar Khorshid et al. in A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding prove that on tree topologies, the problem can be solved in polynomial time using localized swapping strategies, even when the environment is nearly saturated with agents.
  • Real-World Constraints and Uncertainty: The theoretical hardness compounds when moving from abstract grids to physical execution. Hang Ma et al. note in Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems that physical constraints like velocity and safety distances drastically expand the search space. Furthermore, when execution delays occur, determining whether a pre-planned set of paths remains deadlock-free is itself an NP-complete problem, as proven by Yihao Liu 0002 et al. in Multi-Agent Path Execution with Uncertainty.

Algorithmic Strategies to Tame the Explosion

To deploy MAPF in real-world systems like automated warehouses, researchers must bypass the exponential worst-case complexity. The literature reveals three primary paradigms to achieve scalability.

Decomposition and Conflict Reasoning

Instead of searching the joint $V^k$ space directly, modern solvers decouple the problem. Conflict-Based Search (CBS) frames MAPF as a two-level optimization: the low level plans paths for individual agents, while the high level builds a tree to resolve conflicts. To make this scalable, Jiaoyang Li et al. developed advanced heuristics that reason deeply about agent dependencies, preventing the high-level search tree from exploding.

Trading Optimality for Scalability

When finding the absolute shortest path is too expensive, we can relax our goals. Liron Cohen et al. in Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding explore bounded-suboptimal algorithms that guarantee solutions within a fixed factor of the optimum, significantly reducing search overhead.

Taking this further, Jiaoyang Li et al. introduced an anytime approach using Large Neighborhood Search in Anytime Multi-Agent Path Finding via Large Neighborhood Search. This method quickly finds a suboptimal initial solution and iteratively repairs local conflicts, allowing the system to scale to thousands of agents by avoiding global combinatorial optimization.

Decentralization and Learning

The ultimate way to avoid a centralized combinatorial explosion is to distribute the computation entirely. Guillaume Adrien Sartoretti et al. developed PRIMAL in PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning, combining reinforcement learning and imitation learning to let agents navigate locally based on partial observations.

More recently, Anton Andreychuk introduced MAPF-GPT in MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale, demonstrating that a transformer trained on massive expert trajectories can achieve zero-shot decentralized pathfinding, entirely sidestepping runtime centralized search.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 280 papers
  2. Version 1 · 2026-10-04 · 389 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_multi_agent_pathfinding_complexity_171c8866,
  title = {multi-agent pathfinding complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-pathfinding-complexity/rdr_171c8866d2044c58b41c172294afcf8b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_multi_agent_pathfinding_complexity_171c8866_v2,
  title = {multi-agent pathfinding complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-pathfinding-complexity/rdr_171c8866d2044c58b41c172294afcf8b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake