Hacker's Handbook

AI Laser Metal Cutting - Part 2

Replacing humans by AI optimization as a service

Posted: 2023-06-15

The Optimizer - part 2

Timeline: 2009-2020. Potentially reducing CO2 globally by 1%.

2D packing — extra everything

Let's dive into the specifics. 2D packing, what is the actual problem we aim to solve?

For simplicity, assume we have 20 unique irregular polygons (without holes) of various shapes and sizes that all fit together on a single sheet with room to spare. Also, let's disallow rotations and flips, and assume we use a greedy left-bottom placement strategy; there are 20! (20! = 20•19•18•...1) ways to place these polygons (if we include symmetrical solutions). Each solution will result in some amount of waste, and typically the goal is trying to produce as short a horizon as possible, since after making a cut at the horizon there may be a useable part of the sheet left over to use down the line. You can naturally have both vertical and horizontal horizons, but that is just more of the same.

There is no reasonable approach that will let us place and evaluate all 20! orders of parts, this is why this is a hard problem (adding 1 more part makes the problem 21 times bigger). A typical packing problem could easily have hundreds of unique parts with up to thousands of copies each, resulting in a huge number of parts to be placed. This is why all software employs heuristic approaches when trying solve these problems.

Now, imaging allowing flips and rotations, and optimizing over multiple sheets. Fun!

At Tomologic we had a fundamentally different approach compared to 2D Nesting at the time. The core idea is to reduce the waste and cutting time as much as possible. We achieved this by incorporating some brilliant insights and knowledge of the the cutting process from the founder of Tomologic, a long time laser machine operator. Basically, we took his know-how and created algorithms to make it automatic and systematic. We created a knowledge-based AI system. He invented some brilliant methods for controlling heat conduction and cut part stability.

We removed assumption 1 (place parts individually) and 2 (cut parts independently) which, together with our proprietary cutting patterns, allowed us to create clusters of almost any shapes. Our algorithms and valuation models allowed us to compute an estimated multidimensional cost for a particular cluster of parts, taking into account how it needs to be split and cut to guarantee production safety without all that waste. The revolutionizing idea lies in our algorithms for controlling how heat spreads through the metal sheet and how to keep parts from moving and tilting during the cutting process, and taking this into account when creating the packing and cutting paths.

Thus we created an even more complicated 2D packing problem, where the cutting path is part of the packing problem and the cost of cutting a cluster of parts depends on where on the sheet it is placed since location impacts how to cut. This interdependency makes it so much harder. In addition to this, by removing assumption 1 and 2, we are also faced with a precision problem that traditional Nesting does not have — since we are cutting clusters of parts, we need to guarantee the cut parts are within acceptable tolerances when measured. When making a cut between two parts (not simply straight lines), this puts additional complexity on placement algorithms. Even when we do use safety distances, these are also optimized based on the characteristics of adjacent parts or clusters. We also needed a clever constraint engine to handle how parts interact and produce pockets of waste between them.

To make it better (and harder) we also allowed free rotations, where most Nesting allows rotations in discrete increments (e.g. 5 degrees). This basically makes our search space infinite, at least in theory, in a practical implementation rotations are limited by 64-bit floating point numbers.

So, how does one get any results at all given this daunting scope? You need a great team, a dash of creativity, and a lot of hard work.