• 
• 
• 
• 
• 
• 

Human-Guided Search for Packing

We designed both automatic and interactive systems for tightly packing a given set of rectangles, without overlap, into a larger rectangle of fixed width. This is important for industrial problems in which a large number of variable-sized rectangles must be cut from a sheet of material, such as metal, glass, or wood. The goal is to minimize waste by packing the rectangles as tightly as possible. Our automatic method significantly improves on the best automatic method we found in the literature. Furthermore, we found that people can reason about packing problems extremely well. Our interactive system allows people to apply packing algorithms to quickly produce much tighter packings than the packing algorithms can produce without guidance.

Background & Objective:  We have worked on what is referred to in the literature as the two-dimensional rectangular strip packing problem. The goal is to pack a given set of rectangles as tightly as possible, to minimize wasted space. This problem appears unamenable to standard local search techniques, such as simulated annealing or genetic algorithms. A standard simple heuristic, Bottom-Left-Decreasing (BLD), has been shown to handily beat these more sophisticated search techniques.

Technical Discussion:  We have developed and demonstrated the effectiveness of BLD*. Furthermore, we observe that people seem able to reason about packing problems extremely well. We incorporate our new algorithms in an interactive system that combines the advantages of computer speed and human reasoning. Using the interactive system, we are able to quickly produce significantly better solutions than previous methods on benchmark problems.

Technology Areas:
Sensor and Data Systems
Artificial Intelligence

Modification Date:  October 3, 2007