曾德標， 萬世明， 李迎光， 劉 勇， 李東明

(1. 成都飛機工業(yè)(集團)有限責任公司技術(shù)裝備公司，四川 成都 610092；2. 南京航空航天大學(xué)機電學(xué)院，江蘇 南京 210016)

裝配機器人加工站位設(shè)置混合優(yōu)化算法

曾德標1， 萬世明1， 李迎光2， 劉 勇1， 李東明1

(1. 成都飛機工業(yè)(集團)有限責任公司技術(shù)裝備公司，四川 成都 610092；2. 南京航空航天大學(xué)機電學(xué)院，江蘇 南京 210016)

為了降低生產(chǎn)成本，提高生產(chǎn)效率，裝配機器人開展加工作業(yè)需要優(yōu)化設(shè)置加工站位以減少機器人數(shù)量或機器人轉(zhuǎn)換加工站位的次數(shù)。提出一種結(jié)合聚類算法與模擬退火算法的加工站位設(shè)置混合優(yōu)化算法。首先通過聚類算法合并可在相同站位下加工的加工對象以減小問題規(guī)模，然后采用多解并行搜索模擬退火算法優(yōu)化選擇加工全部加工對象所需的最少加工站位。實際測試表明該算法能夠在顯著改善優(yōu)化結(jié)果的同時大幅提高算法收斂的速度。

機器人；加工站位；聚類算法；模擬退火算法

工業(yè)機器人具有高度的靈活性和可靠性，廣泛應(yīng)用于汽車、航空、電子、機械等制造領(lǐng)域。由于工業(yè)機器人的有效工作空間區(qū)域有限，對于尺寸較小的單一加工對象或者多個分布集中的加工對象，單臺機器人可在一個固定的加工站位(即機器人在內(nèi)部軸歸零后相對于加工對象的位置和姿

態(tài))加工完所有加工對象。若加工對象尺寸比較大或?qū)ο蠖嗲曳稚?，則可采用多臺機器人在不同的加工站位同時加工，或者通過外部軸來擴展單臺機器人的有效工作空間[1]以覆蓋全部加工對象。后者又可分為 2種加工模式：①聯(lián)動加工，外部軸與機器人各關(guān)節(jié)聯(lián)動并連續(xù)加工完成一個較大的加工對象，如邵秋萍等[2]研制的機器人弧焊工作站；②分站加工，外部軸將機器人或工件移動至不同的加工站位，機器人在每個站位上完成一部分加工對象的加工，最終完成全部加工，如田威等[3]研制的機器人自動鉆鉚系統(tǒng)。單臺機器人固定站位加工、多臺機器人多站位同時加工以及單臺機器人分站加工均需要優(yōu)化設(shè)置加工站位。文獻[4]研究了機器人焊接的加工站位優(yōu)化設(shè)置問題，通過構(gòu)建焊縫可達性、機器人靈巧性、焊槍運動平穩(wěn)性等多目標融合的優(yōu)化目標函數(shù)，并采用遺傳算法求解機器人完成整條焊縫焊接的最佳站位。文獻[5]研究了機器人白車身點焊加工站位的設(shè)置問題，首先針對給定的一組焊接對象分析機器人可行安裝區(qū)域，然后選擇機器人可行安裝區(qū)域的中心位置作為焊接該組加工對象的機器人加工站位，若無可行安裝區(qū)域則重新選擇加工區(qū)域更大的機器人。文獻[3]針對具有單個外部軸的工業(yè)機器人自動鉆鉚系統(tǒng)，在給定機器人站位設(shè)置的條件下，研究了加工對象的站位劃分問題以及機器人轉(zhuǎn)站的精確定位控制問題。上述文獻從加工對象的可達性、機器人靈巧性、加工過程平穩(wěn)性和加工精度等方面對加工站位的設(shè)置問題進行了研究，但沒有研究如何優(yōu)化設(shè)置加工站位的數(shù)量，即如何使得完成全部加工對象加工所需的加工站位數(shù)最少。本文針對飛機裝配領(lǐng)域的工業(yè)機器人加工作業(yè)，研究加工站位優(yōu)化設(shè)置問題，以在確保加工精度的前提下，使得加工完所有加工對象所需總的加工站位數(shù)最少，從而減少機器人的數(shù)量或機器人轉(zhuǎn)換加工站位的次數(shù)，節(jié)約生產(chǎn)成本并提高生產(chǎn)效率。

