基于視覺抓取的并聯桁架機器人最優路徑控制

楊繼東 孫兆琦 王飛龍

摘 要：針對元件的抓取路徑規劃問題，提出一種以最小化時間為目的，結合蟻群算法和禁忌搜索算法的混合優化算法。首先，將基于機器視覺抓取元件的問題確定為有約束的旅行商問題（TSP）;然后，分析了元件大小和抓取放置過程對于路徑規劃的綜合影響，對路徑選擇概率和禁忌域進行了適應性改進;其次，一方面引入了2-opt局部優化以及信息素懲罰、獎勵機制以改善螞蟻的搜索能力，另一方面對信息揮發因子作適應性改進以提高螞蟻的自適應能力;

最后，針對基本算法和改進的混合優化算法，仿真實驗和平臺實驗分別進行了性能指標和抓取時間的對比分析。

實驗結果表明，仿真環境下，與蟻群優化（ACO）算法和禁忌搜索（TS）算法相比，混合優化算法的平均迭代次數降低了約50%，且其他性能較為優越，平臺測試的抓取用時測試結果也說明了混合優化算法較隨機結果和基本算法的優越性，可以快速完成元件抓取任務。

關鍵詞：機器視覺;有約束的TSP;最優路徑;蟻群算法;混合優化算法

中圖分類號： TP273;TP18

文獻標志碼：A

文章編號：1001-9081（2019）03-0913-05

Abstract： To solve the problem of component grasping path planning， a hybrid optimization algorithm based on ant colony algorithm and tabu search algorithm was proposed to minimize the time. Firstly， the problem of grasping components based on machine vision was defined as Traveling Salesman Problem （TSP） with precedence constraint. Secondly， comprehensive effects of the sizes of components and the grasping and placement process on path planning were analyzed， and the path selection probability and tabu region were improved adaptively. Thirdly， on the one hand， 2-opt local optimization， pheromone punishment and reward mechanism were introduced to improve the search ability of ants; on the other hand， pheromone evaporation factor was improved adaptively to increase the adaptability of ants.

Finally， for the basic algorithm and the improved hybrid optimization algorithm， the performance index and grasping time were compared and analyzed by simulation experiment and platform experiment.

The experimental results show that， compared with Ant Colony Optimization （ACO） algorithm and Tabu Search （TS） algorithm， the average iteration times of the proposed hybrid optimization algorithm is reduced by about 50%， and other performances are superior to the other algorithms. The results of platform test also show that the hybrid optimization algorithm is superior to random results and basic algorithm， and it can realize component grasping task quickly.

Key words： machine vision; Traveling Salesman Problem （TSP） with precedence constraint; optimal path; ant colony algorithm; hybrid optimization algorithm

0 引言

工業攝像機作為工業機器人的視覺傳感器，是工業生產需要的柔性制造系統（Flexible Manufacture System， FMS）、自動化工廠（Factory Automation， FA）的重要環節，是實現“中國制造2025”的自動化工具。

目前，機器視覺在工業生產過程中的檢測、識別已有較為廣泛的應用，同時在定位抓取過程中的研究也有一定的應用，但是對物體抓取路徑的控制規劃研究較少，優化抓取路徑可以有效地提高重復抓取過程中效率，是視覺系統抓取過程中的重要一環。從理論分析來講，抓取路徑可以劃歸為旅行商問題（Travelling Salesman Problem， TSP），同時該過程為取放過程，因此其屬于有約束的旅行商問題（Traveling Salesman Problem with Precedence Constraint， TSPPC）。李堯等[1]提出基于圖像識別和遺傳算法的最優軌跡控制，但是其抓取模型的約束較多，不具有通用性，且算法未進行優化分析。解決TSP的方法較多，其中：枚舉法算法較為簡單，但算法效率較低;模擬退火算法、遺傳算法、蟻群算法的質量較高，但是優化時間較長，易于陷入局部解;禁忌搜索算法（Tabu Search， TS）局部搜索能力較強，但是依賴初始解。蟻群算法應用于TSP最早是由意大利學者Dorigo等 [2]提出，基本思想是依據螞蟻尋找食物過程中釋放信息素，來引導其他螞蟻的爬行路徑實現正反饋，具有較好的魯棒性和協作性。葉小勇等[3]引入隨機搜索蟻同時增加信息素的獎勵懲罰機制，有效地提高全局最優解的搜索能力，但是搜索用時較長，實時性較差。張慕雪等[4]通過該禁忌搜索來加強蟻群算法的全局搜索能力，但是由于是基于蟻群算法的優化算法，搜索用時較長，實時性差，不適用于工業抓取過程。

