高岳林，武少華

(1.北方民族大學 寧夏智能信息與大數(shù)據(jù)處理重點實驗室,寧夏 銀川 750021；2.寧夏大學 數(shù)學統(tǒng)計學院,寧夏 銀川 750021)

0 引言

機器人技術(shù)是近年來興起的一種現(xiàn)代科學技術(shù)，它的發(fā)展結(jié)合了許多高新技術(shù)學科，主要有機械電子、信息學、控制論、軟件開發(fā)、人工智能等。移動機器人路徑的研究是機器人學科中一個重要的研究領(lǐng)域，研究的問題是從工作空間中尋找一個從開始位置到目標位置的一個最優(yōu)路徑。本質(zhì)上屬于路徑規(guī)劃問題。智能算法是近年來提出用來解決機器人路徑規(guī)劃問題的算法，主要使用的方法有遺傳算法、蟻群算法、粒子群算法、神經(jīng)網(wǎng)絡等等。

國內(nèi)外學者對機器人路徑規(guī)劃也作了許多研究。Willms等[1]提出了一種高效的動態(tài)實時機器人路徑規(guī)劃系統(tǒng)，進行實時機器人路徑規(guī)劃。Fujimura等[2]提出了一種基于人工勢場的機器人路徑規(guī)劃。Saska等[3]提出了一種采用Ferguson 樣條的粒子群優(yōu)化算法,該方法得到的路徑比傳統(tǒng)方法得到的路徑光滑，而且易于執(zhí)行。劉廣瑞等[4]利用蟻群算法來進行最優(yōu)路徑的搜索，并對算法進行收斂性分析，從而提高了算法的收斂效果。趙開新等[5]通過梯度計算、節(jié)點探測、路徑評估3種方式對機器人路徑規(guī)劃進行研究。陳志軍等[6]將機器人路徑規(guī)劃是建立在三維空間里，建立了三維路徑規(guī)劃的評價指標和優(yōu)化函數(shù),提出了一種基于模糊神經(jīng)網(wǎng)絡和遺傳算法的機器人路徑規(guī)劃。強寧等[7]采用了三次樣條插值和粒子群算法來進行多機器人全局路徑規(guī)劃。

粒子群算法在解決機器人路徑規(guī)劃問題時主要存在兩個缺陷：①算法迭代到后期,粒子群多樣性下降，當路徑陷入局部較差路徑時，很難自動跳出，出現(xiàn)“早熟”現(xiàn)象。②算法的收斂性差，算法迭代后期，許多粒子適應度相差不大，導致粒子搜索進入停滯狀態(tài)，路徑尋優(yōu)也會停滯，造成了路徑的精度低。因此對算法進行改進十分必要。粒子群優(yōu)化算法(PSO)和模擬退火算法(SA)是兩種不同的智能優(yōu)化算法，粒子群優(yōu)化算法通過追隨當前搜索到的最優(yōu)解來尋找全局最優(yōu)，模擬退火算法的機制便是以一定的概率來接受一個比當前解要差的解，從而可能跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。針對以上問題，筆者提出一種基于模擬退火的改進粒子群算法(APSO-SA)，通過充分發(fā)揮粒子群算法和模擬退火算法的優(yōu)勢從而實現(xiàn)機器人全局最優(yōu)路徑規(guī)劃。

1 標準粒子群算法

粒子群算法(PSO)是一種啟發(fā)式隨機算法。鳥群中每一個鳥相當于粒子群算法中的一個粒子。每個粒子好比尋找食物的鳥都有速度和位置，通過自身和社會兩種學習方式，粒子在搜索空間中運動，從而得到全局最優(yōu)解。假設種群有N個粒子在D維空間搜索，標準粒子群算法更新公式為:

(1)

(2)

式中：t為迭代次數(shù)；vij表示第i個粒子j維的速度大小；xij表示第i個粒子j維的位置大小；w表示慣性權(quán)重；c1、c2表示學習因子；r1、r2表示隨機數(shù)。粒子群算法雖然簡單，但是算法迭代后期，由于粒子多樣性差導致粒子容易陷入局部最優(yōu)解，所以要對粒子群算法進行改進。

2 粒子群算法的改進

