張　鐵　蘇杰汶

華南理工大學(xué)，廣州，510641

?

基于改進蟻群算法的機器人末端路徑排序優(yōu)化

張鐵蘇杰汶

華南理工大學(xué)，廣州，510641

建立了針對機器人加工時的末端運動路徑排序優(yōu)化問題的數(shù)學(xué)模型，將該模型轉(zhuǎn)化為廣義旅行商問題并用蟻群算法求解。同時對經(jīng)典的蟻群算法進行了改進，即采用多階段搜索策略、鄰域搜索策略及多蟻種搜索策略，使改進后的蟻群算法能為機器人求取一條更優(yōu)的末端運動路徑。計算機仿真與機器人加工實驗結(jié)果表明，改進蟻群算法所得的末端運動路徑比基本蟻群算法所得結(jié)果縮短了3%以上。

機器人；路徑排序優(yōu)化；旅行商問題；改進蟻群算法優(yōu)化

0　引言

在機器人打磨與雕刻中，為了提高加工效率，需要對機器人末端的運動路徑進行優(yōu)化。路徑優(yōu)化分兩種：一是對路徑質(zhì)量的優(yōu)化，即通過動力學(xué)理論與工藝要求來生成質(zhì)量更優(yōu)的運動路徑，令機器人運動平穩(wěn)，運動過程中無干涉、無碰撞且令機器人加工的質(zhì)量更優(yōu)[1-2]；二是路徑排序優(yōu)化，即采用最優(yōu)化理論對給定的加工路徑進行排序優(yōu)化，得到最優(yōu)的加工路徑執(zhí)行順序，令機器人運動達到時間上的最優(yōu)[3]。本文研究的路徑優(yōu)化問題屬于后者，即：對于工件現(xiàn)有的加工路徑，合理地安排它們的執(zhí)行順序，令機器人末端在執(zhí)行加工路徑時產(chǎn)生的空行程最短以提高生產(chǎn)效率。空行程是指由于加工路徑轉(zhuǎn)換時機器人末端存在抬升、平移、下移等沒有產(chǎn)生加工效果的動作。

針對路徑的排序優(yōu)化問題，國內(nèi)外學(xué)者提出了不少方法，大部分都是將此問題轉(zhuǎn)化為旅行商問題(TSP)或廣義旅行商問題(GTSP)，然后采用智能算法來求解，如蟻群算法[4-5]、遺傳算法[6]等。其中遺傳算法魯棒性強，但其局部搜索能力強而全局搜索能力較弱，易于早熟從而陷于局部最優(yōu)，而蟻群算法是一種并行進化算法，它模擬蟻群的覓食機制而設(shè)計，具有很強的局部收斂能力，但全局收斂性能較差，易于陷入局部最優(yōu)且收斂的速度較慢[7]，故在使用蟻群算法時須對算法進行改進以獲得較好的結(jié)果，如最大最小螞蟻系統(tǒng)算法[8]等。

本文針對機器人末端運動路徑優(yōu)化的問題，建立了一個最優(yōu)化模型，得出了最優(yōu)化的目標(biāo)函數(shù)，將這個模型轉(zhuǎn)化為GTSP問題，再用改進的蟻群算法進行了求解。采用鄰域搜索策略、多蟻種搜索策略與分階段搜索策略對蟻群算法進行改進。最后編寫程序?qū)崿F(xiàn)改進的蟻群算法，求解機器人末端運動路徑的排序優(yōu)化問題，并進行實驗驗證。

1　機器人末端運動路徑優(yōu)化模型

1.1優(yōu)化模型的建立

如圖1a所示，設(shè)工件有n條加工路徑，加工路徑的類型只有直線與多邊形兩種，當(dāng)加工路徑i為直線時，直線的任一端點均可作該路徑的起點si，而另一端點為該路徑的終點ei，當(dāng)加工路徑i為多邊形時，可以任意選擇多邊形中的任一頂點作為該路徑的起點si，由于多邊形為封閉圖形，故si、ei為同一點。

圖1b中粗實線是工件的加工路徑，細實線與虛線為機器人末端的運動路徑，“起點”位于s1的正上方。機器人末端在加工時所走的路徑如圖1a所示。由此可得，在加工工件時，機器人末端的運動路徑總長LT為

