基于DFS 與蟻群算法的電弧增材復(fù)合路徑規(guī)劃算法優(yōu)化

王瑞超，高祥，李會(huì)軍，朱國(guó)崇，許健儀

(五邑大學(xué)，智能制造學(xué)部，廣東 江門(mén) 529020)

0 前言

電弧增材制造（Wire and arc additive manufacturing,WAAM）是一種以電弧焊接技術(shù)為基礎(chǔ)，基于三維數(shù)字化切片模型，采用逐層熔敷堆積原理，在基板上堆積出接近產(chǎn)品形狀和尺寸要求的三維金屬胚件的先進(jìn)制造技術(shù)[1-3]，特別適用于中大型復(fù)雜結(jié)構(gòu)金屬部件的制造。電弧增材制造的路徑規(guī)劃方法是影響成形件的尺寸精度和成形效率的重要因素[4]。若路徑規(guī)劃不合理，可能會(huì)出現(xiàn)過(guò)多的弧坑塌陷、欠堆積和過(guò)堆積現(xiàn)象，導(dǎo)致成形尺寸精度低、表面成形不平整；增材過(guò)程中焊槍空行程過(guò)多，則會(huì)降低成形效率[5]。目前，電弧增材制造路徑規(guī)劃方法主要有zigzag 掃描、輪廓偏置掃描、螺旋掃描和分形掃描。其中zigzag掃描方法具有算法簡(jiǎn)單、路徑連續(xù)性高，存在拐角較多、邊緣臺(tái)階效應(yīng)；輪廓偏置掃描方法具有邊緣成形精度高，存在起弧熄弧次數(shù)較多，適應(yīng)性差、存在干涉等；螺旋掃描方法具有路徑連續(xù)性高，存在算法復(fù)雜、適應(yīng)性差等；分形掃描方法具有路徑連續(xù)性高，存在算法復(fù)雜、拐角多、邊緣臺(tái)階效應(yīng)。對(duì)于形狀復(fù)雜的填充截面采用單一的路徑規(guī)劃方式，成形質(zhì)量往往不能得到保證，而且成形效率較低。在權(quán)衡各種路徑規(guī)劃方法的優(yōu)劣后，得出較好的路徑規(guī)劃方案是采用復(fù)合路徑規(guī)劃。而目前應(yīng)用較多zigzag 掃描和輪廓偏置相結(jié)合的復(fù)合路徑規(guī)劃，即成形件的內(nèi)外輪廓采用輪廓偏置填充，在輪廓偏置內(nèi)采用zigzag 掃描填充[6-8]，其具有成形尺寸精度高、成形效率高、算法簡(jiǎn)單等優(yōu)點(diǎn)。

采用zigzag 掃描與輪廓偏置相結(jié)合的復(fù)合路徑規(guī)劃方法，在此基礎(chǔ)上，為了進(jìn)一步提高成形效率，采用深度優(yōu)先搜索算法對(duì)zigzag 掃描路徑分區(qū)進(jìn)行連接，減少zigzag 掃描路徑的起弧熄弧次數(shù)，同時(shí)引入蟻群算法搜尋路徑規(guī)劃順序和起弧點(diǎn)的最優(yōu)組合，使總空行程長(zhǎng)度最小。

1 復(fù)合路徑規(guī)劃方法

1.1 輪廓偏置路徑

成形件的輪廓是由STL 格式的三維模型與切片平面相交而得，其由多條線段組成的封閉多邊形。多邊形的偏置向量正好位于其輪廓線內(nèi)角的角平分線上，外輪廓的偏置向量方向指向其內(nèi)部，而內(nèi)輪廓?jiǎng)t指向其外部。內(nèi)外輪廓的偏置原理相同，僅偏置方向相反，下面以外輪廓為例進(jìn)行說(shuō)明。

