ON PACKING CONFIGURATION TREES
Year: 2022

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, i.e. 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 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.

heading: 1 INTRODUCTION
text: As one of the most classic combinatorial optimization problems, the 3D bin packing problem usually refers to packing a set of cuboid-shaped items i ∈ I, with sizes sxi , s y i , s z i along x, y, z axes, respectively, into the minimum number of bins with sizes Sx, Sy, Sz , 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 is known to be strongly NP-hard (De Castro Silva et al., 2003). However, in many real-world application scenarios, e.g., logistics or warehousing (Wang & Hauser, 2019a), the upcoming items cannot be fully observed; only the current item to 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. Different 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., 2017) or learning-based ones (Zhao et 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 is hard to converge with a large action space, which has greatly limited the applicability of learning-based 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 learning with a novel hierarchical representation –– packing configuration tree (PCT). PCT is a dynamically 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.
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 reinforcement learning (DRL). We extract state features from PCT using graph attention networks (Velickovic et al., 2018) which encodes the spatial relations of all space configuration nodes. The state feature is input 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 et al., 2000), Extreme Point (Crainic et al., 2008), and Empty Maximal Space (Ha et al., 2017). Although PCT is expanded with heuristic rules, confining the solution space to what the heuristics 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 DRL 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-based method on solving online 3DBPP with continuous solution space successfully.

heading: 2 RELATED WORK
text: Offline 3D-BPP The early interest of 3D-BPP mainly focused on its offline setting. Offline 3DBPP assumes that all items are known as a priori and can be placed in an arbitrary order. Martello et al. (2000) first solved this problem with an exact branch-and-bound approach. Limited by exponential 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), tabu search (Crainic et al., 2009), and hybrid genetic algorithm (Kang et al., 2012). Hu et al. (2017) decompose the offline 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 handdesigned heuristic. This two-step fashion is widely accepted and followed by Duan et al. (2019), Hu et al. (2020), and Zhang et al. (2021).
Heuristics for Online 3D-BPP Although offline 3D-BPP has been well studied, their searchbased approaches cannot be directly transferred to the online setting. Instead, lots of heuristic methods have been proposed to solve this problem. For reasons of simplicity and good performance, the deep-bottom-left (DBL) heuristic (Karabulut & Inceoglu, 2004) has long been a favorite. Ha et al. (2017) sort the empty spaces with this DBL order and place the current item into the first fit one. Wang & Hauser (2019b) propose a Heightmap-Minimization method to minimize the volume increase of the packed items as observed from the loading direction. Hu et al. (2020) optimize the empty spaces available for the packing future with a Maximize-Accessible-Convex-Space method.
DRL for Online 3D-BPP The heuristic methods are intuitive to 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 3D-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 a policy that works well on specified online 3D-BPP, Verma et al. (2020); Zhao et al. (2021) 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 Hong et al. (2020); Yang et al. (2021); Zhao et al. (2022) for logistics robot implementation. Zhang et al. (2021) adopt a similar online placement policy for offline packing needs referring to Hu et al. (2017). All these learning-based methods only work in a 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 1 and containment constraint 2:
pdi + s d i ≤ pdj + Sd(1− edij) i 6= j, i, j ∈ I, d ∈ {x, y, z} (1)
0 ≤ pdi ≤ Sd − sdi i ∈ I, d ∈ {x, y, z} (2)
Where pi means the front-left-bottom coordinate of item i and d the coordinate axis, eij takes value 1 otherwise 0 if item i 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), are considered. Zhao et al. (2022) propose a 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. (2021) 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).

heading: 3 METHOD
text: 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 3.2 and Section 3.3 respectively. In Section 3.4, we formulate online 3D-BPP as Markov Decision Process based on PCT, followed by the description of the training method.

