# Iterative Refinement for Real-Time Multi-Robot Path Planning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2021.

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

- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [Graph Attention-Guided Search for Dense Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.17382/) (2025)
- [Engineering LaCAM^ast: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.04292/) (2023)
- [SkyRover: A Modular Simulator for Cross-Domain Pathfinding](https://mlsanity.com/paper/2502.08969/) (2025)
- [Local Guidance for Configuration-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.19072/) (2025)
- [Fault-Tolerant Offline Multi-Agent Path Planning](https://mlsanity.com/paper/2211.13908/) (2022)
- [Terraforming -- Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2305.11510/) (2023)
- [Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks](https://mlsanity.com/paper/2309.10275/) (2023)
- [Alternating Target-Path Planning for Scalable Multi-Agent Coordination](https://mlsanity.com/paper/2605.07744/) (2026)
- [Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances](https://mlsanity.com/paper/2609.39559/) (2026)

## Abstract (arXiv)

We study the iterative refinement of path planning for multiple robots, known as multi-agent pathfinding (MAPF). Given a graph, agents, their initial locations, and destinations, a solution of MAPF is a set of paths without collisions. Iterative refinement for MAPF is desirable for three reasons: 1)~optimization is intractable, 2)~sub-optimal solutions can be obtained instantly, and 3)~it is anytime planning, desired in online scenarios where time for deliberation is limited. Despite the high demand, this is under-explored in MAPF because finding good neighborhoods has been unclear so far. Our proposal uses a sub-optimal MAPF solver to obtain an initial solution quickly, then iterates the two procedures: 1)~select a subset of agents, 2)~use an optimal MAPF solver to refine paths of selected agents while keeping other paths unchanged. Since the optimal solvers are used on small instances of the problem, this scheme yields efficient-enough solutions rapidly while providing high scalability. We also present reasonable candidates on how to select a subset of agents. Evaluations in various scenarios show that the proposal is promising; the convergence is fast, scalable, and with reasonable quality.