假設(shè)外輪廓上有n個(gè)頂點(diǎn)pi(xi,yi)(i=1,2,3,···,n)，并進(jìn)行逆時(shí)針排序，設(shè)pi的偏置點(diǎn)為，偏置間距為d，向量V1=pi-pi-1，向量V2=pi+1-pi，若V1×V2的值為正，則pi為凸頂點(diǎn)，否則pi為凹頂點(diǎn)。當(dāng)pi為凸頂點(diǎn)時(shí)，根據(jù)幾何關(guān)系[9]，則有

當(dāng)pi為凹頂點(diǎn)時(shí)，根據(jù)幾何關(guān)系，則有

由此可以求得pi點(diǎn)的偏置頂點(diǎn)連接外輪廓的每個(gè)偏置點(diǎn)便可得到輪廓偏置路徑。對(duì)于內(nèi)輪廓偏置，相反地，其頂點(diǎn)需要按照順時(shí)針排序，若V1×V2的值為負(fù)，則pi為凸頂點(diǎn)，否則pi為凹頂點(diǎn)，同樣通過(guò)式（1）～式（6）求解其偏置頂點(diǎn)。如果輪廓偏置的過(guò)程中出現(xiàn)干涉現(xiàn)象，可以采用輪廓連接合并與分解的方法進(jìn)行消除[10]。為了避免干涉現(xiàn)象的產(chǎn)生，文中只求解一次內(nèi)外輪廓偏置路徑。

1.2 zigzag 掃描路徑

上一節(jié)介紹了輪廓偏置路徑的計(jì)算方法，獲得輪廓偏置路徑后使用zigzag 掃描路徑對(duì)其內(nèi)部進(jìn)行填充。zigzag 掃描路徑是由平行掃描路徑連接而成的連續(xù)路徑[11]，該算法基本實(shí)現(xiàn)步驟如下所述。

步驟1：設(shè)掃描線的間距為d′，求出輪廓偏置線的y坐標(biāo)最大值ymax和最小值ymin，沿y軸負(fù)方向生成掃描線

步驟2：求掃描線與輪廓偏置線的交點(diǎn)，將交點(diǎn)按照x的坐標(biāo)值從小到大進(jìn)行排序，記錄交點(diǎn)個(gè)數(shù)Ni，然后將交點(diǎn)存儲(chǔ)到一個(gè)數(shù)組中。已知掃描線縱坐標(biāo)為yi，設(shè)輪廓偏置多邊形的相鄰兩頂點(diǎn)分別為pm(xm,ym)和pn(xn,yn)，求得交點(diǎn)橫坐標(biāo)x：

步驟3：當(dāng)交點(diǎn)個(gè)數(shù)Ni發(fā)生變化時(shí)，則創(chuàng)建新數(shù)組存儲(chǔ)新產(chǎn)生的交點(diǎn)，然后將各數(shù)組中同一條掃描線上的交點(diǎn)兩兩奇偶配對(duì)構(gòu)成0.5Ni個(gè)掃描路徑，再將同一條掃描線上的掃描路徑進(jìn)行分區(qū)，分區(qū)數(shù)目為0.5Ni，最后對(duì)所有分區(qū)進(jìn)行排序。圖1 為掃描路徑的生成與分區(qū)示意圖。

圖1 掃描路徑生成與分區(qū)示意圖

步驟4：依次連接各數(shù)組中同一分區(qū)內(nèi)y坐標(biāo)值相鄰的掃描路徑的末端點(diǎn)和首端點(diǎn)，便可在該分區(qū)內(nèi)生成一條連續(xù)的zigzag 掃描路徑。

上述每條掃描線與輪廓偏置線交點(diǎn)數(shù)目Ni一直為偶數(shù)，但實(shí)際中根據(jù)不同的掃描間隔d′，掃描線可能會(huì)與輪廓偏置線頂點(diǎn)相交，使得交點(diǎn)數(shù)目為奇數(shù)；或者掃描線與某一段輪廓偏置線重合，在理論上會(huì)有無(wú)窮多個(gè)交點(diǎn)，實(shí)際上會(huì)導(dǎo)致步驟2 的式（8）無(wú)解，這2 種異常情況最終可能會(huì)導(dǎo)致步驟3 中生成錯(cuò)誤的掃描路徑和分區(qū)。若出現(xiàn)此類異常情況，將對(duì)異常輪廓線及異常交點(diǎn)進(jìn)行刪除處理[12]。

