基于改進PSO算法的移動機器人路徑規劃*

趙甜甜, 王思明

(蘭州交通大學 自動化與電氣工程學院，甘肅 蘭州 730070)

0 引 言

近年來，機器人技術發展迅猛，尤其是移動機器人在港口貨物搬運、倉儲物流方面取得了相當的成果。但工作任務的多節點特性使得移動機器人的路徑規劃成為其研究領域的重要分支。目前，粒子群優化(particle swarm optimization,PSO)算法、蟻群算法[1]、遺傳算法、人工勢場法是路徑規劃常用的方法。PSO算法的優點是計算量小，實時性好，結構簡單，但容易陷入局部最優解產生死鎖現象。文獻[2]設計了一種將雙混沌映射與自適應PSO算法相結合的混合算法，并通過仿真測試驗證了其在解決傳統PSO算法容易陷入局部最優點的良好性能[3,4]。文獻[5,6]針對實際的工業問題，分別提出了基于萊維飛行的PSO算法和混沌優化與基本PSO算相結合的路徑規劃方法，并將其成功應用。

本文針對目前PSO算法在移動機器人路徑規劃方面存在的缺陷[7,8]，提出了一種基于PSO算法和細菌覓食優化(bacterial foraging optimization,BFO)算法混合的路徑規劃算法，BFO算法中細菌以一定的概率遷徙到新的空間區域，其搜索方向隨機變換，因此BFO算法全局搜索能力強[9]。基于此，本文采用PSO算法對機器人所處環境中的障礙物進行全局路徑規劃；在粒子群迭代的算法過程中使用BFO算法對機器人所處環境中的障礙物進行局部路徑規劃，并利用MATLAB仿真驗證了混合算法的有效性和可行性。

1 環境建模

本文研究對象是機器人在已知環境下的路徑規劃，實際環境中的障礙物多是不規則的，為了便于研究將障礙物的各個邊切線連接起來等效為矩形、三角形等規則形狀。如圖1所示,黑白二值位圖代表機器人的運動場景，其中,障礙區為黑色，自由通行區為白色。在實際情況中機器人先通過傳感器獲取所處位置的環境信息，然后用MATLAB中的IMREAD命令將障礙物信息用矩陣表示；在矩陣中利用像素灰度值為255的點代表白色自由通行區域，而像素灰度值為0的點代表黑色障礙物區域。

圖1 處理后的障礙物環境

2 PSO算法

假設存在一個能夠搜索的n維空間，種群由m個單獨粒子組成，并記為X=[x1,…,xi,…,xm]T,其中，第i個個體粒子的位置信息為xi=[xi1,xi2,…,xin]T；速度信息為vi=[vi1,vi2,…,vin]T；每一個粒子的個體極值表示為Pi=[pi1,pi2,…,pin]T；而用Pg=[pg1,pg2,…,pgn]T代表整個種群的全局極值。優化問題的可行解能夠用每個個體粒子的位置信息表示，而適應度函數的取值很大程度上影響解的好壞；通常都要根據實際問題進行具體設計。

粒子的位置與速度以迭代方式進行更新

(1)

本文定義粒子的危險性系數為粒子各維的危險性系數之和

(2)

式中fi為粒子距離障礙物的最短距離之和，若無障礙物，則危險性系數為0。

第i個粒子的適應值函數即為對路徑長度與路徑危險系數以及粒子當前速度的共同約束，適應度函數定義為

fiti=αLpi+βdargeri+γvi

(3)

式中α，β，γ為對路徑長度、粒子危險系數及粒子當前速度的加權系數。

3 BFO算法

3.1 BFO算法的基本操作

3.1.1 趨向性操作

細菌的趨向性操作以游走和翻轉兩種運動形式存在。趨化操作的步驟是：細菌先隨機選擇一個方向，然后向前游走一個單位步長，此時計算該位置的適應度值，如果適應度值劣于上一次位置的適應值，則隨機選擇一個方向翻轉。翻轉按照式(4)更換

P(i,j+1,k,l)=P(i,j,k,l)+C(i)φ(i)

(4)

