連結かつ無向のグラフ上で、複数のエージェントを衝突なく移動させる問題を扱う。エージェントは、ピボットを訪問する必要があるタスク付きエージェントと、直接目的地へ向かえるタスクなしエージェントに分類される。最終的な目的地であるステーションは匿名的に割り当てられ、全エージェントがそれぞれ異なるステーションに停止する必要がある。従来のMAPFと比較して、中間リソースの訪問制約と終端位置の匿名性を組み合わせている点が特徴である。
2-辺連結グラフであれば常に解が存在することや、任意の連結グラフにおける解の存在条件が、空き頂点数に関連する構造的な有効距離によって決定されることを明らかにした。また、ピボットが一つのみの場合であっても、最大完了時間（makespan）や完了時刻の総和（flowtime）の最小化がNP困難であることを証明した。
提案手法であるPivot-Prioritized Planning (PPP) は、二段階の処理を行う。第一段階では、優先順位に基づきSpace-Time A*を用いてタスクエージェントをピボットへ移動させる。第二段階では、最大流問題を用いて全エージェントを目的地へ割り当てて移動させる。また、完全性を保証するBaseline Algorithm (BA) は、タスクエージェントを順番にピボットへ運び、移動後に状態を巻き戻す操作を経て、残りのプロセスを匿名MAPFとして解く。
ベンチマーク実験において、PPPは74%から89%のインスタンスを解決し、BAと比較してmakespanおよびflowtimeを大幅に改善した。最適解ソルバーとの比較では、PPPは最適解とのmakespanの差を0.55から2.73ステップ以内に抑えつつ、非常に短い実行時間で動作した。エージェントの優先順位付けの評価では、最大衝突優先（MC）のヒューリスティックが、高密度なマップにおいて低い実行時間と高い成功率を示した。
PPPは完全性を欠いており、ピボット数が極端に少なくタスク割り当て率が高いボトルネック状況では、第一段階でのフロー飽和により失敗する可能性がある。また、エージェント密度が50%を超え、かつ全エージェントがタスクを持つような高密度環境では、SATベースの最適ソルバーの実行時間が急増する。今後の課題として、ピボットに基づく目的関数の検討や、特定のドメインに特化したソルバーの開発、最新のMAPF技術の適応が挙げられる。
本論文では、タスクを割り当てられたエージェントの一部が、交換可能な複数のピボット（ワークステーションなど）のいずれかを訪問した後、最終的に各エージェントが1つずつ匿名的なステーションに停止するという、Pivot-and-Station Multi-Agent Path Finding (PS-MAPF) という新しいMAPFの変種を提案している。グラフの構造に関する解の存在条件を特定しており、2-辺連結グラフであれば常に解が存在すること、および任意の連結グラフにおいては、空き頂点の数に対する構造的な有効距離の指標が解の必要十分条件であることを示している。ステーションにおける完了時刻の最大値であるmakespanや、完了時刻の総和であるflowtimeを最小化する問題は、ピボットが1つのみの場合であってもNP困難であることが証明されている。提案手法として、完全性を保証するベースライン、SATを用いた最適解ソルバー、およびPivot-Prioritized Planning (PPP) という3つのアルゴリズムを提示している。PPPはベンチマークにおいて74%から89%のインスタンスを解決し、ベースラインと比較してmakespanおよびflowtimeを大幅に改善する性能を示している。
本論文では、高密度な自動倉庫システムをモデル化した、Pivot-and-Station Multi-Agent Path Finding (PS-MAPF) という新しいMAPFの変種を提案している。この問題は、グラフ上のエージェントのうち、タスクを持つ一部のエージェントが、最終的な終端位置であるステーションに到達する前に、機能的に交換可能な中間リソースであるピボットを少なくとも1つ訪問しなければならないという制約を持つ。タスクを持たないエージェントも空間を占有して他のエージェントと干渉するため、全エージェントがそれぞれ異なるステーションに収まる必要がある。既存のTAPFやMCPFといった手法と比較して、PS-MAPFは「タスクを持つエージェントが必ずいずれかのピボットを訪問する」という制約と、「全エージェントの終端位置を匿名的に割り当てる」という性質を組み合わせている点が特徴である。研究の貢献として、2-edge connectivityを用いた解の存在判定が多項式時間で可能であることや、単一のピボットであってもmakespanやflowtimeの最小化がNP-hardになるという複雑性の閾値を明らかにしている。アルゴリズム面では、SATへの帰着に基づく最適解ソルバーと、ピボットへの経路計画を優先し、ステーションへの割り当てをフローベースで行う高速なPivot-Prioritized Planning (PPP) を提案しており、PPPはベンチマークにおいてベースラインよりも数桁低いコストで74%から89%のインスタンスを解決している。
本研究では、連結かつ無向のグラフ上で、ピボット（中継点）、ステーション（目的地）、および複数のエージェントが移動するPivot-and-Station Multi-Agent Path Finding (PS-MAPF) という問題を定義している。エージェントは、目的地に到達する前にいずれかのピボットを経由しなければならないタスク付きエージェントと、直接目的地へ向かえるタスクなしエージェントに分類される。解となる経路集合は、エージェント同士が同じ時刻に同じ頂点を占有する頂点衝突や、同じエッジを逆方向に通過するスワップ衝突が発生しない、衝突のない経路の集合として定義される。タスク付きエージェントの成功条件は、ある時刻にピボットに到達し、その後、ある時刻にステーションに到達してそこから離れないことである。評価指標として、全エージェントがステーションに到着するまでの最大時刻を表すStation-Makespanと、全エージェントのステーション到着時刻の総和を表すStation-Flowtimeの2つのコスト関数が用いられる。
Pivot-and-Station Multi-Agent Path Finding (PS-MAPF) における解の存在条件を、グラフの構造とエージェント数に基づき分析しています。ピボット（特定の訪問必須地点）を必要としない状態では、グラフが連結であれば常に解が存在しますが、ピボットの制約がある場合、例えばパスグラフにおいてピボットが端点に位置し、エージェントの相対的な順序を入れ替えられない状況では解が存在しません。グリッドや倉庫のような2-辺連結グラフにおいては、各タスクエージェントの始点とピボットが2-辺連結であれば、エージェント数に関わらず常に解が存在します。これは、2-辺連結性を利用してエージェントを回転移動させることで、空きスペースを制御しながら目的の移動を実現できるためです。一般的な連結グラフにおいては、グラフを2-辺連結成分に分解し、それらを橋で結んだ2-辺凝縮木を用いて解の存在を判定できます。具体的には、空きスペースがピボット付近に集約された状態において、エージェントの始点からピボットまでの凝縮木上の経路における「有効距離」が、空きスペースの数 k 以下である場合に解が存在するという必要十分条件が導出されています。
本セクションでは、最小ステーション・メイクスパン（MSM）および最小ステーション・フロータイム（MSF）の決定問題がNP困難であることを証明している。3SAT問題からの帰着により、変数エージェントと節エージェントを含むグラフ構造を構築し、ピボットを戦略的に配置することで、各エージェントが特定のステーションへ向かうよう強制する手法を用いている。MSMについては、3SATの充足解が存在する場合、すべてのエージェントが待機なしで最短経路を通り、指定されたメイクスパン内でタスクを完了できることを示している。MSFについては、解が交差しない条件と、エージェントがピボットを通過する際の順序関係を解析することで、MSFの最適化が3SATの充足可能性と等価であることを導いている。これらの結果は、ピボットが存在しない場合の匿名MAPFは多項式時間で解けるのに対し、たとえ1つのピボット訪問が要求されるだけでも、問題の複雑さが劇的に増大することを明らかにしている。
本セクションでは、Pivot-and-Station MAPF問題を解くための3つのアルゴリズム、Baseline Algorithm (BA)、Pivot-Prioritized Planning (PPP)、およびSATベースの最適ソルバーについて述べている。
BAは、解の存在に関する構成的な分析に基づいた完全なアルゴリズムであり、解が存在するすべてのインスタンスに対して解を導出できるが、解の品質は非常に低い。この手法は、まず各タスクエージェントを順番にピボットへ移動させるフェーズ1を行い、エージェントの移動後にシステムの状態を初期状態へと完全に巻き戻すために移動経路を逆方向に辿ることで、後続のエージェントが干渉を受けないように設計されている。その後、フェーズ2として、ピボット条件が満たされた状態での匿名MAPF問題として全エージェントを目的地へ移動させる。BAの計算量は、グラフの2辺連結縮約木の構築や、空きスペース（hole）を移動させる操作を含め、最悪計算量で O(n^4) となり、インスタンスサイズに対して多項式時間で動作する。
PPPは、BAよりも高い解の品質と高速な実行を目指した多項式時間アルゴリズムであるが、完全性は失われており、解が存在するインスタンスでも失敗する場合がある。フェーズ1では、優先順位に基づきSpace-Time A*を用いてタスクエージェントをピボットへ経路計画し、その経路を予約することで衝突を防ぐ。フェーズ2では、フェーズ1で予約されたノードやエッジを除外した時間拡張グラフ上で最大流問題を解くことで、全エージェントを目的地へ移動させる。PPPの最悪計算量は O(n^5) であり、これも多項式時間である。
最後に、SATベースの最適ソルバーは、高密度な環境において優れた性能を示すことが知られている従来のMAPFの還元手法を、本問題の制約に合わせて適用したものである。
本実験では、SATベースの最適解ソルバー、提案手法であるPPP、およびベースラインのBAを用いて、様々なパラメータ条件下での性能評価を行っています。最適解ソルバーを用いた解析により、エージェント密度が50%かつ全エージェントがタスクを持つ場合に実行時間が急増することや、ステーション密度が高まるほど問題の難易度が下がり、平均的なメイクスパンが線形に減少することが確認されました。PPPは、BAが制限時間内に解を見つけられない条件下でも、非常に短い実行時間で、最適解とのメイクスパンの差を0.55から2.73ステップ以内に抑えつつ高い成功率を維持しています。エージェントの優先順位付けに関する評価では、最短経路優先、最長経路優先、ランダム、最小衝突優先、最大衝突優先の各ヒューリスティックを比較した結果、最大衝突優先（MC）が全体として最も強力であり、特に高密度なマップで低い実行時間と高い成功率を示しました。PPPの失敗は、ピボット数が極端に少なくタスク割り当て率が非常に高いボトルネック状況に集中しており、これはフェーズ1におけるフローの飽和が原因で、フェーズ2において許容されるホライゾン内に全エージェントをルーティングできなくなるためです。
本研究では、各エージェントが最終目的地である匿名的なステーションに到達する前に、まず匿名的なピボットを経由しなければならないという、MAPFの新しい変種であるPS-MAPFを提案した。この問題において、ステーションへの到達における最大完了時間や、全エージェントのステーション到達時間の総和を最小化する問題は、ピボットが一つのみの場合でもNP困難であることを証明し、解の可否に関する完全な特性を明らかにした。提案手法として、解の完全性は保証するが品質は低いベースライン、SATソルバーを用いて最大完了時間を最適化する手法、および不完全ながらもベースラインより大幅に優れた解を高速に出力するPivot-Prioritized Planning（PPP）の3つのアルゴリズムを提示した。今後の展望として、ピボットに基づく新たな目的関数の検討や、特定のドメインに特化したソルバーの開発、および最新のMAPF技術をPS-MAPFへ適応させる研究が挙げられる。