複数のグリッドを同時に占有する幾何学的形状を持つ「大規模エージェント（Large Agent）」を対象としたマルチエージェント経路計画（LA-MAPF）を扱う。エージェントが点ではなく形状を持つため、衝突検知のオーバーヘッドが増大し、エージェント数の増加に伴って計算複雑性が増大するという困難がある。
問題を解く順序に制約がない「クラスター」と、解く順序に制約がある「レベル」という2種類のサブ問題に階層分解するフレームワークを提案する。既存の独立性検出（ID）などの手法とは異なり、解の順序を考慮した分解を行うことで、解の存在可能性を損なわずに問題を細分化できる点が新規性である。
エージェント間の関連性を示すグラフを用いて、インスタンスをクラスターへと分解する。クラスターの分解には、回避不能なエージェントの集合を特定し、二分割を繰り返すプロセスを用いる。次に、各クラスターをレベルへと分解する。レベルの分解では、あるエージェントの開始・目標地点が他のエージェントの経路に関連する場合に解決順序の制約を課し、強連結成分を抽出することで初期レベルを構成する。各サブ問題は独立して解かれ、他のサブ問題の解は動的障害物として扱われる。
6種類のマップを用い、円形および矩形の形状を持つエージェントを対象に評価を行った。既存手法であるLA-CBSに適用した結果、60秒以内の解の発見成功率は平均0.27から0.80へと向上し、計算時間は平均40秒から20秒へと短縮された。分解プロセス自体の計算コストは、100エージェントを超えるインスタンスでも平均1秒未満である。
空きグリッドが少なくエージェントが密集している環境では、分解率が1に近づき、分解による効果が限定的になるという限界がある。また、問題を分割して解く性質上、元の手法と比較して最長経路長（makespan）や経路コストの総和（sum of costs）が大きくなるというトレードオフが存在する。今後の課題として、分解プロセスの最適化や、マルチスレッドを用いた並列処理への適用が挙げられる。
本研究は、複数のセルを同時に占有する幾何学的な形状を持つ「Large Agent」を対象としたマルチエージェント経路計画（LA-MAPF）において、計算複雑性を低減するためのLayered LA-MAPF手法を提案している。この手法は、LA-MAPFのインスタンスを、解の順序に制約のない「クラスター」へと分解し、さらに各クラスターを解の順序に制約を持つ「レベル」へと階層的に分解するものである。実験では、LA-CBSやLA-LaCAMといった既存手法の加速を検証しており、エージェント数が増加する様々なマップにおいて、60秒以内に解を見つける成功率が平均0.27から0.80へと向上し、計算時間も平均40秒から20秒へと短縮されることを示している。この階層的な分解アプローチにより、大規模な幾何学的エージェント問題の効率的な解決を目指している。
本研究は、幾何学的な形状を持ち複数のグリッドを占有する「Large Agent」を対象としたマルチエージェント経路探索（LA-MAPF）において、計算コストを削減するための階層的な分解手法を提案している。従来のMAPFはエージェントを単一の点として扱うが、実世界のロボットのような形状を持つエージェントを扱うLA-MAPFは、衝突検知の複雑さや衝突確率の高さから計算負荷が極めて高い。提案手法であるLayered LA-MAPFは、元の問題を、解く順番に制約がない「クラスター」と、解く順番に制約がある「レベル」という2種類のサブ問題に分解する。具体的には、まずエージェントを独立して解けるクラスターに分割し、さらにそれらを解く順序を規定したレベルへと段階的に細分化する。各サブ問題を独立して解き、他のサブ問題の解を動的障害物として扱うことで、元の問題の解の存在性を損なわずに計算コストを削減するフレームワークを構築している。
マルチエージェント経路計画（MAPF）を複数の小規模な問題に分割する既存手法として、Independence Detection (ID) がある。IDはエージェントを最小のグループに分割するが、グリッド単位の経路探索を繰り返すため計算コストが高い。Meta-Agent CBS (MA-CBS) は、衝突回数に応じてエージェントを統合するパラメータを導入することで、CBSとIDの中間的な挙動を実現している。Priority-Based Search (PBS) は、優先順位の木を構築して衝突を解消する効率的な手法だが、一般には完全性と最適性を保証しない。Prioritized Planning (PP) は、特定の条件下で優先順位に基づいた逐次的な解法を保証するが、始点や終点の配置に制約を必要とする。著者らが提案するLayered MAPFは、問題を複数のサブ問題に分解し、他のサブ問題の解を動的障害物として扱うことで、解の存在可能性を損なわずに計算コストを削減するフレームワークである。本論文では、このLayered MAPFを拡張し、大規模なエージェントへの対応や、レベルをさらに細かく分割する手法を新たに提案している。
本セクションでは、エージェントの形状や向きを考慮するLA-MAPFの基礎定義が述べられている。エージェントの状態は位置と向きの組として定義され、向きの変化に伴う衝突を考慮することで、より現実的な経路計画を可能にしている。衝突検知はエージェントの形状をグリッドに離散化して行い、計算コスト削減のために外接円と内接円を用いた距離に基づく最適化手法を導入している。エージェントごとに異なる形状に基づいた移動可能な状態遷移を表すサブグラフを定義し、同一時刻におけるグリッドの重なりである頂点衝突や、移動中のグリッドの重なりである転送衝突を衝突として扱う。大規模な問題を解くための手法として、エージェント集合を複数の部分問題に分割する分解を定義しており、各部分問題が他のエージェントの開始・目標状態を回避できる場合に、その分解は有効であるとみなされる。分解の質は、分割された部分問題のサイズのうち最大のものが全体に対して占める割合である分解率によって評価される。さらに、順序制約のないクラスターと、特定の順序で解く必要があるレベルという2種類の部分問題の概念を導入し、各エージェントの経路が他者の開始・目標状態に関連するノードを回避できるかという条件に基づいた解法可能性の定理を提示している。
本手法は、大規模なマルチエージェント経路計画（LA-MAPF）のインスタンスを、解の存在可能性を維持したまま、より小さなクラスターとレベルへと分解することで計算を高速化するものである。まず、エージェント間の関連性に基づき、インスタンスをクラスターへと分解する。クラスターの分解では、あるエージェントが常に他のエージェントと関連を持つ状態を示す「回避不能エージェント」の概念を用い、回避不能グラフの最大連結成分を「主要セット」として、残りのエージェントを分離・再統合する二分割プロセスを反復的に行うことで、クラスターの最小化を図る。次に、同一クラスター内のエージェントであっても、解決の順序を考慮することで、さらに小さな「レベル」へと分解する。解決順序グラフにおいて、あるエージェントの開始地点や目標地点が他方の関連する状態集合に含まれる場合に、解決の前後関係を向きのあるエッジとして定義し、その強連結成分を初期レベルとする。レベルの分解においてもクラスターと同様に、二分割プロセスを繰り返すことで、解決順序の制約を満たしつつ問題を細分化し、各レベルの独立した解決を可能にする。
本研究では、大規模なエージェントを伴うMAPF（Multi-Agent Path Finding）問題を、解の存在可能性を損なわずに高速化する分解手法「Layered LA-MAPF」の有効性を検証しています。実験では、既存のデータセットから選定した6種類のマップを用い、半径0.4から2.0の円形エージェントと、幅・長さ0.4から4.0の矩形エージェントを組み合わせて評価を行いました。分解プロセスは、初期クラスタリング、クラスタ分解、初期レベル割り当て、レベル分解の4段階で構成され、エージェントが疎な環境ではサブ問題の最大サイズを抑える効果が高い一方、エージェントが密集し空きグリッドが少ない環境では分解率が1に近づき、分解の効果が限定的になる特性があります。分解自体の計算コストは、ほとんどのマップで1秒未満に抑えられており、解決に30秒以上を要する場合があるLA-MAPFの計算負荷と比較して十分に小さいものです。提案手法をLA-CBSに適用した結果、エージェント数が増加しても計算時間の増加が緩やかになり、平均成功率は0.26から0.78へと向上しました。ただし、分解によって問題を小規模なサブ問題に分割するため、解の品質を示すmakespan（最長経路長）およびsum of costs（全経路長の総和）は、元の手法よりも大きくなる傾向があります。
本研究では、エージェント数の増加に伴い計算コストが指数関数的に増大する大規模エージェントMAPF（LA-MAPF）に対し、解の存在可能性を損なわずに問題を複数の小さな部分問題へ分解するLayered LA-MAPFを提案する。この手法は、各部分問題を独立して解きつつ、他の部分問題の解を障害物として考慮することで計算負荷を軽減するもので、100エージェントを超えるインスタンスでも分解にかかる時間は平均1秒未満である。実験において、LA-CBSやLA-LaCAMに本手法を適用した結果、標準的な手法と比較して計算時間を平均で半分（40秒から20秒）に短縮し、60秒の制限時間内における解の発見成功率を平均0.80に向上させた。解の品質については、両手法で同等であるが、25エージェントを超えるような標準手法が解を見つけられないケースにおいても、Layered LA-MAPFは解を見つけられる可能性がある。なお、エージェント数が多く密集したインスタンスでは効果が低下するという限界はあるが、最悪の場合でも標準的な手法を下回る性能にはならない。