heading: 3.1 PACKING CONFIGURATION TREE
text: When a rectangular item nt is added to a given packing with position (pxn, p y n, p z n) at time step t, it introduces a series of new candidate positions where future items can be accommodated, as illustrated in Figure 1. Combined with the axis-aligned orientation o ∈ O for nt 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 a 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 a dynamic packing configuration tree is formed, denoted as T . The internal node set Bt ∈ Tt represents the space configurations of packed items, and the leaf node set Lt ∈ Tt the packable candidate placements. During the packing, leaf nodes that are no longer feasible, e.g., covered by packed items, will be removed from Lt. When there is no packable leaf node that makes nt satisfy the constraints of placement, the packing episode ends. Without loss of generality, we stipulate a vertical top-down packing within a single bin (Wang & Hauser, 2019b).
Traditional 3D-BPP literature only cares about the remaining placements for accommodating the current item nt, their packing policies can be written as π(Lt|Lt, nt). If we want to promote this problem for practical demands, 3D-BPP needs to satisfy more complex practical constraints which also act on Bt. Taking packing stability for instance, a newly added item nt has possibly force and torque effect on the whole item set Bt (Ramos et al., 2016). The addition of nt should make Bt a more stable spatial distribution so that more items can be added in the future. Therefore, our packing policy over Lt is defined as π(Lt|Tt, nt), which means probabilities of selecting leaf nodes from Lt given Tt and nt. For online packing, we hope to find the best leaf node selection policy to expand the PCT with more relaxed constraints so that more future items can be appended.
Leaf Node Expansion Schemes The performance of online 3D-BPP policies has a strong relationship with the choice of leaf node expansion schemes –– which incrementally calculate new candidate placements introduced by the just placed item nt. A good expansion scheme should reduce
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 proposed, such as Corner Point (Martello et al., 2000), Extreme Point (Crainic et al., 2008), and Empty Maximal Space (Ha et 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.

heading: 3.2 TREE REPRESENTATION
text: Given the bin configuration Tt and the current item nt, the packing policy can be parameterized as π(Lt|Tt, nt). The tuple (Tt, nt) 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 t and cannot be embedded by spectral-based approaches (Bruna et al., 2014) which require a 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 Bt,Lt, nt are presented by descriptors in different formats. We use three independent node-wise Multi-Layer Perceptron (MLP) blocks to project these heterogeneous descriptors into the homogeneous node features: ĥ = {φθB (Bt), φθL(Lt), φθn(nt)} ∈ Rdh×N , dh is the dimension of each node feature and φθ is an MLP block with its parameters θ. The feature number N should be |Bt| + |Lt| + 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(ĥi) = WO N∑ j=1 softmax
( (WQĥi)
TWK ĥj√ dk
) WV ĥj (3)

heading: Where WQ ∈ Rdk×dh , WK ∈ Rdk×dh , WV ∈ Rdv×dh , and WO ∈ Rdh×dv are projection
text: matrices, dk and dv are dimensions of projected features. The softmax operation normalizes the relation weight between node i and node j. The initial feature ĥ is embedded by a GAT layer and the skip-connection operation (Vaswani et al., 2017) is followed to get the final output features h:
h′ = ĥ + GAT(ĥ) h = h′ + φFF (h′) (4)
Where φFF is a node-wise Feed-Forward MLP with output dimension dh and h′ is an intermediate variable. Equation 4 can be seen as an independent block and be repeated multiple times with different parameters. We don’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 dv = dk. More implementation details are provided in Appendix A.

heading: 3.3 LEAF NODE SELECTION
text: Given the node features h, we need to decide the leaf node indices for accommodating the current item nt. Since the leaf nodes vary as the PCT keeps growing over time step t, we use a pointer mechanism (Vinyals et al., 2015) which is context-based attention over variable inputs to select a leaf node from Lt. We still adopt Scaled Dot-Product Attention for calculating pointers, the global context feature h̄ is aggregated by a mean operation on h: h̄ = 1N ∑N i=1 hi. The global feature h̄ is projected to a query q by matrixW q ∈ Rdk×dh and the leaf node features hL are utilized to calculate a set of keys kL by W k ∈ Rdk×dh . The compatibility uL of the query with all keys are:
q = W qh̄ ki = W khi ui = qT ki√ dk
(5)
Here hi only comes from hL. The compatibility vector uL ∈ R|Lt| represents the leaf node selection logits. The probability distribution over the PCT leaf nodes Lt is:
πθ(Lt|Tt, nt) = softmax (cclip · tanh (uL)) (6) Following Bello et al. (2017), the compatibility logits are clipped with tanh, where the range is controlled by hyperparameter cclip, and finally normalized by a softmax operation.

heading: 3.4 MARKOV DECISION PROCESS FORMULATION
text: The online 3D-BPP decision at time step t only depends on the tuple (Tt, nt) 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 st at time step t is represented as st = (Tt, nt), where Tt consists of the internal nodes Bt and the leaf nodes Lt. Each internal node b ∈ Bt is a spatial configuration of sizes (sxb , s y b , s z b) and coordinates (p x b , p y b , p z b) corresponding to a packed item. The current item nt is a size tuple (sxn, s y n, s z n). Extra properties will be appended to b and nt for specific packing preferences, such as density, item category, etc. The descriptor for leaf node l ∈ Lt is a placement vector of sizes (sxo , s y o , s z o) and position coordinates (p x, py, pz), where (sxo , s y o , s z o) indicates the sizes of nt along each dimension after an axis-aligned orientation o ∈ O. Only the packable leaf nodes which satisfy placement constraints are provided.
Action The action at ∈ A is the index of the selected leaf node l, denoted as at = index(l). The action space A has the same size as Lt. A surge of learning-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, our action space solely depends on the leaf node expansion scheme and the packed items Bt. Therefore, our method can be used to solve online 3D-BPP with continuous solution space. We also find that even if only an intercepted subset Lsub ∈ Lt is provided, our method can still maintain a good performance. Transition The transition P(st+1|st) is jointly determined by the current policy π and the probability distribution of sampling items. Our online sequences are generated on-the-fly from an item set I in a uniform distribution. The generalization performance of our method on item sampling distributions different from the training one is discussed in Section 4.4.
Reward Our reward function R is defined as rt = cr · wt once nt is inserted into PCT as an internal node successfully, otherwise, rt = 0 and the packing episode ends. Here cr is a constant and wt is the weight of nt. The choice of wt depends on the customized needs. For simplicity and clarity, unless otherwise noted, we set wt as the volume occupancy vt of nt, where vt = sxn · syn · szn. Training Method A DRL agent seeks for a policy π(at|st) to maximize the accumulated discounted reward. Our DRL agent is trained with the ACKTR method (Wu et al., 2017). The actor weighs the leaf nodes Lt and outputs the policy distribution πθ(Lt|Tt, nt). The critic maps the global context h̄ into a state value prediction to predict how much accumulated discount reward the agent can get from t and helps the training of the actor. The action at is sampled from the distribution πθ(Lt|Tt, nt) for training and we take the argmax of the policy for the test.
ACKTR runs multiple parallel processes for gathering on-policy training samples. The node number N of each sample varies with the time step t and the packing sequence of each process. For batch calculation, we fullfill PCT to a fixed length with dummy nodes, as illustrated by Figure 2 (a). These redundant nodes are eliminated by masked attention (Velickovic et al., 2018) during the feature calculation of GAT. The aggregation of h only happens on the eligible nodes. For preserving node spatial relations, state st is embedded by GAT as a fully connected graph as Figure 2 (b), without any inner mask operation. More implementation details are provided in Appendix A.

heading: 4 EXPERIMENTS
text: 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 or reproduce various online 3D-BPP algorithms, both heuristic and learning-
based, from potentially relevant literature. We help the heuristic methods to make a pre-judgment of placement constraints, e.g., stability, in case of premature downtime. The learning-based agents are trained until there are no significant performance gains. Although both Zhao et al. (2022) and Zhao et al. (2021) are learning-based methods recently proposed, we only compare with the former since it is the upgrade of the latter. We also compare with the reported results of Zhang et al. (2021) under the same condition. All methods are implemented in Python and tested on 2000 instances with a desktop computer equipped with a Gold 5117 CPU and a GeForce TITAN V GPU. We publish the source code of our method along with related baselines at Github1.
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 Sd are set to 10 with d ∈ {x, y, z} and the item sizes sd ∈ Z+ are not greater than Sd/2 to avoid over-simplified scenarios. Our performance on a 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:
Setting 1: Following Zhao et al. (2022), the stability of the Bt is checked when nt is placed. Only two horizontal orientations (|O| = 2) are permitted for robot manipulation convenience. Setting 2: Following Martello et al. (2000), item nt only needs to satisfy Constraint 1 and 2. Arbitrary orientation (|O| = 6) is allowed here. This is the most common setting in 3D-BPP literature. Setting 3: Inherited from setting 1, each item nt has an additional density property ρ sampled from (0, 1] uniformly. This information is appended into the descriptors of Bt and nt.

heading: 4.1 PERFORMANCE OF PCT POLICIES
text: We first report the performance of our PCT model combined with different leaf node expansion schemes. Three existing schemes which have proven to 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 nt with the boundary points of b ∈ Bt to get the superset, namely Event Point (EV). See Appendix B 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 a reasonable range, we only randomly intercept a subset Lsubt from Lt if |Lt| exceeds a certain length, for saving computing resources. The interception length is a constant during training and determined by a grid search (GS) during the test. See Appendix A for implementation details. The performance comparisons are summarized in Table 1.
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. It 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 Lt 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 Lsub. 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 a predefined item set |I| = 64 in setting 2. While Zhang et al. (2021) packs on average 15.6 items and achieves 67.0% space utilization, our method packs 19.7 items with a space utilization of 83.0%.

heading: 4.2 BENEFITS OF TREE PRESENTATION
text: 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) to 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., 2015), 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 Lt makes DRL agents easy to train, then we remove the internal nodes Bt from Tt, along with its spatial relations with other nodes, to prove Bt is also a necessary part. We choose EV as the leaf node expansion scheme here. The comparison results are summarized in Table 2.
If we ignore the spatial relations between the PCT nodes or only treat the state input as a flattened sequence, the performance of the learned policies will be severely degraded. The presence of B functions more on setting 1 and setting 3 since setting 2 allows items to be packed in any empty spaces without considering constraints with internal nodes. This also confirms that a complete PCT representation is essential for online 3D-BPP of practical needs.
4.3 PERFORMANCE ON CONTINUOUS DATASET
𝑧
xo The most concerning issue about online 3D-BPP is their solution space limit. Given that most learning-based methods can only work in a limited discrete coordinate space, we directly test our method in a continuous bin with sizes Sd = 1 to prove our superiority. Due to the lack of public datasets for online 3D-BPP issues, we generate item sizes through a uniform distribution sd ∼ U(a, Sd/2), a 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 sz needs to be controlled. If all subsets of Bt meet:∑
i∈Bsub1
szi 6= ∑
i∈Bsub2
szi Bsub1 6= Bsub2,Bsub1,Bsub2 ∈ Bt (7)
This means any packed items cannot form a new plane for providing support in the direction of gravity and the available packing areas shrink. Excessive diversity of sz will degenerate 3D-BPP into 1D-BPP as shown in the toy demo. To prevent this degradation from leading to the underutilization of the bins, we sample sz from a finite set {0.1, 0.2, . . . , 0.5} on setting 1 and setting 3.
We find that some heuristic methods (Ha et al., 2017) also have the potential to work in the continuous domain. We improve these methods as our baselines. Another intuitive approach for solving online 3D-BPP with continuous solution space is driving a DRL agent to sample actions from a gaussian distribution (GD) and output continuous coordinates directly. The test results are summarized in Table 3. Although the continuous-size item set is infinite (|I| = ∞) 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.

