AC-HAPE3D：基于強化學習的異形填充算法

朱鵬輝，袁宏濤，聶勇偉，李桂清

AC-HAPE3D：基于強化學習的異形填充算法

朱鵬輝，袁宏濤，聶勇偉，李桂清

(華南理工大學計算機科學與工程學院，廣東 廣州 510006)

在3D打印、快遞物流等領域，需要將形狀各異的零件或貨物在限定的空間中擺放，稱為異形填充。給出一種擺放方案，以便將盡可能多的多面體放入給定容器；或者一批物體緊密地擺放，使得占用體積最小，則稱為異形填充問題。這是個NP問題，很難高效求解?；诖?，研究在一個可變維度的三維容器內擺放給定的一組多面體，使得打包后容器的可變維度最小。并提出一個基于強化學習的算法AC-HAPE3D，利用啟發式算法HAPE3D將問題建模為馬爾可夫過程，再利用基于策略的強化學習方法Actor-Critic進行學習。同時用體素來表示容器和多面體，從而簡化狀態信息的表達，并用神經網絡表示價值函數和策略函；為了解決狀態信息長度以及動作空間可變的問題，采取遮罩的方法來屏蔽部分輸入和輸出，并且引入LSTM來處理變長的狀態信息。在5個不同的數據集進行的實驗表明算法能夠取得較好的結果。

異形填充；啟發式算法；體素；強化學習；三維打印

三維集裝優化問題作為一個經典的組合優化問題，已經有了很長時間研究歷史和廣泛的應用場景。早期的研究關注解決交通運輸中貨物運載的優化，其目標要么是在長方體形狀的貨箱中裝入盡可能多的貨物，要么是固定長方體中裝入盡可能高價值的貨物，這樣的問題稱為三維集裝優化問題(3D bin packing problem，3D-BPP)[1]。MARTELLO等[1]對這個問題進行了細致的研究，斷定其是一個多項式復雜程度的非確定性(non-deterministic polynomial，NP)問題，并給出了其下界和精確求解算法。此外，也有一些工作[2-4]用啟發式算法來求得近似解。

當貨物的形狀不再是長方體，而是任意的幾何形狀時，問題就成了三維異形填充(3D irregular packing，3DIP)。其應用場景更為復雜，還經常伴隨有額外約束。如，在3D打印中需要將要打印的零件在工作臺上進行布局，由于3D打印按層構建的方式，對于零件之間的距離、堆疊都有限制，；在電商行業中，將商品裝入快遞箱中也需要考慮到貨物密度以及用緩沖物填充空隙，這些問題均可以描述為3DIP。

3DIP問題根據優化的目標和約束條件分為不同種類。ARAúJO等[5]依照問題的維度(dimensionality，D)、優化目標(criteria，C)、容器類型(build，B)和問題特性(attributes，A)進行分類?；诖?，本文所研究的問題類型為3/Si/Oo/A，即三維，單容器一個維度大小可變，目標是使得可變維度的大小最小，無額外約束，具體描述如下：

此類型的3DIP問題出現在基于選擇性激光燒結(selective laser sintering，SLS)的3D打印技術中。在這種情況下，容器的高度一般不是無限的但是足夠長，可以視為可變的維度，同時對于打印部件沒有諸如支撐結構之類的要求，自由度很高，此時最小化高度即為最小化材料的消耗，因此存在3DIP問題。

1 相關工作

3DIP問題最終歸結為組合優化問題，組合優化問題常見的解法在對3DIP的研究中也都有出現，如啟發式算法、設計數學模型等等，也有專門的異形填充算法，如臨界多邊形(no-fit polygon，NFP)方法。

