改進(jìn)Q學(xué)習(xí)的薄壁結(jié)構(gòu)3D打印路徑規(guī)劃

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

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

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

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

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

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

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

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

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

1.1 算法概述

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

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

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

1.2 仿真環(huán)境

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

1.3 Q-path算法

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

采用Zigzag算法（Zigzag-path）、Fleury算法（Fleurypath）作為對(duì)比算法，從轉(zhuǎn)彎次數(shù)、啟停次數(shù)以及打印時(shí)長(zhǎng)三個(gè)方面測(cè)試Q-path算法的性能。所有實(shí)驗(yàn)均在Python 2.7環(huán)境下實(shí)現(xiàn)，運(yù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)

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

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

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

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

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

圖6 三種算法對(duì)模型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)計(jì)結(jié)果。可以看出，Zigzag-path算法的總成本仍然是最高的。Fleury-path與Q-path的性能數(shù)據(jù)相似，但計(jì)算得出的總成本比Q-path略高。數(shù)據(jù)顯示當(dāng)模型復(fù)雜程度為n=5時(shí)，F(xiàn)leury-path的轉(zhuǎn)彎次數(shù)要低于Q-path，這是由于2.1節(jié)中所述的Fleury-path容易多次訪問(wèn)同一位置的特點(diǎn)，啟停次數(shù)則會(huì)代償轉(zhuǎn)彎次數(shù)，因此有時(shí)轉(zhuǎn)彎次數(shù)可能較少，但總成本仍比Q-path高。隨著模型復(fù)雜度的增加，Q-path總成本的提升率最低，證明了Q-path在處理復(fù)雜模型時(shí)具有較好的穩(wěn)定性。

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

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

2.3 整體打印效率

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

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

3 結(jié)束語(yǔ)

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