Deliberate planning of 3D bin packing on packing configuration trees

Abstract

The 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, that is, candidate placements, making the DRL model easy to train and well-performing even with continuous solution space. We further discover the potential of PCT as tree-based planners in deliberately solving packing problems of industrial significance, including large-scale packing and different variations of the BPP setting. A recursive packing method is proposed to decompose large-scale packing into regular sub-trees while a spatial ensemble mechanism integrates local solutions into a global one. For different BPP variations with additional decision variables, such as lookahead, buffering, and offline packing, we propose a unified planning framework enabling various problem-solving based on a pre-trained PCT model with no additional adaptation. Extensive evaluations demonstrate that our method outperforms existing online BPP baselines and is versatile in incorporating various practical constraints. Driven by PCT, the planning process excels across large-scale problems and diverse problem variations, with performance improving as the problem scales up and the decision variables grow. To verify our method, we develop a real-world packing robot for industrial warehousing, with careful designs accounting for constrained placement and transportation stability. Our packing robot operates reliably and efficiently on unprotected pallets at 9.8 seconds per box. It achieves averagely 19 boxes per pallet with 57.4% space utilization for large-size boxes.