2.1 帶壓縮因子的粒子群算法

為了有效地控制粒子飛行速度使算法全局搜索和局部搜索平衡，Clerc等[8]提出了帶壓縮因子的PSO算法，其速度更新公式如下:

(3)

其中搜索因子:

帶壓縮因子的PSO算法相當于線性遞減權(quán)重的PSO算法，該算法的優(yōu)勢在于去掉了慣性權(quán)重w，減少了算法參數(shù)，只有兩個學習因子參數(shù),所以只需對兩個學習因子進行自適應調(diào)節(jié)。其調(diào)節(jié)公式如下：

當f(xi)≤favg，粒子xi需要進行局部搜索，學習因子取:

(4)

當f(xi)>favg，粒子xi要進行全局搜索，所以學習因子?。?/p>

(5)

式中：cmin=1.5；cmax=2.5；f(xi)表示粒子xi的適應度大小;favg表示所有粒子的平均適應度。

2.2 模擬退火算子

模擬退火算法是由Metropolis等于1953年提出的，該算法在搜索過程中具有概率突跳的能力，能夠在一定程度上避免搜索過程中陷入局部最優(yōu)解，由于粒子群算法對pg全局最優(yōu)粒子依賴性很強，所以為了避免粒子搜索過程陷入pg，所以對pg引入模擬退火操作，其中Metropolis準則如下：

(6)

式中：f(pi)表示pi粒子的適應度；f(pg)表示當前粒子群算法迭代的全局最優(yōu)適應度。采用輪盤賭策略從pi中確定全局最優(yōu)的某個個體代替pg，初溫和退溫公式為：

(7)

以上為APSO-SA算法的基本思想，標準粒子群算法的時間復雜度為O(M，D，N)，其中M為最大迭代次數(shù)，D為粒子維數(shù)，N為粒子個數(shù)。由于該算法是建立在壓縮因子的粒子群算法的基礎上，壓縮因子的粒子群算法時間復雜度為O(M，D，N),學習因子的自適應調(diào)節(jié)策略和模擬退火操作的時間復雜度均為O(N)，所以APSO-SA算法的時間復雜度為O(M，D，N)。

3 機器人路徑規(guī)劃模型建立

3.1 三次樣條插值編碼設計

兩點法對機器人路徑進行規(guī)劃[9]會造成路徑平滑性差，機器人運動不平穩(wěn)，頻繁轉(zhuǎn)向會造成能源的極大浪費，本文機器人路徑規(guī)劃是建立在二維平面上，提出的APSO-SA算法在二維平面進行三次樣條插值編碼，根據(jù)文獻[3]提出的Ferguson三次樣條插值對路徑進行編碼優(yōu)化，其原理如下。

假設有以下節(jié)點(xi,yi)，其中xi

(1)每個分段區(qū)間[xi,xi+1]，S(x)=Si(x)為三次多項式。

(2)每一個端點滿足S(xi)=yi，i∈N∩i≤n。

(3)S(x)的1、2階導數(shù)為S′(x)、S″(x),而且在[a,b]區(qū)間內(nèi)連續(xù)，即Si(x)可以寫成：

