点阵结构部件的增材制造路径连接方法*

周 波，刘殿海，赵宇辉，田同同，赵吉宾

（1.中国科学院沈阳自动化研究所，沈阳 110016；2.中国科学院机器人与智能制造创新研究院，沈阳 110169）

三维点阵结构是近年兴起的一种新型轻质结构，不仅具有良好的力学性能，而且能很好地满足对结构功能一体化的需求[1]。因点阵结构通常是具有质量轻、刚度大、优良的抗冲击性能及散热性能等多功能特性的轻质结构，被广泛地用于工艺品设计（图1（a））、高速运载工具、运动装备（图1（b）[2]）及建筑（图1（c）[3]）。此外，在军工领域还用于舰船潜艇及航空航天飞行器的外壳结构等[4–5]。目前，从空间卫星的大跨度支撑结构件到飞机发动机组件，增材制造无疑是制造领域的研究热点与技术聚焦点，相对于传统的减材制造如数控加工技术，增材制造是一个逐层累加的过程，被定位于传统制造技术无法实现的一体化先进制造方式，具有材料利用率高、复杂结构制造能力强、满足个性化小批量生产需求等技术优势[6]。

点阵结构的命名源于晶体结构，晶体的基本特征是其内部结构具有周期的重复性，把分子空间排列与空间的网点阵列联系起来，就是晶体的点阵结构，如图2（a）为某种晶体结构。此外，自然界也广泛存在这种类似的结构，如海绵及其他动物骨骼以及植物纤维（图2（b））。现代的材料和机械学科，借用这个名词，将满足这种具有大量的连接杆及节点部件的模型统称为三维点阵结构。目前，三维点阵结构的设计多采用算法完成，如图2（c）所示的某周期性点阵结构，其某些相同的结构层具有周期重复的特性。研究人员在追求轻质的同时要求结构满足弹塑性、空气动力学及高散热等物理特性。

这一热点问题吸引商业软件开发了相关控件，绑定在软件上配合用户使用。2018年，著名的三维造型软件Rhino就在其平台下运行采用程序算法生成模型的插件（Grasshopper），用于创建轻量的内部结构，共提供了10余种单元晶格体，用户可根据不同需求将单元晶格体填充于设计空间内[7]，充分满足研究人员对开发增材制造路径算法的初步要求，图3为在模型上调用该控件生成的点阵结构部件。此外，法国洛林大学的学者受Voronoi开孔泡沫成型过程的启发，研究了一种非周期性的微观结构[8]，该方法可以针对目标对象及其表面内的泡沫几何形状及其机械性能进行分级，不需要全局优化过程，而是直接生成微结构以显示特定的弹性行为，如图1（a）所示。

点阵结构部件因结构复杂，不能采用传统的减材制造加工方式进行加工。而采用增材制造，其加工效率一直是亟待解决的难题，其制造总时间主要集中于切片后多边形的填充时间及从当前多边形移动到下一待加工多边形的机构执行非填充加工（连接路径）的时间。

点阵结构虽然切片后多边形数量众多，但是其填充算法仍需采用填充其他种类部件的填充路径，包括：传统的主要基于等距轮廓偏置填充算法（CPO）或者往复填充算法（Zig–Zag），以及这两种方案的混合路径，如图4所示。而效率更高的路径如螺旋轨迹[8]以及适用于薄壁结构增材制造的直骨架[9]方法，往往仅适用于特殊几何特征的多边形的填充，前者适用于外形轮廓圆润的区域而后者适用于具有狭长几何特征的区域。传统方式虽然填充效率相对低，但是在保证多边形轮廓边界精度以及对形状繁杂的多边形轮廓适用性上，是效率高的路径无法比拟的。因此，本文在采用传统方式作为填充方式的基础上，重点讨论连接路径的规划问题。

图1 点阵结构应用Fig.1 Applications of lattice structure

图2 自然界中点阵结构及周期性点阵结构Fig.2 Lattice structures in nature and periodic lattice structure

图3 Grasshopper生成点阵结构Fig.3 Lattice structure generated by Grasshopper

图4 传统轮廓扫描路径类型Fig.4 Conventional scanning paths

针对点阵模型的加工，若采用现有的连接路径，将存在严重的制造效率问题。因点阵模型的切片轮廓过于复杂且数量巨大，而切片过程是根据面片顺序决定的，在填充阶段仍然遵循这一顺序，致使填充过程中大量行程是浪费的，极大影响了加工效率。基于此，本文提出下述轨迹连接算法，见图5的算法流程图。

