周 波，劉殿海，趙宇輝，田同同，趙吉賓

（1.中國科學(xué)院沈陽自動化研究所，沈陽 110016；2.中國科學(xué)院機器人與智能制造創(chuàng)新研究院，沈陽 110169）

三維點陣結(jié)構(gòu)是近年興起的一種新型輕質(zhì)結(jié)構(gòu)，不僅具有良好的力學(xué)性能，而且能很好地滿足對結(jié)構(gòu)功能一體化的需求[1]。因點陣結(jié)構(gòu)通常是具有質(zhì)量輕、剛度大、優(yōu)良的抗沖擊性能及散熱性能等多功能特性的輕質(zhì)結(jié)構(gòu)，被廣泛地用于工藝品設(shè)計（圖1（a））、高速運載工具、運動裝備（圖1（b）[2]）及建筑（圖1（c）[3]）。此外，在軍工領(lǐng)域還用于艦船潛艇及航空航天飛行器的外殼結(jié)構(gòu)等[4–5]。目前，從空間衛(wèi)星的大跨度支撐結(jié)構(gòu)件到飛機發(fā)動機組件，增材制造無疑是制造領(lǐng)域的研究熱點與技術(shù)聚焦點，相對于傳統(tǒng)的減材制造如數(shù)控加工技術(shù)，增材制造是一個逐層累加的過程，被定位于傳統(tǒng)制造技術(shù)無法實現(xiàn)的一體化先進制造方式，具有材料利用率高、復(fù)雜結(jié)構(gòu)制造能力強、滿足個性化小批量生產(chǎn)需求等技術(shù)優(yōu)勢[6]。

點陣結(jié)構(gòu)的命名源于晶體結(jié)構(gòu)，晶體的基本特征是其內(nèi)部結(jié)構(gòu)具有周期的重復(fù)性，把分子空間排列與空間的網(wǎng)點陣列聯(lián)系起來，就是晶體的點陣結(jié)構(gòu)，如圖2（a）為某種晶體結(jié)構(gòu)。此外，自然界也廣泛存在這種類似的結(jié)構(gòu)，如海綿及其他動物骨骼以及植物纖維（圖2（b））?，F(xiàn)代的材料和機械學(xué)科，借用這個名詞，將滿足這種具有大量的連接桿及節(jié)點部件的模型統(tǒng)稱為三維點陣結(jié)構(gòu)。目前，三維點陣結(jié)構(gòu)的設(shè)計多采用算法完成，如圖2（c）所示的某周期性點陣結(jié)構(gòu)，其某些相同的結(jié)構(gòu)層具有周期重復(fù)的特性。研究人員在追求輕質(zhì)的同時要求結(jié)構(gòu)滿足彈塑性、空氣動力學(xué)及高散熱等物理特性。

這一熱點問題吸引商業(yè)軟件開發(fā)了相關(guān)控件，綁定在軟件上配合用戶使用。2018年，著名的三維造型軟件Rhino就在其平臺下運行采用程序算法生成模型的插件（Grasshopper），用于創(chuàng)建輕量的內(nèi)部結(jié)構(gòu)，共提供了10余種單元晶格體，用戶可根據(jù)不同需求將單元晶格體填充于設(shè)計空間內(nèi)[7]，充分滿足研究人員對開發(fā)增材制造路徑算法的初步要求，圖3為在模型上調(diào)用該控件生成的點陣結(jié)構(gòu)部件。此外，法國洛林大學(xué)的學(xué)者受Voronoi開孔泡沫成型過程的啟發(fā)，研究了一種非周期性的微觀結(jié)構(gòu)[8]，該方法可以針對目標(biāo)對象及其表面內(nèi)的泡沫幾何形狀及其機械性能進行分級，不需要全局優(yōu)化過程，而是直接生成微結(jié)構(gòu)以顯示特定的彈性行為，如圖1（a）所示。

點陣結(jié)構(gòu)部件因結(jié)構(gòu)復(fù)雜，不能采用傳統(tǒng)的減材制造加工方式進行加工。而采用增材制造，其加工效率一直是亟待解決的難題，其制造總時間主要集中于切片后多邊形的填充時間及從當(dāng)前多邊形移動到下一待加工多邊形的機構(gòu)執(zhí)行非填充加工（連接路徑）的時間。

