王 玫 孟正大

(1南京工程學(xué)院工程基礎(chǔ)實(shí)驗(yàn)與訓(xùn)練中心，南京 210013)(2東南大學(xué)自動(dòng)化學(xué)院，南京 210096)

通常的機(jī)器人切割過程中，切割先后順序以及輪廓的切割起始點(diǎn)主要是根據(jù)經(jīng)驗(yàn)安排，作業(yè)編程繁瑣耗時(shí)，經(jīng)常發(fā)生機(jī)器人作業(yè)順序不合理的情況，導(dǎo)致生產(chǎn)周期長，降低生產(chǎn)效率.通過切割優(yōu)化排序可減少機(jī)器人切割加工的空行時(shí)間，提高加工效率.對于切割優(yōu)化排序問題，文獻(xiàn)［1-3］是將切割路徑優(yōu)化問題簡單地抽象為旅行商(traveling saleman problem，TSP)模型，然后利用傳統(tǒng)的遺傳算法、蟻群算法、模擬退火算法等智能算法進(jìn)行優(yōu)化［4］.切割優(yōu)化排序中每一個(gè)切割輪廓都由多個(gè)頂點(diǎn)和邊組成，并且切割順序有內(nèi)外之分，把切割路徑優(yōu)化簡單抽象為常規(guī)的旅行商問題，優(yōu)化效果差.針對以上問題，文獻(xiàn)［5］提出了兩步遺傳算法，先執(zhí)行全局搜索封閉輪廓切割起始點(diǎn)的位置，然后局部搜索最優(yōu)的切割順序，得到的優(yōu)化效果比較好.陳金成等［6-7］對輪廓切割路徑優(yōu)化問題提出了具有主從兩條不同編碼方式染色體的遺傳算法，得到的優(yōu)化結(jié)果能滿足其生產(chǎn)要求.

上述研究基本上都是針對激光和等離子切割，本文以汽車內(nèi)飾件機(jī)器人水切割為研究對象，提出切割優(yōu)化排序方案.對機(jī)器人空行路徑進(jìn)行優(yōu)化，對切割排序問題進(jìn)行分析和建模，提出了基于改進(jìn)禁忌表的蟻群算法，對具有三維空間曲面的汽車內(nèi)飾件中輪廓切割順序和各輪廓起始點(diǎn)同時(shí)進(jìn)行優(yōu)化，實(shí)驗(yàn)表明該算法的可行性與有效性，可在不影響切割質(zhì)量的前提下提高生產(chǎn)效率.

1 水切割路徑規(guī)劃問題分析與建模

1.1 切割路徑規(guī)劃問題分析

本研究的所有切割輪廓均為封閉式切割路徑，即加工的起始點(diǎn)和終止點(diǎn)在同一位置.一個(gè)封閉切割輪廓一般由多個(gè)子路徑組成，兩個(gè)相鄰子路徑的連接點(diǎn)稱為節(jié)點(diǎn)，包括起始節(jié)點(diǎn)和非起始節(jié)點(diǎn).起始節(jié)點(diǎn)是指可作為水刀開始切割或結(jié)束切割的節(jié)點(diǎn)；其他節(jié)點(diǎn)即為非起始節(jié)點(diǎn).對于封閉式的加工路徑，所有節(jié)點(diǎn)均可作為起始節(jié)點(diǎn)，但只能選擇一個(gè).

切割的最終目的是要切割出所有的封閉切割輪廓而形成工件.整個(gè)切割過程是水刀頭從工作零位出發(fā)，快速行進(jìn)到某一內(nèi)部封閉切割輪廓上的切割起始點(diǎn)，然后開高壓水開始切割，依次切割完該有向有序的封閉輪廓又回到切割起始點(diǎn)，然后關(guān)高壓水，快速行進(jìn)到下一個(gè)內(nèi)部封閉輪廓上的切割起始點(diǎn)，重復(fù)前面類似過程，直到切割完所有內(nèi)部封閉輪廓；再關(guān)高壓水，快速行進(jìn)到外部輪廓切割起始點(diǎn)，開高壓水，切割外部輪廓；完成切割后關(guān)高壓水，快速返回到機(jī)器人工作零位，完成整個(gè)工件的切割加工過程.

在切割過程中，工件上各個(gè)切割輪廓的加工順序以及每個(gè)封閉輪廓的切割起始點(diǎn)的選取是否合理直接影響到加工效率，尤其當(dāng)很多加工輪廓分布在一個(gè)具有復(fù)雜空間曲面的工件上.

