基于改進(jìn)蟻群算法的打磨機(jī)器人路徑規(guī)劃

蔡改貧，陳永康，周小云，李宇達(dá)，曾常熙

(江西理工大學(xué)機(jī)電工程學(xué)院，江西贛州 341000)

0 前言

打磨機(jī)器人是從事打磨加工的工業(yè)機(jī)器人，在機(jī)器人的末端安裝抓取工具，進(jìn)行運(yùn)動控制，使抓取的工件可以到達(dá)并固定于刀具的特定位置，根據(jù)工件打磨形狀的需要，機(jī)器人抓取工件進(jìn)行相應(yīng)的軌跡運(yùn)動，完成工件弧形曲面的加工。打磨機(jī)器人路徑規(guī)劃目的是在空間環(huán)境中按照一定的規(guī)則，規(guī)劃出由起點(diǎn)到終點(diǎn)用時最短或最光滑的路徑，有利于深入研究機(jī)器人應(yīng)用領(lǐng)域。

自20世紀(jì)以來，路徑規(guī)劃技術(shù)的研究已經(jīng)取得了許多重要成果。許多二維路徑規(guī)劃建模方法沿用至今，如網(wǎng)格法、拓?fù)浞?、可見圖法等。隨著軌跡規(guī)劃領(lǐng)域不斷發(fā)展，出現(xiàn)了更多復(fù)雜的路徑規(guī)劃算法，如Dijkstra算法、Prim算法、模擬退火算法、蟻群算法、A算法、人工勢場法和模糊邏輯控制算法，它們在工程實(shí)踐中得到了廣泛應(yīng)用。其中，蟻群算法是一種分布式智能仿生算法，主要模擬蟻群在尋找食物過程中協(xié)同合作搜尋最佳路徑的過程，搜尋過程具有正反饋性、并行性及較強(qiáng)的魯棒性等優(yōu)點(diǎn)。蟻群算法已廣泛應(yīng)用于車間調(diào)度、旅行規(guī)劃、網(wǎng)絡(luò)路由、機(jī)器人路徑規(guī)劃、電力系統(tǒng)、聚類分析、數(shù)據(jù)挖掘和圖像處理等領(lǐng)域。在機(jī)器人路徑規(guī)劃領(lǐng)域，LEE等利用遺傳算法優(yōu)化蟻群算法參數(shù)，實(shí)現(xiàn)動態(tài)路徑規(guī)劃。邱莉莉和鄭建立改進(jìn)信息素初始化和狀態(tài)轉(zhuǎn)移概率，但該方法只能降低螞蟻陷入死鎖的可能性，不能完全避免死鎖的發(fā)生。趙華東等提出相應(yīng)的死角表，當(dāng)螞蟻陷入死鎖時，可以使用罰函數(shù)來更新軌跡。

基于以上分析，根據(jù)打磨機(jī)器人工作方法的有效性和實(shí)時性的要求，針對具體打磨機(jī)器人的構(gòu)型，對機(jī)器人進(jìn)行D-H建模分析，再進(jìn)行運(yùn)動學(xué)分析與驗(yàn)證。針對路徑規(guī)劃問題，通過改進(jìn)蟻群算法的信息素更新方法，將新的自適應(yīng)計(jì)算方法應(yīng)用于狀態(tài)轉(zhuǎn)移規(guī)則中，并通過引入阻尼系數(shù)改進(jìn)啟發(fā)式信息函數(shù)，在MATLAB中進(jìn)行模擬實(shí)驗(yàn)，尋找到一條最優(yōu)路徑，驗(yàn)證該方法的可行性。

1 打磨機(jī)器人運(yùn)動學(xué)分析

1.1 正運(yùn)動學(xué)模型分析

