arXiv cs.MA· Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li, Jun Jiang, Weiwei Shang·· 23 小时前AI 评分26
FOCBS:面向含未分配智能体的多智能体路径规划的非对称分解方法
Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents
AI 导读
针对未分配任务机器人可能阻塞活跃机器人的问题,研究者提出 flow-oracle conflict-based search(FOCBS),用 CBS 搜索已分配智能体路径,并通过 min-cost flow oracle 为无目标任务智能体规划路线。
正文 · 原文
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 this https URL
| Subjects: | Robotics (cs.RO); Multiagent Systems (cs.MA) |
| Cite as: | arXiv:2611.24108 [cs.RO] |
| (or arXiv:2611.24108v1 [cs.RO] for this version) | |
| https://doi.org/10.48550/arXiv.2611.24108 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Xi Jin [view email]
[v1]
Wed, 18 Nov 2026 09:26:08 UTC (10,579 KB)
来源:arXiv cs.MA · arxiv.org