點陣結(jié)構(gòu)雖然切片后多邊形數(shù)量眾多，但是其填充算法仍需采用填充其他種類部件的填充路徑，包括：傳統(tǒng)的主要基于等距輪廓偏置填充算法（CPO）或者往復(fù)填充算法（Zig–Zag），以及這兩種方案的混合路徑，如圖4所示。而效率更高的路徑如螺旋軌跡[8]以及適用于薄壁結(jié)構(gòu)增材制造的直骨架[9]方法，往往僅適用于特殊幾何特征的多邊形的填充，前者適用于外形輪廓圓潤的區(qū)域而后者適用于具有狹長幾何特征的區(qū)域。傳統(tǒng)方式雖然填充效率相對低，但是在保證多邊形輪廓邊界精度以及對形狀繁雜的多邊形輪廓適用性上，是效率高的路徑無法比擬的。因此，本文在采用傳統(tǒng)方式作為填充方式的基礎(chǔ)上，重點討論連接路徑的規(guī)劃問題。

圖1 點陣結(jié)構(gòu)應(yīng)用Fig.1 Applications of lattice structure

圖2 自然界中點陣結(jié)構(gòu)及周期性點陣結(jié)構(gòu)Fig.2 Lattice structures in nature and periodic lattice structure

圖3 Grasshopper生成點陣結(jié)構(gòu)Fig.3 Lattice structure generated by Grasshopper

圖4 傳統(tǒng)輪廓掃描路徑類型Fig.4 Conventional scanning paths

針對點陣模型的加工，若采用現(xiàn)有的連接路徑，將存在嚴(yán)重的制造效率問題。因點陣模型的切片輪廓過于復(fù)雜且數(shù)量巨大，而切片過程是根據(jù)面片順序決定的，在填充階段仍然遵循這一順序，致使填充過程中大量行程是浪費的，極大影響了加工效率?；诖耍疚奶岢鱿率鲕壽E連接算法，見圖5的算法流程圖。

相關(guān)研究工作

21世紀(jì)初，三維點陣結(jié)構(gòu)最初由哈佛大學(xué) Evans教授、Hutchison教授和劍橋大學(xué)Ashby教授等[10]提出。Deshpande等[11]對金屬四面體點陣夾芯結(jié)構(gòu)進行了彎曲試驗，且發(fā)現(xiàn)點陣結(jié)構(gòu)可簡化為鉸接體系。Li等[12]針對開口式泡沫等多孔材料，提出一種十四面體結(jié)構(gòu)單元作為簡化計算模型。其中，三維點陣結(jié)構(gòu)是由面板、桿件等微元件根據(jù)一定規(guī)律排列構(gòu)成的空間桁架結(jié)構(gòu)，見圖6[13]。三維點陣結(jié)構(gòu)具有工程意義和實際應(yīng)用價值，因此本文以三維構(gòu)型的點陣結(jié)構(gòu)為研究對象。

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

增材制造的路徑規(guī)劃算法，主要包括切片輪廓的路徑填充、連接路徑規(guī)劃等。因增材路徑主要在切片后的平面輪廓內(nèi)進行填充，所以路徑填充相對簡單，大多選擇前述的CPO或者Zig–Zag方法。為了增加路徑覆蓋效果及材料熔覆強度，可以選擇對臨近層的填充路徑做角度覆蓋填充，圖7和圖8以Zig–Zag路徑為例，實現(xiàn)對邊界區(qū)域的覆蓋填充。通過上述方法，邊界區(qū)域覆蓋質(zhì)量有了一定的提高。

圖6 三維點陣結(jié)構(gòu)Fig.6 3D lattice structure

圖7 Zig–Zag掃描路徑疊加示意圖Fig.7 Schematic diagram of Zig–Zag overlapped scanning path

針對增材制造速度相對緩慢的問題，本文專注于點陣模型制造的局限性，提出了高效的軌跡連接方法。在本文中提出了現(xiàn)有增材技術(shù)存在的問題，并分析了旅行商問題在增材制造點陣結(jié)構(gòu)中的應(yīng)用，進行了模擬及打印試驗并給出了結(jié)論。

旅行商問題規(guī)劃點陣模型填充

復(fù)雜的點陣模型切片后，會產(chǎn)生大量的多邊形，這些多邊形大多微小且零散。由于切片算法是基于原模型面片的順序執(zhí)行切片的，所以輸出的多邊形次序并沒有規(guī)律，現(xiàn)有算法沒有對這些多邊形進行排序方面的研究。而在后續(xù)的填充過程中，填充順序?qū)⒋蟠笥绊懱畛涞穆窂竭B接距離以及總體填充時間。

