基于帶約束強(qiáng)化學(xué)習(xí)的 BPP-1 求解

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

在物流倉儲(chǔ)場景中，無序混合紙箱碼垛機(jī)器人有著大量的應(yīng)用需求。對(duì)于亂序到來的、多種尺寸規(guī)格的箱子，如何用機(jī)器人實(shí)現(xiàn)自動(dòng)、高效的碼垛，節(jié)省人力的同時(shí)提升物流周轉(zhuǎn)效率，是物流倉儲(chǔ)自動(dòng)化的一個(gè)難點(diǎn)問題。其核心是求解裝箱問題（Bin Packing Problem，BPP）這一經(jīng)典的 NP 難題，即為每一個(gè)紙箱規(guī)劃在容器中的擺放位置，以最大化容器的空間利用率。求解 BPP 問題的傳統(tǒng)方法大多是基于啟發(fā)式規(guī)則的搜索。

在實(shí)際應(yīng)用場景中，機(jī)器人往往無法預(yù)先看到傳送帶上即將到來的所有箱子，因而無法對(duì)整個(gè)箱子序列進(jìn)行全局最優(yōu)規(guī)劃。因而現(xiàn)有的 BPP 方法無法被直接用于真實(shí)物流場景。

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

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

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

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

方法介紹

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

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

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

基于帶約束強(qiáng)化學(xué)習(xí)的 BPP-1 求解

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

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

圖 2：基于「預(yù)測(cè) - 投影」的動(dòng)作監(jiān)督機(jī)制實(shí)現(xiàn)帶約束的深度強(qiáng)化學(xué)習(xí)。

基于蒙特卡洛樹搜索的 BPP-k 擴(kuò)展

圖 3：本文算法的空間利用率與前瞻箱子個(gè)數(shù)正相關(guān)。

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

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

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

顯然，考慮所有的排序可能很快帶來組合爆炸問題。為此，作者使用蒙特卡洛樹搜索（MCTS）來減小搜索空間。作者基于 critic 網(wǎng)絡(luò)輸出的 Q 值，對(duì)從當(dāng)前狀態(tài)之后可能得到的獎(jiǎng)勵(lì)進(jìn)行估計(jì)。在排序樹搜索過程中，優(yōu)先選擇可能得到更高獎(jiǎng)勵(lì)的節(jié)點(diǎn)進(jìn)行展開。這樣可將搜索復(fù)雜度控制在線性級(jí)別。

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

實(shí)驗(yàn)結(jié)果

在 BPP-1 上，作者將本文方法和其他啟發(fā)式算法進(jìn)行了對(duì)比（圖 5）。在三種不同數(shù)據(jù)集上，基于深度強(qiáng)化學(xué)習(xí)算法的性能顯著優(yōu)于人為設(shè)計(jì)啟發(fā)式規(guī)則（尤其是面向 Online BPP 的）。

圖 5：深度強(qiáng)化學(xué)習(xí)算法和啟發(fā)式算法在 BPP-1 問題上的性能（擺放箱子數(shù)目和空間利用率）對(duì)比。

同樣在 BPP-1 問題上，作者針對(duì)不同的約束項(xiàng)進(jìn)行了消融實(shí)驗(yàn)（圖 6）：MP - 可行掩碼預(yù)測(cè)；MC - 可行掩碼投影；FE - 動(dòng)作熵（多樣性）最大化。實(shí)驗(yàn)結(jié)果表明，在訓(xùn)練過程中加入可行動(dòng)作約束對(duì)訓(xùn)練效果有顯著提升。

圖 6：本文算法在 BPP-1 問題上的消融實(shí)驗(yàn)

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

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

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

圖 8：在三個(gè)數(shù)據(jù)集上的 BPP-k 任務(wù)中，深度強(qiáng)化學(xué)習(xí)算法與啟發(fā)式算法的性能對(duì)比。

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

圖9： 基于深度強(qiáng)化學(xué)習(xí)的高效能無序混合碼垛機(jī)器人。

責(zé)任編輯：lq