國防科技大學、克萊姆森大學和視比特機器人的研究人員合作使用深度強化學習求解在線裝箱問題，該方法的性能表現優于現有的啟發式算法。用戶研究顯示，該算法達到甚至超越了人類的在線碼垛水平。作者團隊還將訓練模型部署到了工業機器人上，實現了業界首個高效能（連續碼放 50 個以上隨機尺寸箱子，空間利用率大于 70%）無序混合碼垛機器人。

在物流倉儲場景中，無序混合紙箱碼垛機器人有著大量的應用需求。對于亂序到來的、多種尺寸規格的箱子，如何用機器人實現自動、高效的碼垛，節省人力的同時提升物流周轉效率，是物流倉儲自動化的一個難點問題。其核心是求解裝箱問題（Bin Packing Problem，BPP）這一經典的 NP 難題，即為每一個紙箱規劃在容器中的擺放位置，以最大化容器的空間利用率。求解 BPP 問題的傳統方法大多是基于啟發式規則的搜索。

在實際應用場景中，機器人往往無法預先看到傳送帶上即將到來的所有箱子，因而無法對整個箱子序列進行全局最優規劃。因而現有的 BPP 方法無法被直接用于真實物流場景。

事實上，人可以根據即將到來的幾個箱子的形狀尺寸，很快地做出決策，并不需要、也無法做到對整個箱子序列的全局規劃。這種僅僅看到部分箱子序列的裝箱問題，稱為在線裝箱問題（Online BPP）。物流輸送線邊上的箱子碼垛任務一般都可以描述為 Online BPP 問題。因此，該問題的求解對于開發真正實用的智能碼垛機器人有重要意義。

在 Online BPP 問題中，機器人僅能觀察到即將到來的 k 個箱子的尺寸信息（即前瞻 k 個箱子），我們稱其為 BPP-k 問題。對按序到來的箱子，機器人必須立即完成規劃和擺放，不允許對已經擺放的箱子進行調整，同時要滿足箱子避障和放置穩定性的要求，最終目標是最大化容器的空間利用率。Online BPP 問題的復雜度由箱子規格、容器大小、箱子序列的分布情況、前瞻數量等因素共同決定。由于僅知道部分箱子序列的有限信息，以往的組合優化方法難以勝任。

近日，國防科技大學、克萊姆森大學和視比特機器人的研究人員合作提出了使用深度強化學習求解這一問題。該算法性能優異，實現簡單，可適用于任意多個前瞻箱子的情形，擺放空間利用率達到甚至超過人類水平。同時，該團隊結合 3D 視覺技術，實現了業界首個高效能無序混合碼垛機器人。論文已被人工智能頂會 AAAI 2021 大會接收。

論文鏈接：https://arxiv.org/abs/2006.14978

方法介紹

作者使用帶約束的深度強化學習求解 BPP-1 問題，即只能前瞻一個箱子的情形。然后基于蒙特卡洛樹搜索實現了從 BPP-1 到 BPP-k 的拓展。下圖 1 給出了 BPP-1 和 BPP-k 問題的場景示意。

圖 1（上）：BPP-1的場景示意，綠色箱子為前瞻箱子。

圖1（下）：BPP-k 問題的場景示意，綠色箱子為前瞻箱子。

基于帶約束強化學習的 BPP-1 求解

強化學習是一種通過自我演繹并從經驗中學習執行策略的算法，很適合求解 Online BPP 這種基于動態變化觀察的序列決策問題。同時，堆箱子過程的模擬仿真非常「廉價」，因而強化學習算法可以在模擬環境中大量執行，并從經驗中學習碼垛策略。然而，將強化學習算法應用到 Online BPP 上面臨幾個方面的挑戰：首先，如果將水平放置面劃分成均勻網格，BPP 的動作空間會非常大，而樣本效率低下的強化學習算法并不擅長應對大動作空間的問題；此外，如何讓強化學習算法更加魯棒、高效地學習箱子放置過程中的物理約束（如碰撞避免、穩定支持等），也是需要專門設計的。

為了提升算法的學習效率，同時保證碼放的物理可行性和穩定性，作者在 Actor-Critic 框架基礎上引入了一種「預測 - 投影」的動作監督機制（圖 2）。該方法在學習 Actor 的策略網絡和 Critic 的 Q 值（未來獎勵的期望）網絡之外，還讓智能體「預測」當前狀態下的可行動作空間（可行掩碼，feasibility mask）。在訓練過程中，依據預測得到的可行掩碼將探索動作「投影」到可行動作空間內，再進行動作采樣。這樣的有監督可行性預測方法，一方面可以讓強化學習算法快速學習到物理約束，另一方面也盡可能避免了訓練中箱子放置到不可行位置而提前終止序列，從而顯著提升訓練效率。

圖 2：基于「預測 - 投影」的動作監督機制實現帶約束的深度強化學習。

基于蒙特卡洛樹搜索的 BPP-k 擴展

圖 3：本文算法的空間利用率與前瞻箱子個數正相關。

