機(jī)械手三維操作空間建立與路徑規(guī)劃

姚 舜，付永忠，周 航

(江蘇大學(xué)機(jī)械工程學(xué)院，江蘇鎮(zhèn)江 212013)

0 引言

在以機(jī)械加工代替手工勞作的自動(dòng)化發(fā)展進(jìn)程中，機(jī)械手在上下料、安裝、搬運(yùn)、噴涂、焊接、采摘等領(lǐng)域充當(dāng)著舉足輕重地位。機(jī)械手根據(jù)接收到的指令信息，按照一定的評(píng)判標(biāo)準(zhǔn) (如時(shí)間最短，距離最短，能量最低等)規(guī)劃出一條符合標(biāo)準(zhǔn)的最優(yōu)路徑，從空間一點(diǎn)運(yùn)動(dòng)到空間另一點(diǎn)，從而完成整個(gè)指令操作。

機(jī)器人路徑規(guī)劃的研究可以分為二維平面移動(dòng)機(jī)器人的路徑規(guī)劃和三維機(jī)械手的操作路徑規(guī)劃［1-2］。對(duì)于二維平面移動(dòng)機(jī)器人的路徑規(guī)劃的技術(shù)研究已經(jīng)較為成熟。機(jī)械手空間三維路徑規(guī)劃需要解決的問題包括:1重構(gòu)三維空間環(huán)境模型。2建立機(jī)械手空間障礙干涉操作模型。3搜索滿足避障要求的路徑。4對(duì)路徑合理性進(jìn)行探討實(shí)現(xiàn)路徑優(yōu)化。5滿足動(dòng)力學(xué)約束以及其它約束問題。

在國(guó)外，Khatib提出的人工勢(shì)場(chǎng)法［3］雖然在機(jī)械手末端執(zhí)行器的局部路徑規(guī)劃算法方面已經(jīng)取得了應(yīng)用，但在全局避障路徑規(guī)劃上還需要深入研究。賈慶軒等采用A*算法［4］對(duì)機(jī)器人路徑進(jìn)行了規(guī)劃，雖然滿足了避障要求，但對(duì)路徑的合理性沒有進(jìn)行深入探討。伊華偉等采用蟻群算法［5］對(duì)機(jī)械手三維操作空間路徑完成了優(yōu)化，但沒有考慮機(jī)械手臂連桿與障礙物的干涉情況。

本文在采用柵格法建立機(jī)械手的環(huán)境模型以及垂直平面兩次投影法［6］建立機(jī)械手操作空間柵格模型的基礎(chǔ)上，提出了基于改進(jìn)遺傳算法的機(jī)械手三維操作空間路徑規(guī)劃方法。最后采用Matlab工具建立了機(jī)械手仿真系統(tǒng)，驗(yàn)證了算法的有效性，保證了機(jī)械臂連桿與障礙物不發(fā)生干涉，且相對(duì)于傳統(tǒng)路徑規(guī)劃算法，搜索效率，最優(yōu)路徑比等得到明顯提升。

1 問題描述及空間模型的建立

1.1 問題描述

因?yàn)闄C(jī)械手路徑規(guī)劃研究的是機(jī)械手末端的位置變化，不考慮機(jī)械手末端的姿態(tài)，因此可以將機(jī)械手的末端作為質(zhì)點(diǎn)處理。本文以Scara機(jī)械手為研究對(duì)象，機(jī)械手避障問題描述如圖1所示。圖中A為障礙物，B為機(jī)械手末端。末端B從起始點(diǎn)q0運(yùn)動(dòng)到目標(biāo)點(diǎn)q1，要求保證機(jī)械臂本體與障礙物不發(fā)生碰撞且使機(jī)械手末端點(diǎn)B從q0到q1運(yùn)動(dòng)路徑最短。與行走機(jī)器人路徑規(guī)劃相比，機(jī)械手路徑規(guī)劃必須避開機(jī)械臂與障礙物的干涉。

