王 祎，葛靜怡，薛昕惟，王勝法，李鳳岐

1.大連理工大學(xué) 國際信息與軟件學(xué)院，遼寧 大連 116620

2.大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620

3D打印技術(shù)也稱增材制造技術(shù)（additive manufacturing，AM），是指融合了計算機輔助設(shè)計（computer aided design，CAD）、計算機輔助制造（computer aided manufacturing，CAM）、計算機數(shù)字控制（computer numerical control，CNC）和材料科學(xué)等一系列技術(shù)，通過將塑料、金屬、粉末等材料層層堆疊形成目標(biāo)實體[1]。經(jīng)過幾十年的快速發(fā)展，3D打印技術(shù)已廣泛應(yīng)用于醫(yī)療、航空航天、教育等領(lǐng)域[2-3]。當(dāng)前，最常用的3D打印方式是熔融沉積（fused deposition modeling，F(xiàn)DM）打印，通過對目標(biāo)模型進行切片，逐層打印并從下至上累積最終獲得目標(biāo)實體。在打印單層切片的過程中，打印噴頭的運動路徑規(guī)劃是核心環(huán)節(jié)。良好的路徑規(guī)劃可以顯著提高打印的性能，如何提高成型效率，保證成型精度是其中的重點研究方向[4]。

薄壁結(jié)構(gòu)使用微少的輕量材料即可承受較大的載荷。18世紀(jì)中葉，薄壁結(jié)構(gòu)被廣泛用于建造箱形金屬橋、船舶和車輛。1930年起，薄壁結(jié)構(gòu)成為飛行器主要采用的結(jié)構(gòu)形式，其在平滑流線的塑造，抗變形和承載能力方面具有很大優(yōu)勢。此外，薄壁軸承可實現(xiàn)極薄的軸承截面，確保了輕量和布線空間。近年來，薄壁結(jié)構(gòu)的理論分析和實驗研究不斷增加，使其在工程中得到廣泛應(yīng)用。

用于3D打印路徑規(guī)劃的傳統(tǒng)方法在打印薄壁結(jié)構(gòu)時存在著一些問題。比如，ZigZag算法由于打印方向平行因而容易集中應(yīng)力[5]，這種應(yīng)力會影響材料散熱，使模型容易發(fā)生變形甚至斷裂；同時，噴頭頻繁的轉(zhuǎn)彎行為會對成型質(zhì)量造成一定的影響。輪廓偏置算法[6]是通過模型輪廓偏移生成掃描矢量，然后在內(nèi)外方向上掃描成型。由于掃描線方向的不斷變化，零件的內(nèi)部應(yīng)力方向發(fā)散并符合傳熱規(guī)律，從而避免了應(yīng)力集中和階梯效應(yīng)，但可能因掃描間距差異而導(dǎo)致輪廓環(huán)相交，此外噴頭較多的啟停次數(shù)也會降低成型質(zhì)量。王騰飛[7]提出基于等距偏移算法的路徑規(guī)劃方法，提高了成形件的精度和強度。分區(qū)掃描是把待掃描區(qū)域按照一定的規(guī)則分成若干個小區(qū)域，在一個小分區(qū)加工完成后快速移動到下一個分區(qū)進行掃描，這種掃描方式減少了空行程的數(shù)量，提高了成型效率[4]。程艷階[8]對SLS成型進行了研究，提出了改進的分區(qū)算法，減少了分區(qū)的數(shù)量。連續(xù)的費馬螺旋線能夠形成較長且曲率低的路徑[9]，其特殊幾何特性能夠提高分層打印的成型質(zhì)量和效率。打印過程中噴頭啟停時的空程會導(dǎo)致制造效率和成型質(zhì)量下降，為減少空程，Lensgraf等[10]提出了一種基于局部搜索的算法，并利用線性規(guī)劃優(yōu)化了路徑方案。Panchagnula等[11]提出了一種用于打印復(fù)雜薄壁金屬結(jié)構(gòu)的方法，通過增加沉積頭的自由度并利用高階運動學(xué)，使懸垂特征與沉積方向成直線對齊來實現(xiàn)。Jin等[12]提出了一種薄壁零件路徑規(guī)劃方法，采用波浪形狀填充細(xì)長截面，具有良好的沉積效果和較高打印效率。歐拉路徑是圖中的一種路徑，該路徑恰好訪問圖的每個邊一次，F(xiàn)leury算法[13]是歐拉路徑的一種遍歷方法，該算法始終在遍歷期間選擇非橋，以便返回到頂點并繼續(xù)遍歷其余邊，適用于解決復(fù)雜薄壁結(jié)構(gòu)的路徑規(guī)劃問題。

