従来のMAPFはエージェントを点として扱い、同一頂点の占有や同一エッジの同時使用のみを衝突として扱う。しかし、実世界のロボティクスではエージェントの大きさを考慮しなければ安全な実行ができない。本研究の対象は、ユークリッド平面上に埋め込まれた無向グラフ上で、半径 r を持つ円盤としてモデル化されたエージェント群の経路計画問題である。入力はグラフ、エージェントの初期配置、目標配置、および半径であり、出力は衝突を回避して目標配置へ到達する遷移の列である。衝突には、エージェントの体が重なる頂点衝突に加え、移動中のエージェントの体が、同じエッジを使用していない静止中のエージェントの体と重なるエッジ衝突が含まれる。
エージェントに幾何学的な形状を持たない従来のMAPFは、無向グラフにおける決定問題が多項式時間で解けることが知られている。これに対し、エージェントのサイズを考慮するLA-MAPFが、従来のMAPFと同様に多項式時間で解けるのか、あるいは計算困難なのかという未解決の問いに対し、NP困難であることを理論的に示した。
NP完全問題である3SAT問題からLA-MAPF問題への多項式時間還元を用いて、問題の困難性を証明する。構成は、変数、節、およびブロッキングの3つのガジェット（部分グラフ）から成る。変数ガジェットは各変数に対応するエージェントを配置し、その位置で真偽を表現する。節ガジェットは各節に対応するエージェントを配置し、節内のリテラルが真である場合にのみ目的地へ到達できる衝突条件を設計する。ブロッキングガジェットは、特定の役割を持つエージェントを用いて変数の値を固定する。各ガジェット内の頂点間距離をエージェントの半径未満に設定することで、エージェントの存在が互いの移動を制限する仕組みを構築している。
3SATの充足可能性と、構築されたLA-MAPFの解の存在が同値であることを論理的に証明した。3SATの解が存在する場合、変数エージェントを真偽に対応する頂点へ移動させ、ブロッキングエージェントで領域を確保した後、節エージェントがリテラルに対応する頂点を通って目的地へ到達できる経路が存在することを示した。逆に、LA-MAPFの解が存在する場合、最終的な占有状況を逆方向に辿ることで、全ての節を充足する3SATの解を導出できることを示した。この還元において、グラフの頂点数やエージェント数は元の3SATの変数および節の数に対して多項式となる。
本研究は、一度に一つのエージェントのみが移動する設定を前提としている。複数のエージェントが互いの占有位置を順次入れ替える「閉じた鎖」のような、単一の移動の連続に分解できない同時移動を許容する設定については、本帰着は成立しないため、その複雑性は今後の課題である。また、LA-MAPFがNPに属するかどうか、すなわち多項式時間の長さの解が常に存在するかどうかの解明も必要である。今後は、平面グラフやグリッドグラフといった特定のグラフ構造への限定による問題の簡略化や、同時移動を許容する設定への拡張が研究の方向性として挙げられる。
従来のMAPF（Multi-Agent Path Finding）は、エージェントのサイズを無視し、同一頂点の占有や同一エッジの同時使用のみを衝突として扱うが、実世界のロボティクス等の応用ではエージェントの大きさを考慮することが不可欠である。エージェントが大きくなると、あるエージェントがエッジを移動する際に、その身体の一部が同じエッジを使用していない別のエージェント（静止しているエージェントなど）と重なるという、新たな種類の衝突が発生する。本論文は、このような大きなエージェントを考慮したMAPFがNP困難であることを初めて証明した。この証明は、NP完全問題である3SAT問題から、特定のグラフ、開始頂点、および目標頂点を持つMAPFのインスタンスを構成する帰着手法に基づいている。具体的には、任意の3SATの論理式が充足可能であることと、対応するMAPFの経路計画問題に解が存在することが同値であることを示している。
マルチエージェント経路探索（MAPF）は、グラフ上の各エージェントに対して、衝突を避けながら始点から終点へ移動する経路を求める問題である。従来のMAPFではエージェントを点として扱い、同じ時刻に同じ頂点やエッジを使用することを衝突と定義するが、実世界の制約を十分に反映できていない。これに対し、エージェントが物理的な体積を持ち、頂点での占有やエッジ移動時の空間の掃引を考慮するMAPF for Large Agents（LA-MAPF）という、より現実的な定式化が提案されている。LA-MAPFでは、エージェントの体積によって、従来のMAPFでは衝突が発生しない経路であっても衝突が生じる場合がある。本研究では、無向グラフにおけるMAPFの決定問題が多項式時間で解けることが知られている一方で、LA-MAPFの決定問題（解が存在するか否かの判定）はNP困難であることを証明した。
本研究に関連する先行研究は、エージェントに形状やサイズを持たせる拡張手法と、計算複雑性の解析という2つの観点に大別される。点エージェントを対象とした従来のMAPFでは、Push and Rotateのような多項式時間で動作するアルゴリズムが存在するが、これを大型エージェント（LA-MAPF）へ適応させた手法は、多項式時間で動作するものの、解が存在する場合でも解を見つけられない不完全なものである。一方、Conflict-Based Search（CBS）をLA-MAPFへ適応させた研究では、制約の追加による枝刈りの強化や、問題をより少ないエージェント数を持つ小さな部分問題へ分解する手法が提案されているが、これらは依然として指数関数的な計算時間を要する。既存の複雑性解析に関する研究は、エッジの方向性やグラフの構造、決定問題か最適化問題かといった条件下でPやNPの判定結果を示しているが、いずれもエージェントに幾何学的な形状を持たないことを前提としている。したがって、LA-MAPFが従来のMAPFと同様に多項式時間で解けるのか、あるいは計算困難なのかという問いは未解決のままである。
本研究では、ユークリッド平面上に埋め込まれた無向グラフ上で、半径 r を持つ円盤としてモデル化されたエージェント群の経路計画問題を定義している。エージェントの配置は離散的な時刻におけるグラフの頂点の集合として表され、ある時刻から次の時刻への遷移は、一つのエージェントがエッジに沿って移動し、他のすべてのエージェントがその場に留まる場合にのみ許容される。衝突の定義として、二つのエージェントが同じ頂点を占有する頂点衝突と、移動中のエージェントの円盤が、特定の頂点に留まっているエージェントの円盤と重なるエッジ衝突の二種類を考慮する。エッジ衝突は、移動中のエージェントの中心点と、留まっているエージェントの頂点と次の頂点を結ぶ線分との距離が、エージェントの半径 r 未満になる場合に発生する。LA-MAPF問題の目的は、初期配置から目標配置まで、これらの衝突を一切回避しながら遷移の列を見つけることであり、遷移回数などのコスト最小化ではなく、解を見つけること自体を対象としている。
本セクションでは、巨大なエージェントのマルチエージェント経路探索（LA-MAPF）がNP困難であることを示すため、3-SAT問題をLA-MAPF問題へ帰着させる手法を述べている。この帰着では、グラフのサイズとエージェント数が元の3-SATの変数および節の数に対して多項式となるように構成され、エージェントの半径は節の数に設定される。構成は3つのガジェット（部分グラフ）から成り、変数ガジェットは各変数に対応するエージェント（v-agent）を配置し、その位置によって変数の真偽を表現する。節ガジェットは各節に対応するエージェント（c-agent）を配置し、節内のリテラルが真である場合にのみ、c-agentが目的地へ到達できるような衝突条件を設計している。ブロッキングガジェットは、b-agentを用いてv-agentの移動を制限し、変数の値を固定する役割を担う。各ガジェット内の特定の頂点間の距離をエージェントの半径未満に設定することで、エージェントが同時に存在すると衝突が発生するように設計されており、これにより3-SATの充足可能性とLA-MAPFの解の存在が等価になる。
本セクションでは、3-SAT問題と構築されたLA-MAPF問題の間の等価性を証明している。3-SATの解からLA-MAPFの解を構成する手法では、まず変数エージェントを真偽に対応する頂点へ移動させ、次にバッファエージェントを移動させて特定の領域を空けた後、節エージェントが各節を充足するリテラルに対応する頂点を通るように移動させる。その後、節エージェントを目的地へ移動させ、最後に最初に行った変数エージェントとバッファエージェントの移動を逆順に実行することで、全エージェントが衝突することなく目的地へ到達できることが示されている。逆に、LA-MAPFの解から3-SATの解を構成する手法では、全エージェントが目的地にいる最終状態から、特定の頂点が占有されるまでエージェントの動きを逆方向に辿る。このとき、特定の頂点の占有状況に基づいて変数の真偽を決定することで、全ての節が充足されるような3-SATの解が得られることが証明されている。
本セクションでは、エージェントのサイズが大きいマルチエージェント経路探索（LA-MAPF）問題がNP困難であることを証明している。具体的には、NP完全問題である3-SAT問題からLA-MAPF問題への多項式時間還元を用いることで、元の3-SAT式に解が存在する場合に限り、構築されたLA-MAPF問題も解が存在するように構成されている。この還元によって生成されるグラフの頂点数やエージェントの数は、元の3-SAT式のサイズに対して多項式的な大きさとなる。3-SATの解の存在とLA-MAPFの解の存在が同値であることが示されており、この還元を通じてLA-MAPF問題がNP困難であることが結論付けられている。
本研究では、エージェントをグラフ上のディスクとしてモデル化し、一度に一つのエージェントのみが移動する設定を前提としている。本論文で示したLA-MAPFの特定のバリアントがNP困難であることを示すことで、より一般的な定式化も同様にNP困難であると推論できる。また、複数のエージェントが同時に移動する同期的な設定についても、ある状態から次の状態への遷移が単一エージェントの移動の連続として分解可能である限り、本研究の帰着は有効である。しかし、複数のエージェントが互いの占有位置を順次入れ替える「閉じた鎖」のような移動は、単一の移動の連続に分解できないため、この帰着は成立しない。このような分解不可能な同時移動を許容する設定におけるLA-MAPFの計算複雑性を評価することが、今後の研究課題として挙げられる。
本研究では、エージェントのサイズを考慮するLA-MAPF問題の決定問題における計算複雑性を調査し、3-SAT問題からの帰着を用いることで、この問題がNP困難であることを示した。これにより、通常のMAPFとは異なり、LA-MAPFはP=NPでない限り多項式時間では解けないことが理論的に示された。問題が困難である主な要因は、MAPFグラフが埋め込まれている計量空間におけるエージェント間の近接性を考慮する必要がある点にある。今後の研究方向として、平面グラフやグリッドグラフのような特定のグラフ構造やレイアウトに限定することで、問題が簡略化される可能性がある。また、複数のエージェントが同時に移動できる設定への拡張や、LA-MAPFがNPに属するかどうか、すなわち任意のインスタンスに対して多項式時間の長さの解が存在するかどうかの解明も課題である。