A vision-based intelligent system for packing 2-D irregular shapes

Packing two-dimensional shapes on a surface such that no shapes overlap and the uncovered surface area is minimized is an important problem that arises in a variety of industrial applications. This paper introduces an intelligent system which tackles the most difficult instance of this problem, where two-dimensional irregular shapes have to be packed on a regularly or irregularly shaped surface. The proposed system utilizes techniques not previously applied to packing, drawn from computer vision and artificial intelligence, and achieves high-quality solutions with short computational times. In addition, the system deals with complex shapes and constraints that occur in industrial applications, such as defective regions and irregularly shaped sheets. We evaluate the effectiveness and efficiency of the proposed method using 14 established benchmark problems that are available from the EURO Special Interest Group on Cutting and Packing. Note to Practitioners-Packing two-dimensional shapes on a surface such that no shapes overlap and the uncovered surface area is minimized is an important problem that arises in a variety of industrial applications, such as shipbuilding, textile, wood, plastic, sheet metal, and leather manufacturing. Although effective and efficient methods have been developed for packing rectangular parts on a rectangular sheet, this is not the case for the most difficult instance of the problem, namely packing irregular parts on an irregularly shaped sheet. This paper presents an automated system that utilizes techniques not previously applied to packing, drawn from computer vision and artificial intelligence, and succeeds in achieving high-quality solutions in short computation times. These techniques enable the system to "look" at the layout during the placement of the parts, and find potential matches of the unplaced ones within the unoccupied regions of the sheet. By integrating a vision system, this new method is: 1) fully automated since no human interference is needed (e.g., the input shapes of the parts an the sheet need not be given manually); 2) highly compatible with robotic applications within manufacturing where the initial positions and orientations of the parts are not precisely known, since the proposed method is not sensitive to the initial configurations of the parts; and 3) flexible in packing parts effectively on a surface with unexpected defective regions. We evaluate the performance of the proposed method using 14 established benchmark problems.