如何更有效率解決物品裝箱任務？ICLR 2022 值得注意的裝箱演算法介紹

在物流業與製造業中，常會遇到材料分類裝箱，或是物品裝箱的問題，以往都是以人工方式排列，但這十分耗費人力，且不一定能排列最佳的裝箱方式。隨著人工智慧的興起，許多學者針對裝箱問題進行研究。

隨著人工智慧的興起，許多學者針對裝箱問題進行研究。這篇文章將介紹什麼是裝箱任務，並介紹以往裝箱任務的解決方法，同時，也將介紹在 ICLR 2022 所提出的 Learning efficient online 3D bin packing on packing configuration trees. 效率更好且表現較佳的裝箱演算法。

什麼是裝箱任務？

裝箱任務 (Bin Packing Problem, BPP) 是組合最佳化的經典問題，目前場域中，較常遇到的情境是 3D 裝箱任務， 3D 裝箱任務通常會針對長方形物體，依照箱子的 x、y、z 三軸分別對齊並裝箱，所以這篇文章以 3D 的裝箱任務為主，而裝箱任務又分為 Offline Bin Packing 與 Online Bin Packing。

Offline Bin Packing (Offline BPP) ：傳統裝箱任務中，通常會知道要裝箱的物品大小與數量，並依照已知的大小進行組合，這樣的任務稱為 Offline Bin packing
Online Bin Packing (Online BPP)：在實際情境中，很難確切掌握到所有要裝箱的物品大小，大多數只有當下所見的物品大小，在只知道當前的物品大小進行裝箱任務，稱為 Online Bin Packing，也因為這個方法在實際場域較為適用，所以也逐漸受到大眾的關注。

Online 的裝箱問題，無法像 Offline 可以從全部的物品中進行搜尋，並任意放置，Online BPP 必須按照即將到來的順序放置物品，所以會需要加上額外的限制條件。

3D Bin Packing Problem 有哪些解決方法？

Heuristics for Online 3D-BPP
雖然 Offline 3D-BPP 已經有比較好的研究成果，但他們基於搜索的方法是不能直接轉移到 Online 的情境下，所以還是有許多學者研究利用啟發式演算法解決這個問題，例如：
1. Deep-bottom-left (DBL, Karabulut & Inceoglu, 2004) 演算法是較多人喜愛使用的演算法，利用 DBL 對空間進行排序，並將當前項目放入第一個適合的位置。
2. Heightmap-Minimization(Wang & Hauser 2019b)，利用高度圖來觀察當前物體擺放的狀況，來計算可用空間減少的程度最小，換句話說計算的會是剩餘空間最大化。
Deep Reinforcement Learning for Online 3D-BPP
啟發式的演算法雖然實作起來較為直觀，但是 Online 3D-BPP 通常都有限制條件，大多數的 3D-BPP 討論都是較為簡單不複雜的任務，例如：假設後擺放的物品在x,y,z的座標上都不小於先擺放的物品，但我們的確會將物品先堆高在一側後，剩下的物品再擺於其他較低，但有空間的角落。實際場域裡，要考慮的限制不會只有物體擺放，還需要考慮穩定性，以及物體品重疊的狀況，在這些限制條件下，啟發式演算法的表現就較為一般。為了讓裝箱任務的策略可以更自動化，提出了使用 Deep Reinforcement Learning 來解決裝箱任務。儘管 DRL 一開始只可以在較小的空間實作，但是在實際的場域依然有結合機械手臂，進行裝箱的嘗試。Demo 影片連結
本次介紹之論文作者在 ICLR 2021 Learning Practically Feasible Policies for Online 3D Bin Packing. 提出了較為快速與穩定的預估方法，利用每一次的當前箱子的狀況，配合高度圖，估計空間的利用，以及決策擺放的方式。然而使用等高圖來觀察當下的狀況，還是有一些潛藏的限制被忽略掉，例如:物品之間擺放的關係等，這個是不利於 DRL 的訓練。

優化 DRL 的 PCT

因為作者在 2021 年提出 DRL 的做法，但是他也提到 DRL 只考慮物體到達的順序，並沒有考慮到物品之間的關係，所以在這篇論文裡面使用 Packing Configuration Tree 的方法，讓 DRL 在訓練的時候，除了考慮到物品到達的順序之外，也需要考慮到每個物品之間的擺放關係。

Packing Configuration Tree
Packing Configuration Tree (PCT)，是針對當前可放置的空間，找到左下角的點位，從這些候選點位以及當前的物品生長出一棵樹，如下圖。