1 分層切片算法

圖9（a）中的八爪魚模型因具有大量的連桿及節(jié)點構(gòu)造，屬于典型的點陣模型；圖9（b）中大耳狐模型采用樹形支撐部件以保證在滿足支撐強度的前提下，節(jié)省支撐部件打印材料及打印時間，因樹形支撐部件具有復(fù)雜的連桿及節(jié)點構(gòu)造，也屬于本文所述的點陣模型。

通過查找模型中與給定平面相交的所有三角形，并將相交點依次連接到相應(yīng)的閉合多邊形中，可以獲得每一層的切片軌跡（包括內(nèi)部和外部軌跡）。區(qū)分內(nèi)部和外部軌跡的技術(shù)非常成熟，如文獻[14]中的父子關(guān)系和層次排序算法。通過分層切片算法，可以獲得圖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

將各個多邊形的重心坐標(biāo)抽象替代各個多邊形，如圖11（a）所示。若采用現(xiàn)有技術(shù)直接填充這些復(fù)雜的、形狀及尺寸各異的多邊形，獲得填充的路徑連接如圖11（b）所示，可見直接填充的路徑連接基本是隨機、混亂的，存在多次交叉。在圖11（c）中采用人工的“Z”字形（采用往復(fù)、順序連接）路徑連接，這種連接方式可以保證在人工連接時無交叉，大大縮短了連接路徑總長，無疑會提高加工效率。

上述數(shù)據(jù)見表1，可知，相較于默認(rèn)的無連接規(guī)劃，采用人工連接可以大大縮短路徑連接長度。但是人工連接不僅耗時較長，路徑長度也難以保證，對于實際加工時每層存在大量多邊形的點陣部件，其連接效率及準(zhǔn)確性難以保證。因此本文提出基于求解旅行商問題（Travelling salesman problem,TSP）獲得的自動規(guī)劃填充次序的方法，該方法可以快速計算出無交叉的連接路徑并保證連接路徑的長度。

2 旅行商問題

旅行商問題是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個NP困難（Non deterministic ploynomial–hard）問題，在運籌學(xué)和理論計算機科學(xué)中非常重要[15]。

TSP是計算數(shù)學(xué)中研究最深入的問題之一，但對于一般情況卻沒有有效的解決方法，最為顯著的問題是：隨著點數(shù)的增加，時間消耗將急劇增加。在這些求解方法中，Uwaterloo大學(xué)研究人員所提出的TSP求解算法雖然具有良好的準(zhǔn)確性但是時間消耗顯著[16]；而基于Lin–Kernighan算法的Local Search求解TSP的算法[15]具有良好的時間消耗性，但準(zhǔn)確性欠佳。

本文采用蟻群算法（Ant colony optimization，ACO）來求解TSP路徑計算，這是一種用來尋找優(yōu)化路徑的概率型算法。蟻群算法于1992年由Dorigo在其博士論文中提出，并在文獻[17]中給出系統(tǒng)論述，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，本質(zhì)上是進化算法中的一種啟發(fā)式全局優(yōu)化算法[18]。本文采用蟻群算法解決前述的TSP求解路徑連接問題，算法的流程如下（以某一只螞蟻的行走路徑代表一個可行解，即一個路徑連接方案）：

圖11 掃描路徑的連接效果Fig.11 Linking effects of scanning path

表1 狐貍某層切片的輪廓軌跡連接數(shù)據(jù)統(tǒng)計Table 1 Statistics of linking data of fox model

（1）設(shè)定迭代次數(shù)；

（2）確定螞蟻數(shù)n；

①對每只螞蟻，隨機選擇一個抽象點作為起點；

·進入循環(huán)選擇后n–1個抽象點；

·根據(jù)所有與當(dāng)前抽象點相連的路徑上的信息素多少，決定下一步，即選擇信息素最多的路徑；

·螞蟻有一定概率選擇錯誤，即隨機選擇下一步要走的路徑；

·在選擇的路徑上按照一定規(guī)則留下一定量的信息素；

②螞蟻行走路徑就是本次搜索的軌跡連接路徑；

（3）每群螞蟻結(jié)束后，所有路徑上的信息素進行一次衰退，保證越后進行的螞蟻的信息素影響越大；

（4）等待迭代結(jié)束。

