摘要：提出了一種工業機器人的時間最優軌跡規劃方法。將機器人的軌跡視為由機器人關節空間中一系列的關鍵點構成，關鍵點的兩點之間將采用二次多項式加三角余弦函數構造機器人的關節軌跡方程。使其既滿足位移、速度、加速度連續的約束條件。采用差分進化算法（DE)和改進的差分進化算法（MDE)引入到機器人時間最優軌跡規劃中來，使得規劃出的軌跡不僅可以保證關節運動的位移、速度、加速度連續，而且在這些運動學約束條件下使得機器人手部沿規定的軌跡運動的時間最短。六自由度機器人（PUMA機器人）的仿真結果顯示兩種算法運行良好，然而改進的差分進化算法比簡單差分進化算法收斂速度更快，解的質量更好。

1引言

最優軌跡規劃（OptimalTrajectoryPlanning,OTP）是工業機器人最優控制問題之一規劃的任務是根據給定的路徑點規劃出通過這些點并滿足邊界約束條件的光滑的最優運動軌跡。時間最優是機器人OTP問題中的很重要的優化指標。機器人時間最優軌跡規劃就是指以機器人手部完成指定運動所消耗時間最短為優化目標而進行的軌跡規劃。時間最優的目的是為了最大化操作速度從而得到最小化機器人動作時間，這樣的研究可參見文獻[1]。對于有約束的非線性優化問題，已經開發出許多有效算法，如:罰函數法[2]、廣義既約梯度法[3]（GRG）、逐次二次規劃法[4]（SQP）等，但是這些方法只能得到與初始點有關的局部最優解，不能保證全局最優解。在某些復雜情況下，優化問題甚至表現為不連續、不可微性。而高效率的直接搜索法是一種很有潛力的方法，在解的允許空間內直接利用優化問題的一些點值進行搜索而不管其解析性質如何，而且求出的極值往往是全局最優點。

本文根據機器人時間最優軌跡規劃的約束與要求，采用了一種新的軌跡規劃方法。該方法采用一個二次多項式加上一個三角余弦函數的樣條曲線函數來擬合機器人關節的軌跡，同時充分考慮了機器人關節空間上的位移、速度、加速度連續約束條件；并且使用了差分進化算法(DE)和改進的差分進化算法(MDE)來求解時間最優軌跡規劃的最優解。

2問題描述

所謂的機器人規劃,根據機器人自身的任務要求,完成任務得到解決方案的過程。任務,是一個更廣泛的概念,機器人完成的可以是一個特定的任務,也可能是一個動作,如手部的預定的運動或關節運動以實現預定的運動軌跡規劃，因此軌跡規劃是機械手按照機器人預先設定的動作來完成關節的位移，速度和時間t的運動。機器人軌跡規劃起源于1960年代末?？梢栽谠陉P節空間進行也可以再笛卡爾空間進行軌跡規劃。無論是在關節空間還是在笛卡兒空間必須滿足連續性和平滑性。本文主要討論的是連續路徑無障礙的軌跡規劃。

2.1時間最優軌跡規劃問題的描述

在笛卡爾坐標空間中，沿著機器人手部的軌跡從起點開始到終點選取m個節點（包括起點和終點），規定ti為機器人手部到達節點i的時間，則相鄰兩個節點之間的時間間隔長度:

（1）

機器人手部從起點到終點總的運動時間可表示為：

（2）

其中，表示問題空間的解向量。

假設：

——關節j在節點i和節點i+1之間的位移曲線函數為關節序號,為節點序號，m為機器人關節數,n為軌跡上的節點數；

——關節j在區間上的運動速度ï¼›

——關節j在區間上的運動加速度ï¼›

——關節j在區間上的運動二階加速度。

再假設：

——關節的速度約束（最大允許角速度）。

這樣就可以得到基于時間最優的機器人軌跡規劃的優化問題描述：

(3)

2.2關節軌跡的構造函數

從機器人手部運動軌跡選取m個節點（包括起點和終點），它們所對應的時刻依次記為。利用機器人逆運動學方法將每一個節點處機器人手部的位置與姿態逐個轉化為所對應的關節坐標（j為關節序號，i為節點序號）。在本節中，由于每次關節軌跡的構造過程只涉及到一個關節，因此對關節數本節不做任何要求。這樣就可以簡化為。為了擬合各節點處的關節坐標且保證機器人手部運動連續平整，本文采用如下樣條函數進行軌跡擬合：

(4)

其中

