Communications of the ACM
Technical Perspective: A Woodworker's Easy Fix
I like woodworking. I have built quite a number of pieces of furniture, like cabinets, shelves, beds, and tables, as well as a ladder, a shack, and other things. Not being professionally trained, I restrict myself to simple construction projects, for which I trust my intuition on stability. For more complex constructions I stick to the standards I find in books. This obviously limits my freedom.
As a computer scientist, I know it would be possible to check the validity of a construction using physical simulation. If the panels chosen are the right type (thickness or kind of wood), the main structural problems are where the pieces come together—in the joints. Each joint bears linear and rotational forces; the result of the weight of the wood itself and the stuff being put onto or into the object (for example, the person on a ladder). There are natural limits to these forces in the joints, which I could find in the literature. Given all this information (combinatorial structure of the panels, dimensions, loads, limits on joint forces) checking validity is a straightforward project in scientific computing.
Now, what would I have gained from this programming project? If the computer tells me my construction is stable I can go ahead and build it. But what if it does not confirm? I would change my design and try again. This is obviously a tedious exercise. Nonetheless, this "workflow" is the current design standard.
Wouldn't it be much better if the computer told me how to fix my construction? Or, even better, offered several ways to fix it, so that I could just chose one? Certainly yes, but this is a difficult problem. Just as in NP problems: deciding if a given answer is correct is easy, but finding one is hard. Here, the technical difficulty is the large dimension and the mixed discrete-continuous nature of the design space: each panel has two dimensions, each joint has numerous parameters, and some constructions can only be fixed by changing the combinatorial structure (typically adding a panel), hence the mixed discrete-continuous space.
Nonetheless, the authors of the following paper have found a way to provide the user with instant feedback on how to fix unstable or toppling wooden panel constructions. They formulate the desired goal as finding small design changes, that is, the length of the vector of design parameter changes is minimal.
The solution to this problem requires several key ingredients: First, it is easier to check for validity in the space of joint forces. So, for the current design, they linearize the connection between the design space and the 'force space' (and make some additional simplifying assumptions). This allows them to quickly check if a small change in the design space leads to a feasible construction. Still, the dimension of the design space is too large to find short vectors that make the construction feasible. The second main idea is to limit the change to only a few independent parameters, while the rest stay fixed. This limitation drastically reduces the dimension of the search space, not only making it feasible to compute solutions (for all possible combinations of changeable parameters), but also easier to understand the suggested modification for the human user in the loop. Lastly, discrete changes are restricted to adding a panel, and the location of the panel is based on established rules.
Together with some additional features in the user interface, the resulting system really solves the problem of developing, rather than just checking, wood panel constructions. As a woodworker, I cannot wait to get my hands on this system. As a computer scientist, I am more interested in the general solution for the interactive search of feasible solutions in a high-dimensional design space—this solution will serve as a blueprint for a variety of related design problems.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.