基于混合粒子群算法的移動機器人路徑規劃①

熊昕霞,何利力

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

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

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

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

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

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

1 新型混合粒子群優化和遺傳算子

1.1 粒子群優化

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

粒子的速度更新:

粒子的位置更新:

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

1.2 改進的粒子群優化

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

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

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

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

Singer 映射定義如下:

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

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

1.3 遺傳算法中的遺傳算子

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

圖1 Singer 映射

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

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

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

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

1.4 IPSO-GOP 算法

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

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

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

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

2 目標函數與三次樣條插值

2.1 目標函數

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

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

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

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

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

式中,Mmax是路徑的線段總數.

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

3.1 函數優化

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

表1 標準測試函數

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

表2 函數優化結果

3.2 路徑生成與修正

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

在仿真實驗中,不同障礙物數量環境中的參數設置如表3所示.

圖2 全局路徑規劃仿真實驗圖

表3 算法的相關參數

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

3.3 與其他路徑規劃算法比較

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

圖3 多障礙物環境下PSO-GOP 算法路徑規劃結果

圖4 復雜環境下IPSO-GOP 算法收斂曲線

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

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

圖6 目標函數值與迭代次數的關系

圖7 10 次實驗對比結果

4 結束語

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