相关研究工作

21世纪初，三维点阵结构最初由哈佛大学 Evans教授、Hutchison教授和剑桥大学Ashby教授等[10]提出。Deshpande等[11]对金属四面体点阵夹芯结构进行了弯曲试验，且发现点阵结构可简化为铰接体系。Li等[12]针对开口式泡沫等多孔材料，提出一种十四面体结构单元作为简化计算模型。其中，三维点阵结构是由面板、杆件等微元件根据一定规律排列构成的空间桁架结构，见图6[13]。三维点阵结构具有工程意义和实际应用价值，因此本文以三维构型的点阵结构为研究对象。

图5 算法流程图Fig.5 Flow chart of algorithm

增材制造的路径规划算法，主要包括切片轮廓的路径填充、连接路径规划等。因增材路径主要在切片后的平面轮廓内进行填充，所以路径填充相对简单，大多选择前述的CPO或者Zig–Zag方法。为了增加路径覆盖效果及材料熔覆强度，可以选择对临近层的填充路径做角度覆盖填充，图7和图8以Zig–Zag路径为例，实现对边界区域的覆盖填充。通过上述方法，边界区域覆盖质量有了一定的提高。

图6 三维点阵结构Fig.6 3D lattice structure

图7 Zig–Zag扫描路径叠加示意图Fig.7 Schematic diagram of Zig–Zag overlapped scanning path

针对增材制造速度相对缓慢的问题，本文专注于点阵模型制造的局限性，提出了高效的轨迹连接方法。在本文中提出了现有增材技术存在的问题，并分析了旅行商问题在增材制造点阵结构中的应用，进行了模拟及打印试验并给出了结论。

旅行商问题规划点阵模型填充

复杂的点阵模型切片后，会产生大量的多边形，这些多边形大多微小且零散。由于切片算法是基于原模型面片的顺序执行切片的，所以输出的多边形次序并没有规律，现有算法没有对这些多边形进行排序方面的研究。而在后续的填充过程中，填充顺序将大大影响填充的路径连接距离以及总体填充时间。

1 分层切片算法

图9（a）中的八爪鱼模型因具有大量的连杆及节点构造，属于典型的点阵模型；图9（b）中大耳狐模型采用树形支撑部件以保证在满足支撑强度的前提下，节省支撑部件打印材料及打印时间，因树形支撑部件具有复杂的连杆及节点构造，也属于本文所述的点阵模型。

通过查找模型中与给定平面相交的所有三角形，并将相交点依次连接到相应的闭合多边形中，可以获得每一层的切片轨迹（包括内部和外部轨迹）。区分内部和外部轨迹的技术非常成熟，如文献[14]中的父子关系和层次排序算法。通过分层切片算法，可以获得图10模型中各层的多边形。

图8 Zig–Zag扫描打印实例Fig.8 Actual printing samples of Zig–Zag scanning

图9 非周期性点阵模型Fig.9 Non–periodic lattice models

图10 切片效果Fig.10 Slicing effects

将各个多边形的重心坐标抽象替代各个多边形，如图11（a）所示。若采用现有技术直接填充这些复杂的、形状及尺寸各异的多边形，获得填充的路径连接如图11（b）所示，可见直接填充的路径连接基本是随机、混乱的，存在多次交叉。在图11（c）中采用人工的“Z”字形（采用往复、顺序连接）路径连接，这种连接方式可以保证在人工连接时无交叉，大大缩短了连接路径总长，无疑会提高加工效率。

上述数据见表1，可知，相较于默认的无连接规划，采用人工连接可以大大缩短路径连接长度。但是人工连接不仅耗时较长，路径长度也难以保证，对于实际加工时每层存在大量多边形的点阵部件，其连接效率及准确性难以保证。因此本文提出基于求解旅行商问题（Travelling salesman problem,TSP）获得的自动规划填充次序的方法，该方法可以快速计算出无交叉的连接路径并保证连接路径的长度。

2 旅行商问题

旅行商问题是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难（Non deterministic ploynomial–hard）问题，在运筹学和理论计算机科学中非常重要[15]。

