複数のエージェントを衝突させずに目的地へ移動させるMAPFにおいて、木構造のような制限されたグラフトポロジーにおける計算複雑性の境界を対象とする。入力は木グラフ、各エージェントの開始地点および目標地点であり、出力は衝突のない経路計画である。一般グラフでは、メイクスパン、燃料消費量、コストの総和の各最適化がNP困難であることが知られているが、木構造において燃料消費量やコストの総和の最適化がどの程度の複雑さを持つかは未解明であった。
先行研究では木構造上でのメイクスパンの最小化がNP困難であることが示されていたが、本研究は燃料消費量およびコストの総和の最適化についてもそれぞれNP困難であることを新たに証明し、理論的な空白を埋めた。また、エージェントの移動を最短経路のみに制限した場合、燃料消費量の最適性を維持したまま多項式時間で解ける特殊なケースを特定した。
燃料消費量の最適化については、E3-SAT問題からの帰着を用いる。変数、節、リテラル、フィラーの4種類のエージェントと、変数の割り当てを制御するWings and Tailガジェット、および節の充足条件を検証するCoat Hangerガジェットを木構造内に構築する。コストの総和の最適化については、2P1N-SAT問題からの帰着を用い、移動と待機に等しくコストがかかる性質を利用した遅延ガジェットを導入する。このガジェットには、特定の時間枠内でのみ通過を許すウィンドウモードと、通過可能なエージェント数を制限するキャパシティモードがある。最短経路に限定した問題については、エージェント間の依存関係を示す待機グラフを構築し、その閉路の有無を判定する。
燃料消費量の最適化問題では、E3-SATの変数数をn、節の数をmとしたとき、燃料コストの閾値を 4n + 42m と設定することで、問題の充足可能性と等価であることを示した。コストの総和の最適化問題では、構築されるグラフの頂点数およびエージェント数が O(n^2 + nm + m^2) となり、多項式時間で構成可能であることを確認した。
木構造における最適化の困難さは、経路の選択肢の多さではなく、ボトルネックにおける衝突制約の解消に起因する。最短経路に限定した実行可能性判定は、CBSなどのソルバーにおいて、迂回なしでは解けない構成を迅速に排除する枝刈りヒューリスティックとして活用できる。今後の課題として、この判定手法を既存のソルバーへ統合することや、グラフの最大分岐度、直径、ボトルネックの数といったパラメータに基づくパラメータ化複雑性の解析が挙げられる。
マルチエージェント経路探索（MAPF）は、一般的なグラフ構造において様々な最適化指標に対してNP困難であることが知られているが、木構造のような制限されたトポロジーにおける計算複雑性の境界を明らかにすることは重要な理論的課題である。本研究では、木構造におけるMAPFの複雑性を調査した。先行研究では木構造上でのメイクスパン（全エージェントの完了時間）の最小化がNP困難であることが示されているが、他の標準的な指標については未解明であった。本論文では、木構造においても燃料消費量（全移動距離の総和）およびコストの総和の最適化がそれぞれNP困難であることを証明した。一方で、各エージェントの経路を個別の最短経路に限定し、待機アクションのみを追加することで実行可能な解が存在するかを判定する問題については、燃料消費量の最適性を維持したまま多項式時間で解けることを特定した。
マルチエージェント経路計画（MAPF）は、複数のエージェントを衝突させずに目的地へ移動させる問題であり、エージェント数の増加に伴い、全エージェントの完了時刻であるMakespan、全エージェントの移動コストの総和であるSum of Costs（SOC）、および待機を除いた総移動距離であるFuelの最適化は、一般グラフにおいてNP困難であることが知られています。木グラフはサイクルを持たず、任意の2頂点間に一意な経路が存在する構造ですが、狭い通路や高次数の分岐点といったボトルネックが存在するため、MAPFの複雑性を分析する上で重要な境界線となります。本研究では、木グラフにおけるMAPFの複雑性を解明することを目的とし、まずFuelの最小化が木グラフ上でNP困難であることを証明します。一方で、すべてのエージェントの移動を個別の最短経路のみに限定した場合、木グラフ上での衝突のないスケジュールの存在判定は多項式時間で決定可能であることを示し、Fuel最適化における扱いやすい部分集合を特定します。最後に、SOCの最小化についても木グラフ上でNP困難であることを証明し、これら主要な最適化指標に関する理論的な空白を埋めるものです。
本研究では、木構造のグラフにおけるマルチエージェント経路計画（MAPF）問題を扱う。MAPFは、k個のエージェントが、頂点と辺からなる無向グラフ上で、各々の開始地点から目標地点へ移動する計画を求める問題である。移動の際は、同一時刻に複数のエージェントが同じ頂点を占有する頂点衝突、およびエージェント同士が同じ辺を逆方向に渡るエッジ衝突の2種類の制約を回避しなければならない。グラフが木構造である場合、任意の2頂点間に唯一の単純パスが存在するため、サイクルを利用してエージェント同士が位置を入れ替えることができない。本研究では、最適化の指標として、全エージェントの目標到達時刻の総和であるSOC（Sum of Costs）と、待機動作を除いた全エージェントの総移動距離であるFuelの2つを対象とする。木構造におけるFuelの最適化は、エージェントを一度に1つずつ動かす逐次的なペブルモーション問題と等価になるが、その計算複雑性は未解明であった。本論文では、FuelおよびSOCの最適化を、与えられた整数境界以下で解が存在するかを判定する決定問題として定義し、その複雑性を分析する。
木構造における燃料（Fuel）コストの最適化問題（TMAPFf）がNP困難であることを、E3-SAT問題への帰着を通じて証明している。この帰着では、変数を表すブロックエージェント、節を表す節エージェント、節のリテラルを表す節リテラルエージェント、およびリテラルの物理的な対応物となるフィラーエージェントの4種類のエージェントを用いる。グラフ構造には、変数の割り当てを分岐として表現するWings and Tail (WaT) ガジェットと、節の充足条件を検証するためにエージェントの迂回を強制するCoat Hanger (CH) ガジェットが用いられる。燃料コストの閾値を 4n + 42m（nは変数、mは節の数）に設定することで、このコスト以下で解が存在することは、元のE3-SAT式が充足可能であることと等価になる。さらに、すべてのエージェントの経路をそれぞれの最短経路に厳密に制限する場合、木構造においては待機グラフ（wait-graph）に閉路が存在するかどうかを判定するだけで、多項式時間で解の存在を確認できることが示されている。
木構造におけるマルチエージェント経路探索（TMAPF）の最適化問題がNP困難であることを、2P1N-SAT問題からの帰着を用いて証明している。証明の核となるのは、移動と待機にそれぞれ1単位のコストがかかる性質を利用した遅延ガジェットの導入である。このガジェットは、特定の時間枠内でのみ外部エージェントの通過を許容するウィンドウモードと、通過可能なエージェントの総数を制限するキャパシティモードの2つの動作モードを持つ。これらを用いて、変数への割り当てをブロックエージェントの経路選択に、節の充足条件をリテラルエージェントが遅延なくガジェットを通過できるかどうかに対応させたグラフ構造を構築している。構築されるグラフの頂点数およびエージェント数は、元の問題の変数数nと節数mに対してO(n^2 + nm + m^2)となり、多項式時間で構成可能である。2P1N-SATが充足可能であれば、すべてのエージェントが遅延ペナルティを回避して目標に到達できる経路が存在し、総コストが特定の閾値以下になることが示されている。
本研究では、木構造グラフにおけるマルチエージェント経路探索（MAPF）において、燃料消費量とSOC（状態の充足度）を最適化する問題の計算複雑性を検討し、これらがNP困難であることを証明した。木構造はサイクルを持たない最も単純な連結グラフであるが、最適解の探索が困難な理由は、経路の選択肢の多さではなく、衝突制約の厳しさやボトルネックの解消にあることが示された。一方で、すべてのエージェントが最短経路のみを使用する場合に衝突のないスケジュールが存在するかを判定する問題は、多項式時間で解ける実行可能問題として特定された。この性質をCBSなどの状態空間探索ソルバーに組み込むことで、迂回なしでは解けない構成を迅速に排除し、待機アクションによって生成される膨大な探索空間を回避できる可能性がある。今後の展望として、この実行可能性判定を枝刈りヒューリスティックとして活用する手法や、分岐度やグラフの直径といった木構造のパラメータに基づくパラメータ化複雑性の解析が挙げられる。