ピボット・ステーション型マルチエージェント経路探索：可解性、複雑性、およびアルゴリズム
Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
倉庫やロボット駐車場などで、タスクを持つエージェントがピボット（作業台）を経由してからステーションに停車する問題（PS-MAPF）を新たに定義し、可解条件の解明、NP困難性の証明、および3つの解法アルゴリズムを提案した。
著者: 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.