I-Corps: Deep-Scale Evolution for Industrial Shape Nesting

Northern Michigan University, Marquette MI

Investigators

Abstract

The broader impact/commercial potential of this I-Corps project is the development of an approach to manufacturing that may reduce material waste by fifty percent (50%). Manufacturers cutting shaped pieces from expensive substrates (steel, titanium, leather, composites) use shape nesting software to fit as many pieces as possible on substrate blanks and remnants to minimize wasted material. However, current shape nesting software often falls short of optimal material usage. Current products nest shapes sequentially, placing each piece on the substrate one after another. The proposed technology is designed to improve the placement of items on a 2D substrate more efficiently. The technology is based on the simulated evolution of multiple, inter-dependent species into a tightly knit, stable and productive ecosystem. The result is a substantial reduction in wasted material. In the auto industry, for example, the proposed technology may more tightly nest body parts to be cut from steel sheets, reducing the amount of raw steel needed as well as the scrap steel, which requires substantial energy to melt and reuse. The technology may be applied to cloth and leather (textiles), aluminum and steel (shipbuilding), or titanium and composites (aerospace). The reductions in scrap may make the US economy more efficient and workers more productive. Reduced demand for mined metals may have environmental benefits, as will the reduced need for landfill space (since trim waste is often unusable). More efficient manufacturing of parts from raw materials may provide for sustainable resource management, save energy, lower greenhouse gas emissions, reduce pollution and the strain on ecosystems, and make final products more affordable for consumers. This I-Corps project is based on the development of an algorithm for simulating evolution of cooperation using an ecosystem strategy. The proposed algorithm for deep-scale evolution uses massively-parallel simultaneous consideration of global layout patterns, a new approach distinct from the sequential piece placement and local layout decisions used in available nesting products. Millions of species (each a possible placement of a shaped piece on a flat substrate in 2D nesting) compete to cover the 2D material. The biggest set of cooperating (i.e., non-competing) species emerges. The ecosystem perspective favors large sets of cooperative species over individual, locally successful species. Co-evolutionary selection pressure pushes the population toward globally optimal total solutions. This emphasis on cooperative groups of solution components often will find tighter, more efficient nestings of 2D shapes (or packings of 3D pieces) than current sequential techniques that place one shape at a time, or pack one item before the next. Recent studies comparing commercial 2D shape nesting software products on one problem showed that the proposed technology nested twelve pieces, while the commercial product offerings nested only ten or eleven. The performance of the proposed technology for both speed and output quality may be used to scale up to larger nesting problems from industry. Based on the evolution of populations, the algorithm is inherently massively parallel. As with deep learning neural networks, the proposed approach depends on the exponential growth in computing power of graphics processing units (GPUs). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.