(1)

而末端運動路徑中空行程的長度Linv為

(2)

式中，di為機器人末端下移的高度；ri為機器人末端抬升的高度；ci為機器人末端執(zhí)行加工路徑的長度；mi為末端在空中移動的路徑長度。

(a)工件加工路徑　(b)機器人末端運動路徑圖1　加工路徑與機器人末端運動路徑

為了簡化問題，設(shè)di=ri=H(i=1,2,…,n)，其中H為常數(shù)，此時有

(3)

式中，D(x,y)為x、y兩點的距離。

由此可建立機器人末端運動路徑的優(yōu)化模型。設(shè)工件有n條加工路徑p1,p2,…,pn，合理確定各路徑的起點si與ei(i=1,2,…,n)與各加工路徑的執(zhí)行順序，從而可求

(4)

其中，d(ei,si+1)為點ei與點si+1的歐氏距離，式(4)即為機器人末端運動路徑排序優(yōu)化的目標(biāo)函數(shù)。

1.2將優(yōu)化模型轉(zhuǎn)化成GTSP問題

上述的路徑排序優(yōu)化模型可以轉(zhuǎn)化為一種特殊的GTSP問題。GTSP可以表述為：有m個城市被分為n個城市群(每個城市群中至少有一個城市，且城市群之間無相同的城市)，求一條最短的回路，即令旅行商從一個城市群中的一個城市出發(fā)，遍歷每個城市群，且經(jīng)過每個城市群時至少經(jīng)過其中的一個城市，最后回到出發(fā)點，如圖2所示。

圖2　廣義旅行商問題

在機器人末端運動路徑排序優(yōu)化問題中，每條加工路徑就相當(dāng)于一個城市群，加工路徑中的插補點相當(dāng)于城市群中的一個城市。對于直線類型的加工路徑，即相當(dāng)于只有兩個城市的城市群，因為直線類型的加工路徑的起點si與終點ei不是同一點，所以旅行商必須經(jīng)過城市群中的兩個城市；對于多邊形類型的加工路徑，因為其起點si與終點ei均為同一點，所以旅行商只需要經(jīng)過該城市群中的任意一個城市即可。

由此可將機器人末端運動路徑優(yōu)化問題轉(zhuǎn)化成一個特殊的GTSP問題：設(shè)有n個城市群(n為工件加工路徑的數(shù)目)，每個城市群中至少有兩個城市且城市群之間沒有相同的城市，求一條最短回路使旅行商從一個城市群中的一個城市出發(fā)，有且只有經(jīng)過每個城市群一次，最后回到起點，當(dāng)城市群中只有兩個城市時，則必須經(jīng)過該城市群中的這兩個城市，否則旅行商只能經(jīng)過該城市群中的任意一個城市，如圖2所示。

設(shè)回路的城市依次為：c1,c2,…,ci,…，cl。則回路的長度L定義為

(5)

(6)

L相當(dāng)于機器人末端運動路徑中的總空行程，求式(5)最小值的問題即是求機器人末端運動路徑排序優(yōu)化問題中的最短空行程問題，其與式(4)是等價的。對于式(6)可以解釋為：如果ci、ci+1同屬一城市群Gj，即相當(dāng)于兩個插補點同屬于一加工路徑，兩點之間的路徑并不是空行程，所以它們之間的距離取值為0。

2　蟻群算法及其改進

2.1基本蟻群算法

針對GTSP問題，蟻群算法(ACA)描述為：每只螞蟻代表一條完整的回路，而評價每只螞蟻的優(yōu)劣則根據(jù)式(5)、式(6)，L值越小則螞蟻越優(yōu)。

(7)

設(shè)所有城市的集合為S，其中allowedk={S-tabuk}，表示下一步中允許螞蟻轉(zhuǎn)移到的城市的集合；α為信息啟發(fā)因子，表示每條路徑上殘留信息素的重要程度；β為期望啟發(fā)因子，表示路徑自身啟發(fā)信息對螞蟻行進運動的影響力。

當(dāng)所有螞蟻對所有城市群進行了一次遍歷(即一次循環(huán))之后，需更新所有路徑上的信息素，為凸顯較優(yōu)路徑的優(yōu)勢，所以采用全局更新規(guī)則，即在所有螞蟻中選出一只路徑總長最短的螞蟻，該螞蟻對應(yīng)的路徑為當(dāng)前最優(yōu)路徑，然后僅更新該路徑的信息素。τij(t+n)表示t+n時刻路徑(i,j)上信息素的量，其更新規(guī)則如下[10]：

τij(t+n)=

(8)

(9)

2.2對蟻群算法的改進

基本的蟻群算法擁有很強的全局尋優(yōu)能力，但它有如下缺陷：①其求解速度較慢，這是由于搜索初期信息素差異不明顯，算法的收斂速度較慢，算法的初期浪費了大量的時間所致；②基本蟻群算法中的蟻種單一，所有螞蟻都是完成同一種任務(wù)而無明確的分工，從而導(dǎo)致了算法的求解速度不高，求解能力不強[11]。針對基本蟻群算法的缺點,采用多階段搜索策略、鄰域搜索策略與多蟻種搜索策略對其進行改進。

2.2.1多階段搜索策略

(10)

(11)

圖3　轉(zhuǎn)移概率(t)的放大

2.2.2鄰域搜索策略

表1　Nc與Nn之間的關(guān)系

在得到中心城市i的鄰域U(i)后，還要用信息素來標(biāo)記城市i到其鄰域的路徑，其標(biāo)記規(guī)則如下[11]：

(12)

然后將標(biāo)記的信息素加到各路徑中去，從而得到初始時刻各路徑的信息素為[11]

(13)

2.2.3多蟻種搜索策略

(14)

(15)

傳統(tǒng)蟻有很強的局部搜索能力，而叛逆蟻與反叛蟻則是真正意義上的全局搜索，可以提高算法所得解的全局最優(yōu)性。

改進的蟻群算法步驟如下：

(1) 初始化參數(shù)，包括螞蟻數(shù)目m、傳統(tǒng)蟻的比例p、城市群數(shù)Ng、循環(huán)總次數(shù)為N、前期階段循環(huán)次數(shù)為N′、初始時刻各路徑信息素含量τo、信息啟發(fā)因子α、期望啟發(fā)因子β、信息素強度Q、揮發(fā)系數(shù)ρ。

(2) 計算各城市的鄰域，并按式(12)、式(13)初始化各路徑上的信息素。

(3) 初始化蟻群，每只螞蟻k隨機選擇一個城市群，然后在該城市群中隨機選擇一個城市作為出發(fā)點，將該城市加入到螞蟻路徑pathk中，而將螞蟻所在城市群中的所有城市加入到禁忌表tabuk中。

(4) 循環(huán)次數(shù)n←0。

(5) 設(shè)時刻t←0，則

Fort=0,1,2,…,Ng-2Then

Fork=1,2,…,mThen

k←k+1

End

t←t+1

End

(6) 根據(jù)式(5)、式(6)計算所有螞蟻的路徑中空行程的總長度，選出L值最小的螞蟻，并根據(jù)式(2)、 式(3)更新各路徑上的信息素。

(7) n←n+1。

(8) 如果n=N則終止算法，輸出最優(yōu)結(jié)果，否則返回步驟(5)。

3　仿真與實驗結(jié)果

為了驗證改進蟻群算法的有效性，分別采用基本蟻群算法與改進蟻群算法對三個不同工件的加工路徑進行優(yōu)化，比較優(yōu)化的機器人末端運動路徑中的空行程長度。由于本文研究的是運動路徑排序優(yōu)化問題，工件的加工路徑是給定的，優(yōu)化的是加工路徑的執(zhí)行順序，為了簡化問題，故實驗中工件的所有路徑都位于同一平面上。三個工件的加工路徑數(shù)目分別為47、104與192,如圖4所示。

(a)工件一(47條軌跡)

(b)工件二(104條軌跡)

(c)工件三(192條軌跡)圖4　實驗的工件軌跡

改進蟻群算法與基本蟻群算法的參數(shù)設(shè)置為：螞蟻數(shù)目m與加工路徑的數(shù)目相同，城市群數(shù)Ng與加工路徑數(shù)目相同，循環(huán)總次數(shù)為N=100，初始時刻各路徑信息素含量τo=1，信息啟發(fā)因子α=1.0，期望啟發(fā)因子β=10.0，信息素強度Q=100，揮發(fā)系數(shù)ρ=0.1；而對于改進蟻群算法而言，前期階段循環(huán)次數(shù)為N′=35，傳統(tǒng)蟻比例為0.77。在計算機上進行仿真計算，所得結(jié)果如表2所示。

表2　工件的刀具路徑優(yōu)化的仿真結(jié)果比較

從表2、表3的數(shù)據(jù)可得：①對機器人末端運動路徑進行優(yōu)化后，其中的空行程長度會減少62.8%～86.4%；②改進蟻群算法的優(yōu)化結(jié)果與基本蟻群算法優(yōu)化結(jié)果相比，空行程減少1.13%～3.86%，而且隨著問題規(guī)模的增大，其優(yōu)勢會更加明顯；③改進蟻群算法與基本蟻群算法相比，改進蟻群算法的全局搜索能力更佳，更快地跳出局部最優(yōu)，從而避免浪費大量的循環(huán)迭代時間。

表3　改進蟻群算法與基本蟻群算法改進效果比較

在實驗平臺上進行平面雕刻實驗，對表2中的三種工件進行加工，分別采用未優(yōu)化前、基本蟻群算法優(yōu)化后、改進蟻群算法優(yōu)化后的機器人末端運動路徑進行加工，同時測量整個加工的時長，由時長來驗證優(yōu)化后空行程是否真的減少。改進蟻群算法與基本蟻群算法的改進效果比較如表3所示。

實驗條件： 采用直角坐標(biāo)機器人平臺，如圖5a所示，運動方式采用OXYZ三坐標(biāo)直線插補，合成插補速度為4 mm/s，合成加速度為50 mm/s2，插補段終點速度為0，在一個平面上進行雕刻加工，雕刻的深度為0.5 mm，機器人末端的抬升高度r與下降高度d均為3 mm，所用刀具為φ3的端面銑刀。加工過程如圖5b所示。

(a)直角坐標(biāo)機器人平臺　　　(b)加工過程圖5　實驗過程

由表4可知，對于同一工件，對機器人末端運動路徑進行蟻群算法優(yōu)化后，其加工時長大幅縮短，而進行了改進蟻群算法優(yōu)化后，其加工時長最短。由表5可知，隨著加工路徑數(shù)目的增大，改進蟻群算法的優(yōu)化效果相對于基本蟻群算法的優(yōu)化效果而言，會節(jié)省更多的時間。結(jié)果與仿真結(jié)果一致。雕刻的工件如圖6所示。

表4　優(yōu)化前后末端運動路徑的加工時長比較

表5　改進蟻群算法與基本蟻群算法優(yōu)化的實驗效果對比

(a)工件加工路徑　　　　(b)加工工件效果圖6　工件加工效果

4　結(jié)論

本文采用蟻群算法對機器人加工時的末端運動路徑進行了排序優(yōu)化，并對傳統(tǒng)的蟻群算法提出了改進措施，即采用了多蟻種、多階段搜索、鄰域搜索三種策略，使改進后的蟻群算法的優(yōu)化結(jié)果更優(yōu)。仿真實驗結(jié)果表明，采用改進蟻群算法優(yōu)化后的機器人末端運動路徑中的空行程比基本蟻群算法的優(yōu)化結(jié)果短3%；而在實際的機器人雕刻實驗中，采用改進蟻群算法優(yōu)化后，對同工件的加工時間最短，在實驗中最大節(jié)省時間為6.94 s，從而證明了改進蟻群算法的有效性。

本文主要研究減少雕刻加工中不同區(qū)域空行程問題，因此實驗僅僅進行了平面的雕刻實驗，本文的成果可以推廣到機器人曲面雕刻與打磨加工。

[1]王偉,贠超,張令. 機器人砂帶磨削的曲面路徑優(yōu)化算法[J]. 機械工程學(xué)報,2011,47(7):8-15.

