# Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 22 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [HyperTree Proof Search for Neural Theorem Proving](https://mlsanity.com/paper/2205.11491/) (2022)
- [POGEMA: Partially Observable Grid Environment for Multiple Agents](https://mlsanity.com/paper/2206.10944/) (2022)
- [Monte-Carlo Robot Path Planning](https://mlsanity.com/paper/2208.02673/) (2022)
- [Multi-agent Multi-target Path Planning in Markov Decision Processes](https://mlsanity.com/paper/2205.15841/) (2022)

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

- [Mulberry: Empowering MLLM with o1-like Reasoning and Reflection via Collective Monte Carlo Tree Search](https://mlsanity.com/paper/2412.18319/) (2024)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [SE-Agent: Self-Evolution Trajectory Optimization in Multi-Step Reasoning with LLM-Based Agents](https://mlsanity.com/paper/2508.02085/) (2025)
- [VLA-Reasoner: Empowering Vision-Language-Action Models with Reasoning via Online Monte Carlo Tree Search](https://mlsanity.com/paper/2509.22643/) (2025)
- [DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search](https://mlsanity.com/paper/2509.25454/) (2025)
- [MC-NEST: Enhancing Mathematical Reasoning in Large Language Models leveraging a Monte Carlo Self-Refine Tree](https://mlsanity.com/paper/2411.15645/) (2024)
- [MCTSr-Zero: Self-Reflective Psychological Counseling Dialogues Generation via Principles and Adaptive Exploration](https://mlsanity.com/paper/2505.23229/) (2025)
- [MCTS-SQL: Light-Weight LLMs can Master the Text-to-SQL through Monte Carlo Tree Search](https://mlsanity.com/paper/2501.16607/) (2025)
- [Toward Template-Free Explainability for Monte Carlo Tree Search](https://mlsanity.com/paper/2605.16524/) (2026)

## Abstract (arXiv)

In this work we study a well-known and challenging problem of Multi-agent Pathfinding, when a set of agents is confined to a graph, each agent is assigned a unique start and goal vertices and the task is to find a set of collision-free paths (one for each agent) such that each agent reaches its respective goal. We investigate how to utilize Monte-Carlo Tree Search (MCTS) to solve the problem. Although MCTS was shown to demonstrate superior performance in a wide range of problems like playing antagonistic games (e.g. Go, Chess etc.), discovering faster matrix multiplication algorithms etc., its application to the problem at hand was not well studied before. To this end we introduce an original variant of MCTS, tailored to multi-agent pathfinding. The crux of our approach is how the reward, that guides MCTS, is computed. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior, while leaving them freedom to get off the track if it is needed to avoid collisions. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure. Empirically we show that the suggested method outperforms the baseline planning algorithm that invokes heuristic search, e.g. A*, at each re-planning step.