heading: 4.4 GENERALIZATION ON DIFFERENT DISTRIBUTIONS
text: The generalization ability of learning-based methods has always been a concern. Here we demonstrate 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 sd from normal distributions N(µ, σ2) for generating test sequences where µ and σ are the expectation and the standard deviation. Three normal distributions are adopted here, namely N(0.3, 0.12), N(0.1, 0.22), and N(0.5, 0.22), as shown in Figure 3. The larger µ of the normal distribution, the larger the average size of sampled items. We still control sd 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.
We directly transfer our policies trained onU(0.1, 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 a 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.

heading: 4.5 MORE COMPLEX PRACTICAL CONSTRAINTS
text: To further prove that our method fits 3D-BPP with complex constraints well, we give two demonstrations 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 category should be packed as closely as possible. The item weight is set as wt = max(0, vt − c · dist(nt,Bt)), c is a constant. The additional object function dist(nt,Bt) means the average distance between nt and the items of the same category in Bt. The additional category information is appended into the descriptors of Bt and nt. 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 as wt = max(0, vt−c ·var(nt,Bt)). Object var(nt,Bt) is the variance of the mass distribution of the packed items on the bottom of the bin.
We choose the learning-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 5. Compared with the baseline algorithm, our method better achieves the additional object while still taking into account the space utilization as the primary.

heading: 5 DISCUSSION
text: We formulate the online 3D-BPP as a novel hierarchical representation -– packing configuration tree. PCT is a full-fledged 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 constraints, 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 online 3D-BPP with continuous solution space successfully. Our method performs well even on item 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 representing 3D-BPP with different packing constraints and designing better leaf node expansion schemes for PCT are also interesting directions.

heading: ACKNOWLEDGEMENTS
text: 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).