為了好說明，先以 2D 的平面做說明，$t$ 代表的是時間點，從 $t=0$ 的時間點可以看到，初始的是一個空的 Bin ，從現在的空間找到左下角的候選點為 Tree 的根節點，此時來了一個 Item0，將 Item0 對齊空箱的左下角擺放，此時樹的根節點擺放的就會是 Item0 這個物品。在 $t=1$ 針對 Item0 的長與寬，找到兩個左下角的候選點，以兩點為這棵樹的葉節點，這時來了 Item1 將此物品放入一個恰當的位置，並將此節點的內容換成 Item1。以此類推，最後可以得到一顆可以代表物品關係的樹，稱為 Packing Configuration Tree。
Tree representation
要怎麼表示這一棵樹呢? 論文中提到，是將目前的 State 利用 Graph Neural Network (GNN) 進行 Encode，將每一個候選點轉換成節點。那要怎麼表示點與點之間的關係呢? 其中又使用了 Graph Attention Network (GAT)，在 GNN 裡面加入的 Attention 的機制，使每個節點都可以表達彼此的關係。
Leaf Node Selection
葉節點會怎麼選擇呢? 由於葉節點隨著 PCT 隨著時間 $t$ 不斷增長而變化，所以加上了 Attention，透過前幾次的變化來表示 Node 之間的關係。決策的時候其實是透過 Softmax 輸出所有候選點的機率分布，再與 PCT 做配合，選擇更適合的 Node 將物品擺放進去。
Training with Deep reinforcement learning
在這篇論文中，所使用的強化學習演算法為 Actor Critic using Kronecker-Factored Trust Region(ACKTR)，是一個經過優化的 Actor-Critic 的演算法，其目的是更有效地從樣本中學習有效資訊，減少對樣本量的需求。而訓練這個網路，需要以下資訊。
1. State：有物品的大小資訊，可以擺放的位置資訊，與可放置物品的葉節點，並且這個節點是要滿足實際的限制。
2. Action：傳統的 DRL 大多是都使用在離散的空間，決定該物體要擺放的位置，但是現在改用 PCT 的葉節點進行擴展，所以作者發現可以使用在連續的空間使用，並且不會因為離散空間改為連續空間，而讓效能有所影響。
3. Transition：Transition 是從當前的決策 $\pi$ 與取樣的機率分布共同產生的，然後再轉換成均勻分布，根據這個分布進行採樣，而這個均勻分布會即時產生，用這個分布進行採樣增加模型的泛化。
4. Reward：獎勵的計算，如果可以順利的將物品插入 PCT 的葉節點中，會給予對應的獎勵，如果 reward=0 就代表已經沒有空間可以放入接下來的物品，以此代表此輪任務的結束。而在設計獎勵的時候，會依照實際的狀況進行調整，比如要定義甚麼是結束，若是可以將物品順利放進去，要回饋幾分。

實驗結果

在實驗的過程中，選定了三種不同限制的實驗場域分別為：setting1、setting2 與 setting3，在這三種場域中對演算法做不同的比較。

PCT 加上不同 Leaf node 生成方法與不同 Heuristic 演算法處理這個任務的比較結果，如下表。可以發現使用 PCT 的表現皆比啟發式也算法好，而不同的 Leaf node 生成，會需要依照場域實際的限制與狀況來選擇。
此表是證明 Tree representation 在這個任務上的重要性，PointNet 是有使用 Node 的方式表示空間的訊息，但是沒有使用 Tree representation；Ptr-Net 是有使用 Tree representation 但是沒有使用 Graph 與 GAT 的機制；PCT($\tau/B$) 是使用 Tree representation 與 DRL 訓練，但是移除 Tree represeantation 裡面的所有節點。從這表格可以知道，有使用節點或是 Tree representation 的表現其實已經不錯，但是使用 Graph 與 GAT 的機制，是可以更有效表達節點中的關係，並且達到更好的表現，由此可以證明在 3D-BPP的任務中，PCT 是重要的關鍵。
論文有提到，因為改用 PCT 所以可以使用在連續的動作空間上，下表比較了 DRL 與 Heuristic 在連續空間上的結果，可以發現在連續空間，DRL 的表現優於啟發式演算法，在不同的場域或不同的限制下，需要選擇不同的葉節點生成方式。

總結

作者在 ICLR 提出的論文已經證實了 DRL 可以有效的解決 Online 3D-BPP 的問題，但同時也發現單純使用 DRL 其實是會忽略掉一些限制，所以又提出了 PCT 的方法，將 Tree representation、Graph 跟 Attention 的概念加入，讓輸入進 DRL 的 State 除了可以考慮物品的大小，同時也可以考慮物品之間的關係，來提升裝箱的空間使用率。實作的過程中，大多分為兩種一種是離散空間一種是連續空間，改使用 PCT 讓連續空間的 BPP 也可以被解決。當然場域也是很重要的選擇條件之一，不同的場域會有不同的限制，不管是箱子或是的大小，也可能是硬體設備上的限制，在選擇方法的時候，必須考慮到實際場域的狀況，再來選擇最適合的演算法喔。

（撰稿工程師：魏旻柔）