從軌跡的起點到終點共有m個節點，將軌跡分成m-1段，因此需要構造m-1個樣條函數，共出現了4(m-1)個未知數。每個節點的位移以及起點和終點的速度是已知的，這樣得到m+2個初始條件；中間m-2個節點的位移、速度與加速度是連續的，共3(m-2)個連續性條件。初始條件與連續性條件總數為4(m-1)，與未知系數數量相同，因此這些系數可以被唯一確定出來。

2.3約束條件

機器人時間最優軌跡優化問題不僅要受到笛卡爾空間路徑的約束，同時每個關節處的速度、加速度也要受到約束，所求出的最優時間間隔必須受到約束條件式的約束。約束如下：

(5)

式中分別表示機械手第j個關節對應的速度、加速度的約束值。且,L為軌跡的段數。

3軌跡規劃的優化算法

本文使用和這兩種算法為6自由度機器人（PUMA560機器人）獲得時間最優的軌跡規劃，使用前提是假設由軌跡規劃器產生的軌跡是可行的，而且是由機器人操作空間中由一系列的關鍵點組成的。

差分進化算法是一種采用浮點矢量編碼并在連續空間中進行隨機搜索的優化方法，由RainerStorn和KennethPrice于1995年最早提出。經過最近幾年的發展，差分進化算法已經被證明是一種有效的實值、多目標、全局優化方法。除去具有較好的收斂性外，差分進化算法非常易于理解與執行，它只含有不多的幾個控制參數，并且在整個迭代過程中，這些參數的值保持不變。

差分進化算法在優化迭代過程中，采用NP個n維向量

作為每一代G（每一次迭代）的一個種群。其中NP稱為種群規模，在迭代過程中大小不變。初始種群隨機生成，并盡可能均勻地覆蓋整個解空間。

差分進化算法的基本原理是將種群中任意兩個個體的差分向量加權后差分進化算法的基本原理是將種群中任意兩個個體的差分向量加權后根據一定的規則加到第三個個體上從而獲得新個體，如果新生成的個體的目標函數值比種群中預先確定的一個個體的目標函數值小，則用新生成個體替代原種群與之相比較的個體，否則原個體保存到下一代。在實際問題中，這個基本原理可以適當地進行擴展。例如，可以將不止一個差分向量加權后加到第三個向

量上以獲取新個體，也可引入當前種群中的最優個體以加速搜索等。在比較新舊個體目標函數值之前，可以對新個體與舊個體中某些位置上的解進行等位交換，類似于遺傳算法中的交叉操作，這可以提高差分進化算法的搜索能力。

差分進化算法的基本原理是將種群中任意兩個個體的差分向量加權后根據一定的規則加到第三個個體上從而獲得新個體，如果新生成的個體的目標函數值比種群中預先確定的一個個體的目標函數值小，則用新生成個體替代原種群與之相比較的個體，否則原個體保存到下一代。在實際問題中，這個基本原理可以適當地進行擴展。例如，可以將不止一個差分向量加權后加到第三個向量上以獲取新個體，也可引入當前種群中的最優個體以加速搜索等。在比較新舊個體目標函數值之前，可以對新個體與舊個體中某些位置上的解進行等位交換，類似于遺傳算法中的交叉操作，這可以提高差分進化算法的搜索能力。

3.1DE/rand-to-best/1方法

方法DE/rand-to-best/1將當前種群的最優個體置于差分向量中，即

(6)

此種方法既利用了當前種群的最優個體的信息，加速了搜索的速度，同時又降低了優化陷入局部最優解的危險。式（6）中，λ控制算法的“貪婪”程度。為了減少控制參數的數量，一般取λ=F，則式（7）可改寫為

(7)

差分進化算法的流程圖如圖1所示。

圖1差分進化算法流程圖

3.2改進的差分進化算法

大量研究表明，DE的性能同樣依賴于控制參數，主要表現在兩方面：（1)DE的收斂性及收斂速度依賴于進化步長F和交叉概率CR；（2)DE擁有獨特的變異機制，若差分進化種群失去多樣性（F或CR選擇不合適），也就是說種群間無差異，DE的搜索將會完全停滯或終止。然而，控制參數的選擇因具體問題而異，合理地設置控制參數需大量的先驗知識，人類能力很難完成，若采用算法尋找，則需耗費大量計算開銷，因此，如何自適應地選擇DE的控制參數尤為重要。

