AC-HAPE3D：基于強(qiáng)化學(xué)習(xí)的異形填充算法

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

AC-HAPE3D：基于強(qiáng)化學(xué)習(xí)的異形填充算法

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

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

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

異形填充；啟發(fā)式算法；體素；強(qiáng)化學(xué)習(xí)；三維打印

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

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

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

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

1 相關(guān)工作

3DIP問(wèn)題最終歸結(jié)為組合優(yōu)化問(wèn)題，組合優(yōu)化問(wèn)題常見(jiàn)的解法在對(duì)3DIP的研究中也都有出現(xiàn)，如啟發(fā)式算法、設(shè)計(jì)數(shù)學(xué)模型等等，也有專門的異形填充算法，如臨界多邊形(no-fit polygon，NFP)方法。

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

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

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

在3DIP中，近期的研究并沒(méi)有基于強(qiáng)化學(xué)習(xí)的。但在3D-BPP中，已經(jīng)有了一些研究，VERMA等[18]提出基于強(qiáng)化學(xué)習(xí)的PackMan算法，用于解決在線的3D-BPP——貨物并未預(yù)先給出，而是每次給出一個(gè)，該算法為當(dāng)前狀態(tài)計(jì)算出潛在位置作為動(dòng)作，用DQN方法來(lái)學(xué)習(xí)策略-價(jià)值函數(shù)進(jìn)行決策，其結(jié)果相較于一些經(jīng)典方法有顯著的提升。ZHANG等[19]提出了Attend2Pack方法，用于離線的2D-BPP和3D-BPP，并將動(dòng)作空間分解為了選擇貨物和決定貨物的位置和朝向，用多代理強(qiáng)化學(xué)習(xí)來(lái)解決，其結(jié)果相較于同期方法有著顯著的優(yōu)勢(shì)。可以看到強(qiáng)化學(xué)習(xí)在3D-BPP中已經(jīng)有運(yùn)用且得到了較好的結(jié)果，而本文探索了強(qiáng)化學(xué)習(xí)在3DIP上的應(yīng)用方法。

上述算法中，啟發(fā)式算法和設(shè)計(jì)數(shù)學(xué)模型的方法都可以得到較好的結(jié)果，但同時(shí)計(jì)算時(shí)間長(zhǎng)，從幾十分鐘到幾十小時(shí)不等。而基于NFP的方法并不能得到好的結(jié)果。基于強(qiáng)化學(xué)習(xí)的方法在3D-BPP中得到了較好的結(jié)果，尚無(wú)在3DIP中的嘗試。

2 HAPE3D算法和Actor-Critic方法

2.1 基于最小化勢(shì)能的啟發(fā)式算法

基于最小化勢(shì)能的啟發(fā)式算法(heuristic algorithm based on the principle of minimum total potential energy，HAPE3D)[8]基于最小化勢(shì)能的原則，按一定順序?qū)⒍噙呅窝b入容器中。由于其計(jì)算流程簡(jiǎn)單直接，效果也比較好，而且可以支持任意形狀多邊形以及有限數(shù)量的旋轉(zhuǎn)，因此選擇該算法作為本文強(qiáng)化學(xué)習(xí)算法的基礎(chǔ)，同時(shí)給出在算法實(shí)現(xiàn)上做出的優(yōu)化。

2.1.1 算法流程

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

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

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

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

步驟4. 在可行的打包點(diǎn)，即未在相交的點(diǎn)上，計(jì)算對(duì)應(yīng)的重心高度，其重心高度最小的就是最優(yōu)的點(diǎn)，可將這個(gè)多面體就放置在這個(gè)點(diǎn)上；

步驟5. 因?yàn)榇虬c(diǎn)是離散的分布在容器內(nèi)，會(huì)導(dǎo)致多面體之間以及多面體和容器之間產(chǎn)生間隙，本文提出了一種間隙消除算法，來(lái)最后確定多面體的位置；

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

2.1.2 實(shí)現(xiàn)優(yōu)化

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

