基于新型煙花算法的機器人時間最優軌跡規劃

陶 慶,王文杰,王曉華,張 蕾

(西安工程大學 電子信息學院,陜西 西安 710048)

0 引 言

軌跡規劃是機器人運動控制的基礎,隨著智能算法的出現,軌跡規劃算法也在向智能化發展,高性能的軌跡規劃算法可以使機器人運行更平穩,控制精度更高,工作效率更高,使用壽命更長,因此對軌跡規劃算法的研究一直是機器人領域的研究熱點。

三次多項式插值軌跡規劃[1]計算簡單,應用廣泛,但是軌跡規劃過程中可能會產生機械振動,增加關節磨損,影響控制精度。為得到更平滑的運動軌跡,采用提高多項式的插值階次或者進行分段插值的方法,文獻[2]提出了采用 3-5-3 樣條函數法對機器人軌跡進行規劃,使運動軌跡更加平穩,但是以上方法沒有考慮到插值時間問題。機器人時間最優軌跡規劃就是要求機器人在多約束條件下,能夠以最短的時間完成指定的運動。基于多項式插值的軌跡規劃,具有階次高、沒有凸包性質等特點,很難用傳統方法優化[3]。使用智能算法實現軌跡規劃時間最優成為研究重點,常用的智能算法有人工魚群算法[4]、差分進化算法[5]、遺傳算法[6-8]、粒子群算法[9]、凸優化算法[10]，但是這些算法需要的迭代次數較多,參數調整復雜,性能方面有待提高。

煙花算法(fireworks algorithm,FWA)是TAN等在2010 年提出的一種新穎的智能優化算法[11],具有所需參數少,求解性能強等特點。學者們在其基礎上進行深入研究并將其應用到各個領域。文獻[12]提出增強煙花算法(EFWA),在煙花算法基礎上增加最小爆炸半徑檢測策略,并對高斯變異、映射規則、選擇策略進行改進,降低了算法運行時間。文獻[13]提出自適應煙花算法(AFWA),無需人為設定最小半徑,而是最優煙花自動調整爆炸半徑,使算法更加智能。文獻[14]提出反向煙花算法,在增強煙花算法中引入反向學習算子,提高了算法求解精度。文獻[15]提出精英導向煙花算法(ELFWA),增加了煙花之間的信息交流,較差火花接受隨機選擇的精英煙花的指導,提高了搜索效率。文獻[16] 提出了一種簡化的混合煙花算法(SHFWA),通過改變煙花爆炸產生火花的方式,從而化簡算法過程,使算法性能提高。但是這些算法依然存在收斂速度較慢等缺陷。

在軌跡規劃中,XIA等提出用分段連續函數對軌跡規劃過程中的速度和加速度進行限制[17],達到縮短運行時間的目的,但是其運算復雜,計算量較大。HE等采用免疫算法對機器人時間和能量進行同時優化[18],并取得了很好的效果,但是同時優化多個目標,可能會導致時間不是最優的情況。CHEN等采用和聲搜索算法對五次B樣條曲線進行優化[19],得到了平滑且時間最優的軌跡,而對比分段多項式插值函數,軌跡還不夠平滑。

針對以上方法的問題,本文提出了混沌自適應煙花算法,以自適應煙花算法為基礎,將混沌算法與其相結合,加速收斂過程,提高求解精度。通過8個不同的測試函數驗證了算法的正確性。以UR機器人為研究對象,以在速度約束下插值時間為優化目標,采用混沌自適應煙花算法確定出機器人運動時間最短的軌跡,在滿足位置、速度、加速度等一系列約束的情況下,實現速度約束下的時間最優3-5-3多項式插值軌跡規劃,解決了時間不確定性問題,證明了算法的正確性。

1 多項式插值函數的構造

為了完成機器人在關節空間中的指定運動,利用已知的笛卡爾坐標系下的起始點、抬起點、下降點和終點的位姿,通過運動學逆解求解出關節角度,從而得到多項式插值函數,使機器人末端經過要求路徑點,滿足運動軌跡要求。本文采用3-5-3多項式插值方法,其通式如下所示:

(1)

式中:aimn為第i個關節插值軌跡的第m段(m=1,2,3)多項式軌跡函數的第n個未知系數；him(t)為第i個關節的第m段多項式軌跡函數；t為時間變量。

在軌跡規劃過程中,需要滿足起始點θi1、抬起點θi2、下降點θi3、終點θi4的位置、速度和加速度約束,其約束條件是：4個插值點的位置(已知),起始點的速度與加速度為0,終點的速度與加速度也為0,抬起點的速度和加速度連續,下降點的速度和加速度也連續,通過以上14個約束條件,可以根據式(2)～(4)推導出未知系數aimn。其中式(2)為關于第i個關節的三段插值時間ti1、ti2、ti3的矩陣，式(3)為第i個關節角的位置矩陣，式(4)為系數矩陣。

(2)

式中:A、B、C、D、E、F、G、H的具體內容見文獻[3]。

θ=[0 0 0 0 0 0θi30 0θi00 0θi2θi1]T

(3)

