Turn-it：优化线材重构雕塑制造

🐨文章摘要abstract

• 电线雕塑在工业应用和日常生活中都很重要。

• 本文提出了一种新的制造策略，通过调整目标形状以适应电线弯曲机，然后由人工将其弯曲回目标形状。（机器弯曲+人工弯曲）

• 该方法通过两阶段弯曲策略实现，首先在机器弯曲阶段创建输入电线的变形版本，然后在人工弯曲阶段由人工将其弯曲回目标形状。

🐨关键词keyword

电线雕塑、电线制造、电线重配置、计算制造。

🐨背景background

🐼研究对象

本文的研究对象是电线雕塑，电线雕塑在艺术形式中具有独特的美学吸引力，同时也在工业领域中发挥着重要作用。

🐼术语

调谐点：简言之就是需要进行调整的点，在图里用红点表示

目标导线：机器生成的曲线。

协调导线：通过调整最小数量的弯曲角度来生成的无碰撞协调线

ORP问题：机器人领域的最优重构规划问题

---

补充：ORP问题

最优重构规划（Optimal Reconfiguration Planning, ORP）问题在机器人领域通常涉及如何在给定的约束和目标条件下，优化机器人的配置或路径，以实现特定的任务或功能。这种问题在多种应用场景中都非常重要，例如机器人操作、自动化制造、移动机器人导航等。

ORP 问题的基本概念

1. 重构：在机器人领域，重构通常指的是调整机器人组件或机器人的整体结构，以适应不同的任务或环境。这可能包括改变机器人关节的位置、调整工具或手臂的姿态等。

2. 最优性：ORP 问题的“最优”部分通常意味着在多个可能的配置中，选择一个最优解。这个最优解可以基于多个标准，如能量消耗、时间效率、路径长度、执行成本等。

3. 规划：规划涉及制定一系列动作或步骤，以实现从初始状态到目标状态的转换。对于机器人来说，这可能包括路径规划、动作序列的确定、碰撞避免等。

ORP 问题的关键要素

1. 状态空间：机器人可能的配置或状态的集合。状态空间的复杂性直接影响规划算法的效率和可行性。

2. 目标函数：定义“最优”的标准，例如最小化能耗、时间、运动距离或最大化任务完成的成功率等。

3. 约束条件：机器人在执行重构时需要满足的条件，例如物理限制、工作环境的限制（如障碍物）、操作安全等。

4. 动作模型：描述机器人如何在状态之间转换的模型，包括各种可用动作的定义和效果。

ORP 问题的求解方法

1. 搜索算法：使用图搜索算法（如 A* 或 Dijkstra 算法）在状态空间中找到最佳路径。

2. 优化算法：应用优化技术（如遗传算法、粒子群优化等）来找到最佳配置。

3. 动态规划：在需要考虑时间序列的情况下，可以使用动态规划来求解。

4. 学习方法：使用机器学习或强化学习方法，通过数据驱动的方式优化重构策略。

应用场景

1. 多机器人系统：在协作任务中，多个机器人需要重构其任务分配和运动路径，以实现最佳的整体效果。

2. 工业机器人：在自动化制造中，机器人可能需要根据生产需求调整其工作姿态和工具配置。

3. 移动机器人：在复杂环境中，移动机器人需要实时重构其路径以避开障碍并优化行进时间。

---

🐼关键挑战

1.关键的挑战在于调整最小数量的弯曲点，这被表述为“优化线材重构”问题。

线材弯曲机所能产生的复杂性和几何细节在很大程度上受到无碰撞约束的限制，这种约束不允许线材在弯曲过程中与机身发生任何自碰撞和全局碰撞，因为碰撞会破坏物理制造过程；（简单来讲就是说，机器弯曲的限制在于，在完成某些形状时，前边弯曲好的部分会与机器发生碰撞，造成后续弯曲无法进行的情况，如中间这张图所示）

（记住这个图，这个图表示了无碰撞约束）