當(dāng)需要確定機(jī)器人在空間中的位置關(guān)系時，可以在機(jī)械手的三維空間中固定一個坐標(biāo)系，然后分析該坐標(biāo)系的原點(diǎn)位置與、、軸的位置關(guān)系，即建立D-H坐標(biāo)系，分析得出各個連桿D-H參數(shù)；從第一個關(guān)節(jié)開始依次進(jìn)行變換，直到最后一個關(guān)節(jié)被確定，這樣就確定了機(jī)械手的總變換矩陣。圖1所示為打磨機(jī)器人結(jié)構(gòu)簡圖，圖中右側(cè)為打磨刀具。

圖1 打磨機(jī)器人模型簡圖

各關(guān)節(jié)D-H參數(shù)如表1所示。

表1 各關(guān)節(jié)D-H參數(shù)

(=1,2,…,6)表示各個關(guān)節(jié)的D-H矩陣，則得出運(yùn)動學(xué)方程如下：

(1)

其中：、、分別表示機(jī)械手末端坐標(biāo)系的3個坐標(biāo)軸上的單位向量投影到基座坐標(biāo)系的方向余弦;表示末端坐標(biāo)原點(diǎn)在基座坐標(biāo)系的坐標(biāo)值。

(2)

1.2 逆運(yùn)動學(xué)分析

(3)

(4)

其中：

=sin=cos

=-[(+)-(-)]-

(-)

=[(+)-(-)]-

(-)

=-(+)-(-)

=-(+)-[(+)+

(-)]

=(+)-[(-)+

(+)]

=[(-)+(+)]+

(+)

=(+)-(-)

=--(-)-[(-)-

(+)]

令式(4)左右兩邊(2,3)和(2,4)元素對應(yīng)相等，則有-=和-=。解該方程組得tan=(-)(-)，得的表達(dá)式為

=arctan[(-)(-)]

(5)

(6)

=-=

(7)

(8)

(9)

(10)

其中：

=sin(+)=cos(+)

=++-+

=cos==sin=

驗(yàn)證過程：設(shè)連桿參數(shù)=300 mm、=320 mm、=400 mm，并設(shè)6個關(guān)節(jié)角度均為30°，從而由運(yùn)動方程求解得：

(11)

則可得、、、、、、、、、、、，將各數(shù)據(jù)代入各關(guān)節(jié)角度表達(dá)式，使用MATLAB得計(jì)算結(jié)果：=30004 9°、=30010 3°、=20931 3°、=29999 8°、=30006 4°、=30006 6°。

2 改進(jìn)蟻群算法的路徑規(guī)劃

2.1 三維環(huán)境建模

路徑規(guī)劃中傳統(tǒng)的環(huán)境建模方法包括可視圖法、單元樹法和二維柵格法，此類柵格法可推廣到三維空間中。本文作者采用山峰式環(huán)境模型模擬機(jī)器人工作環(huán)境，將真實(shí)的機(jī)器人三維環(huán)境用抽象的山峰圖形表示。為簡化蟻群算法路徑規(guī)劃，以機(jī)器人自身基坐標(biāo)系為基礎(chǔ)，建立環(huán)境模型坐標(biāo)系-。

實(shí)驗(yàn)環(huán)境是Window 10系統(tǒng)、MATLAB 2016a、RobotStudio6.0、英特奔騰CPU 1.70 GHz,內(nèi)存12 GB,64位操作系統(tǒng)。圖2所示為機(jī)器人工作環(huán)境，將工作空間中的其他設(shè)備與障礙物以山峰代替。如圖3所示，在MATLAB 2016a中繪制立體抽象的山峰圖形模擬機(jī)器人的工作環(huán)境。(0～100 km)軸表示經(jīng)度方向距離，(0～100 km)軸表示緯度方向距離，(0～2 500 m)軸表示海拔高度。地形中的非平面部分可以理解為障礙物，凸起的曲面障礙物為斜坡，凹陷的曲面障礙物為溝渠。

圖2 機(jī)器人工作環(huán)境

圖3 三維環(huán)境模型

2.2 蟻群算法介紹

(12)

其中:是下一節(jié)點(diǎn)集合；()是路徑(，)的信息素值；是信息素激勵因子;是期望的啟發(fā)式因子。啟發(fā)式因子計(jì)算公式：

