Reinforcement learning for the shape nesting problem

This thesis addresses the “2D Irregular Packing problem”, a combinatorial optimization challenge with significant applications in industries such as manufacturing, furniture production, textiles and aerospace. The problem focuses on efficiently arranging two-dimensional objects of irregular shapes on a surface with the goal of minimizing unused space and maximizing material utilization. Given the problem’s NP-complete nature, finding an optimal solution is computationally infeasible for most real-world scenarios. As a result, in literature approximate solutions are typically sought using heuristic and metaheuristic algorithms. This thesis first addresses the nesting problem through the algorithms present in the literature. The geometric problem of positioning a polygon into a hole or relative to another polygon is treated with two methods: the Envelope Polygon and the No-Fit Polygon. These geometric methods are then used by the two main approaches to solve nesting: the first decomposes the problem into a placement algorithm (e.g., the Bottom Left) and a sequencing algorithm like the Genetic Algorithm; the second approach, allowing temporary overlaps of polygons by progressively reducing the area that acts as the container and swapping polygons, finds the optimal sequence for this heuristic approach. Subsequently, although it is still a largely unexplored field, reinforcement learning (RL) is applied to the nesting problem to solve the sequencing problem and the Bottom Left for polygon placement. In reinforcement learning, the machine learns through interaction with the environment, by trial and error. Particularly, two main algorithms of RL are applied to nesting: SARSA and Monte Carlo. SARSA updates the sequence based on state-action pairs encountered, while the Monte Carlo relies on complete episodes for learning. The results indicate that RL algorithms outperform conventional approaches in terms of space utilization in some instances. This suggests that integrating machine learning into combinatorial optimization could bring significant economic and environmental benefits. In conclusion, an improvement of the state of art is proposed by changing a reinforcement learning parameter, specifically the exploration parameter. This led to achieve better results than those found in the literature with RL. This is done by exploring more sequences in the first few episodes, then decreasing exploration and doing more exploitation once you gain more knowledge of the environment.