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

1引言

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

本文根據(jù)機(jī)器人時(shí)間最優(yōu)軌跡規(guī)劃的約束與要求，采用了一種新的軌跡規(guī)劃方法。該方法采用一個(gè)二次多項(xiàng)式加上一個(gè)三角余弦函數(shù)的樣條曲線函數(shù)來(lái)擬合機(jī)器人關(guān)節(jié)的軌跡，同時(shí)充分考慮了機(jī)器人關(guān)節(jié)空間上的位移、速度、加速度連續(xù)約束條件；并且使用了差分進(jìn)化算法(DE)和改進(jìn)的差分進(jìn)化算法(MDE)來(lái)求解時(shí)間最優(yōu)軌跡規(guī)劃的最優(yōu)解。

2問(wèn)題描述

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

2.1時(shí)間最優(yōu)軌跡規(guī)劃問(wèn)題的描述

在笛卡爾坐標(biāo)空間中，沿著機(jī)器人手部的軌跡從起點(diǎn)開(kāi)始到終點(diǎn)選取m個(gè)節(jié)點(diǎn)（包括起點(diǎn)和終點(diǎn)），規(guī)定ti為機(jī)器人手部到達(dá)節(jié)點(diǎn)i的時(shí)間，則相鄰兩個(gè)節(jié)點(diǎn)之間的時(shí)間間隔長(zhǎng)度:

（1）

機(jī)器人手部從起點(diǎn)到終點(diǎn)總的運(yùn)動(dòng)時(shí)間可表示為：

（2）

其中，表示問(wèn)題空間的解向量。

假設(shè)：

——關(guān)節(jié)j在節(jié)點(diǎn)i和節(jié)點(diǎn)i+1之間的位移曲線函數(shù)為關(guān)節(jié)序號(hào),為節(jié)點(diǎn)序號(hào)，m為機(jī)器人關(guān)節(jié)數(shù),n為軌跡上的節(jié)點(diǎn)數(shù)；

——關(guān)節(jié)j在區(qū)間上的運(yùn)動(dòng)速度；

——關(guān)節(jié)j在區(qū)間上的運(yùn)動(dòng)加速度；

——關(guān)節(jié)j在區(qū)間上的運(yùn)動(dòng)二階加速度。

再假設(shè)：

——關(guān)節(jié)的速度約束（最大允許角速度）。

這樣就可以得到基于時(shí)間最優(yōu)的機(jī)器人軌跡規(guī)劃的優(yōu)化問(wèn)題描述：

(3)

2.2關(guān)節(jié)軌跡的構(gòu)造函數(shù)

從機(jī)器人手部運(yùn)動(dòng)軌跡選取m個(gè)節(jié)點(diǎn)（包括起點(diǎn)和終點(diǎn)），它們所對(duì)應(yīng)的時(shí)刻依次記為。利用機(jī)器人逆運(yùn)動(dòng)學(xué)方法將每一個(gè)節(jié)點(diǎn)處機(jī)器人手部的位置與姿態(tài)逐個(gè)轉(zhuǎn)化為所對(duì)應(yīng)的關(guān)節(jié)坐標(biāo)（j為關(guān)節(jié)序號(hào)，i為節(jié)點(diǎn)序號(hào)）。在本節(jié)中，由于每次關(guān)節(jié)軌跡的構(gòu)造過(guò)程只涉及到一個(gè)關(guān)節(jié)，因此對(duì)關(guān)節(jié)數(shù)本節(jié)不做任何要求。這樣就可以簡(jiǎn)化為。為了擬合各節(jié)點(diǎn)處的關(guān)節(jié)坐標(biāo)且保證機(jī)器人手部運(yùn)動(dòng)連續(xù)平整，本文采用如下樣條函數(shù)進(jìn)行軌跡擬合：

(4)

其中

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

2.3約束條件

機(jī)器人時(shí)間最優(yōu)軌跡優(yōu)化問(wèn)題不僅要受到笛卡爾空間路徑的約束，同時(shí)每個(gè)關(guān)節(jié)處的速度、加速度也要受到約束，所求出的最優(yōu)時(shí)間間隔必須受到約束條件式的約束。約束如下：