針對蟻群算法和禁忌搜索算法各自的優缺點，本文提出了一種混合優化算法（Ant Colony Optimization-Tabu Search， ACO-TS），用來取長補短，優化視覺處理后的元件的抓取路徑，同時提高算法的收斂速度和算法處理速度。對蟻群算法中的選取概率和禁忌搜索算法的禁忌域作出了適應性修正，同時優化蟻群算法的信息素揮發因子，引入局部2-opt進行優化和信息素獎勵懲罰機制，在有效的迭代次數里提高收斂速度，為禁忌搜索算法提供優良的初始解，利用禁忌搜索算法的記憶能力和藐視原則得到路徑最優解。

1 相關工作

1.1 實驗平臺簡介

本文中搭建的視覺系統實驗平臺是基于并聯桁架機器人，攝像機采用大恒的MER-125-30GM-PS數字面陣相機，鏡頭采用Computar的H2Z0414C-MP變焦鏡頭，采用打背光的打光方式，工控機采用研華IPC-610L，運動控制卡采用雷賽DMC5480板卡。相機的固定方式采用眼在手上（Eyes In Hand）。搭建出的樣本的實驗平臺如圖1所示。

為了有效得到實驗測試結果，將測試的抓取元件和碼盤作了如下簡化：

1）抓取元件個數和放置位置個數均為9，抓取的圓形玻璃元件有大中小三種尺寸類型，每種尺寸類型元件各有三個，放置位置個數與之對應。

2）抓取元件在打光區域任意擺放，碼盤擺放位置、方向固定，且選取如圖碼盤的右上角3×3大小的碼盤作為放置元件位置。

首先采用Halcon和Visual Studio 2013聯合編程的方式對本組進行數字圖像處理如圖2所示，后通過攝像機傳統標定的方法獲取攝像機的內參數，借鑒文獻[5]的手眼標定方法來確定攝像機坐標到吸盤末端坐標的轉化。

經過Halcon對圓形玻璃元件視覺處理后得到不同元件的大小信息和元件的抓取中心特征點的坐標信息，經過標定將結果轉為世界坐標信息。根據圓形玻璃元件的大小將其依次進行2～10編號，對于已知坐標的碼盤放置元件位置，同樣對碼盤放置元件位置根據孔洞大小依次進行11～19進行編號，起始點位置確定為1。然后通過與Visual Studio 2013聯合編程，便于控制運動控制卡來進行抓取運動的實現。

1.2 問題分析

本文重點研究的內容是并聯桁架機器人抓取排放9個圓形玻璃元件的先后順序問題，以最優的路徑實現圓形元件擺放到直徑一致的碼盤位置。問題描述如下：機械手末端從起始點出發，無重復地到達抓取、放置的每一個點，最終返回原點。與TSP作對比，發現二者有很多相似之處。本文元件抓取和放置位置相當于TSP里的城市，無重復經過每一個點，達到最優路徑。但是，本文的最優路徑相對于TSP有所約束，

體現如下：

1）末端機械手到達抓取點，完成抓取動作之后，下一步必須到達放置點。

2）抓取和放置過程中，元件的直徑和放置位置直徑要對應，不能出現直徑較小的元件放置在直徑較大的碼盤位置的情況。

根據問題描述，可以確定該問題為NP問題[6-7]，傳統概率算法、并行算法非常復雜，要尋求一個最優的解需要很長的時間，因此本文針對視覺抓取過程提出基于蟻群算法和禁忌搜索算法的混合優化算法。

2 算法介紹

2.1 蟻群優化算法

蟻群優化（Ant Colony Optimization， ACO）算法是一種較為新的模擬進化算法，是從整個蟻群可以找到一條從巢穴到食物源之間的最優路線而啟發得到的[8-9]。原因在于螞蟻在爬行過程中會在路徑上釋放信息素的物質，隨著時間的推移，該物質會揮發，路徑上的信息素越濃，螞蟻選擇該路徑的機會就越大[10-11]。

其中基本的3個公式如下：

2.2 禁忌搜索算法

