Learning Practically Feasible Policies for Online 3D Bin Packing

 SCIENCE CHINA Information Sciences 2022


Hang Zhao1    Chenyang Zhu1    Xin Xu1    Hui Huang2    Kai Xu1*

1National University of Defense Technology    2Shenzhen University




Figure 1 Online 3D-BPP has widely practical applications in logistics, manufacture, warehousing, etc. Left: The agent can only observe the next item to be packed (shaded in red). Right: More items (shaded in green) can be observed with additional sensors.


Abstract

We tackle the Online 3D Bin Packing Problem, a challenging yet practically useful variant of the classical Bin Packing Problem. In this problem, the items are delivered to the agent without informing the full sequence information. Agent must directly pack these items into the target bin stably without changing their arrival order, and no further adjustment is permitted. Online 3D-BPP can be naturally formulated as Markov Decision Process (MDP). We adopt deep reinforcement learning, in particular, the on-policy actor- critic framework, to solve this MDP with constrained action space. To learn a practically feasible packing policy, we propose three critical designs. First, we propose an online analysis of packing stability based on a novel stacking tree. It attains a high analysis accuracy while reducing the computational complexity from O(N2) to O(N logN), making it especially suited for RL training. Second, we propose a decoupled packing policy learning for different dimensions of placement which enables high-resolution spatial discretization and hence high packing precision. Third, we introduce a reward function that dictates the robot to place items in a far-to-near order and therefore simplifies the collision avoidance in movement planning of the robotic arm. Furthermore, we provide a comprehensive discussion on several key implemental issues. The extensive evaluation demonstrates that our learned policy outperforms the state-of-the-art methods significantly and is practically usable for real-world applications.


Figure 2 The environment state of the agent. The grey boxes indicate the items already packed, which also represents the bin configuration. The green box is the next item to be packed and it can only be placed at the grid cell where feasibility mask M is 1. Right: The network architecture with decomposed actor-heads. Note that the training of three actor-heads is coupled with conditional probabilistic dependencies, actor-heads perform their prediction tasks in sequence.



Figure 5 Left: The red box packed in the middle of the bin first introduces potential collisions for the following packing. Right: If the robot always enters the packing area at the same entrance line, packing on the green area may introduce fewer potential collisions.



Figure 6 We implement our system in a practical industry environment. Left: The online autonomous bin packing system with an RGB-D sensor and a robot arm. Right: The digital twin which constructed by our method based on the captured data.



Figure 7 Visualization of the ablation study. The numbers beside each bin are space uti. and # items.



Figure 11 (a): Segmentation result under BPP-1 view. (b): The item n is labeled with an anchor, its dimension and location are recognized. (c): Segmentation result under BPP-k (k is a variable) view. (d) If multiple items are observed by the camera, we sort their positions and select the first one in the queue.




Figure 12 Visual examples are given by our robot implementation. The robot places items in a far-to-near order and reduces collisions with packed items.



Acknowledgements

We thank Qijin She, Yin Yang, Kun Huang, Yixing Lan, Kaiwen Li, Junkai Ren, and Yao Duan for active discussions. Thanks also go to Hanchi Huang for maintaining a good community to communicate reinforcement learning related technologies. This paper is supported in part by National Key Research and Development Program of China (2018AAA0102200), NSFC (62132021, 61825305, 62002375, 62002376, 62102435), NUDT Research Grants (ZK19-30), DEGP Key Project (2018KZDXM058), GD Science and Technology Program (2020A0505100064), and Shenzhen Science and Technology Program (JCYJ20210324120213036).


Bibtex

@article{BinPacking22,

title={Learning Practically Feasible Policies for Online 3D Bin Packing},

author={Hang Zhao and Chenyang Zhu and Xin Xu and Hui Huang and Kai Xu},

journal={SCIENCE CHINA Information Sciences},

volume={65},

pages={112105:1--112105:18},

year={2022},

}



Downloads (faster for people in China)

Downloads (faster for people in other places)