很多早期的研究采用的是啟發式算法，如采用遺傳算法和模擬退火算法[6-7]。文獻[6]為SLS設計了一個基于遺傳算法的方法，即在“染色體”上編碼了打印部件的順序和朝向，依據上述信息嘗試放置部件，再通過遺傳算法來搜索更優的結果。LIU等[8]提出了基于最小化勢能的啟發式算法(heuristic algorithm based on the principle of minimum total potential energy，HAPE3D)，首先在容器中均勻地放置打包點，并按一定順序為每個多面體找出勢能最小的位置。WANG和HAUSER[9]為機器人自動裝貨提供了一個高度圖最小化(heightmap minimization，HM)啟發式算法，考慮了貨物放置時的穩定性和可操作性，為每個候選的變換計算貨箱內的高度圖，再用變換和高度圖計算分數，算法結果傾向于穩定，且可操作性強。WU等[10]按照可變尺寸的三維不規則容器、可變尺寸的三維長方體容器和單個容器，將3DIP分解為3個問題，建立了每個子問題的數學模型，并提出了三階段啟發式算法，在真實的隨機實例上驗證了算法的有效性。

通過數學模型來解決3DIP的方法，最早在文獻[11]中提出。其通過將凹多面體分解為凸多面體表示，在其提出的Phi函數的基礎上，構造出了3DIP的數學模型，并提供了一個能找到全局最優解的方法，但該方法需要將凹多面體提前分解為凸多面體，不支持旋轉，同時計算耗時大，因此其通過提供一些預定義的凸多面體，將凹多面體近似地分解為這些凸多面體，提供了一個找到近似解的方法。WOLCZYK[12]使用深度學習實現了基于Phi函數的局部解算器，自動梯度計算可以與GPU并行計算，從而加速計算。STOYAN等[13]提出了新的Quasi-Phi函數，為打包橢圓提供了新的數學模型。ROMANOVA等[14]在Quasi-Phi函數的方法上進行了擴展，將其從只能處理橢圓擴展到了能處理任意凹多面體上，把3DIP問題建模為了非線性優化問題，并通過非線性優化求解器直接求解，且支持任意的移動和旋轉。但該算法仍然需要將多面體分解為凸多面體才能計算，且很難加入新的約束，應用范圍有限。

臨界多邊形(no-fit polygon，NFP)最早在文獻[15]中提出，用于解決二維的異形填充問題。NFP可描述出一個多邊形相較于另一個多邊形，在空間中放置的區域，但由于計算開銷大且計算難度高，在3DIP中的應用較少。為了降低NFP的計算開銷和難度，VERKHOTUROV等[16]提出計算基于體素的NFP，之后在選擇多面體的放置位置時，也將容器劃分為體素，再深度優先地搜索可用的位置。該算法最終在打包高度和耗時上表現的都較差。LAMAS-FERNANDEZ等[17]提出了臨界體素(no-fit voxel，NFV)的概念，基于NFV的離散表示提出了一種構造性算法和一種迭代局部搜索，以及2種在包含重疊的解空間上搜索的元啟發式技術，有效地解決了3D打印行業中的復雜幾何體的真實實例，證明了使用不同精度的體素表示更適合現實問題。

在3DIP中，近期的研究并沒有基于強化學習的。但在3D-BPP中，已經有了一些研究，VERMA等[18]提出基于強化學習的PackMan算法，用于解決在線的3D-BPP——貨物并未預先給出，而是每次給出一個，該算法為當前狀態計算出潛在位置作為動作，用DQN方法來學習策略-價值函數進行決策，其結果相較于一些經典方法有顯著的提升。ZHANG等[19]提出了Attend2Pack方法，用于離線的2D-BPP和3D-BPP，并將動作空間分解為了選擇貨物和決定貨物的位置和朝向，用多代理強化學習來解決，其結果相較于同期方法有著顯著的優勢?？梢钥吹綇娀瘜W習在3D-BPP中已經有運用且得到了較好的結果，而本文探索了強化學習在3DIP上的應用方法。

