張瑞星，李秀娟，高 喚

(河南工業(yè)大學 電氣工程學院，鄭州 450000)

0 引言

焊接是汽車生產(chǎn)的主要工藝之一，其質量的高低會直接影響車身的性能。白車身作為汽車其它零件的載體[1]共有上千個焊點，單機器人系統(tǒng)已經(jīng)無法快速的完成如此復雜的焊接任務，因此雙機器人系統(tǒng)得以迅猛發(fā)展。文獻[2]針對雙機同步焊接問題，引入虛擬焊點將多個旅行商問題(Multiple Traveling Salesman Problem，MTSP)轉換為旅行商問題(Traveling Saleman Problem，TSP)，建立雙機同步焊接模型；文獻[3]針對白車身雙機同步焊接路徑規(guī)劃問題，采用柵格法建立同步焊接模型。文獻[4]通過對機器人動作節(jié)拍的設計優(yōu)化以及雙機的互索設計，完成了雙機協(xié)同控制。文獻[5]以雙機對稱焊接為例，提出了雙機協(xié)調鏡像運動的協(xié)調軌跡方法。

傳統(tǒng)焊接路徑規(guī)劃大都是基于技術人員的示教操作，這種方法不僅周期長且很難得出最優(yōu)路徑。隨著人工智能的迅猛發(fā)展，目前已經(jīng)提出了許多智能算法并將其應用到焊接機器人的路徑規(guī)劃中。文獻[6]以生產(chǎn)節(jié)拍為約束條件，采用遺傳算法(Genetic Algorithm，GA)進行焊接路徑規(guī)劃。文獻[7]提出了一種結合萊維飛行的粒子群算法(Particle Swarm Optimization，PSO)來求解焊接任務。文獻[8]以最短無碰撞為焊接約束條件，提出遺傳粒子群優(yōu)化算法解決焊接機器人的路徑規(guī)劃問題。文獻[9]以時間最短為約束條件，提出了遺傳混沌粒子群優(yōu)化算法來解決焊接機器人路徑規(guī)劃問題，能夠快速的得到全局最優(yōu)解。

蟻群算法(Ant Colony Optimization，ACO)是Marco Dorigo[10]提出的一種具有正反饋調節(jié)能力的啟發(fā)式算法。針對該算法的存在的問題，學者們提出了很多改進方法。文獻[11]提出了對傳統(tǒng)蟻群算從概率計算、最優(yōu)路徑二次優(yōu)化等方面進行改進，增強了算法的魯棒性與快速收斂性。文獻[12]在蟻群算法的啟發(fā)函數(shù)中引入人工勢場思想的引力系數(shù)和避障系數(shù)，提高了算法的收斂速度。文獻[13]引入約束因子，改進信息素的更新規(guī)則，加強了算法的全局搜索能力。文獻[14]提出一種基于蟻群的并行協(xié)同算法，通過使用3-opt算法避免陷入局部最優(yōu)，增強了算法的全局搜索能力。文獻[15]提出了一種新的增強信息素更新機制，增強了未使用過的信息素，利用動態(tài)信息進行路徑優(yōu)化，提高了全局搜索能力。

由上述分析可知，解決雙機協(xié)同焊接的核心就是正確建立協(xié)同焊接模型，本文選擇MTSP作為焊接的數(shù)學模型。改進ACO算法的主要方式是提升算法的收斂速度和全局搜索能力。本文針對ACO算法和PSO算法進行分析，提出了一種基于蟻群粒子群的融合算法求解MTSP問題。實驗結果表明該算法對于求解組合優(yōu)化問題能夠得到更優(yōu)解。

1 問題描述

對于多機協(xié)同作業(yè)，在不考慮焊接工藝的前提下，可將其抽象為MTSP問題。MTSP問題是指給定N個城市的集合，M個商人分別從各自所在的城市出發(fā)，每一個商人走一條線路，使得每一個城市有且只有一個商人訪問過，最后商人們返回出發(fā)的城市，要求商人所走的路徑之和最短。解決MTSP問題的核心思想是對待優(yōu)化問題進行帶約束條件的分組，令MTSP問題轉化為一般的TSP問題。本文構建的TSP模型為：

