姚 舜，付永忠，周 航

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

0 引言

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

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

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

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

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

1.1 問題描述

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

圖1 Scara機械手避障問題描述模型

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

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

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

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

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

圖3 Scara機械手臨界避障點H平面投影

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

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

2 路徑規(guī)劃算法設計

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

2.1 遺傳算法基本原理

1)遺傳算法的原理。

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

2)遺傳算法的步驟。

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

Step1:將種群特征進行編碼，使實際問題的解X轉化為編碼解D的問題。

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

圖4 遺傳算法流程圖

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

Step4:隨即產生由初始個體編碼構成的初始種群p0。

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

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

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

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

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

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

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

2.3 適應度函數(shù)

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

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

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

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

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

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

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

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

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

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

2.4 遺傳算子

2.4.1 選擇算子

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

2.4.2 交叉算子

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

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

圖6 兩父代個體基因片段交叉

2.4.3 變異算子

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

3 實驗結果及分析

3.1 實驗結果

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

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

3.2 算法對比

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

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

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

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

4 結束語

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