切割工件中一般包含多個(gè)待切割的內(nèi)部輪廓和外部輪廓，內(nèi)部輪廓又有大小之分.在實(shí)際加工中，按水切割工藝要求，切割排序優(yōu)化過程主要遵循以下幾個(gè)原則:

1)先內(nèi)后外原則 內(nèi)部封閉輪廓切割是指將工件上的內(nèi)部封閉環(huán)路內(nèi)的廢料切除的過程，外部輪廓切割是指沿工件的外部邊緣將整個(gè)工件從材料上切割下來的過程.為避免工件從加工材料中完全切割下來后無法準(zhǔn)確定位，應(yīng)首先切割內(nèi)部輪廓，所有內(nèi)部輪廓切完后，再切割外部輪廓.

2)先小后大原則 在切割過程中，先切小尺寸，以減少對工件剛度的影響，降低材料在高壓水沖擊力下的變形和工件定位誤差.

3)路徑最短原則 路徑最短原則是優(yōu)化排序的最基本原則，是縮短加工時(shí)間和提高生產(chǎn)效率的關(guān)鍵途徑.

最短路徑的選擇可抽象為TSP問題模型，它屬于組合優(yōu)化范疇，已被證實(shí)是一個(gè)NP難題.對于點(diǎn)到點(diǎn)(point to point，PTP)加工，由于每次切割運(yùn)動(dòng)都可簡化為空間的一個(gè)點(diǎn)(相當(dāng)于TSP中的一個(gè)城市)，因此，PTP加工中切割優(yōu)化排序問題可看成常規(guī)的TSP問題.而本文切割模型中的封閉切割輪廓都由若干個(gè)頂點(diǎn)和邊組成，并且切割輪廓有大小和內(nèi)外之分，因此不能簡單抽象為常規(guī)TSP問題.針對水切割輪廓的特殊性，本文提出了一種改進(jìn)禁忌表蟻群算法.為遵循上述原則，這里采用分層思想對切割輪廓進(jìn)行歸類和優(yōu)化:

1)第一層:內(nèi)部很小的孔，在切割路徑中抽象為一個(gè)點(diǎn)，一般為幾何圖形的中心點(diǎn).

2)第二層:比較大的內(nèi)部封閉輪廓，每個(gè)封閉切割輪廓均由不同的邊組成，邊包括直線、曲線等，對于多條邊組成的封閉輪廓，其切割節(jié)點(diǎn)集合包含每條邊的端點(diǎn)，對于僅有單條邊組成的封閉輪廓，可通過離散化，并根據(jù)精度要求均勻選取幾個(gè)離散點(diǎn)組成其切割節(jié)點(diǎn)集.

3)第三層:外部邊緣輪廓(有且僅有一個(gè))，為不影響優(yōu)化效果，與較大封閉輪廓一樣不能簡單抽象為一個(gè)點(diǎn)，其切割節(jié)點(diǎn)集的選取同較大內(nèi)部輪廓.

1.2 切割路徑排序問題建模

定義1 封閉式切割輪廓為環(huán)，記為LOOP，分為內(nèi)環(huán)與外環(huán)，內(nèi)環(huán)又有大環(huán)和小環(huán)之分.任意內(nèi)部小環(huán)記為LOOPTi，將小環(huán)特征點(diǎn)抽象為環(huán)的中心點(diǎn)，記為 Tp，i-0(i=1，2，…，n)；任意內(nèi)部大環(huán)記為LOOPj，其對應(yīng)的切割節(jié)點(diǎn)的總數(shù)記為v，則第j個(gè)內(nèi)部大環(huán)LOOPj對應(yīng)的第k個(gè)切割節(jié)點(diǎn)記為Pj-k(k=1，2，…，v)；外環(huán)記為 LOOPE，其切割節(jié)點(diǎn)總數(shù)為ω，則外環(huán)上任意切割節(jié)點(diǎn)記為 Ep，l(l=1，2，…，ω).環(huán)集為{LOOPT1，…，LOOPTn，LOOP1，…，LOOPm，LOOPE}，頂點(diǎn)集{Tp，1-0，…，Tp，n-0，P1-1，P1-2，…，P1-v(1)，…，Pi-j，…，Pm-v(k)，Ep，1Ep，2，…，Ep，ω}.

水刀從Ps(工作零位)出發(fā)，切割排序優(yōu)化任務(wù)就是指確定各封閉輪廓的切割順序和各輪廓的切割起始點(diǎn)，使切割過程中空移行程的路徑最短.然而，輪廓上的切割起始點(diǎn)從工藝上看并不唯一，在優(yōu)化算法中應(yīng)考慮的切割起始點(diǎn)總數(shù)為所有內(nèi)部封閉輪廓的總切割節(jié)點(diǎn)數(shù)加上外部輪廓總切割節(jié)點(diǎn)數(shù) ω.LOOPTi上的切割起始點(diǎn)記為 Tp，i，LOOPj上的切割起始點(diǎn)記為Pj，LOOPE上的切割起始點(diǎn)記為 PE，顯然 Pj∈{Pj-1，…，Pj-v(k)}；PE∈{Ep，1，…，Ep，ω}.設(shè)對所有封閉輪廓切割起始點(diǎn)的一個(gè)訪問順序?yàn)?T={Ps，tp，1，…，tp，n，t1，…，tm，PE，Ps}，其中ti∈{P1，…，Pm}，則切割路徑的性能指標(biāo)下式:

2 基于改進(jìn)禁忌表蟻群算法的切割路徑優(yōu)化

2.1 改進(jìn)禁忌表蟻群算法

Dorigo等［8］在1991年根據(jù)“螞蟻尋找食物”的集體行為最早提出了蟻群算法的基本模型，1992年，Dorigo又在其博士論文中進(jìn)一步闡述了蟻群算法的核心思想，該算法具有并行分布式正反饋機(jī)制的特點(diǎn)，在路徑優(yōu)化中得到較廣泛的應(yīng)用.

與傳統(tǒng)的蟻群算法相比，在水切割優(yōu)化排序過程中，將水刀看作螞蟻，將封閉輪廓的切割節(jié)點(diǎn)看作城市，螞蟻(水刀)走過路徑上城市(切割節(jié)點(diǎn))的順序自然形成了一個(gè)個(gè)切割排序.由于傳統(tǒng)的蟻群算法是用來優(yōu)化點(diǎn)到點(diǎn)加工類型的TSP問題，而切割優(yōu)化排序問題中每一個(gè)封閉切割輪廓都由多個(gè)頂點(diǎn)和邊組成，并且切割時(shí)遵循先小后大、先內(nèi)后外的約束條件，故需對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，以解決實(shí)際切割優(yōu)化排序問題.由于螞蟻k(k=1，2，…，m)在搜索運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息量確定其轉(zhuǎn)移方向，用禁忌表tabuk(k=1，2，…，m)記錄螞蟻k當(dāng)前所走過的輪廓，tabuk隨著螞蟻的移動(dòng)不斷更新.在搜索過程中，螞蟻根據(jù)各條路徑上的信息素濃度及路徑的啟發(fā)信息計(jì)算狀態(tài)轉(zhuǎn)移概率(t)，而(t)基于禁忌表進(jìn)行計(jì)算，故本文主要是對螞蟻的禁忌表和搜索方法進(jìn)行重新設(shè)計(jì).

利用分層思想將禁忌表劃分為3段:內(nèi)部小環(huán)段、內(nèi)部大環(huán)段、外部輪廓段，各段的優(yōu)先級依次降低.每只螞蟻的禁忌表在初始化時(shí)，需將屬于內(nèi)部大環(huán)和外部輪廓的切割節(jié)點(diǎn)全部設(shè)置為禁忌轉(zhuǎn)移狀態(tài)，內(nèi)部小環(huán)上的切割節(jié)點(diǎn)全部設(shè)置為允許轉(zhuǎn)移狀態(tài).當(dāng)螞蟻訪問完所有內(nèi)部小環(huán)時(shí)，將所有內(nèi)部大環(huán)的切割節(jié)點(diǎn)恢復(fù)為允許轉(zhuǎn)移狀態(tài)，當(dāng)所有內(nèi)部環(huán)都訪問完時(shí)，將外部輪廓的切割節(jié)點(diǎn)恢復(fù)為允許轉(zhuǎn)移狀態(tài)(見圖1).其次，由于每個(gè)封閉輪廓有且僅有一個(gè)切割起始點(diǎn)，而每個(gè)切割輪廓的長度是固定不變的，所以為了簡化計(jì)算，每當(dāng)螞蟻?zhàn)叩竭@個(gè)封閉輪廓上的任意一點(diǎn)時(shí)，屬于該封閉輪廓上的所有切割節(jié)點(diǎn)均不再訪問，即在禁忌表中均設(shè)置為禁忌轉(zhuǎn)移狀態(tài).經(jīng)過這樣的處理，運(yùn)用蟻群算法，在滿足水切割約束條件下，可使螞蟻在搜索封閉輪廓的切割順序時(shí)，同時(shí)也選擇了各個(gè)封閉輪廓的切割起始點(diǎn).

