Research map / Multi-agent systems and games / Human-AI and goal-conditioned
LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding
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 LNS2+RL, which replaces the prioritized planner inside LNS2 with a PPO-trained MARL replanner in early iterations, switching to PP+SIPPS later to clear remaining collisions.
Problem
Multi-agent path finding for high-agent-density tasks, where LNS2's fast prioritized-planning replanner leaves many collisions and MARL planners degrade outside their training scale and often fail one-shot.
Approach
Hybridize LNS2 with a MARL replanner: early LNS2 iterations use a PPO-trained, partially observable MARL policy (with SIPPS reference paths, predicted paths, and congestion maps) for 8-agent replanning, falling back to PP+SIPPS for incomplete agents and later iterations, with an adaptive switch based on a queue of CP comparisons.
Key results
- On random-small 10x10 maps at 50%-65% agent density, LNS2+RL success rate was 82%/70%/59%/27% versus LNS2's 80%/68%/50%/27%, with remaining colliding pairs reduced by roughly 25-30%.
- On maze maps at 20% density LNS2+RL reached 100% SR versus LNS2's 92%, and on room maps at 40% density 100% versus 90%.
- LaCAM, EECBS and SCRIMP reached 0% SR on most complex-structure maps where LNS2+RL achieved substantial success rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine MARL replanning with LNS2 and adaptive switching to PP+SIPPS | LNS2 · Random-small, 50% agent density | success rate: 80% -> 82% | Helped |
| combine MARL replanning with LNS2 and adaptive switching to PP+SIPPS | LNS2 · Maze, 20% agent density | success rate: 92% -> 100% | Helped |
| combine MARL replanning with LNS2 and adaptive switching to PP+SIPPS | LNS2 · Random-small, 50% agent density | sum of cost: 831.0 -> 852.7 | Hurt |
| use MARL policy instead of PP+SIPPS for low-level replanning | LNS2 low-level replanning · Random-medium, 65% agent density, replanning iteration 1 | collisions: -73.7% | Helped |
| use MARL policy instead of PP+SIPPS for low-level replanning | LNS2 low-level replanning · Random-medium, 65% agent density, replanning iteration 1 | time: +1,175% | Hurt |
| set neighborhood size to 4 instead of 8 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 55% | Hurt |
| set neighborhood size to 16 instead of 8 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 57% | Hurt |
| vary switch threshold rho from 0.3 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 58%, 57%, 59%, 50%, 56% | Mixed |
| stop MARL planning at t_l=0.8 instead of t_l=1.2 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 55% | Hurt |
| stop MARL planning at t_l=1.6 instead of t_l=1.2 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 58% | Hurt |
| set maximum hybrid path length t_h to 1.8 instead of 2.2 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 57% | Hurt |
| set maximum hybrid path length t_h to 2.6 instead of 2.2 (ablation) | LNS2+RL · Random-small, 60% agent density | success rate: 59% -> 54% | Hurt |
Surprising findings
- The MARL planner reduces collisions substantially but its advantage in colliding pairs shrinks with iterations, and its one-shot success rate drops sharply, motivating SIPPS-based path supplementation.
- A single MARL model trained on 8-agent random-obstacle maps generalizes to other team sizes and map structures without retraining.
Limitations
- MARL replanner is roughly seven times slower than PP+SIPPS, so it is used only in early iterations.
- Hyperparameters such as neighborhood size and switching threshold need task-specific tuning.
- Performance on the largest 50x50 maps remains low (35% SR at best), and all tasks use a high agent density setting.
Experimental setup
Datasets: randomly generated MAPF instances with random obstacles
Benchmarks: random-small random-medium random-large empty maze room warehouse MAPF maps
Metrics: success rate sum of costs runtime remaining colliding pairs
Baselines: LNS2 EECBS LaCAM SCRIMP
Builds on: LNS2 PPO SCRIMP ODrM*
Closest papers by meaning
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.91)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.90)
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding (ICLR 2025 · similarity 0.89)
- MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale (AAAI 2025 · similarity 0.89)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
- Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search (AAAI 2024 · similarity 0.88)
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.