因此，折线机只能处理简单或规则的几何形状，例如平面杆结构[Miguel et al. 2016]和欧拉导线[Lira et al. 2018]，用于抽象3D形状。我们很好奇，是否有可能极大地扩大金属丝弯曲机可以制造的物体范围，比如具有艺术吸引力的金属丝结构。

2.另一个挑战是OWR问题。机器生成的线我们叫目标导线，目标导线的形状是未知的，我们的目标是从输入导线（生成目标导线，再）生成无碰撞的调谐导线，这个目标问题就是OWR问题。其挑战性在于，由于其指数搜索空间，其中每个输入弯曲角都有其调谐自由，因此在计算上具有挑战性。更重要的是，无碰撞的全局约束进一步增加了它的难度。

🐼文章贡献

1.开发了一种将人工协作与线材弯曲机相结合的线材弯曲方法。（机器弯曲+人工弯曲）

2.生成一种全自动计算框架：首先，将输入导线拟合到一组可制造的弯曲线段中，如3D线段和圆形线段，使拟合的线段和圆形线段满足弯曲制造约束。其次，通过双层优化生成调谐线材，其中上层优化侧重于选择要调谐的弯曲点，而下层优化旨在确定调谐角度，同时考虑消除所有碰撞。

3.探索了一种加权波束搜索策略，以权衡搜索效率和解决方案质量。

🐨相关工作

🐼计算制造

[Bickel et al. 2018；Matusik and Schulz 2019；Umetani et al. 2015]

🐼利用增材或减法制造来创建3D几何图形

[Martínez等人，2016；Narumi et al. 2023；Wu et al. 2016；Yue et al. 2017；Zhong et al. 2023]

🐼机器的雕塑弯曲

[Xu等人，2018]和[Liu等人，2017]应用折弯机制造弹性变形的金属丝结构，作为产生的动态金属丝特征的骨架。

问题：它们的金属丝结构具有相对简单的几何形状

🐼增加制造线雕塑的复杂性——“分解-组装”策略

[Miguel et al. 2016]使用一组平面杆线轮廓抽象出目标形状，然后计算稳定性感知装配序列；[Lira et al. 2018]和[Bhundiya and Cordero 2023]将导线抽象分解成一系列可制造的欧拉导线，然后用连接器进行组装。

🐼弯曲序列本身的规划

[Baraldo等人，2022]专注于优化折线机的弯曲顺序，而[Liu等人，2023]则提出了一种运动规划算法，用于机器人手臂与折线机协作，执行3D金属丝弯曲。

🐼人工弯曲过程中辅助人类弯曲的方法

[Yang et al. 2021]提供了弯曲导线的详细说明。[Iarussi等人，2015]，[Torres等人，2016]和[Tojo等人，2024]计算了可打印的物理支撑结构，使用户能够将导线缠绕在突出的结构上。[Wang et al. 2019]在给定模型的3D表面上生成凹槽，并将其打印为线模结构。[Garg et al. 2014]通过激光切割创建3D支架，并对平面钢丝网材料进行标记，以辅助钢丝网的弯曲过程。

🐼最优重构规划

[Hou and Shen 2010]证明了链式模块化机器人ORP问题的np -完备性。ORP涉及搜索在不同机器人配置之间转换所需的最小重构步骤数，这带来了许多应用，包括魔方蛇的转换[Zhang等人，2022]，基于可折叠链的转换[Zhang等人，2023]，家具重构[Song等人，2017]，单线结构的基于链的物理转换[Yu等人，2019]。

---

本文工作与典型ORP问题目标的同：

• 最小数量的调谐弯曲点对应于最少数量的重构步骤。

• 论文中使用的角度调谐算子在链式模块化机器人的重新配置中也很常见。

异：

• 弯曲钢丝并不是一个能够自行移动的机器人。弯丝的运动是被动的，依赖于弯丝机或人的外力。

• ORP中给出目标机器人的构型。然而，在本文的例子中并不是这样，我们需要通过搜索最少数量的调谐弯曲点，从输入导线生成目标调谐导线。

• 机器人模块可以从一个模块断开连接到另一个模块，这在本文的情况下是不允许的。

