趙甜甜, 王思明

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

0 引 言

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

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

1 環(huán)境建模

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

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

2 PSO算法

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

粒子的位置與速度以迭代方式進(jìn)行更新

(1)

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

(2)

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

第i個(gè)粒子的適應(yīng)值函數(shù)即為對(duì)路徑長(zhǎng)度與路徑危險(xiǎn)系數(shù)以及粒子當(dāng)前速度的共同約束，適應(yīng)度函數(shù)定義為

fiti=αLpi+βdargeri+γvi

(3)

式中α，β，γ為對(duì)路徑長(zhǎng)度、粒子危險(xiǎn)系數(shù)及粒子當(dāng)前速度的加權(quán)系數(shù)。

3 BFO算法

3.1 BFO算法的基本操作

3.1.1 趨向性操作

細(xì)菌的趨向性操作以游走和翻轉(zhuǎn)兩種運(yùn)動(dòng)形式存在。趨化操作的步驟是：細(xì)菌先隨機(jī)選擇一個(gè)方向，然后向前游走一個(gè)單位步長(zhǎng)，此時(shí)計(jì)算該位置的適應(yīng)度值，如果適應(yīng)度值劣于上一次位置的適應(yīng)值，則隨機(jī)選擇一個(gè)方向翻轉(zhuǎn)。翻轉(zhuǎn)按照式(4)更換

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

(4)

(5)

式中P(i,j,k,l)為細(xì)菌個(gè)體i執(zhí)行完第j次趨向性、第k次復(fù)制和第l次遷徙后的新節(jié)點(diǎn)位置；C(i)為細(xì)菌執(zhí)行一次趨向性操作往前的步長(zhǎng)；φ(i)為細(xì)菌翻轉(zhuǎn)后進(jìn)行方向調(diào)整選定的單位步長(zhǎng)向量；Δ(i)為隨機(jī)向量。

假設(shè)翻轉(zhuǎn)后的適應(yīng)值變優(yōu)，則按照此時(shí)的方向繼續(xù)進(jìn)行游走運(yùn)動(dòng)，直到溢出給定的最大移動(dòng)步數(shù)Ns或適應(yīng)值不能繼續(xù)優(yōu)化為止?；诩?xì)菌感應(yīng)機(jī)制的適應(yīng)度采用Jcc表示

(6)

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

3.1.2 復(fù)制操作

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

3.1.3 遷徙操作

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

3.2 BFO算法優(yōu)化設(shè)計(jì)

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

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

圖2 BFO算法優(yōu)化設(shè)計(jì)

4 混合算法步驟

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

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

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

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

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

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

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

5 仿真分析

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

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

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

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

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

表1給出了在不同的環(huán)境下，PSO，BFO及混合算法執(zhí)行相同任務(wù)的相關(guān)特征值?；旌纤惴軌蛴行У乜s短最優(yōu)路徑長(zhǎng)度與搜索時(shí)間。

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

6 結(jié)束語(yǔ)

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

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

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

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

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

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

[6] 梁 旭,劉才慧.基于混合粒子群算法的在線檢測(cè)路徑規(guī)劃[J].國(guó)外電子測(cè)量技術(shù),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.