Source-linked AI summary
Online 3D Bin Packing with Constrained Deep Reinforcement Learning
Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, Kai Xu
TL;DR
Online 3D-BPP requires packing partially observed items immediately while avoiding collisions and unstable placements. The paper formulates this as a constrained Markov decision process and trains an actor-critic DRL policy with feasibility prediction and action projection. The resulting method outperforms existing methods and reaches human-level performance in a preliminary user study.
Problem
Online 3D-BPP must handle limited item information, immediate placement, no readjustment, collision avoidance, and physical stability.
Method
The paper combines constrained actor-critic DRL with height-map state representation, feasibility prediction, action-probability modulation, and permutation search for lookahead items.
Results
The learned policy outperforms existing methods and achieves 68.9% average space utilization versus 52.1% for human players over 1,851 games.
Takeaways & Limitations
The approach generalizes to lookahead items, multi-bin packing, item re-orienting, and permutation-based search over multiple incoming items.
Takeaways & Limitations
The method assumes integer dimensions, restricts each item dimension to at most half the corresponding bin dimension, and uses a conservative support-based stability criterion.
Abstract
from arXiv · showhide
We solve a challenging yet practically useful variant of 3D Bin Packing Problem (3D-BPP). In our problem, the agent has limited information about the items to be packed into the bin, and an item must be packed immediately after its arrival without buffering or readjusting. The item's placement also subjects to the constraints of collision avoidance and physical stability. We formulate this online 3D-BPP as a constrained Markov decision process. To solve the problem, we propose an effective and easy-to-implement constrained deep reinforcement learning (DRL) method under the actor-critic framework. In particular, we introduce a feasibility predictor to predict the feasibility mask for the placement actions and use it to modulate the action probabilities output by the actor during training. Such supervisions and transformations to DRL facilitate the agent to learn feasible policies efficiently. Our method can also be generalized e.g., with the ability to handle lookahead or items with different orientations. We have conducted extensive evaluation showing that the learned policy significantly outperforms the state-of-the-art methods. A user study suggests that our method attains a human-level performance.
1 Introduction
3D-BPP is practically important but difficult because real packing may reveal only a limited item sequence and require immediate, stable placement without readjustment. The paper addresses these constraints with constrained DRL and reports better performance than existing methods, including human-level results in a user study.
- Problem importance: Efficient bin packing can reduce inventorying, wrapping, transportation, and warehousing costs in parcel logistics.The paper identifies large-scale parcel packaging as a representative application.
- Practical constraints: Real-world online packing differs from most existing 3D-BPP settings because item information is limited, placement is immediate, and repacking is disallowed.These settings also require order-dependent packing and physical stability.
- Approach: The paper formulates online 3D-BPP as a constrained Markov decision process and solves it with an on-policy actor-critic DRL method.The method accommodates order dependence and stable stacking during placement.
- Approach: A feasibility predictor produces placement masks that modulate actor action probabilities, helping the policy learn feasible actions efficiently.The method also generalizes to lookahead items, multi-bin packing, and item re-orienting.
- Results: The learned policy outperforms existing methods by a noticeable margin and reaches human-level performance in a preliminary user study.The paper reports this as the outcome of extensive testing and validation.
2 Related Work
Prior work establishes bin packing as a hard combinatorial optimization problem, while higher-dimensional and exact methods become impractical at realistic scales. The paper positions constrained DRL within this landscape and represents packing states with structured spatial information.
- 1D-BPP: 1D-BPP research includes greedy heuristics, approximation algorithms, exact solutions, and benchmark implementations such as BPPLib.The related literature also covers practical variants such as cutting stock.
- 2D- and 3D-BPP: 2D- and 3D-BPP add geometric feasibility constraints requiring non-overlap and containment, substantially increasing complexity.Exact methods can be generalized from 1D, but realistic 3D parcel-packing instances remain infeasible to solve exactly.
- Deep reinforcement learning: DRL research spans on-policy and off-policy methods that learn policies from agent-environment interaction data or replayed experience.The paper draws on DRL's broader success in high-dimensional control tasks.
- Paper representation: The paper uses a height-map representation to encode the bin configuration and tensors to represent the next item's dimensions.Figure 2 also presents a feasibility mask and the network architecture with auxiliary losses.
- RL for combinatorial optimization: RL has also been applied to combinatorial optimization, including heuristic selection and NP-hard problems such as TSP.This work extends that research direction to constrained online 3D packing.
3 Method
The method models online 3D bin packing as a constrained Markov decision process and uses actor-critic DRL to place each arriving item immediately under feasibility and stability constraints. It represents the bin with a height map, predicts feasible placement locations, projects actor probabilities toward feasible actions, and searches permutations for lookahead items.
- Online 3D-BPP exposes only immediately incoming items, requires immediate placement without adjustment, and constrains item dimensions to at most half the bin dimensions.
- The state combines a discretized bin height map with the dimensions of the current and available lookahead items.For BPP-1, only the current item is observed; BPP-k extends the state with k items.
- Each action places the item’s front-left-bottom corner at a grid location, after which the height map is updated deterministically over the cells covered by the item.
- Placement feasibility requires sufficient space and conservative support conditions that enforce physical stability despite unknown item mass distributions.The criteria require specified percentages of bottom-area support and combinations of supported bottom corners.
- The constrained DRL agent uses ACKTR actor-critic learning, with a step-wise volumetric occupancy reward and a composite loss for policy, value, mask prediction, infeasibility, and entropy terms.The action entropy is computed over feasible actions, while the feasibility mechanism penalizes infeasible placement probabilities.
- For lookahead items, Monte Carlo permutation tree search tests alternative placement orders without additional training while respecting arrival-order dependence.
4 Experiments
Experiments show that the proposed representation and constraint-based training improve packing quality and feasibility, while extensions preserve useful efficiency and generality. The method outperforms online baselines across benchmarks and exceeds human performance in the reported user study.
- Ablation study: Feasibility mask prediction, mask-constrained projection, and feasibility-based entropy each contribute to final packing performance.Removing mask prediction causes a significant drop, omitting mask constraints impairs performance, and feasibility-based entropy benefits training and final results.
- Height parameterization: 16.0% and 19.1% higher space utilization is achieved by HM than HV and ISV, respectively, on CUT-1.HM also packs 4.3 and 5.0 more items than HV and ISV, respectively.
- Constraint vs. reward: 99.5% of placements predicted by constraint-based DRL are legitimate, outperforming reward tuning for discouraging unsafe placements.The comparison evaluates learning invalid moves through mask prediction against penalizing unsafe placements with negative rewards.
- Scalability of BPP-k: MCTS takes 3.6s at k = 20, whereas brute-force permutation search exceeds 100s at k = 8 and becomes computationally intractable for larger k.The MCTS permutation search has slightly lower space utilization, but is substantially more efficient than brute-force search.
- 3D-BPP variants: Allowing item re-orientation increases space utilization by 11.6% and average items packed by 3 on the RS dataset.The extension doubles the action space by representing two horizontal, axis-aligned orientations per item.
- Comparisons: 66.3% average space utilization over 50 random sequences exceeds boundary rule at 39.2% and online BPH at 43.2%.In a preliminary real-robot BPP-1 test, the method also outperforms the reported online alternatives across all three benchmarks and beats the offline approach on CUT-1 and CUT-2.
5 Conclusion
The paper formulates online 3D-BPP with order-dependence and physical-stability constraints as a CMDP and solves it using constrained DRL. Supplemental sections document implementation, benchmarks, user studies, rewards, and additional experiments.
- Conclusion: The method combines an actor-critic framework, height-map representation, and feasibility prediction to optimize policies under order and stability constraints.For multiple lookahead items, MCTS searches over item permutations.
- Supplementary materials: The supplement provides additional network, training, benchmark, user-study, reward, and experiment details.These materials are organized across Sections B–H.
- Supplementary materials: Additional experiment results are reported in Section H.
B Implementation Details
The implementation uses actor, critic, and feasibility-mask components trained with a composite loss. Extensions support lookahead, multiple bins, and item re-orientation, with MCTS selecting among future item orders.
- Network architecture and training: The network contains actor, critic, and feasibility-mask predictor components that process the height map, current-item dimensions, and training mask.The ground-truth feasibility mask is used only during training.
- Network architecture and training: Training combines actor, critic, mask-prediction, infeasibility, and action-entropy losses.
- Training objectives: The reward measures space utilization as 10×l_n·w_n·h_n/(L·W·H), while an unplaceable item receives zero reward and ends the sequence.The discount factor is set to 1, so the return directly represents obtainable utilization from the current state.
- Training objectives: The actor’s action probabilities are scaled by feasibility information and then normalized with softmax; infeasibility penalties may be omitted during testing.
- Lookahead packing: MCTS searches for the best packing order among the next k items using maximum reward rather than mean reward.
- Multi-bin packing: For multiple bins, the item is assigned to the bin whose estimated state-value change produces the highest packing score.
- Item orientation: Allowing m orientations multiplies the feasibility mask and action space by m, increasing packing flexibility.The supported orientation changes occur around the Z axis.
C Benchmark Construction
The benchmark construction uses a predefined item set and generates sequences through random sampling or cutting-stock procedures. These designs support quantitative evaluation when optimal configurations are unavailable for random sequences.
- Dataset construction: The dataset is constructed from bin dimensions and a valid item-size threshold, using 64 predefined items.
- Random benchmark: Random sequences sample each item from the predefined set, but their optimal packing configurations are generally unknown without exhaustive search.
- Cutting-stock benchmark: Cutting-stock generation provides additional item sequences for quantitative evaluation.
D Heuristic Baseline Method
The heuristic baseline measures packing regularity through spare cuboids, favoring placements that preserve large, versatile rectangular residual spaces.
- Heuristic motivation: The boundary-rule baseline is motivated by keeping packed volume regular so that large residual spaces remain available.
- Spare cuboid: A spare cuboid is an unoccupied rectangular region, and bin regularity is based on the maximum spare cuboids.
- Heuristic score: Each maximum spare cuboid is scored by the number of valid item types it can contain plus its volume, with an additional reward when it fits all predefined items.
- Heuristic score: The baseline scores a placement by summing maximum-spare-cuboid rewards and selects the position with the best score.
E User Study
The user study app lets participants inspect packed items from multiple angles, preview suggested placements, and make placement decisions without a time limit.
- User study interface: The interface combines 3D visualization with an action space showing suggested placements for the current item.Users can change the viewing angle and select suggestion circles to preview placements virtually.
- Study procedure: Test sequences are randomly selected from the CUT-2 test set.
- Study procedure: When no suitable placement exists, the test resets and saves the selected sequence.
F Reward function design
The study compares step-wise and termination rewards for online packing. Termination reward performs similarly on CUT-1 and CUT-2, especially when additional state information resolves height-map ambiguity.
- Reward definitions: The step-wise reward assigns volume-based reward after each successful placement, whereas termination reward uses final capacity utilization only when packing ends.The step-wise reward is rn = 10 × l_n · w_n · h_n/(L · W · H); termination reward sums item volumes relative to bin volume.
- Reward comparison: Termination reward can perform similarly to step-wise reward on the CUT-1 and CUT-2 benchmarks.
- Reward comparison: Additional information makes termination-reward performance nearly equal to step-wise reward by resolving ambiguity in the state input.The added information indicates whether free space exists below the height map.
G Penalized reward
The penalized-reward alternative rewards successful placements and penalizes physically unstable ones, but it does not guarantee safe placement during testing.
- Penalized reward: The reward-guided alternative rewards successful placement according to item volume and penalizes physical-stability violations with −1 before terminating the sequence.
- Comparison: Explicitly penalizing unsafe placements still leaves occasional test-time mistakes, unlike the constraint-based DRL method.
H More Results
Additional experiments examine resolution, boundary heuristics, generalization, DRL frameworks, and benchmark construction. The results show modest resolution sensitivity, benefits from learned strategic placement, some generalization, and strong performance for ACKTR within the tested frameworks.
- Action-space resolution: Increasing bin resolution from 10×10×10 to 30×30×30 only slightly decreases performance while making problem complexity approximately 27× larger.Higher discretization widens the action distribution and dilutes the optimal action’s weight.
- Boundary strategy: Imposing the corner-and-boundary rule reduces average reward by about 20%, whereas the method learns when to apply it for globally better packing.
- Learned versus heuristic strategy: Packing the red item between existing items reserves space for subsequent moves and allows three more items to be packed in the same sequence.
- Unseen items: The method demonstrates some generalizability when trained on 40 items and tested on the complete predefined item set.
- Additional generalization tests: The experiments also evaluate untrained sequences and an expanded predefined item set of 125 types.The expanded items satisfy l ≤ L/2, w ≤ W/2, and h ≤ H/2.
- DRL frameworks: ACKTR achieves the fastest convergence and best performance among the tested DRL frameworks on CUT-2.The comparison includes A2C, DQN, RAINBOW, and SAC.