自動倉庫のような大規模かつ動的な環境における、多数のロボットの衝突回避経路計画を対象とする。エージェント数の増加に伴い探索空間が指数関数的に増大するため、計算量が爆発的に増加する点が課題である。従来のオフラインアルゴリズムは、全エージェントの計画が完全に完了するまでロボットの移動を開始できず、大規模環境では実行開始までの待ち時間が長くなる。
全エージェントの計画完了を待たずに、計算された最初のステップを即座に実行できるオンラインフレームワークを提案する。有限の時間範囲内における衝突と到達可能性に基づき、ロボットを動的にグループ化して階層的に問題を分解する手法を導入した。これにより、個別の計画とグループ単位の再計画の両方を並列化し、既存のオフライン手法と比較して応答時間を短縮しつつ、高い解の品質を実現した。
各反復において、まず全ロボットが逆方向の幅優先探索を用いた貪欲なプランナーにより、個別の経路を並列に計算する。次に、空間ハッシュを用いて将来のタイムステップにおける衝突を検出し、衝突のないロボットを確定させる。確定したロボットを動的障害物として扱うことで、残りのロボットを分離する第一段階の分解を行う。続いて、衝突が発生しているロボットを、限定された時間範囲内での到達可能性に基づいて再帰的にグループ化し、適応させたPIBTアルゴリズムを用いてグループ単位で並列に再計画を行う。再計画が失敗した場合は、混雑解消モジュールがグループの範囲を拡大して柔軟性を確保する。最後に、得られた軌道を統合し、最初の1ステップのみを実行する。
倉庫マップとランダムマップのベンチマークを用い、LaCAM*を比較対象として評価した。評価指標には、実行開始までの待ち時間（TNBE）と、衝突を無視した場合の下限値に対する総移動時間（SOC）の比率を用いた。900台のロボットを用いた実験では、TNBEを最大で60%削減した。各計画ステップは30ミリ秒未満で完了する。倉庫マップでは計画ホライゾンを長くするほど解の品質が向上するが、ランダムマップではロボット数に応じて最適なホライゾンが変化する結果となった。
ランダムマップにおいては、計画ホライゾンを長く設定しすぎると、衝突のないエージェントの割合が減少し、グループ単位の再計画が頻発することで解の品質が低下するというトレードオフが存在する。今後の課題として、より一般的なタスク割り当て設定への拡張、生涯継続的な経路計画への適用、ネットワークとの共同設計、学習を用いた改善、および理論的な保証の強化が挙げられる。
本研究は、自動倉庫のような動的な環境における大規模なマルチエージェント経路計画（MAPF）を高速かつスケーラブルに実現する、有限ホライゾン階層分解を用いた新しいアルゴリズムを提案している。この手法は、後退ホライゾン方式で一歩ずつ計画を進めるフレームワークであり、まず各ロボットが個別の計画を並列に計算した後、時空間的な衝突や到達可能性に基づいて動的にグループ化を行う。このフレームワークは、衝突解決、即時実行、および並行計画を考慮することで、オフラインアルゴリズムと比較して応答時間を短縮している。ベンチマークマップを用いた実験の結果、提案手法は高品質な解を維持しつつ、最初の行動を開始するまでの時間を最大で60%削減しており、様々な問題規模や計画ホライゾンにおいて最先端のオフライン手法を上回る性能を示している。
大規模な自動倉庫におけるマルチエージェント経路探索（MAPF）は、エージェント数の増加に伴い探索空間が指数関数的に増大するため、計算の複雑さが課題となります。既存手法の多くは、全エージェントの計画が完了するまで実行を開始できないオフライン方式であり、計算待ちによる遅延や、大規模環境におけるスケーラビリティの欠如、並列化の活用不足といった問題があります。本研究では、有限ホライゾン階層分解と高度な並列化を組み合わせた、新しいオンラインアルゴリズムを提案します。この手法は、個々のエージェントに対して一様な貪欲最適プランナーを用い、有限の時間範囲内における衝突や到達可能性に基づいてロボットを動的にグループ化することで、問題の構造を利用して計算量を削減します。衝突解決にはPIBTに基づくルーチンを使用し、各ステップを計算後すぐに実行できるため、オフライン手法と比較して実行開始までの遅延を短縮できます。実験の結果、多様なシナリオにおいて、迅速な実行開始と競争力のある解の品質が示されています。
提案手法は、並列化可能な複数の段階からなる階層的な分解アルゴリズムである。各反復において、まず全ロボットが逆方向の幅優先探索に基づく貪欲なプランナーを用いて、個別の経路を並列に計算する。次に、空間ハッシュを用いて将来のタイムステップにおける衝突を検出し、衝突のないロボットを確定させ、残りのロボットは確定済みロボットを動的障害物として扱うことで再計画を行う第一段階の分解を行う。続いて、衝突が発生しているロボットを、限定されたホライゾン内での到達可能性に基づいて再帰的にグループ化し、適応させたPIBTアルゴリズムを用いてグループ単位で並列に再計画を行う。再計画が失敗した場合には、混雑解消モジュールがグループの範囲を拡大することで、時空間的な柔軟性を高めて解決を図る。最後に、軌道を統合して最初のステップのみを実行する。この手法は、個別の計画とグループ単位の再計画の両方が並列化可能であるため高速であり、多くのロボットがホライゾン内で衝突を回避できる特性を利用して、既存のオフライン手法に匹敵する解の質を実現し、同等の速度を持つLaCAM*を大幅に上回る性能を示す。
本実験では、MAPFベンチマークの倉庫マップとランダムマップの2種類を用い、200回の試行に基づく平均性能を評価しています。提案手法は、実行開始までの待ち時間（TNBE）においてLaCAM*と比較して大幅な高速化を実現しており、例えばロボット数が900台の場合にはTNBEを60%削減しています。各計画ステップは30ミリ秒未満で完了するため、大規模な環境においても、ロボットの実際の動作時間と並行して次ステップの計画を行うことが可能です。解の品質については、全エージェントの総移動時間であるSOCを、衝突を無視した場合の下限値に対する比率で評価しています。倉庫マップでは、計画ホライゾンを長くするほど解の品質が単調に向上しますが、ランダムマップでは、ホライゾンが長すぎると衝突のないエージェント数が減少し、グループ単位の再計画が頻発するため、ロボット数に応じて最適なホライゾンが変化します。
本研究では、有限ホライゾン階層分解に基づく、スケーラブルなオンラインのマルチエージェント経路計画（MAPF）アルゴリズムを提案している。この手法は、衝突や到達可能性に基づく動的な2レベルのグルーピング、並列的な個別プランニング、および効率的なオンザフライの衝突解決を組み合わせることで、即時実行を可能にし、プランニングの遅延を削減する。実験により、計算速度と解の品質の両面において高い性能が確認されており、リアルタイムのマルチロボット協調における既存のオフライン手法に対する実用的な選択肢となる。今後の課題として、より一般的なタスク割り当て設定への拡張、生涯継続的なMAPFへの適用、ネットワークとの共同設計、学習を用いた改善、および理論的な保証の強化が挙げられる。