群制御2026/8/25arXiv:2608.24585

ピボット・ステーション型マルチエージェント経路探索：可解性、複雑性、およびアルゴリズム

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

倉庫やロボット駐車場などで、タスクを持つエージェントがピボット（作業台）を経由してからステーションに停車する問題（PS-MAPF）を新たに定義し、可解条件の解明、NP困難性の証明、および3つの解法アルゴリズムを提案した。

詳しい要約

1. どんなもの？

本論文は、Pivot-and-Station Multi-Agent Path Finding (PS-MAPF) という新しいMAPF変種を提案している。これは、倉庫やロボット駐車場などの高密度自動保管システムにおいて、タスクを持つエージェントのサブセットがそれぞれ交換可能なピボット（例：ワークステーション）を訪問し、その後、全エージェントが匿名のステーションに1台ずつ停車するという問題を扱う。

2. 先行研究と比べてどこがすごい？

従来のMAPF研究は、エージェントが特定のゴールに到達することに焦点を当てていたが、PS-MAPFは、タスク実行と停車の両方を考慮し、ピボットの交換可能性とステーションの匿名性を導入する点で新しい。また、solvabilityの完全な特徴付けを提供し、複雑性解析と効率的なアルゴリズムを提示している点が先行研究と比べて優れている。

3. 技術・手法の肝は？

手法の肝は、solvabilityの特徴付け（2-edge-connectedグラフでは常に可解、任意の連結グラフでは構造的なeffective-distance測度による必要十分条件）、NP-hardnessの証明（単一ピボットでもstation-makespanやstation-flowtimeの最小化はNP困難）、および3つのアルゴリズム（完全なベースライン、SATベースの最適ソルバー、Pivot-Prioritized Planning (PPP)）の設計にある。

4. どうやって有効だと検証した？

ベンチマークインスタンスを用いて、PPPがベースラインと比較して、makespanとflowtimeを桁違いに改善し、74-89%のインスタンスを解くことを実験的に検証した。

5. 議論はある？

要旨からは、議論の詳細は不明だが、solvabilityの条件やNP-hardnessの結果は理論的な興味を引く。また、PPPの性能は高いが、最適性は保証されない可能性があり、SATベースの最適ソルバーとの比較や、より大規模なインスタンスでのスケーラビリティが議論の対象となるかもしれない。

6. 次に読むべき論文は？

要旨で参照されている関連研究は明示されていないが、MAPFの一般的な研究や、SATベースのプランニング手法、および高密度保管システムにおけるマルチエージェント経路計画に関する論文が関連する。具体的には、MAPFの古典的なアルゴリズム（CBSなど）や、SAT-based planningの研究を読むことが推奨される。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini

分類: cs.AI

原文アブストラクト

Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.

arXivで原文を読む →arXiv概要ページ