(1)

其中，Ld為路徑長度；di,i+1為城市間的距離。

2 融合算法

2.1 蟻群算法的原理與改進

2.1.1 基本蟻群算法

(2)

其中，ηij(t)=1/dij為啟發(fā)函數(shù)；allowk為螞蟻k未訪問城市的集合；α為信息度濃度重要因子；β為啟發(fā)函數(shù)重要程度因子。當蟻群完成一次循環(huán)后，城市之間的信息素將會更新，更新公式為：

(3)

(4)

其中，Q為常數(shù)；Lk為本倫循環(huán)最短路徑。

2.1.2 蟻群算法的改進

由于未對信息素濃度閾值進行設定，當多次循環(huán)后，信息素會聚集在幾條相對較短的路徑上，這些路徑不一定是全局最優(yōu)，有可能是局部最優(yōu)解。為避免上述問題的發(fā)生，本文針對蟻群算法的缺點，提出了一種基于災變策略的最大最小螞蟻算法(Catastrophe Max Min Ant，CMMA)，具體實現(xiàn)如下：

(1)增加信息素濃度的閾值。在初始時，設置信息素濃度的上限max_ph與下限min_ph；設置信息素的初始濃度τ0=max_ph。

(2)更改狀態(tài)轉移規(guī)則。設常數(shù)p0,若rand>p0則按照公式(3)更新，若rand

(5)

(3)加入精英蟻群思想。將上次循環(huán)中的最優(yōu)路徑替換掉本次循環(huán)中的最劣路徑，使得優(yōu)秀信息可以保留。

(4)改變信息素更新規(guī)則。每次循環(huán)只允許最優(yōu)路徑參與信息素更新，令當前最優(yōu)與歷史最優(yōu)路徑交叉參與，完成信息素的一次更新，新的信息素增量公式為：

(6)

其中，Lk_best為歷史最短路徑；N為當前迭代次數(shù)。本次循環(huán)找出最優(yōu)路徑的螞蟻為第i只，以信息素矩陣的第i行為藍本進行信息素閾值更新，通過閾值完成信息素二次更新，信息素閾值的更新公式：

(7)

(5)災變操作。若連續(xù)C次歷史最短路徑未發(fā)生變化，則進行災變操作，將信息素矩陣重置。

(6)若達到結束條件則停止循環(huán)，否則重復上述過程。

2.2 粒子群算法的原理與改進

2.2.1 基本粒子群算法

在M維的空間里，n個粒子組成粒子群X，X=(X1,X2,...,Xn),第i個粒子為一個M維的向量Xi，Xi=(x1,x2,...,xM),表示粒子在M維空間中的位置，即一個待優(yōu)化問題的可行解。粒子Xi的速度為Vi；其個體極值為Pi,表示第i個粒子的歷史最優(yōu)值；粒子群的群體極值為Pg,表示當前粒子群中的最優(yōu)值。

粒子群算法的核心思想是在每次循環(huán)過程中，通過個體極值與群體極值跟蹤粒子的速度與位置，使粒子的位置不斷向最優(yōu)解靠近，計算公式：

(8)

其中，ω為慣性權值，決定當前粒子速度對下次粒子速度的影響程度；k為當前的迭代次數(shù)；c1、c2為屬于[0,1]的常數(shù)，分別決定了當前個體極值與群體極值對下次粒子速度的影響程度。

2.2.2 粒子群算法的改進

粒子群算法與其他智能算法相比，有著收斂迅速這一鮮明特點，但是粒子算法有著諸多不足，其中最為突出的是無法解決離散問題與易“早熟”。為解決上述問題本文提出一種混沌粒子群遺傳算法(Chaos Particle Swarm Genetic，CHPG)。

(1)生成混沌種群

常見的混沌映射有一維logistic映射、二維Henon映射、三維Lorenz映射等。其中l(wèi)ogistic映射被廣泛的使用，本文使用的就是logistic混沌映射，logistic混沌映射的更新公式：

Xn+1=Xnμ(1-Xn)

(9)

其中，X為(0,1)的隨機數(shù)；μ為[0,4]的隨機數(shù)?；煦绶N群的產(chǎn)生過程如下所示：

