量子粒子群優(yōu)化算法在移動機器人路徑規(guī)劃中的應用

楊 靜

(安徽文達信息工程學院 藝術(shù)設計學院，安徽 合肥 230032)

0 引 言

移動機器人路徑規(guī)劃是找到一個從初始位置到終止位置的可行不交叉的途徑，滿足路徑短、安全、高效率等要求[1-2].最近幾年越來越多的研究者把蟻群法、神經(jīng)系統(tǒng)、進化算法和粒子群優(yōu)化等計算方法都運用到機器人路徑研究中.移動機器人路徑的理論研究狀態(tài)慢慢轉(zhuǎn)向到群體優(yōu)化計算的途徑，粒子群優(yōu)化(PSO)計算方法是一類啟發(fā)式優(yōu)化方法[3]，此方法對于目標函數(shù)的特性是不作規(guī)范，已慢慢成為群體智能優(yōu)化研究方法的一個潮流.移動機器人運用粒子群優(yōu)化計算可以讓規(guī)劃更容易、計算方法簡易，其缺點是對參數(shù)較大依賴，會陷入局部最優(yōu)等問題.

已有很多研究者研究了基于啟發(fā)式優(yōu)化算法的機器人路徑規(guī)劃方法.如文獻[4]提出了一種基于改進灰狼優(yōu)化算法的機器人路徑規(guī)劃方法.文獻[5]提出一種基于改進人工魚群算法和MAKLINK圖的機器人路徑規(guī)劃方法.文獻[6]提出一種改進蟻群算法的移動機器人路徑規(guī)劃，解決了傳統(tǒng)蟻群算法收斂慢，易產(chǎn)生局部最優(yōu)的問題.文獻[7]提出在隨機擴展樹算法中引入目標偏差搜索策略, 在度量函數(shù)中增加距離、角度因素, 用神經(jīng)網(wǎng)絡處理規(guī)劃路徑.文獻[8]提出了在離散化環(huán)境下規(guī)劃出初始路徑，然后在連續(xù)環(huán)境中進行路徑優(yōu)化.該方法使算法獨立于網(wǎng)格尺寸，并且創(chuàng)建了曲線路徑，增加了路徑的準確性和平滑性.近些年，機器人路徑規(guī)劃得到了迅速的發(fā)展, 以蟻群算法(ant colony optimization, ACO)、粒子群算法(particle swarm optimization, PSO)為代表的群體智能算法在解決復雜環(huán)境路徑規(guī)劃問題上表現(xiàn)出了突出的性能.文獻[9]將A*算法與啟發(fā)式優(yōu)化算法相結(jié)合，運用復合路徑規(guī)劃算法在地圖上搜索全局最優(yōu)路徑，然后運用模糊控制器調(diào)整移動機器人的角度.文獻[10]提出運用Max-Min Ant系統(tǒng)優(yōu)化算法在未知環(huán)境中規(guī)劃路徑.

粒子群計算方法傳遞信息多數(shù)依賴全局數(shù)值往全體粒子的傳輸，相比于其他計算方法，其速度更快，精度更高.缺點是會發(fā)生較早的局部最優(yōu)情況.針對這一問題，本文提出一種基于量子粒子群優(yōu)化(Quantum particle swarm optimization，QPSO)算法的移動機器人路徑規(guī)劃方法(QPSO法)，它運用的單個粒子優(yōu)化進度和整體分散的動態(tài)運動比重，讓慣性比重含有控制特征和適應特征，這個運算方法能快速提高計算的收斂進度、維持不同群里的特性.最終將新的計算方法運用到移動機器人的軌跡規(guī)劃中，實驗結(jié)果證明所提方法的優(yōu)化路徑明顯優(yōu)于其他方法.

1 改進粒子群優(yōu)化算法

按粒子群的特征性質(zhì)，QPSO方法的搜索最優(yōu)解的能力比PSO計算方法的更全面.

因此，本文對PSO計算方法展開優(yōu)化，其計算公式如下：

(1)

Pi.j=φ·Pbesti,j(t)+(1-φ)·Gbest(t),(i=1,2…，N,j=1,2,…，M)

(2)