HAPE3D算法還能夠支持并行優(yōu)化。在為每個(gè)不同旋轉(zhuǎn)的多面體確定打包點(diǎn)的時(shí)候，可以將每個(gè)旋轉(zhuǎn)所對(duì)應(yīng)的流程進(jìn)行并行計(jì)算，將每個(gè)計(jì)算的結(jié)果保存在數(shù)組中，待所有計(jì)算都結(jié)束后，再?gòu)闹羞x出重心最低的作為結(jié)果。

2.2 Actor-Critic方法簡(jiǎn)介

強(qiáng)化學(xué)習(xí)的一個(gè)經(jīng)典方法是Actor-Critic方法[20]，其是基于策略的方法，直接學(xué)習(xí)每個(gè)動(dòng)作的概率，依據(jù)概率選擇動(dòng)作。

SUTTON和BARTO[21]證明了策略梯度定理，因此可以通過(guò)梯度上升的方法來(lái)求得最大值。在Actor-Critic方法中，利用價(jià)值函數(shù)來(lái)指導(dǎo)策略函數(shù)的參數(shù)更新，即設(shè)一個(gè)可微分的參數(shù)化價(jià)值函數(shù)為

更新參數(shù)和為

其中，和為學(xué)習(xí)率。

3 AC-HAPE3D基于強(qiáng)化學(xué)習(xí)的異形填充

3.1 問(wèn)題建模

3.1.1 狀態(tài)空間

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

3.1.2 動(dòng)作空間

動(dòng)作是指選擇下一個(gè)要打包的多面體，隨后選定的多面體將通過(guò)HAPE3D算法得到對(duì)應(yīng)的位置和旋轉(zhuǎn)，并被移入到已打包的序列中。在當(dāng)前狀態(tài)下，可以采取的動(dòng)作由未打包的多面體決定，動(dòng)作和未打包的多面體索引是一一對(duì)應(yīng)的，即動(dòng)作空間為={1,2,···,a}，每個(gè)動(dòng)作就表示選擇了對(duì)應(yīng)索引的多面體。

3.1.3 獎(jiǎng)勵(lì)設(shè)計(jì)

在3DIP中，最終目標(biāo)是使得打包的高度最小，即使得終止?fàn)顟B(tài)下的高度h最小。設(shè)每個(gè)時(shí)間步狀態(tài)對(duì)應(yīng)的高度為h，+1時(shí)刻狀態(tài)的高度相對(duì)于上一次高度的變化量為Δh+1=h+1-h，該變化量的相反數(shù)就作為本次動(dòng)作所帶來(lái)的獎(jiǎng)勵(lì)，即R=-Δh。顯然，在該獎(jiǎng)勵(lì)函數(shù)下最大化回報(bào)，就等同于最小化高度。

3.2 基于Actor-Critic強(qiáng)化學(xué)習(xí)模型的異形填充算法AC-HAPE3D

本文選擇Actor-Critic[20]方法作為強(qiáng)化學(xué)習(xí)框架，考慮到狀態(tài)信息的復(fù)雜性，采用神經(jīng)網(wǎng)絡(luò)的形式來(lái)表示策略函數(shù)和價(jià)值函數(shù)。同時(shí)限定多面體數(shù)量最多為50，那么輸入的多面體體素網(wǎng)格和體積數(shù)量也最多為50，而當(dāng)環(huán)境中的多面體數(shù)量不足50個(gè)或某些索引的多面體已經(jīng)被打包時(shí)，可用0將其填充到50個(gè)，并用一個(gè)布爾值數(shù)組來(lái)表示非填充值，該數(shù)組稱為遮罩?jǐn)?shù)組。

3.2.1 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

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

圖1 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

輸入接受50個(gè)多面體體素網(wǎng)格，但依據(jù)遮罩信息，其中存在不需要參與運(yùn)算的部分，因此用一個(gè)長(zhǎng)短期記憶(long short-term memory，LSTM)層[21]來(lái)處理。LSTM層是循環(huán)計(jì)算的，其輸入是一個(gè)二維張量，第一維稱為時(shí)間步，第二維是特征值。可在時(shí)間步上循環(huán)計(jì)算，每次將當(dāng)前時(shí)間步的特征值以及上一時(shí)間步的輸出進(jìn)行特定的運(yùn)算，得到當(dāng)前時(shí)間步的輸出，將最后一個(gè)時(shí)間步輸出的一部分作為L(zhǎng)STM層的輸出。在循環(huán)中，如果對(duì)應(yīng)的遮罩值為假，則直接將上一時(shí)間步的輸出作為這一時(shí)間步的輸出，達(dá)到跳過(guò)這一時(shí)間步的效果。這樣可通過(guò)LSTM層和遮罩信息處理狀態(tài)信息中變長(zhǎng)的部分。