圖1 Scara機(jī)械手避障問題描述模型

機(jī)械手三維操作空間的路徑規(guī)劃流程如圖2所示。機(jī)械手獲取到外部環(huán)境信息，內(nèi)部建立起障礙物模型，并根據(jù)自身尺寸、關(guān)節(jié)角等信息建立起關(guān)節(jié)空間障礙模型，通過路徑搜索算法獲得空間點(diǎn)位，最后運(yùn)用機(jī)械手運(yùn)動(dòng)學(xué)逆解求解各關(guān)節(jié)角，機(jī)械手根據(jù)獲取指令從而完成相應(yīng)的動(dòng)作。本文主要研究的是機(jī)械手的三維操作空間路徑規(guī)劃，因此空間環(huán)境信息以一個(gè)標(biāo)準(zhǔn)的立方體塊作為障礙物。

圖2 機(jī)械手三維操作空間的路徑規(guī)劃流程圖

1.2 空間模型及操作模型的建立

本文運(yùn)用兩次投影的思想研究Scara機(jī)械手操作空間模型。Scara機(jī)械手操作空間模型V平面投影即為障礙物空間的V平面投影，H平面的投影如圖3所示。上臨界碰撞角θ2UC和θ2LC下臨界碰撞角之間的變化關(guān)系如式 (1)和式(2)所示:

點(diǎn)A(x，y)和點(diǎn)B(x，y1)為臨界碰撞點(diǎn)坐標(biāo)，a1、a2分別為兩桿的長(zhǎng)度，w1、w2分別兩桿的寬度，障礙物高度為z。關(guān)節(jié)坐標(biāo) (θ2UC，θ2LC)到空間坐標(biāo) (X，Y)的轉(zhuǎn)換公式如式 (3)和式 (4)所示:

圖3 Scara機(jī)械手臨界避障點(diǎn)H平面投影

垂直于H平面的障礙物空間體集合表示為DH，垂直于V平面的障礙物空間體集合表示為DV，DH和DV的集合表示如下:

則最終的障礙物操作空間即為H平面障礙物空間體構(gòu)成的集合與V平面障礙物空間體構(gòu)成的集合的交叉部分，集合DB可以表示為:

2 路徑規(guī)劃算法設(shè)計(jì)

針對(duì)在解決二維路徑規(guī)劃的問題上，遺傳算法在眾多的文章中提出，眾多學(xué)者嘗試將其不斷改進(jìn)更好得解決了路徑規(guī)劃的問題，被證明是一種有效的路徑規(guī)劃算法［7-9］。將這種算法應(yīng)用到三維空間，本文提出了柵格化操作空間模型，采用改進(jìn)遺傳算法對(duì)機(jī)械手三維操作空間進(jìn)行路徑規(guī)劃。三維路徑規(guī)劃的遺傳算法主要改進(jìn)方案有下面幾點(diǎn):采用三維編碼和實(shí)數(shù)編碼相結(jié)合的編碼方式，適應(yīng)度函數(shù)包括了路徑最短和避障的要求。

2.1 遺傳算法基本原理

1)遺傳算法的原理。

遺傳算法是模擬生物界自然選擇學(xué)說提出的，完全符合了“物競(jìng)天擇，適者生存”的觀點(diǎn)。自然選擇學(xué)說主要包括生物種群的遺傳、變異、生存斗爭(zhēng)和適者生存。遺傳算法將生物種群特征串聯(lián)起來并進(jìn)行相應(yīng)的編碼，將大自然的選擇作為適應(yīng)度函數(shù)，使用適應(yīng)度函數(shù)評(píng)估現(xiàn)有的種群個(gè)體，適應(yīng)度值大的個(gè)體將被保留，按照適應(yīng)度值提供的方向進(jìn)行交叉變異等操作從而產(chǎn)生新的后代個(gè)體，新的后代個(gè)體組成的種群再次被評(píng)估執(zhí)行下一步操作，周而復(fù)始，得出問題的最優(yōu)解。遺傳算法以初始種群為問題的解，以適應(yīng)度函數(shù)為導(dǎo)向，確定解搜索方向，避免了傳統(tǒng)優(yōu)化算法求導(dǎo)和不可行解的問題;同時(shí)它是一種全局搜索方法，能夠有效解決局部最優(yōu)的問題;概率選擇的方法增加了遺傳算法使用的靈活性，針對(duì)不同問題都可以靈活的建立相應(yīng)問題的解決模型。