禁忌搜索算法是利用禁忌表來記錄當前搜索過程中的局部最優點，在下一次的搜索中，對于禁忌表中的信息不再或有選擇地搜索，以此來跳出局部最優點。但禁忌搜索算法對初始解的依賴性較強[12-13]，好的初始解有助于搜索很快達到最優解。所以，對禁忌搜索算法的改進一直是人們研究的重點[14]。

3 混合優化算法

3.1 適應性算子的改進

3.1.1 路徑選擇概率適應性的改進

針對機器人路徑上有抓取和放置過程且直徑大小對應，本文對路徑選擇概率作出了如下的適應性改進，螞蟻由節點i訪問節點j的概率為：

其中：概率選取的過程是從抓取位置i到放置位置（用i′表示），然后再從放置位置j再到下一個抓取位置j′這樣的抓取、放置、抓取過程為單次循環過程來進行概率選取。根據抓取元件直徑大小來選擇放置位置（allowsize表示），然后返回下一個抓取位置（allow表示），如此改進可以有效避免單次選取帶來的陷入局部最優解。

3.1.2 禁忌域適應性的改進

由于研究問題是有約束的TSP，在禁忌域建立過程中，本文建立交換允許表，在進行禁忌交換時加以利用。交換允許表可以用allowsize表示如表1所示，它是一個二維表，第1行、第1列表示2個元件交換前的序號。

行列節點交叉處的值表示禁忌交換時是否被允許。值為“1”表示允許交換，值為“0”表示不允許交換。產生兩個隨機交換位置，根據位置對應的初始解的數值在交換允許表中對應的“0”“1”確定該組交換是否可以被接受，且當交換對應的初始解數值在區間[2-10]時，各交換位置的后一位同時進行交換。如初始解為（1-7-16-9-17-2-12-4-13-8-19-10-18-6-14-5-15-3-11-1），如隨機產生的交換位置為（2，10），對應的初始解的數值為7，10，在交換允許表的對應數值為“1”，允許交換，且對應的初始解的數值在區間[2，10]，因此初始解數值16，18對應位置同時進行交換。

3.2 蟻群算法優化

3.2.1 2-opt局部優化

將2-opt引入蟻群算法，對于螞蟻所構建出的路徑較短的路徑執行2-opt算法來進行當前解的局部優化[15]，這樣既可以避免算法陷入局部最優解，又能加快收斂，同時針對路徑較優的前n/2個解路徑進行2-opt局部優化，減少引入2-opt算法來引起的計算時間過長的現象。過程大致如下：對于節選路徑i、i′、i+1、i′+1、…、 j、 j′、 j+1、 j′+1，假設選定i′+1、 j為交換位置、區間內的路徑進行抓取位置反向處理，放置位置跟隨處理，如下i、i′、 j、 j′、…、i+1、i′+1、 j+1、 j′+1，如圖3所示。

3.2.2 引入信息素懲罰、獎勵機制

prize為獎勵系數，punish為懲罰系數，為設定的固定參數，prize大小影響收斂速度，punish大小影響全局最優解的尋求能力。為了在有限的迭代次數里，為禁忌搜索提供較好的初始解，可以適當地增大punish，減小punish，提高收斂速度，全局最優解搜索能力依靠禁忌搜索來改善。

3.2.3 信息揮發因子適應性優化

蟻群算法的信息素發揮因子ρ設定為固定值，如式（2）所示， ρ設定較小時會造成快速陷入局部最優解，失去全局搜索能力; ρ設定較大時會造成收斂速度過慢，降低工作效率。因此，將ρ設定為與蟻群算法迭代次數相適應的函數，如式（9）所示：

其中：λ為設定參數，NC為蟻群算法搜索的迭代次數，NCmax為最大迭代次數，同時設定上下限為（0.7，0.1），使其值保持在一定的范圍。起始時，選擇較大的信息素揮發因子，提高蟻群算法搜索全局最優解的能力，動態改變ρ，使其隨著迭代次數的增加不斷減小，提高其收斂速度，同時算子過程中引入NCmax，提高算子自適應能力。

至此，對機器視覺抓取過程最優路徑的規劃所需要的實驗平臺，利用蟻群算法提高收斂速度同時為禁忌搜索提供較優的初始解，通過禁忌搜索求解全局最優解，形成混合優化算法，同時根據抓取路徑的具體特點對混合優化算法進行適應性改進。改進的混合優化算法流程如圖4所示。

