Towards Online 3D Bin Packing: Learning Synergies between Packing and Unpacking via DRL
Authors: Shuai Song
Shuo Yang
Ran Song
Shilei Chu
yibin Li
Wei Zhang
Venue: CoRL 2022 Poster (2022)
Keywords: Bin packing
Robotics
Deep reinforcement learning

Abstract: There is an emerging research interest in addressing the online 3D bin packing problem (3D-BPP), which has a wide range of applications in logistics industry. However, neither heuristic methods nor those based on deep reinforcement learning (DRL) outperform human packers in real logistics scenarios. One important reason is that humans can make corrections after performing inappropriate packing actions by unpacking incorrectly packed items. Inspired by such an unpacking mechanism, we present a DRL-based packing-and-unpacking network (PUN) to learn the synergies between the two actions for the online 3D-BPP. Experimental results demonstrate that PUN achieves the state-of-the-art performance and the supplementary video shows that the system based on PUN can reliably complete the online 3D bin packing task in the real world.

Towards Online 3D Bin Packing: Learning Synergies between Packing and Unpacking via DRL
Shuai Song, Shuo Yang, Ran Song, Shilei Chu, Yibin Li, Wei Zhang"
Shandong University (shuaisongss, shuoyang, slchuj ) @ maii..su..du..cm {ransong, liyb, davidzhang @ @sdu.edu.cn
There an emerging research interest addressing the online 3D bin packing problem (3D-BPP), which has a wide range of applications in logistics industry. However, neither heuristic methods nor those based on deep reinforce- ment learning (DRL.) outperform human packers in real logistics scenarios. One important reason is that humans can make corrections after performing inappro- priate packing actions by unpacking incorrectly packed items. Inspired by such unpacking mechanism, we present a DRL-based macking-and-unpackee (PUN) to learn the synergies between the two actions for the online 3D-BPP. Ex- perimental results demonstrate that PUN achieves the state-of taa---ffthhhteee the-art performance and the supplementary video shows that the system based on PUN reliably complete the online 3D bin packing task in the real world.
Abstract:
network
Keywords: Bin packing, robotics, deep reinforcement learning.
Introduction
The rapid growth of e-commerce has signifi- cantly increased the burden of human packers in logistics warehouses. Thus there is an emerg- ing research interest in developing intelligent robotic systems to replace human labors in the repetitive work [1]. nario, the human packer is asked to pick the items from a running conveyor belt one by one and then pack them into bin with higher space utilization as possible. To solve this task, most researchers formulated it the online 3D bin packing problem BD-BPP) and presented algorithms optimize the bin packing policy [2, 3, 4]. However, as one of the most classic combinatorial optimization problems, the on- line 3D-BPP is notoriously NP-hard [5]. It is nontrivial to find the optimal policy as only one item is observable each time.
Unpacking action
Initial state
typical packing sce-
Synerqies
Final state
Packing action
Figure 1: Illustration of the synergies between packing and unpacking actions. Our method can unpack the in- appropriately placed items and repack them into the to improve the overall space utilization.
Early methods for the bin packing problem mostly focus on designing reasonable bin packing heuristics [6, 7, 8]. Such heuristics are essen- tially hand-designed rules abstracted from the experiences of human packers. Although this is an intuitive way to solve the bin packing task and usually maintains good working efficiency, the expe- riences of human packers algorithms are less likely to find the optimal bin packing policy in various scenarios.
always perfect. Moreover, without learning process, the heuristic
Inspired by the recent advances in deep reinforcement learning (DRL) [9, 10, 11], researchers at- tempt to solve the online 3D-BPP via DRL [12, 13, 14]. Although these methods have achieved promising results in the bin packing task, they neglected the crucial human experience of unpacking when the currently observed item cannot packed into an appropriate position. The ability of un-
Cooresspndiigg author
6th Conference on Robot Learning (CoRI. 2022), Auckland, New Zealand.

---

