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

王瑞超，高祥，李會軍，朱國崇，許健儀

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

0 前言

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

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

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

1.1 輪廓偏置路徑

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

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

當pi為凹頂點時，根據(jù)幾何關系，則有

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

1.2 zigzag 掃描路徑

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

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

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

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

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

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

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

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

圖2 復合路徑生成流程

2 zigzag 分區(qū)連接

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

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

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

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

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

步驟3：以當前分區(qū)Gi進行擴展，搜索其鄰近分區(qū)Gj，然后判斷分區(qū)Gj是否被訪問過，若Gj未被訪問過，則標記Gj；若Gj已被訪問過，則搜索Gi的其它鄰近分區(qū)。

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

步驟5：若當前結(jié)點的所有鄰近分區(qū)都已被訪問過，仍未找到目標分區(qū)，則回溯其前一分區(qū)，搜索該分區(qū)的其它鄰近分區(qū)。

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

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

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

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

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

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

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

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

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

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

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

當每只螞蟻訪問所有區(qū)域后，對所走路徑上的信息素進行全面更新，信息素更新的表達式為

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

圖5 蟻群算法流程

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

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

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

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

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

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

4 算法驗證與分析

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

圖6 填充對象

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

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

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

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

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

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

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

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

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

表1 總空行程路徑長度對比

圖17 最短空行程長度

圖18 空行程路徑對比

5 結(jié)論

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

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

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