(13)

式中：為節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的歐氏距離。

局部信息素會在螞蟻搜尋下一個節(jié)點(diǎn)時進(jìn)行更新：

(+1)=(1-)()

(14)

式中:()表示信息素在離散點(diǎn)(，，)上的濃度值；表示更新的次數(shù)；(0<<1)為全局信息素更新系數(shù)。

2.3 改進(jìn)蟻群算法

利用蟻群算法進(jìn)行路徑規(guī)劃時，要找到全局最優(yōu)路徑，搜索空間必須足夠大，而且該算法搜索機(jī)制具有較強(qiáng)的不確定性，特別是在初始階段，隨機(jī)搜索使得它不可避免地產(chǎn)生大量的局部交叉路徑、圓形路徑和鋸齒形路徑，得出的規(guī)劃曲線并不能達(dá)到預(yù)期的效果。對此，作出如下改進(jìn)：

(1)改進(jìn)信息素更新規(guī)則

當(dāng)螞蟻利用公式(14)完成局部信息素更新后，加入全局信息素更新，在已完成搜索的路徑中，只更新最短路徑中節(jié)點(diǎn)的信息素，減少信息素更新時所需的時間，提高了搜索效率。全局信息素更新規(guī)則如下：

(+1)=(1-)()+Δ

(15)

(16)

式中：()表示三維環(huán)境中離散點(diǎn)的信息素濃度；{()}表示螞蟻(=1，2，…,)搜索的路徑長度集;為常數(shù)。

(2)改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則

為提高搜索效率和算法質(zhì)量，采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則。設(shè)螞蟻在時位于節(jié)點(diǎn)，則在+1時的位置為

(17)

式中：為過渡比的基準(zhǔn)速率,在(0，1)范圍內(nèi)；為一個隨機(jī)數(shù)。

當(dāng)<時，下一個節(jié)點(diǎn)直接由信息素濃度的最大值和啟發(fā)式信息的實(shí)現(xiàn)決定；然后，采用輪盤賭方式確定節(jié)點(diǎn)。具體實(shí)現(xiàn)過程：根據(jù)公式(17)計(jì)算出所有允許路徑的轉(zhuǎn)移概率，將轉(zhuǎn)移概率從大到小排序，用輪盤賭選擇方法確定下一個節(jié)點(diǎn)。

(3)改進(jìn)啟發(fā)式信息函數(shù)

基本蟻群算法的啟發(fā)式信息值與下一個節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離呈反比，但是在不考慮當(dāng)前節(jié)點(diǎn)和下一個節(jié)點(diǎn)位置的情況下，選擇的路徑不一定是最短的，在搜索后期，為加快收斂速度，應(yīng)該弱化啟發(fā)式信息對路徑選擇的影響。為此，提出一種改進(jìn)啟發(fā)式信息函數(shù)的方法，通過引入阻尼系數(shù)，新的啟發(fā)式信息函數(shù)如式(18)所示：

(18)

(19)

其中:為當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的歐氏距離；為最大迭代次數(shù)；為當(dāng)前迭代次數(shù)。

2.4 改進(jìn)蟻群算法步驟

(1)參數(shù)初始化。初始化初始點(diǎn)位置、目標(biāo)點(diǎn)位置、迭代次數(shù)、螞蟻數(shù)、信息素啟發(fā)式因子、期望啟發(fā)式因子、全局信息素更新系數(shù)和阻尼系數(shù)。

(2)開始迭代，進(jìn)行路徑探索。發(fā)動螞蟻開始正向搜索，根據(jù)公式和輪盤賭法選擇下一個路徑點(diǎn)。

(3)局部信息素更新。當(dāng)螞蟻搜尋到某一個點(diǎn)時，先進(jìn)行局部的信息素更新，進(jìn)而判斷當(dāng)前螞蟻是否進(jìn)入死鎖狀態(tài)。死鎖狀態(tài)時返回上一節(jié)點(diǎn)，更改下一節(jié)點(diǎn)位置；非死鎖時進(jìn)入下一步驟。