采用輪廓偏置路徑和zigzag 掃描路徑相結(jié)合的復(fù)合填充路徑，圖2 為單層截面輪廓的復(fù)合填充路徑生成流程。需要注意的是，實(shí)際上內(nèi)外輪廓需進(jìn)行2次偏置運(yùn)算。第一次偏置的目的是獲得內(nèi)外輪廓偏置路徑，第二次偏置作為求解掃描線交點(diǎn)的依據(jù)。

圖2 復(fù)合路徑生成流程

2 zigzag 分區(qū)連接

根據(jù)zigzag 路徑生成原理可知各分區(qū)之間zigzag掃描路徑并不連續(xù)，故在每個(gè)分區(qū)內(nèi)都需要重新起頭，實(shí)際增材過(guò)程中則需重新起弧。顯然，zigzag 掃描路徑的分區(qū)越多，起弧和熄弧次數(shù)越多，空行程越多，既降低了表面成形質(zhì)量，也降低了成形效率，同時(shí)也增加了起弧失敗的風(fēng)險(xiǎn)。為了減少起弧熄弧次數(shù)，采用深度優(yōu)先搜索（Deep first search,DFS）來(lái)盡可能連接各分區(qū)之間的掃描路徑。

深度優(yōu)先搜索算法是將最近剛產(chǎn)生的結(jié)點(diǎn)優(yōu)先擴(kuò)展，當(dāng)達(dá)到一定的深度限制時(shí)，如果未找到目標(biāo)或者無(wú)法再擴(kuò)展，則回溯到前一個(gè)分叉結(jié)點(diǎn)繼續(xù)擴(kuò)展[13-14]。深度優(yōu)先搜索過(guò)程，如圖3 所示，圖中箭頭上的標(biāo)號(hào)表示搜索的順序。假定從分區(qū)1 開(kāi)始搜索并標(biāo)記分區(qū)1，若分區(qū)1 不是目標(biāo)分區(qū)，則搜索與分區(qū)1 相鄰且未訪問(wèn)的分區(qū)，此時(shí)滿足的分區(qū)有分區(qū)2 和分區(qū)3，假定優(yōu)先訪問(wèn)分區(qū)2 并標(biāo)記分區(qū)2。若分區(qū)2 不是目標(biāo)分區(qū)，則搜索與分區(qū)2 相鄰且未訪問(wèn)的分區(qū)。重復(fù)以上操作，直至訪問(wèn)到分區(qū)5，由于2 是已訪問(wèn)的分區(qū)，所以此時(shí)分區(qū)5 已沒(méi)有相鄰且未訪問(wèn)的分區(qū)，則開(kāi)始回溯搜索并判斷前一分區(qū)是否存在其他相鄰且未訪問(wèn)的分區(qū)，重復(fù)回溯搜索直至分區(qū)1，然后訪問(wèn)分區(qū)3，直至搜索分區(qū)6，遍歷所有分區(qū)后結(jié)束搜索。深度優(yōu)先搜索算法的基本操作步驟如下所述。

圖3 分區(qū)深度優(yōu)先搜索過(guò)程示意圖

步驟1：建立所有分區(qū)的無(wú)向圖G。

步驟2：選取某一分區(qū)Gi作為起始搜索分區(qū)，并標(biāo)記該分區(qū)。

步驟3：以當(dāng)前分區(qū)Gi進(jìn)行擴(kuò)展，搜索其鄰近分區(qū)Gj，然后判斷分區(qū)Gj是否被訪問(wèn)過(guò)，若Gj未被訪問(wèn)過(guò)，則標(biāo)記Gj；若Gj已被訪問(wèn)過(guò)，則搜索Gi的其它鄰近分區(qū)。