強化學(xué)習(xí)被廣泛用于機器人控制、游戲和智能交通等領(lǐng)域[14-15]。其中，Q-learning指智能體在未知環(huán)境中進行無監(jiān)督學(xué)習(xí)的過程，通過給予智能體獎勵指導(dǎo)其行動，使其不斷學(xué)習(xí)來做出最佳決策[16-17]。Q-learning可以適用于薄壁模型的打印。首先，智能代理可以通過感知周圍的環(huán)境決定下一步行動來自適應(yīng)地改變打印方向并提高打印效率。此外，Q-learning可以設(shè)置關(guān)于3D打印性能方面的約束條件，使智能體獲得獎勵以指導(dǎo)操作，以優(yōu)化打印性能。

提出一種基于強化學(xué)習(xí)的復(fù)雜薄壁結(jié)構(gòu)3D打印路徑規(guī)劃方法。這是目前關(guān)于3D打印的路徑規(guī)劃問題的已知研究中首次應(yīng)用強化學(xué)習(xí)方法。首先，將強化學(xué)習(xí)中常規(guī)的路徑規(guī)劃問題轉(zhuǎn)化為路徑的全遍歷問題，然后根據(jù)3D打印的特性設(shè)計Q-learning的約束條件來控制打印頭啟停和轉(zhuǎn)彎次數(shù)，通過路徑規(guī)劃訓(xùn)練實驗尋找最佳規(guī)劃方案。實驗結(jié)果表明，與用于3D打印路徑規(guī)劃的傳統(tǒng)方法相比，該方法可以顯著減少打印頭的啟停和轉(zhuǎn)彎次數(shù)，從而提高成型質(zhì)量，同時還可提升打印效率。

1 基于Q-learning的路徑規(guī)劃算法

1.1 算法概述

3D打印的過程整體上分為四部分：（1）利用建模軟件建立3D模型；（2）利用切片軟件對3D模型進行切片；（3）對3D模型的單層切片進行2D路徑規(guī)劃；（4）路徑填充后的切片經(jīng)過逐層堆疊形成模型實體。提出的方法用于處理（3）中的路徑規(guī)劃部分，具體流程設(shè)計見圖1。

圖1 基于Q-learning的路徑規(guī)劃方法流程圖Fig.1 Procedure of Q-learning-based path planning method

提出一種基于Q-learning的智能路徑規(guī)劃算法（Qpath）。根據(jù)FDM打印系統(tǒng)的特點，將打印噴頭作為智能體，2D切片作為環(huán)境，噴頭通過觀察切片環(huán)境獲取當(dāng)前狀態(tài)和下一步動作等信息，并根據(jù)設(shè)計的針對轉(zhuǎn)彎和啟停次數(shù)的約束條件做出決策。每次做出的決策會更新Q表，該表用于評估狀態(tài)-行為對，并通過決策獲得的獎勵指導(dǎo)噴頭的后續(xù)動作。噴頭通過這種方式多次學(xué)習(xí)，尋找擁有最大總獎勵的最佳路徑規(guī)劃方案。

1.2 仿真環(huán)境

將薄壁模型的STL文件切片為Ci(i=1,2,…,k)，將Ci中優(yōu)化后的離散二維空間Ii作為路徑規(guī)劃的仿真環(huán)境。切片軟件提取平面與網(wǎng)格模型上小三角面片的交線，為了減少計算量，將這些交線簡化，只保留其中的拐點、交叉點及端點，稱為打印控制點。圖2（a）表示一個目標(biāo)模型中某層切片Ci的打印仿真環(huán)境Ii及打印控制點（藍色點表示）。