(5)

式中P(i,j,k,l)為細菌個體i執行完第j次趨向性、第k次復制和第l次遷徙后的新節點位置；C(i)為細菌執行一次趨向性操作往前的步長；φ(i)為細菌翻轉后進行方向調整選定的單位步長向量；Δ(i)為隨機向量。

假設翻轉后的適應值變優，則按照此時的方向繼續進行游走運動，直到溢出給定的最大移動步數Ns或適應值不能繼續優化為止。基于細菌感應機制的適應度采用Jcc表示

(6)

式中P(j,k,l)= {θi(j,k,l)|i=1,2,…,S}為菌群；dattract為引力深度；wattract為引力寬度；hrepellant為斥力高度；wrepellant為斥力寬度。在細菌感知規則的作用下，細菌的最終適應度將包含了細菌的感知適應度Jcc值。

3.1.2 復制操作

細菌的復制機會完全取決于其能量值的高低。為了保持種群數量穩定及盡可能地減少算法的運算量，規定了一種對半復制規則，不斷淘汰能量低于50 %的細菌個體。因此，在BFO復制算子中一般設定細菌的規模數為偶數。

3.1.3 遷徙操作

假設某個細菌完成了相應的繁殖活動，則賦予其一個進行遷徙的概率Ped，每一個細菌個體會隨機產生一個[0,1]區域上的隨機數Rand，若Rand

3.2 BFO算法優化設計

在執行優化算法的趨化操作步驟時，細菌隨機翻轉行為影響了細菌的尋優時間數(使其變長)。為了解決這一問題，引入具有環境感知能力的群體協作概念，保證了BFO算法尋優速度和精度與算法復雜度之間的平衡。

在算法的趨化算子中，細菌具有自我判斷、自動調整的目標空間感知能力。為了提高細菌個體的尋優能力，將按照其適應度值的大小劃分搜索方式：優于適應度值80 %的，追蹤最優細菌個體進行搜索；劣于適應度值80 %的，通過追蹤細菌群體中心位置進行搜索；如果兩種方式均失效，則隨機搜索；隨機搜索失敗，則將搜索方向調轉180°，保證了算法具有一定的收斂速度。算法流程如圖2。

圖2 BFO算法優化設計

4 混合算法步驟

1)定義群體及個體的各變量：c1，c2為學習因子；w為慣性權重參數；Kmax為最大進化代數；X(k)為隨機產生粒子群。

將當前進化代數的初始化值設為k=1，而粒子的初始位置和初始速度分別用x(k)，v(k)表示，并規定個體繼承屬性，即原始最優位置(個體極值)也為初始位置。

2)將粒子當前位置信息代入適應度函數計算其當前適應值大小，群體極值的大小取決于適應度值最優的粒子位置信息。

3)在式(1)的作用下，不斷計算每個粒子的位置信息和速度大小，生成下一代種群X(k+1)。

4)遍歷比較粒子個體極值與不斷更新后每個粒子的當前位置適應值，將適應值優的粒子當前位置作為其歷史最優位置。

5)遍歷對比所有粒子的個體極值與群體極值，將群體粒子最優位置用極值比較好的粒子當前位置信息替代；在迭代過程中，PSO算法的信息共享機制是算法陷入局部極值的主要原因。BFO算法中的趨化、遷徙操作的引入將有效改善PSO算法的全局搜索水平和收斂快速性，用來擴大搜索目標區域的粒子移動方向和前進步長，則可以根據翻轉和游動2種方式來實現，避免其陷入局部最優解；如果粒子的遷徙概率滿足遷徙條件，則將該粒子在目標區域隨機擴散，保證種群有一定大小的搜索范圍。

6)當滿足迭代要求時，若k=Kmax，結束程序，此時會找到全局的較優解；否則，令k=k+1，返回步驟(3)。

5 仿真分析