(5)

式中分別表示機(jī)械手第j個(gè)關(guān)節(jié)對(duì)應(yīng)的速度、加速度的約束值。且,L為軌跡的段數(shù)。

3軌跡規(guī)劃的優(yōu)化算法

本文使用和這兩種算法為6自由度機(jī)器人（PUMA560機(jī)器人）獲得時(shí)間最優(yōu)的軌跡規(guī)劃，使用前提是假設(shè)由軌跡規(guī)劃器產(chǎn)生的軌跡是可行的，而且是由機(jī)器人操作空間中由一系列的關(guān)鍵點(diǎn)組成的。

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

差分進(jìn)化算法在優(yōu)化迭代過(guò)程中，采用NP個(gè)n維向量

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

差分進(jìn)化算法的基本原理是將種群中任意兩個(gè)個(gè)體的差分向量加權(quán)后差分進(jìn)化算法的基本原理是將種群中任意兩個(gè)個(gè)體的差分向量加權(quán)后根據(jù)一定的規(guī)則加到第三個(gè)個(gè)體上從而獲得新個(gè)體，如果新生成的個(gè)體的目標(biāo)函數(shù)值比種群中預(yù)先確定的一個(gè)個(gè)體的目標(biāo)函數(shù)值小，則用新生成個(gè)體替代原種群與之相比較的個(gè)體，否則原個(gè)體保存到下一代。在實(shí)際問(wèn)題中，這個(gè)基本原理可以適當(dāng)?shù)剡M(jìn)行擴(kuò)展。例如，可以將不止一個(gè)差分向量加權(quán)后加到第三個(gè)向

量上以獲取新個(gè)體，也可引入當(dāng)前種群中的最優(yōu)個(gè)體以加速搜索等。在比較新舊個(gè)體目標(biāo)函數(shù)值之前，可以對(duì)新個(gè)體與舊個(gè)體中某些位置上的解進(jìn)行等位交換，類似于遺傳算法中的交叉操作，這可以提高差分進(jìn)化算法的搜索能力。

差分進(jìn)化算法的基本原理是將種群中任意兩個(gè)個(gè)體的差分向量加權(quán)后根據(jù)一定的規(guī)則加到第三個(gè)個(gè)體上從而獲得新個(gè)體，如果新生成的個(gè)體的目標(biāo)函數(shù)值比種群中預(yù)先確定的一個(gè)個(gè)體的目標(biāo)函數(shù)值小，則用新生成個(gè)體替代原種群與之相比較的個(gè)體，否則原個(gè)體保存到下一代。在實(shí)際問(wèn)題中，這個(gè)基本原理可以適當(dāng)?shù)剡M(jìn)行擴(kuò)展。例如，可以將不止一個(gè)差分向量加權(quán)后加到第三個(gè)向量上以獲取新個(gè)體，也可引入當(dāng)前種群中的最優(yōu)個(gè)體以加速搜索等。在比較新舊個(gè)體目標(biāo)函數(shù)值之前，可以對(duì)新個(gè)體與舊個(gè)體中某些位置上的解進(jìn)行等位交換，類似于遺傳算法中的交叉操作，這可以提高差分進(jìn)化算法的搜索能力。

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

方法DE/rand-to-best/1將當(dāng)前種群的最優(yōu)個(gè)體置于差分向量中，即

(6)

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

(7)

差分進(jìn)化算法的流程圖如圖1所示。

圖1差分進(jìn)化算法流程圖

3.2改進(jìn)的差分進(jìn)化算法

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

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

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

(8)

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

(9)

其中,我們采用冪平均計(jì)算，即：

(10)

我們采用式(10)的一般式，Sf表示在當(dāng)前策略下生成的子代個(gè)體，成功保留至下一代個(gè)體所使用的F值集合,表示集合大小。之所以采用上述方式進(jìn)行F值更新，是因?yàn)檩^大的F值能夠增加種群分布性，避免種群陷入局部最優(yōu)，因此我們采用增大方差值的方式，擴(kuò)大F的變動(dòng)區(qū)間，避免F值過(guò)度集中，從而獲得更適合優(yōu)化問(wèn)題的F值。對(duì)于采用冪平均以增大值，從而對(duì)目標(biāo)向量進(jìn)行更大的擾動(dòng)。