heading: ETHICS STATEMENT
text: 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 (Skiena, 1997). Providing a 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 can also be treated as a separate decision module and utilized to 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 et al., 2017), and the logistics robot implementation for online packing (Zhao et al., 2022), which have been well studied in previous works. We give demonstrations about applying our method to solving online 3D-BPP with various complex practical constraints, the similar idea can also be adopted to meet other customized desires.

heading: REPRODUCIBILITY
text: Our real-world video demo is submitted with the supplemental material. The source code of our method and related baselines is published at https://github.com/alexfrom0815/ Online-3D-BPP-PCT.

heading: C MORE RESULTS
text: In this section, we report more results of our method. Section C.1 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 C.3 scales our method to a 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.5. Section C.6 introduces our real-world packing system.

heading: C.1 FURTHER DISCUSSIONS ON GENERALIZATION
text: We have verified in Section 4.4 that our method has good generalization performance on item sampling distributions different from the training one. Now we further analyze the generalization ability of our method. Firstly, we demonstrate that our algorithm has a good generalization performance on disturbed item sampling distributions. We conduct this experiment in the discrete setting where the item set is finite (|I| = 125). For each item i ∈ I, we add a random non-zero disturbance δi on its original sample probability pi, e.g., pi = pi ·(1−δi). We normalize the disturbed pi as the final item sampling probability. Note that δi is fixed during sampling one complete sequence. The state transition of DRL P(st+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 probabilities. Generalizing to a new transition is a classic challenge for reinforcement learning (Taylor & Stone, 2009). We test different ranges of δi and the results are summarized in Table 6.
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 δi ∈ [−100%, 100%] applied, which means some items may never be sampled by some distributions when δi = 1 and pi · (1− δi) = 0 in a specific sequence. Beyond experiments on generalization to disturbed distributions, we also test our method with unseen items. We conduct this experiment in the discrete setting. We randomly delete 25 items from I and train PCT policies with |Isub| = 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.

heading: C.2 RUNNING COSTS
text: 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 Table 8. Each running cost at time step t is counted from putting down the previous item nt−1 until the current item nt 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.

heading: C.3 SCALABILITY
text: 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|, we conduct a stress test on setting 2 where the most orientations are allowed and the most leaf nodes are generated. We limit the maximum item sizes sd to Sd/5 so that more items can be accommodated. We transfer the best-performing policies on setting 2 (trained with EMS) to these new datasets without any fine-tuning. The results are summarized in Table 9.
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. |I| =∞), however, |L| still doesn’t explode with |B| and it grows in a sub-linear way. Our method can execute packing decisions at a real-time speed with controllable PCT sizes even if the item scale is around two hundred.