利用MATLAB軟件驗證本文提出的PSO算法與BFO算法相結合的混合算法在移動機器人路徑規劃方面的可行性，并與單獨的細菌算法和PSO算法對比。所選的參數如下：粒子數目m=50、學習因子c1=c2=1.531 2、最大迭代次數Kmax=1 000；細菌個數S=50、引力深度(吸引劑數量)dattractant=0.05、引力寬度(吸引劑的釋放速度)ωattractant=0.05、斥力高度(排斥劑的數量)hrepellant=0.05、斥力寬度(排斥劑的釋放速度)ωrepellant=0.05、復制的分裂數Sr=S/2、細菌的遷徙概率Ped=0.25。

圖3(a)、圖3(b)分別為傳統的PSO算法、混合算法在地圖模型一環境下的路徑規劃搜索軌跡，2種算法的迭代次數、適應值曲線如圖3(c)所示。對比圖3(a)～圖3(c)可以看出，迭代次數在150以前，本文所提的混合算法路徑規劃結果在收斂速度、路徑長短及適應值明顯優于(適應值斜率較大)原始的PSO算法。粒子在坐標(250,150)遇到障礙物時，圖3(b)的原始PSO算法陷入了局部最優值，而不是全局最優；對比圖3(c)的混合算法，粒子跳出局部最優得到了全局最優。

圖3 地圖一模型2種算法路徑規劃效果對比

在地圖二模型中，采用BFO法、混合算法的路徑規劃分別如圖4(a)、圖4(b)所示，2種算法的迭代次數、適應值曲線如圖4(c)所示。由圖4(a)～圖4(c)可以看出，在迭代次數小于200時，混合算法的適應值基本趨于最優，而BFO算法由于搜索效率低，導致迭代時間長，并且得到的路徑適應度降低。說明本文所設計的混合算法很好地提高了機器人對最優值的全局搜索能力和收斂速度。

圖4 地圖二模式下2種算法路徑規劃效果對比

表1給出了在不同的環境下，PSO，BFO及混合算法執行相同任務的相關特征值。混合算法能夠有效地縮短最優路徑長度與搜索時間。

表1 不同環境下各算法對比

6 結束語

以移動機器人為研究對象，將BFO算法的趨化、遷徙和復制操作引入到PSO算法中，得到一種具有全局搜索能力和快速收斂的混合路徑規劃算法。實驗過程中分別使用PSO算法和BFO法對移動機器人進行全局路徑規劃，再與兩者混合后的算法作對比分析。仿真研究表明，與傳統的PSO算法相比，混合算法可以有效找到最優路徑，并具有收斂速度快的特點。同時，本文算法陷入死循環的概率很小，可以有效避免陷入局部最優，在移動機器人路徑規劃的應用中具有一定的參考性和可行性。

[1] 何少佳,史劍清,王海坤.基于改進蟻群粒子群算法的移動機器人路徑規劃[J].桂林理工大學學報,2014,34(4):765-770.

[2] 李明皓.基于混合離散粒子群算法的焊接機器人路徑規劃[D].上海：華東理工大學,2014.

[3] 張萬緒,張向蘭,李 瑩,等.基于改進粒子群算法的智能機器人路徑規劃[J].計算機應用,2014,34(2):510-513.

[4] 翁理國,紀壯壯,夏 旻,等.基于改進多目標粒子群算法的機器人路徑規劃[J].系統仿真學報,2014,26(12):2892-2898.

[5] 王學武,嚴益鑫,顧幸生.基于萊維飛行粒子群算法的焊接機器人路徑規劃[J].控制與決策,2017,32(2):373-377.

[6] 梁 旭,劉才慧.基于混合粒子群算法的在線檢測路徑規劃[J].國外電子測量技術,2015(12):30-34.

[7] Wang J,Wu L J.Robot path planning based on artificial fish swarm algorithm under a known environment[J].Advanced Materials Research,2014,989-994:2467-2469.

[8] Mandal P,Barai R K,Maitra M,et al.Path planning of autonomous mobile robot: A new approach[C]∥International Confe-rence on Intelligent Systems and Control,IEEE,2013:238-243.

[9] Zhang Y,Gong D W,Zhang J H.Robot path planning in un-certain environment using multi-objective particle swarm optimization[J].Neurocomputing,2013,103(2):172-185.