(4)路徑搜索。根據(jù)偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則確定節(jié)點(diǎn)后，螞蟻持續(xù)進(jìn)行搜索，最終判斷當(dāng)前螞蟻是否完成路徑搜索，若當(dāng)前螞蟻完成路徑搜索，則下一只螞蟻開始進(jìn)行搜索。

(5)全局信息素更新。當(dāng)所有螞蟻完成搜索后，需要找到該迭代過程中所有完整路徑中的最優(yōu)路徑和最差路徑，并根據(jù)公式加強(qiáng)最優(yōu)路徑上的信息素以及減弱最差路徑上的信息素。

(6)搜索結(jié)束。判斷是否滿足結(jié)束條件，如果滿足，則輸出最佳路徑；否則繼續(xù)循環(huán)執(zhí)行，直到滿足結(jié)束條件或達(dá)到最大迭代次數(shù)時終止。

圖4 改進(jìn)算法流程

3 仿真結(jié)果與分析

3.1 算法參數(shù)的選擇與分析

蟻群算法中的參數(shù)選擇對路徑規(guī)劃的效果有很大影響。仿真中采用經(jīng)驗(yàn)和實(shí)驗(yàn)相結(jié)合的方法，通過設(shè)置不同的參數(shù)進(jìn)行仿真實(shí)驗(yàn)，并分析實(shí)驗(yàn)結(jié)果的優(yōu)缺點(diǎn)，選擇最佳參數(shù)組合。當(dāng)螞蟻數(shù)量過多時，會削弱信息素濃度的影響。而當(dāng)算法收斂速度過快時，則將削弱算法對全局搜索能力的影響。因此，在仿真實(shí)驗(yàn)中，在保持其他參數(shù)不變的情況下，不斷比較和分析不同螞蟻數(shù)量得出的仿真運(yùn)算結(jié)果，最終設(shè)置螞蟻數(shù)=100。

、是算法的重要參數(shù)，是信息素激勵因子，反映信息素濃度對路徑選擇的重要性，是期望的啟發(fā)式因子，反映啟發(fā)式信息對路徑的重要性。當(dāng)大于時，經(jīng)驗(yàn)因素占主導(dǎo)地位，螞蟻可能重復(fù)行走路徑，進(jìn)而削減搜索的隨機(jī)性；當(dāng)小于時，確定性因素占主導(dǎo)地位，螞蟻急于綜合選擇路徑成本最小的路徑，無法實(shí)現(xiàn)全局最優(yōu)。同樣，全局信息素更新系數(shù)和阻尼系數(shù)直接關(guān)系到全局搜索能力和算法收斂速度。在實(shí)際情況下，、、和不是獨(dú)立的，而是相互影響、綜合作用的。因此，通過嘗試各種組合模擬，并分析所得結(jié)果，最終設(shè)置參數(shù)為=1、=6、=05、=0.8。

3.2 基本蟻群算法與改進(jìn)蟻群算法的比較仿真

打磨機(jī)器人通常運(yùn)用于大型工件的打磨，并且在實(shí)時環(huán)境中隨時需要避開障礙物。因此,在抽象的山峰圖形中模擬機(jī)器人的環(huán)境進(jìn)行仿真實(shí)驗(yàn)時，采用2種蟻群算法對2組不同的初始點(diǎn)和目標(biāo)點(diǎn)進(jìn)行實(shí)驗(yàn)，并分析仿真結(jié)果。在實(shí)驗(yàn)1中設(shè)置初始點(diǎn)為(0 m，42 km，570 m)，目標(biāo)點(diǎn)為(100 km，39 km，600 m)；在實(shí)驗(yàn)2中設(shè)置起始點(diǎn)為(20 km，0 m，530 m)，目標(biāo)點(diǎn)為(33 km，100 km，730 m)。圖5—圖8所示為基本蟻群算法和改進(jìn)蟻群算法的路徑規(guī)劃水平。

