计算机图形学论文 | 木工设计与制造计划的共同优化

🦌🦌🦌读论文

我们的系统共同探索离散设计变量和制造计划的空间，以生成（设计，制造计划）对的帕累托前沿，使制造成本最小化。在该图中，(a)是椅子的输入设计和仅探索该设计的制造方案空间的帕累托前沿，(b)是由椅子的设计变体和制造方案共同探索生成的帕累托前沿，其中每个点是一个（设计，制造方案）对。设计变化表明不同的方式组成相同的3D模型从一个集合的部分，并在帕累托前面用相同的颜色说明。实物椅子是按照结果制作计划制作的。联合勘探的帕累托面优于(a)的帕累托面，这表明通过探索设计变化可以显著提高制造成本。

🐨🐨0摘要

本文提出了一种新方法，用于同时优化木工对象的设计与制造计划。通过自适应基于等价图（e-graphs）的程序合成中的近期工作，我们将双层优化问题变得可行。我们的洞察是，双层问题中的子问题共享显著的子结构。通过在新的零件集合（BOP）e-图中表示设计和制造计划，我们分摊了优化多个候选者中共享的设计组件的成本。即使使用BOP e-图，优化空间在实践中也迅速增长。因此，我们还展示了一种名为E-图迭代收缩和扩展（ICEE）的反馈引导搜索策略，它可以保持e-图的大小可控，并将搜索导向有希望的候选者。我们通过木工领域的示例来说明我们的流程的优势。

🐨🐨1引言

虽然针对制造的优化设计是一个长期且研究充分的工程问题，但绝大多数工作都假设从设计到制造计划有一个唯一的映射。然而，在现实中，许多应用允许多种制造替代方案。例如，模型显示了不同的制造计划在材料成本和制造时间之间的权衡。在这种情况下，面向制造的设计优化变得更加具有挑战性，因为它需要为许多设计变体探索最优制造计划的景观。在这项工作中，我们提出了一种新的方法，同时优化木工的设计与制造计划。我们的方法也使用类似程序的表示，但我们同时优化设计和制造计划。

🐨🐨2相关工作

🐼2.1设计与制造的优化

面向制造的设计是一个激动人心的研究领域，旨在自动实现所需的属性，同时优化制造计划。

🐼2.2木工的设计和制造

木工是设计和制造中研究充分的领域，因为它的应用范围广泛。

🐼2.3双层多目标优化

我们的问题和类似的问题都是双层的，具有嵌套结构，其中每个设计确定不同的可行制造计划空间。

🐼2.4E-图

E-图是一种高效的数据结构，用于紧凑地表示大量等价程序。

🐨🐨3背景

为了提高文章的可读性并帮助读者更早地获得必要的背景知识，本节介绍了文章其余部分使用的一些数学基础。

🐼3.1多目标优化

多目标优化问题由一组目标函数fi定义，这些函数为可行搜索空间X中的每个点x分配一个实数值。我们选择的约定是目标fi需要较小的值fi (x)。由于这些目标通常是相互冲突的，我们的算法搜索代表最佳权衡的不同点集，称为帕累托最优，所有帕累托最优点的图像称为帕累托前沿。

🐼3.2双层多目标优化

给定一个定义木工模型可能变体的设计空间D，我们的目标是找到一个设计d和相应的制造计划p，以最小化冲突目标的向量。

🐼3.3等价图（E-图）

通常，程序（通常称为项）被视为包含较小子项的树状结构。e图是一种数据结构，它通过尽可能地共享子项来有效地表示许多等效项，解决大型程序面临的搜索等效项的空间难以处理的问题。

电子图示例：e类（用字母标记的虚线框）包含等价的e节点（实框），它们指代子e类（ar-行）。e类(c)包含一个叶子e节点3，它代表一个项3。e类(b)包含两个e节点，(c)+(c)和(c)∗(d)，它表示两个项：3+3和3∗2。虽然e类(a)只包含一个e节点，但它表示4项：(3+3)+(2+2)、(3∗2)+(2+2)、(3+3)+4和(3∗2)+4。如果+比*便宜，则(3 + 3)+ 4是e类(a)表示的最便宜的项。