2.2 汽車內(nèi)飾件水切割路徑優(yōu)化方法

基于改進(jìn)禁忌表的蟻群算法的切割路徑優(yōu)化方法主要包括以下幾個(gè)步驟:

①從工件的CAD模型中提取出每個(gè)封閉輪廓的切割節(jié)點(diǎn)，確定螞蟻的搜索空間；

設(shè)m是蟻群中螞蟻的個(gè)數(shù)；n表示所有切割節(jié)點(diǎn)個(gè)數(shù)；bi(t)表示t時(shí)刻位于切割節(jié)點(diǎn)i的螞蟻的個(gè)數(shù)，m=i(t)；Γ ={τij(t)|ci，cj?C} 是t時(shí)刻集合C中元素(切割節(jié)點(diǎn))兩兩連接lij上殘留的信息量的集合.τij(t)表示t時(shí)刻在路徑(i，j)上的信息量.

②初始化時(shí)間t=0和循環(huán)次數(shù)N=0，設(shè)置最大循環(huán)次數(shù)Nmax，將m只螞蟻置于切割工作零位上，螞蟻個(gè)數(shù)k=0，令有向圖上每條邊(i，j)的初始化信息量τij(t)=const，const為常數(shù)，且初始時(shí)刻τij變化量 τij(0)=0.

③按照先小后大，先內(nèi)后外的原則初始化每只螞蟻的禁忌表.

圖1 改進(jìn)蟻群禁忌表搜索過程

式中，α為信息啟發(fā)式因子；β為期望啟發(fā)式因子；allowedk={C－tabuk}表示螞蟻k下一步允許選擇的節(jié)點(diǎn)集合；ηij(t)為啟發(fā)函數(shù)，其計(jì)算如下式:

式中，dij表示相鄰兩節(jié)點(diǎn)距離.為防止殘留信息素過多造成啟發(fā)信息被殘留信息淹沒，當(dāng)每只螞蟻搜索完所有節(jié)點(diǎn)后，需更新處理螞蟻殘留信息，在t+n時(shí)刻在路徑(i，j)上的信息量按下式調(diào)整［8］:

式中，ρ∈［0，1］表示信息素?fù)]發(fā)系數(shù)，則1－ρ為信息素殘留系數(shù)；Δτij(t)表示本次循環(huán)中(i，j)上信息素增量，初始時(shí)刻 Δτij(0)=0，(t)表示第k只螞蟻在本次循環(huán)中留在路徑(i，j)上的信息量.應(yīng)用Ant-Cycle模型更新信息量，即螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，Δt)的求法為

式中，Q表示信息素濃度；Lk表示第k只螞蟻在本次循環(huán)中所走的路徑總長度.針對復(fù)雜空間曲面，本文采用安全平面方法規(guī)劃兩節(jié)點(diǎn)間的無碰過渡路徑，計(jì)算路徑長度.

⑤搜索完內(nèi)部小環(huán)后，修改內(nèi)部大環(huán)的禁忌表，按④同樣方法搜索內(nèi)部大環(huán)，在選擇內(nèi)部大環(huán)順序的同時(shí)，也選擇了其切割起始點(diǎn).

⑥內(nèi)部大環(huán)搜索完后，修改外部輪廓的禁忌表，對外部輪廓的節(jié)點(diǎn)進(jìn)行搜索.

⑦按式(4)與(5)更新每條路徑上的信息量.

⑧若滿足條件，即若循環(huán)次數(shù)N達(dá)到最大循環(huán)次數(shù)Nmax，則循環(huán)結(jié)束并輸出程序計(jì)算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到③.

3 切割優(yōu)化排序結(jié)果與分析

圖2中給出了待優(yōu)化的工件切割輪廓信息，待切輪廓包含10個(gè)小孔，5個(gè)大輪廓以及1個(gè)外部邊緣，共有48個(gè)切割節(jié)點(diǎn).采用第2節(jié)介紹的改進(jìn)禁忌表蟻群算法，令蟻群算法參數(shù)如下:螞蟻個(gè)數(shù)為60，最大迭代次數(shù)為50，信息啟發(fā)因子為1，期望啟發(fā)因子為5，信息揮發(fā)系數(shù)為0.8，信息素強(qiáng)度為100.迭代后得到的優(yōu)化排序結(jié)果及各輪廓切割起始點(diǎn)如圖2所示，路徑長度為10039.428 mm，滿足先小后大、先內(nèi)后外的原則.

將優(yōu)化得到的水切割路徑數(shù)據(jù)，轉(zhuǎn)化為MOTOMAN UP-20機(jī)器人程序，進(jìn)行水切割實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明采用改進(jìn)禁忌表蟻群算法，對本文中的切割排序規(guī)劃問題能進(jìn)行很好的優(yōu)化，通過對各輪廓切割順序規(guī)劃和切割起始點(diǎn)的選擇，能很好地優(yōu)化空行路徑.由此可見，采用改進(jìn)禁忌表蟻群算法是可行的、有效的.同時(shí)，將該方法與遺傳算法進(jìn)行了比較，在優(yōu)化效果相同的情況下，優(yōu)化速度比后者快得多.

4 結(jié)語

圖2 改進(jìn)禁忌表蟻群算法優(yōu)化結(jié)果

本文以汽車內(nèi)飾件水切割路徑優(yōu)化為研究對象，對切割優(yōu)化排序問題進(jìn)行分析和建模，提出了一種改進(jìn)禁忌表蟻群算法.根據(jù)水切割過程特點(diǎn)和工藝要求，設(shè)計(jì)了改進(jìn)的禁忌表，利用分層思想可將禁忌表劃分為3段:內(nèi)部小環(huán)段、內(nèi)部大環(huán)段、外部輪廓段，各段的優(yōu)先級依次降低，確定了與此相應(yīng)的禁忌表的更新規(guī)則.在此基礎(chǔ)上，給出了基于改進(jìn)禁忌表蟻群算法的水切割路徑優(yōu)化排序方法.仿真與實(shí)驗(yàn)結(jié)果表明，改進(jìn)禁忌表蟻群算法在解決水切割優(yōu)化排序問題中是可行、有效的，可大大縮短水切割機(jī)器人的示教編程時(shí)間，顯著提高水切割作業(yè)的效率和質(zhì)量.

References)

［1］李妮妮，陳章位，陳世澤.基于局部搜索和遺傳算法的激光切割路徑優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(2):234-239.Li Nini，Chen Zhangwei，Chen Shize.Optimization of laser cutting path based on local search and genetic algorithm ［J］.Computer Engineering and Applications，2010，46(2):234-239.(in Chinese)

［2］何漢武.數(shù)控等離子切割機(jī)的路徑優(yōu)化［D］:上海:上海交通大學(xué)電子信息與電氣工程學(xué)院，2008.

［3］劉會(huì)霞，王霄，蔡蘭.鈑金件數(shù)控激光切割割嘴路徑的優(yōu)化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)，2004，16(5):660-665.Liu Huixia，Wang Xiao，Cai Lan.Torch path optimization for nc laser cutting of sheet metal part［J］.Journal of Computer Aided Design＆Computer Graphics，2004，16(5):660-665.(in Chinese)

［4］高海昌，馮博琴，朱利.智能優(yōu)化算法求解TSP問題［J］.控制與決策，2006，21(3):241-248.Gao Haichang，F(xiàn)eng Boqin，Zhu Li.Reviews of the meta-heuristic algorithms for TSP［J］.Control and Decision，2006，21(3):241-248.(in Chinese)

［5］Lee Moon-Kyu，Kwon Ki-Bum.Cutting path optimization in CNC cutting processes using a two-step genetic algorithm ［J］.International Journal of Production Research，2006，44(24):5307-5326.

［6］Chen J C，Zhong T X.A hybrid-code genetic algorithm based optimization of non-productive paths in CNC machining［J］.The International Journal of Advanced Manufacturing Technology，2002，20(3):163-168.

［7］陳金城.多軸聯(lián)動(dòng)高性能數(shù)控加工的運(yùn)動(dòng)優(yōu)化與復(fù)雜軌跡實(shí)時(shí)控制策略［D］:上海:上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，2001.

［8］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，2005:25-45.