A new tool for cleaning up multi-robot path plans runs a median 10.5 times faster than the previous best method, without sacrificing solution quality.
Multi-agent path finding, or MAPF, routes many robots through shared space without collisions. Modern learning-based MAPF solvers are fast but sloppy: they often produce valid plans stuffed with avoidable moves, an NP-hard cleanup problem called MAPFC. The existing fix, a tool named Judgelight from researcher Tang and colleagues, runs one large integer linear program across every agent at once, even when most of them never interact. The new work shows that MAPFC instances usually split into small, independent pieces, most involving a single agent that needs no coordination at all, and builds a lightweight solver for exactly those cases.
That split matters because it exposes how much of the "hard" problem was never actually hard. For the coordination-free majority of cases, the new solver is roughly 1,900 times faster than Judgelight; for the smaller set of cases where agents genuinely must negotiate shared space, the researchers fall back to Judgelight or a new CBS-style solver tuned for easier instances. Across the full benchmark suite, that regime-aware combination comes out a median 10.5x faster than Judgelight alone, with matching plan quality and no commercial ILP solver required.
Treat the 1,900x figure as a measure of how much waste was baked into treating every cleanup job as a joint problem, not as the headline result; the number that actually describes real-world performance is the more modest, and still respectable, 10.5x.