步驟4：根據(jù)步驟2 確定當(dāng)前分區(qū)，并重復(fù)步驟2進(jìn)行搜索。

步驟5：若當(dāng)前結(jié)點(diǎn)的所有鄰近分區(qū)都已被訪問(wèn)過(guò)，仍未找到目標(biāo)分區(qū)，則回溯其前一分區(qū)，搜索該分區(qū)的其它鄰近分區(qū)。

步驟6：重復(fù)步驟3～5 直至找到目標(biāo)分區(qū)或者遍歷所有分區(qū)為止。

文中設(shè)定兩分區(qū)之間能夠建立連接應(yīng)滿足的條件為：①兩分區(qū)之間的相鄰掃描路徑規(guī)劃方向相反；②兩分區(qū)相鄰掃描路徑的端點(diǎn)在同一輪廓偏置線的同一側(cè)且到該輪廓偏置線具有相同間隔；③兩分區(qū)相鄰掃描線端點(diǎn)y坐標(biāo)的差值等于1 倍掃描間距，且兩端點(diǎn)的距離不大于倍掃描間距，從而避免產(chǎn)生過(guò)小的拐角[15]。將“目標(biāo)分區(qū)”設(shè)定為“與起始分區(qū)滿足分區(qū)連接條件的分區(qū)”，若搜索不到目標(biāo)分區(qū)，則返回起始分區(qū)的序號(hào)。zigzag 路徑分區(qū)DFS 連接流程如圖4 所示，若存在目標(biāo)分區(qū)，兩分區(qū)會(huì)合并為一，在下一次循環(huán)中以目標(biāo)分區(qū)的序號(hào)參與搜索，而且作為起始分區(qū)進(jìn)行填充時(shí)，會(huì)一次性連續(xù)填充，進(jìn)而實(shí)現(xiàn)分區(qū)連接。

圖4 zigzag 路徑分區(qū)DFS 連接流程

3 復(fù)合路徑空行程優(yōu)化

空行程，即某一段路徑熄弧點(diǎn)到下一段路徑起弧點(diǎn)的水平距離，是影響電弧增材成形效率的重要因素。zigzag 分區(qū)連接在減少起弧熄弧次數(shù)，同時(shí)也能夠在一定程度上減少空行程。此外，另一個(gè)直接影響空行程大小的因素是各區(qū)域路徑規(guī)劃順序和起弧熄弧點(diǎn)的選擇，這可以歸為旅行商問(wèn)題（Traveling salesman problem,TSP），即找到路徑規(guī)劃順序和起弧熄弧點(diǎn)的最優(yōu)組合，確定最優(yōu)空行程路徑，在保證焊接工藝穩(wěn)定的前提下，使得每個(gè)區(qū)域只被填充一次且總空行程最短。蟻群算法最早應(yīng)用于求解TSP，是目前解決組合優(yōu)化問(wèn)題最有效的工具之一[16]。對(duì)于復(fù)合填充路徑，每條zigzag 的起弧熄弧點(diǎn)數(shù)量為2，而每條輪廓偏置路徑的起弧熄弧點(diǎn)數(shù)量取決于輪廓的頂點(diǎn)數(shù)目。根據(jù)此特點(diǎn)，使用改進(jìn)的蟻群算法搜索路徑規(guī)劃順序和起弧熄弧點(diǎn)的最優(yōu)組合，求解最小總空行程。該算法具體表述如下所述。

設(shè)填充路徑區(qū)域的數(shù)量為n，區(qū)域i到區(qū)域j的距離為Dij，(i,j=1,2,3,···,n)，區(qū)域i有p個(gè)點(diǎn)，區(qū)域j有q個(gè)點(diǎn)，Dij的表達(dá)式如下

式中：dpq為區(qū)域i的第p個(gè)熄弧點(diǎn)到區(qū)域j第q個(gè)起弧點(diǎn)的距離。

設(shè)t時(shí)刻區(qū)域i到區(qū)域j之間路徑上的信息素濃度為T(mén)ij(t)，(i,j=1,2,3,···,n)，Tij(t)的表達(dá)式如下