4 實驗結果

本文將實驗結果分為仿真結果和平臺實驗，仿真主要是論證本文論述的混合優化算法的實驗效果，平臺實驗旨在說明該算法在機器視覺抓取過程實現最優路徑的優化效果，進行整體方案驗證。

4.1 仿真結果

本文的仿真環境為Windows 10系統下Matlab R2016b，主要是將本文得到的混合優化算法和蟻群算法、禁忌搜索算法進行對比分析，從而測試改進算法的效果。位置設定如相關工作所描述，各參數根據經驗和多次實驗得到，初始值設定如表2所示。

在仿真環境下，選取最短路徑和平均路徑因素，將改進的混合優化算法和蟻群算法、禁忌搜索算法進行對比，混合優化算法生成的途徑圖、最短路徑和平均路徑效果如圖5所示。

混合優化算法的到的最優路徑為： 1-3-13-7-16-10-19-8-18-2-11-6-14-9-17-5-15-4-12-1，最優路徑長度為157.991，且根據最短路徑對比圖看出三種算法不同程度反映了其收斂能力和尋求全局最優路徑能力，可以得到以下結論：

1）混合優化算法隨著程序的執行，快速收斂，在迭代10次左右陷入死路，在30代左右，用死路作為禁忌搜索的初始解，加強全局搜索能力，在45代左右得到最優解。

2）混合優化算法相比蟻群算法收斂速度明顯提高，尋找到的最短路徑明顯較優。

3）混合優化算法相比禁忌搜索算在30代左右收斂速度提高，之后經歷10代左右達到最優解，收斂速度快，得到路徑較優。

結合平均距離對比圖可以驗證以上說法，同時看出混合優化算法得到的路徑距離的穩定性較優。

將三種算法同時應用于本文研究的機器視覺抓取圓形玻璃元件問題，選取多組元件進行不同位置的抓取，每組進行20次測試，測試結果如表3所示。

從表3中可以看出，改進的蟻群算法結合禁忌搜索算法的混合優化算法在抓取不同距離位置的元件時均有更好的尋優結果，且尋優結果和距離無關。同組比較，混合優化算法得到較優的最優解且穩定性較好，與ACO和TS相比，混合優化算法的平均迭代次數降低了約50%，且算法用時較短。禁忌搜索算法雖然也可以達到相同的最優解，且算法用時較短，但是得到最優解的穩定性不足，收斂速度不足。蟻群算法得到的最優解過早地收斂，全局搜索能力不足。綜上仿真結果來看，混合優化算法尋優能力優于蟻群算法和禁忌搜索算法，且尋優過程中與元件放置位置到碼盤位置的距離無關，因此在將該混合優化算法應用于機器視覺抓取元件尋求最優路徑較ACO、TS更優。

4.2 平臺實驗

將Matlab生成的混合優化算法封裝成函數供Visual Studio2013調用，做平臺抓取實驗。抓取起始點定義在光源中心點，在對現有抓取起始點，元件抓取點以及碼盤放置點進行1～19依次排序，得到路徑為1-8-19-2-11-3-12-4-13-7-16-10-18-9-17-5-14-6-15-1，完成全部抓取所需要的時間為20.23s，樣機取放結果如圖6所示。

同時保持起始點、放置位置不變，選取三組較放置位置不同距離的元件進行對比，同樣做三種算法的對比實驗，每種進行10組，取抓取時間的平均值（單位：秒），得到結果如表4所示。

由距離組之間的對比實驗可以看出，距離對于各種算法影響差異不大，說明尋優結果與距離無關，驗證仿真實驗的結果。算法之間的對比可知，隨機路徑的用時要優于蟻群算法，其原因在于蟻群算法本身耗時較路徑優化節省的時間更長。混合優化算法較蟻群算法和禁忌搜索算法抓取用時更短，且與隨機路徑相比，混合優化算法平均耗時縮短了6.68%。

5 結語

本研究基于機器視覺定位元件，將元件抓取、放置過程轉換為有約束的TSP，通過仿真結果和平臺實驗表明，結合蟻群優化算法和禁忌搜索算法的混合優化算法在機器視覺定位抓取、放置的過程中，較隨機抓取、蟻群算法和禁忌搜索算法來講，抓取路徑得以優化，抓取效率有效提高。

參考文獻 （References）