TSP是计算数学中研究最深入的问题之一，但对于一般情况却没有有效的解决方法，最为显著的问题是：随着点数的增加，时间消耗将急剧增加。在这些求解方法中，Uwaterloo大学研究人员所提出的TSP求解算法虽然具有良好的准确性但是时间消耗显著[16]；而基于Lin–Kernighan算法的Local Search求解TSP的算法[15]具有良好的时间消耗性，但准确性欠佳。

本文采用蚁群算法（Ant colony optimization，ACO）来求解TSP路径计算，这是一种用来寻找优化路径的概率型算法。蚁群算法于1992年由Dorigo在其博士论文中提出，并在文献[17]中给出系统论述，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，本质上是进化算法中的一种启发式全局优化算法[18]。本文采用蚁群算法解决前述的TSP求解路径连接问题，算法的流程如下（以某一只蚂蚁的行走路径代表一个可行解，即一个路径连接方案）：

图11 扫描路径的连接效果Fig.11 Linking effects of scanning path

表1 狐狸某层切片的轮廓轨迹连接数据统计Table 1 Statistics of linking data of fox model

（1）设定迭代次数；

（2）确定蚂蚁数n；

①对每只蚂蚁，随机选择一个抽象点作为起点；

·进入循环选择后n–1个抽象点；

·根据所有与当前抽象点相连的路径上的信息素多少，决定下一步，即选择信息素最多的路径；

·蚂蚁有一定概率选择错误，即随机选择下一步要走的路径；

·在选择的路径上按照一定规则留下一定量的信息素；

②蚂蚁行走路径就是本次搜索的轨迹连接路径；

（3）每群蚂蚁结束后，所有路径上的信息素进行一次衰退，保证越后进行的蚂蚁的信息素影响越大；

（4）等待迭代结束。

更新信息素的大小有多种，以下给定其中两种模型。

设定更新选择的路径上的信息素方式，为式（1）：

设定全局更新信息素为蚁密系统，见式（2）：

式中，Messageij为从第i个城市到第j个城市的路径上的信息素（初始化为该路径长度的倒数）；u为信息素衰退因子；Q为常数因子；len为从起始城市遍历后再次回到起始城市的路径距离。本文的参数设置如表2所示。

算法模拟蚂蚁寻找食物的过程：以蚂蚁行走路径表示连接路径的可行解，整个蚁群的所有路径构成最短连接路径的解空间。蚂蚁在选择路径时总是倾向于朝信息素浓度高的方向移动，而距离短的路径上走过的蚂蚁多，留下的信息素也多，后续蚂蚁选择它的概率也会越大；其他路径上的信息素会随着时间的推移不断挥发，这样就形成了一种正反馈机制，最后整个蚁群聚集到最短路径上。

蚁群算法的优点在于：（1）采用正反馈机制，使搜索过程不断收敛，不容易陷入局部最优，易于获得全局最优解；（2）搜索过程采用分布式计算方式，多个个体同时进行并行计算，保证算法的计算效率和运行效率[18]。

表2 蚁群算法参数设置数据统计Table 2 Statistics of ACO parameters

3 TSP算法对比分析

通过将几种TSP算法运行对比，以验证本文所提出算法的有效性，这几种对比算法在求解TSP的相关专著[15]中均得到了详细的阐述，这里仅做简单描述。

首先，本文所述的贪婪算法是针对无权图的，且每次选择得到的都是局部最优解。选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

针对TSP问题，使用贪心算法求解的过程为：

（1）从某一个城市开始，每次选择一个城市，直到所有的城市被走完。

（2）每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。

其次，Boruvka与Quick Boruvka算法均基于带权图的最小支撑树（Minimum spanning tree，MST）算法，前者是MST算法中最为古老的算法，后者是前者的优化算法。

分别运行上述算法，并将轨迹连接效果和统计数据分别列于图12及表3。

从列表的数据可以看出，（1）除了Uwaterloo大学及本文所提出的算法，其余算法都存在交叉；（2）虽然Uwaterloo大学所提出的算法路径最短，但是计算时间显著较长，其算法的时空效果并不好。本文进一步比较了时间消耗和精度的随机点（2000点）的计算结果，如图13和表4所示。

图12 多种连接方法对比Fig.12 Comparison of multiple linking methods

与连接路径的长度相比，本文方法在时间消耗方面表现出更大的优势。每层切片的多边形数量可能很大，因此建议在处理点阵结构部件的轨迹连接规划方法时，宜使用所提出的蚁群算法来求解TSP路径。

数值模拟与试验分析