heading: C.4 UNDERSTANDING OF MODEL BEHAVIORS
text: The qualitative understanding of model behaviors is important, especially for practical concerns. We visualize our packing sequences to 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 a fixed corner (Figure 7 (a)). The learned policies tend to 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)). If additional packing preference is considered, the learned policies behave differently. For online 3DBPP with load balancing, the model will keep the maximum height in the bin as low as possible and pack items layer by layer (Figure 7(e)). For online 3D-BPP with isle friendliness, our model tends to pack the same category of items nearby the same bin corner (Figure 7 (f)).
C.5 VISUALIZED RESULTS
We visualize the experimental results of Section 4.1 in Figure 8. Each plot is about a randomly generated item sequence packed by our best-performing policies (PCT & EV on setting 1 and setting 3, PCT & EMS on setting 2).
C.6 REAL-WORLD PACKING SYSTEM
We follow the online autonomous bin packing system implementation of Zhao et al. (2022) in a logistics warehouse 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 onconveyor RGB-D camera (PhoXi 3D Scanner XL) recognizes the size and location of the current item. This information is sent to 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 a table trolley with sizes Sx = 110cm, Sy = 90cm, and Sz = 80cm. We record sizes and positions of packed items as descriptors of internal nodes B.
Different from the original implementation of Zhao et al. (2022) where only one on-conveyor camera is 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 a 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 b ∈ B with the offset position. We use items with sx and sy ranging from 20cm to 40cm, and sz ranging from 10cm to 25cm. We fill items with paddings of the same density and train PCT policies on setting 1 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.

Review summaries:
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.

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.