Geometry-Aware Reinforcement Learning for 2D Irregular Nesting
cs.LG, cs.CV
Submitted: 2026-06-09
Updated: 2026-09-18
Comments: 20 pages, 6 figures, 7 tables. Under review at the Transaction on Machine Learning Research (TMLR)
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: Traditional heuristic solvers for the 2D irregular nesting problem share a fundamental limitation: they are blind to polygon geometry, relying on guided brute-force to navigate the continuous
Terminology
Abstract
Traditional heuristic solvers for the 2D irregular nesting problem share a fundamental limitation: they are blind to polygon geometry, relying on guided brute-force to navigate the continuous placement space with minimal geometrical guidance. In this paper, we argue that Reinforcement Learning is uniquely positioned to overcome this bottleneck. By pairing an optimization policy with a geometry-aware neural encoder, an agent can automatically discover rich geometric priors directly from data, utilizing these learned intuitions to strategically guide exploration. To realize this, we introduce the Polygons Transformer (PoT), a novel architecture that encodes 2D continuous vector geometries while allowing cross-polygon attention. We couple this novel architecture with a Combinatorial Optimization Reinforcement Learning (CORL) training framework to find optimal solutions. To support this paradigm, we release an open-source training dataset derived from complex geographic contours alongside a dedicated evaluation benchmark. Empirically, our agent slightly exceeds Sparrow, the state-of-the-art heuristic, on small (4-polygon) instances, while a clear scaling gap remains on larger (8-polygon) instances.
Sources
- Neural Combinatorial Optimization with Reinforcement Learning
- Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization
- Combinatorial Optimization with Policy Adaptation using Latent Space Search
- An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks