規(guī)則激光切割路徑規(guī)劃研究

規(guī)則激光切割路徑規(guī)劃研究

1切割路徑自動編程在線檢測現(xiàn)在，激光加工技術越來越受到重視。要充分發(fā)揮激光加工機的效率，必須使用自動駕駛軟件和激光加工編程軟件進行。排樣軟件的目的是在給定大小的板材上排列盡可能多的零件或將給出的零件排列在盡可能小的板材上,從而使材料利用率盡可能高。而自動編程軟件的目的是根據(jù)排樣的板材圖形來規(guī)劃切割路徑,并自動生成數(shù)控加工切割機床的數(shù)控代碼,保證數(shù)控機床自動完成切割。在實際生產(chǎn)中,激光切割機用戶認識到:如果自動編程不能保證有效地切割零件、保證部件質(zhì)量及提高產(chǎn)量,排樣軟件在材料效率上獲得的收益將會喪失。排樣軟件的新發(fā)展趨勢是充分考慮后續(xù)切割機床的效率,即采用共邊排樣實現(xiàn)共邊切割。共邊切割是在優(yōu)化排樣時按照一定規(guī)則將具有長邊的零件盡可能以長邊對長邊的方式排列在一起,在生成切割指令時對這些零件外輪廓的公共邊部分只進行一次切割。共邊切割已被認為是提高切割效率、節(jié)省切割成本的重要措施。但現(xiàn)在的數(shù)控切割自動編程軟件中,切割路徑的確定仍不能令用戶滿意。絕大多數(shù)自動編程系統(tǒng)仍是靠操作者的經(jīng)驗在共邊排樣好的板材上交互式地生成切割路徑的順序。由于排樣板材中零件位置分布復雜,因此手工設置切割路徑就顯得十分復雜。另外,即使有少量的能實現(xiàn)共邊切割路徑自動化生成的商品化數(shù)控自動編程系統(tǒng),但其切割路徑并不理想,存在著打孔點過多及空行程較長的問題,直接影響切割效率與加工質(zhì)量。本文的研究重點就是在共邊排樣好的板材上,為自動編程系統(tǒng)研究出割嘴路徑規(guī)劃的高效處理算法,最大限度提高效率,保證質(zhì)量,降低切割成本。2邊界檢測路徑的數(shù)學模型2.1共邊排樣圖形的生成圖1是板材上待切割零件典型的共邊排樣布局圖。共邊排樣件圖形十分適合于用圖論或網(wǎng)絡圖來表達,而且圖論技術是解決割嘴路徑優(yōu)化問題的一個重要理論與方法。很顯然共邊排樣圖形屬于圖論中的無向圖。圖論中無向圖G是一個非空有限集合V(G)和V(G)中某些元素的無序對的集合E(G)構成,即G=(V,E),其中V=V(G)={v1,v2,…,vn}仍稱為圖G的頂點集;E=E(G)={e1,e2,…,en}稱為圖G的邊集合,E中的每一個元素ek(即V中某兩元素vi,vj的無序對)記為ek=(vi,vj)或ek=vivj,或ek=vjvi(k=1,2,…,m),被稱為該圖的一條邊。圖1排樣圖中都是由首尾連接的直線、圓弧等圖元所構成,直線、圓弧的端點構成圖論表達中的頂點。為了統(tǒng)一并準確地用圖論表達共邊排樣圖形,假設共邊排樣圖形信息已經(jīng)過如下處理:1)共邊圖形信息中已將共邊的較短邊或等邊的某一零件上重合的一邊的圖形信息刪除,如圖2,圖2(a)中兩單一零件Ⅰ,Ⅱ共邊排樣后形成圖2(b),此時應刪除零件Ⅱ短邊eh。顯而易見,若不刪除,后續(xù)圖形信息處理時,仍會自動讀取到這條邊的信息,不但影響圖論表達而且后續(xù)數(shù)控加工編程仍對這一條邊產(chǎn)生加工指令,這樣會產(chǎn)生雖共邊排樣但這些邊仍會重復加工的情況,喪失了共邊排樣共邊切割的本意。2)按圖形系統(tǒng)所記錄的信息,在圖2(b)中頂點e的度數(shù)應為1,而不是3。因為邊bc是由一條直線一次繪制出來的,即不會產(chǎn)生頂點e分割邊bc而形成邊be,ec的情況。在本文中為確保排樣圖是一個連通圖,已采用了一定的算法,能檢測到頂點e在直線bc上,并將其分割為兩段形成邊be,ec。這樣頂點e的度數(shù)已變成了3而不是1。3)共邊排樣前,每一個零件都是由首尾連接的直線、圓弧等圖元所構成的連通的閉路,共邊排樣后由于任一零件至少有一個邊與另一零件相重合,這樣再經(jīng)過2)的處理,則排樣構成的G圖總是連通的。通過上面的分析,圖1用G=(V,E)來表達時,V={v1,v2,…,v17},E={e1,e2,…,e27},e1=(v1,v2),e2=(v2,v3),e3=(v3,v4),…,e27=(v16,v17)。2.2切割路徑及尺寸實際生產(chǎn)中最常見的激光切割機床一般僅有一個激光切割頭也就是一個切割割嘴。按實際切割工藝,共邊切割路徑規(guī)劃問題是:無論任何順序的路徑都要求G圖中所有邊只能被割嘴切割一次(即遍歷一次),而且不得重復切割任何邊。這是因為板材一旦切開會發(fā)生熱變形和移動,若再重復切割則會影響已加工斷面質(zhì)量。這點與G圖某些問題求解可重復走G圖中某些邊是不同的。把割嘴遍歷G圖所有邊當且僅當一次用數(shù)學模型來表達,則需要一系列路徑G=Ρ1∪Ρ2∪?∪ΡΚ,且?i,jΡi∩Ρj=ΦG=P1∪P2∪?∪PK,且?i,jPi∩Pj=Φ對激光切割而言,一個路徑僅需要一個打孔點,而打孔點可選路徑的起點或終點中的任一頂點,當共邊排樣G圖被分解為不同的切割路徑,激光切割共邊排樣件的過程就很容易描述。對圖1而言,若切割路徑優(yōu)化分為5條:path1:v6e10v7e11v8e12v10;path2:v2e6v7e14v10e21v14;path3:v3e7v8e15v11e22v15;path4:v4e8v12e23v16;path5:v9e20v14e25v15e26v16e27v17e24v13e19v12e18v11e17v10e16v9e13v6e5v1e1v2e2v3e3v4e4v5e9v13。且打孔點定為:v6,v14,v3,v16,v9,其打孔順序為:v6,v16,v3,v14,v9。則一個完整的切割過程可表示為:割嘴快速移動到v6(開光打孔)切割→path1→切割path1到v9(關光)快速直線空移→v16?→快速直線空移v16(開光打孔)切割→path4→切割path4到v4(關光)快速直線空移→v3(開光打孔)切割→path3到v15(關光)快速直線空移→v14(開光打孔)切割→path2到v2(關光)快速直線空移→v9(開光打孔)切割→path5到v13(關光,切割完成)。從上述切割路線可看出:共邊切割除打孔及開光切割路徑外,切割過程還包括一個路徑切完后關光快速直線空移到下一個切割路徑,這就是所謂切割過程的空行程。這些問題就構成了共邊切割的路徑優(yōu)化問題:它要求割嘴路徑不但要滿足單割嘴必須遍歷G圖中所有邊當且僅當一次,而且要盡量達到打孔點數(shù)量要少以及切割過程空移行程要短。這個目標正是激光切割機床用戶所關心的。空行程最短能減少機床運行時間,降低成本,而打孔點最少更是十分必要,因為一般情況下激光打孔的時間較長,而且打孔點處的質(zhì)量遠低于連續(xù)切割處的質(zhì)量。通過上述分析,共邊切割路徑優(yōu)化的關鍵是求打孔點少且空行程要短的G圖的路徑劃分及排序。若不同路徑間空行程用dpj表示,共邊切割路徑優(yōu)化的數(shù)學模型就可表示為:對于無向圖G,需求一系列路徑G=Ρ1∪Ρ2∪?∪ΡΚ其中?i,jΡi∩Ρj=Φ且滿足:打孔點最少,minK,空行程最短,minΣdpj(j=1,2,…,K)。3聯(lián)合邊界切割路徑優(yōu)化算法共邊切割路徑優(yōu)化與共邊排樣賦權無向G圖頂點的度數(shù)性質(zhì)有密切的關系。3.1共邊切割的求解算法如果G圖中各頂點的度數(shù)均為偶數(shù),則G圖一定是一個歐拉回路,即可無重復邊一筆繪出,并且由歐拉回路性質(zhì)可知,從任一點出發(fā)都能求得一歐拉回路。這反映在切割上就是僅有一個打孔點且G圖中無空行程一次連續(xù)可切割出零件。假若G圖中僅有兩個頂點vi,vj的度數(shù)為奇數(shù),其某頂點的度數(shù)均為偶數(shù),則一定存在從vi到vj的一條路徑,它經(jīng)過了G各邊一次且無重復邊,這又稱為歐拉通路。這個問題不難理解,連接vi,vj補加一條新邊,則此時G圖變成各頂點的度數(shù)都是偶數(shù),即構成了歐拉回路,求得歐拉回路后,再去掉vi與vj間補加邊即得到vi到vj的歐拉通路。顯然歐拉通路也僅需一個打孔點且一次切割中無空行程。以上兩種情況是最理想的共邊切割情況,而且其解法都與求解歐拉回路有關。當前,求解歐拉回路比較有名的算法是Fleury算法及逐步插入回路算法,然而這些算法都不適應用在共邊切割上。因為在共邊切割時還必須滿足的一個重要約束條件是每個零件僅當G圖中所有內(nèi)部邊切割完后才能從毛坯板上掉下來,也就是當G圖中一個回路被切割掉時,它的內(nèi)部再無別的以該回路任一頂點為公共頂點而形成的任何回路(零件)。這個約束的提出是基于對實際切割工藝過程的考慮:切割中一旦一個回路被切割即這部分板料會因重力而自然下落并使其位置發(fā)生變化。若薄板再受熱變形的影響,其情況更為嚴重。因此不適應以該回路某一公共點在其內(nèi)再進行切割。下面提出一種滿足共邊排樣切割的歐拉回路求解算法。算法1(最理想狀態(tài)下共邊切割路徑算法)設C是共邊排樣歐拉圖中沿著圖形外圍周長的封閉路徑,顯然C是一個歐拉圖。現(xiàn)將G中屬于C的邊全刪去,再去除孤立頂點得圖G1,則G1=G-E(C)中各頂點度數(shù)的奇偶性質(zhì)不變。對于共邊排樣,由于至少有兩個零件,故E(G)-E(C)≠Φ,所以G1可由連通分支G11,G12,…,G1k來表達,即:G1=G11∪G12∪…∪G1k,而且每個最大連通分支G1i(i=1,2,…,k,k≥1)仍為歐拉圖,且G1i互不連通。假若G11,G12,…,G1k歐拉環(huán)游已求出,并令C1i是G1i的歐拉環(huán)游,再回到原來的G圖中,由于G連通,所以每個C1i與C至少有一個公共頂點,設其中之一為VWi∈V(C)(i=1,2,…,k)。由C中的某個點V1出發(fā)沿C前進,每行至一個頂點VWi就是先走完C1i再回到VWi繼續(xù)沿C前進,這樣可以遍歷每一條邊一次且僅一次回到出發(fā)點V0,這樣的行走軌跡就是G的一條共邊切割歐拉環(huán)游。對于C1i的求法,若E(G1i)-E(C1i)=Φ,則C1i就是沿著C1i圖形外圍周長封閉路徑。而E(G1i)-E(C1i)≠Φ,則要先求出沿著G1i圖形外圍周長的封閉路徑,仿照求G的思路,如此繼續(xù)下去,經(jīng)過有限次,即可得到G的歐拉環(huán)游。依據(jù)以上思路,很容易形成一個遞歸的求解共邊切割路徑的算法。圖3(a)是一個共邊排樣后形成的無奇度頂點的無向圖G,圖3(b)是算法1所求得的最終切割路徑,其打孔點為圖示左下角圓點上。3.2edmds-bohns一般情況下,G圖既非歐拉回路又不具有歐拉通路,由圖論知:在任何圖G=(V,E)中,奇度頂點的個數(shù)為偶數(shù),故可設一般情況下G圖中頂點的個數(shù)為2K(顯然K>1)。又由歐拉圖性質(zhì)知,在一個具有2K個奇度頂點的連通圖中,存在K個不變子圖,這些子圖包含了圖G的所有邊,且每個子圖都是一條歐拉通路。這個性質(zhì)揭示了一般情況下K條路徑是必須的,也是足夠的,最小的。即:G=P1∪P2∪P3∪…∪PK,且對任意i,j,Pi∩Pj=Φ。也就是說激光切割最少需要K個打孔點,K條切割路徑即可完成共邊切割。由于K條歐拉通路的求解可通過在2K個奇度點間添加K條邊形成歐拉回路而求解,故現(xiàn)在的問題歸結為如何求出符合K條歐拉通路間空行程最短的K條添加邊,這就啟發(fā)構造一個以所有奇度頂點集合的賦權完全圖F=K2k,由空行程含義知F中每條邊vivj上的權ω就是兩點間的直線距離,即ω=√(vix-vjx)2+(viy-vjy)2。這樣就能保證歐拉通路間空行程最短的K條添加邊的問題就等價于求F的最小權完美匹配,即最小權最大匹配問題。其求解方法可采用當前最好的匹配算法Edmonds-Johason算法求解實現(xiàn)。定義:如果F(V,E,ω)的最大匹配M滿足:ω(M)=min{ω()|是F的最大匹配},則稱M是F的最小權最大匹配。Edmonds-Johason算法的原理是利用最大權匹配問題的線性規(guī)劃模型及其與對偶規(guī)劃問題的關系,采用原始-對偶方法來求解G=(V,E,ω)最大權匹配問題。因此可采用它求出賦權圖F=(V,E,ω)的最小權最大匹配。具體做法如下:構造賦權圖F′=(V,E,ω′),其中ω′(e)=K-ω(e),對一切e∈E,K是足夠大的正常數(shù),可取Κ=Σe∈E|ω(e)|+1。同樣F′中最大權匹配一定是F的最大匹配,這樣用Edmonds-Johason算法求出F′最大權匹配就是F的最小權最大匹配。Edmonds-Johason求解F′最小權最大匹配算法步驟:STEP0:在賦權圖F′=(V,E,ω′)中取匹配M=Φ,對F′的所有頂點vi,令其對偶變量:yi=12max,對F′的所有頂點奇集Sm,令其對偶變量zm=0。并且令k=0。把F′記為。STEP1:在■k中任取一個yv>0的非人造的非飽和點v,如果不存在這樣的頂點,轉STEP5;否則令:E*={vivj|vivj∈Ek且yi+yi+Σm:vivj∈Τmzm=■ij},記■*=■k[E*]。應用生長種上樹的子程序,在■*中生長以v為根的種上樹。子程序結束時,必然有下列三種情況之一發(fā)生:(1)得到一條增廣鏈P,轉STEP2;(2)得到一個花朵B,轉STEP3;(3)得到一個匈牙利樹J。如果J不包含人造頂點,轉STEP4;如果J包含人造頂點vbm,其中vbm是收縮花朵Bm而成的,此時用vbm標號去標記Bm中所有頂點,轉STEP4。STEP2:置M=M⊕E(P),去掉中所有頂點的標號,轉STEP1。STEP3:置k=k+1,Bk=B。把Bk收縮成人造頂點vbk,令其對偶變量zk=0,置M=M/Bk,。并把vbk標以“+”(外點),Bk中所有頂點的標號修改為“+”(外點),轉STEP1,如果v不包含在Bk中,則以v為根繼續(xù)生長種上樹;如果v包含在Bk中,則以vbk為根繼續(xù)生長種上樹。STEP4:令δ1=min{yi|vi∈V0,且vi為外點},,vi為外點,vj未標號},δ3=12min{yi+yj-,vi,vj均為外點,且vi,vj不在同一個人造頂點中},δ4=12min{zm|Sm收縮為人造頂點vbm,且vbm為內(nèi)點},δ=min{δ1,δ2,δ3,δ4}。調(diào)整對偶變量:(Ⅰ)把V0中的每一個外點vi對應的對偶變量yi減去δ;(Ⅱ)把V0中的每一個內(nèi)點vi對應的對偶變量yi加上δ;(Ⅲ)把中每個人造的內(nèi)點vbm對應的對偶變量zm加上2δ;(Ⅳ)把中每個人造的外點vbm對應的對偶變量zm加上2δ。如果δ=δ1,此時存在一個頂點vi的對偶變量yi=0,當vi不是J的根,則把從J的根v到vi的M交錯鏈找出來,置M=M⊕E(),去掉所有頂點的標號,轉STEP1;當vi是J的根,則去掉所有頂點的標號,轉STEP1。如果δ=δ4,此時存在一個人造頂點vbm,其對偶變量zm=0,則應用展開人造頂點的子程序,把vbm展開為奇圈Bm,得到Bm的一個最大匹配Mm,置M=M∪Mm,k=k+1,得到新的賦權圖=(Vk,Ek,ω′),轉STEP1,繼續(xù)生長以v為根的種上樹。如果δ=δ2或δ=δ3,轉STEP1,此時E*將擴大。STEP5:應用展開人造頂點的子程序,按中所有人造頂點的收縮次序的相反次序,把中所有人造頂點展開為奇圈,求出所產(chǎn)生的奇圈上的一個最大匹配。從而所有奇圈上的最大匹配與M的并集就是F′的最大權匹配。添加邊問題解決后就容易得到一般情況下求解共邊切割路徑的求解算法。算法2(一般情況下共邊切割路徑算法)STEP1:求出G中任意一對奇點之間的直線距離dpi,j(i≠j)(i,j=1,2,…,k);STEP2:構造完全圖F,F的頂點對應于G的奇點,其每條邊的權ω=dpij;STEP3:調(diào)用Edmonds-Johason算法求出F的最小權最大匹配M;STEP4:按最小權最大匹配結果添加邊到G中去,得歐拉圖G′;STEP5:調(diào)用算法1(共邊切割歐拉圖路徑算法)求出G′閉跡C,則從C中可方便地形成完整的切割路線及順序。圖1中是奇度頂點的有:v2,v3,v6,v4,v9,v12,v13,v14,v15,v16,共10個。所有這些頂點集合構成的賦權完全圖F=(V,E,ω)經(jīng)Edmonds-Johason算法求得的最小權完美匹配為M={v2v6,v3v4,v9v14,v12v13,v15v16}。經(jīng)算法2求得的最終優(yōu)化切割路徑為:v14e20v9e16v10e14v6快速直線空移→v2e6v7e11v8e15v11e18v12e12v8e7v3e3v4e8v12e19v13快速直線空移→v12e23v16e26v15e22v11e17v10e21v14e25v15快速直線空移→v16e27v17e24v13e9v5e4v4快速直線空移→v3e2v2e1v1e5v6e13v9切割完成。