基于遺傳算法的分揀機器人最優(yōu)路徑規(guī)劃

（華南理工大學 聚合物新型成型裝備國家工程研究中心 聚合物成型加工工程教育部重點實驗室，廣州 510640）

近年來，工業(yè)機器人技術(shù)發(fā)展迅速，廣泛應(yīng)用于工業(yè)生產(chǎn)的各個方面，具有較大的發(fā)展空間[1-2]。機器人抓取技術(shù)是指工業(yè)生產(chǎn)中實現(xiàn)不同物體的分揀，并且將其快速準確地放在指定位置。如果讓工人長時間從事重復的分揀工作易產(chǎn)生疲勞且效率不高。因此，采用機器人完成分揀工作不僅可以提高工作效率和準確性，更能節(jié)省人力資源成本，增加工廠的效益。機器人分揀物體的路徑優(yōu)化問題是生產(chǎn)中常見的實際難題，如果路徑設(shè)計不合理，將會增加系統(tǒng)的運行時間。分揀順序優(yōu)化是一個組合優(yōu)化問題，而組合優(yōu)化問題是一個復雜的問題，得到了廣泛的研究[3-7]，但對并聯(lián)機器人路徑優(yōu)化的研究還比較少。本文運用遺傳算法對多約束條件的并聯(lián)機器人分揀順序進行了仿真研究并在貝加萊公司最新的Tripod機器人上進行實驗，驗證了該方法的有效性。

1 問題描述

Tripod機器人是貝加萊工業(yè)自動化有限公司和奧地利HTL Wels大學共同設(shè)計的四軸并行機器人，具有3個機械手臂。在3臺相同電機的配合控制下，工具中心可以在X，Y，Z工作空間中進行平移運動，并通過一個步進電機實現(xiàn)旋轉(zhuǎn)。

模擬工件分揀平臺如圖1所示，由外圓環(huán)和內(nèi)圓圈2部分組成。外圓環(huán)上隨機放置9個幾何體，三角形、五角形、圓形各有3片，分別為紅色、藍色和橙色；內(nèi)圓圈上有9個不同形狀的槽位。幾何體放置的朝向與內(nèi)圓圈槽位的朝向一致。機械手依次從外圓環(huán)上抓取9個幾何體放置在對應(yīng)的內(nèi)圓槽位，要求顏色相同的幾何體放置在一起，并且總路徑最短。

圖1 分揀平臺Fig.1 Sorting platform

2 模型建立

Tripod機器人在分揀過程中，對每個分揀工件都只允許抓取一次，這可以等效為一個帶約束條件的旅行商問題。旅行商問題（TSP）是指給定n個城市的點的坐標，遍歷所有城市以最短距離路線，即搜索自然子集X=｛1，2，…，n｝（X的元素表示n個城市的編號）的一個排列π（X）=（V1，V2，…，Vn），使其滿足：

取最小值，其中 d（Vi，Vi+1）表示城市 Vi到 Vi+1的距離[8]。

本文采用遺傳算法進行TSP問題的求解。遺傳算法是一種借鑒生物進化過程中“物競天擇，適者生存”規(guī)則的智能算法，可以由1個8元組組成[9]：

式中：C為個體編碼方法；E為個體適應(yīng)度評價函數(shù)；P0為初始群體；M為群大小；Φ為選擇算子；Γ為交叉算子；Ψ為變異算子；T為遺傳算法終止條件。

設(shè)機器人分揀的工件為n個，V=｛V1，V2，…，Vn｝是n個工件的集合，［Dij］n×n（i，j=1，2，3，…，n）為物體Vi與物體Vj之間距離所組成的距離矩陣，計算出通過V中所有工件最短路徑矩陣D1。建立約束矩陣D2，D1與D2是同維矩陣。將D1與D2進行組合，尋找F=min（Td）的抓取順序。這樣就建立了機器人分揀順序的數(shù)學模型，將機器人分揀順序最優(yōu)化問題抽象成圖論中TSP來求解。

3 最優(yōu)路徑規(guī)劃問題遺傳算法實現(xiàn)

3.1 遺傳算法流程

通過遺傳算法進行機器人分揀最優(yōu)路徑規(guī)劃，并在其中加入約束矩陣完成目標。算法的流程如圖2所示。

圖2 遺傳算法流程Fig.2 Flow chart of genetic algorithm

3.2 遺傳算法實現(xiàn)步驟

1）編碼：采用符號編碼方法，內(nèi)圓上9個點的順序與序號是固定的，依次標記為｛1，2，3，4，5，6，7，8，9｝。外環(huán)上9個點的順序是可以變化的，設(shè)定10代表橙三角形，11代表橙五角星，12代表橙圓，13代表黃三角形，14代表黃五角星，15代表黃圓，16代表藍三角形，17代表藍五角星，18代表藍圓，如圖3所示。

圖3 對象編號Fig.3 Object code

分揀臺上18個中心坐標，可以由Tripod機器人上的攝像機拍照求得，本文主要研究該機器人的路徑規(guī)劃問題，對圖像處理部分不作介紹。18個目標的坐標值如表1所示。

表1 18個編號的坐標表Tab.1 18 number coordinates

2）多約束條件矩陣化：根據(jù)模型，在生成的距離矩陣的基礎(chǔ)上添加一個對應(yīng)的約束矩陣為