改進(jìn)的差分進(jìn)化算法的流程圖如圖2所示。

圖2改進(jìn)的差分進(jìn)化算法流程圖

4仿真結(jié)果

本文中通過(guò)對(duì)PUMA機(jī)器人的仿真實(shí)驗(yàn)來(lái)說(shuō)明本文算法的性能。軌跡規(guī)劃的初始條件設(shè)為各關(guān)節(jié)在第一個(gè)節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)處角速度為0。

在空間中任意找到10個(gè)節(jié)點(diǎn)，它們的位置與姿態(tài)用的齊次坐標(biāo)變換表示，1-10節(jié)點(diǎn)坐標(biāo)依次如下：

本文差分進(jìn)化算法選用DE/rand-to-best/1方法，其參數(shù)為：

種群規(guī)模：NP=200；

差分因子:F=1.2；

交叉概率：CR=0.1；

最大種群代數(shù)：Gmax=4000。

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

種群規(guī)模：NP=200；

差分因子:F=0.5；

交叉概率：CR=0.5；

最大種群代數(shù)：Gmax=4000。

由DE算法和MDE算法得到的到關(guān)節(jié)位置、速度、加速度的輪廓圖分別如圖3和圖4所示，圖5為應(yīng)用兩種算法的收斂曲線，通過(guò)這些圖形的觀察發(fā)現(xiàn)所有最優(yōu)解完全滿足給定的約束條件。

圖3由DE所得到的各關(guān)節(jié)優(yōu)化運(yùn)動(dòng)曲線

圖4由MDE所得到的各關(guān)節(jié)優(yōu)化運(yùn)動(dòng)曲線

圖5應(yīng)用DE和MDE的兩種優(yōu)化結(jié)果曲線

通過(guò)觀察仿真圖5可知，簡(jiǎn)單差分進(jìn)化算法在迭代4000后找到近似最優(yōu)解16.38；而改進(jìn)的差分進(jìn)化算法在迭代到300步左右后即找到了最優(yōu)解14.56。

5結(jié)論與展望

5.1結(jié)論

本文采用一個(gè)由二次多項(xiàng)式與三角余弦函數(shù)的組合形式構(gòu)成的樣條曲線函數(shù)來(lái)擬合機(jī)器人各關(guān)節(jié)的軌跡，使得最終求解的關(guān)節(jié)軌跡滿足關(guān)節(jié)位移、速度以及加速度的連續(xù)，以此為基礎(chǔ)確定了用于時(shí)間最優(yōu)軌跡規(guī)劃的優(yōu)化函數(shù)。

本文使用了GA和DE來(lái)解決非線性約束的優(yōu)化問(wèn)題，它能提高搜索效率，找到全局最優(yōu)解。

對(duì)PUMA560機(jī)器人的仿真結(jié)果表明了兩種算法都運(yùn)行良好，而且MDE能夠更快地搜索到更高質(zhì)量的解。證明了改進(jìn)的差分進(jìn)化算法是一種性能優(yōu)良的，具有高效性、并行性、魯棒性等優(yōu)點(diǎn)的優(yōu)化方法。

5.2展望

機(jī)器人軌跡規(guī)劃的研究作為機(jī)器人學(xué)的一個(gè)重要分支，仍有許多問(wèn)題亟待解決，作者認(rèn)為還可在以下問(wèn)題進(jìn)行進(jìn)一步的研究。

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

（2）在本文中，它也沒(méi)有考慮機(jī)器人動(dòng)力學(xué)的影響。在今后的研究中，可以將機(jī)器人動(dòng)力學(xué)問(wèn)題引入到軌跡規(guī)劃當(dāng)中，從而使優(yōu)化結(jié)果更接近于現(xiàn)實(shí)。

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