3.2.2 損失函數(shù)設(shè)計(jì)

用神經(jīng)網(wǎng)絡(luò)來(lái)擬合價(jià)值函數(shù)和策略函數(shù)，需要分別對(duì)這2個(gè)函數(shù)計(jì)算損失。

價(jià)值函數(shù)的損失采用Huber損失函數(shù)[23]進(jìn)行計(jì)算，即

為每個(gè)時(shí)間步的價(jià)值計(jì)算Huber損失，求和作為價(jià)值函數(shù)的損失。

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

策略函數(shù)返回的是選擇動(dòng)作的概率，使用log函數(shù)會(huì)使得損失對(duì)小概率的動(dòng)作更加敏感，對(duì)每個(gè)時(shí)間步所采取的動(dòng)作計(jì)算損失，求和作為策略函數(shù)的損失。

神經(jīng)網(wǎng)絡(luò)的損失則為上述2個(gè)損失之和，即

4 實(shí)驗(yàn)與分析

網(wǎng)絡(luò)訓(xùn)練在CPU為i7-6700K、GPU為GTX1080以及內(nèi)存16 GB的設(shè)備上進(jìn)行。使用文獻(xiàn)[8]中的數(shù)據(jù)集，即下文中的L2015，作為訓(xùn)練集，容器的長(zhǎng)寬均為20，為了減少訓(xùn)練所需的時(shí)間，每個(gè)多面體的個(gè)數(shù)減少到原本的四分之一，本文使用Adam優(yōu)化器，學(xué)習(xí)率設(shè)為0.001，以此進(jìn)行訓(xùn)練。在訓(xùn)練了660個(gè)回合后，得到的打包結(jié)果高度為10.6，作為參考HAPE3D算法在訓(xùn)練集上得到的結(jié)果為11。后面將用AC-HAPE3D代表本文方法。

此外，通過(guò)移除模型中的策略函數(shù)輸出的Softmax層以及價(jià)值函數(shù)，可將模型輸出轉(zhuǎn)換為直接輸出每個(gè)行動(dòng)的價(jià)值，且貪心地選擇預(yù)測(cè)價(jià)值最高的行動(dòng)，記為A-HAPE3D模型。此時(shí)損失簡(jiǎn)單地用Huber函數(shù)計(jì)算真實(shí)值和預(yù)測(cè)值的偏差。在同樣的訓(xùn)練集和優(yōu)化器下，訓(xùn)練1 000個(gè)回合后得到結(jié)果為11.4。

4.1 異形填充實(shí)驗(yàn)

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

第1個(gè)實(shí)驗(yàn)在數(shù)據(jù)集L2015上進(jìn)行，包含1個(gè)測(cè)試，打包結(jié)果如圖2所示，與其他算法的比較見(jiàn)表1。

圖2 L2015打包結(jié)果

表1 L2015結(jié)果比較

第2個(gè)實(shí)驗(yàn)在數(shù)據(jù)集S2004上進(jìn)行，包含4個(gè)測(cè)試，打包結(jié)果如圖3所示，與其他算法的比較見(jiàn)表2～表4。

第3個(gè)實(shí)驗(yàn)A2018和第4個(gè)實(shí)驗(yàn)Spheres的實(shí)驗(yàn)結(jié)果如圖4所示。

第5個(gè)實(shí)驗(yàn)M2000的實(shí)驗(yàn)結(jié)果如圖5所示。

實(shí)驗(yàn)3，4，5的打包耗時(shí)、高度和填充率見(jiàn)表5。

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

首先分析數(shù)據(jù)集L2015和S2004上的實(shí)驗(yàn)數(shù)據(jù)。

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

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

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

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