更新信息素的大小有多種，以下給定其中兩種模型。

設(shè)定更新選擇的路徑上的信息素方式，為式（1）：

設(shè)定全局更新信息素為蟻密系統(tǒng)，見式（2）：

式中，Messageij為從第i個城市到第j個城市的路徑上的信息素（初始化為該路徑長度的倒數(shù)）；u為信息素衰退因子；Q為常數(shù)因子；len為從起始城市遍歷后再次回到起始城市的路徑距離。本文的參數(shù)設(shè)置如表2所示。

算法模擬螞蟻尋找食物的過程：以螞蟻行走路徑表示連接路徑的可行解，整個蟻群的所有路徑構(gòu)成最短連接路徑的解空間。螞蟻在選擇路徑時總是傾向于朝信息素濃度高的方向移動，而距離短的路徑上走過的螞蟻多，留下的信息素也多，后續(xù)螞蟻選擇它的概率也會越大；其他路徑上的信息素會隨著時間的推移不斷揮發(fā)，這樣就形成了一種正反饋機制，最后整個蟻群聚集到最短路徑上。

蟻群算法的優(yōu)點在于：（1）采用正反饋機制，使搜索過程不斷收斂，不容易陷入局部最優(yōu)，易于獲得全局最優(yōu)解；（2）搜索過程采用分布式計算方式，多個個體同時進行并行計算，保證算法的計算效率和運行效率[18]。

表2 蟻群算法參數(shù)設(shè)置數(shù)據(jù)統(tǒng)計Table 2 Statistics of ACO parameters

3 TSP算法對比分析

通過將幾種TSP算法運行對比，以驗證本文所提出算法的有效性，這幾種對比算法在求解TSP的相關(guān)專著[15]中均得到了詳細(xì)的闡述，這里僅做簡單描述。

首先，本文所述的貪婪算法是針對無權(quán)圖的，且每次選擇得到的都是局部最優(yōu)解。選擇的策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

針對TSP問題，使用貪心算法求解的過程為：

（1）從某一個城市開始，每次選擇一個城市，直到所有的城市被走完。

（2）每次在選擇下一個城市的時候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過的路徑總距離最小。

其次，Boruvka與Quick Boruvka算法均基于帶權(quán)圖的最小支撐樹（Minimum spanning tree，MST）算法，前者是MST算法中最為古老的算法，后者是前者的優(yōu)化算法。

分別運行上述算法，并將軌跡連接效果和統(tǒng)計數(shù)據(jù)分別列于圖12及表3。

從列表的數(shù)據(jù)可以看出，（1）除了Uwaterloo大學(xué)及本文所提出的算法，其余算法都存在交叉；（2）雖然Uwaterloo大學(xué)所提出的算法路徑最短，但是計算時間顯著較長，其算法的時空效果并不好。本文進一步比較了時間消耗和精度的隨機點（2000點）的計算結(jié)果，如圖13和表4所示。

圖12 多種連接方法對比Fig.12 Comparison of multiple linking methods

與連接路徑的長度相比，本文方法在時間消耗方面表現(xiàn)出更大的優(yōu)勢。每層切片的多邊形數(shù)量可能很大，因此建議在處理點陣結(jié)構(gòu)部件的軌跡連接規(guī)劃方法時，宜使用所提出的蟻群算法來求解TSP路徑。

數(shù)值模擬與試驗分析

為了評估所提出的TSP連接軌跡規(guī)劃算法，以圖14所示的兩個點陣模型的分層切片為例。兩者都是典型的具有節(jié)點和連桿的點陣模型，其中圖14（a）屬于典型的周期性點陣結(jié)構(gòu)，為模型1；圖14（b）屬于非周期性點陣結(jié)構(gòu)，為模型2。經(jīng)切片后，各個切片層均可以獲得多個零散的多邊形，適合驗證本文所提出的算法。在仿真部分，僅測試示例層的計算時間，以驗證TSP算法的計算效率；在打印試驗部分，統(tǒng)計對比本文方法節(jié)省的實際打印時間。本文所提出的算法以C++實現(xiàn)，并在配置有8 GB RAM的Intel?Core TM i7–4790 CPU 3.6GHz臺式計算機上進行了測量。

1 數(shù)值模擬

采用前述所提出的方法，先將周期性點陣模型的連接結(jié)果顯示于圖15（左側(cè)為原切片后獲得的多邊形；右側(cè)為應(yīng)用本文算法獲得的連接結(jié)果），并將統(tǒng)計數(shù)據(jù)列于表5。