1.3 Q-path算法

首先建立Q-learning和3D打印要素之間的關(guān)系。將打印噴頭作為Q-learning中的智能體，仿真環(huán)境Ii作為環(huán)境，打印頭的當(dāng)前位置即是智能體的狀態(tài)，下一個要打印的點則是智能體的動作。路徑規(guī)劃的主要任務(wù)是在一系列約束條件下，連接具有相鄰關(guān)系的打印控制點來完成對Ii遍歷。

在Q-learning中設(shè)計了兩個約束條件以優(yōu)化打印性能。首先，打印過程中的轉(zhuǎn)彎行為會造成材料堆積，影響切片層厚從而影響成形質(zhì)量。因此設(shè)計約束條件為當(dāng)智能體進行轉(zhuǎn)彎時根據(jù)轉(zhuǎn)彎角度獲得一定的負(fù)獎勵，以控制轉(zhuǎn)彎的影響。定義獎勵函數(shù)Rt(spre,s,a)用于計算上一步的位置是spre的情況下，從當(dāng)前位置s執(zhí)行動作a獲得的獎勵，元素間位置關(guān)系見圖2（b），函數(shù)見式（1）：

圖2 仿真環(huán)境Fig.2 Simulation environment

式中，Angle(spre,s,a)為向量spres和sa的夾角，μ是一個負(fù)常數(shù)?？梢钥闯?，執(zhí)行動作a獲得的負(fù)獎勵隨著與當(dāng)前方向spres的偏差的增加而增加，方向不改變則不會獲得負(fù)獎勵。另一方面，打印頭的啟停次數(shù)也是影響打印效率和成型質(zhì)量的因素之一，噴頭的空程不僅耗費時間，還會造成材料拉絲和堆積，因此噴頭啟停行為的成本比轉(zhuǎn)彎行為的成本更高。設(shè)計約束條件為當(dāng)智能體進行啟停時根據(jù)空程距離獲得一定的負(fù)獎勵。當(dāng)處于狀態(tài)s，沒有可選的動作a時，智能體會選擇并直接轉(zhuǎn)移到距離最近的狀態(tài)s?，定義獎勵函數(shù)Rl(s,s?)用于計算啟停行為獲得的獎勵，見式（2）：

其中，πμ是式（1）中Rt的最大值，即最大角度的轉(zhuǎn)彎懲罰。由于啟停行為會造成兩處材料堆積，且堆積程度相對轉(zhuǎn)彎行為高，因此2πμ代表啟停行為關(guān)于材料堆積方面的懲罰。ν是一個負(fù)常數(shù)，Dist(s,s?)是啟停點s和s?之間的歐式距離，因此這部分代表空程導(dǎo)致的效率降低及拉絲的方面懲罰。

建立行動-效用矩陣Q(spre,s,a)，假設(shè)在某個策略下某個狀態(tài)的后續(xù)行動是已知的，則該矩陣存儲的元素在上一個狀態(tài)是spre的情況下，在狀態(tài)s執(zhí)行動作a所獲得的累積獎勵。初始化Q中元素為0。優(yōu)化目標(biāo)為最大化單層切片的總獎勵。為尋找全局優(yōu)化方案，采用ε-Greedy方法：以ε的概率探索，以1-ε的概率利用，狀態(tài)轉(zhuǎn)換公式見式（3）、（4）。若在ε的概率下選擇了動作a，則有：

關(guān)于終止條件，Q-learning中是智能體在Q矩陣中不斷進行狀態(tài)轉(zhuǎn)移，直到到達約定的最終狀態(tài)，過程中不限制某個狀態(tài)被選擇的次數(shù)。然而3D打印中路徑規(guī)劃的基本目標(biāo)是打印所有路徑，因此將終止條件設(shè)為所有狀態(tài)都被無重復(fù)地遍歷。設(shè)定一個列表L來存儲所有狀態(tài)，每當(dāng)執(zhí)行一次動作時，從L中刪除該狀態(tài)，不斷執(zhí)行動作直到L為空，以防止后續(xù)動作再次選擇已遍歷狀態(tài)，從而避免在打印過程中重復(fù)遍歷。關(guān)于起終點的設(shè)置，由于獲得最佳起點需要將環(huán)境中的所有狀態(tài)分別設(shè)置為起點，比較每條路徑的總成本來選擇最佳起點，但這種方式會導(dǎo)致過高的時間成本，因此隨機選擇起點。由于Q-path尋找最佳路徑方案的過程是完全智能的，因此在遍歷問題中終點無法被預(yù)先設(shè)置。