上述算法中，啟發式算法和設計數學模型的方法都可以得到較好的結果，但同時計算時間長，從幾十分鐘到幾十小時不等。而基于NFP的方法并不能得到好的結果?；趶娀瘜W習的方法在3D-BPP中得到了較好的結果，尚無在3DIP中的嘗試。

2 HAPE3D算法和Actor-Critic方法

2.1 基于最小化勢能的啟發式算法

基于最小化勢能的啟發式算法(heuristic algorithm based on the principle of minimum total potential energy，HAPE3D)[8]基于最小化勢能的原則，按一定順序將多邊形裝入容器中。由于其計算流程簡單直接，效果也比較好，而且可以支持任意形狀多邊形以及有限數量的旋轉，因此選擇該算法作為本文強化學習算法的基礎，同時給出在算法實現上做出的優化。

2.1.1 算法流程

本文給出的HAPE3D算法步驟如下：

步驟1. 將所有多面體按照體積降序排序，并依次將多面體打包入容器中；

步驟2. 在容器中，按照給定的間隔，在水平和豎直方向上，均勻地放置打包點，將這個間隔稱為打包間距(packing point distance，PPD)，打包點的總數量設為打包數(packing point number，PPN)；

步驟3. 將當前多面體，依次放到各個打包點上，用基于閾值的射線相交算法 (threshold-based ray-crossing algorithm，TBRC)檢查是否放在了可行的打包點上；

步驟4. 在可行的打包點，即未在相交的點上，計算對應的重心高度，其重心高度最小的就是最優的點，可將這個多面體就放置在這個點上；

步驟5. 因為打包點是離散的分布在容器內，會導致多面體之間以及多面體和容器之間產生間隙，本文提出了一種間隙消除算法，來最后確定多面體的位置；

步驟6. 處理完所有多面體，算法結束。

2.1.2 實現優化

HAPE3D算法的主要計算瓶頸在于尋找可行點，即需要進行大量的多面體分離測試，因此可以通過減少分離測試次數進行加速。先進行包圍盒相交測試，在確定相交時進行進一步測試。在容器內已有大量多面體時，可以快速地過濾掉大部分不相交的多面體。

HAPE3D算法還能夠支持并行優化。在為每個不同旋轉的多面體確定打包點的時候，可以將每個旋轉所對應的流程進行并行計算，將每個計算的結果保存在數組中，待所有計算都結束后，再從中選出重心最低的作為結果。

2.2 Actor-Critic方法簡介

強化學習的一個經典方法是Actor-Critic方法[20]，其是基于策略的方法，直接學習每個動作的概率，依據概率選擇動作。

SUTTON和BARTO[21]證明了策略梯度定理，因此可以通過梯度上升的方法來求得最大值。在Actor-Critic方法中，利用價值函數來指導策略函數的參數更新，即設一個可微分的參數化價值函數為

更新參數和為

其中，和為學習率。

3 AC-HAPE3D基于強化學習的異形填充

3.1 問題建模

3.1.1 狀態空間

在給定了容器和多面體的情況下，狀態可以用J和J來唯一確定，但僅靠索引來描述狀態無法全面刻畫出多面體在容器中占位的實際分布，也無法表示剩余的多面體的幾何特征，在用Actor-Critic方法學習價值函數和策略函數時，難以訓練出有較強泛化能力的模型。因此實際具體應用時，除了J與J，還引入了如下信息: 容器體素網格，容器參數，未打包多面體的體素網格和體積。容器體素網格通過體素化容器內已經打包的多面體獲得，記為V。當前所有多面體頂點坐標中最大值記為高度h，容器的長寬固定為和，已打包多面體的總體積記為V，則容器參數為C={,,h,V}。

3.1.2 動作空間

動作是指選擇下一個要打包的多面體，隨后選定的多面體將通過HAPE3D算法得到對應的位置和旋轉，并被移入到已打包的序列中。在當前狀態下，可以采取的動作由未打包的多面體決定，動作和未打包的多面體索引是一一對應的，即動作空間為={1,2,···,a}，每個動作就表示選擇了對應索引的多面體。

