趙甜甜, 王思明

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

0 引 言

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

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

1 環(huán)境建模

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

圖1 處理后的障礙物環(huán)境

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代表整個種群的全局極值。優(yōu)化問題的可行解能夠用每個個體粒子的位置信息表示，而適應度函數(shù)的取值很大程度上影響解的好壞；通常都要根據(jù)實際問題進行具體設計。

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

(1)

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

(2)

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

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

fiti=αLpi+βdargeri+γvi

(3)

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

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執(zhí)行完第j次趨向性、第k次復制和第l次遷徙后的新節(jié)點位置；C(i)為細菌執(zhí)行一次趨向性操作往前的步長；φ(i)為細菌翻轉后進行方向調(diào)整選定的單位步長向量；Δ(i)為隨機向量。

假設翻轉后的適應值變優(yōu)，則按照此時的方向繼續(xù)進行游走運動，直到溢出給定的最大移動步數(shù)Ns或適應值不能繼續(xù)優(yōu)化為止?；诩毦袘獧C制的適應度采用Jcc表示

(6)

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

3.1.2 復制操作

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

3.1.3 遷徙操作

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

3.2 BFO算法優(yōu)化設計

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

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

圖2 BFO算法優(yōu)化設計

4 混合算法步驟

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

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

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

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

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

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

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

5 仿真分析

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

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

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

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

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

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

表1 不同環(huán)境下各算法對比

6 結束語

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

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

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

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

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

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

[6] 梁 旭,劉才慧.基于混合粒子群算法的在線檢測路徑規(guī)劃[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.