技術要約：最大容量におけるマルチロボットの順序付き保管および回収のための、完全、スケーラブル、かつ堅牢な優先度付きプランニング

1. 問題定義

本論文は、高密度なパズル型ストレージ（PBS）システム、特に「最大容量における順序付き保管および回収問題」におけるマルチロボットの調整という課題に取り組んでいる。

背景と課題:

• 高密度制約: Kivaスタイルのような専用の通路に依存する従来の自動倉庫システム（AS/RS）とは異なり、PBSアーキテクチャは内部通路を排除してストレージ密度を最大化する。ストレージグリッドは、限られた空セルを使用して荷物を再配置する、スライディングタイルパズルのように機能する。
• 運用フェーズ: システムは2つの明確なフェーズで動作する。
  1. 保管（Storage）: 荷物は特定のシーケンスに従ってコンベアベルト経由で到着し、グリッド容量の最大100%まで保管される必要がある。
  2. 回収（Retrieval）: 荷物は事前に計画された出発シーケンスに従って回収されなければならない。
• 核心的な対立: 先行研究（StoRMRおよびR-StoRMR）は、逐次的（シングルロボット）なリロケーションフリー（再配置不要）な配置が幾何学的に実現可能であることを確立したが、これらを複数のロボットを用いて並列に実行することについては未探索のままであった。このような高密度で通路のない環境において、複数のロボットを調整することは、デッドロックのリスクと中央集権型プランナーにおける次元の呪いのために、計算量的に困難である。
• 不確実性: システムは、実際の回収順序が計画からわずかに逸脱する場合（$k$境界の摂動としてモデル化される）の、出発シーケンスにおける不確実性にも対処しなければならない。

2. 手法

著者らは、デッドロックを防止し完全性を保証するために、リロケーションフリーなストレージ配置の特定の幾何学的不変量を利用した、**オンライン・優先度付きマルチエージェント経路探索（MAPF）**アルゴックリズムを提案している。

システムモデル

• 環境: 長方形のグリッド（$R \times C$）と、その下にあるI/O行およびコンベアベルト。
• エージェント: $m$台のロボット（$m \le C$）。移動、回転、荷物のピックアップ、およびドロップオフが可能。
• 2層高さモデル: ロボットは静止した荷物の下をナビゲートする（AMRスタイル）。これにより、同時に同じセルを占有しない限り、保管されたアイテムの下を衝突することなく通過できる。
• 制約: 位置の衝突（2つのエンティティが1つのセルに存在すること）および方向の衝突（入れ替えや直交する衝突）を回避する。ただし、「トレイン（列車）」運動（同じ方向に続いて進むこと）は許可される。

アルゴリズム：非同期優先度付きプランニング

このアプローチは、全エージェントに対して同時に解を求めるのではなく、アイドル状態のロボットに動的にタスクを割り当てることで、プランニングプロセスをデカップル（分離）する。

1. タスク割り当て:
   • 保管: ロボットがアイドル状態になると、到着シーケンスにおける次に未請求の荷物が割り当てられる。ピックアップ地点に最も近いロボットが貪欲に選択される。
   • 回収: ロボットは、出発シーケンスにおける次に未請求の荷物を請求する。ロボットは、有効なパスが正常に計算された場合にのみ、荷物を請求できる。
2. 経路計画:
   • プランナーは、空間時間A探索（space-time A search）を使用し、ロボットの現在位置からピックアップ/ドロップオフ地点までの時間最小の軌跡を生成する。
   • グローバル予約テーブル: 衝突を防ぐため、システムは位置 $p$、タイムステップ $t$、禁止進入方向 $d$ からなる空間時間制約 $(p, t, d)$ を追跡する予約テーブルを維持する。これにより、方向的な追従衝突を明示的に防止する。
   • 障害物管理: 保管された荷物は静的な障害物として扱われる。荷物をピックアップする際にロボットが計画を行うと障害物テーブルから動的に削除され、ドロップオフ時に再び追加される。
3. 回収の複雑さへの対処:
   • 回収における重要な課題は、荷物をドロップオフした後にロボットがどこで待機すべきかを決定することである。
   • 戦略: アルゴリズムは、ロボットを次の未請求の荷物の下に配置しようと試みる。それがアクセス不能な場合は、最も近いアクセス可能な未請求の荷物の下に待機するというフォールバックを行う。アクセス可能な荷物がない場合、ロボットは後方の行にある、確実に妨げにならないセルに移動する。
   • シーケンスの遵守: 出発シーケンスが尊重されることを確実にするため、ロボットは荷物 $j-1$ がI/O行へ向かうパスがキューに入った後にのみ、荷物 $j$ のためのパスを計画する。