如果算法能夠在碼放當前箱子的同時考慮之后到來的箱子尺寸，可能會得到更好的碼放效果（如圖 3 所示）。對于前瞻 k（k》1）個箱子的情況，一種方法是直接學習前瞻多個箱子的碼放策略。但是，這種策略往往難以在任意前瞻箱子數目上很好地泛化。針對不同的 k 單獨訓練一種策略顯然是不夠聰明的做法。

對此，本文的處理方法是基于 BPP-1 這一基礎策略，通過排序樹搜索的方法拓展到 BPP-k 的情況。事實上，前瞻多個箱子的基本思想，就是在擺放當前箱子時，為后續箱子「預留」合適的空間，以使得這些箱子的整體擺放空間利用率更高。「預留」暗含了對于 k 個前瞻箱子的不同排序。因此，我們只需要搜索 k 個前瞻箱子的不同排序（圖 4），找出一種空間利用率最高的排序，該序列所對應的當前箱子的擺放位置，即為當前箱子的最佳擺放位置。這樣的處理方式，等同于在當前箱子的擺放過程中考慮了后來的箱子。不過，需要注意的是，在這些虛擬的擺放序列中，實際順序中先到的箱子不能擺在后到的上面。

圖 4：箱子的真實順序（左上）和虛擬重排順序（左下，實際順序靠前的箱子不能放在實際順序靠后箱子的上面），右邊展示了不同序列的排序樹。

顯然，考慮所有的排序可能很快帶來組合爆炸問題。為此，作者使用蒙特卡洛樹搜索（MCTS）來減小搜索空間。作者基于 critic 網絡輸出的 Q 值，對從當前狀態之后可能得到的獎勵進行估計。在排序樹搜索過程中，優先選擇可能得到更高獎勵的節點進行展開。這樣可將搜索復雜度控制在線性級別。

此外，作者還介紹了處理箱子水平旋轉和多容器碼放的擴展情況。如果碼放過程中允許箱子水平旋轉，則只需將 BPP-1 模型中的動作空間和可行掩碼同時復制，分別處理兩種朝向。針對多容器碼放，算法需要對箱子放入每個容器所帶來的 Q 值變化進行量化：作者使用 critic 網絡對箱子碼放到某個容器前后的 Q 值進行評估，每次都將箱子放入 Q 值下降最小的容器內。

實驗結果

在 BPP-1 上，作者將本文方法和其他啟發式算法進行了對比（圖 5）。在三種不同數據集上，基于深度強化學習算法的性能顯著優于人為設計啟發式規則（尤其是面向 Online BPP 的）。

圖 5：深度強化學習算法和啟發式算法在 BPP-1 問題上的性能（擺放箱子數目和空間利用率）對比。

同樣在 BPP-1 問題上，作者針對不同的約束項進行了消融實驗（圖 6）：MP - 可行掩碼預測；MC - 可行掩碼投影；FE - 動作熵（多樣性）最大化。實驗結果表明，在訓練過程中加入可行動作約束對訓練效果有顯著提升。

圖 6：本文算法在 BPP-1 問題上的消融實驗

作者在 BPP-k 上驗證了排序樹搜索可以使空間利用率隨著前瞻數量 k 的提升而提升（圖 7b），而使用蒙特卡洛樹搜索可以在不明顯影響性能的前提下，顯著降低排序樹搜索的時間開銷（圖 7a）。此外，作者針對 BPP-1 進行了用戶研究，比較本文 BPP-1 算法和人擺放的空間利用率。如圖 7c 所示，本文方法超越了人類擺放的性能：在總共 1851 個高難度隨機箱子序列中，人類獲勝的次數是 406 次，平均性能表現是 52.1%，而強化學習獲勝的次數是 1339 次，平均性能表現是 68.9%。

圖 7 （a）：窮舉排序數搜索和 MCTS 算法的時間開銷對比；（b）：窮舉排序數搜索和 MCTS 算法的時間開銷對比；（c）：本文算法、啟發式算法 BPH 和人類用戶的碼放性能對比。

對于不同的前瞻箱子數，本文方法和啟發式算法 BPH 的性能對比情況如圖 8 所示。盡管 BPH 算法允許對前瞻箱子的順序進行任意調整而本文方法不允許，但本文方法仍然能取得更好的性能。

圖 8：在三個數據集上的 BPP-k 任務中，深度強化學習算法與啟發式算法的性能對比。

為驗證本文算法的有效性，作者團隊將模型部署到工業機器人上，實現了一個智能碼垛機器人（圖 9，查看完整視頻）。將仿真環境訓練的策略應用到真實環境，涉及從虛擬到真實環境的策略遷移（Sim2Real）問題。為此，作者基于「Real2Sim」的思路，采用 3D 視覺算法，實時檢測容器上箱子的真實擺放情況，并轉換為與虛擬世界對應的理想 box 表示，作為強化學習模型的輸入。對于亂序到來的隨機尺寸箱子，該機器人能夠連續、穩定、快速碼放數十個箱子，容器空間利用率達到 70% 以上，性能遠超現有同類型機器人。

圖9： 基于深度強化學習的高效能無序混合碼垛機器人。

責任編輯：lq