マルチエージェント経路探索（MAPF）は、グラフ $G = (V, E)$ 上の $n$ 個のエージェント $A = \{1, \dots, n\}$ に対し、各エージェントが開始地点 $s_i$ から目標地点 $g_i$ へ到達する、衝突のない経路集合を求める問題である。衝突には、同一時刻に同じ頂点に位置する vertex conflict ($\pi_i[t] = \pi_j[t]$) と、エージェントが隣接頂間で入れ替わる swap conflict ($\pi_i[t] = \pi_j[t+1] \land \pi_i[t+1] = \pi_j[t]$) が含まれる。本研究では、解の品質指標として、各エージェントの到達時刻 $T_i$ の総和である sum-of-costs (SOC) $\sum_{i \in A} T_i$ を用いる。既存のサブオプティマルな手法では、高密度な環境や大規模なエージェント数において、計算時間の増大や解の発見失敗が課題となっていた。
本論文の主な貢献は、完全性を維持しながら、極めて高いスケーラビリティと実行速度を実現する LaCAM アルゴリズムを提案したことである。LaCAMは、高レベルの構成（configuration）探索と、低レベルの制約生成を分離した2層構造を採用し、制約を遅延的に適用することで探索コストを劇的に削減している。実験により、32 $\times$ 32 グリッドでエージェント数400、障害物密度20%という既存手法がタイムアウトする困難な設定において、中央値1秒で解決できることを示した。また、最大10,000エージェントの極めて大規模なインスタンスにおいても、30秒以内に全ての解を見出す高い拡張性を実証した。
LaCAMは、高レベル探索と低レベル探索の2層構造からなる。高レベル探索は、スタックを用いた深さ優先探索（DFS）スタイルで構成の列を探索し、各ノードは制約ツリーを保持する。低レベル探索は、幅優先探索（BFS）を用いて、エージェント $i$ が現在の頂点 $v$ から隣接頂点 $u \in \text{neigh}(v) \cup \{v\}$ へ移動するという正の制約を、ツリーの深さが $|A|$ に達するまで逐次的に構築する。新しい構成の生成（`get_new_config`）には PIBT などの既存アルゴリズムを応用した構成生成器を用い、制約を満たしつつ目標へ向かう有望な後続ノードを生成する。高レベルの探索空間が $O(|V|^{|A|})$、低レベルの接続可能な構成が $O(\Delta^{|A|})$ であることから、解が存在する場合に必ず解を返す完全性が保証されている。
評価では、PP, OD, PIBT, PIBT+, EECBS, LNS2 をベースラインとして、成功率、計画時間、SOC の観点から検証を行った。MAPFベンチマークにおいて、LaCAM は PP, OD, EECBS, LNS2 よりも成功率と実行時間の両面で優位であり、特に 400 エージェントの困難なシナリオ（random-32-32-20）で他手法が失敗する中、解を見出した。スケーラビリティ試験（warehouse-20-40-10-2-2）では、10,000 エージェントの条件下でも全てのインスタンスを30秒以内に解決した。解の質については、短い計画ホライゾンを用いる性質上、PP や LNS2 に劣る場合があるが、高密度な状況下では PIBT+ に対して優れた SOC を記録した。
LaCAM の高速性の要因は、高レベルノードから初期状態では1つの後続ノードのみを生成し、必要に応じて遅延的に他のノードを生成することで、実質的な分岐係数を抑制している点にある。しかし、狭い通路でエージェントがすれ違う必要がある敵対的インスタンスでは、エージェント数の増加に伴い探索回数が劇的に増大し、DFS 形式の探索が類似した構成に捕まることでタイムアウトに至るという限界も示された。今後の課題として、幅優先探索（BFS）スタイルによる makespan 最適解の導出や、大規模インスタンスに対する漸近的最適性を持つバージョンの開発、および低レベル探索における効果的な制約追加手法の検討が挙げられている。
本論文では、マルチエージェント経路探索（MAPF）のための、完全性を備えた新しいアルゴリズムである LaCAM (lazy constraints addition search for MAPF) を提案している。LaCAMは、数百台以上のエージェントが存在する環境でも迅速に解を探索するため、2レベルの探索構造を採用している。低レベルの探索ではエージェントの位置に関する制約を探索し、高レベルの探索では低レベルで指定された制約に従いながら、全エージェントの位置のシーケンスを探索する。広範な実験の結果、LaCAMは成功率、計画時間、および解の品質（sum-of-costs）のすべての観点において、既存の最先端な劣最適（sub-optimal）MAPFアルゴリズムと同等、あるいはそれ以上の性能を示すことが明らかになった。
本論文では、大規模かつリアルタイム性が求められるマルチエージェント経路計画（MAPF）問題に対し、高速なサブオプティマル解を導出する「Lazy Constraints Addition Search (LaCAM)」を提案している。LaCAMは、全エージェントの配置を示す「構成（configuration）」を探索するハイレベルな探索と、次なる構成におけるエージェントの移動制約を探索するローレベルな探索からなる2層構造のアルゴリズムであり、ハイレベルの探索においてローレベルの制約を遅延的に（lazy manner）適用することで探索コストを劇的に削減している。理論的には完全性（completeness）を備えており、解が存在する場合は解を返し、存在しない場合はその旨を報告する。実験では、1491 $\times$ 656のグリッドや10,000エージェントといった大規模・高密度なインスタンスにおいても極めて短時間での解決が可能であることを示しており、例えば32 $\times$ 32グリッドで障害物密度20%かつエージェント数400のベンチマークにおいて、既存のサブオプティマル手法が30秒のタイムアウトで失敗する中、LaCAMは中央値1秒で全インスタンスを解決した。また、その構造の簡潔さから、MAPFに限定されずマルチロボットの運動計画など幅広いドメインへの適用が期待される。
Multi-Agent Pathfinding (MAPF) は、グラフ $G = (V, E)$ 上の $n$ 個のエージェント $A = \{1, \dots, n\}$ に対し、各エージェント $i$ が開始地点 $s_i$ から目標地点 $g_i$ へ到達する一連の経路 $\pi_i = (\pi_i[0], \dots, \pi_i[T])$ を割り当てる問題である。各時刻 $t$ において、エージェントは隣接頂点または現在の頂点に留まることができ、$\pi_i[t+1] \in \text{neigh}(\pi_i[t]) \cup \{\pi_i[t]\}$ を満たす必要がある。解は、同一時刻に同じ頂点に位置する vertex conflict ($\pi_i[t] = \pi_j[t]$) および、エージェントが隣接する頂点間で入れ替わる swap conflict ($\pi_i[t] = \pi_j[t+1] \land \pi_i[t+1] = \pi_j[t]$) が発生しない conflict-free な経路集合である。本研究では、各エージェントが目標に到達して以降もその場に留まると仮定した、各エージェントの到達時刻 $T_i$ の総和である sum-of-costs (SOC) $\sum_{i \in A} T_i$ を解の品質指標として用いる。また、全エージェントの所在のタプルを configuration と定義し、エージェント間の移動が conflict-free である場合に、2つの configuration $X, Y$ は接続しているとみなす。
LaCAMは、高レベル探索と低レベル探索の2層構造を持つマルチエージェント経路探索（MAPF）アルゴリズムである。高レベル探索は、スタックを用いた深さ優先探索（DFS）スタイルで構成（configuration）の列を探索し、各ノードは制約ツリー（constraint tree）を保持する。低レベル探索は幅優先探索（BFS）を用いて制約を生成し、エージェント $i$ が現在の頂点 $v$ から隣接頂点 $u \in \text{neigh}(v) \cup \{v\}$ へ移動するという制約を、ツリーの深さが $|A|$ に達するまで（全エージェントに制約が割り当てられるまで）逐次的に構築する。新しい構成の生成（`get_new_config`）はブラックボックス関数として扱われ、PIBTなどの既存のMAPFアルゴリズムを応用して、制約を満たしつつ目標へ向かう有望な後続ノードを生成する。エージェントの選択順序は、初期ノードではスタートとゴールの距離の降順、以降のノードではゴールに未到達のエージェントを優先するなどのヒューリスティックが用いられる。本手法は、高レベルの探索空間が $O(|V|^{|A|})$、低レベルの接続可能な構成が $O(\Delta^{|A|})$ であることから、解が存在する場合に必ず解を返す完全性（completeness）が証明されている。
LaCAMの評価実験では、PP、OD、PIBT、PIBT+、EECBS、LNS2といった既存のサブオプティマルなMAPFアルゴリズムをベースラインとして、複雑な小規模インスタンス、MAPFベンチマーク、敵対的インスタンス、最大10,000エージェントの拡張性、および実装設計の5つの観点から検証が行われた。MAPFベンチマークにおいて、LaCAMはPP、OD、EECBS、LNS2と比較して成功率と実行時間の両面で優位性を示し、特に400エージェントの困難なシナリオ（random-32-32-20）において、他のベースラインが失敗する中で解を見出した。解の質（SOC）については、短い計画ホライゾンを用いる性質上、PPやLNS2に劣るものの、PIBT+と比較して高密度な状況下では優れたSOCを記録した。一方で、狭い通路でエージェントがすれ違う必要がある敵対的インスタンスでは、エージェント数の増加に伴い探索回数が劇的に増大し、DFS形式の探索が類似した構成に捕まることでタイムアウトに至るという限界が示された。スケーラビリティ試験では、warehouse-20-40-10-2-2において10,000エージェントの条件下でも全てのインスタンスを30秒以内に解決し、極めて高い拡張性を実証した。また、設計の検討により、再挿入（reinsert）操作がSOCを改善すること、およびPIBTによる後続構成生成がLaCAMの高性能に不可欠であることが確認された。
MAPF（Multi-Agent Pathfinding）のアルゴリズムは、エージェント間を結合して探索する探索ベース、SAT等へ帰着させるコンパイルベース、個別に順次計画する優先度付き計画、およびルールに従い逐次移動するルールベースの4種に分類される。LaCAMは探索ベースの手法であり、既存の主要なアルゴリズム（CBS等）と同様に2レベルの探索構造を持つが、制約の扱いが異なる。具体的には、高レベルで制約を探索するのではなく、低レベルにおいて「誰がいつどこにいるべきか」を指定する正の制約（positive constraints）を用いることで、低レベルの探索空間が劇的に増大することを防いでいる。また、既存の $A^*$ 変種が衝突判定のみを行うのに対し、LaCAMは高レベルの次状態生成時に、構成生成器として他のMAPFアルゴリズムを利用することで、より積極的な協調（aggressive coordination）を実現している。さらに、制約の追加手法については、全エージェントの行動ではなく単一エージェントの行動に対応するノードを生成する $A^*$ with operator decomposition (OD) の仕組みを部分的に継承している。
本論文では、完全性と高速性を両立した新しい探索ベースのMAPFアルゴリズムであるLaCAMを提案している。LaCAMが高速である理由は、従来のA*が1つのノードから $O(\Delta|A|)$ 個の構成（configuration）を生成し、分岐係数が膨大になるのに対し、LaCAMは高レベルノードから初期状態では1つの後続ノードのみを生成し、必要に応じて遅延評価（lazy manner）的に他の後続ノードを生成することで、実質的な分岐係数を抑制しているためである。実験では、他の最先端の非最適ソルバーが対応できない複雑で高密度なシナリオにおいても、10,000エージェントのインスタンスを数十秒で解決できるスケーラビリティを示している。今後の展望として、幅優先探索（BFS）スタイルを採用することでmakespan最適解を得る手法や、大規模なインスタンスに対して実用的な漸近的最適性（asymptotic optimality）を持つバージョンの開発が挙げられている。また、低レベル探索における効果的な制約の追加や、構成生成器（configuration generator）の設計改善が、現在の限界を克服するための重要な研究課題として示されている。