3.1.3 獎勵設計

在3DIP中，最終目標是使得打包的高度最小，即使得終止狀態下的高度h最小。設每個時間步狀態對應的高度為h，+1時刻狀態的高度相對于上一次高度的變化量為Δh+1=h+1-h，該變化量的相反數就作為本次動作所帶來的獎勵，即R=-Δh。顯然，在該獎勵函數下最大化回報，就等同于最小化高度。

3.2 基于Actor-Critic強化學習模型的異形填充算法AC-HAPE3D

本文選擇Actor-Critic[20]方法作為強化學習框架，考慮到狀態信息的復雜性，采用神經網絡的形式來表示策略函數和價值函數。同時限定多面體數量最多為50，那么輸入的多面體體素網格和體積數量也最多為50，而當環境中的多面體數量不足50個或某些索引的多面體已經被打包時，可用0將其填充到50個，并用一個布爾值數組來表示非填充值，該數組稱為遮罩數組。

3.2.1 神經網絡結構設計

神經網絡的架構如圖1所示，可以分為輸入層、隱藏層和輸出層：①輸入層為當前狀態中所包含的信息，分為5個，在圖中按序號a)～e)標出，其中a)～d)為對應狀態信息的輸入，而e)是遮罩輸入； ②隱藏層對不同的信息用不同的節點進行特征提取，之后拼接在一起用一個全連接層進行處理并連接到輸出層，其中對體素網格進行特征提取的部分參考了文獻[22]，其用三維卷積完成體素網格的分類任務，本文用作特征提??；③輸出層通過全連接層輸出價值和輸出各個動作概率，在圖中用I)和II)標出，考慮到策略函數和價值函數都接受同樣的輸入，因此可共用同樣的特征提取網絡，即接受相同隱藏層的特征提取結果，再分別通過一個全連接層來獲得不同的輸出。

圖1 神經網絡結構

輸入接受50個多面體體素網格，但依據遮罩信息，其中存在不需要參與運算的部分，因此用一個長短期記憶(long short-term memory，LSTM)層[21]來處理。LSTM層是循環計算的，其輸入是一個二維張量，第一維稱為時間步，第二維是特征值?？稍跁r間步上循環計算，每次將當前時間步的特征值以及上一時間步的輸出進行特定的運算，得到當前時間步的輸出，將最后一個時間步輸出的一部分作為LSTM層的輸出。在循環中，如果對應的遮罩值為假，則直接將上一時間步的輸出作為這一時間步的輸出，達到跳過這一時間步的效果。這樣可通過LSTM層和遮罩信息處理狀態信息中變長的部分。

3.2.2 損失函數設計

用神經網絡來擬合價值函數和策略函數，需要分別對這2個函數計算損失。

價值函數的損失采用Huber損失函數[23]進行計算，即

為每個時間步的價值計算Huber損失，求和作為價值函數的損失。

策略函數的損失按照Actor-Critic方法的更新方式為

策略函數返回的是選擇動作的概率，使用log函數會使得損失對小概率的動作更加敏感，對每個時間步所采取的動作計算損失，求和作為策略函數的損失。

神經網絡的損失則為上述2個損失之和，即

4 實驗與分析

網絡訓練在CPU為i7-6700K、GPU為GTX1080以及內存16 GB的設備上進行。使用文獻[8]中的數據集，即下文中的L2015，作為訓練集，容器的長寬均為20，為了減少訓練所需的時間，每個多面體的個數減少到原本的四分之一，本文使用Adam優化器，學習率設為0.001，以此進行訓練。在訓練了660個回合后，得到的打包結果高度為10.6，作為參考HAPE3D算法在訓練集上得到的結果為11。后面將用AC-HAPE3D代表本文方法。

