強化学習と3Dビジョンを組み合わせた新たなブレークスルー：高性能オンラインパレタイジングロボット

国立防衛技術大学、クレムソン大学、Seebit Robotics の研究者らが協力し、深層強化学習を使用してオンライン ビン パッキング問題を解決し、既存のヒューリスティック アルゴリズムを上回る成果を上げました。ユーザー調査では、このアルゴリズムが人間のオンラインパレタイジングのレベルに達しているか、あるいはそれを上回っていることが示されています。著者チームはまた、このトレーニング モデルを産業用ロボットに展開し、業界初の高性能 (スペース利用率 70% 以上で、ランダム サイズの箱を 50 個以上連続して積み重ねる) な無秩序混合パレタイジング ロボットを実現しました。

[[375389]]

物流や倉庫管理の分野では、乱雑に混載されたカートンをパレット化するロボットに対する需要が大きくなっています。さまざまなサイズの箱が順番どおりに到着しない場合、ロボットを使用して自動化および効率的なパレタイジングを実現し、人手を節約しながら物流回転効率を向上させることは、物流倉庫の自動化における難しい問題です。この問題の核心は、コンテナのスペース利用率を最大化するためにコンテナ内の各カートンの配置を計画するという、古典的な NP 困難な問題であるビンパッキング (BPP) を解くことです。 BPP 問題を解決するための従来の方法は、主にヒューリスティックなルール検索に基づいています。

実際のアプリケーション シナリオでは、ロボットはコンベア ベルトに流れてくるすべての箱を事前に確認できないことが多く、そのため箱のシーケンス全体にわたって最適な計画を立てることができません。したがって、既存の BPP 方式を実際の物流シナリオに直接使用することはできません。

実際、人々はこれから出てくる箱の形や大きさに基づいて素早く決定を下すことができます。箱のシーケンス全体についてグローバルな計画を立てる必要はなく、また立てることもできません。この部分的なボックスのシーケンスのみが見られるビンパッキング問題は、オンライン ビンパッキング問題 (オンライン BPP) と呼ばれます。物流コンベア ライン上で箱をパレット化するタスクは、一般的にオンライン BPP 問題として説明できます。したがって、この問題を解決することは、真に実用的なインテリジェントパレタイジングロボットの開発にとって非常に重要です。

オンライン BPP 問題では、ロボットは今後表示される k 個のボックス (つまり、先読みされる k 個のボックス) のサイズ情報のみを観察できます。これを BPP-k 問題と呼びます。順番に到着する箱については、ロボットはすぐに計画と配置を完了する必要があります。すでに配置されている箱の調整は許可されません。同時に、箱の障害物の回避と配置の安定性の要件を満たす必要があります。最終的な目標は、コンテナのスペース利用率を最大化することです。オンライン BPP 問題の複雑さは、ボックスの仕様、コンテナーのサイズ、ボックス シーケンスの分布、先読みの数などの要因によって決まります。一部のボックスシーケンスについては限られた情報しか知られていないため、これまでの組み合わせ最適化手法ではこのタスクに対応できません。

最近、国立防衛技術大学、クレムソン大学、VisionBit Robotics の研究者が協力し、深層強化学習を使用してこの問題を解決することを提案しました。このアルゴリズムはパフォーマンスに優れ、実装も簡単です。先読みボックスがいくつあっても適用でき、スペース利用率は人間のレベルに達するか、それを上回ります。同時に、チームは3Dビジョン技術を組み合わせて、業界初の高効率な無秩序混合パレタイジングロボットを実現しました。この論文は人工知能に関する最高峰の会議であるAAAI 2021に採択されました。

論文リンク: https://arxiv.org/abs/2006.14978

方法の紹介

著者らは、制約付き深層強化学習を使用して、1 つのボックスのみを先読みできる場合の BPP-1 問題を解決します。その後、モンテカルロ木探索に基づいて BPP-1 から BPP-k への拡張が実現されました。下の図 1 は、BPP-1 問題と BPP-k 問題のシナリオ図を示しています。

図 1 (上): BPP-1 シーンの概略図。緑色のボックスは前方を向いたボックスです。

図 1 (下): BPP-k 問題のシナリオ図。緑色のボックスは先読みボックスです。

制約付き強化学習による BPP-1 の解決

