熊昕霞,何利力

(浙江理工大學 信息學院,杭州 310018)

移動機器人中的路徑規(guī)劃問題被認為是一項復雜的任務.工業(yè),醫(yī)學和農(nóng)業(yè)中機器人的廣泛應用鼓勵研究人員在路徑規(guī)劃領域開展研究工作.路徑規(guī)劃者應根據(jù)特定標準,在充滿障礙物的環(huán)境中,在機器人的起始位置與目標位置之間找到一條最佳(或接近最佳)的無碰撞路徑.在某些情況下,機器人所處的環(huán)境可能包含危險區(qū)域或敏感區(qū)域,在路徑規(guī)劃算法中需要考慮這些危險區(qū)域或敏感區(qū)域.除了生成更短的路徑,路徑規(guī)劃算法還需要生成與危險區(qū)域和環(huán)境中的敏感區(qū)域相距安全距離的軌跡.在路徑規(guī)劃中,為移動機器人提供自主權的不同元啟發(fā)式技術的開發(fā)是當前探索中最具挑戰(zhàn)性的領域之一.

在過去的幾十年中,通過使用一些傳統(tǒng)的和啟發(fā)式方法,來優(yōu)化路徑規(guī)劃問題,如細胞分解(CD),勢場法(APF)[1],模擬退火,遺傳算法(GA)[2],粒子群優(yōu)化(PSO)[3]和神經(jīng)網(wǎng)絡.

通常,PSO 非常適合于開發(fā),但可能導致局部最優(yōu)問題.因此,在某些情況下,PSO 無法找到全局最優(yōu)解.標準PSO中使用的搜索策略主要基于隨機游動,它不能總是成功地解決優(yōu)化問題.為了進一步提高算法的性能,已將不同策略添加到優(yōu)化算法中,例如文獻[4]在算法中引入雞群算法中的母雞更新方程和小雞更新方程對搜索停滯的粒子進行擾動,使粒子跳出較差的搜索區(qū)域,脫離局部最優(yōu);帶有變異算子的粒子群優(yōu)化[5]被用于開發(fā)移動機器人路徑規(guī)劃算法.文獻[3]使用隨機PSO 解決了移動機器人的平滑路徑規(guī)劃問題,文獻[6]使用自適應慣性權重改進的粒子群算法減少粒子群的無效迭代次數(shù),文獻[7]結(jié)合差分進化算法中的變異算子來優(yōu)化粒子群算法的適應度值.

雖然已有文獻對PSO 進行研究和改進,但是,PSO在進化過程中會過早收斂,同時會處理一些復雜的問題,例如一些基于現(xiàn)實世界的導航優(yōu)化問題,PSO 還取決于用戶來調(diào)整控制參數(shù)例如慣性權重,“社會”和“認知”系數(shù)以及速度以實現(xiàn)所需的解決方案.因此,PSO算法的結(jié)構(gòu)需要進一步改進,以實現(xiàn)最優(yōu)解.GA 執(zhí)行交叉和突變操作以重組染色體.它具有強大的全局搜索功能,可以在搜索范圍內(nèi)搜索最優(yōu)問題的最優(yōu)解或接近最優(yōu)解,并且具有優(yōu)于傳統(tǒng)最優(yōu)技術的性能.但其主要缺點是,解決方案更容易陷入局部最小值.這是由于在搜索空間中僅從單個方向搜索解決方案.因此,可以將GA 算法改進為從多個方向看作一種搜索方法,這意味著更容易擺脫局部最小值[8].將文獻[8]的多重交叉和變異算子,與IPSO 融合,整合了PSO的開發(fā)能力和GA的探索能力,以實現(xiàn)全局最優(yōu).

本文提出了一種混合遺傳算法中遺傳算子的改進粒子群算法(IPSO-GOP).首先,為提高算法搜索能力,在算法運行的各個階段利用粒子與全局最優(yōu)位置的距離對慣性權重進行自適應調(diào)整,采取混沌變量對粒子進行擾動的方法提高收斂速度;其次,為了擺脫局部最小值并增加種群的多樣性,引入遺傳算法繼承的多重交叉和變異兩個進化算子協(xié)同粒子群優(yōu)化;最后,根據(jù)三次樣條插值對該混合算法生成的路徑進行平滑處理,得到無碰撞路徑最短的幾何連續(xù)路徑.

1 新型混合粒子群優(yōu)化和遺傳算子

1.1 粒子群優(yōu)化