Wang Wei, Yun Chao, Zhang Ling. Optimization Algorithm for Robotic Belt Surface Grinding Process[J]. Journal of Mechanical Engineering, 2011,47(7):8-15.

[2]晁永生,劉海江. 白車身焊接機器人加工路徑優(yōu)化和仿真[J]. 中國機械工程,2010,21(4):442-445.Chao Yongsheng, Liu Haijiang. Welding Robot Path Optimization and Simulation for Body in White[J]. China Mechanical Engineering， 2010,21(4):442-445.

[3]Alatartsev S, Stellmacher S, Ortmeier F. Robotic Task Sequencing Problem: a Survey[J]. Intell. Robot Syst., 2015, 80:279-298

[4]Li Cuiming, Gong Jun, Niu Wancai ，et al. Combinatorial Optimization of Spray Painting Robot Tool Trajectory Based on Improved Membership Cloud Models Ant Colony Algorithm[J]. Journal of Shanghai Jiaotong University, 2015，49(3)：387-391.

[5]Wang Mei, Meng Shengda. Path Planning Method of Water-jet Cutting Robot[J]. Journal of Southeast University (Natural Science Edition),2012，42(S):212-216.

[6]Baizid K, Chellali R, Yousnadj A, et al. Genetic Algorithms Based Method for Time Optimization in Robotized Site[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Taipei, 2010:1359-1364.

[7]Saenphon T, Phimoltares S, Lursinsap C. Combi-ning New Fast Opposite Gradient Search with Ant Colony Optimization for Solving Travelling Salesman Problem [J]. Engineering Applications of Artificial Intelligence，2014，35：324-334.

[8]李士勇, 陳永強, 李研. 蟻群算法及其應(yīng)用[M]. 哈爾濱: 哈爾濱工業(yè)大學(xué)出版社，2004.

[9]Yang Jinhui, Shi Xiaohu. An Ant Colony Optimization Method for Generalized TSP Problem [J]. Progress in Natural Science,2008,18:1417-1422.

[10]Liu Dan, Zheng Lijuan, Wang Jianmin. Applica-tion of Improved Ant Colony Algorithm in Solving TSP[J]. International Journal of Multimedia and Ubiquitous Engineering,2014,9(7):395-402.

[11]王霜. 大型TSP問題的蟻群優(yōu)化規(guī)則研究[D].長春：吉林大學(xué),2012.

[12]Kan Junman, Zhang Yi. Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem[J]. Energy Procedia,2012,17:319-325.

[13]全惠云，文高進. 求解 TSP 的子空間遺傳算法[J]. 數(shù)學(xué)的理論與應(yīng)用，2002，22(1):36-39.

Quan Huiyun, Wen Gaojin. Subspace Genetci Algorithm for TSP[J]. Mathematical Theory and Applications，2002, 22(1):36-39.

(編輯袁興玲)

Path Sorting Optimization of Robotic End-effector by Improved ACA

Zhang Tie Su Jiewen

South China University of Technology，Guangzhou，510641

For the path sorting optimization of robotic end-effector in robotic machining , a solution was presented, that established mathematical model for this problem and converted it to generalized traveling salesman problem (GTSP) and solved this problem by ACA. Meanwhile, the classical ACA was improved with multi stage search strategy, neighborhood search strategy and multi ant type strategy, so that the improved ACA was able to calculate a more optimized end-effector path for robotic machining. The results of simulation and robotic machining prove that the end-effector path obtained by improved ACA is shorter than 3% above the basic ACA’s.

robot; path sorting optimization; traveling salesman problem (TSP); improved ant colony algorithm (ACA) optimization.

2015-12-07

國家科技重大專項(20152X04005006);廣東省科技計劃重大專項(2014B090921004，2014B090920001)

TP242.2

10.3969/j.issn.1004-132X.2016.19.011

張鐵，男，1968年生。華南理工大學(xué)機械與汽車工程學(xué)院教授、博士研究生導(dǎo)師。主要研究方向為工業(yè)機器人、服務(wù)機器人及自動化設(shè)備等。 發(fā)表論文100余篇。蘇杰汶，男，1991年生。華南理工大學(xué)機械與汽車工程學(xué)院碩士研究生。