標準的なMAPFは、離散的なグラフ $G=(V, E)$ 上で、エージェントの集合 $\mathcal{A}$ が各エージェント $a \in \mathcal{A}$ の開始地点 $v_{a,s}$ から目標地点 $v_{a,g}$ への衝突のないパス $\Pi$ を見つける問題である。しかし、実世界の応用では、連続空間での移動、タスク割り当てとの結合、環境やエージェントの不確実性、非ホロノミックな制約など、標準的な仮定を緩和した複雑な問題が数多く存在する。既存のサーベイは特定の応用や手法に偏っており、Combinatorial MAPFやMAPDといった重要なバリエーションが欠落しているという課題がある。
既存のサーベイが主に古典的なMAPFに焦点を当てているのに対し、本研究は近年派生した広範な問題群を網羅的に収集・分類している点が新規である。MAPFの前提条件を「目標」「エージェント」「環境」「通信」「時間」の5つの主要カテゴリに分類し、それらを変更することで生じる派生問題を体系化した。また、単なる問題の列挙に留まらず、各問題の定義的特徴、解決手法の概要、および問題間の類似性と相違性をマッピングすることで、研究者が適切なベースライン手法や関連問題を見つけやすくするためのカタログを提供している。
MAPFの派生問題を分類するために、5つの基本仮定（問題情報の事前既知性、実行の確実性、環境の離散性・均質性、エージェントのモデル、時間）に基づいたフレームワークを用いている。目標ベースのバリエーションについては、タスク割り当て（TA）の有無、マルチゴール（MG）特性、サブゴール（SG）の数、目的地（Destination）の定義、目標への制約（Goal constraints）といった軸で整理している。解決手法は、決定問題への帰着を用いるreduction-based approach、Conflict-Based Search (CBS) を中心としたsearch-based approach、メタヒューリスティクスを用いたLarge Neighborhood Search、および学習ベースの手法に大別して整理している。
本論文は特定の実験結果を報告するものではなく、既存のMAPF研究における多様な問題設定と解決手法のカタログ化を行っている。目標ベースの具体的な問題として、グローバルな期限 $T_{dl}$ を扱うMAPF-DL、個別の期限と遅延の最小化を扱うMAPF-DT、複数のサブゴールを訪問するMG-MAPF、および匿名的な目標割り当てを行うAMAPFなどが挙げられている。これらの問題に対し、ネットワークフロー、整数線形計画法、SMT、CBSの修正版といった既存の解決手法の適用可能性が整理されている。
MAPFの解決手法には、解の質とスケーラビリティの間にトレードオフが存在する。例えば、reduction-based approachは強力なソルバーを利用できるが、マップサイズが大きくなるとスケーラビリティが低下する傾向がある。また、CBSのような最適アルゴリズムは、衝突数が増加するとツリーの分岐が爆発的に増えるという課題がある。これに対し、PIBTや学習ベースの手法は高いスケーラビリティを実現する一方で、解のコストが増大する傾向がある。今後の課題として、複雑な制約や不確実性を伴う実世界の動的な環境への適応が挙げられる。
本論文は、マルチエージェント経路探索（MAPF）から派生した多様な問題設定、すなわち「MAPF flavors」を体系的に整理したサーベイである。標準的なMAPFは、離散的な環境、完全な同期、エージェントの均質性、および環境と全エージェントの位置が完全に既知であることを前提としているが、実世界の応用では連続空間での移動やタスク割り当てとの結合（TAPF）など、これらの仮定を緩和した問題が数多く存在する。著者らは、既存のMAPF研究を網羅するために48種類の派生問題を収集し、それらを定義する主要な特徴に基づいて分類し、問題間の関係性をマッピングした。本サーベイの目的は、新しい研究者や既存手法の限界を探る研究者に対し、関連する問題の特定、最新の解決手法の俯瞰、および使用されるデータセットへのアクセスを容易にすることにある。既存のサーベイが主に古典的なMAPFに焦点を当てているのに対し、本研究は近年派生した広範な問題群を対象としている点が特徴である。
既存のMAPFに関するサーベイは、特定の応用分野や解決手法に焦点を当てたものが多く、Combinatorial MAPFやMulti-Agent Pickup and Delivery (MAPD) といった重要なバリエーションが欠落している、あるいはOnline MAPFなどの定義が不十分であるといった課題がある。本論文は、MAPFの多様なバリエーション（flavors）を網羅的に収集・分類し、それらの定義的特徴、解決手法の概要、および問題間の類似性と相違性をマッピングすることを目的としている。MAPFはグラフ $G=(V, E)$ とエージェントの集合 $\mathcal{A}$ によって定義され、各エージェント $a \in \mathcal{A}$ は開始地点 $v_{a,s} \in V$ から目標地点 $v_{a,g} \in V$ への移動を、離散的なタイムステップ $t \in \{0, 1, \dots, \infty\}$ にわたって行う。エージェントの行動 $\alpha_a = (v, v')$ は、隣接する頂点への移動または待機を表し、一連の行動の順序 $\pi(a) = (\alpha_{a,1}, \alpha_{a,2}, \dots, \alpha_{a,n})$ がパスとなる。本研究の目的は、衝突のないパスの集合 $\Pi = (\pi(a_1), \pi(a_2), \dots, \pi(a_m))$ を見つける問題において、頂点衝突、エッジ衝突、スワップ衝突、フォロー衝突、およびサイクル衝突といった異なる衝突形態を整理し、研究者が適切なベースライン手法を見つけやすくするためのカタログを提供することである。
MAPFにおける衝突の定義は、一般的に頂点衝突とスワップ衝突の回避に焦点を当てているが、実行の不完全性を考慮する場合、同期を前提とするフォローイング衝突やサイクル衝突の認識も重要となる。最適化の目的関数には、全エージェントの経路長の総和であるflowtime（またはSOC, SIC）と、全タスクが完了するまでの時間であるmakespanの2種類があり、flowtimeは燃料消費などの最小化に適している一方、makespanは最後のエージェントが到着するまでの時間を最小化する。解決手法は、解の質とスケーラビリティの観点から、最適（Optimal）、限定的な劣解（Bounded-suboptimal）、劣解（Suboptimal）の3つのクラスに分類される。アルゴリズムの原理別では、MAPFをSATやネットワークフローなどの決定問題に帰着させるreduction-based approachと、個別の経路計画と衝突解消を組み合わせるsearch-based approachに大別される。reduction-based approachは強力な既存ソルバーを利用できる利点があるが、マップサイズが大きくなるとスケーラビリティが低下する傾向にある。一方、代表的なsearch-based手法であるConflict-Based Search (CBS) は、低レベルでの経路計画と高レベルでの制約ツリー構築による衝突解消を行う2レベルの最適アルゴリズムであるが、衝突数が増加するとツリーの分岐が爆発的に増える課題がある。これに対し、Enhanced CBS (ECBS) は限定的な劣解を、Prioritized Planningは優先順位に基づく逐次的な計画を、Large Neighborhood Searchはメタヒューリスティクスを用いた反復的な解の改善をそれぞれ提供する。
MAPFの解決手法として、ルールベースのPriority Inheritance via Backtracking (PIBT) や、PIBTを構成生成器として探索手順と組み合わせるLazy Constraint Addition Searchなどのハイブリッド手法が挙げられ、これらは複雑なインスタンスに対して高いスケーラビリティを示す一方で、解のコストが増大する傾向がある。また、PRIMALやRAILGUNといった学習ベースの手法も、解の質を犠牲にすることで有望なスケーラビリティを実現している。MAPFの応用範囲は極めて広く、自律型倉庫や生産ラインにおける移動ロボット群、農業用ロボット、ビデオゲームのキャラクター移動、さらにはUAVスウォームの3Dロードマップ上での経路計画や、隊列形成、UAV交通管理など多岐にわたる。鉄道のルーティングや可変長列車、道路上のエッジを占有する車列（convoy）の計画、避難時におけるリーダーとフォロワーによるスウォーム制御、自動運転車のバリパークや交差点管理、空港での牽引車両の計画にも適用されている。その他、仮想ネットワーク埋め込み、3D配管ルーティング、ビンピッキングにおける協調ロボットアームなど、リソース割り当てや物理的な制約を伴う多様な問題にMAPFの枠組みが活用されている。MAPFの前提条件は、エージェントの目標に関する仮定、エージェントの性質、環境の性質、通信、および時間に関する5つの主要なカテゴリに分類される。
本セクションでは、マルチエージェント経路探索（MAPF）における多様な問題設定（flavors）を分類するための5つの基本仮定と、それらを拡張・変更することで生じる問題カテゴリについて詳述している。基本仮定には、問題情報の事前既知性、実行の確実性、環境の離散性や均質性、およびエージェントのモデル（ホロノミック性や運動学的制約の欠如など）が含まれる。これらを変更することで、エージェントの目的地割り当てを伴う問題、実行中に新たな目標や障害物が出現する時間拡張型割り当て問題、移動時間の変動や行動失敗を考慮する行動の不確実性を含む問題などが定義される。さらに、連続空間や連続時間といった特殊な環境、あるいは非ホロノミックな車両や複数頂点を占有するエージェントといった特殊なエージェントモデルを用いる問題、および多目的最適化などの固有の問題へと拡張される。各カテゴリの記述では、タスク割り当ての有無などの影響力の大きい特徴から順に整理され、既存の解法（帰着ベースやCBSベース、メタヒューリスティクス、学習ベースなど）の適用可能性についても言及される。
目標ベースのMAPF（Goal-Based Variations）は、エージェントが到達すべき目標の数や性質を変化させた問題群であり、タスク割り当て（Task Assignment, TA）の有無、マルチゴール（MG）特性、サブゴール（SG）の数、目的地（Destination）の定義、目標への制約（Goal constraints）によって分類される。TAが存在する場合、どのエージェントにどの目標を割り当てるかという匿名性（Anonymity）が重要となり、全エージェントが対象となる完全匿名（Full）から、特定のサブセットのみが対象となる選択的匿名（Selective）まで存在する。マルチゴール問題では、1つの目標が複数のサブゴール（$N$個など）を持つ場合があり、目標の完了はすべてのサブゴールが達成された時点と定義される。目的地については、最後に訪れた目標を終点とする「Last goal」のほか、目標とは別の特定の場所を終点とする「Distinct subset」や、終了後に自由に移動できる「None」などのタイプが定義される。目標制約には、全エージェントに適用されるグローバルな期限（G-deadline）や各目標に個別の期限がある形式（I-deadline）、遅延に対してペナルティを課す形式（Tardiness penalty）があり、さらに目標間やサブゴール間の順序制約（G-precedence, S-precedence, Order）や、複数のエージェントによる協力（Cooperation）が含まれる。既存の解決手法としては、問題への帰着を用いる手法（R）、Conflict-Based Search（CBS）に基づく手法（C）、およびその他の手法（O）が用いられている。
本セクションでは、エージェントの目標達成条件や制約が異なる複数のMAPFのバリエーションが定義されている。MAPF-DLはグローバルな期限 $T_{dl}$ を持ち、全エージェントが期限内に目標に到達できない場合、到達したエージェント数を最大化することを目的とし、CBSの修正版やネットワークフロー、制約充足問題への帰着によって解かれる。MAPF-DTは各エージェントに個別の期限（due time）が設定され、遅延（tardiness）を最小化する問題であり、最大遅延、合計遅延、または合計単位ペナルティの最適化が検討され、整数線形計画法への帰着により解かれる。MG-MAPFは各エージェントが順序不定の複数のサブゴールを訪問する必要があり、訪問順序の最適化と衝突回避経路の探索の二段階で構成され、SMTを用いた帰着手法などが提案されている。OMG-MAPFはサブゴールの訪問順序が既定である問題であり、MAPF-PCはエージェント間でも適用可能な先行制約（precedence constraints）を導入したMG-MAPFの一般化である。AMAPFは目標がエージェントに紐付けられていない匿名的な問題であり、ネットワークフローへの帰着によって、makespanの最適化において多項式時間で解けるという特性を持つ。
AMAPFwIDは、各匿名ゴールに対して、そのゴールがエージェントによって占有されなければならない期限（deadline）が設定されたAMAPFの一般化問題である。この問題におけるゴールの獲得とは、エージェントがそのゴール上に位置することを指し、MAPF-DLにおける「完了したゴールの数を最適化する」というグローバルな期限の概念とは異なり、個別の期限が厳密に定義されている。本セクションでは、エージェントの挙動に基づいた3つのバリエーションが提示されており、第一に、エージェントがターゲットに到達した時点で環境から消失するケース、第二に、エージェントがターゲット上に留まり続けるケース、そして第三に、期限が切れた後もゴールが占有されている限りエージェントがターゲットから離脱できるケースが挙げられている。特に第一のケースでは、期限の時点でゴール上に位置しているすべてのエージェントが環境から消失するという制約を持つ。