• 碰撞约束不仅限于ORP中考虑的自避碰。本文的场景还应该考虑避免与折线机发生碰撞。

---

🐨概述

🐼线材弯曲设置

典型的线材弯曲机的部件，包括线材矫直器、送料器和弯曲销，它们分别用于拉直、送料和弯曲输入线材。

折线机可以生产两种类型的弯曲段：使用弯曲弯曲策略的线段和使用内插弯曲策略和打击弯曲策略的圆形段。

• Flexion弯曲策略：

  • (i)将导线穿过主轴，直至其预设长度(1-2)。

  • (ii)通过弯曲销将金属丝弯曲，直到其预设的弯曲角度，以制造线段(3)。

  • (iii)将弯曲销返回其主位置，以进行后续的弯曲操作(4)。

• 插值弯曲策略：

  • (i)将线材穿过主轴，直到到达弯曲销(5)。

  • (ii)使用弯曲销将线材弯曲，直到其预设的弯曲角度(6)。

  • (iii)固定弯曲销并连续馈送线材，以制造圆形线材(7)。通过该策略生产的圆形线材具有有限的最小半径𝑅𝑚𝑖𝑛，详见附录a。

• 冲击弯曲策略：为了创建半径小于𝑅𝑚𝑖𝑛的圆形线段，在冲击弯曲策略中应用了多个递增的弯曲弯曲操作，其中每次弯曲操作之后都是钢丝的增量进料距离𝐿𝑖𝑛(8)。

制造约束

除了无碰撞约束外，还有三个制造约束来保证机器弯曲阶段每个弯曲段的可制造性。

• 最小长度约束：每条线段必须不短于𝐿𝑚𝑖𝑛，其定义为导线出线与弯曲销之间的距离。

• 弯曲角度范围约束：相邻线段之间的弯曲角度受弯曲销绕出线口旋转范围的限制，该范围为[−α𝑚𝑎𝑥, α𝑚𝑎𝑥]。

• G1线段约束：每个圆线段的前面必须跟着一条线段，这条线段是G1连续到圆线段的。

---

综上所述，只要其长度大于𝐿𝑚𝑖𝑛，线段就是可弯曲可加工的，只要其前面有G1连续线段，该圆形线段就是可弯曲可加工的。

如果电线满足以下条件，则认为它是可弯曲可加工的：

1. 无碰撞（没有自碰撞）或全局碰撞；

2. 其包含的弯曲段是可弯曲的；

3. 连续段之间的弯曲角度在[−α𝑚𝑎𝑥，α𝑚𝑎𝑥]的范围内。

---

🐼算法概述

设W表示输入导线，由于无法满足无碰撞约束或其他制造约束，因此无法由弯线机制造。W包括一系列采样点{𝑝0，𝑝1，…，𝑝𝑛，𝑝𝑛+1} 和弯曲段序列{𝑠0，𝑠1，…，𝑠𝑛}，其中𝑠𝑖可以是圆段（通过插值弯曲策略弯曲）或线段（弯曲弯曲或打击弯曲策略），以{𝑝𝑖，𝑝𝑖+1}作为𝑠𝑖，𝑖+1 = 0，1，…，𝑛的两个端点。点{𝑝1，𝑝2，…，𝑝𝑛}表示W的弯曲点，与由折线机操作的期望的弯曲角度{𝛼1，𝛼2，…，𝛼𝑛}。其中，𝛼𝑖表示连续段𝑠𝑖−1和𝑠𝑖之间的弯曲角度，𝑖=1，2，…，𝑛。

为了应用机器弯曲+人工弯曲策略，我们首先通过拟合一系列W的可加工弯曲段来生成一个可弯曲的线材W‘，然后通过调整W’的弯曲角子集来生成一个无碰撞的可调谐线材W *。假设W'和W * 由𝑚+ 1个可加工的弯曲线段组成。分别设𝑝𝑖‘和𝛼𝑖’为W ‘的弯曲点和弯曲角，𝑝𝑖* 和𝛼𝑖* 为W* 的弯曲点和弯曲角，𝑠𝑖’和𝑠𝑖* 为W'和W* 的弯曲段。只要𝛼𝑖* 与𝛼𝑖’不同，𝑝𝑖* 就是一个可调谐点，否则，它就是一个常定点。

