Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Manufacturing Algebras for Algorithmic Automation

View Current Project Information

Anand Kulkarni1 and Ken Goldberg

National Science Foundation

The design of automated physical manufacturing systems and assembly lines today is still a “black art” relying on guesswork and rules of thumb rather than algorithmic treatment. A rigorous mathematical framework for representing and optimizing assembly line operations has the potential to dramatically reduce costs and increase efficiency in automated manufacturing environments.

To this end, we are defining logical algebras formally representing relationships between primitive parts and primitive operations during the assembly process. By defining assembly relationships in abstract terms that are independent of the underlying physical parameters, such manufacturing algebras may be applied to test and compare geometric, cost, and manufacturability properties of an object under differing physical implementations of part orienters and other assembly tools.

While many of the associated optimization problems are NP- and PSPACE-hard, we are working on finding and solving approximate variants that are computationally tractable. As a first result, we have demonstrated how a small universal set of operations may be applied to near-optimally assemble arbitrary constructions made from LEGO bricks in two and three dimensions using a small set of primitive blocks. We have also produced polynomial-time algorithms for finding minimum-cost assembly sequences for a large class of LEGO objects when the number of parallel paths during assembly is bounded.

Figure 1
Figure 1: Proof that the 2 x 1/3 primitive brick is universal for sets built from a standard 2 x 2 block, with a valid minimum stable assembly sequence

1IEOR PhD Student