packing is thus particularly important for the online 3D-BPP, where the agent can only observe one upcoming item and hence less likely learn the optimal bin packing policy.
Therefore, we introduce the unpacking mechanism for the online 3D-BPP as shown in Fig. 1. To learn the synergies between packing and unpacking, propose a macking-and-uupacking network (PUN) based on DRL. Specifically, PUN is a two-branch architecture which generates the packing and the unpacking actions and their corresponding state values. then determines to perform either the packing or the unpacking action based on the state values. Finally, the synergies between packing and unpacking actions are learned via DRL. We also design packing and unpacking heuristics and incorporate them into the DRL framework.
The main contributions of this paper are twofold: 1) introduce the unpacking mechanism for online 3D-BPP and propose to solve with both the packing and unpacking actions; 2) we present PUN to learn the synergies between packing and unpacking actions via DRL in the simulated envi- ronment, seeking for the optimal bin packing policy. And a bin packing system developed based on PUN is demonstrated in the real world.
2 Related Work
Existing methods for the 3D-BPP can be divided into two groups: heuristic and DRL-based methods. We herein briefly review both of them.
Heuristic methods. The 3D bin packing problem (3D-BPP) focuses on packing a set of cubical items into a confined 3D space (e.g. shipping box) with high rate of space utilization [15]. It classic NP-hard optimization problem [5]. The online 3D-BPP assumes that only the current item to be packed is observable while the upcoming items are unknown. Early work mostly de- signed different heuristic algorithms [16, 17] such as Tabu Search [18], First-Fit [19] and Extreme Point-Based Heuristics [7]. The heuristic algorithms are essentially the distillation of the real-world packing experience human packers, which are not always perfect for various scenarios.
DRL-based methods. Recently, DRL has been demonstrated effective to solve combinatorial op- timization problems [20, 21, 22, 23]. Some researchers thus attempted to solve the 3D-BPP using DRL [12, 13, 24, 14, 25]. For example, Zhao et al. [13] formulated the 3D-BPP as constrained Markov decision process and first employed the DRL method to optimize the sequence of the items to be packed into the bin. Verma et al. [24] developed a DRL algorithm to solve the online 3D-BPP for an arbitrary number of bins with various sizes. More recently, Yang et al. [14] made the pri- mary attempts to incorporate the heuristics into the DRL framework for learning more optimal bin packing policy. However, such methods cannot perform comparably well with the human packers.
A neglected human experience is that human packers can unpack some item from the bin if packing the current item difficult. We thus incorporate the unpacking mechanism into the DRL framework which learns the synergies between the packing and the unpacking actions.
Method
In online bin packing task, the items delivered from running conveyor belt one by and then packed into a bin. Only the immediately incoming item is observable. We formulate the bin packing task Markov Decision Process (MDP) [26] subject the state S, the action A, the transition P, and the reward R. We solve the MDP with an end-to-end DRL framework which seeks for policy x(a s (x) to maximize the sum of the expected rewards, expressed as:
J JR
max E, Es
Σ t- (St, dz)
This section provides details of PUN and the implementation of a real-world logistics application.
3.1 Packing-and-Unpacking Network
The architecture of the proposed PUN is illustrated in Fig. 2 and elaborated follows.
State representation. We model the state representation 8; as current configuration of the bin and the current item to be packed. To parameterize the configuration of an L x W H bin,

---

Packing Net
Packing position
Packing-leuristiee predictor
Packing-actor (MLP)
(,tals)
Mp
Packing-critic (MLP)
V (18)
Heightmap
Feature extractor
max
Packing/ Unpacking
Unpacking-critic (MLP)
Vu(s)
M,
Unpucking-actor (MLP)
Unpacking heuristios predictor
II, (H/b))
Item Size
Unpacking Net
Unpacising pesition
Figure 2: Illustration of the proposed PUN for learning synergies between packing and unpacking.
we discrete the state observation of the bin the time as a heightmap H, E Z+Lx where Z+ E [0, H.. The heightmap is I, x W discrete grid and the value at each cell represents the height of the stacked items at that position. The state of the current item n with the size of L X W x map, the 3 channels of which are assigned with the values of b,, Wn and h, respectively (see Fig. 2).
in X wnn f,, is represented
Action definition. We parameterize each action as motion primitive behavior và (e.g. packing or unpacking) executed at the position p projected from cell c of the heightmap representation of the bin configuration:
a = (+,p) P) u/ {pack, unpack), c E H,
Each cell e in the heightmap of the bin configuration corresponds to specific position to execute the packing or unpacking action. We use the left-front-bottom corner of item as its packing or unpacking coordinates. The motion primitive behaviors are defined as below:
Packing: p denotes putting the item at the cell of the grid corresponding to the bin heightmap. We 2D coordinates (In, yr) to represent the position of The action (pack, P(r.....)) denotes that the agent puts the item at the position (In; yn) of the heightmap.
Unpacking: p denotes removing the item from the cell e of the grid corresponding to the bin heightmap. We temporary item buffer to store most B unpacked items. The action (unpack; P(mm-ymm)) denotes that the agent removes the item m from the position (Im Vm) of the heightmap and places the temporary item buffer.
Synergies between packing and unpacking actions. As illustrated in Fig. 2, PUN is designed as a two-branch network to learn the synergies between packing and unpacking. the heightmap of the bin configuration and the sizes of the item, and outputs the motion primitive behavior ei (packing or unpacking) executed at the position projected from a cell of the heightmap. The state input is encoded into features by shared feature extraction module which is implemented with 5 fully-connected layers. Such features are then fed into to the packing and the unpacking networks, respectively.
takes as input
The packing and unpacking branches both consist of three major components: an actor network, a critic network and a heuristic mask predictor. The actor network outputs the probability distribu- tion of the motion primitive behavior (packing and unpacking) with the same resolution as that of the state st The two critic networks predict the state values Vs(5s) and Va(s;) which measure the cumulative reward of taking the two motion primitive behaviors in the state s, at the time respec- tively [27]. The heuristic mask predictors generate the packing and the unpacking masks M, and M,, to estimate valid packing and unpacking positions based on the heuristic rules. The probability distribution output by the actor network modulated by the heuristic mask.
For the state 8, at the time step I, the network outputs two state values (V,( (x))) and two probability distributions (a, st), n. (arls))) corresponding to packing and unpacking actions.

