New Approach Addresses Unassigned Agents in Multi-Agent Pathfinding

A new paper explores how to integrate the concept of "unassigned agents" into compilation-based multi-agent pathfinding (MAPF) problems. In standard MAPF, all agents have defined start and goal positions, and the task is to navigate them collision-free. However, in real-world scenarios, some agents might only have an initial position without a specific destination; their primary role is to move aside if they obstruct other goal-oriented agents. This presents a unique challenge for traditional MAPF solvers. The researchers demonstrate that this variant, termed UA-MAPF (MAPF with unassigned agents), can be effectively expressed within recent compilation-based MAPF techniques. Specifically, they adapt solvers like SMT-CBS and NRF-SAT, which convert MAPF problems into Boolean satisfiability problems. By modifying these counterexample-guided abstraction refinement and non-refined abstraction solvers, the framework can now manage the movement of unassigned agents, ensuring they clear paths for other agents without needing to reach a specific goal themselves.