同樣，調(diào)用本文算法再將非周期性點陣模型的連接結(jié)果顯示于圖16，并將統(tǒng)計數(shù)據(jù)列于表6。此處需要說明的是，給出的兩個連接方案中，方案2是考慮部分多邊形的抽象點距離遠(yuǎn)，加入了距離聚類算法[15]：以點集中抽象點距離的遠(yuǎn)近作為判定依據(jù)，將抽象點集分為兩個區(qū)域，再分別對兩個聚類子區(qū)域進行TSP路徑規(guī)劃連接的結(jié)果；而方案1并沒有加入距離聚類算法。

圖13 TSP連接隨機點Fig.13 TSP linking random points

表4 本文算法與Uwaterloo大學(xué)算法的數(shù)據(jù)統(tǒng)計Table 4 Statistics of algorithms presented by this paper and Uwaterloo University

圖14 兩種點陣模型Fig.14 Two lattice models

表5 模型1仿真結(jié)果統(tǒng)計Table 5 Statistics of simulation results (Model 1)

圖15 路徑連接實例 （模型1）Fig.15 Linking example (Model 1)

圖16 路徑連接實例 （模型2）Fig.16 Linking example (Model 2)

對照兩個方案的結(jié)果，可知在計算時間方面，雖然處理的總抽象點數(shù)量相同，但是方案2因為距離聚類產(chǎn)生了兩個點集，減少了每個點集的TSP路徑規(guī)劃的計算時間，所以總計算時間并沒有因為調(diào)用聚類算法而增大，反而減少了總的TSP路徑規(guī)劃時間；在連接距離方面，方案2顯著降低，因為只經(jīng)過一次較大距離的跨越（兩個子點集之間），而方案1因為有兩次比較大距離的點連接，所以路徑顯著增加。

2 打印試驗

本文的打印測試試驗是在熔融沉積建模（FDM）3D打印機上進行的，為了驗證所述的軌跡連接方法的效率，測試試驗均采用相同的參數(shù)：印刷材料是直徑為2.0mm的PLA（聚乳酸）塑料，噴嘴直徑為0.4mm，將層厚度設(shè)置為0.1mm，最大噴嘴移動速度為50mm/s。此外，填充方式均采用Ultimaker Cura軟件提供的等距偏置填充路徑，填充方式及填充行距的設(shè)定值見表7。最終打印效果對比及數(shù)據(jù)統(tǒng)計如圖17及表7。

通過對比打印效果外觀，因兩種打印方式采用的填充方式及參數(shù)相同，所以打印完的成品件外觀并沒有明顯差異，局部特征也基本一致；進一步，通過數(shù)據(jù)對比，兩次打印的成品質(zhì)量相差僅0.3g；考慮外觀和質(zhì)量基本相同，可認(rèn)為這兩種方式的打印結(jié)果沒有差異。但在總打印時間消耗及總長度方面，本文方法均比沒有進行路徑連接規(guī)劃的方法縮短很多：總打印時間減少17.52%，總連接長度減少17.38%。因此，本文的方法能夠很高速、準(zhǔn)確地進行軌跡連接，大大地縮短了連接軌跡，提高了加工效率。

結(jié)論

本文提出了一種基于蟻群算法解決TSP的增材制造的分層切片數(shù)據(jù)連接方案。通過將大量的多邊形抽象為重心坐標(biāo)，再將重心坐標(biāo)以TSP方法獲得填充次序和連接路徑。該方法主要解決以下問題：

表6 模型2仿真結(jié)果統(tǒng)計Table 6 Statistics of simulation results (Model 2)

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

表7 打印結(jié)果統(tǒng)計Table 7 Statistics of simulation results (Model 2)

（1）采用蟻群算法解決了TSP軌跡規(guī)劃方法，對比多種TSP算法得到的連接路徑長度和計算時間，證明本文提出的算法可以有效保證軌跡連接效率；

（2）通過比較連接路徑長度和時間消耗的結(jié)果，可知如果多邊形數(shù)量相對較大（超過2000個），推薦使用蟻群算法求解TSP；

（3）在規(guī)劃抽象點集中加入距離聚類算法，對聚類后的子區(qū)域分別進行路徑規(guī)劃，將縮短計算時間及路徑規(guī)劃距離。