Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning
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 Follower, a decentralized lifelong MAPF solver that pairs a heuristic path planner (with congestion-aware dynamic/static transition costs) with an RL-trained local policy that follows the path and resolves collisions.
Problem
Decentralized lifelong multi-agent pathfinding (LMAPF), where agents have no central controller or communication and only observe nearby agents locally, while maximizing throughput and generalizing to unseen maps.
Approach
Combine heuristic search for individual paths, with transition costs penalizing congested cells (static betweenness-like cost plus agent-observed dynamic cost), and a shared recurrent PPO policy that follows the path to the first waypoint and avoids collisions, trained without reward shaping.
Key results
- On maze-like maps, the main learnable competitor PRIMAL2 achieves roughly half the throughput of Follower with 256 agents.
- On the warehouse map, Follower outperforms RHCR with a 1s time cap when agent count reaches 160 and 192, and is much faster per action than RHCR.
- Follower (no RL) and ablations removing cost penalties show notable throughput degradation, supporting that all components are needed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Follower instead of PRIMAL2 | Decentralized lifelong MAPF solvers · Maze-like maps | throughput | Helped |
| use Follower instead of SCRIMP | Decentralized lifelong MAPF solvers · Random maps | throughput | Helped |
| use Follower instead of SCRIMP | Decentralized lifelong MAPF solvers · MovingAI den520d and Paris_1 | throughput | Helped |
| use Follower instead of PRIMAL2 | Decentralized lifelong MAPF solvers · MovingAI den520d and Paris_1 | throughput | Helped |
| use Follower instead of RHCR with a 1s time cap | Lifelong MAPF solvers · warehouse, 160 and 192 agents | throughput | Helped |
| use Follower instead of RHCR | Lifelong MAPF solvers · warehouse | runtime per action decision | Helped |
| use Follower instead of PIBT | Lifelong MAPF solvers · warehouse | throughput | Helped |
| add the learnable policy for collision avoidance (ablation) | Follower · warehouse | throughput | Helped |
| add dynamic cost accumulation for frequently observed cells (ablation) | Follower · warehouse | throughput | Helped |
| add precalculated static costs for frequently used cells (ablation) | Follower · warehouse | throughput | Helped |
| use the full recurrent network instead of the trimmed network without RNN blocks (ablation) | Follower · MovingAI out-of-distribution maps | throughput | Helped |
| use SCRIMP instead of FollowerLite | Decentralized lifelong MAPF solvers · Random maps | throughput | No clear effect |
Surprising findings
- Without the cost-accumulation component or the RL policy, throughput collapses over long episodes due to congestion snowballing.
Limitations
- Assumes accurate static map, perfect localization and synchronized, deterministic action execution.
- No theoretical completeness or optimality guarantees.
- Action space limited to wait and move to adjacent cell.
Experimental setup
Datasets: MovingAI benchmark maps (den520d, Paris_1, Boston_0, den312d, room-64-64-16, room-64-64-8) for out-of-distribution evalu procedurally generated maze and random maps in POGEMA
Benchmarks: POGEMA maze-like maps POGEMA random maps MovingAI den520d MovingAI Paris_1 warehouse map from RHCR paper
Metrics: throughput runtime per action
Baselines: PRIMAL2 SCRIMP PICO RHCR PIBT
Builds on: PPO PRIMAL2 RHCR PIBT SCRIMP
Closest papers by meaning
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.93)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.92)
- MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale (AAAI 2025 · similarity 0.91)
- LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding (AAAI 2025 · similarity 0.91)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.91)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.90)
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.