a=T-1·θ=[a1a2a3]T

(4)

式中:a1=[ai13ai12ai11ai10];

a2=[ai25ai24ai23ai22ai21ai20];

a3=[ai33ai32ai31ai30]

2 基于CAFWA的時間最優求解

2.1 自適應煙花算法

煙花算法的靈感來源于煙花在燃放過程中會爆炸并且在一定范圍內產生火花的行為,是一種群體智能優化算法。煙花算法的步驟大致如下:

初始化即在求解空間產生N個位置任意的煙花,然后爆炸算子在爆炸范圍Ai中產生Si個新的火花,其中Ai和Si分別為

(5)

(6)

為避免火花數量不均影響性能,將Si改為

(7)

式中:r(·)為取整函數;a和b為給定常數。

為增加火花多樣性,對火花采取位移操作和高斯變異:

(8)

(9)

為避免火花位置越過邊界,采用映射規則:

(10)

選擇策略采用精英保留策略,直接保留適應度最好的火花,采用輪盤賭的方式篩選剩余火花,每個火花被選中的概率為

(11)

式中:R(xi)為個體xi與其他火花的距離之和;K為產生的火花總數。

但是煙花算法具有一定缺陷,若優化函數的最優解位于原點,煙花算法存在“早熟”現象。若優化函數的最優解距原點位置較遠,煙花算法性能較差，煙花算法耗時嚴重。自適應煙花算法是對煙花算法的改進。自適應煙花算法使爆炸半徑具有自動調節的能力,對高斯變異,映射規則和選擇策略都進行了改進,提高了算法的性能。

選擇一個條件滿足自適應半徑的計算:① 適應度值比這一代的煙花要差；② 到最優個體的距離是滿足① 中的個體中最短的個體,將這個個體與最優煙花的距離作為下一次的爆炸半徑。初始化半徑為整個求解范圍。

新型高斯變異算子:高斯火花的計算公式為

(12)

新型映射規則:采用隨機映射規則,計算公式為

(13)

式中：U(0,1)為[0,1]區間上的均勻分布隨機數。

精英-隨機選擇策略:首先選擇出種群中適應度最優的個體,然后對其余煙花的選擇采用隨機策略,降低其運算時間。

2.2 混沌自適應煙花算法

混沌搜索的遍歷性、隨機性有利于智能算法擺脫局部最優值的束縛[20]。很多模型都能產生混沌序列,本文采用邏輯自映射函數產生混沌序列,其數學表達式為

yi+1=1-2×(yi)2，yi∈(-1,1)

(14)

當yi≠0和yi≠0.5時就會有混沌發生。

混沌算法首先將解空間中煙花個體xi的每一維的位置映射到混沌區域(-1,1),映射規則為

(15)

式中：ai為混沌搜索范圍的下邊界；bi為混沌搜索范圍的上邊界。

然后對式(15)中映射產生的值,按照式(14)進行迭代,生成混沌序列。最后混沌序列逆映射,將混沌區域的值逆映射到解空間。逆映射規則為

(16)

CAFWA的步驟：

1) 初始化算法基本參數,包括煙花種群數、爆炸火花數、高斯火花數、優化范圍等。

2) 根據混沌算法對隨機產生的N個煙花進行優化,選擇其中最好的N個煙花作為初始煙花。

3) 計算初始煙花的適應度。

4) 計算最優煙花除外的各個煙花的爆炸半徑及所有煙花的爆炸數目。

5) 產生成高斯火花。

6) 計算所有火花的適應度值。

7) 計算最優煙花半徑。

8) 選擇下一代煙花。

9) 用混沌算法對產生的煙花進行優化,更新種群。

10) 如果未達到最大迭代次數,則執行步驟4)。

11) 輸出最優煙花及其適應度值。

2.3 算法測試

為測試CAFWA算法的性能,選擇煙花算法(FWA)和自適應煙花算法(AFWA)進行對比,測試函數如表1所示,其中f1和f2為只有一個極值點的單峰函數,f3～f5為擁有多個極值點的多峰函數,f6～f8為多峰函數且最優解的位置不在原點附近,能夠比較全面的評估算法的性能。

表 1 測試函數Tab.1 Test functions

測試函數時各算法的參數統一,其中最大迭代次數為10 000,煙花數目為5,火花數目為50,測試維度為10。每種算法獨立重復運行50次,把最佳適應度值對應的平均值、方差和運行時間作為算法性能的評價標準,測試結果如表2所示。

根據表2可以看出，在求解前5個函數時煙花算法具有很好的效果,這是由于煙花算法不夠完善造成的,而且其算法耗時嚴重。而AFWA和CAFWA相比,CAFWA對單峰函數求解結果相差不大,但是對于多峰函數具有更高的求解精度,而且時間和AFWA相差不多且遠遠小于FWA算法。

2.4 適應度函數的選擇

若選擇未知系數aimn為待優化的目標函數,則混沌自適應煙花算法優化的維數為14,增加了尋優的困難程度。以第i個關節的三段插值時間ti1、ti2、ti3為目標函數,使搜索維度大大降低,運算更加簡單。待優化的目標函數是使各關節在速度的約束下運行時間最短,其目標函數為

