匿名マルチエージェント経路探索（AMAPF）は、無向グラフ上で複数のエージェントを衝突を回避しながら、任意の目標地点へ一対一で割り当てる問題である。エージェントが目標到達後にグラフから消滅する設定では、総コスト（各エージェントの完了時刻の総和）の最小化はネットワークフローを用いて多項式時間で解ける。しかし、標準的な設定である「目標に留まり続ける（ゴール滞在）」条件では、目標への到達がその後の全エージェントの動きと結合するため、計算の困難さが変化する。
エージェントの挙動の違いが、問題の計算複雑性の境界を決定づけることを明らかにした。目標滞在を伴うAMAPFにおける総コスト最小化がNP困難であることを、3-SAT問題からの帰着を用いて証明した。また、目標への永続的な占有制約を導入した整数計画問題の線形計画緩和が、整数解を持たないこと、および整数性のギャップが2に達する場合があることを示した。
目標地点への滞在をモデル化するため、特定の時刻以降に目標地点が最終的な占有者によって永続的に占有されることを示す定着変数を導入した整数計画式を定式化した。NP困難性の証明には、3-SAT問題からの帰着を用いている。具体的には、各変数に対して2つのリテラルゲートと共有ボトルネック、セレクターエージェントを含む変数ガジェットを構成し、各節に対して節エージェントを含む節ガジェットを導入した。各エージェントが目標に到達するまでの各ステップでポテンシャル関数が1ずつ増加する場合にのみ、コストの総和が理論的な下限値に達するという性質を利用している。
6つの頂点を持つ木構造のグラフを用いた検証により、整数計画問題の性質を評価した。この検証において、整数解による最小の総コストが10であるのに対し、線形計画緩和ではフローを分数的に分割して目標に定着させることで、総コストを7.5まで下げられることが示された。これにより、目標への定着条件が単一商品フローの整数性を破壊することを数値的に示した。
本研究の困難さの根源は、目的地での永続的な占有制約が、時間拡張フロー定式化における整数性を破壊することにある。今後の課題として、変数の出現回数が制限されたSATを用いることで、節やセレクターの経路長を定数に抑え、平面グラフや2Dグリッド上での困難性を証明すること、あるいはMax-SATを用いた近似困難性の証明へと拡張することが挙げられる。
エージェントがゴールに到達した後に消滅する設定の匿名マルチエージェント経路探索（AMAPF）では、総コストの最小化がネットワークフローを用いて多項式時間で解ける。これに対し、エージェントがゴールに留まり続ける標準的な設定では、問題の性質が根本的に異なることを示している。著者らは、標準的な時間拡張フローモデルにゴールへの定着制約を加えることで総コスト最小化問題を定式化し、その線形計画緩和が整数解にならないことを明らかにした。さらに、3-SAT問題からの帰着を用いることで、ゴールに留まる設定のAMAPFにおける総コスト最小化がNP困難であることを証明している。この結果は、完了したエージェントがゴールに留まるか否かという条件が、問題の計算複雑性の境界を決定づけることを示している。
マルチエージェント経路計画（MAPF）において、エージェントがどの目標地点に到達してもよいとする匿名MAPF（AMAPF）は、各エージェントの目標が固定されている標準的なMAPFよりも計算複雑性が低い。AMAPFにおいて、最大完了時間の最小化や、エージェントが目標到達後にグラフから消滅する設定での総コスト（SoC）の最小化は、時間拡張ネットワークを用いた最大流問題として多項式時間で解くことが可能である。しかし、エージェントが目標地点に留まり続ける「目標滞在」の設定では、目標への到達がその後の全エージェントの動きと結合するため、既存の最適化手法は指数関数的な計算時間を要する。本論文は、目標滞在を伴うAMAPFにおけるSoCの最小化がNP困難であることを証明し、目標到達後のエージェントの挙動の違いが複雑性の境界を決定づけることを明らかにした。具体的には、目標地点の恒久的な占有を明示的にモデル化した整数計画式を定式化し、その自然な線形計画緩和が整数解を持たないこと、および特定の事例において整数性のギャップが 2 に達することを指摘している。
マルチエージェント経路計画（MAPF）において、エージェントが区別できない匿名（Anonymous）な設定では、エージェントが目的地に到着した後に消滅する場合の総コスト（SoC）最小化は、最小費用最大流問題を用いることで多項式時間で解けます。しかし、エージェントが目的地に留まり続けるゴール滞在型の匿名MAPFにおけるSoC最小化は、既存の最適アルゴリズムの最悪計算量が指数時間となっていました。本研究は、ゴール滞在型の匿名MAPFにおけるSoC最小化がNP困難であることを証明することで、この計算量のギャップを埋めています。エージェントの入れ替え可能性の観点では、チーム数が1つの完全な匿名設定から2つのチームへと増えるだけで、最長完了時間（Makespan）やSoCの最適化はNP困難になります。このように、本研究は完全な匿名性を持つ設定内において、エージェントが目的地に到着した後の挙動が、多項式時間で解けるかNP困難かを分ける境界となることを明らかにしています。
匿名マルチエージェント経路探索（AMAPF）は、無向グラフにおいて、開始地点の集合と目標地点の集合が与えられた際、各エージェントを目標地点へ一対一で割り当て、衝突を回避しながら移動させる問題である。エージェントは各ステップで隣接する頂点へ移動するか、あるいはその場に留まることができ、衝突とは、同じ時刻に複数のエージェントが同一の頂点を占有すること、または同じ時刻にエージェント同士が逆方向に同じエッジを通過することを指す。解の条件として、各エージェントは割り当てられた目標地点に最終的に到達し、その後は永続的にその地点に留まり続けなければならない。なお、開始地点が目標地点と一致しているエージェントであっても、その地点に割り当てられるとは限らず、一度離脱することも許容される。本研究が扱うAMAPF-SoC問題は、各エージェントが割り当てられた目標地点に到達するまでの時刻の総和、すなわち合計コストを最小化する解を求めるものである。
目標地点への滞在を伴う匿名マルチエージェント経路探索（AMAPF）において、コストの総和（SoC）を最小化する問題の定式化と、その線形計画緩和における整数性の喪失について述べている。エージェントが目標到達後に消滅するモデルでは最小費用最大流問題として定式化できるが、目標への滞在を考慮する場合、ある目標地点が特定の時刻以降、最終的な占有者によって永続的に占有されることを示す定着変数を導入する必要がある。この定着条件を組み込んだ整数計画問題（IP-SoC）は、各エージェントの完了時刻の総和を最小化する。しかし、この定着条件の導入により、単一商品フローが持つ整数性、すなわち線形計画緩和の解が整数解となる性質が失われる。具体例として、6つの頂点を持つ木構造のグラフを用いた検証では、整数解の最小SoCが10であるのに対し、線形計画緩和ではフローを分数的に分割して目標に定着させることでSoCを7.5まで下げることができ、整数性のギャップが生じることが示されている。この結果は、目標への永続的な占有が、標準的なネットワークフローの枠組みを超えた組合せ論的な選択を導入していることを示唆している。
本セクションでは、コストの総和を最小化するマルチエージェント経路探索（AMAPF-SoC）がNP困難であることを、3-SAT問題への帰着を用いて証明している。まず、各エージェントが目標に到達するまでの各ステップにおいて、ポテンシャル関数（各ノードに割り当てられた値）が正確に1ずつ増加する場合にのみ、コストの総和が理論的な下限値に達するという性質を定義している。変数ガジェットでは、各変数に対して2つのリテラルゲート、共有のボトルネック、およびセレクターエージェントを導入しており、コストの下限を達成するためには、2つのリテラルゲートのうち一方のみが空席になり、セレクターがその空いたゲートへ移動しなければならないという制約を課している。節ガジェットでは、各節に対して節エージェントを導入し、その節に含まれる真のリテラルに対応するゲートを経由して、ポテンシャルが2の目標へ到達する経路を構成している。この構成により、元の3-SAT式が充足可能であることと、構築されたAMAPFインスタンスにおいてコストの総和が特定の閾値以下となることが同値であることが示されている。したがって、最小のコストの総和を求める問題はNP困難であると結論付けている。
本研究は、エージェントが目的地に到着した後に留まり続ける制約を持つ、標準的なゴール滞在型Sum-of-Costs（SoC）マルチエージェント経路計画問題（AMAPF）がNP困難であることを証明し、多項式時間で解けるフローベースの変種との複雑性の差を明確にした。この困難さの根源は、目的地での永続的な占有制約が、時間拡張フロー定式化における整数性を破壊することにある。提案された帰着手法は、タイトなポテンシャル下界、二者択一を強制する共有ボトルネック、および節エージェントに選択を伝える永続的なリテラルゴールという要素で構成されており、変数の出現回数に制限がないSATにも適用可能な柔軟性を持つ。変数の出現回数が制限されたSATを用いることで、節やセレクターの経路長を定数に抑えられる可能性があり、これにより平面グラフや2Dグリッド上での困難性、あるいはMax-SATを用いた近似困難性の証明へと拡張できる可能性がある。