2)遺傳算法的步驟。

遺傳算法的流程圖如圖4所示。觀察流程圖可以知道遺傳算法的主要步驟包括如下幾步［10］。

Step1:將種群特征進(jìn)行編碼，使實(shí)際問題的解X轉(zhuǎn)化為編碼解D的問題。

Step2:確定個(gè)體編碼特征參數(shù)x，y，z，…，確定適應(yīng)度函數(shù) fit(x，y，z，…)。

圖4 遺傳算法流程圖

Step3:確定遺傳策略，包括確定種群數(shù)量M，選擇、交叉、變異方法，交叉概率pc，遺傳概率pm等。

Step4:隨即產(chǎn)生由初始個(gè)體編碼構(gòu)成的初始種群p0。

Step5:將個(gè)體編碼特征參數(shù)代入適應(yīng)度函數(shù)fit(x，y，z，…)，計(jì)算適應(yīng)度函數(shù)值。

Step6:按照遺傳策略，進(jìn)行選擇、交叉和變異等操作，進(jìn)化出下一代新的個(gè)體組成的種群。

Step7:判斷是否所需求解問題的最終解或者中間解是否趨達(dá)到終止條件，若達(dá)到條件則結(jié)束當(dāng)前循環(huán)，輸出搜索結(jié)果，若沒有達(dá)到終止條件則跳到Step5，計(jì)算新一代個(gè)體的適應(yīng)度值，直到滿足終止條件。

2.2 環(huán)境模型及遺傳算法路徑編碼

機(jī)器人路徑規(guī)劃的研究都要基于環(huán)境模型和操作模型，對(duì)二維平面移動(dòng)機(jī)器人路徑規(guī)劃的研究一般都是以柵格化的方法建立柵格模型。將這種方法應(yīng)用到三維空間建立三維柵格模型如圖5所示。三維柵格模型由空間N×N個(gè)立方體素構(gòu)成。體素分為兩個(gè)狀態(tài)，障礙物體素 (如體素A)和自由體素 (如體素B)。對(duì)于環(huán)境模型，障礙物體素表達(dá)的是空間障礙物模型，對(duì)于操作空間而言障礙物體素除了表達(dá)空間障礙物模型外還表達(dá)機(jī)械臂與障礙物的干涉模型，即為上述障礙物操作空間集合的柵格化模型。每一個(gè)體素的位置由笛卡爾空間坐標(biāo)系來表達(dá)。對(duì)于Scara機(jī)械手而言，將機(jī)械手末端作為質(zhì)點(diǎn)處理，笛卡爾空間坐標(biāo)系中每一個(gè)體素的位置與機(jī)械手關(guān)節(jié)空間一一對(duì)應(yīng)。