🐨🐨4优化算法

我们的算法以具有离散集合D的可能设计变体的木工设计为输入。设计变体决定了将3D模型分解为一组可制造部件的不同方式，如下边两个图所示。这些可以手工生成，也可以自动生成。我们的目标是找到制造成本最小的帕累托最优解决方案，其中每个解决方案是一对设计变化和制造计划。

一个模型的三种不同的设计变化的例子和相应的制造计划。设计变型决定了将3D模型分解成一组零件的不同方式。制造计划定义这些零件如何在库存材料和切割顺序中排列（通过每次切割的数字来说明）。

设计变化空间的例子：四个连接器中的每一个都可以有三种不同的连接变化，从而产生81种设计变化。请注意，一些不同的设计变型可能使用相同的部件（如d1， d2），并且在我们的优化过程中会被视为冗余。这个模型生产13个独特的零件袋。

🐼4.1动机和洞察

给定一个算法，用于为给定设计找到Pareto最优的制造计划，一个蛮力方法将简单地为D中的每个可能设计变体d找到Pareto最优解，并取主导者形成组合设计/制造空间的Pareto前沿。

🐼4.2零件集合（BOP）E-图

我们的算法选择一个Pareto最优的制造计划集合，每个计划将产生给定模型的一个设计变体。

在一个BOP e图(b)中编码了箱体设计的两个变体(a)。粗体边缘表示需要三个原子填充的根项(c)。BOP e图为两个设计变体编码了多种排列。e类用虚线框表示，并用该e类表示的BOP进行标注。(只有e-节点在语义上是在e-graph中；名称和BOP只是视觉辅助。)e类E1和E2是根e类，因为它们表示设计变体所需的BOP。联合和原子e节点分别以带“U”的正方形或带“A”的圆形表示。原子电子节点对应于一块库存(c)中的零件包装。BOP e图中的一个示例根项是持有的。

🐼4.3迭代收缩和扩展E-图（ICEE）

算法概述使用上边那张图中的示例。第一步初始化防喷器e图（第4.3.2和4.3.3节），其中包含几个设计变量和少量制造安排(a)。U和a分别表示联合和原子e节点。作为ICEE循环的一部分，该算法提取了一个帕累托前沿（第4.3.4节），用于对防喷器e图(b)中的e类进行评分。例如，包含“U”和“a”e节点的灰色e类表示得分较低，即该e类对帕累托最优解没有贡献。然后，通过移除低分数的e类（及其父e节点）来压缩防喷器e图（第4.3.5节），得到压缩的防喷器e图(c)。如第4.3.6节所述，通过探索更多的设计变量和制造安排，进一步扩展(d)这个压缩的防喷器e图。当终止条件达到时，算法退出循环，返回最终的帕累托前沿(e)。

🐶4.3.1概述

ICEE以可行的设计空间D作为输入，并输出每个解决方案s代表一个（设计，制造）对的Pareto前沿。

🐶4.3.2初始设计变体的生成

我们通过观察启动我们的搜索，即具有更多相同部件的设计变体往往更便宜，因为它们在制造过程中花费的时间较少。

🐶4.3.3制造安排的生成

同样，我们不是为给定设计随机生成Kf个安排变体，而是使用启发式方法。

🐶4.3.4Pareto前沿提取

在e-图术语中，提取是从e-图中根据某些（通常是单目标）成本函数选择“最佳”表示的项的过程。

🐶4.3.5BOP E-图收缩

随着算法的进行，BOP E-图收缩保持数据结构不会变得过大。

🐶4.3.6BOP E-图扩展

我们通过首先生成新的设计变体，然后为现有和新生成的设计变体生成制造安排来扩展BOP E-图。

🐨🐨5结果与讨论

第5节中所有实验使用的模型。布朗用于表示仅由木材的一维连续切割制成的模型。灰色仅用于板材的二维分割。橙色用于同时使用木材的1D顺序切割和板材的2D分割。

为了衡量我们工具的实用性，我们希望回答以下问题：