對于DE中的三個參數：CR、F和NP，我們僅對交叉概率CR和進化步長F進行自適應調整。CR和F是兩個極為敏感的參數，前者控制試驗向量的組成，后者控制進化步長。我們根據進化種群中各策略下成功保留的個體信息，自適應控制參數值，在算法運行過程中，并根據CR和F的特性，給出不同的更新方式。

對于交叉概率CR，定義表示父代個體i采用策略a生成子代時所使用的CR值，我們采用均值為，方差為0.1的高斯分布隨機數生成。均值的初始值由使用者定義，針對策略池各元素，采用如下方式進行更新：

(8)

其中，n為[0,1]之間的常數，我們采用算術平均值，表示在當前策略下生成的子代個體，成功保留至下一代的個體所使用的CR值集合。根據優秀的控制參數產生的子代存活概率大的原則，保留成功個體的參數至下一代，并對當前CR值的分布中心進行微調，逐步優化CR值。對于進化步長F，定義表示父代個體i采用策略a生成子代時所使用的F值，相比CR，采用高斯分布隨機數生成F,采用與相同的的方式更新：

(9)

其中,我們采用冪平均計算，即：

(10)

我們采用式(10)的一般式，Sf表示在當前策略下生成的子代個體，成功保留至下一代個體所使用的F值集合,表示集合大小。之所以采用上述方式進行F值更新，是因為較大的F值能夠增加種群分布性，避免種群陷入局部最優，因此我們采用增大方差值的方式，擴大F的變動區間，避免F值過度集中，從而獲得更適合優化問題的F值。對于采用冪平均以增大值，從而對目標向量進行更大的擾動。

改進的差分進化算法的流程圖如圖2所示。

圖2改進的差分進化算法流程圖

4仿真結果

本文中通過對PUMA機器人的仿真實驗來說明本文算法的性能。軌跡規劃的初始條件設為各關節在第一個節點與最后一個節點處角速度為0。

在空間中任意找到10個節點，它們的位置與姿態用的齊次坐標變換表示，1-10節點坐標依次如下：

本文差分進化算法選用DE/rand-to-best/1方法，其參數為：

種群規模：NP=200；

差分因子:F=1.2；

交叉概率：CR=0.1；

最大種群代數：Gmax=4000。

改進的差分進化算法中的變異算子與DE/rand-to-best/1方法中的相同，其參數如下：

種群規模：NP=200；

差分因子:F=0.5；

交叉概率：CR=0.5；

最大種群代數：Gmax=4000。

由DE算法和MDE算法得到的到關節位置、速度、加速度的輪廓圖分別如圖3和圖4所示，圖5為應用兩種算法的收斂曲線，通過這些圖形的觀察發現所有最優解完全滿足給定的約束條件。

圖3由DE所得到的各關節優化運動曲線

圖4由MDE所得到的各關節優化運動曲線

圖5應用DE和MDE的兩種優化結果曲線

通過觀察仿真圖5可知，簡單差分進化算法在迭代4000后找到近似最優解16.38；而改進的差分進化算法在迭代到300步左右后即找到了最優解14.56。

5結論與展望

5.1結論

本文采用一個由二次多項式與三角余弦函數的組合形式構成的樣條曲線函數來擬合機器人各關節的軌跡，使得最終求解的關節軌跡滿足關節位移、速度以及加速度的連續，以此為基礎確定了用于時間最優軌跡規劃的優化函數。

本文使用了GA和DE來解決非線性約束的優化問題，它能提高搜索效率，找到全局最優解。

對PUMA560機器人的仿真結果表明了兩種算法都運行良好，而且MDE能夠更快地搜索到更高質量的解。證明了改進的差分進化算法是一種性能優良的，具有高效性、并行性、魯棒性等優點的優化方法。

5.2展望

機器人軌跡規劃的研究作為機器人學的一個重要分支，仍有許多問題亟待解決，作者認為還可在以下問題進行進一步的研究。

（1）作為工具的優化算法，雖然本文所采用的改進的差分進化算法相對于傳統的差分進化算法以及遺傳算法有了很大的進步，但是正如進化算法本身所描述的事物一樣，算法本身需不斷地改進與進化著。所以會有改善的理論和應用的空間。

（2）在本文中，它也沒有考慮機器人動力學的影響。在今后的研究中，可以將機器人動力學問題引入到軌跡規劃當中，從而使優化結果更接近于現實。

（3）本文只涉及的時間最優軌跡規劃。除此之外，還可基于能量最小原則進行機器人軌跡規劃，或者同時考慮時間最優與能量最小原則，這些都需要進一步的探討。