PSO 算法是由Kennedy和Eberhard 于1995年提出的基于種群的優(yōu)化問題啟發(fā)式策略,與鳥群和魚類群的行為類似,在PSO中,優(yōu)化問題的候選解決方案集被定義為可能通過參數(shù)(搜索)空間定義軌跡的粒子群,這些空間由它們自己和鄰居驅(qū)動的最佳表現(xiàn)[9].PSO中的每個粒子都有一個位置xi和速度vi.位置表示粒子所在搜索區(qū)域的位置,而速度是相對于當前位置到下一個位置的變化率.這兩個值(位置和速度)是隨機初始化的.令(N為粒子群總)數(shù),第i個例子在D維空間的坐標為其中1≤i≤N,速度向量對于每一代,它的第d維(1≤d≤D)根據(jù)如下方程變化:

粒子的速度更新:

粒子的位置更新:

式中,(t)是第d維粒子i第t次迭代的速度;(t)是第d維粒子i第t次迭代的位置;c1、c2是加速常數(shù);r1、r2是在[0,1] 范圍內(nèi)變化的隨機數(shù);是粒子i在t次迭代中最優(yōu)位置;是所有粒子在第t次迭代中經(jīng)歷過的最好的位置.

1.2 改進的粒子群優(yōu)化

參數(shù)控制和自適應一直是粒子群算法研究的熱點,慣性權重w的目的是控制速度,從而影響收斂性,幾乎所有的粒子群算法都將慣性權重作為速度更新規(guī)則的組成部分[10].速度更新公式如式(3)所示:

每個粒子都用較大的慣性因子值更新其位置和速度,有利于全局搜索,而用較小的慣性因子值則有利于采用組合wmax=0.9,wmin=0.4可以達到最佳性能.局部搜索.多項研究表明,對慣性權重進行動態(tài)調(diào)整可以改善PSO的收斂性,而線性遞減慣性權重已經(jīng)顯示出更好的結(jié)果[9].因此,這里采用文獻[11]提出的慣性權重的自適應變化,如式(4)所示.過去已有實驗驗證

式中,disti是粒子i與全局最佳粒子之間的歐式距離;max_dist是某次迭代中粒子與全局最佳粒子之間的最大距離.

最高的隨機運動有益于探索大部分搜索空間.但是,最快的收斂速度是開發(fā)階段的主要目標.局部搜索和梯度下降都可以提高性能,但是會帶來額外的計算成本.有文獻表明,將混沌理論整合到基于群體的算法中是平衡算法的全局探測和局部開采能力的最小計算成本的方法之一[12].由于混沌行為類似于隨機性,但是具有更好的動力學和統(tǒng)計學特性,與隨機搜索相比,混沌搜索可以更容易地從局部最優(yōu)解中逃脫.因此,將隨機參數(shù)r1、r2替換成一維混沌圖,使得算法收斂速度更快.文獻[13]中已有實驗驗證,將隨機參數(shù)r2替換成混沌圖獲得的解果最佳,并且Singer 映射用于該算法的結(jié)果最優(yōu).替換后公式如下:

Singer 映射定義如下:

式中,μ是0.9 到1.08 之間的一個參數(shù).

當 μ=1.069,初值x0=0.1其x值與迭代次數(shù)如圖1所示.Singer 圖一直在0 到1 之間反復波動.可以通過不斷擾動,最大化全局勘探范圍和減小范圍以改善當前的解決方案.

1.3 遺傳算法中的遺傳算子

遺傳算法是一種自適應啟發(fā)式搜索方法,是進化算法的一種.其主要思想是根據(jù)目標函數(shù)構(gòu)建適應度,以評估種群中的所有染色體.經(jīng)過一定數(shù)量的迭代后,選擇適應性最好的染色體作為指定問題的解決方案.該算法以一組隨機選擇的染色體作為初始種群開始,并且兩個遺傳算子(交叉和突變)創(chuàng)建新的染色體(后代).選擇運算符用于一代又一代地創(chuàng)建總體.具有更好適應性值的染色體在下一代中具有更高的概率被選擇.在下文中,主要介紹其中兩個算子,多重交叉和突變.

圖1 Singer 映射

多重交叉:該運算符是基于文獻[8]中改進遺傳算法的交叉公式即多重交叉.多重交叉使用的3個染色體(θ1,θ2,θ3)是從交配池中隨機生成的,并由彼此隨機交叉.若θi(i ∈[1,2,3])最小,它將被選為主要的父母,新的染色體θ′i在等式(10)中生成.

式中,rand是0 到1 之間的隨機值

粒子的更新速度計算公式如下:

突變:變異是一個過程,其中包括通過應用某種隨機變化對染色體的位進行小的改變.變異算子在GA中起至關重要的作用,可以有效維持種群的多樣性,避免算法陷入局部最小值.

1.4 IPSO-GOP 算法

由于依賴于外部參數(shù)(例如慣性權重和加速度參數(shù)),傳統(tǒng)的PSO 算法難以生成最優(yōu)解,并且收斂速度較慢.因此,PSO 算法的效率相對較差.在大多數(shù)情況下,當大多數(shù)粒子在連續(xù)階段中不改變其在群體中的位置時,會聚為時過早,產(chǎn)生的最優(yōu)解較少,因此無法找到全局最優(yōu)解.由于在PSO 算法中遇到了上述問題,因此已采取了措施來改善PSO的性能,即通過進化算子調(diào)節(jié)IPSO的速度多樣化搜索空間以消除過早收斂.