強化学習は、自己推論と経験を通じて実行戦略を学習するアルゴリズムです。動的な変化の観察に基づくオンライン BPP などの逐次的な意思決定問題を解決するのに非常に適しています。同時に、箱の積み重ねプロセスのシミュレーションは非常に「安価」であるため、強化学習アルゴリズムをシミュレーション環境で大量に実行し、経験から積み重ね戦略を学習することができます。

しかし、強化学習アルゴリズムをオンライン BPP に適用するには、いくつかの課題があります。まず、水平配置面が均一なグリッドに分割されている場合、BPP のアクション スペースは非常に大きくなり、サンプル効率の低い強化学習アルゴリズムは大きなアクション スペースの処理に適していません。さらに、ボックス配置プロセスの物理的制約 (衝突回避、安定したサポートなど) を学習する際に、強化学習アルゴリズムをより堅牢かつ効率的にするには、特別な設計も必要です。

スタッキングの物理的な実現可能性と安定性を確保しながらアルゴリズムの学習効率を向上させるために、著者らは、Actor-Critic フレームワークに基づく「予測投影」アクション監視メカニズムを導入しました (図 2)。この方法では、アクターのポリシー ネットワークとクリティックの Q 値 (予想される将来の報酬) ネットワークを学習するだけでなく、エージェントが現在の状態における実行可能なアクション空間 (実行可能性マスク) を「予測」することもできます。トレーニング プロセス中に、予測された実行可能マスクに基づいて探索アクションが実行可能アクション空間に「投影」され、その後アクションがサンプリングされます。この教師あり実現可能性予測法では、一方では強化学習アルゴリズムが物理的制約を迅速に学習できるようになり、他方ではトレーニング中にボックスを実行不可能な位置に配置したり、シーケンスを途中で終了したりすることが回避されるため、トレーニング効率が大幅に向上します。

図 2: 「予測投影」アクション監視メカニズムに基づく制約付き深層強化学習。

モンテカルロ木探索に基づく BPP-k 拡張

図 3: 私たちのアルゴリズムのスペース利用率は、先読みボックスの数と正の相関関係にあります。

アルゴリズムが現在のボックスを積み重ねる際に後から到着するボックスのサイズを考慮できる場合、より良い積み重ね結果が得られる可能性があります (図 3 を参照)。 k (k>1) 個のボックスを先読みする場合、1 つのアプローチは、複数のボックスのスタッキング戦略を直接学習することです。ただし、この戦略は、任意の数の先読みビンにうまく一般化できないことがよくあります。異なる k に対して別々の戦略をトレーニングするのは明らかに賢明な考えではありません。

この点で、本論文で提案されたアプローチは、BPP-1の基本戦略に基づいており、ソートされた木探索法を通じてBPP-kのケースに拡張されています。実際、複数のボックスを先読みする基本的な考え方は、現在のボックスを配置するときに後続のボックス用に適切なスペースを「予約」し、これらのボックスの全体的な配置スペースの利用率を高めることです。 「予約」は、k 個の先読みボックスの異なる順序を意味します。したがって、最も高いスペース利用率を実現する配置を見つけるには、k 個のフォワード ボックスのさまざまな配置 (図 4) を検索するだけで済みます。このシーケンスに対応する現在のボックスの配置が、現在のボックスの最適な配置です。このアプローチは、現在のボックスを配置するときに後のボックスを考慮することと同じです。ただし、これらの仮想配置シーケンスでは、実際の順序で最初に到着したボックスを、後に到着したボックスの上に配置できないことに注意してください。

図 4: ボックスの実際の順序 (左上) と仮想的な並べ替え (左下、実際の順序の先頭のボックスは、実際の順序の末尾のボックスの上に配置できません)。右側は、さまざまなシーケンスのソート ツリーを示しています。

明らかに、すべての順列を考慮すると、すぐに組み合わせ爆発が発生する可能性があります。この目的のために、著者らはモンテカルロ木探索 (MCTS) を使用して検索空間を縮小しました。著者は、批評家ネットワークによって出力された Q 値に基づいて、現在の状態から得られる可能性のある報酬を推定します。ソートされたツリーの検索中、より高い報酬を受け取る可能性が高いノードが拡張のために優先的に選択されます。これにより、検索の複雑さが線形範囲内に維持されます。