---

Currett iee
Curvent sem
2
Conveyor
pack
Bin
unpack
unpack
pack
Current itm
Current item
pack
Buffer
Step
Step t+1
Step
Step
Step
Figure 3: An example of the synergies between packing and unpacking. Current item indicates the item to be packed the current time step. The serial number on the item indicates the order which to packed.
One action is subject to the motion primitive behavior té and the position The final motion primitive behavior is the one with the highest state value between the two primitive behaviors, which means that the DRL agent will theoretically earn the highest rewards. The position is sampled from the probability distribution corresponding to the final motion primitive behavior.
The synergistic process of packing and unpacking is elaborated as follows. For the item to be packed at the time step t, PUN takes its size and the heightmap of the bin as input to predict the motion primitive behavior 1 and the target position of the bin heightmap. If the packing action is predicted, the agent will pick the item from the conveyor belt and place it the target position and take the next item from the conveyor belt as the item to be packed at the time step t + 1. the unpacking action is predicted, the agent will pick the item m from the target position p and place it into the buffer zone to temporarily store it. The agent will continue predict the packing or unpacking action for the item n at the next time step until packing into the bin. After packing the item n, the item in the temporary buffer will be used as the current item to be packed for predicting the next action. If there are multiple items in the temporary buffer, the agent will select the target item to be packed according the order in which the items (first in last out). Only after all items in the temporary buffer are emptied can the robot select the next item to be packed from the conveyor belt. Fig. 3 shows example of the process of packing and unpacking.
unpacked into the temporary buffer
Heuristics- braristics-based action constraint. We incorporate three heuristic rules into the DRL framework to guide the reinforcement learning. The first one is physics heuristics. defines the actions that lead to failure as invalid actions. For example, the packing actions that pack the items beyond the bin boundaries and the unpacking actions that execute on the positions without items. The second one packing heuristies. It consists of four popular packing heuristic algorithms which are described as follows: The Extreme Point algorithm [7] that calculates all extreme points in the bin and packs item based on extreme point rule. The Empty Maximal Space algorithm [8] that packs item in the position which can produce the largest empty orthogonal spaces in the bin. The First Fit algorithm [19] that packs item in the first feasible position. The Floor Building algorithm [28] that packs item in the lowest feasible position. The last one is unpacking heuristics. Since there are fewer heuristic algorithms for unpacking at present, we design two rules for unpacking. We define the positions of the items on the top layer of the bin (the first rule) and whose volume is less than a certain threshold (the second rule) as the valid positions.
To incorporate the heuristics into the DRL framework, we design two predictors to generate the binary feasibility mask M, indicating the valid and invalid actions. Only the actions that satisfy the heuristics are valid. Next, we use the fcasibility masks to modulate the outputs the packing and unpacking branches [29]. In our DRL framework, the actor network outputs the unnormalized scores I (logits) which are then converted into an action probability distribution by a softmax operation. For the invalid actions, the probability of the invalid actions output by the softmax layer is virtually zero. We consider the action constraint as the renormalized probability distribution 7 (ac(st))
replace their corresponding logits with large negative value -108. Thus
exp(1:)
M, True
(ac (5t) soʃ softmaz(femms (l)))
ΣN exp(ly)
(3)
0,
M: False

---