2 實驗結(jié)果與分析

采用Zigzag算法（Zigzag-path）、Fleury算法（Fleurypath）作為對比算法，從轉(zhuǎn)彎次數(shù)、啟停次數(shù)以及打印時長三個方面測試Q-path算法的性能。所有實驗均在Python 2.7環(huán)境下實現(xiàn)，運行環(huán)境為3.40 GHz CPU和8 GB RAM的Intel?Core（i）i7。式（1）～（4）中參數(shù)取值：ε=0.3，γ=0.9，μ=1/π，ν=0.2。

2.1 薄壁結(jié)構(gòu)

在多個不同薄壁結(jié)構(gòu)的環(huán)境下評估Q-path、Zigzagpath和Fleury-path的性能。首先以圖2中的模型1為實驗?zāi)繕?biāo)。圖3描述了Q-path訓(xùn)練出的路徑打印過程，紅色圓點表示起點，紅色箭頭表示打印過程中噴頭的實時位置，實驗結(jié)果的統(tǒng)計數(shù)據(jù)如圖4所示。可以觀察到，傳統(tǒng)的Z-path的表現(xiàn)和另外兩種算法的表現(xiàn)差距較大。由于Zigzag-path的自適應(yīng)性較弱，不能將啟停次數(shù)控制在較低的水平，從而付出了較多的啟停次數(shù)來代償轉(zhuǎn)彎次數(shù)，因此轉(zhuǎn)彎次數(shù)最少，啟停次數(shù)最多。然而按總成本計算，Zigzag-path的成本最高，因為單次啟停行為的成本至少是轉(zhuǎn)彎行為的成本的2倍，因此其較弱的自適應(yīng)性導(dǎo)致了總體性能下降。從打印總路程（包括空程）長度來看，Q-path和Fleury-path在時間效率方面的表現(xiàn)明顯好于Zigzag-path。由于Q-path具有全局性，其總體表現(xiàn)比Fleury-path稍好，總成本最低。

圖3 Q-path對模型1的路徑規(guī)劃過程Fig.3 Path planning process of Q-path for model 1

圖4 三種算法對模型1的路徑規(guī)劃結(jié)果Fig.4 Path planning results of three algorithms for model 1

選取一個通路數(shù)量更多的薄壁結(jié)構(gòu)模型2，圖5顯示了Q-path的訓(xùn)練結(jié)果的路徑規(guī)劃過程。Q-path及對比算法的性能數(shù)據(jù)統(tǒng)計如圖6所示。綜合上一個實驗分析得出，F(xiàn)leury-path和Q-path由于相對靈活而穩(wěn)定性較高，傳統(tǒng)的Zigzag-path算法依然不能較好地適應(yīng)復(fù)雜薄壁結(jié)構(gòu)。對于Fleury-path和Q-path的性能差距，分析Fleury-path路徑規(guī)劃的過程得出，當(dāng)Fleury-path建立歐拉回路時可能會多次經(jīng)過某個位置，打印頭首次經(jīng)過的行為是打印該點，但二次經(jīng)過該位置時，需執(zhí)行啟停動作以跳過該位置繼續(xù)打印，從而打印過程后期會造成較多的啟停次數(shù)。而Q-path的智能性更強，考慮到全局優(yōu)化，通過設(shè)置成本開銷最高的啟停行為獲得最高的懲罰，從而將總啟停次數(shù)控制在低水平，同時提高了打印效率。因此Q-path在此實驗?zāi)Ｐ蜕媳憩F(xiàn)依然最佳。

圖5 Q-path對模型2的路徑規(guī)劃過程Fig.5 Path planning process of Q-path for model 2