圖5中，將環(huán)境柵格模型的左下角作為原點(diǎn)，建立如圖所示坐標(biāo)系，則每一個(gè)柵格的位置可以用坐標(biāo)表示，如左下角第一個(gè)柵格的坐標(biāo)即為，沿著軸方向的第二個(gè)柵格坐標(biāo)為，依次將柵格進(jìn)行編號(hào)。路徑編碼策略主要有實(shí)數(shù)編碼，浮點(diǎn)數(shù)編碼，二進(jìn)制編碼等，實(shí)數(shù)編碼能夠方便遺傳算子的交叉和變異等操作。同時(shí)，若將三維坐標(biāo)進(jìn)行編碼則能簡(jiǎn)單直觀表示出各編碼實(shí)際路徑，方便計(jì)算出路徑的長(zhǎng)度，評(píng)估路徑的可行性。綜合考慮以上兩點(diǎn)，針對(duì)空間三維路徑規(guī)劃的問題，本文提出實(shí)數(shù)編碼與三維坐標(biāo)編碼相結(jié)合的編碼策略。實(shí)數(shù)編碼柵格編號(hào)i與三維坐標(biāo)編碼柵格坐標(biāo) (xi，yi，zi)的映射關(guān)系如下:

上述運(yùn)算關(guān)系中，mod表示取余運(yùn)算，int表示取整運(yùn)算，N為實(shí)數(shù)編號(hào)柵格i的x軸坐標(biāo)，空間中表示了該柵格在第N個(gè)陣列層，求柵格i的y軸和z軸坐標(biāo)即為求該柵格所在陣列層的相應(yīng)位置坐標(biāo)。該映射關(guān)系的主要思想為正方體素的空間陣列，將正方體素作為基本單位，以正方體素構(gòu)成的正方體的一個(gè)邊角頂點(diǎn)為起始點(diǎn)，不斷以正方體素向空間三維的同一個(gè)方向延伸構(gòu)成由i個(gè)正方體素構(gòu)成的新正方體。

2.3 適應(yīng)度函數(shù)

由于機(jī)械手臂與障礙的干涉已經(jīng)在操作空間模型中考慮到了，所以在正確建立了機(jī)械手操作空間模型之后，機(jī)械手的三維操作空間的路徑規(guī)劃的適應(yīng)度函數(shù)與普通的二維平面行駛機(jī)器人路徑規(guī)劃適應(yīng)度函數(shù)所滿足的條件類似，即在保證機(jī)械手不與障礙物發(fā)生碰撞的基礎(chǔ)上使得總規(guī)劃路徑最短，對(duì)應(yīng)到柵格操作空間即要求各自由編碼柵格之間的連線不經(jīng)過障礙物編碼柵格的基礎(chǔ)上，使整條編碼柵格的總長(zhǎng)度最短。

1)任意一條路徑內(nèi)的編碼柵格 (用pi來表示)必須為自由編碼柵格即不能落在障礙物編碼柵格內(nèi)。將障礙物柵格編碼的集合表示為W，則路徑點(diǎn)編碼柵格不落在障礙物編碼柵格內(nèi)的適應(yīng)度函數(shù)可以表示為:

式中，pi表示操作路徑上第i個(gè)柵格點(diǎn)，n表示操作路徑中柵格點(diǎn)個(gè)數(shù)。公式表明，路徑中的柵格點(diǎn)落在障礙物柵格區(qū)域的適應(yīng)度函數(shù)為0，落在自由柵格區(qū)域的適應(yīng)度函數(shù)為1。

2)用pi和pi+1來表示路徑中相鄰的兩點(diǎn)，pipi+1表示相鄰兩點(diǎn)的連線，則連線不經(jīng)過障礙物柵格的適應(yīng)度函數(shù)可以表示為:

綜合以上兩點(diǎn)，可以得出機(jī)械手路徑規(guī)劃中，機(jī)械臂能夠有效避免碰撞的適應(yīng)度函數(shù)為:

對(duì)適應(yīng)度函數(shù)的要求除了避免碰撞之外還要求運(yùn)動(dòng)的路徑最短，即要求計(jì)算出每條路徑的長(zhǎng)度，相鄰兩點(diǎn)路徑pipi+1的長(zhǎng)度計(jì)算公式如下:

設(shè)整條操作路徑柵格點(diǎn)數(shù)為n，則整條路徑的總長(zhǎng)度為:

適應(yīng)度函數(shù)值越大基因編碼被保留下來的概率越大，因此可以得到最短路徑的適應(yīng)度函數(shù)為:

綜合考慮免碰撞以及路徑最短適應(yīng)度函數(shù)，可以得到用于機(jī)械手三維操作空間路徑規(guī)劃的最優(yōu)適應(yīng)度函數(shù)可以表示為:

公式中Cmax，的取值與操作空間的復(fù)雜程度有關(guān)，a為不可行操作路徑的懲罰系數(shù)。

2.4 遺傳算子

2.4.1 選擇算子

選擇操作是建立在適應(yīng)度值的基礎(chǔ)上的，適應(yīng)度值越大的個(gè)體被保留，作為父代進(jìn)行交叉變異等操作，從而產(chǎn)生下一代個(gè)體。選擇算子的種類較多，比較常用的選擇算子有輪盤賭選擇、隨機(jī)競(jìng)爭(zhēng)選擇、最佳保留選擇、無放回隨機(jī)選擇等。本文采用輪盤賭和精英保留策略相結(jié)合的方法進(jìn)行遺傳算法的選擇操作。輪盤賭和精英保留策略的思想是每個(gè)個(gè)體進(jìn)入下一代的概率等于它的適應(yīng)度值與整個(gè)種群中個(gè)體適應(yīng)度值和的比例，然后將當(dāng)前群體中適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整地復(fù)制到下一代群體中。

2.4.2 交叉算子

遺傳算法中，交叉操作應(yīng)用在選擇操作之后，通過染色體之間基因的互換從而產(chǎn)生新的基因序列，每一條新的基因序列組成的染色體即一種新的路徑方案。交叉操作是產(chǎn)生新的路徑方案的必要手段?；虻慕徊婊Q是隨機(jī)的，交叉操作主要包括單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、均勻交叉和算術(shù)交叉。交叉方法的選擇應(yīng)針對(duì)不同的編碼策略進(jìn)行選擇，針對(duì)前面提出的實(shí)數(shù)編碼策略，本文采用的是單基因片段的交叉即兩點(diǎn)交叉。各編碼路徑是按照實(shí)數(shù)編碼從小到大順序排列，通過預(yù)先設(shè)定基因片段交叉最低長(zhǎng)度，比較基因片段實(shí)數(shù)編碼的大小，來選擇可交叉的基因片段。基因片段長(zhǎng)度設(shè)定值越小，可交叉的基因片段種類越多，搜索情況越復(fù)雜，搜索效率越低。相反設(shè)定值越大基因種類越少，不能保證種群的多樣性，容易陷入局部最優(yōu)。本文根據(jù)與總路徑長(zhǎng)度的比值取值為0.1。

假設(shè)兩個(gè)待交叉的父代個(gè)體 (27，98，103，371，483，978，1 239，1 755，3 982)，父代個(gè)體 (81，99，271，372，771，1 560，2 040，3 961，4 092)，如圖 5所示，基因交叉片段長(zhǎng)度為6，按照順序排序進(jìn)行實(shí)數(shù)編碼，通過比較各實(shí)數(shù)編碼的大小，父代個(gè)體在103和1 755之間的基因片段與父代個(gè)體在99和2 040之間的基因片段存在可互換性。從三維坐標(biāo)編碼看，每個(gè)基因片段表示路徑的子路徑編碼，且這兩段子路徑可以相互替代，交換得到的染色體仍然是優(yōu)良的后代，與傳統(tǒng)遺傳算法的無序隨機(jī)交叉相比，采用實(shí)數(shù)順序編碼的編碼方式大大加快了算法的收斂速度。

圖6 兩父代個(gè)體基因片段交叉

2.4.3 變異算子