式中：τpq為區(qū)域i的第p個(gè)熄弧點(diǎn)到區(qū)域j第q個(gè)起弧點(diǎn)的路徑上信息素濃度。設(shè)蟻群中螞蟻的總數(shù)為m，t時(shí)刻螞蟻k會(huì)從區(qū)域i訪問(wèn)區(qū)域j的概率為(k=1,2,3,···,n)，表達(dá)式如下

式中：ppq為t時(shí)刻螞蟻k從區(qū)域i的第p個(gè)熄弧點(diǎn)訪問(wèn)區(qū)域j第q個(gè)起弧點(diǎn)的概率，ppq的求解式如下

式中：ηpq(t)為啟發(fā)函數(shù)，表示區(qū)域i的第p個(gè)熄弧點(diǎn)到區(qū)域j第q個(gè)起弧點(diǎn)路徑的能見(jiàn)度；ηpq(t)=1/dpq，α為信息素因子；β為啟發(fā)函數(shù)因子；allowedk為螞蟻k未訪問(wèn)過(guò)區(qū)域的集合。

當(dāng)每只螞蟻訪問(wèn)所有區(qū)域后，對(duì)所走路徑上的信息素進(jìn)行全面更新，信息素更新的表達(dá)式為

式中：ρ為信息素?fù)]發(fā)因子；為第k只螞蟻在區(qū)域i到區(qū)域j之間的路徑上留下的信息素濃度的增量；Q為信息素常數(shù)；Lk為第k只螞蟻?zhàn)咄晁袇^(qū)域后總的路徑長(zhǎng)度。蟻群算法的流程如圖5 所示，該算法的具體操作步驟如下所述。

圖5 蟻群算法流程

步驟1：輸入?yún)^(qū)域點(diǎn)集并計(jì)算各區(qū)域之間熄弧點(diǎn)到起弧點(diǎn)的距離矩陣。

步驟2：初始化相關(guān)參數(shù)，包括螞蟻數(shù)量m、信息素因子α、啟發(fā)函數(shù)因子β、信息揮發(fā)因子ρ、信息素常數(shù)Q、最大迭代次數(shù)、初始信息素濃度T(0)。

步驟3：隨機(jī)將m個(gè)螞蟻放入不同區(qū)域的出發(fā)點(diǎn)，根據(jù)式（10）～式（12）計(jì)算每只螞蟻從當(dāng)前區(qū)域的熄弧點(diǎn)到下一區(qū)域起弧點(diǎn)的概率，然后根據(jù)概率確定每個(gè)螞蟻下一個(gè)要訪問(wèn)的區(qū)域以及起弧點(diǎn)，同時(shí)更新allowedk，直到每只螞蟻訪問(wèn)完所有區(qū)域。

步驟4：計(jì)算每個(gè)螞蟻經(jīng)過(guò)的路徑長(zhǎng)度Lk，記錄本次迭代中最短路徑距離，同時(shí)根據(jù)式（13）和式（14）更新每條路徑上螞蟻留下的信息素濃度。

步驟5：重復(fù)步驟3～4，直到達(dá)到最大迭代次數(shù)。

步驟6：輸出最優(yōu)路徑對(duì)應(yīng)的區(qū)域訪問(wèn)順序、各區(qū)域的起弧熄弧點(diǎn)及最短空行程的長(zhǎng)度。

4 算法驗(yàn)證與分析

為了驗(yàn)證上述算法的有效性，以圖6a 的三維模型為填充對(duì)象，對(duì)其截面輪廓進(jìn)行復(fù)合路徑規(guī)劃，首先，采用DFS 和蟻群算法先后對(duì)填充結(jié)果進(jìn)行優(yōu)化；然后，對(duì)優(yōu)化結(jié)果進(jìn)行對(duì)比分析。設(shè)置輪廓偏置間距為5 mm，zigzag 掃描間距為10 mm。為了充分測(cè)試DFS 算法連接zigzag 分區(qū)的性能，采用9 種不同掃描傾角zigzag 路徑對(duì)圖6b 的輪廓進(jìn)行規(guī)劃，如圖7～圖15 所示。各種掃描傾角的zigzag 分區(qū)經(jīng)DFS 連接前后起弧熄弧點(diǎn)的對(duì)比結(jié)果如圖16 所示，圖中各輪廓偏置路徑的起弧熄弧點(diǎn)已重合且數(shù)量固定為8。