mbest=(M1(t),M2(t),…,MD(t)=

(3)

在進行優(yōu)化的計算方法里，貼切的計算控制參數(shù)對計算的特征影響特別重，根據(jù)進化公式(1)和(3)展開研究可以增加粒子群運動路徑的多樣性，可以極大提高粒子群的全局搜索能力和收斂速度，依據(jù)粒子pi(t+1)的公式(2)，能夠轉(zhuǎn)換成公式

pi,j(t+1)=Gbesti,j(t)+φ(pbesti,j(t)-Gbesti,j(t))

(4)

從公式(1)和公式(4)中看出，轉(zhuǎn)換粒子pi(t+1)是整體最佳關(guān)系Gbest(t)與當時粒子最佳關(guān)系pbest(t)的差距的總和，Xi(t+1)和當時粒子的均值關(guān)系mbest和當時位置X(t)的差也體現(xiàn)出這一關(guān)系.

本文利用個體粒子優(yōu)化速度和整體分離的動態(tài)慣性比重，讓慣性比例含有自我適應聚集度改變慣性比列，讓慣性比列有自我適應能力，從而避開導致局部情況[11]，并且把隨機選擇的方法代入到最佳位置后解決.為了保證群多樣性能和固定特征，增加了QPSO計算方法的整體搜索力度，同時提升計算方法的收斂效應.

定義1 個體粒子的優(yōu)化速度，假如Fitness(Gbest(t))代表的是整體最佳情況的適應特征和Fitness(Pi(t))代表的是當前最佳情況的適應特征，從而可以得出單個粒子的優(yōu)化進度公式為：

(5)

其中0

定義2 群體分散度代入到粒子公式(5)中，粒子最佳的關(guān)系差距?p(t)可表為?p(t)={?p1(Pbesti,1(t)),?p2(Pbesti,2(t)),…，?PD(Pbesti,D(t)}，同時對進化公式的粒子群體離度可表為：

gst(t)={gsi,1(t),gsi,2(t),…，gsi,D(t)}=

(6)

以上公式可以總結(jié)出，gs代表粒子的離散優(yōu)化進度和種群的不同特征.假設gs的數(shù)值增加，粒子的離散優(yōu)化進度隨即增大，粒子種群的不同性則變小.假如gs=1的時候，最佳情況Pbest和現(xiàn)狀情況X一致，然而gs結(jié)果數(shù)值將繼續(xù)變化.

2 路徑規(guī)劃問題描述與建模

粒子群算法中粒子代表移動機器人運動路徑[12]，本文假設存在N條運動軌跡，粒子維度D表示出發(fā)點到終點間的路徑條數(shù).移動機器人路徑規(guī)劃過程可表示為各個路徑規(guī)劃下獲得最優(yōu)角度值的規(guī)劃過程.

(1)考慮到移動機器人的工作環(huán)境，本文選用柵格法進行模型構(gòu)建，使用的柵格法選擇規(guī)格大小相同的柵格對移動機器人運動范圍進行劃分，運動環(huán)境可借用極坐標和直角坐標相結(jié)合進行表示，極坐標長度為移動機器人從初始點到終點間的距離，角度表示運動可達到的范圍，柵格粒度大小需要根據(jù)移動機器人規(guī)格與障礙物規(guī)格進行設置.以極坐標和直角坐標為基礎(chǔ)的關(guān)系探測法如圖1所示.

圖1 極坐標與直角坐標下移動機器人路徑探測示意圖

(2)設定粒子群參數(shù)值：D表示粒子維度；M表示最大迭代次數(shù)；N表示粒子群；學習因子C1與C2以及擴張-收縮系數(shù)α，那么，本文粒子群的維度可表示為：

(7)

其中，distance(path)表示原始點到終點間的長度，lengthrobot表示移動機器人自身長度.

(3)極坐標的長度依賴于初始點與終點的距離，探測角度區(qū)間設定為[0,π/2]，則可得到：

(8)

其中，β=arccos(Ltarget/ρi)，αtop和αdown依次表示移動機器人運動可探測范圍的最大值與最小值；Ltarget表示移動機器人在直角坐標中的位置；ρL表示極坐標下相應的運動長度，且條件設置為[13]：

(9)

(4)將粒子群設為均勻分布，其中，粒子群中粒子位置與運動速度在運動區(qū)域可表示如下：

αi，j=rand*(αtop-αdown)+αdown

(10)

(5)依據(jù)極坐標與直角坐標轉(zhuǎn)換原理，可計算出移動機器人坐標值，根據(jù)粒子運動約束條件以判定規(guī)劃路徑是否可行與有效，如果判定為無效路徑，則需要重新初始化，直到獲得有效粒子位置.

3 移動機器人路徑規(guī)劃仿真與實驗驗證

3.1 路徑規(guī)劃仿真

為了驗證本文提出算法的可行性，使用仿真軟件Matlab2012b對QPSO算法進行仿真.在仿真系統(tǒng)中設定移動機器人的運動空間大小為10 m×10 m，選取的移動機器人底盤占地面積規(guī)格大小為0.3 m×0.4 m，運動的原始出發(fā)點為(0,0)，正態(tài)分布為N(30，45)，粒子群相應的維度值定為D=8，N=30，M=50，運動過程可以達到的最大線速度V為0.24 m/s，角速度W為0.2 rand/s，運動周期為0.4 s.

為了驗證本文算法的優(yōu)越性，將本文QPSO算法與PSO算法的仿真結(jié)果進行對比，設置相同的參數(shù)值，兩種算法在初始化狀態(tài)下運行50次，依次記錄每次仿真獲得的最優(yōu)路徑，并計算出50個最優(yōu)路徑選擇代價值相應的平均代價、平均耗時以及標準差.

從表1的仿真結(jié)果可知，在均勻分布D=8的情況下，使用兩種算法生成的路徑相近，在正態(tài)分布D=16的情況下，PSO算法和QPSO算法生成的路徑不相同，相比于PSO，本文方法的平均代價降低了約0.2 m，平均耗時降低了1.28 s.此種情況下，PSO算法無法找到最優(yōu)路徑，無法規(guī)劃出路徑最優(yōu)解.根據(jù)圖2和表2可知，移動機器人在正態(tài)分布N(45, 30)下粒子群的維度中對比PSO算法，本文使用的QPSO算法更加優(yōu)越.

表1 均勻分布情況下移動機器人路徑規(guī)劃仿真結(jié)果

(a)最優(yōu)路徑規(guī)劃仿真結(jié)果示意圖 (b)最優(yōu)路徑代價值收斂曲線

表2 正態(tài)分布N(45,30)下移動機器人最優(yōu)路徑規(guī)劃仿真結(jié)果

3.2 移動機器人平臺的實驗

為了測試本文算法在實際應用中的效果，將兩輪移動機器人作為本次研究目標.其中，設定的輪式移動機器人相關(guān)參數(shù)值如表3所示.

表3 輪式移動機器人相關(guān)的機構(gòu)特性值

本次實驗次數(shù)設定為100次，測試得到的路徑規(guī)劃結(jié)果如圖3所示.

圖3 QSO算法與PSO算法最優(yōu)路徑結(jié)果對比

根據(jù)圖3的實驗結(jié)果可知，QPSO算法下移動機器人路徑規(guī)劃結(jié)果優(yōu)于PSO算法，經(jīng)過測量，規(guī)劃路徑長度為4.0253 m，而使用PSO算法下移動機器人運動路徑長度為4.3813 m.主要原因為PSO在搜索路徑過程容易陷入局部最優(yōu)，但是將QPSO算法應用于移動機器人全局搜索中可以得到最優(yōu)路徑.

根據(jù)圖4和圖5的實驗測試結(jié)果可知，移動機器人在PSO算法和QPSO算法下在149次迭代次數(shù)后均可以得到局部最優(yōu)值.但是本文使用的QPSO算法在進行200次迭代后能夠跳出局部最優(yōu)值，大約在250次迭代調(diào)整后搜索到了全局最優(yōu)路徑，但是移動機器人在PSO算法下依舊陷入局部最優(yōu)路徑.根據(jù)以上分析可知，本文提出的QPSO算法在全局收斂速度上優(yōu)于PSO算法.

圖4 PSO算法收斂結(jié)果 圖5 QPSO算法收斂結(jié)果

4 結(jié) 論

本文通過對傳統(tǒng)PSO算法中個體粒子、群體離散度參數(shù)以及自然選擇法進行改進，提出了一種移動機器人路徑優(yōu)化規(guī)劃方法.在初始化分布時隨著粒子維度的不斷變化，通過分析QPSO算法下粒子群與迭代次數(shù)之間的關(guān)系，比較在不同粒子維度下傳統(tǒng)PSO算法與QPSO算法的性能.最后通過仿真實驗結(jié)果表明，與傳統(tǒng)的PSO算法路徑規(guī)劃方法對比，QPSO算法在移動機器人路徑規(guī)劃中搜索能力更強、收斂速度更快，得到的運動路徑最優(yōu).