1 加工站位設(shè)置混合優(yōu)化

1.1 優(yōu)化模型

為了簡化計算，將機器人加工站位所在的連續(xù)位姿空間離散化，得到一組離散的站位 W=。將機器人加工站位優(yōu)化設(shè)置問題轉(zhuǎn)變成從集合W中優(yōu)化選擇加工站位問題(優(yōu)化問題1)：從集合W中選擇一組最少的加工站位用于加工完所有的加工對象，其數(shù)學(xué)模型為

1.2 聚類算法

若機器人在加工站位 w下可以對加工對象 t進行加工且滿足加工精度要求，則稱w為t的可行加工站位，t為w的可加工對象，記為：w→t。用OW和 OT分別表示加工站位的集合和加工對象的集合，定義序偶：O = 〈OW, OT〉，OW≠ φ，OT≠ φ，表示w→t，?w ? OW，?t ? OT。通過加工對象的可加工性分析，可以得到在滿足加工精度要求的條件下每個加工對象的可行加工站位。若某個加工對象沒有可行加工站位，則不考慮該加工對象。將可加工性分析結(jié)果表示為一個序偶集：M = {O1, O2, ·· , Om}，其中OTi= {ti}，ti(i = 1, 2,··, m)為加工對象。定義序偶的聚類運算

若聚類運算的結(jié)果不為φ，則O′仍然是一個有效的序偶。將集合M中的不同元素兩兩之間進行聚類運算得到的結(jié)果(不含φ)組成第1代集合M1。若M中的某個元素與其他所有元素的聚類運算結(jié)果均為φ，則將該元素直接加入M1，且不再參與后續(xù)運算。剔除M1中的冗余元素。對M1做與M同樣的

處理得到第2代集合M2，對M2做與M同樣的處理得到第3代集合M3，……。如此類推，直到某一代集合 Mmax只有一個元素或其中的元素兩兩之間的聚類運算結(jié)果均為φ時為止。將Mmax表示為

其中，Oi′= 〈O′Wi, O'Ti〉，i = 1, …, m′。上述聚類運算過程如圖1所示，其中數(shù)字序號代表加工對象，每一個圓所包圍的黑點構(gòu)成對應(yīng)加工對象的可行加工站位的集合。圖 1(a)表示序偶集 M = {O1, O2, …, O8}，其中OTi= {i}。對集合M進行聚類運算得到的第 1代集合 M1如圖 1(b)所示，對集合M1進行聚類運算得到第二代集合M2，也是最終結(jié)果Mmax，如圖1(c)所示。由圖1(c)可以看出，聚類運算實際上合并了具有相同可行加工站位的加工對象，優(yōu)化問題1等價于從集合Mmax中選擇一組最少的序偶，且每個被選序偶的加工對象集的并集等于全體加工對象的集合T。這樣一來，從每個被選序偶的加工站位集中各自任意選擇一個加工站位組成的一組加工站位，就能完成對全體加工對象的加工，且加工站位數(shù)是最少的。該問題的數(shù)學(xué)模型(優(yōu)化問題2)為