遺傳算法的變異過程是指在原始染色體上的基因位通過一些等位基因來替代，產(chǎn)生新的基因片段的過程。變異方法主要有基本位變異、均勻變異、邊界變異、非均勻變異和高斯近似變異等。變異算子是保證種群多樣性的必要手段，本文對(duì)實(shí)數(shù)編碼進(jìn)行非均勻變異操作，通過對(duì)染色體原有基因位做隨機(jī)的微小擾動(dòng)，每個(gè)基因位以相同的概率進(jìn)行變異操作后從而產(chǎn)生新的染色體，在空間路徑解中即產(chǎn)生了新的解決方案。變異操作的概率通常取值范圍為0.001～0.4，本文取值為0.01。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)結(jié)果

本文基于酷睿i7－6700處理器，內(nèi)存6 GB，Windows7旗艦版 X64位操作系統(tǒng)，采用 Visual Studio2013和 Matlab2014a 64 bit混合編程的方式驗(yàn)證了算法的有效性。

實(shí)驗(yàn)中各項(xiàng)參數(shù)設(shè)定如下:種群規(guī)模為M=80，交叉操作概率PC=0.75，變異操作的概率為Pm=0.01，最大的迭代次數(shù)為T=500，基于實(shí)數(shù)編碼的交叉基因片段長(zhǎng)度比例lC=0.1。Scara機(jī)械手的Matlab仿真模型及仿真結(jié)果如圖6所示，為起始點(diǎn)，為目標(biāo)點(diǎn)，機(jī)械手末端從沿著仿真結(jié)果的連續(xù)路徑點(diǎn)運(yùn)動(dòng)到，此路徑即為最優(yōu)路徑，既避免了機(jī)械臂與障礙物的碰撞，同時(shí)使得從起始點(diǎn)到目標(biāo)點(diǎn)路徑最優(yōu)。觀察圖7可以看到，本文提出的改進(jìn)遺傳算法在迭代到第240次左右趨向于收斂，即找到了最優(yōu)路徑，總長(zhǎng)度為11.2，單位為柵格。

3.2 算法對(duì)比

將本文算法與其它三維路徑規(guī)劃算法進(jìn)行性能參數(shù)比較，從表1中可以看出本文所提出的改進(jìn)遺傳算法在最優(yōu)路徑的選擇上比傳統(tǒng)的一些算法獲取的最優(yōu)路徑更短，在相同的實(shí)驗(yàn)條件的基礎(chǔ)上搜索效率得到提高。在重復(fù)性實(shí)驗(yàn)過程中所得到的最優(yōu)路徑比例明顯高于其它算法。由于目前取得較大進(jìn)展的人工勢(shì)場(chǎng)算法只適用于局部路徑最優(yōu)解，本文沒有與其進(jìn)行比較。

圖7 Scara機(jī)械手Matlab模型及路徑規(guī)劃仿真

圖8 本文遺傳算法迭代次數(shù)與路徑規(guī)劃長(zhǎng)度的變化關(guān)系

表1 本文遺傳算法與其它三維路徑規(guī)劃算法的性能比較

4 結(jié)束語

本文在分析和建立了機(jī)械手的三維操作空間模型的基礎(chǔ)上，提出了基于三維操作空間路徑規(guī)劃的改進(jìn)遺傳算法，保證了機(jī)械手臂在避開障礙物的基礎(chǔ)上，從起始點(diǎn)到目標(biāo)點(diǎn)運(yùn)動(dòng)路徑最短，并與傳統(tǒng)路徑規(guī)劃算法進(jìn)行了性能比較，在最優(yōu)路徑比例及搜索時(shí)間等性能上占據(jù)這相對(duì)優(yōu)勢(shì)。彌補(bǔ)了人工勢(shì)場(chǎng)局部最優(yōu)解，A*算法避障路徑規(guī)劃不合理，傳統(tǒng)遺傳算法搜索效率低，機(jī)械臂與障礙物發(fā)生干涉等問題。同時(shí)本文提出的將實(shí)數(shù)編碼與三維坐標(biāo)編碼相結(jié)合的編碼方式提高了搜索效率，簡(jiǎn)化了計(jì)算過程，同時(shí)使得路徑編碼更加直觀。