  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, with reasonable quality, and
practical because it can be interrupted whenever the solution is needed.