圖6 填充對(duì)象

圖7 0°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖9 45°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖10 67.5°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖11 90°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖13 135°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖14 157.5°掃描傾角zigzag 分區(qū)連接前后對(duì)比

圖15 180°掃描傾角zigzag 分區(qū)連接前后對(duì)比

分區(qū)連接前后的差異越大，則算法的優(yōu)化效果越好，由圖16 可知，當(dāng)掃描傾角為0°，22.5°，45°，67.5°，180°時(shí)，DFS 分區(qū)連接算法優(yōu)化效果最好，zigzag 路徑條數(shù)與連接前相比減少了約71.4%，起弧熄弧點(diǎn)總數(shù)減少了約55.6%；當(dāng)掃描傾角為112.5°時(shí)，算法優(yōu)化效果最差，zigzag 路徑條數(shù)與連接前相比減少了約55.6%，起弧熄弧點(diǎn)總數(shù)減少了約38.5%，原因是其分區(qū)連接前的zigzag 路徑條數(shù)和起弧熄弧點(diǎn)總數(shù)相比其他情況最少。綜上所述，對(duì)于圖7～圖15 的填充模型而言，DFS 分區(qū)連接算法對(duì)不同掃描傾角zigzag 分區(qū)皆能起到很好的連接作用。

設(shè)置蟻群算法的螞蟻規(guī)模為30，信息素因子為2，啟發(fā)函數(shù)因子為2，最大迭代次數(shù)為300。下面以0°掃描傾角的復(fù)合填充路徑為例，測(cè)試蟻群算法優(yōu)化空行程的性能，分區(qū)連接后的復(fù)合填充路徑經(jīng)蟻群算法尋優(yōu)的最短空行程長(zhǎng)度如圖17 所示。復(fù)合填充路徑尋優(yōu)前后空行程路徑對(duì)比如圖18 所示。其中，圖18c 外部矩形和內(nèi)部菱形、五邊形偏置路徑的起弧熄弧點(diǎn)相比優(yōu)化前已發(fā)生變化，總空行程路徑長(zhǎng)度對(duì)比結(jié)果見(jiàn)表1。根據(jù)表1 可得，DFS 與蟻群算法可以大大減少總空行程長(zhǎng)度，具體表現(xiàn)為DFS 連接后的空行程長(zhǎng)度相比優(yōu)化前減少了約58.2%，在此基礎(chǔ)上再經(jīng)蟻群算法尋優(yōu)后空行程長(zhǎng)度又進(jìn)一步減少了約26.9%。

表1 總空行程路徑長(zhǎng)度對(duì)比

圖17 最短空行程長(zhǎng)度

圖18 空行程路徑對(duì)比

5 結(jié)論

（1）實(shí)現(xiàn)了一種適用于復(fù)雜輪廓截面的電弧增材復(fù)合路徑規(guī)劃算法。

（2）提出了一種用于連接各分區(qū)zigzag 路徑的DFS 分區(qū)連接算法，仿真結(jié)果表明：DFS 分區(qū)連接算法對(duì)不同掃描傾角的zigzag 路徑能夠起到良好的連接作用。

（3）采用蟻群算法優(yōu)化分區(qū)已連接的復(fù)合路徑總空行程，結(jié)果顯示：在DFS 與蟻群算法共同作用下可以極大程度上減少總空行程長(zhǎng)度，驗(yàn)證了算法的有效性和可行性，為下一步進(jìn)行實(shí)際的電弧增材制造掃描算法優(yōu)化提供了方法。