従来のMAPFはエージェントを点として扱うが、LA-MAPFはエージェントを半径を持つ円盤としてモデル化し、ユークリッド空間における物理的な重なりに基づく衝突判定を行う。エージェントが辺を移動する際、その円盤が描く軌跡と他の静止エージェントとの衝突も考慮する必要がある。問題の目的は、初期状態から目標状態へ、衝突のない遷移の列が存在するかを判定することである。
LA-MAPFの計算複雑性の下界を、先行研究によるNP困難からPSPACE完全へと引き上げた。特に、グラフが平面グラフであり、かつエージェントの移動が水平・垂直方向に限定されるという厳格な幾何学的制約下においても、問題がPSPACE完全であることを示した。
Savitchの定理に基づき、現在の構成、次の構成、および無限ループを防ぐためのステップカウンタのみを保持する非決定性アルゴリズムを用いることで、LA-MAPFがPSPACEに属することを示した。次に、PSPACE困難性を証明するため、Restricted Sliding Tokens問題からLA-MAPFへの多項式時間還元を行った。直交グラフ描画アルゴリズムを用いて、元のグラフの構成要素を平面的な直交グリッドへ埋め込み、トークン三角形やトークンエッジに対応するガジェットを配置した。エージェントが互いに追い越せない狭い経路内で、一つの空きスペース（ホール）を移動させることで、トークンのスライド動作をシミュレートし、幾何学的な重なりを利用して制約を伝播させる仕組みを構築した。
本研究は理論的な複雑性解析である。入力のバイナリ符号化長をnとしたとき、頂点数、エージェント数、および各時刻の配置を記録するメモリ量がすべてnの多項式内に収まることを示すことで、PSPACEへの属することを証明した。また、Restricted Sliding Tokens問題の構成要素を、エージェントの配置と移動制約に変換する帰着の妥当性を論理的に証明している。
LA-MAPFがPSPACE完全であることは、この問題が極めて高い計算コストを持つことを示唆している。本研究は、幾何学的な制約がどのように論理的な制約へと変換されるかを、特定のポート間のみに移動を制限するガジェットを用いて示した。
本研究では、エージェントを円盤としてモデル化し、ユークリッド空間における物理的な重なりに基づいて衝突を判定する、幾何学的バリエーションであるLarge Agents Multi-Agent Path Finding (LA-MAPF) の計算複雑性を扱う。LA-MAPFの目的は、初期状態から目標状態へ、衝突のない遷移の列が存在するかどうかを判定することである。先行研究ではLA-MAPFがNP困難であることが示されていたが、本論文ではRestricted Sliding Tokens問題からの多項式時間還元を用いることで、LA-MAPFがPSPACE完全であることを証明し、その複雑性の下界を強化している。
従来のMAPFはエージェントを点として扱うが、LA-MAPFはエージェントを半径を持つ円盤としてモデル化し、エッジ移動時に円盤が掃引する連続的な領域による衝突を考慮する。この連続空間における衝突が幾何学的な困難さを生んでおり、先行研究では3-SATからの帰着によりNP困難であることが示されていたが、厳密な計算複雑性は未解明であった。本論文は、LA-MAPFがPSPACE完全であることを証明している。まず、指数関数的に巨大な状態空間における到達可能性判定が、Savitchの定理を用いることで多項式メモリで決定可能であることを示し、PSPACEに属することを証明した。次に、Sliding Tokensの制限されたバージョンからの多項式時間帰着を用いて、PSPACE困難性を証明している。この帰着では、直交グラフ描画アルゴリズムに基づき、エッジの交差がない直交グリッド上のワイヤと局所的な定数サイズのガジェットを用いることで、グラフの独立集合制約をシミュレートしている。これにより、グラフが平面グラフであり、かつエージェントの移動が水平・垂直方向に限定されている場合でも、問題がPSPACE完全であることが示されている。
本セクションでは、大規模エージェントのマルチエージェント経路探索（LA-MAPF）の定義と、計算複雑性の証明に用いる制限付きスライディングトークン問題について述べている。LA-MAPFは、平面上に埋め込まれたグラフ上で、共通の半径を持つ円盤状のエージェント群を、頂点および辺における衝突を避けながら開始配置から目標配置へ移動させる問題である。移動は、一度に一つのエージェントのみが辺に沿って動き、他のエージェントは現在の頂点に静止している形式を想定している。衝突回避の条件として、すべてのエージェントの円盤が重ならないこと、および移動中のエージェントの軌跡と静止しているエージェントとの距離が、半径の2倍以上であることを求めている。一方、還元元となる制限付きスライディングトークン問題は、グラフの頂点集合が3頂点の完全グラフである三角形と、2頂点の完全グラフである辺に分割され、それらがリンクエッジで接続された構造を持つ。この問題は、トークンが配置された頂点集合が常に独立集合、すなわち隣接する頂点に同時にトークンが存在しない状態を維持するように、一つのトークンを隣接する頂点へスライドさせて目標配置へ到達できるかを判定するものである。この制限付き設定では、各三角形および各辺に必ず一つのトークンが存在する標準的な配置が維持され、リンクエッジは二つの端点に同時にトークンを置けないという排他的制約として機能する。
LA-MAPFがPSPACEに属することを示すため、非決定性アルゴリズムを用いて多項式領域で解けることを証明している。入力のバイナリ符号化長をnとすると、頂点数およびエージェント数はnの多項式で抑えられ、各時刻におけるエージェントの配置を記録するのに必要なビット数も多項式となる。アルゴリズムは、現在の構成と次に推測される有効な構成、および無限ループを防ぐためのステップカウンタのみを保持する。ステップカウンタは、構成の総数を超えるステップに達した場合に探索を打ち切るために用いられ、その格納に必要なビット数も多項式に収まる。幾何学的な衝突検証に必要なメモリを含めても、保持する情報はすべて入力サイズnの多項式内に収まるため、Savitchの定理に基づき、LA-MAPFはPSPACEに属する。
本セクションでは、Restricted Sliding Tokens問題からの帰着により、大きなエージェントを用いたマルチエージェント経路探索（LA-MAPF）がPSPACE困難であることを証明している。まず、元のグラフの構成要素であるトークン三角形とトークンエッジを成分とし、それらを頂点とするマクログラフを構築した上で、直交グラフ描画アルゴリズムを用いて平面的な直交グリッドへの埋め込みを行う。トークン三角形には1つのv-agentを割り当て、4つのポート頂点からなる長方形構造を配置することで、エージェントの移動を特定のポート間のみに制限し、他のエージェントとの幾何学的な衝突を利用して移動を制御する。トークンエッジおよびリンクエッジには、経路上の頂点数より1つ少ない数のv-agentを配置することで、常に1つの空きスペース（ホール）が存在する状態を作り出す。エージェントが互いに追い越せない狭い経路内でホールを移動させることで、トークンのスライド動作をシミュレートしており、リンクエッジにおいてはポート頂点にエージェントが存在する場合の幾何学的な重なりを利用して、反対側の端点におけるホールの位置を強制し、制約を伝播させる。開始状態と目標状態は、元のトークンの配置に基づいて各エージェントおよびホールの位置を決定することで定義され、エージェントの相対的な順序が固定される性質を利用して、トークンの移動とエージェントの配置を論理的に対応させている。
本研究は、大きなエージェントを扱うマルチエージェント経路探索（LA-MAPF）の計算複雑性が、PSPACE完全であることを明らかにした。具体的には、制限付きスライディングトークン問題からの幾何学的な還元を用いることで、LA-MAPFのPSPACE困難性を証明した。