曾德標(biāo), 萬世明, 李迎光, 劉 勇, 李東明
(1. 成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司技術(shù)裝備公司,四川 成都 610092;2. 南京航空航天大學(xué)機(jī)電學(xué)院,江蘇 南京 210016)
裝配機(jī)器人加工站位設(shè)置混合優(yōu)化算法
曾德標(biāo)1, 萬世明1, 李迎光2, 劉 勇1, 李東明1
(1. 成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司技術(shù)裝備公司,四川 成都 610092;2. 南京航空航天大學(xué)機(jī)電學(xué)院,江蘇 南京 210016)
為了降低生產(chǎn)成本,提高生產(chǎn)效率,裝配機(jī)器人開展加工作業(yè)需要優(yōu)化設(shè)置加工站位以減少機(jī)器人數(shù)量或機(jī)器人轉(zhuǎn)換加工站位的次數(shù)。提出一種結(jié)合聚類算法與模擬退火算法的加工站位設(shè)置混合優(yōu)化算法。首先通過聚類算法合并可在相同站位下加工的加工對(duì)象以減小問題規(guī)模,然后采用多解并行搜索模擬退火算法優(yōu)化選擇加工全部加工對(duì)象所需的最少加工站位。實(shí)際測試表明該算法能夠在顯著改善優(yōu)化結(jié)果的同時(shí)大幅提高算法收斂的速度。
機(jī)器人;加工站位;聚類算法;模擬退火算法
工業(yè)機(jī)器人具有高度的靈活性和可靠性,廣泛應(yīng)用于汽車、航空、電子、機(jī)械等制造領(lǐng)域。由于工業(yè)機(jī)器人的有效工作空間區(qū)域有限,對(duì)于尺寸較小的單一加工對(duì)象或者多個(gè)分布集中的加工對(duì)象,單臺(tái)機(jī)器人可在一個(gè)固定的加工站位(即機(jī)器人在內(nèi)部軸歸零后相對(duì)于加工對(duì)象的位置和姿
態(tài))加工完所有加工對(duì)象。若加工對(duì)象尺寸比較大或?qū)ο蠖嗲曳稚ⅲ瑒t可采用多臺(tái)機(jī)器人在不同的加工站位同時(shí)加工,或者通過外部軸來擴(kuò)展單臺(tái)機(jī)器人的有效工作空間[1]以覆蓋全部加工對(duì)象。后者又可分為 2種加工模式:①聯(lián)動(dòng)加工,外部軸與機(jī)器人各關(guān)節(jié)聯(lián)動(dòng)并連續(xù)加工完成一個(gè)較大的加工對(duì)象,如邵秋萍等[2]研制的機(jī)器人弧焊工作站;②分站加工,外部軸將機(jī)器人或工件移動(dòng)至不同的加工站位,機(jī)器人在每個(gè)站位上完成一部分加工對(duì)象的加工,最終完成全部加工,如田威等[3]研制的機(jī)器人自動(dòng)鉆鉚系統(tǒng)。單臺(tái)機(jī)器人固定站位加工、多臺(tái)機(jī)器人多站位同時(shí)加工以及單臺(tái)機(jī)器人分站加工均需要優(yōu)化設(shè)置加工站位。文獻(xiàn)[4]研究了機(jī)器人焊接的加工站位優(yōu)化設(shè)置問題,通過構(gòu)建焊縫可達(dá)性、機(jī)器人靈巧性、焊槍運(yùn)動(dòng)平穩(wěn)性等多目標(biāo)融合的優(yōu)化目標(biāo)函數(shù),并采用遺傳算法求解機(jī)器人完成整條焊縫焊接的最佳站位。文獻(xiàn)[5]研究了機(jī)器人白車身點(diǎn)焊加工站位的設(shè)置問題,首先針對(duì)給定的一組焊接對(duì)象分析機(jī)器人可行安裝區(qū)域,然后選擇機(jī)器人可行安裝區(qū)域的中心位置作為焊接該組加工對(duì)象的機(jī)器人加工站位,若無可行安裝區(qū)域則重新選擇加工區(qū)域更大的機(jī)器人。文獻(xiàn)[3]針對(duì)具有單個(gè)外部軸的工業(yè)機(jī)器人自動(dòng)鉆鉚系統(tǒng),在給定機(jī)器人站位設(shè)置的條件下,研究了加工對(duì)象的站位劃分問題以及機(jī)器人轉(zhuǎn)站的精確定位控制問題。上述文獻(xiàn)從加工對(duì)象的可達(dá)性、機(jī)器人靈巧性、加工過程平穩(wěn)性和加工精度等方面對(duì)加工站位的設(shè)置問題進(jìn)行了研究,但沒有研究如何優(yōu)化設(shè)置加工站位的數(shù)量,即如何使得完成全部加工對(duì)象加工所需的加工站位數(shù)最少。本文針對(duì)飛機(jī)裝配領(lǐng)域的工業(yè)機(jī)器人加工作業(yè),研究加工站位優(yōu)化設(shè)置問題,以在確保加工精度的前提下,使得加工完所有加工對(duì)象所需總的加工站位數(shù)最少,從而減少機(jī)器人的數(shù)量或機(jī)器人轉(zhuǎn)換加工站位的次數(shù),節(jié)約生產(chǎn)成本并提高生產(chǎn)效率。
1.1 優(yōu)化模型
為了簡化計(jì)算,將機(jī)器人加工站位所在的連續(xù)位姿空間離散化,得到一組離散的站位 W=。將機(jī)器人加工站位優(yōu)化設(shè)置問題轉(zhuǎn)變成從集合W中優(yōu)化選擇加工站位問題(優(yōu)化問題1):從集合W中選擇一組最少的加工站位用于加工完所有的加工對(duì)象,其數(shù)學(xué)模型為
1.2 聚類算法
若機(jī)器人在加工站位 w下可以對(duì)加工對(duì)象 t進(jìn)行加工且滿足加工精度要求,則稱w為t的可行加工站位,t為w的可加工對(duì)象,記為:w→t。用OW和 OT分別表示加工站位的集合和加工對(duì)象的集合,定義序偶:O = 〈OW, OT〉,OW≠ φ,OT≠ φ,表示w→t,?w ? OW,?t ? OT。通過加工對(duì)象的可加工性分析,可以得到在滿足加工精度要求的條件下每個(gè)加工對(duì)象的可行加工站位。若某個(gè)加工對(duì)象沒有可行加工站位,則不考慮該加工對(duì)象。將可加工性分析結(jié)果表示為一個(gè)序偶集:M = {O1, O2, ·· , Om},其中OTi= {ti},ti(i = 1, 2,··, m)為加工對(duì)象。定義序偶的聚類運(yùn)算
若聚類運(yùn)算的結(jié)果不為φ,則O′仍然是一個(gè)有效的序偶。將集合M中的不同元素兩兩之間進(jìn)行聚類運(yùn)算得到的結(jié)果(不含φ)組成第1代集合M1。若M中的某個(gè)元素與其他所有元素的聚類運(yùn)算結(jié)果均為φ,則將該元素直接加入M1,且不再參與后續(xù)運(yùn)算。剔除M1中的冗余元素。對(duì)M1做與M同樣的
處理得到第2代集合M2,對(duì)M2做與M同樣的處理得到第3代集合M3,……。如此類推,直到某一代集合 Mmax只有一個(gè)元素或其中的元素兩兩之間的聚類運(yùn)算結(jié)果均為φ時(shí)為止。將Mmax表示為
其中,Oi′= 〈O′Wi, O'Ti〉,i = 1, …, m′。上述聚類運(yùn)算過程如圖1所示,其中數(shù)字序號(hào)代表加工對(duì)象,每一個(gè)圓所包圍的黑點(diǎn)構(gòu)成對(duì)應(yīng)加工對(duì)象的可行加工站位的集合。圖 1(a)表示序偶集 M = {O1, O2, …, O8},其中OTi= {i}。對(duì)集合M進(jìn)行聚類運(yùn)算得到的第 1代集合 M1如圖 1(b)所示,對(duì)集合M1進(jìn)行聚類運(yùn)算得到第二代集合M2,也是最終結(jié)果Mmax,如圖1(c)所示。由圖1(c)可以看出,聚類運(yùn)算實(shí)際上合并了具有相同可行加工站位的加工對(duì)象,優(yōu)化問題1等價(jià)于從集合Mmax中選擇一組最少的序偶,且每個(gè)被選序偶的加工對(duì)象集的并集等于全體加工對(duì)象的集合T。這樣一來,從每個(gè)被選序偶的加工站位集中各自任意選擇一個(gè)加工站位組成的一組加工站位,就能完成對(duì)全體加工對(duì)象的加工,且加工站位數(shù)是最少的。該問題的數(shù)學(xué)模型(優(yōu)化問題2)為
其中,xi(i = 1, 2,··, m')是與序偶Oi′對(duì)應(yīng)的二值整型變量,F(xiàn)(wi)是加工對(duì)象集。若序偶Oi′被選中,則xi= 1,F(xiàn)(wi) =OT′i;否則xi= 0,F(xiàn)(wi) = φ。
圖1 聚類運(yùn)算
優(yōu)化問題1,2的數(shù)學(xué)模型是完全一樣的,但是兩個(gè)問題需要優(yōu)化選擇的對(duì)象和范圍是不一樣的。在優(yōu)化問題 1中,優(yōu)化選擇的對(duì)象是加工站位,選擇范圍為加工站位集W,解空間為W的全部基數(shù)小于或等于m in(|W|,|T|)的非空子集,解空間大小為
其中,符號(hào)|W|表示集合W的基數(shù),亦即集合W的元素個(gè)數(shù)。在優(yōu)化問題2中,選擇的對(duì)象是序偶,選擇范圍為序偶集Mmax,解空間為Mmax的全部基數(shù)小于或等于 m in(|Mmax|,|T|)的非空子集,解空間大小為
根據(jù)聚類運(yùn)算的過程及圖 1(c)可看出,|Mmax|必然小于或等于|W|,在多數(shù)情況下會(huì)遠(yuǎn)小于|W|,因此,s2一般遠(yuǎn)小于s1。亦即優(yōu)化問題2的選擇范圍相對(duì)于優(yōu)化問題 1變小了,所以通過聚類運(yùn)算可以減小問題的規(guī)模,改善SA的站位優(yōu)化結(jié)果。下面采用多解并行搜索SA求解優(yōu)化問題2。
1.3 改進(jìn)模擬退火算法優(yōu)化加工站位
為了改善SA的優(yōu)化結(jié)果,本文采取多種策略對(duì)簡單SA進(jìn)行改進(jìn)。先采用一組解在解空間中并行搜索,并輔以禁忌策略,盡量避免狀態(tài)產(chǎn)生函數(shù)生成與當(dāng)前解集中的解相同的候選解,加大對(duì)解空間的覆蓋面,增大跳出局部極小值的概率。然后依概率進(jìn)行啟發(fā)式搜索,其是指狀態(tài)產(chǎn)生函數(shù)按照一定的啟發(fā)式規(guī)則由當(dāng)前解生成一個(gè)不次于當(dāng)前解的候選解。在迭代搜索的初期,采用隨機(jī)搜索的概率大于采用啟發(fā)式搜索,以便候選解盡
可能覆蓋全解空間,避免陷入局部極小值;在迭代搜索的后期,采用啟發(fā)式搜索的概率要大于采用隨機(jī)搜索,以便使算法盡快收斂,并且不會(huì)破壞優(yōu)質(zhì)解的編碼結(jié)構(gòu),從而更易找到全局最優(yōu)解。在迭代末期采取反復(fù)升溫的策略,當(dāng)溫度低于設(shè)定閾值時(shí)重新升溫以增大采用隨機(jī)搜索和接受劣化解的概率,從而有助于跳出局部極小值,找到全局最優(yōu)解。整個(gè)SA結(jié)束的準(zhǔn)則是重升溫的次數(shù)達(dá)到了設(shè)定的最大升溫次數(shù)。多解并行搜索SA的詳細(xì)算法流程如下:
多解并行搜索主算法:
步驟1. 算法初始化:
(1) 設(shè)置SA的參數(shù);
(2) 隨機(jī)生成一組初始解;
(3) 歷史最優(yōu)解設(shè)為初始解中的最優(yōu)解。
步驟2. 令升溫次數(shù)i = 0,溫度t等于初始溫度。
步驟3. 降溫循環(huán):
(1) 計(jì)算重新生成候選解的最大許可次數(shù)
其中,μ0是產(chǎn)生候選解的最小次數(shù),λ是控制產(chǎn)生候選解的最大許可次數(shù)隨溫度t變化速率的參數(shù),μ0和λ取值均為正整數(shù),符號(hào)?x?表示小于或等于x的最大整數(shù)。
(2) 計(jì)算當(dāng)前解集的平均基數(shù);
(3) 令解的序號(hào)j = 1;
(4) 多解搜索循環(huán):
①取出當(dāng)前解集中的第j個(gè)解,計(jì)算第j個(gè)解的基數(shù);
②令生成候選解的次數(shù)k = 0,采用等溫搜索算法進(jìn)行等溫搜索循環(huán);
③令解的序號(hào)j = j + 1,若j小于當(dāng)前解集中解的個(gè)數(shù),則轉(zhuǎn)①;否則轉(zhuǎn)(5),跳出該循環(huán);
(5) 若歷史最優(yōu)解不存在于當(dāng)前解集中,則用歷史最優(yōu)解替換當(dāng)前解集中的最差解,然后降溫;
(6) 若溫度t小于設(shè)定的閾值,則適當(dāng)升溫,并令升溫次數(shù)i = i + 1;
(7) 若升溫次數(shù)i大于設(shè)定的最大升溫次數(shù),終止算法,輸出歷史最優(yōu)解;否則轉(zhuǎn)(1)。
等溫搜索子算法:
步驟1. 令生成候選解的次數(shù)k = k + 1。
步驟2. 令禁忌搜索次數(shù)p = 0。
步驟3. 禁忌搜索循環(huán):
(1) 令禁忌搜索次數(shù)p = p + 1;
(2) 計(jì)算采用啟發(fā)式搜索的概率Ph
(3) 隨機(jī)生成一個(gè)0到1之間的隨機(jī)數(shù)r,若Ph> r,則由當(dāng)前解采用啟發(fā)式方法搜索產(chǎn)生候選解;否則采用隨機(jī)方式搜索產(chǎn)生候選解;
(4) 判斷候選解是否存在于當(dāng)前解集中,若存在則轉(zhuǎn)(5);否則轉(zhuǎn)步驟4,跳出禁忌搜索循環(huán);
(5) 判斷禁忌搜索次數(shù)p是否小于重新生成候選解的最大許可次數(shù)f(t),若小于則轉(zhuǎn)(1);否則轉(zhuǎn)步驟4,跳出禁忌搜索循環(huán)。
步驟4. 計(jì)算候選解的基數(shù)。
步驟5. 若候選解的基數(shù)比第j個(gè)解的基數(shù)或當(dāng)前解集的平均基數(shù)小,則用候選解替代第 j個(gè)解,轉(zhuǎn)步驟6;否則轉(zhuǎn)步驟7。
步驟6. 若候選解的基數(shù)比歷史最優(yōu)解的基數(shù)小,用候選解替代歷史最優(yōu)解,轉(zhuǎn)步驟9。
步驟7. 計(jì)算接受劣化解的概率Pb
其中,ΔC為當(dāng)前解的基數(shù)與當(dāng)前解集的平均基數(shù)中的最大值與候選解的基數(shù)的差。
步驟8. 隨機(jī)生成一個(gè)0到1之間的隨機(jī)數(shù)r,若Pb> r,則用候選解替代第j個(gè)解,轉(zhuǎn)步驟9。
步驟9. 判斷生成候選解的次數(shù)k是否小于設(shè)定值,若小于則轉(zhuǎn)步驟1;否則結(jié)束。
以圖 2所示制孔機(jī)器人為例說明上述加工站位混合優(yōu)化算法的使用方法。圖中制孔機(jī)器人需要鉆制工件上均勻分布的 8個(gè)孔位 t1~t8。原始的加工站位優(yōu)化設(shè)置問題是在機(jī)器人第七軸(地面導(dǎo)軌)上設(shè)置最少的加工站位,并能加工完所有孔位。為了簡化計(jì)算,將機(jī)器人的加工站位空間離散成11個(gè)均勻分布在第七軸上的站位 w1~w11??孜?ti可以被站位wi至wi+3下的機(jī)器人加工,用序偶集表示為
將加工站位優(yōu)化設(shè)置問題轉(zhuǎn)變成加工站位優(yōu)化選擇問題(優(yōu)化問題1):從11個(gè)站位中選擇最少的一組加工站位用于加工8個(gè)孔位,解空間大小為
序偶集M通過聚類方法最終得到的序偶集為:
將加工站位優(yōu)化選擇問題進(jìn)一步轉(zhuǎn)化為序偶的優(yōu)化選擇問題(優(yōu)化問題2):從集合Mmax的5個(gè)序偶中選擇最少的一組序偶,并且每個(gè)被選序偶的加工對(duì)象集的并集等于全部 8個(gè)孔位的集合,解空間大小為
圖2 加工對(duì)象聚類
可見,通過聚類運(yùn)算大幅減小了解空間,有效地縮減了加工站位優(yōu)化問題的規(guī)模,有利于SA找到全局最優(yōu)解并加快收斂速度。然后采用多解并行搜索SA求解優(yōu)化問題2,得出加工完8個(gè)孔位所需的最少加工站位為w4和w8。
為了驗(yàn)證上述優(yōu)化算法的有效性,用一組模擬加工數(shù)據(jù)對(duì)算法進(jìn)行了測試。模擬加工數(shù)據(jù)有108個(gè)加工對(duì)象,機(jī)器人加工站位分布空間離散化得到3 066個(gè)加工站位,為每個(gè)加工對(duì)象分配了數(shù)量不等的加工站位。經(jīng)過聚類運(yùn)算得到了包含245個(gè)元素的序偶集。然后用 4種算法優(yōu)化選擇加工站位,分別是簡單 SA、聚類運(yùn)算結(jié)合簡單 SA、改進(jìn) SA、以及聚類運(yùn)算結(jié)合改進(jìn) SA。每種算法獨(dú)立測試60次,測試結(jié)果如表1所示。對(duì)比算法1和2,通過加入聚類算法能夠顯著改善優(yōu)化結(jié)果并加快SA的收斂速度。對(duì)比算法1和3,改進(jìn)SA能夠更有效地改善優(yōu)化結(jié)果并加快算法收斂速度。對(duì)比算法3和4,聚類算法能在改進(jìn)SA的基礎(chǔ)上進(jìn)一步改善優(yōu)化結(jié)果,但對(duì)于算法收斂性沒有進(jìn)一步改善。從模擬加工數(shù)據(jù)的測試結(jié)果可知,本文提出的聚類結(jié)合改進(jìn)SA相對(duì)于簡單SA無論在尋優(yōu)結(jié)果還是收斂速度方面都有顯著的優(yōu)勢。
表1 模擬加工數(shù)據(jù)測試結(jié)果
為了進(jìn)一步驗(yàn)證加工站位設(shè)置混合優(yōu)化算法的有效性,用圖3所示的工件對(duì)算法進(jìn)行了測試。圖中為小型飛機(jī)的機(jī)身模擬件,機(jī)身內(nèi)部是由框、梁連接而成的骨架,機(jī)身外表面用蒙皮覆蓋,蒙皮與骨架用鉚釘連接。待鉆的鉚釘孔數(shù)量約為3 000個(gè),測試用的鉆孔機(jī)器人為KUKA KR200-1。經(jīng)過多次測試,采用KUKA KR200-1型機(jī)器人加工完所有鉚釘孔需要3個(gè)加工站位,其分布如圖3所示。
圖3 模擬件測試
本文提出了基于聚類算法和改進(jìn) SA的機(jī)器人加工站位設(shè)置混合優(yōu)化算法。首先將加工站位分布的連續(xù)位姿空間離散化,得到一組均勻分布的離散化加工站位。通過分析加工對(duì)象的可加工性,得到每個(gè)加工對(duì)象能夠被哪些站位下的機(jī)器人加工。然后用聚類算法將相同加工站位下可加工對(duì)象合并,以此縮減問題的規(guī)模,提高SA找到全局最優(yōu)解的概率和收斂速度。最后采用多解并行搜索 SA優(yōu)化選擇加工站位。通過實(shí)際測試表明,該算法能夠在顯著改善加工站位優(yōu)化結(jié)果的同時(shí)大幅提高算法的收斂速度。但是該算法需要對(duì)機(jī)器人加工站位所在的連續(xù)空間進(jìn)行離散化處理,離散的步長越長,可選的加工站位越少,加工站位優(yōu)化選擇的結(jié)果也會(huì)越差;另一方面,離散的網(wǎng)格步長越短,可選的加工站位越多,SA找到全局最優(yōu)解的概率也越小,同時(shí)優(yōu)化的時(shí)間也越長。因此對(duì)加工站位分布空間進(jìn)行離散化的最佳步長仍需要進(jìn)一步研究。
[1] 黃 進(jìn), 胡 英, 馬 孜, 等. 基于粒子群優(yōu)化算法的工業(yè)機(jī)器人與外部軸標(biāo)定[J]. 機(jī)械工程學(xué)報(bào), 2009, 45(7): 63-67.
[2] 邵秋萍, 劉極峰, 王孜凌. 基于外部軸控制的塞拉門機(jī)器人弧焊工作站[J]. 機(jī)械設(shè)計(jì)與制造, 2006, (9): 117-119.
[3] 田 威, 戴家隆, 周衛(wèi)雪, 等. 附加外部軸的工業(yè)機(jī)器人自動(dòng)鉆鉚系統(tǒng)分站式任務(wù)規(guī)劃與控制技術(shù)[J]. 中國機(jī)械工程, 2014, 25(1): 23-27.
[4] 何廣忠, 高洪明, 吳 林. 機(jī)器人弧焊離線編程與仿真系統(tǒng)的設(shè)計(jì)[J]. 焊接, 2006, (2): 24-28.
[5] 林巨廣, 湯東華. DELM IA在機(jī)器人白車身點(diǎn)焊工作站規(guī)劃設(shè)計(jì)中的應(yīng)用[J]. 機(jī)械設(shè)計(jì)與制造, 2010, (12): 90-92.
[6] Pham D T, Karaboga D. Intelligent optim isation techniques: genetic algorithms, tabu search, simulated annealing and neural networks [M]. London: Springer, 2000: 187-217.
[7] 李金林, 譚建榮. 改進(jìn)模擬退火算法在配氣凸輪機(jī)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用[J]. 工程圖學(xué)學(xué)報(bào), 2006, 27(1): 19-23.
[8] 董德威, 顏云輝. 缺陷板材非規(guī)則件優(yōu)化排樣[J]. 圖學(xué)學(xué)報(bào), 2013, 34(2): 31-37.
[9] 許良鳳, 林 輝, 胡 敏, 等. 基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割[J]. 工程圖學(xué)學(xué)報(bào), 2011, 32(5): 25-29.
A Hybrid Optim ization Algorithm for Working Position Setting of Assembling Robot
Zeng Debiao1, Wan Shim ing1, Li Yingguang2, Liu Yong1, Li Dongm ing1
(1. Institute of Technology and Equipment, Chengdu Aircraft Industry (Group) Co. Ltd., Chengdu Sichuan 610092, China; 2. College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu 210016, China)
In order to reduce production cost and increase productive efficiency, working positions of assembling robots need to be optim ized to reduce the number of robots and the times of changing working positions. A hybrid optim ization algorithm combining clustering algorithm and simulated annealing algorithm was proposed to optim ize working positions of robots. Firstly, processing objects w ith common available working positions of robots were clustered by the clustering algorithm in order to reduce the scale of the problem. Then, a simulated annealing algorithm w ith multi-solution parallel search was employed to search for the m inimum working positions of robots available for processing all objects. Testing results show that this algorithm is capable of improving optimization result significantly as well as accelerating the convergence of the algorithm remarkably.
robot; working position; clustering algorithm; simulated annealing algorithm
TP 391
10.11996/JG.j.2095-302X.2016040496
A
2095-302X(2016)04-0496-06
2015-11-25;定稿日期:2015-12-28
曾德標(biāo)(1985–),男,四川達(dá)州人,博士。主要研究方向?yàn)橛?jì)算機(jī)輔助工藝規(guī)劃、飛機(jī)數(shù)字化裝配。E-mail:debiaozeng@126.com