跳到正文
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 为无目标任务智能体规划路线。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:未分配任务的机器人可能会妨碍活跃机器人,而将它们引导至指定停放位置又会造成不必要的移动。本文针对含未分配智能体的多智能体路径规划(MAPF-UA)提出流预言机冲突搜索(FOCBS)。FOCBS 使用冲突搜索(CBS)在已分配智能体的路径上进行搜索,并通过最小费用流预言机为无目标的未分配智能体规划路径。当所选的已分配智能体路径使未分配智能体无无碰撞路径可走时,流冲突分支将最小割阻塞者转化为已分配智能体约束,从而在不排除最优解的情况下引导搜索。批量零成本热启动加速了预言机,而避开起点的平局打破规则减少了未分配智能体的移动。对于有限图上的可行实例,我们证明了终止性以及已分配智能体服务时间总和(以最后到达时间衡量)的全局最小化。未分配智能体的移动在所选已分配智能体路径的条件下被最小化,但不具备全局字典序最优性保证。基准实验表明,FOCBS 随未分配智能体数量的增加具有良好的扩展性;消融研究表明,与丢弃无法完成的已分配智能体路径相比,流冲突分支在保持最优性的同时能求解显著更多的实例。仿真和实体机器人实验证明了规划的可执行性,实验室测试相对于基于停放的协调基线将车队移动减少了 40.8%。源代码及相关资源可在 此 https URL 获取
学科: 机器人学(cs.RO);多智能体系统(cs.MA)
引用为: arXiv:2611.24108 [cs.RO]
  (或 arXiv:2611.24108v1 [cs.RO] 用于此版本)
  https://doi.org/10.48550/arXiv.2611.24108

由 DataCite 颁发的 arXiv DOI(待注册)

提交历史

来自:Xi Jin [查看邮箱]
[v1] 2026年11月18日星期三 09:26:08 UTC(10,579 KB)

来源:arXiv cs.MA · arxiv.org