f(t)=min(ti1+ti2+ti3)

(17)

max{vi}

(18)

式中:vi為各段多項式的實時速度；vimax為關節的限制速度。

表 2 測試結果Tab.2 The test results

基于混沌自適應煙花算法的機器人時間最優軌跡規劃算法就是以關節速度為約束條件,選擇最短的關節運動時間。

3 仿真結果驗證及分析

本文以UR機器人為例,采用旋量理論對其進行運動學建模,如圖1所示,其中各旋轉軸方向的單位矢量ωi,位置矢量ri等參數見表3。

圖 1 UR機器人結構圖Fig.1 Structure diagram of UR robot

表 3 UR機器人參數

根據Paden-Kahan子問題法和消元法對UR機器人進行逆運動學分析,將笛卡爾空間坐標系下的插值點變成關節空間的角度插值點。給定機器人末端的位姿信息,如表4所示。表4中路徑點前3個值為位置信息,后3個值為姿態信息。根據其位姿信息可以求解出各關節在各路徑點時所對應的角度,如表5所示。

表 4 機器人末端的位姿信息Tab.4 Posture information at the end of the robot

表 5 關節角度插值點

傳統的3-5-3多項式插值方法,各段插值時間是人為給定的具有不確定性,從而影響機器人的工作效率,圖2是給定各段插值時間為4 s時各關節運動的位置、速度、加速度曲線。

(a) 位置變化曲線 (b) 速度變化曲線 (c)加速度變化曲線圖 2 3-5-3多項式插值的關節位置、速度、加速度變化曲線Fig.2 3-5-3 polynomial interpolation curve of joint position, velocity and acceleration

根據圖2可知其滿足起始點和終點的速度與加速度都為0,抬起點和下降點的速度和加速度連續的約束條件,綜合考慮安全、穩定、效率等多方面因素,UR機器人各關節的速度最大為30°/s,但是由圖2(b)可以發現機器人各關節的最大速度還未能到達所允許的最大速度,這就導致其工作效率不高。

采用混沌自適應煙花算法對有速度約束的3-5-3插值多項式方法求解最優時間。以求解關節1的最優時間為例,本文設定初始煙花數目N為5,在三維解空間內進行最優化搜索,初始的煙花位置為[0.01,4]的任意隨機數,煙花爆炸產生火花m的數目為50,循環迭代100次。可以得到最優粒子進化圖,如圖3和圖4所示。

圖 3 關節1的最優時間粒子進化圖Fig.3 Optimal time particle evolution diagram of joint 1

圖 4 關節1的總時間最優粒子進化圖Fig.4 Total time optimal particle evolution diagram of joint 1

同理可以得到其他關節的各段最優時間,如表6所示。

表 6 各關節最優時間

Tab.6 Optimal time of each joint 單位：s

關節iti1ti2ti3 11.524 50.779 91.498 6 21.138 00.186 60.709 2 30.369 30.148 90.357 9 41.197 41.634 41.195 3 50.756 90.207 81.838 6 60 0 0

由于機器人的關節運動具有時間同步性,所以選擇每段插值時間里的最大值max(ti1)=1.524 5 s,max(ti2)=1.634 4 s,max(ti3)=1.838 6 s作為每段的插值時間。與未經優化的3-5-3插值多項式插值時間相比減少了7.002 5 s。

圖5是采用混沌自適應煙花算法得到最優插值時間后,機器人的位置、速度、加速度曲線。由圖5可知，優化后也滿足起始點和終點的速度與加速度都為0,抬起點和下降點的速度和加速度連續的約束條件。對比未經優化和優化后的位置曲線可以發現時間縮短后其位置變化和未優化時相差不大。對比速度曲線可以發現優化后各關節速度都有所增加,但都未超過限制速度,且最大速度趨近于限制速度,這樣能夠在保障安全的情況下提高工作效率，驗證了算法的正確性。

(a) 位置變化曲線

(b) 速度變化曲線

(c) 加速度變化曲線圖 5 優化后關節位置、速度、加速度變化曲線Fig.5 The curve of joint position,velocity and acceleration after optimization

4 結 語

本文提出了一種混沌自適應煙花算法,針對自適應煙花算法收斂速度慢、精度低等缺陷,將混沌算法與自適應煙花算法相結合,將隨機初始化改為混沌初始化,在選擇策略之后進行混沌優化,提高其收斂速度和求解精度,對8個測試函數進行測試,可以發現,CAFWA在求解多峰函數和最優解距離原點較遠的問題時具有更好的性能。

以UR機器人為例,在關節空間中,以速度為約束條件,提出了基于混沌自適應煙花算法的時間最優軌跡規劃方法。由于傳統 3-5-3 多項式插值,各段插值時間具有不確定性,所以對機器人的工作效率,機械磨損及生產安全會產生不利的影響。通過Matlab仿真可以發現經過混沌自適應煙花算法優化后,機器人各關節平穩運行且各關節都滿足速度約束,其速度、加速度在插值時間點連續且平滑,該算法有較高的實用價值。