在這種雜交中,使用兩個進化算子更新了IPSO的粒子的位置.在所有粒子都構(gòu)建完成后,根據(jù)突變概率Pm更 新粒子的位置.粒子被分配了隨機數(shù)ε ∈[0,1],如果粒子的隨機數(shù)小于多重交叉概率Pc,則新粒子的速度將使用IPSO 等式的速度更新式(7)生成,否則,將使用等式(10)的多重交叉算子生成.

改進后算法流程如算法1.

算法1.IPSO-GOP 算法1)初始化種群大小,搜索空間,迭代次數(shù),粒子的初始位置和速度2)根據(jù)適應度函數(shù)評價每個粒子的適應度3)根據(jù)突變概率更新粒子的位置4)更新每個粒子經(jīng)歷過的最好位置pbest和全局所經(jīng)歷最好位置gbest,并且根據(jù)式(4)計算w ε?Pc 5)判斷是否成立,成立轉(zhuǎn)至步驟 6),否則轉(zhuǎn)至步驟 7)6)根據(jù)式(7)更新粒子的速度7)根據(jù)式(10)更新粒子的速度8)使用式(2)對粒子位置進行更新9)計算位置更新后各粒子的適應度值并更新個體最優(yōu)適應度值以及全局最優(yōu)適應度值10)判斷是否滿足停止條件,若是,輸出最優(yōu)適應度值,否則轉(zhuǎn)至步驟 2)

2 目標函數(shù)與三次樣條插值

2.1 目標函數(shù)

在給出環(huán)境,設初始位置和目標位置后,將所提出的IPSO-GOP 算法應用于計算無碰撞軌跡.

路徑長度影響機器人的運輸時間,為更快完成任務,通過形成第一個目標函數(shù)f1使得機器人路徑長度最短.在任一迭代中,如果點pj(t)到 目標點pj(N)距 離f1最短,則被選為最優(yōu)的點.

式中,d(·)是歐式距離.

最短距離長度為起始點p(1)和目標點p(N)之間的點的距離總和.則,f1公式如下所示:

第2個目標函數(shù)為懲罰函數(shù),若路徑上有一路徑線段與障礙物碰撞,則懲罰函數(shù)乘以一個懲罰因子δ.

式中,Mmax是路徑的線段總數(shù).

αi是第i個路徑片段與障礙物相交的個數(shù).

總目標(適應度)函數(shù)如下:

2.2 三次樣條插值的平滑路徑

本文路徑規(guī)劃地圖采用柵格地圖表示,因此會在轉(zhuǎn)彎處產(chǎn)生尖峰.為了讓移動機器人減少實際機器人輪子的軸磨損和能耗,應保證路徑的平滑性,盡量保證平滑處理后的路徑與實際路線相同.

由于拉格朗日插值法因龍格現(xiàn)象在分段曲線邊緣處的擬合誤差影響路徑的平滑度.三次樣條曲線線性光滑,具有連續(xù)的二階導數(shù);能夠保證擬合曲線通過所有的規(guī)劃的路徑點.

三次樣條插值具有一階和二階導數(shù)的收斂性.當三次函數(shù)的最高項系數(shù)為0 時,三次樣條插值曲線仍為曲線,插值效果應更好.另外,三次樣條插值與高階插值相比,具有計算簡單,穩(wěn)定性好的優(yōu)點.由于三次樣條插值已得到廣泛應用[14],并在路徑平滑方面的應用效果很好[15,16],因此本文使用三次樣條插值形成平滑路徑.

取區(qū)間 [a,b] 分成n個區(qū)間[(x0,x1),(x1,x2),···,xn?1,(xn)],三次樣條方程滿足以下條件:

在每個小區(qū)間[xi?1,xi]上,S(x)=Si(x)都是一個三次方程:

S(x)在區(qū)間[a,b]中是連續(xù)的:

S′(x)在區(qū)間[a,b]中是連續(xù)的:

S′′(x)在區(qū)間[a,b]中是連續(xù)的:

在本文中,三次樣條函數(shù)用于在起點,控制點和目標點的路徑上進行插值,可以將移動機器人的路徑繪制為一系列連接路徑點的線段,從而獲得了通過連接所有插值點而形成的完整路徑.

3 實驗分析

為了驗證本文提出算法的有效性,對算法尋優(yōu)性能進行測試與對比.并在仿真環(huán)境下對機器人的路徑規(guī)劃問題進行了研究,以起點S(0,0),終點G(20,20)在不同障礙物環(huán)境進行路徑規(guī)劃,并利用三次樣條插值對路徑進行擬和修正.最后,針對相同環(huán)境下與不同算法的每次迭的最優(yōu)適應度值進行對比.計算環(huán)境均為操作系統(tǒng):Window10、CPU:Intel Core i5、編程語言:Python 3.7.

