Scalable Search and Learning for Multi Agent Path Finding

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2389 papers453 conceptsfrozen 2026-10-04

Multi-Agent Path Finding (MAPF) is the problem of moving a fleet of agents from their starting positions to their respective goals without collisions. While finding a path for one robot is a solved problem, finding paths for hundreds of robots in a shared warehouse or laboratory is a combinatorial nightmare. As Nathan R. Sturtevant and colleagues note in Heuristic Search Comes of Age, the transition from single-agent navigation to multi-agent coordination shifts the problem from simple reachability to a complex constraint satisfaction challenge.

The core difficulty is the exponential growth of the search space. If one agent has $N$ possible moves, $K$ agents have $N^K$ possible joint moves at every time step. This makes optimal solving NP-hard. To make these systems work in the real world, researchers have developed three primary strategies: decomposing the search, trading optimality for speed, and learning from experience.

Decomposing the Conflict Space

The most intuitive way to solve MAPF is to treat agents as independent until they aren't. Trevor Scott Standley pioneered this with Independence Detection (ID). The algorithm plans for each agent individually; if two agents collide, it merges them into a single "meta-agent" and replans their paths together. This works beautifully until the environment becomes congested, at which point the meta-agents grow so large that the search becomes intractable again.

A more flexible approach is to search for a priority ordering. In Searching with Consistent Prioritization, Daniel Harabor, Jiaoyang Li, and Sven Koenig introduced Priority-Based Search (PBS). Instead of a fixed order (e.g., "Agent 1 always goes first"), PBS treats priorities as constraints to be discovered. If two agents collide, the algorithm tries two branches: one where Agent A has priority over B, and one where B has priority over A. This allows the system to resolve complex coordination problems for hundreds of agents by only imposing the minimum necessary constraints.

Bounded Suboptimality and Iterative Refinement

In industrial settings like automated warehouses, a "perfect" path that takes 10 minutes to compute is useless if a "good enough" path can be found in 10 milliseconds. This realization led to Bounded-Suboptimal Search.

Jiaoyang Li and Wheeler Ruml developed EECBS, which uses online learning to estimate how much a path can be improved. By guaranteeing that the final solution is within a specific factor (e.g., 1.1x) of the optimal cost, EECBS can solve for 1,000 agents in under a minute—a feat impossible for exact solvers.

When even bounded search is too slow, researchers turn to Large Neighborhood Search (LNS). As described in Anytime Multi-Agent Path Finding via Large Neighborhood Search, the idea is to start with a "quick and dirty" solution that might have many delays or long paths. The algorithm then repeatedly selects a "neighborhood" (a subset of agents), erases their paths, and replans them optimally while keeping other agents' paths fixed. This "anytime" property is crucial for robotics: the system always has a valid plan ready to execute, and it simply gets better the longer it is allowed to think.

The Neural Shift: Learning to Plan

The latest frontier moves away from explicit search trees toward neural architectures. The challenge with traditional search is that it often "re-invents the wheel" for every new map. MAPF-GPT, developed by Anton Andreychuk and Konstantin Yakovlev, treats pathfinding as a massive imitation learning problem. By training on a billion expert trajectories, the model learns the "intuition" of coordination—knowing when to wait and when to bypass—without needing to explicitly search through every possible collision.

Similarly, Zhongxia Yan and Cathy Wu demonstrated in Neural Neighborhood Search that deep learning can be used to guide traditional algorithms. Instead of picking random agents to replan in LNS, a neural network identifies which agents are causing the most congestion, providing a 4x speedup in finding high-quality solutions.

By combining the rigorous guarantees of search with the pattern-recognition power of neural networks, the field is moving toward a future where thousands of autonomous agents can navigate dense, dynamic environments with the same fluidity as a single robot.

Papers in this version

Showing 60 of 389 papers.

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 1, frozen text):

@misc{lacuna_scalable_search_and_learning_for_multi_a_171c8866_v1,
  title = {Scalable Search and Learning for Multi Agent Path Finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-search-and-learning-for-multi-agent-path-finding/rdr_171c8866d2044c58b41c172294afcf8b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}