AI Laser Metal Cutting - Part 1
Replacing humans by AI optimization as a servicePosted: 2023-06-14
The Optimizer - part 1
Timeline: 2009-2020. Potentially reducing CO2 globally by 1%.
"We made an AI and attached it to a 6kW laser cutting machine!" ;).
On a more serious note. Discrete optimization problems are ubiquitous and you will find them in many domains. Laser cutting of sheet metal is no exception. Sheet metal cutting is a crucial part of the multi-billion-dollar metalworking industry, serving various sectors like automotive, aerospace, construction, electronics, and more. It's used for producing parts such as car body panels, aircraft components, building facades, electronic casings, and countless other metal parts. The optimization of this process is crucial, given the industry's size, to save on costs and reduce waste. Specifically the optimization of the placement of parts to be cut, on one or more sheets, is the problem we will touch on in these posts.
The Nesting Problem in sheet metal cutting is similar to arranging as many gingerbread cookies as possible onto a baking sheet without any overlap, aiming to utilize the entire surface. Each cookie represents a part to be cut from the sheet, and the goal is to minimize the leftover or wasted dough (the unused metal), while fitting all the desired cookie shapes (metal parts). This is a complex task that involves deciding the best layout of the "cookies" to minimize waste.
The Nesting Problem is a type of 2D packing problem, a combinatorial optimization or discrete optimization problem. The problem becomes increasingly complex as the number of different parts and sizes increase. Solving this problem efficiently can lead to significant cost savings, by minimizing waste and maximizing the usage of raw materials. It also reduces the environmental impact by minimizing scrap metal.
The problem is further complicated by issues such as heat expanding the metal sheet, customers having requirements on the rotations and flipping of parts, and avoiding risks such as a part tilting and potentially destroying the cutting head causing expensive production outages. The side constraints are many and not always obvious.
Parts can also contain empty areas, or holes, inside the outer geometry that also can be used for placing smaller parts. Parts can generally have any rotation or flip transformation unless specifically disallowed.
This results in a truly mind-boggling search space, and not unsurprisingly this is one of the hardest problems in computer science, an NP-hard problem. Such fun!
Various algorithms and heuristic are used to tackle this problem, like the bottom-left placement algorithm, the best-fit algorithm, and metaheuristic algorithms such as Local Search, Simulated Annealing, Genetic Algorithms, and many many more. In practice, one often seeks to find a good enough solution that significantly reduces waste, even if it isn't the optimal solution.
During my time at Tomologic, I was fortunate to work with these very interesting and fun challenges that often gave rise to equally interesting and very often hard or at least tricky sub-problems, very rarely did anyone on the team go: "Well, that was easy!"
2D Nesting pre-Tomologic
After that brief introduction to Nesting, let's get into the actual issue at hand. Nesting, as it was (is?) used in the industry, produces an uncomfortable amount of waste due to some simplifications that are introduced to "solve" certain production requirements.
Assumption 1: Place parts individually. This is achieved by introducing a safety distance around each part. This ensures that parts do not get in the way of the cutting head, since that may cause damage to it, which would cause a production interruption associated with a high cost. This is incidentally also the root of the waste problem.
Assumption 2: Cut parts independently. The cutting path (how to move the laser cutting head), is basically just solving a (also NP-hard) Traveling Salesman Problem for each sheet since each part can be cut individually. There are naturally exceptions. Fun fact: when cutting many small parts you may actually want to cut in a way as to spread out the heat as much as possible, that is, not the shortest path.
These two simplifications allow the algorithms to use significant simplifications on how geometries are represented, and how the placement of parts is performed. Combined, this significantly reduces the computational effort needed to explore the search space.
In the next two parts, I will talk more about Tomologic's view of Nesting and how we solved a more involved problem to achieve up to 50% reduction in waste material and up to 30% reduction in cutting time.