1)設問題規(guī)模n,隨機生成一個可行解X，X=(x1,x2,...,xn)；

2)將X歸一化，使結果映射到[0,1]之間，轉換公式如下所示，其中ε為常數(shù)：

(10)

3)根據(jù)公式(9)，生成序列Z對應的混沌序列ZCH。將混沌序列中的元素按從大到小排序，此時混沌元素對應的標簽組成的元素就是一個混沌粒子；

4)根據(jù)種群規(guī)模重復上述過程m次，即可得到種群規(guī)模為m的混沌種群。

(2)交叉、變異的融合

引入遺傳算法的交叉、變異策略克服粒子群算法無法解決離散問題的缺點；引入混沌種群，通過多種群信息交換，克服粒子群算法“早熟”的缺點。具體實現(xiàn)過程如下所示：

1)種群交叉：設粒子群為pop1，混沌種群為pop2，將兩個種群交叉生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

2)群體極值交叉：pop1、pop2分別與各自的群體極值交叉，生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

3)一次變異：對于pop1、pop2中的每個粒子，分別選擇兩個交叉位，交換交叉位上的元素，生成新的種群child1、child2，若子代優(yōu)秀則更新父代；

4)二次變異：對于pop1，pop2中的每個粒子，分別選擇兩個交叉位，翻轉兩個交叉位之間的元素，生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

5)找出最短路徑。找出上述child1、child2的群體極值，進行比較找出最短路徑；

6)災變操作。若連續(xù)C次歷史最短路徑未發(fā)生變化時，則進行災變操作，即重新生成pop1、pop2兩個種群；

7)若達到結束條件則停止循環(huán)，否則重復上述過程。

2.3 融合算法思想

融合算法(Chaos Ant Particle Genetic，CHAPG)的核心思想就是充分的利用蟻群算法的正反饋調節(jié)機制。令經(jīng)過優(yōu)化的路徑參與信息素的更新，在正反饋調節(jié)的作用下，指導蟻群在下一次循環(huán)中建立優(yōu)秀的可行解空間，具體的操作如下：

(1)初始化算法參數(shù)；

(2)在改進后的狀態(tài)轉移規(guī)則的指導下構建解空間pop1，依據(jù)上述混沌種群的生成規(guī)則，構建解空間pop2；

(3)分別計算pop1、pop2的群體極值；

(4)進行種群交叉、群體極值交叉、一次變異操作、二次變異操作；

(5)計算經(jīng)過優(yōu)化后的兩個種群的群體極值，并找出最優(yōu)解；

(6)對pop1進行精英操作，將上次循環(huán)中pop1的最優(yōu)路徑代替本次循環(huán)中pop1中的最劣路徑；

(7)判斷是否滿足災變條件，若滿足則初始化信息素與pop2；否則，令經(jīng)優(yōu)化過的路徑參與信息素的更新，在改進后的信息素增量規(guī)則的指導下更新信息素，完成信息素一次更新，更新信息素的閾值，利用閾值再次更新信息素，完成信息素二次更新；

(8)若達到結束條件則停止循環(huán)，否則返回到步驟(2)繼續(xù)循環(huán)。

3 算法的設計與仿真

3.1 算法設計

根據(jù)上述算法的工作原理，本文所提出的算法流程圖如圖1所示。

圖1 CHAPG算法流程圖

3.2 MATLAB 仿真與分析

為驗證本文所提出CHAPG算法的有效性，在TSPLIB標準庫中選擇不同樣本進行驗證，與ACO、CMMA、CHPG算法的結果進行對比，得到的驗證結果如表1～表3所示。

表1 Eil51試驗結果

表2 Eli101試驗結果

表3 Ch150實驗結果

圖4 雙機器人焊接工作站

上表中分別列出了4種算法在不同樣本集下運行10次結果。在不同樣本試驗中，ACO算法與其他3種算法相比，均陷入了局部最優(yōu)，無法進行全局搜索；CMMA算法取得了較好全局最優(yōu)解，但是搜索時間過長；CHPG在最優(yōu)解與搜索時間上取得了較好的結果，但是算法的魯棒性較差；CHAPG算法在5種指標中均取得了較好的結果，體現(xiàn)出了CHAPG算法良好的性能。試驗表明CHAPG算法在處理不同規(guī)模數(shù)據(jù)時均擁有良好的全局搜索能力與快速收斂能力。

4 雙機協(xié)同

對于雙焊接機器人系統(tǒng)，不僅需要最短路徑為準則，還需要增加一些約束條件，確保焊接的同步性，具體做法如下所示。

圖5 焊點可達性分析

(1)根據(jù)焊點數(shù)據(jù)與機器人TCP之間的歐氏距離的大小進行焊點的初次分配。S1、S2分別為焊點到與機器TCP距離的集合，若S1

(2)分別計算出R1、R2對應的焊接距離L1、L2，計算L1與L2之間的差值，若小于常數(shù)D則跳出循環(huán)，否則繼續(xù)。

圖2 協(xié)同算法流程圖

圖6 干涉性檢查

(3)S12為R1的TCP到n2的距離由小到大的集合，S21為R2的TCP到n1的距離由小到大的集合。若L1>L2，則將S21中最小值對應的焊點添加到n2中；若L2>L1，則將S12中最小值對應的焊點添加到n1中，完成焊點的更新，否則，跳轉到(2)繼續(xù)循環(huán)。

根據(jù)上述算法的工作原理，本文所提出的協(xié)同算法的流程圖如圖2所示。

5 ROBCAD仿真

5.1 雙機器人路徑規(guī)劃

以某汽車白車身一側為例，共192個焊點；CHAPG算法的參數(shù)設置如下：m=192，n=50，α=1，β=5，θ=0.1，設置迭代次數(shù)為200，在MATLAB中進行仿真實驗，得到的路徑如圖3所示。

圖3 雙機器人路徑規(guī)劃(mm)

5.2 建立三維模型

將在CATIA中建立的白車身數(shù)模，導入ROBCAD中；將焊點數(shù)據(jù)導入在白車身上；在ROBCAD中建立雙機器人工作站，如圖4所示。

5.3 焊點可達性分析

將導入的焊點映射到白車身這一過程中，焊點自身的坐標系是隨機生成的，標準的焊點坐標系是z軸垂直向上，x軸是向著焊槍的方向。對于點焊機器人來說，由于關節(jié)角的限制，機器人都有著自己的工作空間，因此必須通過ROBCAD的Spot模塊進行可達性分析，如圖5所示，當焊點坐標的x軸在藍色區(qū)域則表明該機器人可以到達該焊點，當在紅色區(qū)域時，則表示無法到達該焊點。依次調整焊點坐標系，確保每一個焊點都在對應機器人的工作空間。

5.4 機器人干涉檢查

對于多機器人協(xié)同路徑規(guī)劃，一般都會存在干涉情況，因此需要通過使用ROBCAD中的Collision Setup模塊進行干涉檢查，找出發(fā)生干涉的位置。對于大多數(shù)發(fā)生干涉的位置，只需要通過調整焊點的坐標系或者機器人的姿態(tài)就可以。如圖6所示，x軸的方向朝向車身，當焊槍進行焊接時會與車身發(fā)生干涉，旋轉焊點坐標系，使焊點的x軸離開車身。對于一些特殊情況，不能通過上述方法進行調解時，可以通過增加過度焊點的方法解決。適當?shù)脑黾舆^渡焊點，可以使焊槍避開工件或夾具。

6 結論

利用焊點與機器人TCP之間的歐式距離關系將焊點進行分配，將MTSP問題轉換為TSP問題，依靠焊接路徑之間的關系不斷更新焊點，確保多機器人協(xié)同工作的同步性；在ACO算法中加入精英思想，改變狀態(tài)轉移規(guī)則與信息素更新方式，增加了算法的全局收縮能力；引入混沌總群，加入GA算法的進化思想，提高了算法的快速收斂能力。通過MATLAB的實驗驗證，本文所提出的CHAPG算法在求解組合優(yōu)化問題時比ACO算法、CMMA算法、CHPG算法、CHPG算法具有更佳的效果。在ROBCAD平臺上進行雙機器人協(xié)同焊接仿真實驗，解決了可達性與干涉性等在實際應用中存在的問題，提高了焊接效率。