我们的目标是最小化W* 的调谐点的数量，其中W* 必须满足两个关键的自碰撞标准：

1. W* 的非相邻弯曲段不应相互碰撞；

2. 在机器弯曲阶段，W* 必须避免与线材弯曲机(M)发生任何碰撞。

此外，制造约束对W* 施加了进一步的要求，包括以下内容：

• 弯曲角度𝛼𝑖* 必须小于𝛼𝑚𝑎𝑥（弯曲角度范围约束），弯曲段𝑠𝑖*必须短于𝐿𝑚𝑖𝑛（最小长度约束）。

• 此外，由于调谐点是手动弯曲的，如果弯曲角度太小，用户要准确定位它们就变得具有挑战性。为了解决这个问题，我们的算法为弯曲角度设置了10°的最小角度。

上面描述的OWR优化问题提出了三重挑战：

1. 在线材弯曲设置部分的制造约束下，W的初始弯曲段可能无法制造。

2. 指数搜索空间[−α𝑚𝑎𝑥：α𝑚𝑎𝑥]𝑚，其中每个弯曲角𝛼𝑖* 都有其调谐自由[−α𝑚𝑎𝑥：α𝑚𝑎𝑥]。

3. 弯曲角不是相互独立的，其中𝛼𝑖* 的可行弯曲角由所有先前的弯曲角决定，{𝛼1* ，𝛼2* ，…，𝛼𝑖-1*}

为了解决上述问题，文章在节段可弯曲线材的生成部分中使用曲线拟合过程生成W'。其次，文章通过使用基于启发式的搜索过程确定调谐点并在基于贪婪的搜索方法部分中使用碰撞解决算子（CRO）分配W* 的弯曲角度来计算W* 。此外，采用加权波束搜索策略来权衡搜索效率和质量（波束搜索优化部分）。

🐨节段可弯曲线材的生成

分段可弯曲导线生成演示。(a)输入线段𝑠𝑖序列。每𝑠𝑖一个都生成一个线段和一个前后遍历的圆段。(b)显示了生成的两个候选可加工段。通过图形切割优化(c)获得非重叠段可弯曲线材，其中线段和圆形线段分别用黑色和灰色线表示。(d)显示了满足制造约束的重新拟合过程，灰色小点表示G1线段约束中的交点。

本节通过将{𝑠0，𝑠1，…，𝑠𝑛}拟合到一系列可弯曲线段{𝑠0‘，𝑠1’，…，𝑠𝑛‘}中，从不可加工的输入线段W中生成可分段弯曲线段W ’。这涉及到首先通过向前和向后遍历过程从W的每个弯曲段开始创建一组候选可加工段，然后使用图切割分解过程生成非重叠的可弯曲可加工段。

🐼候选可加工段

这一步尽可能长地从W的每个弯曲段（𝑠）中拟合一个候选可加工段（\dot{𝑠}𝑖），其中\dot{𝑠}可以是线段（\bar{𝑠}）或圆形段（\overset{˘}{𝑠}）。从𝑠𝑖开始，文章沿着W的弯曲段在向后和向前两个方向上遍历，这是由向后𝑠𝑖−1和向前𝑠𝑖+1初始化的。在每次迭代中，文章分别用遍历的弯曲段拟合一个\bar{𝑠}和一个\overset{˘}{𝑠}。这样的遍历将继续下去，直到拟合的弯曲段（ E(\bar{𝑠}) 或 E(\overset{˘}{𝑠}) ）的拟合误差（E）超过一定的阈值（𝜖），在我们的实现中设置为0.6 mm。拟合误差（E）计算为从拟合的弯曲段到穿过的弯曲段的最大欧几里德距离。最后，文章从\bar{𝑠}和\overset{˘}{𝑠}中选择较长的拟合弯曲段作为𝑠𝑖中的候选可加工段\bar{𝑠}𝑖。最终，文章得到𝑛+1个候选可加工段{\dot{𝑠}0，\dot{𝑠}1，…，\dot{𝑠}𝑛}，其中一些可能是冗余和重叠的，如上图(b)所示。为了解决第一个问题，我们简单地从重复的片段中保留一个候选的可构造片段，并得到{\dot{𝑠}0，\dot{𝑠}1，…，\dot{𝑠}𝑑}。