where N is the number of the valid actions, and
4.
M; True
Seans (l:)
(4)
-100
Mr Folse
Reward function. We design step-wise reward for the bin packing task. contains two parts: the volume utilization ratio vy and the wasted space ratio Tw-- Ta is defined as the ratio of the volume of the items contained in the bin to the total bin volume:
2
Σ 4 x wy x lig
LxW x
Tie is defined as the ratio of the wasted space volume the bin volume and denotes the free space where the items cannot be packed under the current bin state. Fig. 4 shows an example of the wasted spaces highlighted as the red dotted cuboids. We encourage the unpacking action reduce the wasted spaces. The whole reward defined as:
Figure An example wasted spaces.
Rs(St, a, 8(+1) r wrw
(6)
where a is weighting parameter.
3.2 Implementation of Real-world Logistics Application
To validate the actual bin packing perfor- mance, we set up real-world system to de- ploy the policy learned in the simulation.
Robot
On-conveyuu camera
Ont-omtveyoe RGIBO
Ou-bin
System configuration. Fig. 5 shows the developed practical bin packing system. The URS robotic arm equipped with a suc- tion gripper performs picking and placing actions. There are three workspaces: the conveyor belt for transporting items, the bin for holding the items and the buffer zone for temporarily storing items. RGB-D im- ages of resolution 1280 x 720 are captured from Intel RealSense D435i cameras mounted on two fixed tripods overlooking the conveyor belt and the bin.
Item bufliar
Conveyor
Bin packing workspase
Figure The developed hin packing system based on PUN.
Sim-to-real transfer strategy. Since the bin packing policy is learned in the simu- lated environment, we need transfer strategy to apply it into the real world. The PUN takes as input two types of state representations, the bin heightmap and the item size map. To obtain the bin heightmap, we filter the observation captured by the camera and map it onto a discrete orthogonal grid using bilinear interpolation [30]. The mapped grid has the same resolution the size of the bin (i.e. L x W x H). To obtain the item size map, we perform boundary detection on the image of the item on the conveyor belt and calculate its 3D sizes. To ensure the safety the bin packing process, the item sizes are rounded to discrete values as the final state representations.
4 Experimental Results
In this section, we conduct experiments and ablation studies to evaluate the proposed method. We also provide supplementary video to demonstrate real robotic system for the online 3D-BPP
4.1 Data Generation and Implementation Details
To train and test the proposed network, we create three bin packing datasets based on previous works (13, 14), namely DATA-1, DATA-2 and DATA-3. To generate DATA-1, we cut bin of size S with
5

---

Table I: Comparative results of different bin packing methods.
DATA-1
DATA-2
DATA-3
Method
Uti.
Num.
Uti.
Num.
Sta.
Uti.
Num.
Sta.
Heuristic
Random
0.363
15.66
0.131
0.348
9.61
0.134
0.366
10.16
0.127
Columa Building [31]
0.629
25.75
0.125
0.566
14.76
0.124
0.571
15.26
0.127
Floor Building [28]
0.634
25.91
0.127
0,557
14,52
0.139
0.568
15.17
0.136
First Fit [19]
0.611
24.92
0.129
0.571
14.94
0.132
0.572
15.23
0.136
Corner point [2]
0.662
26.76
0.121
0.654
17.05
0.139
0.641
17.10
0.124
Extreme Point [7]
0.667
27.73
0.126
0.584
15.20
0,115
0.586
15.62
0.129
Empty Maximal Space [8]
0.669
27.79
0.114
0.652
16.99
0.118
0.649
17.31
0.124
Learning-
Zhao et al. [13]
0.687
28.61
0.103
0.632
16.39
0.114
0.642
16.97
0.111
Yang al. [14]
0.704
29.13
0.097
0.667
17.31
0.104
0.675
18.05
0.105
Zhao al. [25]
0.834
32.91
0.084
0.819
20.93
0.087
0.813
21.37
0.092
Ours
0.855
34.34
0.061
0.826
21.11
0.073
0.830
21.82
0.071
E {x,y, y, 2 into items of different sizes along the directions of length, width and height. The volume sum of all items is equal to the bin volume, and each item size sd E Z is not larger than / The item sequence is randomly shuffled to increase data diversity. To generate DATA-2 and DATA-3, we first predefine 64 items of different sizes, and then cut bin of size S into different items with the predefined sizes. When cutting the bin into items, we record the size of each item and its position in the bin. Then the items are sorted into a new sequence according to different rules designed in [13]. Note that either DATA-2 or DATA-3 contains fewer items than DATA-1 while the average item volume is larger, which inevitably affects the performance.
In implementation, the PUN is built based on actor-critic framework and extend the frame- work to a two-branch architecture. We create 10 parallel virtual environments for collecting on- policy training samples. In each iteration, the packing and unpacking samples are used update the packing and unpacking branches respectively. When one branch is active for gradient update, the other one fixed and its gradient is episodes in every epoch. Our models are developed using PyTorch and trained with an NVIDIA 2080Ti and an Intel 19-9900K CPU @ 3.60GHz. The hyperparameter settings that we used in the experiments are as follows: the discount factor is 0.95, the learning rate 4, is 0.003, the value function coefficient is 0.5 and the entropy coefficient , is 0.01.
0. We train PUN for 10000 epochs and collect 5120
4.2
Bin Packing Performance Evaluation
Baseline Methods. We compare the proposed method with 10 baseline methods for the online 3D- BPP, which can be classified into two groups. The first group contains random packing policy and heuristic methods. The second group contains state-of-the- art DRL-based methods. For these DRL-based methods, the agent would terminate episode when there is no available space for packing the current item in the bin. Note that the method proposed by Zhao et al. [25] has different variants and select the with the best performance the baseline (i.e. PCT&EV in [25)).
Results. We use 3 metrics to evaluate the bin packing performance. The metric Uti. is the space utilization defined as the average volume ratio of all packed items to the bin. The metric Num. is the average number of all packed items. The metric Sta. is the standard deviation of Uti.
The comparative results reported in Table show that our method outperforms all baseline methods in terms of all evaluation metrics. Such results indicate that PUN utilizes the bin space more suffi- ciently and performs more robustly than other competitors. Besides, due to the difference in the size and the number of the items in the 3 datasets as mentioned Section 4. 1, the bin packing meth- ods performs generally better on DATA-1 than on DATA-2 and DATA-3. We also visualize the bin packing results for a qualitative comparison where we create test sets by changing the item order of DATA-1. The visualization results in Fig. 6 show that our method outperforms the baselines.

---

#Test
#Test
FMS (8g
0.604
0.579
0.557
0.54
0.654
0.489
Thao et al (25]
0.792
0,8
0.736
0.814
0,199
Ours
0.859
0,861
0.587
Figure 6: Visualization results of different methods. The values beside cach sub-figure are the space utilization.
4.3 Ablation Studies
Evaluation of PUN variants. To demonstrate the designing choice of PUN, we create 3 variants for it and perform a series of ablation studies: Packing-only where only the packing branch of PUN retained, UUN-random--upackinng where the unpacking branch of PUN randomly selects items to be unpacked, PUN-no-constraint where PUN trained without heuristics- based constraints.
The comparative experiments are conducted on DATA-1, and the results are shown in Fig. 7, leading to several observations. First, PUN outperforms its vari- ants terms both Uti. and Num., indicating the effectiveness of the proposed network design. Second, compared to the vari- ant without the unpacking action (Packing-only), the variants with the unpacking action (PUN, PUN- no-constraint, and PUN-random-
0.82
33
0.78
0.74
29
0.70
0.66
1M
4M
5M
1M
2M
3M
5M
Training stops
Frnining stops
(Ours)
nuN-too-onstraintt
PUNN-random PUNNrandom-unpackinn unpacking
Packing-only
Figure 7: Learning curves of different PUN variants.
unpacking) achieve better performance in terms of both Uti. and Num. Such results show that the introduction of the unpacking mechanism effectively improves the bin packing performance, which demonstrate the proposed idea of introducing the unpacking action for online 3D-BPP. Third, unpacking action, the learning-basee ones (PUN and PUN-no-constrrintt
for the variants with perform better than the one based on the random policy (PUN-random- www.--anndomuuaaceeeee uupaacknga... It demonstrates the significance the proposed DRL framework for learning the synergies between packing and un- packing. Finally, PUN outperforms the variant without any heuristic constraint (PUN-no-constraint) which indicates that the heuristics-basel action constraints provides useful guidance for the training of PUN and improves the bin packing performance.
Exploration of different reward functions.
Table 2: Comparison different reward functions
To investigate the effect of different settings of
the reward function, we design reward func-
Reward
Uti.
Num.
Sta.
tions and compare them with the proposed one on DATA-I. The first one a constant value re- ward, defined as if the packing action is suc- cessfully performed, 0.5 if the unpacking ac- tion is successfully performed, and () otherwise. The second reward the final volume ratio of all packed items to the bin, which record after all steps and assign each step of bin packing.
Constant reward
0.742
29.96
0.085
Final-vol reward
0.745
30.07
0.091
Item-num reward
0.771
31.84
0.087
Our reward
0.855
34.34
0.061
7

---

Figure 8: Results of the real- world bin packing tests produced by our method.
Table 3: Effect of different buffer capacities
Buffer capacity
2
4
6
8
10
12
14
No limit
Uti. 0.739
0.791
0,815
0.834
0.852
0.855
0.854
0.855
Num. 29.21
30.74
32.57
33.19
34.21
34.32
34.31
34.34
The last one is the item number reward, defined as the number of the packed items in the bin. Ac- cording the results listed in Table 2, our method outperforms the competing methods terms of the space utilization and the number of packed items, which demonstrates the effectiveness of the designed reward.
Exploration of buffer capacity. We conduct the ablation study on DATA-1 to investigate the effect of different capacity B of the item buffer. For this experiment, the terminal condition of an episode is that the number of items in the buffer zone exceeds the buffer capacity there is no position for packing and unpacking the bin. The results reported in Table show that larger B results in better bin packing performance. However, when the buffer capacity exceeds 12, there is no significant performance gain.
4.4 Real-World Bin Packing Demonstration
We also demonstrate the proposed method in real logistics scenario where the implementation details can be found in Section 3.2. In this task, the robotic arm packs items from the conveyor belt into the bin one by one through the learned synergies between packing and unpacking. Fig. shows some testing results produced by our method. It can be seen that various items packed into different bins with high space utilization. The full bin packing process can be found in the supplementary video, which demonstrates that method reliably completes the real-world online 3D bin packing task in different logistics scenarios.
4.5 Limitation
Due to the measurement eπror of the vision sensors, the estimated item size and bin heightmap may have some deviations. The policy takes as input inaccurate state observations the scene and consequently predicts inappropriate packing unpacking actions. A possible solution is to introduce a "re- "re-packing" strategy to reposition the inappropriately packed/unpacked items. Besides, the proposed method focuses mainly on packing cuboid items while it cannot handle the irregularly shaped items. This because the state representations of PUN are unable to precisely represent the 3D geometry of irregularly shaped items. Consequently, as the cuboid one which tightly circumscribes it by PUN. Thus, future work to extend PUN to the items with diverse shapes by designing more powerful state representations of the item and the bin.
irregularly shaped item will be regarded
5 Conclusion
We introduce the idea of unpacking for the online 3D-BPP. Based on it, we propose the packing- and-unpacking network (PUN) which learns the synergies between packing and unpacking actions via DRL. We also incorporate the heuristics which formulate the packing and unpacking experiences of human packers into PUN further improve the bin packing performance. The results of both simulated and real-world experiments demonstrate the effectiveness of the proposed method.

---

Acknowledgments
This work was supported in part by the National Key Research and Development Plan of China under Grant 2021ZD01 12002 and Grant 2018AAA0102504, in part by the National Natural Science Foundation of China under Grant 61991411 and Grant U1913204, in part by the Natural Science Foundation of Shandong Province for Distinguished Young Scholars under Grant ZR2020JQ29, and in part by Project for Self-Developed Innovation Team of Jinan City under Grant 2021GXRC038.
References
[1] F. Wang and K. Hauser. Robot packing with known items and nondeterministic arrival order. IEEE Transactions on Automation Science and Engineering, 18(4):1001-1155, 2020.
[2] S. Martello, D. Pisinger, and D. Vigo. The three-dimensional bin packing problem. Operations research, 48(2):256-267, 2000.
[3] M. Hifi, I. Kacem, S. Nègre, and L. Wu. linear programming approach for the three- dimensional bin-packing problem. Electronic Notes in Discrete Mathematics, 36:993-1000, 2010.
[4] Gzara, S. Elhedhli, and B. C. Yildiz. The pallet loading problem: Three-dimensional bin packing with practical constraints. European Journal of Operational Research, 287(3):1062- 1074, 2020.
[5] E. C. man Jr, M. Garey, and D. Johnson. Approximation algorithms for bin packing: A survey. Approximation algorithms for NP-hard problems, pages 46-93, 1996.
[6] O. Faroe, D. Pisinger, and M. Zachariasen. Guided local search for the three-dimensional bin-packing problem. INFORMS Comput, 15(3):267-283, 2003.
[7] T. G. Crainic, G. Perboli, and R. Tadei. Extreme point-based heuristics for three-dimensional bin packing. INFORMS J Comput, 20(3):668-384 2008.
[8] C. T. Ha, T. T. Nguyen, L. T. Bui, and R. Wang. An online packing heuristic for the three- dimensional container loading problem in dynamic environments and the physical internet. In European Conference the Applications of Evolutionary Computation, pages 140-155, 2017.
[9] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: /6/ 1.09940, 2016.
[10] Yang, W. Zhang, R. Song. J. Cheng, and Y. Li. Learning multi-object dense descriptor for autonomous goal-conditioned grasping. IEEE Robotics and Automation Letters, 6(2):4109- 41 16, 2021. doi: 2.001 3062300.
[11] Z. Rao, Y. Wu, Z. Yang, W. Zhang, S. Lu, W. Lu, and Z. Zha. Visual navigation with multiple goals based on deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 32(12):5445 5455, 2021.
[12] H. Hu, X. Zhang, X. Yan, L. Wang, and Y. Xu. Solving a new 3d bin packing problem with deep reinforeement learning method. arXiv preprint arXiv:1708. 708.05930, 2017.
[13] H. Zhao, Q. She, C. Zhu, Y. Yang, and K. Xu. Online 3d bin packing with constrained deep reinforcement learning. In AAAI, volume 35, pages 741-749, 2021.
[14] Z. Yang. S. Yang. S. Song, W. Zhang, R. Song, Cheng, and Y. Li. Packerbot: Variable-sized product packing with hcuristic deep reinforcement learning, In IROS, pages 5002-5008.
[15] S. Seiden. the online bin packing problem. Journal the ACM (JACM), 4965):640-671, 2002.
[16] Egeblad. Placement of two-and three-dimensional irregular shapes for inertia moment and balance. International Transactions in Operational Research, 16(6):789 -07777888007, 2009.

---

[17] C. Voouoours, E. P. Tsang, and A. Alsheddy. Guided local search. In Handbook of metaheuris- fics, pages 321-361. Springer. 2010.
[18] A. Lodi, S. Martello, and D. Vigo. Heuristic algorithms for the three-dimensional bin packing problem. Eur. J. Oper. Res., 141())410-420 2002.
[19] E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of heuristics, (1):5-30, 1996.
[20] D. Silver, J. Schrittwieser, K. Simonyan, Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676):54-355, 2017.
[21] W. Kool, H. Van Hoof, and M. Welling. Attention, learn to solve routing problems! arXiv preprint arXiv: 180::80030000 08475, 2018.
[22] A. Laterre, Y. Fu, M. K. Jabri, A.-S. Cohen, Kas, K. Hajjar, T. S. Dahl, A. Kerkeni, and K. Beguir. Ranked reward: Enabling self-play reinforcement learning for combinatorial opti- mization. arXiv preprint arXiv: 187.01287. 2018.
[23] M. Nazari, A. Oroojlooy, L. Snyder, and M. Takac. Reinforcement learning for solving the vehicle routing problem. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, NeurlPS, volume 31, 2018.
[24] R. Verma, A. Singhal, H. Khadilkar, A. Basumatary, S. Nayak, H. V. Singh, S. Kumar, and R. Sinha. generalized reinforcement learning algorithm for online 3d bin-packing. arXiv preprint arXiv:2007.00463, 2020.
[25] H. Zhao, Y. Yu, and K. Xu. Learning efficient online 3d bin packing on packing configuration trees. In ICLR, 2021.
[26] M. L. Puterman. Markov decision processes. Handbooks in operations research and manage- ment science, 2:331 1344,,44,, 1990.
[27] I. Grondman, L. Busoniu, G. Lopes, and R. Babuska. A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6): 2012.
[28] Sweep. Three dimensional bin-packing issues and solutions. University of Minnesota, 2003.
[29] Huang and Ontañón. A closer look at invalid action masking in policy gradient algorithms. arXiv preprint vtXiv:2006.14171 2020.
[30] E. J. Kirkland. Bilinear interpolation. In Advanced Computing in Electron Microscopy, pages 261-263. 2010.
[31] B. Mahvash, A. Awasthi, and S. Chauhan. A column generation- heuristic for the three- dimensional bin packing problem with rotation. Journal of the Operational Research Society, pages 1-13, 2017.
10


Reviews:
[{"review_id": "ppn80wxVQ8G", "reviewer": "Reviewer_axHb", "summary": "The paper presents a solution to the 3D Bin Packing problem via the use of Deep Reinforcement Learning. Specifically, a 2 branch architecture is proposed to introduce the unpacking action and to learn how to apply optimally both packing and unpacking actions on boxes off of a conveyor belt in order to fill a bin while leaving as little space empty as possible.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Cool method, very well presented, enjoyable to read. Evaluation was quite thorough. \n\nWeaknesses: While evaluation was thorough, would have liked to have seen simple Imitation Learning approaches discussed, cited and compared against (see below for more details).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "Recommendation is based on not having cited, discussed and compared against at least one simple Imitation Learning approach. Imitation Learning approaches where expert demonstrations have both packing and unpacking actions, should be able to do fairly well on the task which would at least make a strong argument in favor of the efficacy of the approach if it outperformed them. I am willing to change my recommendation if authors address this adequately during rebuttal period. ", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Excellent: Enjoyable to read.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "5: The reviewer is absolutely certain that the evaluation is correct and very familiar with the relevant literature"}, "extra_text": {"issues": "Ln. 88: discretize? Or define? \n\nLn. 91-92: \"The state of the current item n with the size of 91 ln × wn × hn is represented as...\" That means that the state of each object never changes then since no object will ever change in width, height and length? If I'm misinterpreting the sentence, please rephrase to clarify.\n\nLn. 98: nit: tiny typo \"defined\".\n\nLn. 110: \"a shared feature extraction module\": how does this look like? \n\nLn. 112: \"Either the packing or the unpacking branch consists of...\": Did authors mean to say \"The packing and unpacking branches each consist of...\"?\n\nLn. 118. \"based on the heuristic rules\": what are the heuristic rules? Assuming they are explained later in the paper, however please add such note here to point the reader to that fact, e.g. \"based on heuristic rules that will be explained in section XXX\".\n\nLn 132-133: \"The agent will continue to predict the packing or unpacking action for the item n at the next time step until packing it into the bin\" --> how does this avoid possible infinite loops? \n\nGeneral comment: I'm assuming that based on the items and the capacity of the temporary buffer, there can be no solutions found. Does the method simply stop? Or does a best effort as far it's possible? Or?\n\nLn. 147: \"that on the top\". Typo.\n\nLn. 147-148: a) Is this the first rule for unpacking? If yes, please explain what it's aiming to do. b) Was the second rule omitted? Or mentioned later?\n\nEquations 3 & 4: what is M_i?  \n\nLn. 251-254: Not sure what's the rationale for reward function 1. Success in packing or unpacking actions alone does not really give any indication about whether that was a good move. Please explain.  \n\nLn. 64-65: I assume that the no gains observed above 12 was due to the number of items not changing. It's not obvious why this would still hold if number of items on the conveyor belt was very large. Have you increased the number of items and still observed this? If yes, do you hypothesize on why?\n\nGeneral comment: In general, the idea of unpacking and \"retrying\" in assembly tasks is not new. There is a whole line of work by Zeng et. al on Assembly & Disassembly (Transporter Nets, Form2Fit etc.) that was not cited where authors using Imitation Learning techniques to solve assembly tasks. \n\nAlso, have the authors attempted to solve this problem with Imitation Learning techniques like Behavioral Cloning? Not convinced that simple BC wouldn't have comparable results. Would like to have seen this at least as a baseline.  \n"}}, {"review_id": "i5QRTIJWPKZ", "reviewer": "Reviewer_WbWp", "summary": "The authors propose a deep RL based architecture for the 3D bin packing problem (3D BPP). The policy is learnt in simulation and is able to capture the synergy between picking and packing to achieve a target 3D packing configuration that minimizes the wasted space in the box. The policy takes in as input a heightmap and state representation specifying the item size and outputs pixel-locations for the pack/unpacking actions. The policy learns the synergy between pick and unpacking actions. Apart from outperforming prior learning and heuristic methods in simulation, the policy transfers to the real robot and even everyday objects (like cereal boxes).\n", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well written. It also has good ablations and experimental comparisons with prior work. I’m not familiar with the SOTA of the field, but the task seems unique enough.\nThe approach is also demonstrated on the real robot with strong sim2real transfer results.\n\nWeaknesses:\nThe data generation process could be explained better.\nThe approach only seems to work on limited object geometries and fixed-size box volumes. It would be great to clarify if the method can be expanded or if it's beyond the scope.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": " See above.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "issues": " See above.", "reviewer_expertise": "5: The reviewer is absolutely certain that the evaluation is correct and very familiar with the relevant literature"}, "extra_text": {}}, {"review_id": "WxWn09i4Hf1", "reviewer": "Reviewer_G14Q", "summary": "The paper presents a novel deep-RL based method for the online 3D bin packing problem. Here, cuboidal items arrive in random order and need to be packed as tightly as possible. The key idea of this paper is to enable to robot to \"backtrack\" suboptimal packing actions by temporarily unpacking part of the stack into a buffer region, and thus build more optimal packing configurations. The method is evaluated on extensive simulation experiments and a real world demonstrator.\n", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe paper is extremely well-written and easy to understand, despite the technical intricacies of the work. The method is technically sound, offering a great mix of explicit modelling and learning. The experiments are thoughtfully conceived, carried out and analyzed. The method demonstrates performance improvements over the state of the art and purely heuristic methods, mainly owed to the ability to perform backtracking through unpacking. Overall the paper was a very enjoyable and insightful read.\n\n## Weaknesses\n\nI have two concerns regarding the evaluation of the work.\n\n### Efficiency in terms of number of actions\n\nThe paper fully focuses on the cube utilization, i.e. reducing wasted space. While this is obviously a key metric, in industrial applications efficiency and units per hour (UPH) are equally important factors -- and obviously there is a trade-off between cube utilization and efficiency. I'm missing an analysis on how many unpacking actions are required to reach the improved cube utilization. This should be addressed by introducing an additional metric such as the average number of packing+unpacking actions. \n\n### Unfair baseline comparison?\n\nDirectly related to the previous question is whether the baselines are evaluated on a fair basis. If I understand correctly, no baseline (except for PUN-random-unpacking) actually does unpacking. If I interpret Figure 7 correctly, PUN-packing-only (Uti. = ~0.67) significantly underperforms the best performing baseline Zhao et al. (Uti. = 0.834). This immediately raises the question how much better Zhao et al. would perform if it was extended to use unpacking. For example, how well would Zhao et al. perform with random unpacking? \n\n### Minor points\n\n- Heuristics (140-148). I would encourage the authors to make the paper self-sufficient and explain the heuristics, at least 1/2 sentence per heuristic, rather than just naming them.\n- Figure 2. I was initially confused what \"packing mask\" and \"unpacking mask\" meant - I would suggest to explicitly mention \"heuristics\" in the figure to ensure to make clear that the Heuristics section 140-148 will explain it.\n- L154: Typo, -e-8 is not a mathematical expression, better use $10^{-8}$\n- L161: What does the t in the sum refer to? Is this a typo?\n- Sim-to-real strategy. I don't fully understand how individual items are identified in the real world demo, isn't some sort of instance segmentation both on the converyor as well as on the stack needed to identify individual boxes?\n- Limitations. I would suggest to discuss how perception and action errors might affect \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "The paper makes an important contribution to a highly relevant problem. The idea to introduce unpacking and learn an unpacking policy is compelling. However, the impact of unpacking needs to be analyzed more carefully, in particular on the efficiency of the approach (number of actions), and also on whether the baselines comparisons are fair.\n", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Excellent: Enjoyable to read.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "reviewer_expertise": "5: The reviewer is absolutely certain that the evaluation is correct and very familiar with the relevant literature"}, "extra_text": {"issues": "- Metrics/evaluation: Measure efficiency in terms of number of (additional unpacking) actions \n- Fair baseline comparison: Is PUN-packing-only significantly worse than Zhao et al? If yes, how much better is Zhao et al with some simple (e.g. random) or clever (?) unpacking strategy?\n- Minor issues\n\n(see Strengths and Weaknesses section for details)"}}, {"review_id": "P2b_YLdeamLI", "reviewer": "Reviewer_Wn5v", "summary": "The author presented a 3D bin packing algorithm, where unpacking action can be used to correct wrong decisions. They propose a packing-and-unpacking network (PUN) based on Deep Reinforcement Learning (DRL). The architecture is composed of two networks, a first one for the packing action and the second one for the unpacking one. At execution, both network output the value function evaluated at the current state and the action with the max reward is chosen. The networks output also the packing and unpacking position, respectively. The proposed algorithm is tested against 10 benchmarks both in simulation and experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-Strengths\n1) The experiments clearly show the effectiveness of the proposed strategy both in simulation and experiments.\n2) The idea of having an unpacking option is useful in practice.\n\n-Weaknesses\n1) It is a bit unclear how the two networks are trained.\n2) The algorithm is not theoretically sound as it is based on several heuristics.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "I think that overall the Strengths are more than the Weaknesses. In particular, I think that the result section clearly shows the benefit of the method. My only recommendation is to better explain the training process for clarity, and I think that such change is in the reach of the authors.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "I think that the clarity of the paper can be improved. In the Method section, I would add a training subsection where the authors could explain better the training process. It seems that the value function associated with the packing policy is a function of how good the unpacking policy is, i.e., the problem cannot be decoupled. Are the authors considering some coupling effect in the training process? It seems that it is a good idea to decompose the problem into subtasks, but could the authors provide a discussion on the pro and cons?"}}]

Author rebuttal:

Decision: Accept (poster)