3.1 函數(shù)優(yōu)化

為了評估本文所提出算法的性能,本文選取了5個標準測試函數(shù),由于其大多數(shù)全局最小值為0,復雜性更高,所以移動和偏差這些測試函數(shù).測試函數(shù)如表1所示.

表1 標準測試函數(shù)

初始參數(shù)為:種群數(shù):30,迭代次數(shù):500.其中,PSO 加速常量c1、c2為1.5,慣性權重w為0.5.GA 交叉概率為1,變異概率為0.01.實驗結(jié)果如表2所示.結(jié)果是對10 次獨立運行的平均值(ave)和標準差(std)

表2 函數(shù)優(yōu)化結(jié)果

3.2 路徑生成與修正

建模環(huán)境為:設計具有不同障礙物數(shù)量的20×20 網(wǎng)格工作區(qū),如圖2所示,圖中Obs1Obs2為靜態(tài)障礙物,S和G 分別代表機器人的起點和目標點.藍色實線是IPSO-GOP 規(guī)劃出的路線,紅色實線是“光滑處理”后的路徑.

在仿真實驗中,不同障礙物數(shù)量環(huán)境中的參數(shù)設置如表3所示.

圖2 全局路徑規(guī)劃仿真實驗圖

表3 算法的相關參數(shù)

圖3為本文所提出的算法在多障礙物環(huán)境下規(guī)劃出的路徑和采用三次樣條插值平滑后的路徑.由于可行路徑必須經(jīng)過附近障礙物形成的一些狹窄空間,所以最優(yōu)解很可能是具有次優(yōu)目標的函數(shù)值的不可行路徑.本文所提算法很好完成了在多障礙物環(huán)境下規(guī)劃平滑路徑的任務.如圖3所示,其中紅色實線表示用于移動機器人運動的更平滑的路徑.每次迭代中最佳粒子的最佳的目標函數(shù)值如圖4所示,表明本文所提出的算法針對該問題能夠快速收斂.

3.3 與其他路徑規(guī)劃算法比較

對比算法選用粒子群優(yōu)化(PSO)、混合遺傳算法和粒子群優(yōu)化(GA-PSO)[17]兩種相關算法,所有算法設置的參數(shù)(懲罰因子除外)與表2相同,為了讓搜索結(jié)果更明顯,開始迭代適應度值更小,這里設置懲罰因子δ=20.本文對IPSO-GOP和GA-PSO 算法進行路徑規(guī)劃仿真對比,如圖5所示.每次迭代的目標函數(shù)值,如圖6所示,從圖中可見,使用自適應權重和混沌變量改進的粒子群優(yōu)化在收斂時的目標函數(shù)值比PSO 更優(yōu).IPSO-GOP在迭代100 次的時候已經(jīng)得到了比其他兩種算法更優(yōu)的解.在迭代130 次左右的時候,IPSOGOP 已經(jīng)接近收斂,而PSO和GA-PSO在迭代200 次左右才接近收斂,在收斂時IPSO-GOP 目標函數(shù)值最小.

圖3 多障礙物環(huán)境下PSO-GOP 算法路徑規(guī)劃結(jié)果

圖4 復雜環(huán)境下IPSO-GOP 算法收斂曲線

圖5 IPSO-GOP與GA-PSO 路徑圖

為了保證結(jié)果的可靠性,對比算法和本文算法分別進行了10 次獨立的實驗,路徑規(guī)劃仿真10 次結(jié)果如圖7所示.10 次實驗結(jié)果對比顯示,IPSO-GOP 算法更穩(wěn)定,平均最佳適應度值最好.

圖6 目標函數(shù)值與迭代次數(shù)的關系

圖7 10 次實驗對比結(jié)果

4 結(jié)束語

本文提出了一種IPSO-GOP 混合算法,以尋找在充滿障礙物環(huán)境中移動機器人從預定起點到終點的無碰撞最短光滑路徑.所提出的算法使用遺傳算法中的遺傳算子(多重交叉和突變)優(yōu)化IPSO,將IPSO的社會本質(zhì)與GOP的多樣性相結(jié)合,減少了局部最優(yōu)的發(fā)生,同時滿足了收斂速度.實驗結(jié)果表明,IPSO-GOP 算法性能優(yōu)于其他現(xiàn)有的啟發(fā)式算法.仿真實驗中,與已有的元啟發(fā)式算法(如PSO)和混合算法(如GA-PSO)比較,可以得出,IPSO-GOP 算法優(yōu)于障礙物環(huán)境中路徑規(guī)劃的其他算法.