🐼无重叠可加工段

如上图所示，W的每个弯曲段（𝑠𝑖）可作为图节点，W的弯曲点（𝑝𝑖）可作为图节点𝑖之间的图边𝑠𝑖和𝑠𝑖+1。因此，从这些候选可加工段生成无重叠的可弯曲可加工段是一个典型的多标签图切问题，其中候选可加工段作为图切中的标签：

估计分配𝑠𝑖标签的成本𝑙𝑖：

到目前为止，我们得到了一组不重叠的候选可织造段{\dot{𝑠}0，\dot{𝑠}1，…，\dot{𝑠}𝑘}。然而，这些部分可能不符合波束搜索优化部分的制造限制。这是因为在上述工艺中从未考虑过G1线段约束，在图切过程中可能会打破最小长度约束。为了解决这个问题，我们对{\dot{𝑠}0，\dot{𝑠}1，…，\dot{𝑠}𝑘}，首先合并长度较小的线段𝐿𝑚𝑖𝑛和其相邻的候选可加工段。之后，对于每个圆形段\dot{𝑠}𝑖，我们分别拟合一个\bar{𝑠}𝑖‘和一对（\bar{𝑠}𝑖‘，\overset{˘}{s}𝑖‘），其中\bar{𝑠}𝑖‘是\dot{𝑠}𝑖的拟合线段，（\bar{𝑠}𝑖‘，\overset{˘}{s}𝑖‘）是\dot{𝑠}𝑖的两个拟合段，确保G1线段约束。最后，我们从\bar{𝑠}𝑖‘和（\bar{𝑠}𝑖‘，\overset{˘}{s}𝑖‘）中选择拟合误差（E）较小的一个，作为\dot{𝑠}𝑖的结果弯曲段。最后，我们得到段可弯曲线材W'，弯曲线段{𝑠0‘，𝑠1’，…，𝑠𝑚‘}和弯曲点{𝑝1’，…，𝑝𝑚‘}。

🐨双层调线优化

W‘ 保证可用于其每个弯曲段{𝑠0‘，𝑠1’，…，𝑠𝑚‘}。然而，W’ 可能仍然是不可加工的，因为违反了无碰撞约束。为了解决碰撞问题，本节通过调整W′ 的弯曲角度{α0‘，…，α𝑚‘}的最小子集来生成无碰撞的调谐线W* 。

🐼基于贪婪的搜索方法

贪心方法的演示：（a）当𝑝3′和𝑝4′分别弯曲到𝛼3′和𝛼4′时发生碰撞，导致两个调谐点𝑝3* 和𝑝4* 。然而，如果我们设置𝑝4* 为常数点并且它的碰撞可以通过调谐𝑝3* 来解决，从而产生一个单一的调谐点，𝑝3* 。（b）即使没有碰撞也必须设置调谐点的论证，其中的碰撞𝑝3* 不能与常定点𝑝2* 解决。然而，如果我们设置𝑝2* 为调谐点，则可以通过调整的弯曲角度𝑝2* 来解决的碰撞𝑝3* 。

冲突解决算子CRO算法演示：（a）弯曲紫色线段时发生碰撞。（b）我们的CRO算法优化了制造导线中包含的一个调谐点。（c）如果碰撞不能由一个调谐点解决，则在CRO中包括两个调谐点。

🐼波束搜索优化