さらに、著者らは、ボックスの水平回転と複数のコンテナの積み重ねを処理するための拡張機能も提示しています。積み重ね中にボックスが水平方向に回転できる場合、2 つの方向を個別に処理するには、BPP-1 モデルでアクション スペースと実行可能マスクをコピーするだけで済みます。複数のコンテナを積み重ねる場合、アルゴリズムは各コンテナに箱を置くことによってもたらされる Q 値の変化を定量化する必要があります。著者は批評ネットワークを使用して、特定のコンテナに箱を積み重ねる前と後の箱の Q 値を評価し、箱が配置されるたびに Q 値の低下が最小になるようにします。

実験結果

BPP-1では、著者らは提案された手法を他のヒューリスティックアルゴリズムと比較しました（図5）。 3 つの異なるデータセットでは、深層強化学習アルゴリズムのパフォーマンスは、人間が設計したヒューリスティック ルールのパフォーマンスよりも大幅に優れています (特にオンライン BPP の場合)。

図 5: BPP-1 問題における深層強化学習アルゴリズムとヒューリスティック アルゴリズムのパフォーマンス (配置されたボックスの数とスペース利用率) の比較。

また、BPP-1 問題に関して、著者らはさまざまな制約 (図 6) についてアブレーション実験を実施しました。MP - 実行可能なマスク予測、MC - 実行可能なマスク投影、FE - アクション エントロピー (多様性) 最大化。実験結果によると、トレーニング中にアクション制約を追加すると、トレーニング効果が大幅に向上することが示されています。

図6: BPP-1問題における我々のアルゴリズムのアブレーション実験

著者らは、ソート木探索により先読み数 k が増加するにつれて空間利用率が向上すること (図 7b)、およびモンテカルロ木探索を使用するとパフォーマンスに大きな影響を与えずにソート木探索の時間オーバーヘッドを大幅に削減できること (図 7a) を BPP-k で検証しました。さらに、著者らは、本論文の BPP-1 アルゴリズムの空間利用率と人間による配置の空間利用率を比較するために、BPP-1 に関するユーザー調査を実施しました。図 7c に示すように、私たちの方法は人間による配置のパフォーマンスを上回っています。合計 1851 の高難易度ランダム ボックス シーケンスのうち、人間は 406 回勝利し、平均パフォーマンスは 52.1% でした。一方、強化学習は 1339 回勝利し、平均パフォーマンスは 68.9% でした。

図 7 (a): 網羅的ソート数検索と MCTS アルゴリズムの時間コストの比較。(b): 網羅的ソート数検索と MCTS アルゴリズムの時間コストの比較。(c): 提案アルゴリズム、ヒューリスティック アルゴリズム BPH、および人間のユーザーのコーディング パフォーマンスの比較。

先読みボックスの数を変えた場合の、提案手法とヒューリスティックアルゴリズム BPH のパフォーマンス比較を図 8 に示します。 BPH アルゴリズムでは先読みボックスの順序を任意に調整できますが、私たちの方法ではそれができませんが、それでも私たちの方法の方が優れたパフォーマンスを実現します。

図 8: 3 つのデータセットにおける BPP-k タスクでの深層強化学習アルゴリズムとヒューリスティック アルゴリズムのパフォーマンス比較。

本論文のアルゴリズムの有効性を検証するために、著者チームは産業用ロボットにモデルを展開し、インテリジェントなパレタイジングロボットを実装しました (図 9、完全なビデオを参照)。シミュレーション環境でトレーニングされた戦略を実際の環境に適用するには、仮想環境から実際の環境への戦略の移行 (Sim2Real) という問題が発生します。この目的のために、著者らは「Real2Sim」のアイデアに基づいて、3Dビジョンアルゴリズムを使用してコンテナ上のボックスの実際の配置をリアルタイムで検出し、強化学習モデルの入力として仮想世界に対応する理想的なボックス表現に変換しました。ランダムなサイズの箱が不規則に届いた場合でも、数十個の箱を連続して安定して素早く積み重ねることができ、コンテナスペースの利用率は70％以上で、その性能は既存の同型ロボットをはるかに上回っています。

図 9: 深層強化学習に基づく高効率無秩序混合パレタイジングロボット。