圖5 實(shí)驗(yàn)1基本算法路徑

圖6 實(shí)驗(yàn)1改進(jìn)算法路徑

圖7 實(shí)驗(yàn)2基本算法路徑

圖8 實(shí)驗(yàn)2改進(jìn)算法路徑

可以直觀地看到:改進(jìn)的蟻群算法路徑更短，軌跡曲線更平滑。為對仿真結(jié)果作出更全面的分析，分析最佳路徑長度與迭代次數(shù)的關(guān)系，結(jié)果如圖9—圖12所示。

圖9 實(shí)驗(yàn)1基本算法最短路徑長度變化曲線 圖10 實(shí)驗(yàn)1改進(jìn)算法最短路徑長度變化曲線

圖11 實(shí)驗(yàn)2基本算法最短路徑長度變化曲線 圖12 實(shí)驗(yàn)2改進(jìn)算法最短路徑長度變化曲線

實(shí)驗(yàn)1中,基本蟻群算法在迭代26次時得到最佳路徑長度145 km，改進(jìn)蟻群算法在迭代10次時得到最佳路徑長度115 km，相比基本蟻群算法，改進(jìn)蟻群算法迭代次數(shù)減少了61.5%，路徑長度減少20.7%。實(shí)驗(yàn)2中，基本蟻群算法在迭代53次時得到最佳路徑長度128 km，改進(jìn)蟻群算法在迭代27次時得到最佳路徑長度118 km，改進(jìn)蟻群算法相比基本蟻群算法,迭代次數(shù)減少了49.1%，路徑長度減少7.8%。由上述數(shù)據(jù)可知，改進(jìn)后蟻群算法的最短路徑長度平均減少了14.3%，迭代次數(shù)平均減少了55.3%。

由2組實(shí)驗(yàn)結(jié)果可以看出，最佳路徑關(guān)系曲線迅速下降到某個最佳值后，迭代次數(shù)增加，最佳路徑長度不變，曲線呈水平趨勢。結(jié)果表明：改進(jìn)后的蟻群算法能夠在有效避開障礙物的同時縮短迂回路徑；與此同時，搜索策略的改進(jìn)有效提高了算法搜索能力。該方法可行、有效，具有重要的實(shí)際應(yīng)用意義，可用于打磨機(jī)器人的路徑規(guī)劃。

4 結(jié)論

為解決打磨機(jī)器人在復(fù)雜環(huán)境下的路徑規(guī)劃存在收斂速度慢、準(zhǔn)確性低等問題，運(yùn)用改進(jìn)蟻群算法進(jìn)行路徑規(guī)劃。根據(jù)打磨機(jī)器人的實(shí)際結(jié)構(gòu)建立了其運(yùn)動學(xué)連桿模型；對其進(jìn)行正逆運(yùn)動學(xué)分析并驗(yàn)證，改進(jìn)信息素更新規(guī)則，縮短信息素更新時間，從而有效提高效率；采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則，將輪盤賭方式確定節(jié)點(diǎn)作為新的自適應(yīng)計(jì)算方法，加快收斂速度進(jìn)而弱化啟發(fā)式信息對路徑選擇的影響；通過引入阻尼系數(shù)改進(jìn)啟發(fā)式信息函數(shù)。在MATLAB中進(jìn)行模擬實(shí)驗(yàn)，得出最佳參數(shù)組合，利用基本和改進(jìn)蟻群算法進(jìn)行仿真實(shí)驗(yàn)，得出不同運(yùn)動路徑。結(jié)果表明：與基本蟻群算法相比，利用所提出的改進(jìn)蟻群算法能夠得到更短更平滑的運(yùn)動路徑，最短路徑長度平均減少了14.3%，迭代次數(shù)平均減少了55.3%；結(jié)合打磨機(jī)器人刀具位置等特點(diǎn)，可以獲得一條路徑最短且平滑的規(guī)劃曲線，滿足打磨機(jī)器人實(shí)際應(yīng)用需求。