贪心算法显示，通过探索将每个弯曲点设置为常数点或调谐点的各种选项，可以改进贪心方法，进一步减少所得到的调谐点的数量。提出了一种束搜索优化策略，其解空间形成一个搜索树(T)，其中每个节点编码弯曲点的设置{𝑝1* ，𝑝2* ，…，𝑝𝑖* }，包括各弯曲点类型和弯曲角度𝑝𝑗* ，𝑗= 1,2，…，i。

波束搜索算法的三个核心步骤：候选节点生成、候选节点评分、最终选择调谐导线。

🐨限制和未来工作

🐼限制

文章目前对OWR问题的解决方案是纯几何的。文章不考虑物理因素，如重力、电线稳定性或实际电线产品的其他功能方面。在机器弯曲阶段，线材可能因其重量而下垂，导致意外碰撞和制造错误。文章也不评估钢丝的稳定性或强度，同时寻找调谐点以生成无碰撞调谐钢丝。此外，文章的方法可能会为某些输入导线产生过多的调谐点，这可能需要人类付出潜在的巨大努力来完成后续的弯曲过程。

🐼未来的工作

文章提出了未来在金属丝雕塑制作领域工作的几个方向。

• 首先，文章建议将物理模拟纳入金属丝重构规划过程，以提高金属丝雕塑的准确性和真实感。

• 其次，文章建议通过将复杂的金属丝雕塑分解为多个调谐的金属丝路径来推广所提出的金属丝装配两阶段弯曲策略。

• 第三，认识到不考虑物理因素的局限性为未来的工作提供了有希望的方向。例如，人们可以考虑电线的重量来补偿弯曲过程中潜在的变形。

• 第四，由于金属丝雕塑的材料弹性，在机器弯曲阶段允许一定的碰撞可能是有益的，将无碰撞的硬约束转变为软约束。

• 第五，为了实现连续改变曲率的线材，可以考虑探索同时弯曲策略，这涉及到同时移动线材和料仓设置。

• 第六，优化多销折弯机的折弯顺序。

• 第七，优化分段可弯曲线材生成过程中采样点的分布。

• 此外，它有望将我们的解决方案扩展到机器人领域，在一般的图形机器人运动中实现最佳重构和降低能耗。虽然本文主要关注线雕塑制造，但我们相信探索线抽象设计也是一个有趣的探索途径，特别是使用AIGC技术。

🐨创新点总结

这篇文章的主要创新点在于提出了一个名为“Tune-It”的计算框架，用于优化雕塑制造中的电线重配置问题。这个框架的创新之处主要体现在以下几个方面：

1. 两阶段弯曲策略（Machine-And-Then-Human-Bending）：文章提出了一种新颖的制造策略，通过将目标形状调整为适合电线弯曲机的无碰撞形状，然后由人工将其弯曲回目标形状。这种策略结合了机器的精确性和人类的灵活性，允许即使是非熟练工人也能创建具有复杂几何细节的电线雕塑。

2. 优化电线重配置问题（Optimizing Wire Reconfiguration, OWR）：文章将电线重配置问题表述为一个优化问题，目标是调整最少数量的弯曲点以生成无碰撞的电线路径。这个问题在计算上是具有挑战性的，因为需要考虑电线的全局约束，如避免自碰撞和与机器的全局碰撞。

3. 双层优化方法：文章提出了一个双层优化方法，上层优化选择要调整的弯曲点，下层优化确定具体的调整角度，以消除所有碰撞。这种方法通过权衡搜索效率和解决方案质量，使用加权束搜索策略来优化调整点的选择。

4. 物理评估和DIY电线弯曲机：文章通过使用DIY电线弯曲机进行物理评估，验证了所提出方法的有效性。这种方法不仅在理论上是可行的，而且在实际制造中也是有效的，这为计算制造领域提供了一种新的实验验证方法。

5. 算法的通用性和有效性：文章通过在多种不同几何复杂度的电线形状上测试算法，展示了其通用性和有效性。算法能够在保持低拟合误差的同时，生成具有较少调整点的无碰撞电线路径。

6. 与现有技术的比较：文章还与现有的基于组装的弯曲方法和纯人工弯曲方法进行了比较，展示了所提出方法在精度、用户体验和制造效率方面的优势。