Deliberate Planning of 3D Bin Packing on Packing Configuration Trees

• URL: http://arxiv.org/abs/2504.04421v3
• Date: Tue, 29 Apr 2025 08:56:40 GMT
• Title: Deliberate Planning of 3D Bin Packing on Packing Configuration Trees
• Authors: Hang Zhao, Juzhan Xu, Kexiong Yu, Ruizhen Hu, Chenyang Zhu, Kai Xu,
• Abstract summary: Online 3D Bin Packing Problem (3D-BPP) has widespread applications in industrial automation.<n>We propose to enhance the practical applicability of online 3D-BPP via learning on a novel hierarchical representation, packing configuration tree (PCT)<n>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)
• Score: 40.46267029657914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online 3D Bin Packing Problem (3D-BPP) has widespread applications in industrial automation. 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. 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 BPP setting. A recursive packing method is proposed to decompose large-scale packing into smaller sub-trees while a spatial ensemble mechanism integrates local solutions into global. For different BPP variations with additional decision variables, such as lookahead, buffering, and offline packing, we propose a unified planning framework enabling out-of-the-box problem solving. Extensive evaluations demonstrate that our method outperforms existing online BPP baselines and is versatile in incorporating various practical constraints. The planning process excels across large-scale problems and diverse problem variations. 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 10 seconds per box. It achieves averagely 19 boxes per pallet with 57.4% space utilization for relatively large-size boxes.

Related papers

• Optimizing 2D+1 Packing in Constrained Environments Using Deep Reinforcement Learning [0.6827423171182154]
  This paper proposes a novel approach based on deep reinforcement learning (DRL) for the 2D+1 packing problem with spatial constraints.<n>A simulator using the OpenAI Gym framework has been developed to efficiently simulate the packing of rectangular pieces onto two boards with height constraints.
  arXiv  Detail & Related papers  (2025-03-21T23:06:16Z)
• GOPT: Generalizable Online 3D Bin Packing via Transformer-based Deep Reinforcement Learning [12.801743977971434]
  GOPT is a generalizable online 3D Bin Packing approach via Transformer-based deep reinforcement learning (DRL) We propose a Packing Transformer, which fuses the features of the items and bin, to identify the spatial correlation between the item to be packed and available sub-spaces within the bin. We conduct extensive experiments and demonstrate that GOPT achieves superior performance against the baselines, but also exhibits excellent generalization capabilities.
  arXiv  Detail & Related papers  (2024-09-09T06:02:17Z)
• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications. We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately. By introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• 360 Layout Estimation via Orthogonal Planes Disentanglement and Multi-view Geometric Consistency Perception [56.84921040837699]
  Existing panoramic layout estimation solutions tend to recover room boundaries from a vertically compressed sequence, yielding imprecise results. We propose an orthogonal plane disentanglement network (termed DOPNet) to distinguish ambiguous semantics. We also present an unsupervised adaptation technique tailored for horizon-depth and ratio representations. Our solution outperforms other SoTA models on both monocular layout estimation and multi-view layout estimation tasks.
  arXiv  Detail & Related papers  (2023-12-26T12:16:03Z)
• Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation [52.560375022430236]
  Bin Packing Problem (BPP) is a well-established optimization (CO) problem. In this article, we first formulate BPP, introducing its variants and practical constraints. Then, a comprehensive survey on machine learning for multi-dimensional BPP is provided.
  arXiv  Detail & Related papers  (2023-12-13T12:39:25Z)
• Convolutional Occupancy Models for Dense Packing of Complex, Novel Objects [75.54599721349037]
  We present a fully-convolutional shape completion model, F-CON, that can be easily combined with off-the-shelf planning methods for dense packing in the real world. We also release a simulated dataset, COB-3D-v2, that can be used to train shape completion models for real-word robotics applications. Finally, we equip a real-world pick-and-place system with F-CON, and demonstrate dense packing of complex, unseen objects in cluttered scenes.
  arXiv  Detail & Related papers  (2023-07-31T19:08:16Z)
• Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers [0.8434687648198277]
  We introduce a hybrid quantum-classical framework for solving real-world three-dimensional Bin Packing Problems (Q4RealBPP) Q4RealBPP permits the solving of real-world oriented instances of 3dBPP, contemplating restrictions well appreciated by industrial and logistics sectors.
  arXiv  Detail & Related papers  (2023-03-01T14:04:50Z)
• Planning Irregular Object Packing via Hierarchical Reinforcement Learning [85.64313062912491]
  We propose a deep hierarchical reinforcement learning approach to plan packing sequence and placement for irregular objects. We show that our approach can pack more objects with less time cost than the state-of-the-art packing methods of irregular objects.
  arXiv  Detail & Related papers  (2022-11-17T07:16:37Z)
• A Deep Reinforcement Learning Approach for Constrained Online Logistics Route Assignment [4.367543599338385]
  It is crucial for the logistics industry on how to assign a candidate logistics route for each shipping parcel properly. This online route-assignment problem can be viewed as a constrained online decision-making problem. We develop a model-free DRL approach named PPO-RA, in which Proximal Policy Optimization (PPO) is improved with dedicated techniques to address the challenges for route assignment (RA)
  arXiv  Detail & Related papers  (2021-09-08T07:27:39Z)
• Learning Practically Feasible Policies for Online 3D Bin Packing [36.33774915391967]
  We tackle the Online 3D Bin Packing Problem, a challenging yet practically useful variant of the classical Bin Packing Problem. 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.
  arXiv  Detail & Related papers  (2021-08-31T08:37:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.