UA-MAPF: Unassigned Agents in Compilation-based MAPF Research

Pavel Surynek submitted a paper titled "Unassigned Agents in Compilation-based Multi-agent Path Finding" to arXiv on 14 Jun 2026 (arXiv:2606.15797). The paper shows that MAPF with unassigned agents, abbreviated UA-MAPF, can be expressed in compilation-based techniques that formulate the problem as Boolean satisfiability, adapting the recent SMT-CBS and NRF-SAT solvers.

What is UA-MAPF?

UA-MAPF is a variant of multi-agent path finding where some agents keep the standard MAPF setting with initial positions and individual goals, while the remaining agents have initial positions but no goal, the "unassigned agents." Although unassigned agents do not need to reach any goal position, they must be moved out of the way of standard agents when needed. That need to relocate non-goal agents is the specific challenge UA-MAPF introduces for MAPF solvers.

How do compilation-based solvers handle UA-MAPF?

Surynek demonstrates that UA-MAPF can be encoded using recent compilation-based MAPF techniques that reduce MAPF to Boolean satisfiability. The paper adapts two solver families: SMT-CBS, which is based on counterexample guided abstraction refinement, and NRF-SAT, based on non-refined abstractions. Both approaches are presented as recent solvers in the compilation-based stream, and the paper frames UA-MAPF in terms compatible with those SAT formulations.

The submission emphasizes the role of compilation-based techniques for MAPF because of their modularity and adaptability for non-standard variants. By showing an encoding into SAT and concrete adaptations of SMT-CBS and NRF-SAT, the work connects the UA-MAPF variant to an established compilation pipeline rather than proposing a wholly new solver architecture.

Why it matters

Compilation-based MAPF methods are valued for modularity and adaptability, qualities the paper highlights. Adapting SMT-CBS and NRF-SAT to UA-MAPF means existing SAT-based infrastructures can be repurposed for settings where not every agent has a goal, rather than requiring bespoke algorithms. That opens the possibility of reusing refinement loops, SAT encodings, and toolchains already developed for standard MAPF to address the practical complication of unassigned agents.

What to watch

Look for the paper's full PDF and TeX source on arXiv (arXiv:2606.15797) for the precise encodings and adaptation details. The concrete next signals will be empirical evaluations or code releases that apply the adapted SMT-CBS and NRF-SAT encodings to benchmark UA-MAPF instances and report solver behavior when unassigned agents must be relocated.