Learning Efficient Online 3D Bin Packing on Packing Configuration Trees
Authors: Hang Zhao
Yang Yu
Kai Xu
Venue: ICLR 2022 Poster (2022)
Keywords: Bin Packing Problem
Online 3D-BPP
Reinforcement Learning

Abstract: Online 3D Bin Packing Problem (3D-BPP) has widespread applications in industrial automation and has aroused enthusiastic research interest recently. Existing methods usually solve the problem with limited resolution of spatial discretization, and/or cannot deal with complex practical constraints well. We propose to enhance the practical applicability of online 3D-BPP via learning on a novel hierarchical representation – packing configuration tree (PCT). PCT is a full-fledged description of the state and action space of bin packing which can support packing policy learning based on deep reinforcement learning (DRL). The size of the packing action space is proportional to the number of leaf nodes, making the DRL model easy to train and well-performing even with continuous solution space. During training, PCT expands based on heuristic rules, however, the DRL model learns a much more effective and robust packing policy than heuristic methods. Through extensive evaluation, we demonstrate that our method outperforms all existing online BPP methods and is versatile in terms of incorporating various practical constraints.

novel hier- Published as a conference paper at ICLR 2022
LEARNING EFFICIENT ONLINE 3D BIN PACKING ON PACKING CONFIGURATION TREES
Hang Zhao Yang Yu², Kai Xu"
School of Computer Science, National University of Defense Technology, China 2 National Key Lab for Novel Software Technology, Nanjing University, China falex. www...ang....................... zhao, kevin. kain faaj...ueeeee e ltle/mmal..omm com, yuyēnju. edu, cn
ABSTRACT
Online 3D Bin Packing Problem (3D-BPP) has widespread applications in indus- trial automation and has aroused enthusiastic research interest recently. Existing methods usually solve the problem with limited resolution of spatial discretiza- tion, and/or cannot deal with complex practical constraints well. We propose to enhance the practical applicability of online 3D-BPP via learning archical representation - packing configuration tree (PCT). PCT is a full-fledged description of the state and action space of bin packing which can support pack- ing policy learning based on deep reinforcement learning (DRL), The size of the packing action space is proportional to the number of leaf nodes, i.c. candidate placements, making the DRL model easy to train and well-performing even with continuous solution space. During training, PCT expands based on heuristic rules, however, the DRL model learns much more effective and robust packing policy than heuristic methods. Through extensive evaluation, we demonstrate that our method outperforms all existing online BPP methods and is versatile in terms of incorporating various practical constraints.
INTRODUCTION
As one of the most classic combinatorial optimization problems, the 3D bin packing problem usu- ally refers to packing a set of cuboid-shaped items E I, with sizes 8f. s sf along x, V, z axes, respectively, into the minimum number of bins with sizes S , S², in an axis-aligned fashion. Traditional 3D-BPP assumes that all the items to be packed are known a priori (Martello et al.) 2000 which is also called offline BPP. The problem known be strongly NP-hard (De Cas- tro Silva et al., 2003). However, in many real-world application scenarios, e.g., logistics or ware- housing (Wang& Hauser 2019a). the upcoming items cannot be fully observed; only the current item be packed is observable. Packing items without the knowledge of all upcoming items is referred to as online BPP (Seiden 2002).
Due to its obvious practical usefulness, online 3D-BPP has received increasing attention recently. Given the limited knowledge, the problem cannot be solved by usual search-based methods. Dif- ferent from offline 3D-BPP where the items can be placed in an arbitrary order, online BPP must place items following their coming order, which imposes additional constraints. Online 3D-BPP is usually solved with either heuristic methods (Ha et al.] (017) learning- based ones (Zhao al.) 2021], with complementary pros and cons. Heuristic methods are generally not limited by the size of action space, but they find difficulties in handling complex practical constraints such as packing stability or specific packing preferences. Learning- based approaches usually perform better than heuristic methods, especially under various complicated constraints. However, the learning hard to converge with large action space, which has greatly limited the applicability of learning-basee methods due to, e.g., the limited resolution of spatial discretization (Zhao et al. 2021.
We propose to enhance learning- based online 3D-BPP towards practical applicability through learn- ing with a novel hierarchical representation - packing configuration tree (PCT). PCT is a dynam- ically growing tree where the internal nodes describe the space configurations of packed items and
Work conducted while the author was visiting the National Key Lab for Novel Software Technology. Kai Xu is the corresponding author.

---

Published as a conference paper at ICLR 2022
leaf nodes the packable placements of the current item. PCT is a full-fledged description of the state and action space of bin packing which can support packing policy learning based on deep reinforce- ment learning (DRL). We extract state features from PCT using graph attention networks (Velickovic eet al. 2018) which encodes the spatial relations of all space configuration nodes. The state feature imput into the actor and critic networks of the DRL model. The actor network, designed based on pointer mechanism, weighs the leaf nodes and outputs the action (the final placement).
During training, PCT grows under the guidance of heuristics such as Corner Point (Martello al. 2000), Extreme Point (Crainic et al.) 2008), and Emply Maximal Space (Ha et al. 2017). Although PCT is expanded with heuristic rules, confining the solution space to what the heuristies could explore, our DRL model learns a discriminant fitness function (the actor network) for the candidate placements, resulting in an effective and robust packing policy exceeding the heuristic methods. Furthermore, the size of the packing action space is proportional to the number of leaf nodes, making the DRI, model easy to train and well-performing even with continuous solution space where the packing coordinates are continuous values. Through extensive evaluation, we demonstrate that our method outperforms all existing online 3D-BPP methods and is versatile in terms of incorporating various practical constraints such as isle friendliness and load balancing (Gzara et al. 2020). Our work is, to our knowledge, the first that deploys the learning-base based method on solving online 3D- BPP with continuous solution space successfully.
2 RELATED WORK
Offline 3D-BPP The early interest of 3D-BPP mainly focused on its offline setting. Offline 3D-
BPP assumes that all items known as priori and can be placed in an arbitrary order. |Martello itt al. (2000) first solved this problem with an exact branch-and- nential worst-case complexity of exact approaches, lots of heuristic and meta-heuristic algorithms are proposed to get an approximate solution quickly, such as guided local search (Faroe et al.. 2003).
approach. Limited by expo-
tabu search (Crainic et al.] 2009). and hybrid genetic algorithm (Kang et al., 2012). Hu et al. (2017) decompose the offlin 3D-BPP into packing order decisions and online placement decisions. The
packing order is optimized with an end-to-end DRL. agent and the online placement policy is a hand-
designed heuristic. This two-step fashion is widely accepted and followed by Duan et al. (2019). Hu
ct al. (020)) and Zhang et al. (202I).
Heuristies for Online 3D-BPP Although offline 3D-BPP has been well studied, their search- based approaches cannot be directly transferred to the online setting. Instead, lots of heuristic meth- ods have been proposed to solve this problem. For reasons of simplicity and good performance, the beep-bottoom-lett (DBL) heuristic (Karabulut & Inceoglu 2004) has long been a favorite. Ha eet al. (2017) sort the empty spaces with this DBL order and place the current item into the first fit one. [aag & Hauser (2019b) propose a Beightmaa--Mnnmizzen
method to minimize the volume increase of the packed items as observed from the loading direction. Hu al. (2020) optimize the empty spaces available for the packing future with a
wwwesssclcsssscoomeceie SSpace method.
DRL for Online 3D-BPP The heuristic methods are intuitive implement and can be easily applied to various scenarios. However, the price of good flexibility is that these methods perform mediocrely, especially for online 3D-BPP with specific constraints. Designing new heuristics for specific classes of DD-BPP is heavy work since this problem has an NP-hard solution space, many situations need to be premeditated manually by trial and error. Substantial domain knowledge is also necessary to ensure safety and reliability. To automatically generate policy that works well on specified online 3D-BPP, Verma et al. (2020); (Zhoo et al. (202 employ the DRL method on solving this problem, however, their methods only work in small discrete coordinate spaces. Despite their limitations, these works are soon followed by Hyong et al. (2020); Yang et al. (202T); Zhao et al. (022) for logistics robot implementation. Zhang al. (2021) adopt a similar online placement policy for offline packing needs referring to Hu et al. (201)) 7). All these learning based methods only work in grid world with limited discretization accuracy, which reduces their practical applicability.
Practical Constraints The majority of literature for 3D-BPP (Martello et al. 2000) only considers
the basic non-overlapping constraint [ and containment constraint 2
pf +
< p + 55 - (1)) i E I, E (x,
(1)
0 0 p. < 55 o iEI,dE (0.
d
(2)
2

---

Published as a conference paper at ICLR 2022
Bin
Empty space Placement node
Packed item Current item
Packed node Current node
Candidate position
Initial Configuration
t 0
3
Figure 1: PCT expansion illustrated using 2D example (in æoz plane) for simplicity and the number of allowed orientations [O] is (see Appendix [ for the 3D version). newly added item introduces a series of empty spaces and new candidate placements are generated, e.g., the left-bottom corner of the empty space.
Where P. means the Front-left-bottee coordinate of item and d the coordinate axis, Ct takes value 1 otherwise if item precedes item j along d. The algorithms for 3D-BPP are of limited practical applicability if no even basic real-world constraints, e.g., stability (Ramos et al.) 2016). considered. Zhao et al. (2022) propose fast stability estimation method for DRL training and test their learned policies with real logistics boxes. The flaw of their work is the heightmap (the upper frontier of packed items) state representation like Zhang et al. (202I) is still used, while the underlying constraints between packed items are missed. The unavailability of underlying spatial information makes their problem a partially observable Markov Decision Process (Spaan) 2012) which is not conducive to DRL training and limits the performance on 3D-BPP instances with more complex practical constraints, like isle friendliness and load balancing (Gzara et al. 2020
3 METHOD
In this section, we first introduce our PCT concept in Section 3.1 for describing the online packing process. The parameterization of the tree structure and the leaf node selection policy are introduced in Section 33.2 and Section 3.3 respectively. In Section [3.]] we formulate online 3D-BPP as Markov Decision Process based on PCT, followed by the description of the training method.
3.1 PACKING CONFIGURATION TREE
When a rectangular item ne is added to a given packing with position (P%.P% :h. at time step 1, it introduces a series of new candidate positions where future items can accommodated, as illustrated in Figure T Combined with the axis-aligned orientation E O for based on existing positions, we get candidate placements (i.e. position and orientation). The packing process can be seen as a placement node being replaced by packed item node, and new candidate placement nodes are generated as children. As the packing time step t goes on, these nodes are iteratively updated and dynamic packing configuration tree is formed, denoted T. The internal node set B, Te represents the space configurations of packed items, and the leaf node set L, E T, the packable candidate placements. During the packing, leaf nodes that no longer feasible, e-g., covered by packed items, will be removed from L, When there is no packable leaf node that makes satisfy the constraints of placement, the packing episode ends. Without loss of generality, we stipulate vertical top-down packing within single bin (Wang & Hauser 2019b).
Traditional 3D-BPP literature only cares about the remaining placements for accommodating the current item n4, their packing policies can be written as T TL, n2). If we want to promote this problem for practical demands, 3D-BPP needs to satisfy more complex practical constraints which also act on B, Taking packing stability for instance, a newly added item ne has possibly force and torque effect on the whole item set B, (Ramos et al., 2016). The addition of n, should make B, a more stable spatial distribution so that more items be added in the future. Therefore, packing policy over L, is defined as (L, (T,, nt), which means probabilities of selecting leaf nodes from L, given T; and n4- For online packing, the PCT with more relaxed constraints so that more future items can be appended.
hope find the best leaf node selection policy to expand
Leaf Node Expansion Schemes The performance of online 3D-BPP policies has strong rela- tionship with the choice of leaf node expansion schemes - which incrementally calculate new can- didate placements introduced by the just placed item n,. A good expansion scheme should reduce
3

---

Published as a conference paper at ICLR 2022
the number of solutions to be explored while not missing too many feasible packings. Meanwhile, polynomially computability is also expected. Designing such a scheme from scratch is non- trivial.. Fortunately, several placement rules independent from particular packing problems have been pro- posed, such as Corner Point (Martello et al., 2000), Extreme Point (Crainic et al. (2008. and Empty Maximal Space (Ha al.) 2017). We extend these schemes which have proven to be accurate and efficient to our PCT expansion. The performance of learned policies will be reported in Section 4.1
3.2 TREE REPRESENTATION
Given the bin configuration Tr and the current item ne, the packing policy can be parameterized as x (L,]Te, nz). The tuple (Tz, n4) can be treated as a graph and encoded by Graph Neural Networks (GNNs) (Gori et al., 2005). Specifically, the PCT keeps growing with time step and cannot be embedded by spectral-basct approaches (Bruna et al. 2014) which require fixed graph structure. We adopt non-spectral Graph Attention Networks (GATs) (Velickovic et al. 2018), which require no priori on graph structures.
The raw space configuration nodes B,, Lt, ny are presented by descriptors in different formats. We use three independent node-wise Multi-Layer Perceptron (MLP) blocks project these hetero- geneous descriptors into the homogeneous node features: h { (B.), 9o, (L,), do, (ne) xd d, is the dimension of each node feature and de is an MLP block with its parameters 0.
The feature number N should be [B, + [Le| + 1, which is a variable. The GAT layer is used to transform h into high-level node features. The Scaled Dot-Product Attention (Vaswani et al. 2017) is applied to each node for calculating the relation weight of one node to another. These relation weights are normalized and used to compute the linear combination of features h. The feature of node i embedded by the GAT layer can be represented as:
GAT(fu) Wo Σ softma (W9h,) Wh
dd
Where WQ E Rdaxds, W E Rddx,d, WV Rdd, and WO E Idd are projection matrices, dg and d, are dimensions of projected features. The softmax operation normalizes the relation weight between node and node j. The initial feature h is embedded by GAT layer and the skip-connection operation (Vaswani et al. 2017) is followed to get the final output features h:
h'=h+ h- GAT(h)
+
h h' (F)
(4)
Where OFF is a node-wise Feed-Forward MLP with output dimension di and h' is an intermediate variable. Equation 4 can be seen as independent block and be repeated multiple times with differ- ent parameters. We don't t extend GAT to employ the multi-head attention mechanism (Vaswani et al.) 2017) since we find that additional attention heads cannot help the final performance. We execute Equation 4 once and we set d, = dę. More implementation details are provided in Appendix
3.3 LEAF NODE SELECTION
Given the node features we need to decide the leaf node indices for accommodating the current item n4. Since the leaf nodes vary as the PCT keeps growing over time step t, mechanism ( (Vinyals et al. 2013) which is cantext-based attention over variable inputs to select a leaf node from L,. We still adopt Scaled Dot-Product Attention for calculating pointers, the global context feature is aggregated by a mean operation on h: h = 1/ E h4- The global feature is projected to a query q by matrix W E xdd, and the leaf node features h2 are utilized to calculate set of keys ky, by Wi E Rdd xd, The compatibility un of the query with all keys are:
pointer
N
q" K
q = WT k = Wh u,
(5)
Vdl.
Here h2 only comes from h,. The compatibility vector un E IR Tel represents the leaf node selection logits. The probability distribution over the PCT leaf nodes L, is:
Tp (L. Te. n.) = softmaz (Coiip tanh (ur.)
Following Bello et al. (2017), the compatibility logits are clipped with tanh, where the range is controlled by hyperparameter Catip, and finally normalized by softmax operation.
4

---

Published as a conference paper at ICLR 2022
3.4 MARKOV DECISION PROCESS FORMULATION
The online 3D-BPP decision at time step i only depends on the tuple (T₂, n4) and can be formulated as Markov Decision Process, which is constructed with state S. action A. transition P, and reward R. We solve this MDP with an end-to-end DRL agent. The MDP model is formulated as follows.
State The state 8; at time step is represented as s, (Tr, Te),, where T, consists of the internal nodes B, and the leaf nodes L. Each internal node b E B, is a spatial configuration of sizes (sg sh, st) and coordinates (p% PK. P5) corresponding to a packed item. The current item ne a size tuple (s%, 8h, s.). Extra properties will be appended to b and for specific packing preferences, such as density, item category, etc. The descriptor for leaf node E I4 is placement vector of sizes (s", sg s and position coordinates (p", "p",,"""" pp",, where (s% 8% 8)) indicates the sizes of n, along each dimension after an axis-aligned orientation o E O. Only the packable leaf nodes which satisfy placement constraints are provided.
The action de E A the index of the selected leaf node denoted as a, indea (I). The action space A has the same size as Lt A surge of learning- souning-based methods (Zhao et al.) 2021) directly learn their policy on a grid world through discretizing the full coordinate space, where [A] grows explosively with the accuracy of the discretization. Different from existing works, space solely depends on the leaf node expansion scheme and the packed items B, Therefore, our method can be used solve online 3D-BPP with continuous solution space. We also find that even if only an intercepted subset Laub E L, is provided, our method can still maintain a good performance.
Action
action
The transition P(s++ ((c)) is jointly determined by the current policy π and the prob- ability distribution of sampling items. Our online sequences are generated on-the-fly from an item set I in uniform distribution. The generalization performance of our method on item sampling distributions different from the training one is discussed in Section 4.4
Transition
Reward Our reward function R is defined as r; G. We once n, is inserted into PCT as an internal node successfully, otherwise, = 0 and the packing episode ends. Here is a constant and we is the weight of nt- The choice of we depends on the customized needs. For simplicity and clarity, unless otherwise noted, we set w, as the volume occupancy v, of ne, where v x sx sh-
DRL, agent seeks for policy (a (s)) to maximize the accumulated dis- counted reward. Our DRL agent is trained with the ACKTR method (Wu et al.) (017). The actor weighs the Ieaf nodes L, and outputs the policy distribution Ta (Le|Te. n²). The critic maps the global context h into state value prediction predict how much accumulated discount reward the agent can get from t and helps the training of the actor. The action a, is sampled from the distribution To [L TT, n.) for training and take the argmax of the policy for the test.
Training Method
ACKTR runs multiple parallel processes for gather- ing on-policy training samples. The node number N of each sample varies with the time step L and the packing sequence of each process. For batch caleu- lation, we fullfill PCT to fixed length with dummy nodes, as illustrated by F (a). These redundant nodes are eliminated by masked attention (Velickovic al. 2018) during the feature calculation of GAT. The aggregation of h only happens on the eligible nodes. For preserving node spatial relations, state &t is embedded by GAT as fully connected graph Figure (b). without any inner mask operation. More implementation details are provided in Appendix A
C Tree edge
Parked / Placement/ Curret// Dummy oode Relation
Projection
(a)
(b)
Figure Batch calculation for PCT.
EXPERIMENTS
In this section, we first report the performance of our PCT model combined with different leaf node expansion schemes. Then we will demonstrate the benefits of the PCT structure: better node spatial relation representations as well as more flexible action space. Finally, we test the generalization performance of our method and extend it to other online 3D-BPP with complex practical constraints.
Baselines Although there are very few online packing implementations publicly available, we still do our best to collect reproduce various online 3D-BPP algorithms, both heuristic and learning-
5

---

Published as a conference paper at ICLR 2022
based, from potentially relevant literature. We help the heuristic methods to make pre-judgment of placement constraints, c.g., stability, in case of premature downtime. The learning- based agents are trained until there are significant performance gains. Although both [Zhao et al. (2022) and Zhao methods recently proposed, we only compare with the former since is the upgrade of the latter. We also compare with the reported results of ofang et al. (202T) under the same condition. All methods are implemented in Python and tested on 2000 instances with a desktop computer equipped with Gold 5117 CPU and a GeForce TITAN V GPU. We publish the source code of our method along with related baselines at Githut
et al. (021) are learning-basse
Datasets Some baselines like Karabulut & Inceoglu (2004) need to traverse the entire coordinate space to find the optimal solution, and the running costs explode as the spatial discretization accuracy increases. To ensure that all algorithms are runnable within a reasonable period, we use the discrete dataset proposed by Zhao et al. (2021) without special declaration. The bin sizes S are set to 10 with d E (xr y, }} and the item sizes s Z are not greater than S /2 to avoid over-simplified scenarios. Our performance on more complex continuous dataset will be reported in Section 4.3 Considering that there are many variants of 3D-BPP, we choose three representative settings:
54/2
Setting 1: Following Zhao et al. (2022). the stability of the B, is checked when n4 is placed. Only two horizontal orientations (0) 2) are permitted for robot manipulation convenience.
Setting 2: Following Martello et al. 2000), item n, only needs to satisfy Constraint I [ndd] 2 Arbi- trary orientation (O 6) is allowed here. This is the most common setting in 3D-BPP literature.
Setting 3: Inherited from setting 1, each item n, has an additional density property p sampled from (0, 1] uniformly. This information is appended into the descriptors of B, and 72g.
4.1 PERFORMANCE OF PCT POLICIES
We first report the performance of our PCT model combined with different leaf node expansion schemes. Three existing schemes which have proven be both efficient and effective are adopted here: Corner Point (CP), Extreme Point (EP), and Empty Maximal Space (EMS). These schemes are all related to boundary points of a packed item along d axis. We combine the start/end points of n, with the boundary points of b E B, to get the superset, namely Event Point (EV). See Appendix
for details and learning curves. We extend these schemes to our PCT model. Although the number of leaf nodes generated by these schemes is within reasonable range, we only randomly intercept subset Loub, from L, if |L|| exceeds a certain length, for saving computing resources. The intercep- tion length is constant during training and determined by grid search (GS) during the test. See Appendix A for implementation details. The performance comparisons are summarized in Table
Table 1: Performance comparisons. Uti. and Num. mean the average space utilization and the average number of packed items separately. Var. (x10 is the variance of Uti. and Gap is w.r.t. the best Uti, across all methods. Hondom and Rendom & EV randomly pick placements from full coordinates and full EV nodes respectively. DBL, LSAH, MACS, and BR are heuristic methods proposed by Karabulut & Inceoglu (2004) (Hu et al. (2017)
Hu al. 2020
and 7aa et al. (2027) Ha ct al. (017). L.SHH, and BR heuristics hased EMS.
Setting Var.
Selting Var. Num.
Setting 3 Var. Num.
Method
Uti.
Num.
Gap
Uti
Gap
Uti.
Gap
Random
36.7%
10.3
14.9
51.7%
38.6%
8.3
15.7
55.1%
36.8%
10.6
14.9
51.4%
BR
49.0%
10.8
19.6
35.5%
56.7%
6.6
22.6
34.1%
48.9%
10.7
19.5
35.4%
Hcuristic
Ha al.
52.1%
20.1
20.6
31.4%
59.9%
10.4
23.8
30.3%
51.9%
20.2
20.6
31.4%
LSAH
52.5%
12.2
20.8
30.9%
65.0%
6.1
25.6
24.4%
52.4%
12.2
20.7
30.8%
Wang & Hauser MACS
57.6%
11.5
24.1
24.2%
66.1%
8.4
25.9
23.1%
56.5%
11.2
22.3
25.4%
57.7%
10.5
22.6
24.1%
50.8%
8.8
20.1
40.9%
57.7%
10.6
22.6
23.8%
DBL
60.5%
8.8
23.8
20.1%
70.6%
7.9
27.8
17.9%
60.5%
8.9
23.8
20.1%
Zhao et al. PCT CP
70.9%
6.2
27.5
6.7%
70.3%
4.3
27.4
18.3%
59.6%
5.4
23.1
21.3%
Learning- terming-busedd -useed
69.4%
5.4
26.7
8.7%
81.8%
2.0
31.3
4.9%
69.5%
5.4
26.7
8.2%
PCT & EP
71.9%
6.6
27.8
5.4%
78.1%
3.8
30.3
9.2%
72.2%
5.8
27.9
4.6%
PCT & FC
72.4%
4.7
28.0
4.7%
76.9%
3.3
29.7
10.6%
69.8%
5.3
27.1
7.8%
PCT & EMS
75.8%
4.4
29.3
0.3%
86.0%
1.9
33.0
0.0%
75.5%
4.7
29.2
0.3%
PCT EV
76.0%
4.2
29.4
0.0%
85.3%
2.1
32.8
0.8%
75.7%
4.6
29.2
0.0%
PCT & EVF
75.7%
4.8
29.2
0.4%
80.5%
2.9
31.0
6.4%
73.5%
4.6
28.4
2.9%
PCT EV/GS
75.8%
4.7
29.2
0.3%
84.8%
2.1
32.6
1.4%
75.5%
4.8
29.1
0.3%
Random & FV
45.7%
13.5
18.4
39.9%
51.0%
8.3
20.4
40.7%
45.1%
12.5
18.1
40.4%
https: httb
RPP

---

Published as a conference paper at ICLR 2022
Although PCT grows under the guidance of heuristics, the combinations of PCT with EMS and EV still learn effective and robust policies outperforming all baselines by a large margin regarding all settings. Note that the closer the space utilization is to 1, the more difficult online 3D-BPP is. is interesting to see that policies guided by EMS and EV even exceed the performance of the full coordinate space (FC) which is expected to be optimal. This demonstrates that a good leaf node expansion scheme reduces the complexity of the problem and helps DRL agents learn better performance. To prove that the interception of L, will not harm the final performance, we train agents with full leaf nodes derived from the EV scheme (EVF) and the test performance is slightly worse than the intercepted cases. We conjecture that the interception keeps the final performance may be caused by two reasons. First, sub-optimal solutions for online 3D-BPP may exist even in the intercepted leaf node set Lswb. In addition, the randomly chosen leaf nodes force the agent to make new explorations in case the policy т falls into the local optimum. We remove GS from EV cases to prove its effectiveness. The performance of Zhao et al. (2022) deteriorates quickly in setting? 2 and setting 3 due to the multiplying orientation space and insufficient state representation separately. Running costs, scalability performance, behavior understanding, visualized results, and the implementation details of our real-world packing system can all be found in Appendix [C]
We also repeat the same experiment as Zhang et al. (2021) which pack items sampled from pre- defined item set |Z| 64 in selling 2. While Zhang al. (021)) packs on average 15.6 items and achieves 67. 57.0% space utilization, our method packs 19.7 items with a space utilization of 83.0%.
4.2 BENEFITS OF TREE PRESENTATION
Here we verify that the PCT representation does help online 3D-BPP tasks. For this, we embed each space configuration node independently like PointNet (Qi et al. 2017) prove the node spatial relations help the final performance. We also deconstruct the tree structure into node sequences and embed them with Ptr-Net (Vinyals et al., 2013), which selects a member from serialized inputs, for indicating that the graph embedding fashion fits our tasks well. We have verified that an appropriate choice of L, makes DRL agents easy train, then we remove the internal nodes B, from T,, along with its spatial relations with other nodes, to prove B, is also necessary part. We choose EV as the leaf node expansion scheme here. The comparison results are summarized in Table
Table 2: A graph embedding for complete PCT helps the final performance.
Setting Var.
Sefting 2 Num.
Setting Var.
Presentation
Uti.
Num.
Gap
Uti.
Var.
Gap
Uti.
Num.
Gap
PointNet
69.2%
6.7
26.9
8.9%
78.9%
3.2
30.5
7.5%
71.5%
5.3
27.7
5.5%
Ptr-Net
64.1%
10.0
25.1
15.7%
77.5%
4.1
30.1
9.1%
63.5%
7.9
24.8
16.1%
PCT (T B)
70.9%
5.9
27.5
6.7%
84.1%
2.6
32.3
1.4%
70.6%
5.3
27.4
6.7%
PCT (T)
76.0%
4.2
29.4
0.0%
85.3%
2.1
32.8
0.0%
75.7%
4.6
29.2
0.0%
If we ignore the spatial relations between the PCT nodes only treat the state input flattened sequence, the performance of the learned policies will be severely degraded. The presence of B functions more on setting and setting 3 since sefting allows items be packed in any empty spaces without considering constraints with internal nodes. This also confirms that complete PCT representation essential for online 3D-BPP of practical needs.
4.3 PERFORMANCE ON CONTINUOUS DATASET
The most concerning issue about online 3D-BPP is their solution space limit. Given that most learning-base methods can only work in a limited discrete coordinate space, we directly test our method in a continuous bin with sizes superiority. Due to the lack of public datasets for online 3D-BPP issues, we generate item sizes through a uniform distribution sd U(a, Std /2), is set to 0.1 in case endless items are generated. Specifically, for 3D-BPP instances where stability is considered, the diversity of item size s² needs to be controlled. If all subsets of B, meet:
Sá 1 to prove
X
Σ B
s Boudl A Boud2, Baubl, B Baud2 B,
(7)
iEB..t2
7

---

Published as a conference paper at ICLR 2022
This means any packed items cannot form new plane for providing support in the direction of gravity and the available packing areas shrink. Excessive diversity of s will degenerate 3D-BPP into ID-BPP shown in the toy demo. To prevent this degradation from leading to the underutilization of the bins, we sample 8 from a finite set 0.,,.............
on setting and setting 3.
Table 3: Online 3D-BPP with continuous solution space.
Setting Var.
Setting 2 Num.
Setting Num.
Method
Uti.
Num.
Gap
Uti.
Var.
Gap
Uti.
Var.
Gap
BR
40.9%
7.4
16.1
37.5%
45.3%
5.2
17.8
31.7%
40.9%
7.3
16.1
38.6%
Heu.
al. LSAH
43.9%
14.2
17.2
32.9%
46.1%
6.8
18.1
30.5%
43.9%
14.2
17.2
34.1%
48.3%
12.1
18.7
26.1%
58.7%
4.6
22.8
11.5%
48.4%
12.2
18.8
27.3%
DRL
GD
5.6%
2.2
91.4%
7.5%
2.9
88.7%
5.2%
2.1
92.2%
PCT & EMS
65.3 15.3%
4.4
24.9
0.2%
66.3 %
2.3
27.0
0.0%
66.6% %
3.3
25,3
0.0%
PCT & EV
65.4 %
3,3
25.0
0.0%
65.0%
2.6
26.4
2.0%
65.8%
3.6
25.1
2.7%
We find that some heuristic methods (Ha et al. 2017) also have the potential to work in the contin- uous domain. We improve these methods as our baselines. Another intuitive approach for solving online 3D-BPP with continuous solution space is driving a DRI. agent to sample actions from gaussian distribution (GD) and output continuous coordinates directly. The test results are summa- rized in Table 3 Although the continuous-sin item set is infinite (IZ) oo) which increases the difficulty of the problem and reduces the performance of all methods, our method still performs better than all competitors. The DRL agent which outputs continuous actions directly cannot even converge and their variance is not considered, Our work is, to our knowledge, the first that deploys the learning- based method on solving online 3D-BPP with continuous solution space successfully.
4.4 GENERALIZATION ON DIFFERENT DISTRIBUTIONS
The generalization ability of learning- based methods has always been a concern. Here we demon- strate that our method has a good generalization performance on item size distributions different from the training one. We conduct this experiment with continuous solution space. We sample s" from normal distributions N (p, o²)) for generating test sequences where μe and a are the expecta- tion and the standard deviation. Three normal distributions are adopted here, namely NO0.3, 0.12), (0..1, 0. and (0.5, 0.2?), as shown in Figure 3 The larger of the normal distribution, the larger the average size of sampled items. We still control s within the range of [0.1, 0.5). If the sampled item sizes are not within this range, we will resample until it meets the condition.
Table 4: Generalization performance on different kinds of item sampling distributions.
Selling Var.
Selling Var.
Setling Var.
Test Distribution
Method
Uti.
Num.
Uti.
Num.
Uti.
Num.
LSAH
48.3%
12.1
18.7
58.7%
4.6
22.8
48.4%
12.2
18.8
((0.1,0.5)
PCT & EMS PCT & EV
65.3%
4.4
24.9
66.3%
2.3
27.0
66.6 %
3.3
25.3
65.4%
3.3
25.0
65.0%
2.6
26.4
65.8%
3.6
25.1
LSAH
49.2%
11.1
18.9
60.0%
4.1
22.9
49.2%
11.0
18.9
8 ~ N/O.3,0.13 0.13
PCT & EMS
66.1%
3.6
25.1
64.3%
3.5
25.6
66.4%
3.0
25.2
PCT & EV
65.1%
2.8
24.7
63.7%
2.6
25.3
66.2%
2.9
25.1
LSAH
52.4%
8.9
30.3
62.9%
2.4
44.3
52.3%
8.9
30.2
5 0.0.1.0.23)
PCT EMS
68.5%
2.5
39.0
66.4%
3.0
49.7
69.2%
2.5
39.4
PCT EV
66.5%
2.7
38.0
64.9%
2.7
48.3
67.4%
2.4
38.5
LSAH
47.3%
12.6
13.0
56.0%
5.5
12.9
47.3%
12.6
13.0
8d N(...5 0.2?
PCT EMS
63.5%
5.0
17.3
64.5%
2.8
15.4
65.2%
3.8
17.7
PCT & EV
65.1%
3.3
17.7
64.5%
2.8
15.3
65.1%
3.7
17.7
We directly transfer our policies trained on U 0.5) to these new datasets without any fine-tuning.
We use the best-performing heuristic method LSAH (Hu et al. 2017) in Section 4.3 as baseline. The test results are summarized in Table 4 Our method performs well on the distributions different from the training one and always surpasses the LSAH method. See Appendix C for more results about the generalization ability of our method on disturbed distributions and unseen items.
8

---

Published as a conference paper at ICLR 2022
U(0.1,0.5)
N(0.3,0.11)
N(0.1.0.22)
N(O.5,0.22)
Sampling distribution
4-
2
2
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.1
0.2
0.3
0.4
0.5
0.6
0
0.1
0.2 0.3
0.4
0.5
0.6
0.1
0.2 0.3
0.4
0.5 0.6
Item size
Item
Item
size
Item
Figure 3: The probability distribution for sampling item sizes. The area of the colored zone is normalized
4.5 MORE COMPLEX PRACTICAL CONSTRAINTS
To further prove that method fits 3D-BPP with complex constraints well, give two demon- strations about extending our method to online 3D-BPP with additional practical constraints: isle friendliness and load balancing (Gzara et al. 2020):
3D-BPP with Isle Friendliness Isle friendliness refers to that items belonging to the same cat- egory should be packed as closely possible. The item weight is set as wt mar(0, 1 dist(ne, B,)), is a constant. The additional object function dist(n;, B₂) means the average dis- tance between n, and the items of the same category in B,, The additional category information is appended into the descriptors of B, and n4. Four item categories are tested here.
3D-BPP with Load Balancing Load balancing dictates that the packed items should have an even mass distribution within the bin. The item weight is set w/ = max(0, 0t - eevevvrnn B,)). Object war(n, B,) the variance of the mass distribution of the packed items on the bottom of the bin.
Table 5: Online 3D-BPP with practical constraints. Obj. means the task-specific objective score, the smaller the better. Setting 2 involves no mass property and the load balancing is not considered.
Setting 1 Num.
Setting Num. Obj.
Setting 3 Num.
Method
Uti.
Obj.
Ut.
Uti.
Obj.
Zhao al. PCT & EV
58.3%
22.5
4.58
64.2%
24.8
4.67
59.0%
22.8
4.60 4.45
Isle Friendliness
72.1%
29.0
4.44
85.2%
32.8
2.69
74.6%
28.8
Zhao et al. PCT & 73.7%
60.3%
23.3
88.0
61.1%
23.7
30.1
Load Balancing
28.6
40.5
74.0%
28.7
20.9
We choose the learning-bees based method Zhao et al. (2022) as our baseline since heuristic methods only take space utilization as their objects. The results are summarized in Table Compared with the baseline algorithm, method better achieves the additional object while still taking into account the space utilization as the primary.
DISCUSSION
We formulate the online 3D-BPP as novel hierarchical representation - packing configuration tree. PCT is full-fiedged description of the state and action space of bin packing which makes the DRL agent easy to train and well-performing. We extract state feature from PCT using graph attention networks which encodes the spatial relations of all space configuration nodes. The graph representation of PCT helps the agent with handling online 3D-BPP with complex practical con- straints, while the finite leaf nodes prevent the action space from growing explosively. Our method surpasses all other online 3D-BPP algorithms and is the first learning- based method that solves on- line 3D-BPP with continuous solution space successfully. Our method performs well sampling distributions different from the training one. We also give demonstrations to prove that our method is versatile in terms of incorporating various practical constraints. For future research, we are extremely interested in applying our method to the more difficult irregular shape packing (Wang Hauser 2019a), where the sampling costs for training DRL agents are more expensive and the solution space will be far more complex. A good strategy for balancing exploration and exploitation for learning agents is eagerly needed in this situation. Finding other alternatives for better represent- ing 3D-BPP with different packing constraints and designing better leaf node expansion schemes for PCT are also interesting directions.
on item

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank Zhan Shi, Wei Yu, and Lintao Zheng for helpful discussions. We would also like to thank anonymous reviewers for their insightful comments and valuable suggestions. This work is supported by the National Natural Science Foundation of China (62132021, 61876077).
ETHICS STATEMENT
We believe the broader impact of this research is significant. BPP is considered one of the most needed academic problems due to its wide applicability in our daily lives (Skienal 1997). Providing good solution to online 3D-BPP yields direct and profound impacts beyond academia. We note that online packing setups have been already widely deployed in logistics hubs and manufacturing plants. A good online 3D-BPP policy benefits all the downstream operations like package wrapping, transportation, warehousing, and distribution.
Our method also be treated as separate decision module and utilized solve other variants of 3D-BPP issues, such as multi-bin online 3D-BPP, online 3D-BPP with lookahead (Zhao et al.) 2021]. online placement decision for offline 3D-BPP (Hu al. 2017), and the logistics robot imple- mentation for online packing (Zhao et al.) (022). which have been well studied in previous works. We give demonstrations about applying our method solving online 3D-BPP with various complex practical constraints, the similar idea can also be adopted to meet other customized desires.
REPRODUCIBILITY
Our real-world video demo is submitted with the supplemental material. The source code of method and related baselines is published at wtw.acuub.commlleeeeeee33333
Online- BDP
REFERENCES
Irwan Bello, Hieu Pham, Quoe Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Bansf, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei, Extreme woint-based heuristics for three- dimensional bin packing. INFORMS Comput., 20(3):368-384, 2008. doi: 10.1287/jjc.1070. 0250.
Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. Ts2pack: A two-level tabu search for the diree-dimensional bin packing problem. Eur. J. Oper. Res., 195(3):744-760, 2009. doi: 10. 10.10166/jejorr e.l...eo....00........ 00.00006606.....
J. De Castro Silva, NY Soma, and N Maculan. A greedy search for the three-dimensional bin packing problem: the packing static stability case. International Transactions Operational Research, 10(2):141-153 2003.
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang, Jiangwen Wei, and Yinghui Xu. A multi-task selected learning approach for solving 3D flexible bin packing problem. In Pro- ceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, AAMAS 19, Montreal, QC. Canada, May 13-17, 2019, pp. 1386-1399 1394, International Foundation for Autonomous Agents and Multiagent Systems, 2019.
10

---

Published as a conference paper at ICLR 2022
Oluf Faroe, David Pisinger, and Martin Zachariasen. Guided local search for the three-dimensiona. bin-packing problem. INFORMS J. Comput., 15(3):267-283, 2003. doi: 2t.1287/jjo..55.32222 16080.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Pro- ceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734 vol. 2005. doi: 10.1 1001100CCNN2
Fatma Gzara, Samir Elhedhli, and Burak C. Yildiz. The pallet loading problem: Three-dimensional bin packing with practical constraints. Eur. J. Oper. Res., 287(3):1062-1074 2020. doi: 10.1016/ rejorr2020.04.000 04.053.
Chi Trung Ha, Trung Thanh Nguyen, Lam Thu Bui, and Ran Wang. An online packing heuristic for the three-dimensional container loading problem in dynamic environments and the physical inter- net. In Applications of Evolutionary Computation 20th European Conference, ExoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings. Part II, volume 10200 of 10.10077998-33339-5579-2-- Lecture Notes in Computer Science, pp. 140 155, 2017. doi: 10. 1007/978 3-319-55792-2
URL https: /tw.///oiiioooo .or./orgg//oo 10. 1077 978 3- 31 9 557 2010
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1856- 1865. PMLR, 2018. URL bttp::/proceed:ee html
mlr wwwpppessssss....p http://////aaaa///aaaaaa haarno paaarnoja883 jal8b.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick. Mask R-CNN. In IEEE In- lernational Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pp. 2980-200 2988. IEEE Computer Society, 2017. doi: 10.1 109111CC..22....22....
Young-Dat Dae Hong, Young-Joo Kim, and Ki-Baek Lee. Smart pack: Online autonomous object- packing system using RGB-D sensor data. Sensors, 20(16):4448, 2020. doi: 10.3390/s20164448.
Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, and Yinghui Xu. Solving new 3D bin packing problem with deep reinforcement learning method. CoRR, abs//708 75930,,30, 2017.
Ruizhen Hu, Juzhan Xu, Bin Chen, Minglun Gong, Hao Zhang, and Hui Huang. Tap-net: transport- and-pack using reinforcement learning. ACM Trans. Graph., :32: 2020. doi:
Kyungdaw Kang, Iikyeong Moon, and Hongfeng Wang- A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem. Appl. Math. Comput., 219(3): 1287-1299, 2012.
doi: 10. amc.
Korhan Karabulut and Mustafa Murat Inceoglu. A hybrid genetic algorithm for packing in 3d with deepest bottom left with fill method. In Advances in Information Systems, Third International Conference, ADVIS 2004, Izmir. Turkey, October 20-22, 2004, Proceedings, volume 3261 Lec- ture Notes in Computer Science, pp. 441-450. Springer, 2004. doi: 10.1007/978-3-5400300 _45.
Silvano Martello, David Pisinger, and Daniele Vigo. The three-dimensional bin packing problem. Oper. Res., 48(2):256-22) 267, 2000. doi: 10. 20.1187/opre.48.2.002 1....
James Martens and Roger B. Grosse. Optimizing neural networks with sanneckr--fcctoeee approxi- mate curvature. In Proceedings the 32nd International Conference on Machine Learning. ICML 2015, Lille, Frunce, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceed- ings, pp. 2408 2417. JMg,.org, 2015. URL http: htap:://proceedi mwt..mess//../.1.. martens15.htm
Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point for 3D classification and segmentation. In 2017 IEEE Conference Computer Viston and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 77-85. IEEE Computer Society, 2017. doi: 10. 109/C....0017.16.

---

Published as a conference paper at ICLR 2022
António Galrão Ramos, José Fernando Oliveira, and Manuel Pereira Lopes. A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium condi- tions. Int. Trans. Oper. Res., 23(1-2):2152255 2016. doi: 10.1111/ttr.2212..
Steven S. Seiden. On the online bin packing problem. J. ACM, (96)):440-671, 2002. doi: 10.1 585265.585269.
Steven S Skiena. The stony brook algorithm repository. http://www.cs www.ss.unbbbooooo.
shtml 1997.
Mathhij TJ Spaan. Partially observable markov decision processes. Reinforcement Learning, pp.
387-414. Springer, 2012.
Matthew E. Taylor and Peter Stone. Transfer learning for reinforcemeeet leaming domainn domains: A survey. cfm?
J. Mach. Learn. Res., 10: 10:3113168,,, 2009. URL
id 1755839
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998-6008 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Richa Verma, Aniruddha Singhal, Harshad Khadilkar, Ansuma Basumatary, Siddharth Nayak, Harsh Vardhan Singh, Swagat Kumar, and Rajesh Sinha. A generalized reinforcement learning algorithm for online 3d bin-packing. CoRR, 0002007.00466. 2020.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural In- formation Processing Systems 28: Anmual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2692-2700, 2015.
Fan Wang and Kris Hauser. Robot packing with known items and nondeterministic arrival order. In Robotics: Science and Systems XV, University of Freiburg. Freiburg im Breisgau, Germany, June 22-26. 2019, 2019a, doi: 10. 1560755SSS 2019.........
Fan Wang and Kris Hauser. Stable bin packing of non-convex 3D objects with a robot manipulator. In International Conference on Robotics and Automation, ICRA 2019, Montreal, QC, Canada, May 20-24, 2019, pp. 8698-8704, 8704. IEEE, 2019b. doi: 10. 10.1109/CRAA2011..879900
Yuhuai WU, Elman Mansimov, Roger B. Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kronecker-factoree approximation. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Process- ing Systems 2017, December 4-9, 2017. Long Beach, CA, USA, pp. 5279-5277559 5288, 2017.
Zifei Yang, Shuo Yang, Shuai Song, Wei Zhang, Ran Song, Jiyu Cheng, and Yibin Li. Packer- bot: Variable-sized product packing with heuristic deep reinforcement learning. In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2021, Prague, Czech Repub- lic, September 27- Oct. 1, 2021, pp. 5002-5008. IEEE, 2021. doi: 10. 101109//R05511682200 9635914.
Jingwei Zhang, Bin Zi, and Xiaoyu Ge. Attend2pack: Bin packing through deep reinforcement learning with attention. CoRR, abs/2107.04333. 2021.
Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. Online 3D bin packing with con- strained deep reinforcement learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pp. 741-749. AAAI Press, 2021.
Hang Zhao, Chenyang Zhu, Xin Xu, Hui Huang, and Kai Xu. Learning practically feasible policies for online 3d bin packing, Science China Information Sciences, 65(1):1-17, 2022.
12

---

Published as a conference paper at ICLR 2022
In this appendix, we provide more details and statistical results of our PCT method. Our real- packing demo is also submitted with the supplemental material.
Section A] gives more descriptions about training methods, which include the implementa- tion of the deep reinforcement learning method, specific GAT network designs for extract- ing problem features from PCT, and recommendations for finding suitable PCT length.
Section B claborates the concept of the leaf node expansion schemes adopted for finding candidate placements in our method. Learning curves and the computational complexity analysis of these schemes are also provided in this section.
Section C reports more statistical results of our method, including further discussions on generalization ability, running costs, and scalability. The understanding of model behav- iors, the visualized results, and details of our real-world packing system are also provided.
A IMPLEMENTATION DETAILS
Deep Reinforcement Learning We formulate online 3D-BPP as Markov Decision Process and solve it with the deep reinforcement learning method. A agent seeks for a policy ı to maximize the accumulated discounted reward:
0
(T) = ETTO
y R(s ar]
(8)
t=
Where E [0, 1] is the discount factor, and T = (so, ao, 81,...) .) is a trajectory sampled based on the policy æ. We extract the feature of state st (Te, Re) using graph attention networks (Velickovic et al. 2018) for encoding the spatial relations of all space configuration nodes. The context feature fed to two key components of our pipeline: an actor network and a critic network. The actor network, designed based on pointer mechanism, weighs the leaf nodes of PCT, which is written as (ag]s:). The action de an index of selected leaf node E L,, denoted as a+ = index(1). The critic network maps the context feature into state value prediction Vss,) which helps the training of actor network. The whole network trained via a composite loss L = a Lactor + 3 Leriss (a B = in our implementation), which consists of actor loss Lactor and critic loss Leritie- These two loss functions are defined as:
{ Lactor = =(r+ +VV++))) Vss)) ( log (ac(st) (s,))
Leritic = +
Where r, = Cr is our reward signal and we set Ty as 1 since the packing episode is finite. We adopt a step reward r, = G, Wi once ni inserted into PCT as an internal node successfully. Otherwise, r = 0 and the packing episode ends. The choice of item weight wi depends on the packing preferences. In the general sense, we set We as the volume occupancy V; = s -g sf, of ni, and the constant o,- is 10/(S*..) -5 SV. S²). For online 3D-BPP with additional packing constraints, this weight can be set as wi = mar((, (0, 82 - c (st, at) While term ii ensures that space utilization is still the primary concern, the objective function O(s,, a:) guides the agent to satisfy additional constraints like isle friendliness and load balancing. We adopt ACKTR (Wu et al.] (017) method for training our DRL agent, which iteratively updates an actor and critic using Krotecker-factored approximate curvature (K-FAC) (Martens & Grosse 2015) with trust region. Zhhao el al. (202T) have demonstrated that this method has a surprising superiority on online 3D packing problems over other model-free DRL algorithms like SAC (Haarnoja et al. 2018)).
Feature extraction Specifically, ACKTR runs multiple parallel processes (64 here) to interact with their respective environments and gather samples. The different processes may have different packing time step t and deal with different packing sequences, the space configuration nodes number N also changes. To combine these data with irregular shapes into one batch, we fullfill B, and L, to fixed lengths, 80 and 25- |0| respectively, with dummy nodes. The descriptors for dummy nodes are all-zero vectors and have the same size as the internal nodes or the leaf nodes. The relation weight logits Vsy of dummy node j to arbitrary node i is replaced with -fn to eliminate these dummy nodes during the feature calculation of GAT. The global context feature h is aggregated only on the eligible nodes h: h = & >
connected graph as Figure 2 =1 h4. All space configuration nodes are embedded by GAT as a fully
(b), without any inner mask operation.
13

---

Published as a conference paper at ICLR 2022
We only provide the packable leaf nodes which satisfy placement constraints for DRL agents. For setting 2, we check in advance if candidate placement satisfies Constraint and For setting and setting3 where the mass of item n, is U, and p i, respectively, we will additionally check if one placement meets the constraints of packing stability. Benefits from the fast stability estimation method proposed by /Zhao al. (2022). this pre-checking process be completed in very short time, and our DRL agent samples data at frequency of more than 400 FPS.
The node-wise MLPs Φ0g: @+ and de,, used embed raw space configuration nodes are two-layer linear networks with LeakyReLU activation function. OF F is a two-layer linear structure activated by ReLU. The feature dimensions da, dR; and d, are 64. The hyperparameter Celip used to control the range of clipped compatibility logits is set to 10 in our GAT implementation.
Choice of PCT Length Since PCT allows discarding some valid Ieaf nodes and this will not harm our performance, we randomly intercept subset Lyub, from L; if [L,] exceeds certain length. Determining the suitable PCT length for different bin configurations is important, we give our recommendations for finding this hyperparameter. For training, we find that the performance of learned policies is more sensitive to the number of allowed orientations |O]. Thus we set the PCT length as |O| where can be determined by grid search nearby configurations. For our experiments, c = 25 works quite well. During the test, the PCT length can be different from the training one, suggest searching this interception length with validation dataset via a grid search which ranges from 50 to 300 with step length 10.
25 for different bin
B LEAF NODE EXPANSION SCHEMES
We introduce the leaf node expansion schemes adopted in our PCT implementation here. These schemes are used incrementally calculate new can- didate placements introduced by the just placed item ny. good expansion scheme should reduce the num- ber of solutions to be explored while not missing too many feasible packings. Meanwhile, polynomially computability is also expected. As shown in Figure 4 the policies guided by suitable leaf node expansion schemes outperform the policy trained dinate (FC) space in the whole training process. We extend three existing heuristic placement rules which have proven to be both accurate and efficient to our PCT expansion, i.e. Corner Point, Extreme Point, and Empty Maximal Space. Since all these schemes are related to boundary points of packed items, we com- bine the start/end points of n, with these boundary points as superset, namely Event Point.
Space utilization
0.70
0.65
CP
FV
full coor-
FC
EMS
0.60
0.1
0.3 Steps Million
0.2
0.4
0.5
Figure Learning curves setting 1. A good expansion scheme PCT reduces the complex- ity and helps DRL methods for more efficient learning and better performance. EVF means the full EV leaf node set without interception.
Corner Point Martello al. (2000) first introduce the concept of Corner Point (CP) for their branch-and- bound methods. Given 2D packed items in the zoy plane, the comerr points can be found where the envelope of the items in the bin changes from vertical to horizontal, as shown in Figure 5 (a). The past corner points which no longer meet this condition will be deleted. Extend this 2D situation to 3D cases, the new candidate 3D positions introduce by the just placed item n, are a subset of {px + s P%, Pi)), (p" PK + s s.,)), (p% pk P" + +;)}} if the envelope of the corresponding 2D plane, roy, yoz, and roz, is changed by ne. The time complexity of finding 3D corner points incrementally is (cc) with an easy-to pasy-to-ne to--tmatmitaiedd bin height map data structure to detect the change of envelope on each plane, is constant here.
Extreme Point Crainic et al. (2008) extend the concept of Corner Point to Extreme Point (EP) and claim their method reaches the best offline performance the means to exploit the free space defined inside a packing by the shapes of the items that already exist. When the current item ne is added, new EPs are incrementally generated by projecting the coordinates (Fr 5/ PM/ P., (Pr PM 8y p.), (p",, pl, P% sM)} on the orthogonal axes, e.g., project (pr,, + + ph px) )x))r in the directions of the and 2 axes to find intersections with all items lying between item n4 and the boundary of the bin. The nearest intersection in the respective direction is an
that era. Its insight is to provide
14

---

Published as a conference paper at ICLR 2022
y
Envelope
(a) CPs
(b) EPS
(c) EMSs
(d) EVs
Figure 5: Full candidate positions generated by different PCT expansion schemes (all in roy plane). The gray dashed lines are the boundaries the bin. Circles (a) and (b) represent corner points and extreme points respectively, (c): The candidate positions (circles) introduced by different EMSs are rendered with diffcrent colors. All intersections of two dashed lines in (d) constitute event points.
extreme point. Since stipulate vertical top-down loading direction, the 3D extreme points in the strict sense may exist large item blocking the loading direction. So we find the 2D extreme points each distinct p² value (i.e. start/end z coordinate of a packed item) which satisfies P S pz I P + 8 The time complexity of this method is (m [BpD)), where B2D the packed items that exist the corresponding plane and m is the number of related z scans.
(see Figure 5 (b)) in the zoy plane and repeat this operation
Empty Maximal Space Empty Maximal Spaces (EMSs) (Ha et al. 2017) are the largest empty orthogonal spaces whose sizes cannot extend more along the coordinate axes from its front-left- bottom (FLB) corner. This is simple and effective placement rule. An EMS is presented by its FLB corner (p" p Pε) and sizes (s" sy s²). When the current item n, is placed into on its FLB corner, this EMS is split into three smaller EMSS with positions (pÉ + sy p%. p(), (P" pe + sy pε), (pt ph, P + + and sizes (s" sh sy (s" sy s%, s²), s2 22, st -s"), respectively. If the item nt only partially intersects with we can apply similar volume subtraction to the intersecting part for splitting e. For each ems, we define the left-up (v, pe + =8,,2) right-up (F + P + rē), left-bottom (vā P..PE) pE), and right-bottom (ne P= PE) corners of its vertical bottom as candidate positions, as shown in Figure (c). These positions also need to be converted to the FLB corner coordinate for placing item n4. The left-up, right-up, left-bottom and right-bottom corners of should be converted to pp 15+ss-ss -% (. +s n +% 6% Pt), (p': pE),:) and (ve + Se sh P.-Pe) P?) respectively. Since all EMSs E E in the bin needs to detect intersection with nı, the time complexity of finding 3D EMSs incrementally is O(E)). ). A 3D
schematic diagram of PCT expansion guided by EMSs is provided in Figure
Initial Configuration
3
Figure 6: A 3D PCT expansion schematic diagram. This PCT grows under the guidance of the EMS expansion scheme. For simplicity, we only choose the bottom-right hight-utht-upp up corners each EMS as candidate positions and we set |0| = 1 here.
Event Point It's not difficult to find that all schemes mentioned above are related to boundary points of a packed item along d E {x, y axes (we assume the initial empty bin is also special packed item here). When the current item n, is packed, we update the existing PCT leaf nodes by scanning all distinct pz values which satisfy P" S p² < P + s², and combine the start/end points of n, with the boundary points that exist this 2 plane get the superset (see 5) which is called Event Points. The time complexity for detecting event points is O(m |Bapl=).
15

---

Published as a conference paper at ICLR 2022
C MORE RESULTS
In this section, we report more results of our method. Section further discusses the generalization ability of our method on disturbed item sampling distributions and unseen items. Section C.2 reports the running cost of each method. Section
scales our method to larger problem and reports the performance. Section C.4 visualizes packing sequences to analyze model behavior and more visualized results are provided in Section C.3
C.3
Section in our real-world packing system.
C.I FURTHER DISCUSSIONS ON GENERALIZATION
We have verified in Section 4.4 that our method has good generalization performance on item sam- pling distributions different from the training one. Now we further analyze the generalization ability of our method. Firstly, we demonstrate that our algorithm has good generalization performance on disturbed item sampling distributions. We conduct this experiment the discrete setting where the item set is finite ([Z) = 125). For each item E I. we add random non-zero disturbance 6; on its original sample probability Pt, e.g.. P: = p; (1- 11--0 6.). We normalize the disturbed p; as the final item sampling probability. Note that 6, is fixed during sampling one complete sequence. The state tran- sition of DRL (($t+1(st) which is partly determined by the probabilities of sampling items will be different from the training transition where the uniform distribution sample items with equal proba- bilities. Generalizing to a new transition is a classic challenge for reinforcement learning (Taylor & Stone 2009). We test different ranges of 6, and the results are summarized in Table 6
Table 6: Transfer the best persfreeforming PCT policies directly to the disturbed item sampling distributions. Dif. means how much the generalization performance drops from the undisturbed case (6, 0).
Setting Var.
Setting 2 Var.
Setting 3 Var. Num.
Disturbance
Uti.
Num.
Dif.
Uti.
Num.
Dif.
Uti.
Dif.
76.0%
4.2
29.4
0.0%
86.0%
1.9
33.0
0.0%
75.7%
4.6
29.2
0.0%
E 20%, 20%]
75.6%
4.6
29.1
0.5%
85.7%
2.1
32.8
0.3%
75.3%
1.5
29.0
0.5%
8: E - 10%, 10%
75.5%
4.5
29.0
0.7%
85.6%
2.1
32.8
0.5%
75.6%
1.8
29.3
0.1%
8, E 60%, 60%]
75.5%
4.3
28.9
0.7%
85.8%
2.1
32.8
0.2%
75.5%
4.8
28.9
0.3%
6, 80%, 80%
75.7%
4.5
29.2
0.4%
85.6%
2.2
32.9
0.5%
75.4%
4.9
29.3
0.4%
E 100%, 100%]
75.8%
4.4
29.0
0.3%
85.5%
2.2
32.6
0.6%
75.3%
4.7
29.3
0.5%
Benefits from the efficient guidance of heuristic leaf node expansion schemes, our method maintains its performance under various amplitude disturbances. Our method even behaves well with a strong disturbance 6; E [-100% 100%] applied. which means some items may never be sampled by some distributions when 6; and p: (1 5,) in a specific sequence.
Beyond experiments on generalization to disturbed distributions, we also test our method with un- seen items. We conduct this experiment in the discrete setting. We randomly delete 25 items from I and train PCT policies with |Zaubl 100. Then we test the trained policies on full I. See Table 7 for results. Our method still performs well on datasets where unseen items exist regarding all settings.
Table 7: Generalization performance on unseon items. All policies are trained with the EV scheme.
Sefting Var.
Setting Var.
Setting 3 Num.
Train
Test
Uti.
Num.
Uti.
Num.
Uti.
Var.
Z = 125
I 125
76.0%
4.2
29.4
85.3%
2.1
32.8
75.7%
4.6
29.2
Taub 100
Taubl = 100
74.4%
5.1
29.4
86.3%
1.7
33.8
74.2%
4.7
29.3
Iaubl = 100
[ 125
74.6%
5.4
28.9
85.6%
2.6
33.0
74.4%
5.2
28.8
C.2 RUNNING COSTS
For 3D-BPP of online needs, the running cost for placing each item is especially important. We count the running costs of the experiments in Section 4.1 and Section 4.3 and summarize them in Each running cost at time step / counted from putting down the previous item f4-1 until the current item n, is placed, which includes the time to make placement decisions, the time to check placement feasibility, and the time to interact with the packing environment. The running cost of our method is comparable to most baselines. Our method can meet real-time packing requirements in both discrete solution space and continuous solution space.
Table 8
16

---

Published as a conference paper at ICLR 2022
Table 8: Running costs (seconds) tested on online 3D-BPP with discrete solution space (Section 4.1 and continuous solution space (Section 4.3). The running costs latter are usually more expensive since checking Constraint and 2 in the continuous domain is more time-consuming.
Setting 1
Setting 2
Setting 3
Method
Discrete
Continuous
Discrete
Continuous
Discrete
Continuous
Random
4.59 10-2
2.03 10
4.62 10
Wang & Hauser
4.76 x 10
3.01 10
4.55 10 2
Heuristic
DBL
5.58 x 10-2
1.87 X 10
5.44 x 10
BR
1.50 x 10 1.69 x 10 10T2
1.74 X 10
1.76
10
1,42 x 10
1.62 X 10
Ha
5.89 x 10 1.48
10
3.39 10
7.17
10
1.86 10
1.38
10
LSAH
1.22 x 10 1.44 x 10
4.98 10
7.02
10
1.14 X 10
1.33 x 10
MACS
2.68 x 10"2
3.00 x 10
2.79 x 10
Zhao et al.
5.51 x 10
1.33 10
3.31 10
DRL
PCT CP
8.43 x 10 10 1.61 x 10-2
7.36 x 10
1.52
10
8.79 x 10
1.73 x 10-2
PCT & EP
1.22 x 10 3.73
x 10
1.13 10
1.57
10
1.25 10
3.65
x 10
PCT & EMS
1.77 10 4.11
10
9.49 10
2.36
10
1.80
10
3.08
10
PCT EV
2.66 x 10 4.46
1.25 x 10
3.21
10
2.61
10 2
4.38
10
C.3
SCALABILITY
The number of PCT nodes changes constantly with the generation and removal of leaf nodes during the packing process. To verify whether our method can solve packing problems with a larger scale [B], conduct stress test on setting 2 where the most orientations are allowed and the most leaf nodes are generated. We limit the maximum item sizes s to /5 so that more items can be accommodated. We transfer the persfreefonnin policies on setting (trained with EMS) these new datasets without any fine-tuning. The results are summarized in Table
Table 9: Scalability larger packing problems. [L] is the average number of leaf nodes per step. Run. is the running cost.
[L] will not increase exponentially with [B] since invalid leaf nodes will be removed.
Discrete
Continuous Uti.
Item sizes
B
Run.
L|/ BB
B
Run.
L|/ B
Isd /10, srd [2]
33.0 51.5 86.0% 9.5
10-2
2
1.6
27.0 197.5 66.3% 2.4 10 7.3
[$0/10, St /5/
241.3 67.2 81.3% 9.8 x 10-3 0.3
185.4
956.5 61.9%
3.7 10 5.2
PCT size will not grow exponentially with packing scale [B] since invalid leaf nodes will be removed from leaf nodes L during the packing process, both discrete and continuous cases. For continuous cases, [L| is more sensitive to [B] due to the diversity of item sizes (i.e. Z|| oo), however, L still doesn' explode with / and grows in sub-linear way. Our method can execute packing decisions at real-time speed with controllable PCT sizes even if the item scale is around two hundred.
C.4 UNDERSTANDING OF MODEL BEHAVIORS
The qualitative understanding of model behaviors is important, especially for practical concerns. We visualize our packing sequences give our analysis. The behaviors of learned models differ with the packing constraints, If there is no specific packing preference, our learned policies will start packing nearby fixed corner (Figure 7 (a)) The learned policies tend combine items of different heights together to form a plane for supporting future ones (Figure 7 (b)). Meanwhile, it prefers to assign little items to gaps and make room (Figure 7 (c)) for future large ones (Figure 7 (d)). additional packing preference is considered, the learned policies behave differently. For online 3D- BPP with load balancing, the model will keep the maximum height the bin as low as possible and pack items layer by layer (Figure ())). For online 3D-BPP with isle friendliness, our model tends to pack the same category of items nearby the same bin corner (Figure (f))
C.5 VISUALIZED RESULTS
We visualize the experimental results of Section 4.1 ated item sequence packed by our best-performing policies (PCT & EV on setting and setting 3, PCT & EMS on setting 2).
Figure Each plot is about a randomly gener-
17

---

Published as a conference paper at ICLR 2022
(a)
(b)
(c)
(e)
Figure 7: (a)~(d)) Different packing stages same sequence. learned policies assign little items (colored in blue) to gaps save room for future uncertainty. (e): Online 3D-BPP where load halancing considered, (f): Online 3D-BPP with isle-friendliness, different color means different item categories.
Eattrn 11
Sangg 2
Sattiny 3
Figure 8: Visualized results of our method.
C.6 WORLD PACKING SYSTEM
We follow the online autonomous bin packing system implementation of Zhao et al.) (2022) in logistics warchouse to validate our PCT method. As shown in Figure 9 the conveyor belt transports items to the robot arm (STEP@SR20E) at a fixed speed. The on- conveyor RGB-D camera (PhoXi 3D Scanner XL) recognizes the size and location of the current item. This information is sent the robot arm for picking the current item and our PCT model for the placement decision. We align the bin coordinate with the robot coordinate and transform the packing decision to a real-world position. Then the robot arm places the current item into the bin which is table trolley with sizes S 110cm, S" = 90cm, and 5 80cm. We record sizes and positions of packed items de- scriptors of internal nodes B.
On-bin
On-conveyor camera
camera
Figure Our packing system. The on-conveyor camera detects packing targets. The on-bin cam- era monitors possible drifts of packed items.
Different from the original implementation of Zhao et al. (2022) where only one on-conveyor camera used for detecting the target item to be packed, we add one more on-bin RGB-D camera and adopt Mask R-CNN (He et al. 2017) for instance segmentation of input depth image, for monitoring possible drift of packed items. If packed item deviates from the position of the PCT decision and this drift is detected, we will correct the descriptor of the corresponding internal node E B with the offset position. We use items with s and 3 ranging from 20cm to 40cm, and s ranging from 10cm 25cm. We fill items with paddings of the same density and train PCT policies on sefting I with the EV scheme and the load balancing constraint. We test our system with 50 random sequences and our method achieves 78.6% space utilization with 50.9 items packed. Our real-world packing video demo is also submitted with the supplemental material.
18


Reviews:
[{"review_id": "zrCbyRb7obD", "reviewer": "Reviewer_65kq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is important to handle Large scale packing problem with continuous action space. The authors expand the tree by using methods of heuristics, which reduces the action space to limited number of leaf nodes (actions). Then reinforcement learning is incorporated to optimize packing efficiency. As a result, the method reduces the size of action space which leads to better learning results.\n\nHowever, there are some suggestions to improve the paper:\n1. The method reduces the action space to discrete nodes via heuristic search, while after heuristic search, the packing action space is not fully covered because the heuristics only select part of action space. In fact, It is a trend-off between complexity and optimality. In addition, the complexity of the tree search will grow exponentially when lots of items have to be packed, which threaten the scalability of the proposed method. Worse, a large number of leaf node would makes the attention network computationally heavy since it is quadratic related to the number of nodes.\n2. After determine the candidate points, the original heuristics select the placement point of new item by its own heuristic rules. Here, the authors replace the heuristic candidate points selection with DRL. But they do not compare with recent heuristics to show whether the DRL is indeed superior than these heuristic rules.\n3. The dataset is too naive, which only discretizes each edge to 10, while conventional methods have much more resolution. In their continuous setting, their results degrade, but there is no explanation about this. The authors claim that the method works on continuous solution space, but they do not define the continuous solution space. Clearly, it is different from the continuous action space in reinforcement learning. In fact, the method works on discrete action space.\n4. I think Section 4.4 should be modified. The distribution of adding a uniform random disturbance to each point of another uniform distribution is almost uniform. This is not the proper way to evaluate generalization.\n\nThere are some specific points: \n1. The author did not mention how many bins are used in the problem settings, which should be clearly state.\n2. In the second paragraph of introduction, the authors said online packing ‘imposes additional constraints and difficulty’. but it is clear that offline packing is more complex than the its online variety since it includes the item selection step before the ‘online packing’ step. In the next sentence, the authors said ‘Learning-based approaches usually perform better than heuristic methods, especially under various complicated constraints’. Why Learning-based approaches perform better under various complicated constraints?\n3. In equation 1, the right side use a capital S，I didn’t understand this, should this be a lowercase s? \n4. In the first paragraph of page 3,  ‘The flaw of their work is the heightmap (frontier) state representation like Zhang et al. (2021) is still used, while the underlying interactions that exist in packed items are missed’. what does the ‘underlying interactions’ mean?\n5. In Section 3.1, the authors use \\pi(L_t|L_t,n_t) to denote policy, but the policy is \\pi(a|s) in RL. Therefore, people may be confused between the state and action when reading. This notion is very misleading. The same problem exists in the following text.\n", "summary_of_the_paper": "This work proposes a tree-based learning method for online 3D packing problem. Packing configuration tree nodes is constructed using heuristic-based tree expansion, which acts as the action space of deep reinforcement learning. The tree search schema is interesting, but this work still has lots of space to improve in terms of its methodology and experiments.", "summary_of_the_review": "The paper has studies an interesting problem but it still has lots of space to improve.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "r9F5xvsP4eh", "reviewer": "Reviewer_vAx8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The reviewer is not quite familiar with this research area, but the proposed PCT and the corresponding learning method seem to be quite novel and sound.\n- This paper is written in a clear and thoughtful way.\n- The evaluations and related studies have been conducted thoroughly. The performance gain over existing recent baselines is clear. Empirical results on generalization also well demonstrate the efficacy of this work.\n\nI have a few (maybe dumb) following questions:\n- Could you explain the constraint in Eq. (1)? What does it mean when $e_{ij}=0$ and $p_i^d + s_i^d \\le p_j^d + S^d$?\n- What is the inference time for the proposed method with different leaf node expansion schemes? The theoretical time complexities have been introduced in the appendix, and the practical timing is a question of interest.\n- How is the density property considered in Setting 3?\n", "summary_of_the_paper": "This paper proposes a new method for online 3D bin packing problem (3D-BPP), with the newly designed packing configuration tree (PCT) for representing the state and graph attention networks (GAT) for learning the representations. Experimental comparisons with recent baselines and for different constraint settings are provided.", "summary_of_the_review": "The reviewer is not actively working within the scope of this work. Still, it is a pleasure to read this paper, and it clearly describes and motivates the problem and proposes plausible and effective solutions with detailed experiments.\n\n====\nThe reviewer has read all other reviews and the rebuttals and would very much thank the authors for the speedy and detailed response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Q7wQqhlK2Ly", "reviewer": "Reviewer_MYY8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- structuring the state and action space in the proposed manner has many clear advantages over previous methods. This is demonstrated in quantitative comparisons and in the model's capacity to handle continuous spaces. Intuitively there are properties of a tree-based representation and the attention-based action space that would lend themselves better to learning.\n- in the ablations in Table 5 we see that when introducing additional constraints the proposed method outperforms Zhao et al both in utilitzing space and meeting the additional task objective of the target constraint\n- overall the paper is written clearly (a couple confusing spots here and there) but the overall organization is good and I think appropriate choices are made as to what details to leave in the appendices\n\nWeaknesses:\n\nThere are some additional insights that would perhaps offer a clearer picture of what this model is learning to do and which parts of the proposed approach are necessary to do well in this problem setting:\n- it might be nice to have some qualitative understanding of the learned leaf selection process. What behavior does the trained policy exhibit? Does the distribution over available leaves show clear preference for certain locations or is it somewhat uniform over possible options?\n- The random baseline as described in Table 1 seems somewhat weak, for example, how does a random policy perform given the available leaves to choose from in the PCT & EV baseline?\n- we see in Table 2 that removing the internal node set B altogether drops performance, but not too much. Are there simple alternatives to the state representation provided by processing a graph network over the nodes of B that might have performed just as well? Would there be any scaling issues when processing B with a large number of nodes?\n\nI was confused about section 4.4, what exactly is being changed here? There is some set of items I and you are changing the probability of sampling a given object in that set? From Table 4 it doesn't seem like this is a particularly different setting that the model might have any difficulty with, the scores are the same across the board. How does the model handle items it has never seen? Or items with sizes that are far outside of the distribution of the items it has been trained on?", "summary_of_the_paper": "This paper addresses the problem of online 3D bin packing where the order of objects is out of the model's control and it must make placement decisions one object at a time. Training is framed as a deep RL problem closely following recent work [Zhao et al]. The main contribution is a rethinking of the state and action space which yields much better performance. Prior work trained models to predict placement in a voxelized grid that led to a large action space that could not scale well. Instead, this work represents existing objects and potential placement locations as nodes in a tree which are processed with a graph network. Given a new object, placement nodes can be heuristically instantiated to cover valid locations, and the model uses attention to output a distribution over these nodes and determine the object placement.", "summary_of_the_review": "I think the method presented in this paper is a good strategy for defining the state/action space for bin packing. The paper is clear and the experiments are convincing, so I recommend acceptance. It would be stronger with more compelling evidence that the graph network is learning non-trivial policy behavior, but overall the results are certainly strong over prior work and existing heuristics.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IljI01T10D", "reviewer": "Reviewer_Dhzn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The idea of PCT, as a whole, is novel and makes a good sense. It is also well illustrated and easy to follow.\n2. The motivation of the work is well explained and the pros and cons of different methods are clearly discussed.\n3. The experiments are extensive and the proposed method based on PCT outperforms all competing methods significantly.\n\nWeaknesses:\n\n1. PCT is expanded with only 3 existing rules of heuristics, including CP, EP and EMS. Such a strategy seems to oversimplify the problem. There exist a couple of heuristics and some of them were summarised in:\n\n    - A generalized reinforcement learning algorithm for online 3d bin-packing. AAAI 2020.\n\n    - A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 1996.\n\n2. The authors claim that the proposed method is efficient. But there is neither theoretical analysis (e.g. some kind of complexity analysis) nor experimental results (e.g. run time, number of iterations needed for DRL convergence, visualisation of learning curves, etc.) for demonstrating it.\n\n3. There is no real-world experiments, which makes the paper a bit weak especially because it attempts to demonstrate the efficiency of the PCT. A demo like the one provided with the following paper would be impressive. \n\n     - PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. IROS 2021.\n\nIn addition, the paper could be improved if the following issues can be clarified:\n\n1. In Section 3.3, what is the physical meaning of the pointer mechanism (Vinyals et al., 2015) employed for leaf node selection?\n\n2. In Section 3.4, the authors mentioned “we fullfill PCT to a fixed length with dummy nodes”. But how can we find a fixed length for different bin configurations? If it is too small, it will not be enough for holding all leaf nodes; if it is too large, it will make the learning space excessively large and hurt the efficiency significantly.\n", "summary_of_the_paper": "The paper presents PCT, a tree structure that integrates several packing heuristics for addressing the online 3D-BPP. The PCT 1) can be amenably incorporated into DRL as a term of the reward function and 2) makes the training tractable as it effectively trims the learning space defined by the low-level packing heuristics. ", "summary_of_the_review": "The idea of PCT is holistically novel and seems effective for the online 3D-BPP, which is a very challenging issue anyway. Therefore, although the paper has some issues as listed above, I am still slightly positve to it.\n\n------------ Post rebuttal -------------- \n\nMost of my concerns have been well addressed during the rebuttal period of time. I'd appreciate very much the effort made by the authors and am happy to lift my recommendation to a full acceptance. Btw, it seems that some references are missing in the revised version, such as the two recent ones for 3D-BPP listed below:\n\n- A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing. AAAI 2020.\n- PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. IROS 2021.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new approach to online 3D bin packing with deep reinforcement learning. It received mixed reviews. AC finds that the responses from authors have addressed the concerns satisfactorily.
Decision: Accept (Poster)