表4 S2004結(jié)果耗時(shí)比較(s)

圖4 A2018和Spheres的打包結(jié)果

圖5 M2000的打包結(jié)果((a)測(cè)試1～10個(gè)長(zhǎng)方體；(b)測(cè)試2～20個(gè)長(zhǎng)方體；(c)測(cè)試3～30個(gè)長(zhǎng)方體)

表5 實(shí)驗(yàn)3，4，5的打包耗時(shí)、高度和填充率

對(duì)比HAPE3D+SA，在表1和表2的前3個(gè)測(cè)試中，本文算法在打包高度上稍差一些。但在表2的第4個(gè)測(cè)試中，本文算法的打包高度優(yōu)于HAPE3D+SA，并且觀察表2可以發(fā)現(xiàn)，隨著多面體數(shù)量增加，本文算法和HAPE3D+SA的差距逐漸減小到超過(guò)HAPE3D+SA。而結(jié)合表1和表4的數(shù)據(jù)來(lái)看，本文算法在耗時(shí)上遠(yuǎn)優(yōu)于HAPE3D+SA，一般低2到3個(gè)數(shù)量級(jí)。

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

A-HAPE3D是在本文算法基礎(chǔ)上去除了Critic部分得到，表1和表2均表明，本文算法的打包高度都優(yōu)于A-HAPE3D，并且隨著多面體數(shù)量增加優(yōu)勢(shì)越發(fā)明顯。而表14則意味著由于采用了相近的網(wǎng)絡(luò)結(jié)構(gòu)和計(jì)算流程，兩者耗時(shí)比較接近。

在A2018，Spheres和M2000數(shù)據(jù)集上的結(jié)果展示了本文算法在實(shí)際應(yīng)用中，以及在不同形狀的多面體上的效果。從表5中可以看到，在M2000數(shù)據(jù)集上，本文算法在長(zhǎng)方體數(shù)量較少且都體積較大時(shí)可以得到接近最優(yōu)解的結(jié)果，但隨著長(zhǎng)方體數(shù)量增加以及小體積長(zhǎng)方體的出現(xiàn)，本文算法得到的結(jié)果逐漸變差。

綜合來(lái)看，盡管本文算法只在一個(gè)較小的訓(xùn)練集上進(jìn)行訓(xùn)練，但在數(shù)據(jù)集L2015和S2004上都能得到較好結(jié)果，也能夠成功運(yùn)用于區(qū)別較大的數(shù)據(jù)集上，說(shuō)明本文神經(jīng)網(wǎng)絡(luò)的泛用性是比較好的。

5 結(jié)束語(yǔ)

本文對(duì)強(qiáng)化學(xué)習(xí)在3DIP上的應(yīng)用進(jìn)行了探索和實(shí)現(xiàn)。首先介紹了近期的3DIP解決方案，簡(jiǎn)單分析了其優(yōu)缺點(diǎn)，然后介紹與本文新算法相關(guān)的基礎(chǔ)知識(shí)HAPE3D算法和Actor-Critic算法，之后提出了新算法AC-HAPE3D，并在5個(gè)數(shù)據(jù)集上驗(yàn)證了本文算法的有效性。本文算法盡管在5個(gè)數(shù)據(jù)集上均取得了一定的結(jié)果，但因神經(jīng)網(wǎng)絡(luò)架構(gòu)對(duì)輸出進(jìn)行遮罩會(huì)使得神經(jīng)網(wǎng)絡(luò)在大的數(shù)據(jù)集上較難收斂，同時(shí)2個(gè)LSTM節(jié)點(diǎn)的設(shè)計(jì)也使網(wǎng)絡(luò)的計(jì)算性能較差。未來(lái)可以考慮進(jìn)一步優(yōu)化神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，嘗試避免在輸出上使用遮罩，同時(shí)可以嘗試通過(guò)合并LSTM節(jié)點(diǎn)等方法來(lái)優(yōu)化網(wǎng)絡(luò)的性能。

[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-)，男，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：347495867@qq.com

李桂清(1966-)，男，教授，博士。主要研究方向?yàn)閿?shù)字幾何處理與圖像編輯。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