Mitigating Dimensionality in 2D Rectangle Packing Problem under Reinforcement Learning Schema

• URL: http://arxiv.org/abs/2409.09677v1
• Date: Sun, 15 Sep 2024 09:58:48 GMT
• Title: Mitigating Dimensionality in 2D Rectangle Packing Problem under Reinforcement Learning Schema
• Authors: Waldemar Kołodziejczyk, Mariusz Kaleta,
• Abstract summary: This paper explores the application of Reinforcement Learning (RL) to the two-dimensional rectangular packing problem. We propose a reduced representation of the state and action spaces that allow us for high granularity.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper explores the application of Reinforcement Learning (RL) to the two-dimensional rectangular packing problem. We propose a reduced representation of the state and action spaces that allow us for high granularity. Leveraging UNet architecture and Proximal Policy Optimization (PPO), we achieved a model that is comparable to the MaxRect heuristic. However, our approach has great potential to be generalized to nonrectangular packing problems and complex constraints.

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. 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)
• A Framework for Reducing the Complexity of Geometric Vision Problems and its Application to Two-View Triangulation with Approximation Bounds [14.419727000332717]
  Triangulation is the task of estimating a 3D point from noisy 2D projections across multiple images. We present a new framework for reducing the computational complexity of geometric vision problems through targeted reweighting of the cost functions used to minimize reprojection errors. Although this work focuses on two-view triangulation, the framework generalizes to other geometric vision problems.
  arXiv  Detail & Related papers  (2025-03-11T08:00:51Z)
• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  We study optimization methods that leverage the linear minimization oracle (LMO) over a norm-ball. We propose a new family of algorithms that uses the LMO to adapt to the geometry of the problem and, perhaps surprisingly, show that they can be applied to unconstrained problems.
  arXiv  Detail & Related papers  (2025-02-11T13:10:34Z)
• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds [59.875550175217874]
  We show that a simple Model-based Reinforcement Learning scheme achieves strong regret and sample bounds in online and offline RL settings. We highlight that our algorithms are simple, fairly standard, and indeed have been extensively studied in the RL literature.
  arXiv  Detail & Related papers  (2024-08-16T19:52:53Z)
• Concise Plane Arrangements for Low-Poly Surface and Volume Modelling [9.254047358707016]
  We introduce two key novelties that enable the construction of plane arrangements for complex objects and entire scenes. We show that our approach leads to state-of-the-art results by comparing it to learning-based and traditional approaches on various different datasets.
  arXiv  Detail & Related papers  (2024-04-09T09:27:54Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• High-dimensional Linear Bandits with Knapsacks [8.862707047517913]
  We study the contextual bandits with knapsack (CBwK) problem under the high-dimensional setting where the dimension of the feature is large. We develop an online variant of the hard thresholding algorithm that performs the sparse estimation in an online manner. We show that this integrated approach allows us to achieve a sublinear regret that depends logarithmically on the feature dimension.
  arXiv  Detail & Related papers  (2023-11-02T15:40:33Z)
• Learning Gradient Fields for Scalable and Generalizable Irregular Packing [28.814796920026172]
  The packing problem, also known as cutting or nesting, has diverse applications in logistics, manufacturing, layout design, and atlas generation. Recent advances in machine learning, particularly reinforcement learning, have shown promise in addressing the packing problem. In this work, we delve deeper into a novel machine learning-based approach that formulates the packing problem as conditional generative modeling.
  arXiv  Detail & Related papers  (2023-10-18T15:52:55Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Learning based 2D Irregular Shape Packing [29.044043493942013]
  2D irregular shape packing is a necessary step to arrange UV patches of a 3D model within a texture atlas for memory-efficient appearance rendering in computer graphics. We introduce a learning-assisted 2D irregular shape packing method that achieves a high packing quality with minimal requirements from the input. In order to efficiently deal with large problem instances with hundreds of patches, we train deep neural policies to predict nearly rectangular patch subsets.
  arXiv  Detail & Related papers  (2023-09-19T05:21:52Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization [96.1052289276254]
  We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule. We map all existing solvers in a single framework, allowing for a better understanding of their design principles.
  arXiv  Detail & Related papers  (2020-04-16T15:49:13Z)
• Regret Minimization in Partially Observable Linear Quadratic Control [91.43582419264763]
  We study the problem of regret in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose a novel way to decompose the regret and provide an end-to-end sublinear regret upper bound for partially observable linear quadratic control.
  arXiv  Detail & Related papers  (2020-01-31T22:35:08Z)

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.