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

🦌🦌🦌读论文

我们的系统共同探索离散设计变量和制造计划的空间，以生成（设计，制造计划）对的帕累托前沿，使制造成本最小化。在该图中，(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)绘制了从我们的管道计算的帕累托前沿，其中选择了三种设计变化。

🐼6.1多材料和切割工具

出于机械或美学原因，设计者可能需要将多种材料（如不同类型的木材或木材和金属）结合在一个模型中。

🐼6.2目标

我们的方法也自然扩展到其他目标函数。

🐼6.3收敛性

虽然我们的结果表明了该方法在实践中降低制造成本的重要性，但我们不能保证我们输出的计划位于全局最优的Pareto前沿。

🐨🐨7局限性和未来工作

我们当前的方法仅在BOP E-图中编码离散设计变体。

🐨🐨8结论

我们提出了一种新的方法来共同优化模型设计变体及其制造计划。我们的方法依赖于这样一个洞察：不同设计变体的制造计划将共享类似的结构。

🦌🦌🦌做笔记

🐕🐕该文章的研究目的

🐈优化设计与制造计划

文章旨在通过共同优化木工对象的设计与制造计划来最小化制造成本。研究者们提出了一种新的方法，能够同时探索设计变体和制造计划，以找到最佳的解决方案。

🐕🐕该文章的研究方法

🐈双层优化问题

文章采用了双层优化的方法来处理设计和制造计划。上层优化问题涉及设计和制造计划的联合空间，而下层优化问题则是给定设计的可行制造计划空间。

🐈等价图（E-图）

研究者们使用等价图（e-graphs）来表示等价程序，通过共享子结构来优化设计组件。他们提出了一种新的数据结构——零件集合（BOP）E-图，以最大化共享并提高e-图的表现力。

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

文章介绍了一种名为ICEE的反馈引导搜索策略，用于控制e-图的大小并引导搜索朝着有希望的候选者发展。ICEE通过迭代收缩和扩展e-图来有效地探索设计和制造计划的巨大组合空间。

🐕🐕文章的挑战点

🐈设计与制造计划空间的巨大

设计变体和制造计划的空间巨大，使得使用当前技术联合探索这两个空间变得不切实际。

🐈多目标优化问题

制造计划可能需要在多个目标之间进行权衡，如材料浪费、制造时间、精度等，这增加了优化问题的复杂性。

🐈计算可行性

由于优化空间的快速增长，计算上可行的优化方法成为实现双层优化的关键挑战。

🐕🐕该文章的研究内容

🐈设计与制造的联合优化

文章研究了如何联合优化设计和制造计划，以找到在多个目标之间取得最佳权衡的解决方案。

🐈BOP E-图的开发

研究者们开发了一种新的BOP E-图数据结构，用于紧凑地表示设计变体和制造计划，并最大化共享。

🐈ICEE算法的实现

文章实现了ICEE算法，该算法通过迭代收缩和扩展e-图来有效地探索设计和制造计划的空间。

🐕🐕该文章的创新点

🐈BOP E-图

BOP E-图是一种新的数据结构，它允许在设计和制造计划之间共享公共子结构，从而提高了优化过程的效率。

🐈ICEE算法

ICEE算法是一种创新的搜索策略，它结合了反馈引导的搜索和e-图的紧凑表示，以有效地管理和探索巨大的设计和制造计划空间。

🐈双层优化的可行性

文章展示了如何使双层优化问题在计算上可行，这对于复杂的设计和制造领域是一个重要的突破。

🐕🐕该文章给我们的启发

🐈跨领域方法的应用

文章展示了如何将程序合成和等价图的概念应用于设计和制造领域，这为跨学科研究提供了新的视角。

🐈优化策略的创新

ICEE算法提供了一种新的优化策略，可以在其他领域中应用，以解决具有复杂搜索空间的优化问题。

🐈设计与制造的集成

文章强调了设计和制造过程的集成，这提示了在产品设计阶段就考虑制造因素的重要性，以实现更高效的生产过程。