圖6 三種算法對模型2的路徑規(guī)劃結(jié)果Fig.6 Path planning results of three algorithms for model 2

2.2 結(jié)構(gòu)復(fù)雜程度

比較算法的性能隨著薄壁結(jié)構(gòu)復(fù)雜程度增加的表現(xiàn)情況，選取具有不同復(fù)雜程度n（n為模型包含正方形的數(shù)量）的模型，如圖7所示。圖8顯示了三種算法的性能數(shù)據(jù)統(tǒng)計結(jié)果。可以看出，Zigzag-path算法的總成本仍然是最高的。Fleury-path與Q-path的性能數(shù)據(jù)相似，但計算得出的總成本比Q-path略高。數(shù)據(jù)顯示當(dāng)模型復(fù)雜程度為n=5時，F(xiàn)leury-path的轉(zhuǎn)彎次數(shù)要低于Q-path，這是由于2.1節(jié)中所述的Fleury-path容易多次訪問同一位置的特點，啟停次數(shù)則會代償轉(zhuǎn)彎次數(shù)，因此有時轉(zhuǎn)彎次數(shù)可能較少，但總成本仍比Q-path高。隨著模型復(fù)雜度的增加，Q-path總成本的提升率最低，證明了Q-path在處理復(fù)雜模型時具有較好的穩(wěn)定性。

圖7 具有不同復(fù)雜程度的薄壁模型Fig.7 Thin-walled models with different complexity

圖8 三種算法在模型復(fù)雜程度增加過程中的性能變化Fig.8 Performances of three algorithms change as complexity of model increases

2.3 整體打印效率

實驗角度從單層切片收縮到模型整體。由于Q-path采用了強化學(xué)習(xí)方法，在得到打印結(jié)果前需要預(yù)先進行訓(xùn)練，因此比較算法的路徑規(guī)劃時間成本需要考慮訓(xùn)練時間。假設(shè)模型每層切片的結(jié)構(gòu)都是相同的，采用圖2中的模型進行實驗。結(jié)果如圖9所示。其中Q-path的時間成本包括訓(xùn)練時間和打印時間。可以看出，隨著模型層數(shù)的增加，F(xiàn)leury-path和Q-path的時間成本增長速率明顯比Zigzag-path慢。當(dāng)模型只有一層時，Q-path的時間成本要比Fleury-path高，是因為Q矩陣的訓(xùn)練時間，而訓(xùn)練時間取決于該切片所包含的數(shù)據(jù)量。但當(dāng)模型具有較多層時，Q-path花費的時間最少，該算法的優(yōu)勢得以體現(xiàn)。在實際工程應(yīng)用中，模型通常層數(shù)較多，因此Q-path是一種比較節(jié)約時間成本的解決方案。

圖9 三種算法對模型2的路徑規(guī)劃結(jié)果Fig.9 Path planning results of three algorithms for model 2

3 結(jié)束語

由于用于3D打印路徑規(guī)劃的傳統(tǒng)方法對薄壁復(fù)雜模型的適應(yīng)性較弱，因此將強化學(xué)習(xí)應(yīng)用于3D打印領(lǐng)域，提出了一種新穎的適用于薄壁復(fù)雜結(jié)構(gòu)模型的路徑規(guī)劃方法。設(shè)計多個打印約束條件以優(yōu)化打印性能，采用Q-learning算法尋找約束下的最佳路徑方案。實驗結(jié)果表明，與用于3D打印路徑規(guī)劃的傳統(tǒng)方法相比，該方法有效提高了3D打印的效率和性能，并且算法的性能隨著模型復(fù)雜程度的增加能夠保持穩(wěn)定。作為需要預(yù)先訓(xùn)練的強化學(xué)習(xí)方法，Q-path比較適用于每層結(jié)構(gòu)相同的復(fù)雜薄壁模型。未來的工作將主要集中在針對具有不同層結(jié)構(gòu)的模型的智能打印算法的研究，并結(jié)合傳統(tǒng)的打印方法，分區(qū)方法以及模型的物理性能優(yōu)化方法來擴展智能打印算法的應(yīng)用范圍。