此外，通過移除模型中的策略函數輸出的Softmax層以及價值函數，可將模型輸出轉換為直接輸出每個行動的價值，且貪心地選擇預測價值最高的行動，記為A-HAPE3D模型。此時損失簡單地用Huber函數計算真實值和預測值的偏差。在同樣的訓練集和優化器下，訓練1 000個回合后得到結果為11.4。

4.1 異形填充實驗

實驗在L2015，S2004，A2018和一個只有球形的數據集Spheres以及M2000的5個數據集上分別進行。L2015[8]由5種多面體組成，容器的長寬均是20，共1個測試，其包含36個多面體；S2004[11]由10種多面體組成，容器的長和寬分別為35和30，共5個測試，依次包含20，30，40和50個多面體，每個測試中各種多面體的數量均相同；A2018[5]包含了大量不同的用于3D打印的零件模型，選擇其中9個不同的零件進行打包，容器的長寬分別為285和155；球形數據集Spheres由39個半徑為1，10個半徑為2和一個半徑為5的經緯球模型組成，容器的長和寬均是12；M2000[1]是為3D-BPP設計的測試，模型均為長方體，并選擇了其中Class 9的3個測試，分別由10，20和30個長方體組成，容器長寬均是10，最優解高度均為30，此時容器被完全填充。

第1個實驗在數據集L2015上進行，包含1個測試，打包結果如圖2所示，與其他算法的比較見表1。

圖2 L2015打包結果

表1 L2015結果比較

第2個實驗在數據集S2004上進行，包含4個測試，打包結果如圖3所示，與其他算法的比較見表2～表4。

第3個實驗A2018和第4個實驗Spheres的實驗結果如圖4所示。

第5個實驗M2000的實驗結果如圖5所示。

實驗3，4，5的打包耗時、高度和填充率見表5。

4.2 實驗結果分析

首先分析數據集L2015和S2004上的實驗數據。

從表1和表2可以看出，本文算法在打包高度上顯著優于HAPE3D算法，而且隨著多面體數量增加，優勢也變得更大；綜合表1和表4則表明可知，本文算法要比HAPE3D更耗時。

圖3 S2004打包結果((a)測試1～20個多面體；(b)測試2～30個多面體；(c)測試3～40個多面體；(d)測試4～50個多面體)

表2 S2004結果高度比較(mm)

表3 S2004結果體積比較(mm3)

表4 S2004結果耗時比較(s)

圖4 A2018和Spheres的打包結果

圖5 M2000的打包結果((a)測試1～10個長方體；(b)測試2～20個長方體；(c)測試3～30個長方體)

表5 實驗3，4，5的打包耗時、高度和填充率

對比HAPE3D+SA，在表1和表2的前3個測試中，本文算法在打包高度上稍差一些。但在表2的第4個測試中，本文算法的打包高度優于HAPE3D+SA，并且觀察表2可以發現，隨著多面體數量增加，本文算法和HAPE3D+SA的差距逐漸減小到超過HAPE3D+SA。而結合表1和表4的數據來看，本文算法在耗時上遠優于HAPE3D+SA，一般低2到3個數量級。

表1和表3還表明，本文算法的打包體積一般都R2018大，但隨著多面體數量增加，差距逐漸減小。由于R2018無法加入容器尺寸的約束，本文算法在泛用性上具有一定優勢。此外，表1和表4 表明，本文算法在耗時上明顯優于R2018，一般低2到3個數量級。

A-HAPE3D是在本文算法基礎上去除了Critic部分得到，表1和表2均表明，本文算法的打包高度都優于A-HAPE3D，并且隨著多面體數量增加優勢越發明顯。而表14則意味著由于采用了相近的網絡結構和計算流程，兩者耗時比較接近。

在A2018，Spheres和M2000數據集上的結果展示了本文算法在實際應用中，以及在不同形狀的多面體上的效果。從表5中可以看到，在M2000數據集上，本文算法在長方體數量較少且都體積較大時可以得到接近最優解的結果，但隨著長方體數量增加以及小體積長方體的出現，本文算法得到的結果逐漸變差。