为了评估所提出的TSP连接轨迹规划算法，以图14所示的两个点阵模型的分层切片为例。两者都是典型的具有节点和连杆的点阵模型，其中图14（a）属于典型的周期性点阵结构，为模型1；图14（b）属于非周期性点阵结构，为模型2。经切片后，各个切片层均可以获得多个零散的多边形，适合验证本文所提出的算法。在仿真部分，仅测试示例层的计算时间，以验证TSP算法的计算效率；在打印试验部分，统计对比本文方法节省的实际打印时间。本文所提出的算法以C++实现，并在配置有8 GB RAM的Intel®Core TM i7–4790 CPU 3.6GHz台式计算机上进行了测量。

1 数值模拟

采用前述所提出的方法，先将周期性点阵模型的连接结果显示于图15（左侧为原切片后获得的多边形；右侧为应用本文算法获得的连接结果），并将统计数据列于表5。

同样，调用本文算法再将非周期性点阵模型的连接结果显示于图16，并将统计数据列于表6。此处需要说明的是，给出的两个连接方案中，方案2是考虑部分多边形的抽象点距离远，加入了距离聚类算法[15]：以点集中抽象点距离的远近作为判定依据，将抽象点集分为两个区域，再分别对两个聚类子区域进行TSP路径规划连接的结果；而方案1并没有加入距离聚类算法。

图13 TSP连接随机点Fig.13 TSP linking random points

表4 本文算法与Uwaterloo大学算法的数据统计Table 4 Statistics of algorithms presented by this paper and Uwaterloo University

图14 两种点阵模型Fig.14 Two lattice models

表5 模型1仿真结果统计Table 5 Statistics of simulation results (Model 1)

图15 路径连接实例 （模型1）Fig.15 Linking example (Model 1)

图16 路径连接实例 （模型2）Fig.16 Linking example (Model 2)

对照两个方案的结果，可知在计算时间方面，虽然处理的总抽象点数量相同，但是方案2因为距离聚类产生了两个点集，减少了每个点集的TSP路径规划的计算时间，所以总计算时间并没有因为调用聚类算法而增大，反而减少了总的TSP路径规划时间；在连接距离方面，方案2显著降低，因为只经过一次较大距离的跨越（两个子点集之间），而方案1因为有两次比较大距离的点连接，所以路径显著增加。

2 打印试验

本文的打印测试试验是在熔融沉积建模（FDM）3D打印机上进行的，为了验证所述的轨迹连接方法的效率，测试试验均采用相同的参数：印刷材料是直径为2.0mm的PLA（聚乳酸）塑料，喷嘴直径为0.4mm，将层厚度设置为0.1mm，最大喷嘴移动速度为50mm/s。此外，填充方式均采用Ultimaker Cura软件提供的等距偏置填充路径，填充方式及填充行距的设定值见表7。最终打印效果对比及数据统计如图17及表7。

通过对比打印效果外观，因两种打印方式采用的填充方式及参数相同，所以打印完的成品件外观并没有明显差异，局部特征也基本一致；进一步，通过数据对比，两次打印的成品质量相差仅0.3g；考虑外观和质量基本相同，可认为这两种方式的打印结果没有差异。但在总打印时间消耗及总长度方面，本文方法均比没有进行路径连接规划的方法缩短很多：总打印时间减少17.52%，总连接长度减少17.38%。因此，本文的方法能够很高速、准确地进行轨迹连接，大大地缩短了连接轨迹，提高了加工效率。

结论

本文提出了一种基于蚁群算法解决TSP的增材制造的分层切片数据连接方案。通过将大量的多边形抽象为重心坐标，再将重心坐标以TSP方法获得填充次序和连接路径。该方法主要解决以下问题：

表6 模型2仿真结果统计Table 6 Statistics of simulation results (Model 2)

图17 打印效果（左：Ultimaker Cura软件；右：本文算法）Fig.17 Printing effects (left: Cura; right：this paper)

表7 打印结果统计Table 7 Statistics of simulation results (Model 2)

（1）采用蚁群算法解决了TSP轨迹规划方法，对比多种TSP算法得到的连接路径长度和计算时间，证明本文提出的算法可以有效保证轨迹连接效率；

（2）通过比较连接路径长度和时间消耗的结果，可知如果多边形数量相对较大（超过2000个），推荐使用蚁群算法求解TSP；

（3）在规划抽象点集中加入距离聚类算法，对聚类后的子区域分别进行路径规划，将缩短计算时间及路径规划距离。