cs.RONov 18, 2026

Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents

Authors: Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li, Jun Jiang, Weiwei Shang

Organizations: University of Science and Technology of China · Hefei National Laboratory · State Key Laboratory of Precision and Intelligent Chemistry

Abstract

Robots without assigned tasks may obstruct active robots, while routing them to designated parking locations can cause unnecessary travel. This article proposes flow-oracle conflict-based search (FOCBS) for Multi-Agent Path Finding with unassigned agents (MAPF-UA). FOCBS searches over assigned-agent paths using conflict-based search (CBS) and routes targetless unassigned agents through a min-cost flow oracle. When the selected assigned-agent paths leave unassigned agents no collision-free paths, flow-conflict branching converts min-cut blockers into assigned-agent constraints, which guide the search without excluding optimal solutions. A batched zero-cost warm start accelerates the oracle, and start-avoiding tie-breaking reduces unassigned-agent movement. For feasible instances on finite graphs, we prove termination and global minimization of assigned-agent sum of service time, measured by last-arrival times. Unassigned-agent movement is minimized conditional on the selected assigned-agent paths, without a global lexicographic optimality guarantee. Benchmark experiments show that FOCBS scales well with the number of unassigned agents, and ablation studies show that, compared with discarding non-completable assigned-agent paths, flow-conflict branching solves substantially more instances while retaining optimality. Simulation and physical-robot experiments demonstrate plan executability, with laboratory tests reducing fleet travel by 40.8% relative to the parking-based coordination baseline. The source code and related resources are available at https://github.com/Chin-hsi/focbs

Figures & tables

Explore similar work

CardsList
  1. AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

    Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianRobust MAPFConflict-Based Search

  2. Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions

    Mar 19, 2026Xuemian Wu, Shizhe Zhao, Zhongqiang RenMulti-Agent Path FindingConflict-Based Search

  3. Unassigned Agents in Compilation-based Multi-agent Path Finding

    Jun 14, 2026Pavel SurynekCounterexample-Guided RefinementMulti-Agent Path Finding