未割当エージェントを含むマルチエージェント経路計画のための非対称分解手法
Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents
タスク未割当のロボットをフローオラクルで経路付けしつつ、割当済みエージェントの経路をCBSで探索するFOCBSを提案。割当済みのサービス時間和を大域最適化し、駐車方式より移動を40.8%削減した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li, Jun Jiang, Weiwei Shang
分類: cs.RO, cs.MA
原文アブストラクト
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
関連論文
- 異種グラフニューラルネットワークを用いたマルチエージェント経路計画のための共有ロードマップ生成と評価マルチエージェント経路計画
- エレベーター付きマルチエージェント経路探索のための競合ベース探索マルチエージェント経路計画
- 可動障害物を含むマルチエージェント経路探索のための競合ベース探索と優先度計画マルチエージェント経路計画
- 階層型LA-MAPF:大規模エージェントMAPF問題の分解による解法高速化マルチエージェント経路計画
- 自動倉庫における実ロボットダイナミクスと相互依存タスクを考慮したマルチエージェント経路計画マルチエージェント経路計画
- 行き詰まりからの脱出:デッドロック回復アプローチマルチエージェント経路計画
