Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MATS-LP, a decentralized multi-agent neural MCTS for lifelong MAPF that plans over each agent's intrinsic MDP built from local observations, using a PPO-trained lightweight policy (CostTracer) as the simulation/prior policy.
Problem
Lifelong multi-agent pathfinding under decentralized partial observability, where agents see others only locally and cannot communicate; learned MAPF solvers generalize poorly and centralized replanning scales badly.
Approach
Each agent builds an egocentric intrinsic MDP from its observation and runs AlphaZero-style neural MCTS over joint actions of nearby agents (with greedy actions for distant ones), using a compact PPO-trained policy/value network (CostTracer, ~161K parameters) for priors and value estimates.
Key results
- MATS-LP gains 15.6% higher throughput than SCRIMP on random 20x20 maps and about twice the throughput of PRIMAL2 on average.
- On maze-like maps MATS-LP achieves 46.2% higher throughput than SCRIMP and 38.8% higher than PRIMAL2 on average.
- On the warehouse map MATS-LP throughput is 15.8% above SCRIMP and 27.1% above PRIMAL2; its decision time rises from 103ms to 300ms as agents go from 32 to 192.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MATS-LP instead of SCRIMP | LMAPF on random 20×20 maps · Random maps, 20×20, varying obstacle densities | throughput: 15.6% higher throughput on average | Helped |
| Use MATS-LP instead of PRIMAL2 | LMAPF on random 20×20 maps · Random maps, 20×20, varying obstacle densities | throughput: more than twice less throughput than MATS-LP on average | Helped |
| Use MATS-LP instead of SCRIMP | LMAPF on maze-like maps · Maze-like maps, 10×10, 20×20, and 30×30 | throughput: 46.2% higher throughput on average | Helped |
| Use MATS-LP instead of PRIMAL2 | LMAPF on maze-like maps · Maze-like maps, 10×10, 20×20, and 30×30 | throughput: 38.8% | Helped |
| Use PRIMAL2 instead of SCRIMP | LMAPF on 30×30 maze maps with 32 or 64 agents · 30×30 maze maps, 32 or 64 agents | throughput | Helped |
| Use MATS-LP instead of SCRIMP | LMAPF on the warehouse-like map · Warehouse-like map | throughput: 15.8% higher throughput on average | Helped |
| Use MATS-LP instead of PRIMAL2 | LMAPF on the warehouse-like map · Warehouse-like map | throughput: 27.1% higher | Helped |
| Add MCTS to CostTracer (ablation) | MATS-LP on the warehouse-like map · Warehouse-like map | throughput: almost twice | Helped |
| Replace CostTracer with a random policy (ablation) | MATS-LP on the warehouse-like map · Warehouse-like map | throughput | Hurt |
| Plan for proximal agents rather than only the egocentric agent (ablation) | MATS-LP on the warehouse-like map · Warehouse-like map, increasing number of agents | throughput | Helped |
| Increase expansions from 250 to 500 (ablation) | MATS-LP on the warehouse-like map · Warehouse-like map | throughput | Helped |
| Reduce expansions from 250 to 125 (ablation) | MATS-LP on the warehouse-like map · Warehouse-like map | throughput | Hurt |
Surprising findings
- Planning-free CostTracer policy alone yields throughput almost half that of MATS-LP, and a random policy inside MCTS performs worst, showing the learned prior is crucial.
- PRIMAL2 underperforms on random maps, which is attributed to out-of-distribution map topology.
Limitations
- Decision time is higher than SCRIMP's and grows with agent density.
- Relies on a limited field of view and a restricted set of nearby planning agents, with greedy actions for distant agents.
- Learned MCTS is not trained end-to-end; the simulation policy is pre-trained separately with PPO.
Experimental setup
Datasets: randomly generated 20x20 grid maps PRIMAL2 maze generator maps 33x46 warehouse map
Benchmarks: random 20x20 grid maps with 0-30% obstacles maze-like maps 10x10, 20x20, 30x30 33x46 warehouse map
Metrics: throughput decision time per agent 95% confidence intervals
Baselines: Primal2 SCRIMP
Builds on: AlphaZero PUCT Primal2 PPO
Closest papers by meaning
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.93)
- MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale (AAAI 2025 · similarity 0.90)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.90)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.90)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.90)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.