高密度倉庫向けマルチロボット計画アルゴリズムを提案 最大容量での保管・取出しを効率化

何が起きたか

自動倉庫では、保管密度の最大化と高い取出しスループットの実現の間に根本的なトレードオフがある。通路をなくすことで容量を増やすパズルベース保管(PBS)アーキテクチャは、高密度空間での複数ロボットの調整が計算上困難であり、デッドロックの可能性がある。本論文では、単一の境界からアクセス可能な長方形グリッドを対象とし、荷物をまず最大容量まで保管し、その後、計画された出庫順序に従って効率的に取り出す「最大容量での順序付き保管・取出し問題」の新しいマルチロボット定式化を導入した。この研究は、リロケーション不要の配置の特性を活用することで、幾何学的実現可能性と実行効率の間のギャップを埋める。これらの特性は、オンラインの優先順位付きマルチエージェント経路探索アルゴリズムを導くものであり、これが本研究の主な貢献である。一般的な集中型プランナーとは異なり、このアプローチは保管配置の特定の不変条件を利用して完全性を保証し、デッドロックを防止し、スケーラビリティを可能にする。実験では、この手法はロボット台数に対してメイクスパンがほぼ線形に改善し、ロボット台数がグリッド幅Cに達するまでその傾向が続くことを示した。さらに、ロバスト性を支えるアルゴリズムのオーバーヘッドは無視できる程度であり、出庫順序の不確実性をロバストな保管配置で処理しても、非ロバストなベースラインと比較して実行速度に有意なペナルティはない。

Key Facts

なぜ重要か

この研究は、高密度倉庫におけるマルチロボットの調整問題に対して、完全性を保証しデッドロックを防止するスケーラブルなアルゴリズムを提案している点で重要である。実験結果は、ロボット台数が増えてもメイクスパンがほぼ線形に改善することを示しており、実用的な高密度倉庫システムの実現に寄与する可能性がある。また、ロバスト性を追加しても実行速度に大きなペナルティがないことは、不確実性のある実運用環境での適用可能性を示唆している。