🐼5.1模型

我们使用图7中的示例来评估我们的方法。

🐼5.2运行环境

我们根据模型的复杂性（以部件数量np和设计空间|D|的大小来衡量）来调整ICEE算法中使用的参数。

🐼5.3设计探索的好处

为了证明同时探索设计变体和制造计划空间的好处，我们将我们的工具与仅优化单一设计的制造计划进行了比较。下方第一张图强调了探索设计变化如何生成制造计划，这些计划可以支配那些没有设计变化探索产生的计划。然后，第二张图展示了设计变化如何实现不同的权衡，从而节省不同的成本。

搜索设计空间的两个例子揭示了制造计划，这些计划完全支配了为输入设计生成的制造计划。通过设计变化，我们的管道可以搜索框架的设计变化，将所有角度切割变为垂直。对于设计B，我们找到了一个比输入设计中耗时最少的计划a花费更少时间的制造计划。同样，我们展示了A-Bookcase模型的两个制造方案，其中设计和制造方案B主导了输入设计a。制造成本在图中按照材料成本、精度误差和制造时间的顺序表示。切割订单用彩色的圆点和数字标记，其中颜色表示选择的切割工具，堆叠的切割用相同的数字标记。

两个例子表明，探索不同的设计会导致更广泛的计划多样性，其中帕累托前面的每一个权衡都是可能的，因为底层设计。窗口提供了一个更简单的例子。设计A非常统一，只有三个不同的部分。这种设计很容易节省制作时间，因为我们可以将切口堆叠在不同的库存上。设计B的特点是更多样的剪裁，不像A，每条边都是一样长的。这种不规则性使得所有的零件都可以有效地重新排列在两张纸上。常规零件不能很好地配合，导致浪费。材料成本很低，但由于包装紧密，每一次切割都需要更多的时间。书柜的例子展示了一些不直观的设计决策是如何节省成本的。在这个例子中，设计A的两个长而相同的侧件意味着更多的堆叠机会，制造计划充分利用了这一点。这种设计实现了非常低的时间成本，但使用了大量的材料。设计B的左侧被架子分开，没有第二个长片，可以将所有的碎片打包到一块木材上。在这里，使用的材料是经济的，但木匠必须花时间从复杂的布局中切割出碎片。

🐼5.4与专家的比较

对于每个模型，我们要求木工专家生成设计变体和制造计划。生成的点在下图中绘制为菱形。

帕累托前沿是从我们的管道中计算出来的，设计优化为彩色点。每种颜色对应不同的设计。灰点表示所有探索过的设计变化的帕累托前沿。这些与没有设计优化计算的帕累托前沿（仅制造优化，使用原始模型作为输入设计）作为正方形和专家制造计划作为菱形进行比较。通常，来自设计变体的制造计划比由输入设计生成的制造计划更优化。对于客观度量的单位，材料使用量（fc）以美元为单位，切割精度（fp）以英寸为单位，制造时间（ft）以分钟为单位。用大写字母表示的一些（设计、制造计划）对如图9和图10所示。

🐼5.5性能评估

为了测试BOP E-图的共享是否对我们工具的性能至关重要，我们将其实现在基于Carpentry Compiler的嵌套优化管道上进行了比较。

🐼5.6制造结果

我们通过根据我们的工具生成的设计变体-制造计划对构建一些模型来验证我们的流程。

两种窗变的制作结果。不同的设计和制造计划权衡了制造时间和材料的使用。

🐨🐨6讨论

混合材料的织机模型，其中两种木材（云杉胶合板和中密度纤维板）和一种金属（铝板）分配到每个部分。

帕累托前沿计算从我们的管道框架模型有三个目标函数，材料使用fc，制造时间ft和稳定性性能。每个设计变化的物理稳定性用Abaqus/CAE 2021模拟，用最大位移（Max U）测量。所有位移都以英寸为单位。在此图中，(a)是一个方向上的位移可视化，(b)是相同设计但方向不同的位移可视化，(c)绘制了从我们的管道计算的帕累托前沿，其中选择了三种设计变化。