[1] 李堯，石紅瑞.基于圖像識別和遺傳算法的Tripod機器人最優軌跡控制[J].計算機應用，2016， 36（S1）：106-109.（LI Y， SHI H Z. Optimal trajectory control of the Tripod robot based on image recognition and genetic algorithm [J]. Journal of Computer Applications， 2016， 36（S1）：106-109.）

[2] DORIGO M， GAMBARDELLA M L. Ant colonies for the travelling salesman problem [J]. Biosystems， 1997，43（2）：73-81.

[3] 葉小勇，雷勇，侯海軍.蟻群算法在全局最優路徑尋優中的應用[J].系統仿真學報， 2007，19（24）：5643-5647. （YE X Y， LEI Y， HOU H J. Application of ant colony algorithm in global optimal path searching [J]. Journal of System Simulation， 2007， 19（24）： 5643-5647.）

[4] 張慕雪，張達敏，楊菊蜻，等.基于禁忌搜索的蟻群算法優化算法[J].通信技術，20178， 50（8）：1658-1663. （ZHANG M X， ZHANG D M， YANG J Q， et al. Ant colony optimization algorithm based on tabu search [J]. Communications Technology， 2017， 50（8）：1658-1663.）

[5] 陳丹，白軍，石國良.一種新的四自由度SCARA機器人手眼標定方法[J].傳感器與微系統，2018，37（2）：72-75.（CHEN D， BAI J，SHI G L. A new method of four DOF SCARA robot hand-eye calibration [J]. Transducer and Microsystem Technologies， 2018， 37（2）： 72-75.）

[6] 高海昌，馮博琴，朱利.智能優化算法求解TSP問題[J].控制與決策，2006，21（3）：241-247.（GAO H C， FENG B Q， ZHU L. Reviews of the meta-heuristic algorithms for TSP [J]. Control and Decision， 2006， 21（3）： 241-247.）

[7] 吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學報，2001，24（12）：1328-1333.（WU B， SHI Z Z. An ant colony algorithm based partition algorithm for TSP [J]. Chinese Journal of Computers， 2001， 24（12）： 1328-1333.）

[8] MULLEN R J， MONEKOSSO D， BARMAN S， et al. A review of ant algorithms [J]. Expert Systems with Applications， 2009， 36（6）： 9608-9617.

[9] 吳慶洪，張穎，馬宗民.蟻群算法綜述[J].微計算機信息，2011，27（9）：1-2. （WU Q H， ZHANG Y， MA Z M. Review of ant colony optimization [J]. Microcomputer Information， 2011， 27（9）： 1-2.）

[10] CIORNEI I， KYRIAKIDES E. Hybrid ant clony-genetic algorithm （GAAPI） for global continuous optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics. Part B， Cybernetics： a publication of the IEEE Systems， Man， and Cybernetics Society， 2012， 42（1）： 234-245.

[11] 張鵬，魏云霞，薛宏全，等.基于優勝劣汰規則的異類多種群蟻群算法[J].計算機工程，2012，38（18）：182-185.（ZHANG P， WEI Y X， XUE H Q， et al. Heterogeneous multiple colonies ant colony algorithm based on survival of fittest rules [J]. Computer Engineering， 2012， 38（18）： 182-185.）

[12] 王凌.智能優化算法及其應用[M].北京：清華大學出版社，2001：67-68.（WANG L. Intelligent Optimization Agorithm and Its Application [M]. Beijing： Tsinghua University Press， 2001： 67-68.）

[13] 劉興，賀國光.車輛路徑問題的禁忌搜索算法研究[J].計算機工程與應用，2007，43（24）：179-181. （LIU X， HE G G. Study on tabu search algorithm for stochastic vehicle routing problem [J]. Computer Engineering and Applications， 2007， 43（24）： 179-181.）

[14] 彭茂.一種求解TSP問題的改進禁忌搜索算法[J].計算技術與自動化，2012，31（1）：78-81.（PENG M. Improved tabu search algorithm for solving traveling salesman problem [J]. Computing Technology and Automation， 2012， 31（1）： 78-81.）

[15] 張勇.基于改進蟻群算法物流配送路徑優化的研究[J].控制工程，2015，22（2）：252-25.（ZHANG Y. Study of optimizing logistic distribution routing based on improved ant colony algorithm [J]. Control Engineering of China， 2015， 22（2）： 252-256.）