約束矩陣中inf代表無限大數(shù)值，左上角的9×9部分限制內(nèi)環(huán)上9個幾何體之間不能相互在抓取的相鄰次序，右上角部分的9×9部分是從外環(huán)上抓取放入內(nèi)環(huán)上的幾何體的形狀必須是一樣的，且相同顏色放一起，左下角9×9部分是從內(nèi)環(huán)可以到外環(huán)上任何一個幾何體處抓取，右下角的9×9部分代表外環(huán)上9個幾何體之間不能是抓取的相鄰次序。約束矩陣的構(gòu)造是本遺傳算法中一個關(guān)鍵的步驟，約束條件矩陣化的實質(zhì)是對適應(yīng)度函數(shù)進行調(diào)整，對不符合約束條件的增加適應(yīng)度函數(shù)值，從而減少被選中的概率。

3）種群初始化：考慮到滿足約束條件，在約束矩陣的限制下通過一個隨機函數(shù)對種群進行初始化。

其中，n=18。

5）選擇操作：采用聯(lián)賽選擇機制，從群體中任意選擇一定數(shù)目的個體，其中適應(yīng)度最高的個體保存到下一代，反復執(zhí)行，直到保存到下一代的個體數(shù)達到預(yù)先設(shè)定的數(shù)目為止。

6）交叉操作：采用部分匹配交叉法（PMX），依據(jù)均勻隨機分布產(chǎn)生2個位串交叉點，定義這2點之間的區(qū)域為一匹配區(qū)域，并使用位置交換操作交換2個父串的匹配區(qū)域。

7）變異操作：采取隨機在18個目標中選取2個點，將其對換位置。

8）進化逆轉(zhuǎn)操作：為提高遺傳算法的局部搜索能力，引進多次連續(xù)的單方向進化逆轉(zhuǎn)操作，只有經(jīng)逆轉(zhuǎn)后，適應(yīng)度值有提高的才接受下來，否則逆轉(zhuǎn)無效。

對于每一個目標體進行交叉變異，代入適應(yīng)度函數(shù)中進行評估，選出適應(yīng)度最大的個體進行下一代的交叉、變異以及進化逆變操作，直到滿足設(shè)定的最大遺傳代數(shù)。

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

在MATLAB7.1環(huán)境下編寫與運行。種群數(shù)為100，交叉率為0.9，變異率為0.05，代溝為0.9，最大迭代次數(shù)為250。在MATLAB中用遺傳算法最優(yōu)抓取順序 15-＞6-＞18-＞9-＞12-＞3-＞14-＞5-＞10-＞1-＞13-＞4-＞17-＞8-＞16-＞7-＞11-＞2-＞15，總距離：3009.5752 mm，如圖4所示。

圖4 最優(yōu)路徑Fig.4 Optimal path

根據(jù)仿真結(jié)果得到的最優(yōu)路徑，利用TCPUDP Socket調(diào)試工具將最優(yōu)路徑數(shù)據(jù)通過TCP/IP發(fā)送給Tripod機器人，進行試驗。試驗結(jié)果表明機器人能夠按照最優(yōu)路徑準確抓取物體并放入內(nèi)圓相應(yīng)位置，如圖5所示。

圖5 實驗結(jié)果Fig.5 Result of test

5 結(jié)語

通過添加約束矩陣的遺傳算法進行路徑的最優(yōu)化，可以有效減少機器計算運行的時間，提高抓取的準確性，在工業(yè)生產(chǎn)中能有效降低生產(chǎn)成本。提出的將多約束條件變成約束矩陣的方法，對于帶約束條件的TSP問題具有適用性，能夠在以后的TSP及機械手抓取物體的工程應(yīng)用中有較好的適用性、移植性。

[1] 王田苗，陶永.我國工業(yè)機器人技術(shù)現(xiàn)狀與產(chǎn)業(yè)化發(fā)展戰(zhàn)略[J].機械工程學報，2014，50（9）：1-13.

[2] 譚民，王碩.機器人技術(shù)研究進展[J].自動化學報，2013，39（7）：963-972.

[3] 田貴超，黎明，韋雪潔.旅行商問題（TSP）的幾種求解方法[J].計算機仿真，2006，23（8）：153-157.

[4] 朱玲湘，廖芹，鄒亮.運用遺傳算法求解有約束條件的旅行商問題[J].華南理工大學學報：自然科學版，2004，32（4）：97-100.

[5] Moon Chiung，Kim Jongsoo，Choi Gyunghyun，et al.An efficient genetic algorithm forthe traveling salesman problem with precedence constraint[J].European Journal of Operational Research，2002，140（3）：606-617.

[6] 張永德，姜金剛，唐偉，等.基于遺傳算法的直角坐標式排牙機器人路徑規(guī)劃[J].哈爾濱理工大學學報，2013，18（1）：22-26.

[7] 陳冰梅，樊曉平，周志明，等.求解旅行商問題的Matlab蟻群仿真研究[J].計算機測量與控制，2011，19（4）：990-992

[8] 史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學出版社，2011.

[9] 牟銜臣，謝東來，閆威，等.基于遺傳算法航路規(guī)劃TSP問題的研究[J].系統(tǒng)仿真學報，2013，25（8）：86-89.