其中，xi(i = 1, 2,··, m')是與序偶Oi′對應(yīng)的二值整型變量，F(xiàn)(wi)是加工對象集。若序偶Oi′被選中，則xi= 1，F(xiàn)(wi) =OT′i；否則xi= 0，F(xiàn)(wi) = φ。

圖1 聚類運算

優(yōu)化問題1,2的數(shù)學(xué)模型是完全一樣的，但是兩個問題需要優(yōu)化選擇的對象和范圍是不一樣的。在優(yōu)化問題 1中，優(yōu)化選擇的對象是加工站位，選擇范圍為加工站位集W，解空間為W的全部基數(shù)小于或等于m in(|W|,|T|)的非空子集，解空間大小為

其中，符號|W|表示集合W的基數(shù)，亦即集合W的元素個數(shù)。在優(yōu)化問題2中，選擇的對象是序偶，選擇范圍為序偶集Mmax，解空間為Mmax的全部基數(shù)小于或等于 m in(|Mmax|,|T|)的非空子集，解空間大小為

根據(jù)聚類運算的過程及圖 1(c)可看出，|Mmax|必然小于或等于|W|，在多數(shù)情況下會遠小于|W|，因此，s2一般遠小于s1。亦即優(yōu)化問題2的選擇范圍相對于優(yōu)化問題 1變小了，所以通過聚類運算可以減小問題的規(guī)模，改善SA的站位優(yōu)化結(jié)果。下面采用多解并行搜索SA求解優(yōu)化問題2。

1.3 改進模擬退火算法優(yōu)化加工站位

為了改善SA的優(yōu)化結(jié)果，本文采取多種策略對簡單SA進行改進。先采用一組解在解空間中并行搜索，并輔以禁忌策略，盡量避免狀態(tài)產(chǎn)生函數(shù)生成與當前解集中的解相同的候選解，加大對解空間的覆蓋面，增大跳出局部極小值的概率。然后依概率進行啟發(fā)式搜索,其是指狀態(tài)產(chǎn)生函數(shù)按照一定的啟發(fā)式規(guī)則由當前解生成一個不次于當前解的候選解。在迭代搜索的初期，采用隨機搜索的概率大于采用啟發(fā)式搜索，以便候選解盡

可能覆蓋全解空間，避免陷入局部極小值；在迭代搜索的后期，采用啟發(fā)式搜索的概率要大于采用隨機搜索，以便使算法盡快收斂，并且不會破壞優(yōu)質(zhì)解的編碼結(jié)構(gòu)，從而更易找到全局最優(yōu)解。在迭代末期采取反復(fù)升溫的策略，當溫度低于設(shè)定閾值時重新升溫以增大采用隨機搜索和接受劣化解的概率，從而有助于跳出局部極小值，找到全局最優(yōu)解。整個SA結(jié)束的準則是重升溫的次數(shù)達到了設(shè)定的最大升溫次數(shù)。多解并行搜索SA的詳細算法流程如下：

多解并行搜索主算法：

步驟1. 算法初始化：

(1) 設(shè)置SA的參數(shù)；

(2) 隨機生成一組初始解；

(3) 歷史最優(yōu)解設(shè)為初始解中的最優(yōu)解。

步驟2. 令升溫次數(shù)i = 0，溫度t等于初始溫度。

步驟3. 降溫循環(huán)：

(1) 計算重新生成候選解的最大許可次數(shù)

其中，μ0是產(chǎn)生候選解的最小次數(shù)，λ是控制產(chǎn)生候選解的最大許可次數(shù)隨溫度t變化速率的參數(shù)，μ0和λ取值均為正整數(shù)，符號?x?表示小于或等于x的最大整數(shù)。

(2) 計算當前解集的平均基數(shù)；

(3) 令解的序號j = 1；

(4) 多解搜索循環(huán)：

①取出當前解集中的第j個解，計算第j個解的基數(shù)；

②令生成候選解的次數(shù)k = 0，采用等溫搜索算法進行等溫搜索循環(huán)；

③令解的序號j = j + 1，若j小于當前解集中解的個數(shù)，則轉(zhuǎn)①；否則轉(zhuǎn)(5)，跳出該循環(huán)；

(5) 若歷史最優(yōu)解不存在于當前解集中，則用歷史最優(yōu)解替換當前解集中的最差解，然后降溫；

(6) 若溫度t小于設(shè)定的閾值，則適當升溫，并令升溫次數(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) 計算采用啟發(fā)式搜索的概率Ph

(3) 隨機生成一個0到1之間的隨機數(shù)r，若Ph＞ r，則由當前解采用啟發(fā)式方法搜索產(chǎn)生候選解；否則采用隨機方式搜索產(chǎn)生候選解；

(4) 判斷候選解是否存在于當前解集中，若存在則轉(zhuǎn)(5)；否則轉(zhuǎn)步驟4，跳出禁忌搜索循環(huán)；

(5) 判斷禁忌搜索次數(shù)p是否小于重新生成候選解的最大許可次數(shù)f(t)，若小于則轉(zhuǎn)(1)；否則轉(zhuǎn)步驟4，跳出禁忌搜索循環(huán)。

步驟4. 計算候選解的基數(shù)。

步驟5. 若候選解的基數(shù)比第j個解的基數(shù)或當前解集的平均基數(shù)小，則用候選解替代第 j個解，轉(zhuǎn)步驟6；否則轉(zhuǎn)步驟7。

步驟6. 若候選解的基數(shù)比歷史最優(yōu)解的基數(shù)小，用候選解替代歷史最優(yōu)解，轉(zhuǎn)步驟9。

步驟7. 計算接受劣化解的概率Pb

其中，ΔC為當前解的基數(shù)與當前解集的平均基數(shù)中的最大值與候選解的基數(shù)的差。

步驟8. 隨機生成一個0到1之間的隨機數(shù)r，若Pb＞ r，則用候選解替代第j個解，轉(zhuǎn)步驟9。

步驟9. 判斷生成候選解的次數(shù)k是否小于設(shè)定值，若小于則轉(zhuǎn)步驟1；否則結(jié)束。

2 實例測試與驗證

以圖 2所示制孔機器人為例說明上述加工站位混合優(yōu)化算法的使用方法。圖中制孔機器人需要鉆制工件上均勻分布的 8個孔位 t1～t8。原始的加工站位優(yōu)化設(shè)置問題是在機器人第七軸(地面導(dǎo)軌)上設(shè)置最少的加工站位，并能加工完所有孔位。為了簡化計算，將機器人的加工站位空間離散成11個均勻分布在第七軸上的站位 w1～w11。孔位 ti可以被站位wi至wi+3下的機器人加工，用序偶集表示為

將加工站位優(yōu)化設(shè)置問題轉(zhuǎn)變成加工站位優(yōu)化選擇問題(優(yōu)化問題1)：從11個站位中選擇最少的一組加工站位用于加工8個孔位，解空間大小為

序偶集M通過聚類方法最終得到的序偶集為：

將加工站位優(yōu)化選擇問題進一步轉(zhuǎn)化為序偶的優(yōu)化選擇問題(優(yōu)化問題2)：從集合Mmax的5個序偶中選擇最少的一組序偶，并且每個被選序偶的加工對象集的并集等于全部 8個孔位的集合，解空間大小為

圖2 加工對象聚類

可見，通過聚類運算大幅減小了解空間，有效地縮減了加工站位優(yōu)化問題的規(guī)模，有利于SA找到全局最優(yōu)解并加快收斂速度。然后采用多解并行搜索SA求解優(yōu)化問題2，得出加工完8個孔位所需的最少加工站位為w4和w8。

為了驗證上述優(yōu)化算法的有效性，用一組模擬加工數(shù)據(jù)對算法進行了測試。模擬加工數(shù)據(jù)有108個加工對象，機器人加工站位分布空間離散化得到3 066個加工站位，為每個加工對象分配了數(shù)量不等的加工站位。經(jīng)過聚類運算得到了包含245個元素的序偶集。然后用 4種算法優(yōu)化選擇加工站位，分別是簡單 SA、聚類運算結(jié)合簡單 SA、改進 SA、以及聚類運算結(jié)合改進 SA。每種算法獨立測試60次，測試結(jié)果如表1所示。對比算法1和2，通過加入聚類算法能夠顯著改善優(yōu)化結(jié)果并加快SA的收斂速度。對比算法1和3，改進SA能夠更有效地改善優(yōu)化結(jié)果并加快算法收斂速度。對比算法3和4，聚類算法能在改進SA的基礎(chǔ)上進一步改善優(yōu)化結(jié)果，但對于算法收斂性沒有進一步改善。從模擬加工數(shù)據(jù)的測試結(jié)果可知，本文提出的聚類結(jié)合改進SA相對于簡單SA無論在尋優(yōu)結(jié)果還是收斂速度方面都有顯著的優(yōu)勢。

表1 模擬加工數(shù)據(jù)測試結(jié)果

為了進一步驗證加工站位設(shè)置混合優(yōu)化算法的有效性，用圖3所示的工件對算法進行了測試。圖中為小型飛機的機身模擬件，機身內(nèi)部是由框、梁連接而成的骨架，機身外表面用蒙皮覆蓋，蒙皮與骨架用鉚釘連接。待鉆的鉚釘孔數(shù)量約為3 000個，測試用的鉆孔機器人為KUKA KR200-1。經(jīng)過多次測試，采用KUKA KR200-1型機器人加工完所有鉚釘孔需要3個加工站位，其分布如圖3所示。

圖3 模擬件測試

3 結(jié) 論

本文提出了基于聚類算法和改進 SA的機器人加工站位設(shè)置混合優(yōu)化算法。首先將加工站位分布的連續(xù)位姿空間離散化，得到一組均勻分布的離散化加工站位。通過分析加工對象的可加工性，得到每個加工對象能夠被哪些站位下的機器人加工。然后用聚類算法將相同加工站位下可加工對象合并，以此縮減問題的規(guī)模，提高SA找到全局最優(yōu)解的概率和收斂速度。最后采用多解并行搜索 SA優(yōu)化選擇加工站位。通過實際測試表明，該算法能夠在顯著改善加工站位優(yōu)化結(jié)果的同時大幅提高算法的收斂速度。但是該算法需要對機器人加工站位所在的連續(xù)空間進行離散化處理，離散的步長越長，可選的加工站位越少，加工站位優(yōu)化選擇的結(jié)果也會越差；另一方面，離散的網(wǎng)格步長越短，可選的加工站位越多，SA找到全局最優(yōu)解的概率也越小，同時優(yōu)化的時間也越長。因此對加工站位分布空間進行離散化的最佳步長仍需要進一步研究。

[1] 黃 進, 胡 英, 馬 孜, 等. 基于粒子群優(yōu)化算法的工業(yè)機器人與外部軸標定[J]. 機械工程學(xué)報, 2009, 45(7): 63-67.

[2] 邵秋萍, 劉極峰, 王孜凌. 基于外部軸控制的塞拉門機器人弧焊工作站[J]. 機械設(shè)計與制造, 2006, (9): 117-119.

[3] 田 威, 戴家隆, 周衛(wèi)雪, 等. 附加外部軸的工業(yè)機器人自動鉆鉚系統(tǒng)分站式任務(wù)規(guī)劃與控制技術(shù)[J]. 中國機械工程, 2014, 25(1): 23-27.

[4] 何廣忠, 高洪明, 吳 林. 機器人弧焊離線編程與仿真系統(tǒng)的設(shè)計[J]. 焊接, 2006, (2): 24-28.

[5] 林巨廣, 湯東華. DELM IA在機器人白車身點焊工作站規(guī)劃設(shè)計中的應(yīng)用[J]. 機械設(shè)計與制造, 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] 李金林, 譚建榮. 改進模擬退火算法在配氣凸輪機構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J]. 工程圖學(xué)學(xué)報, 2006, 27(1): 19-23.

[8] 董德威, 顏云輝. 缺陷板材非規(guī)則件優(yōu)化排樣[J]. 圖學(xué)學(xué)報, 2013, 34(2): 31-37.

[9] 許良鳳, 林 輝, 胡 敏, 等. 基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割[J]. 工程圖學(xué)學(xué)報, 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

曾德標(1985–)，男，四川達州人，博士。主要研究方向為計算機輔助工藝規(guī)劃、飛機數(shù)字化裝配。E-mail：debiaozeng@126.com