Co-Optimization of Design and Fabrication Plans for Carpentry
Co-Optimization of Design and Fabrication Plans for Carpentry
复制标题
DOI：
10.1145/3508499
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Haisen Zhao;Max Willsey;Amy Zhu;Chandrakana Nandi;Zach Tatlock;J. Solomon;Adriana Schulz
中科院分区：
文献类型：
--
作者：
Haisen Zhao;Max Willsey;Amy Zhu;Chandrakana Nandi;Zach Tatlock;J. Solomon;Adriana Schulz
给定一个木工设计，以往优化制造方案的工作能够提供在材料浪费、制造时间、精度和其他考虑因素之间进行权衡的帕累托最优方案。然而，在制定制造方案时，专家们很少局限于单一设计，而是会考虑一系列设计变体，有时会调整设计以简化制造。使用现有技术联合探索每个设计的设计和制造方案空间是难以处理的。我们提出了一种新方法，用于联合优化木工制品的设计和制造方案。为了使这种双层优化易于处理，我们采用了基于等式图（e - 图）的程序合成的最新研究成果，等式图对等效程序集进行编码。我们的见解是，我们的双层问题中的子问题具有大量共享子结构。通过在一个新的零件包（BOP）e - 图中表示设计和制造方案，我们分摊了优化多个候选方案中共享的设计组件的成本。即使使用BOP e - 图，在实际应用中优化空间也会迅速增大。因此，我们还展示了一种被称为“e - 图上的迭代收缩与扩展”（ICEE）的反馈引导搜索策略如何能够使e - 图的大小易于管理，并引导搜索朝着有希望的候选方案进行。我们通过木工领域的实例说明了我们的流程的优势。
Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design, instead considering families of design variations, sometimes adjusting designs to simplify fabrication. Jointly exploring the design and fabrication plan spaces for each design is intractable using current techniques. We present a new approach to jointly optimize design and fabrication plans for carpentered objects. To make this bi-level optimization tractable, we adapt recent work from program synthesis based on equality graphs (e-graphs), which encode sets of equivalent programs. Our insight is that subproblems within our bi-level problem share significant substructures. By representing both designs and fabrication plans in a new bag of parts (BOP) e-graph, we amortize the cost of optimizing design components shared among multiple candidates. Even using BOP e-graphs, the optimization space grows quickly in practice. Hence, we also show how a feedback-guided search strategy dubbed Iterative Contraction and Expansion on E-graphs (ICEE) can keep the size of the e-graph manageable and direct the search towards promising candidates. We illustrate the advantages of our pipeline through examples from the carpentry domain.