綜合來看，盡管本文算法只在一個較小的訓練集上進行訓練，但在數據集L2015和S2004上都能得到較好結果，也能夠成功運用于區別較大的數據集上，說明本文神經網絡的泛用性是比較好的。

5 結束語

本文對強化學習在3DIP上的應用進行了探索和實現。首先介紹了近期的3DIP解決方案，簡單分析了其優缺點，然后介紹與本文新算法相關的基礎知識HAPE3D算法和Actor-Critic算法，之后提出了新算法AC-HAPE3D，并在5個數據集上驗證了本文算法的有效性。本文算法盡管在5個數據集上均取得了一定的結果，但因神經網絡架構對輸出進行遮罩會使得神經網絡在大的數據集上較難收斂，同時2個LSTM節點的設計也使網絡的計算性能較差。未來可以考慮進一步優化神經網絡的結構，嘗試避免在輸出上使用遮罩，同時可以嘗試通過合并LSTM節點等方法來優化網絡的性能。

[1] MARTELLO S, PISINGER D, VIGO D. The three-dimensional Bin packing problem[J]. Operations Research, 2000, 48(2): 256-267.

[2] CRAINIC T G, PERBOLI G, TADEI R. Extreme point-based heuristics for three-dimensional Bin packing[J]. INFORMS Journal on Computing, 2008, 20(3): 368-384.

[3] FANSLAU T, BORTFELDT A. A tree search algorithm for solving the container loading problem[J]. INFORMS Journal on Computing, 2010, 22(2): 222-235.

[4] LOH K H, GOLDEN B, WASIL E. Solving the one-dimensional Bin packing problem with a weight annealing heuristic[J]. Computers & Operations Research, 2008, 35(7): 2283-2291.

[5] ARAúJO L J P, ?ZCAN E, ATKIN J A D, et al. Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset[J]. International Journal of Production Research, 2019, 57(18): 5920-5934.

[6] IKONEN I, WILLIAM E, et al. Concept for a genetic algorithm for packing three dimensional objects of com- plex shape[C]//The 1st Online Workshop of Soft Computing. Nagoya: Nagoya University, 1996: 211-215.

[7] CAGAN J, DEGENTESH D, YIN S. A simulated annealing- based algorithm using hierarchical models for general three-dimensional component layout[J]. Computer-Aided Design, 1998, 30(10): 781-790.