Si(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3；

式中：i∈N∩i

機器人在搜索空間搜索最優(yōu)路徑可以看作在三次樣條空間中搜索最優(yōu)樣條，APSO-SA算法中的每一組粒子表示為一組路徑的節(jié)點，每一組路徑節(jié)點個數(shù)便為三次樣條曲線的個數(shù)，由于三次樣條插值的性質(zhì)，每一組路徑節(jié)點的個數(shù)體現(xiàn)了路徑可以轉(zhuǎn)向的最大次數(shù)。粒子編碼的路徑節(jié)點個數(shù)會隨著工作環(huán)境的復雜而增加，實際生活中機器人轉(zhuǎn)向3～5次便可以繞過所有的障礙物，本文的障礙物模型設置轉(zhuǎn)向節(jié)點為3。

3.2 路徑初始化

路徑初始化決定著算法的好壞，PSO算法機器人路徑規(guī)劃均是在機器人工作空間隨機取粒子，但是導致算法收斂性差，于是對粒子的初始化進行改進，提出基于高斯分布的隨機初始化，初始化公式如下：

x=(xs+xt)/2+r3；

(8)

y=U(ymin,ymax,1,n)，

(9)

式中：xs、xt分別為開始位置和目標位置的橫坐標；r3為高斯分布產(chǎn)生的隨機數(shù)；n表示產(chǎn)生粒子的個數(shù)；ymax、ymin分別為粒子初始化縱坐標的上下界；U表示在給定上下界中均勻產(chǎn)生n個粒子縱坐標的值。

3.3 障礙物處理

障礙物對機器人路徑規(guī)劃有很大的影響，若沒有障礙物，機器人在二維空間中從開始位置到目標位置運動，直線運動最短，無須進行路徑規(guī)劃，然而現(xiàn)實機器人工作時，障礙物是客觀存在的，筆者研究的是靜態(tài)工作環(huán)境下的機器人路徑規(guī)劃，由于實際工作環(huán)境中障礙物形狀千差萬別，導致建模十分困難，為了方便統(tǒng)一研究，筆者對障礙物進行預處理，在二維空間中，障礙物均進行膨脹處理，即用原障礙物圖形的外接圓表示該障礙物，具體見圖1。

圖1 不同形狀障礙物膨脹處理Figure 1 Different obstacle with different shapes expansion

3.4 適應度函數(shù)

適應度函數(shù)的值可以看作路徑的長度，粒子通過三次樣條編碼，不斷尋找最優(yōu)適應度，而有些路徑與障礙物相交會成為非法路徑，如果直接去掉這些路徑，那么存在的可行路徑就會變得非常少，路徑的多樣性就會減弱，所以構(gòu)造帶有罰函數(shù)的適應度函數(shù)，通過附加較大的懲罰值，使路徑在優(yōu)化過程中自動淘汰非法路徑。文獻[8]中使用了一種帶有罰函數(shù)的適應度函數(shù)，筆者對其做了一些簡單的修改，得出適應度函數(shù)如下：

z=L(1+beta·V),

(10)

式中：L為機器人工作運行路徑的長度；beta為懲罰值，一般設置為100；V為路徑的非法度，當V=0時，z=L，此時適應度的大小就為路徑的大小。

4 算法流程

APSO-SA算法機器人路徑規(guī)劃與粒子群算法機器人路徑規(guī)劃流程相似，具體算法流程如下：

步驟1創(chuàng)建障礙物模型,初始化機器人開始位置以及機器人目標位置，初始化機器人工作空間。

步驟2初始化APSO-SA算法的參數(shù)，包括粒子個數(shù)、學習因子、最大迭代次數(shù)、退火系數(shù)、路徑節(jié)點個數(shù)。

步驟3按照式(8)、(9)初始化每組粒子的位置，以及對粒子進行三次樣條編碼。

步驟4按照式(4)、(5)自適應處理學習因子，同時按照式(3)更新粒子速度，按照式(2)更新粒子的位置。

步驟5按照式(10)計算每組粒子當前的適應度，并根據(jù)式(6)和式(7)對當前適應度最好的粒子進行退火處理。

步驟6判斷算法是否達到最大函數(shù)評價次數(shù)，若滿足，則停止搜索，輸出結(jié)果，否則返回步驟4繼續(xù)迭代。

5 仿真模擬

為了驗證APSO-SA算法在機器人路徑尋優(yōu)中的優(yōu)越性，筆者設計了以下實驗,在3種障礙物模型中對APSO-SA算法與PSO算法進行比較測試。其中3種障礙物模型的最短路徑長度通過幾何計算得到，保留小數(shù)點后2位。見表1。算法比較采用固定粒子個數(shù)和最大函數(shù)迭代次數(shù)，試驗在windows 7系統(tǒng)MATLAB 2012a中完成。電腦配置為Intel(R) Core(TM) i5-3317U CPU@1.70 GHz。

5.1 參數(shù)設置

筆者建立的3個障礙物模型參數(shù)如表1～3所示。

表1 3個模型基本參數(shù)Table 1 Basic parameters of three models

表2 3個模型圓心及其半徑Table 2 Center and rabius of three models

表3 PSO和APSO-SA算法參數(shù)Table 3 Algorithm parameters of PSO and APSO-SA

5.2 數(shù)值實驗

5.2.1 單障礙物模型

兩種算法獨立運行30次，數(shù)值結(jié)果用SPSS進行統(tǒng)計分析，結(jié)果如表4、5所示。

表4 單障礙物模型數(shù)值結(jié)果比較Table 4 Comparison of numerical results of single obstacle model

表5 單障礙物模型單因素方差分析結(jié)果比較Table 5 One-way ANOVA results of single obstacle model

圖2為單障礙物模型兩種算法比較結(jié)果圖，從圖2可以看出，PSO算法和APSO-SA算法都能夠在該模型中規(guī)劃出一條無碰路徑。PSO算法搜索出的最優(yōu)路徑長度為7.47 m，而APSO-SA算法得出的最優(yōu)路徑長度為7.41 m，同時APSO-SA路徑搜索范圍廣，路徑搜索前期變化比較大，10代以后趨于平穩(wěn)，表4、5也表明APSO-SA算法的路徑尋優(yōu)能力優(yōu)于PSO算法，通過方差同質(zhì)性檢驗后進行單因素方差分析，結(jié)果表明，兩種算法具有顯著性差異。

圖2 單障礙物模型兩種算法比較結(jié)果Figure 2 The results of the two algorithms of single obstacle model

5.2.2 多個均勻障礙物模型

圖3分別給出了多個均勻障礙物模型兩種算法得出的最優(yōu)路徑和最優(yōu)路徑長度比較。從實驗結(jié)果可以看出，APSO-SA算法的路徑平滑度明顯優(yōu)于PSO算法。下面兩種算法各自獨立運行30次，運行結(jié)果及統(tǒng)計分析記錄如表6、7所示。

圖3 多個均勻障礙物模型兩種算法比較結(jié)果Figure 3 The results of the two algorithms of multiple uniform obstacle models

由于該模型存在許多局部最優(yōu)路徑，所以獲得的路徑為局部最優(yōu)路徑不可避免。從表6可以看出,APSO-SA有很好地跳出局部最優(yōu)路徑的性能，得到的路徑為局部最優(yōu)路徑的概率僅為20%.從時間上來看兩種算法相差不大，僅比傳統(tǒng)的PSO算法高了0.04 s，總體路徑平均長度卻減少了0.27 m。這充分體現(xiàn)了APSO-SA算法多樣化策略的優(yōu)勢。單因素方差分析也可以得到兩種算法具有顯著性差異。

表6 多個均勻障礙物模型數(shù)值結(jié)果比較Table 6 Comparison of numerical results of multiple uniform obstacle models

表7 多個均勻障礙物模型單因素方差分析結(jié)果比較Table 7 One-way ANOVA results of multiple uniform obstacle models

5.2.3 多個不均勻障礙物模型

從圖4和表8可以看出，在多個不均勻障礙物模型中，APSO-SA算法的路徑尋優(yōu)能力也優(yōu)于PSO，這充分說明了在復雜的工作環(huán)境中PSO算法中的粒子在搜索過程中極易從可行域飛到不可行域，導致種群中大量的粒子進行約束處理后不能按最優(yōu)方向去搜索最優(yōu)值，最終影響搜索效果。

圖4 多個不均勻障礙物模型兩種算法比較結(jié)果Figure 4 The results of the two algorithms of multiple inbomogeneous obstacle models

表8 多個不均勻障礙物模型數(shù)值結(jié)果比較Table 8 Comparison of numerical results of multiple inbomogeneous obstacle models

表9 多個不均勻障礙物模型單因素方差分析結(jié)果比較Table 9 One-way ANOVA results of multiple inbomogeneous obstacle models

6 結(jié)論

筆者提出了一種基于模擬退火與自適應粒子群混合的算法，用來解決機器人路徑規(guī)劃問題。其中采用高斯分布和三次樣條插值法來初始化并編碼粒子,采用退火策略和罰函數(shù)策略進一步提高了算法的運行效率，使機器人路徑更加合理化。通過對適應度函數(shù)的調(diào)整，APSO-SA算法也可以解決不同的應用問題。將來有可能應用于動態(tài)實時路徑規(guī)劃問題中。