理論的保証

論文では、保管および回収の両方のフェーズについて完全性（アルゴリズムは解が存在する場合、常に解を見つける）を証明している。

• 根拠: 証明は、リロケーションフリーな配置の特性（先行するStoRMR/R-StoRMRの研究で確立されたもの）に基づいている。これらの配置は、他の荷物が移動しない限り、シーケンス内の任意の荷物に対してI/O行への経路（またはその逆）が存在することを保証する。
• 帰納法: 著者らは、最初の $k-1$ 個の荷物が正常に保管/回収された場合、配置の幾何学的特性により、$k$ 番目の荷物も少なくとも1台のアイドルロボットによってアクセス可能であることを帰納法を用いて示し、100%の密度においてもデッドロックを防止することを証明している。

3. 主な貢献

1. マルチロボット定式化: 最大容量における順序付き保管および回収のための新しい定式化を導入し、幾何学的実現可能性（逐次的）と実行効率（並列的）の間のギャップを埋めた。
2. 優先度付きプランニングアルゴリズム: 高密度環境において完全性とデッドロック防止を保証するために、リロケーションフリー配置の不変量を利用した、非同期・オンラインアルゴリズムを提案した。これは、優先度付きMAPF手法としては稀な成果である。
3. スケーラビリティと効率性: このアプローチが、$m = C$（グリッド幅）に達するまで、メイクスパン（総時間）において、ロボット数の増加に伴い、ほぼ線形に近い改善を達成することを示す。
4. 無視できるオーバーヘッドでの堅牢性: 出発シーケンスの不確実性（$k$ 境界の摂動）に対処するために堅牢なストレージ配置（R-StoRMR）を使用しても、実行速度に重大なペナルティが生じないことを示す。
5. 低い劣最適性: 理論的には最適だがスケーラビリティに欠ける結合型（centralized coupled）プランナーと比較して、低いメイクスパン劣最適性（比率1.09から1.21）を示す。

4. 実験結果

実験は、最大 $30 \times 30$ のグリッドと、変動するロボット数（1から$C$まで）を用いて行われた。

• スケーラビリティ: システムは、ロボット数の増加に伴い、メイクスパンの減少においてほぼ線形のスピードアップを達成する。$20 \times 20$ のグリッドでは、改善比率は20台のロボットまで理想的な線形ベンチマークに密接に従う。
• 実行時間: グリッドサイズやロボット数が増加しても、1ロードあたりのプランニング時間はサブ秒（1秒未満）の範囲に留まり、リアルタイムのオンライン運用に適している。
• 堅牢性のペナルティ: 標準的な配置（$k=0$）と堅牢な配置（$k=0.4C$）を比較した結果、実行ペナルティは無視できる程度であることが判明した。メイクスパンおよび総移動距離はほぼ同一であった。
• 調整オーバーヘッド: 衝突回避マニューバにより、ロボットが増えると総移動距離はわずかに増加するが、その増加は緩やかである（20台のロボットの場合でも、単一ロボットと比較して5%未満）。
• 最適性: 計算量により小規模なバッチに限定される結合A*ソルバーと比較して、優先度付きプランナーは1.09から1.21の劣最適性比を示す。著者らは、この差の一部は、結合プランナーがコンベアモデルを利用してわずかな順序変更を許容できることによるものであり、優先度付きアプローチは厳格なシーケンス保証を維持するためにそれを避けているためであるとしている。

5. 重要性と主張

本論文は、物流における根本的なトレードオフ、すなわち「ストレージ密度の最大化」と「高い回収スループットの維持」の両立を解決すると主張している。優先度付きプランニングが、特定の幾何学的不変性に導かれることで、100%の密度環境においても完全かつデッドロックフリーであり得ることを証明することで、本研究はパズル型ストレージにおけるマルチロボットシステムの実際的な展開を可能にする。

著者らは、提案手法が「次元の呪い」を伴う中央集権型プランナーを必要としないことを強調している。代わりに、ストレージレイアウトの構造的特性を利用することで、大規模な並列実行を可能にしている。決定的なことは、不確実性（可変的な出発シーケンス）に対する堅牢性を、システムの速度や効率を犠牲にすることなく統合できることを示した点であり、これにより、到着時や出発時の時間が変動する現実世界の物流における実行可能なソリューションとなっている。

結論として、結合探索と比較してわずかな最適性のギャップはあるものの、提案された手法のスケーラビリティと堅牢性は、大規模なリアルタイムアプリケーションにおいてより優れている。今後の課題として、最適性のギャップを狭めるための他のMAPF技術（PIBTなど）の探索や、マルチロボットの調整に特化した配置の調査が挙げられている。