[8] LIU X, LIU J M, CAO A X, et al. HAPE3D—a new constructive algorithm for the 3D irregular packing problem[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 380-390.

[9] WANG F, HAUSER K. Stable Bin packing of non-convex 3D objects with a robot manipulator[C]//2019 International Conference on Robotics and Automation. New York: IEEE Press, 2019: 8698-8704.

[10] WU H T, LEUNG S C H, SI Y W, et al. Three-stage heuristic algorithm for three-dimensional irregular packing problem[J]. Applied Mathematical Modelling, 2017, 41: 431-444.

[11] STOYAN Y G, GIL M, PANKRATOV A, et al. Packing non-convex polytopes into a parallelepiped[EB/OL]. [2022-05-19]. https://www.researchgate.net/publication/2569811_ Packing_of_Convex_Polytopes_Into_a_Parallelepiped.

[12] WO?CZYK M. Deep learning-based initialization for object packing[J]. Schedae Informaticae, 2018, 27: 9-17.

[13] STOYAN Y, PANKRATOV A, ROMANOVA T. Quasi-phi- functions and optimal packing of ellipses[J]. Journal of Global Optimization, 2016, 65(2): 283-307.

[14] ROMANOVA T, BENNELL J, STOYAN Y, et al. Packing of concave polyhedra with continuous rotations using nonlinear optimisation[J]. European Journal of Operational Research, 2018, 268(1): 37-53.

[15] ART JR R C. An approach to the two dimensional irregular cutting stock problem[D]. Cambridge: Massachusetts Institute of Technology, 1966.

[16] VERKHOTUROV M, PETUNIN A, VERKHOTUROVA G, et al. The 3D object packing problem into a parallelepiped container based on discrete-logical representation[J]. IFAC- PapersOnLine, 2016, 49(12): 1-5.

[17] LAMAS-FERNANDEZ C, BENNELL J A, MARTINEZ- SYKORA A. Voxel-based solution approaches to the three- dimensional irregular packing problem[EB/OL]. (2022-05-04) [2022-05-26]. https://pubsonline.informs.org/doi/abs/10.1287/opre. 2022.2260.

[18] VERMA R, SINGHAL A, KHADILKAR H, et al. A generalized reinforcement learning algorithm for online 3D bin-packing[EB/OJ]. [2022-03-02]. https://arxiv.org/abs/2007. 00463.

[19] ZHANG J W, ZI B, GE X Y. Attend2Pack: Bin packing through deep reinforcement learning with attention[EB/OL]. [2022-06-18]. https://arxiv.org/abs/2107.04333.

[20] BHATNAGAR S, SUTTON R S, GHAVAMZADEH M, et al. Natural actor-critic algorithms[J]. Automatica, 2009, 45(11): 2471-2482.

[21] SUTTON R S, BARTO A G. Reinforcement learning: an introduction[M]. 2nd ed. Cambridge: MIT Press, 2018: 265-279.

[22] MATURANA D, SCHERER S. VoxNet: a 3D Convolutional Neural Network for real-time object recognition[C]//2015 IEEE/RSJ International Conference on Intelligent Robots and Systems. New York: IEEE Press, 2015: 922-928.

[23] HUBER P J. Robust estimation of a location parameter[J]. The Annals of Mathematical Statistics, 1964, 35(1): 73-101.

AC-HAPE3D: an algorithm for irregular packing based on reinforcement learning

ZHU Peng-hui, YUAN Hong-tao, NIE Yong-wei, LI Gui-qing

(School of Computer Science and Engineering, South China University of Technology, Guangzhou Guangdong 510006, China)

In areas such as 3D printing and express logistics, irregular packing results from the need to place parts or goods of different shapes in a defined space. A placement solution could be put forward, allowing as many polyhedra as possible to fit into a given container, or a batch of objects could be placed so closely together that they occupy the smallest volume, which is known as the irregular packing problem. This is an NP problem but is difficult to solve efficiently. This paper undertook the following investigation: placing a given set of polyhedra inside a 3D container with a variable dimension, so that the variable dimension of the packed container could be minimized. We proposed a reinforcement learning based algorithm, AC-HAPE3D. This algorithm could model the problem into a Markov process using the heuristic algorithm HAPE3D, and then utilize the policy-based reinforcement learning method Actor-Critic. We simplified the representation of state information by using voxels to represent containers and polyhedra, and employed neural networks to represent value and policy functions; to address the problem of variable length of state information as well as action space, we adopted a masking approach to masking some of the inputs and outputs, and introduced LSTM to handle variable length of state information. Experiments conducted on five different datasets show that the algorithm can yield good results.

irregular packing; heuristic algorithm; voxel; reinforcement learning; 3-dimensional printing

TP 391

10.11996/JG.j.2095-302X.2022061096

A

2095-302X(2022)06-1096-08

2022-08-02；

：2022-10-20

朱鵬輝(2000-)，男，碩士研究生。主要研究方向為計算機圖形學。E-mail：347495867@qq.com

李桂清(1966-)，男，教授，博士。主要研究方向為數字幾何處理與圖像編輯。E-mail：ligq@scut.edu.cn

2 August，2022；

20October，2022

ZHU Peng-hui (2000-), master student. His main research interest covers computer graphics. E-mail：347495867@qq.com

LI Gui-qing (1966-), professor, Ph.D. His main research interests cover digital geometry processing and image editing. E-mail：ligq@scut.edu.cn