韓 明，劉教民，吳朔媚，王敬濤

(1.石家莊學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，石家莊 050035; 2.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)

(*通信作者電子郵箱han_ming2008@126.com)

粒子群優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃算法

韓 明1,2*，劉教民2，吳朔媚1，王敬濤1

(1.石家莊學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，石家莊 050035; 2.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)

(*通信作者電子郵箱han_ming2008@126.com)

針對移動(dòng)機(jī)器人在復(fù)雜環(huán)境下采用傳統(tǒng)方法路徑規(guī)劃收斂速度慢和局部最優(yōu)問題，提出了斥力場下粒子群優(yōu)化(PSO)的移動(dòng)機(jī)器人路徑規(guī)劃算法。首先采用柵格法對機(jī)器人的移動(dòng)路徑進(jìn)行初步規(guī)劃，并將柵格法得到的初步路徑作為粒子的初始種群,根據(jù)障礙物的不同形狀和尺寸以及障礙物所占的地圖總面積確定柵格粒度的大小，進(jìn)而對規(guī)劃路徑進(jìn)行數(shù)學(xué)建模；然后根據(jù)粒子之間的相互協(xié)作實(shí)現(xiàn)對粒子位置和速度的不斷更新；最后采用障礙物斥力勢場構(gòu)造高安全性適應(yīng)度函數(shù)，從而得到一條機(jī)器人從初始位置到目標(biāo)的最優(yōu)路徑。利用Matlab平臺對所提算法進(jìn)行仿真，結(jié)果表明，該算法可以實(shí)現(xiàn)復(fù)雜環(huán)境下路徑尋優(yōu)和安全避障；同時(shí)還通過對比實(shí)驗(yàn)驗(yàn)證了算法收斂速度快，能解決局部最優(yōu)問題。

柵格法；粒子群優(yōu)化；路徑規(guī)劃；步進(jìn)因子；適應(yīng)度函數(shù)

0 引言

智能機(jī)器人研究不斷取得新的成果，機(jī)器人應(yīng)用也越來越多地滲透到社會(huì)的各個(gè)領(lǐng)域。在智能機(jī)器人的控制過程中，機(jī)器人導(dǎo)航是移動(dòng)機(jī)器人研究的一個(gè)重點(diǎn)領(lǐng)域，其中路徑規(guī)劃的研究更是機(jī)器人導(dǎo)航能力的一個(gè)重要體現(xiàn)[1]。

移動(dòng)機(jī)器人的路徑規(guī)劃主要目標(biāo)是使得機(jī)器人在從起始點(diǎn)到目標(biāo)點(diǎn)運(yùn)動(dòng)的過程中避免出現(xiàn)碰撞，因此需要尋找一條最優(yōu)的路徑實(shí)現(xiàn)機(jī)器人在移動(dòng)過程中的無碰撞運(yùn)動(dòng)[2]。

國內(nèi)外學(xué)者作了大量的研究并提出了很多方法，目前移動(dòng)機(jī)器人的路徑規(guī)劃方法主要有全局路徑規(guī)劃和局部路徑規(guī)劃[3-4],其根據(jù)傳感器獲取的信息尋找躲避障礙物的最優(yōu)路徑，并根據(jù)傳感器信息實(shí)時(shí)調(diào)整路徑尋優(yōu)的策略?？梢晥D算法[5]根據(jù)圖搜索的完備性理論可以實(shí)現(xiàn)最優(yōu)路徑搜索，但是該算法由于計(jì)算量大，收斂速度慢，尋優(yōu)的能力較差，在實(shí)時(shí)性和可靠性高的要求中無法滿足需求[6]。隨著遺傳算法和神經(jīng)網(wǎng)絡(luò)算法的深入研究，很多學(xué)者將這些啟發(fā)式的路徑規(guī)劃算法引入到了機(jī)器人的路徑規(guī)劃中實(shí)現(xiàn)局部路徑規(guī)劃[7]；但這些算法大多存在局部最優(yōu)的問題，因此為了解決這一問題需要不斷地引入新的算法實(shí)現(xiàn)路徑的最優(yōu)規(guī)劃，與此同時(shí)增加了算法的復(fù)雜度[8]。粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[9]具有計(jì)算簡單、全局尋優(yōu)能力強(qiáng)、收斂速度快等優(yōu)點(diǎn)，在各類多維連續(xù)空間優(yōu)化問題上取得了非常好的效果。許多學(xué)者對粒子群優(yōu)化算法在路徑規(guī)劃領(lǐng)域的應(yīng)用展開了研究。

文獻(xiàn)[10]首次將PSO算法引入移動(dòng)機(jī)器人路徑規(guī)劃中，該算法首先采用鏈接圖建立機(jī)器人工作空間模型，用Dijkstra 算法求得鏈接圖最短路徑,然后用PSO算法對此路徑進(jìn)行優(yōu)化，得到全局最優(yōu)路徑；但是由于鏈接圖并不能完全體現(xiàn)實(shí)際規(guī)劃環(huán)境中的信息，二次優(yōu)化后得到的路徑不一定是全局最優(yōu)路徑, 因此該方法限制了PSO算法的全局尋優(yōu)能力。文獻(xiàn)[11]利用三次Ferguson樣條算法對移動(dòng)機(jī)器人路徑規(guī)劃進(jìn)行描述，將路徑規(guī)劃問題轉(zhuǎn)化為三次樣條的參數(shù)優(yōu)化問題，為PSO算法在機(jī)器人路徑規(guī)劃中的應(yīng)用提供了新的思路；但是，由于PSO算法普遍存在早熟收斂問題使得規(guī)劃結(jié)果容易陷入局部極值。文獻(xiàn)[12]針對三次樣條早熟收斂問題，提出了具有速度變異的PSO算法，從而改善了早熟收斂問題。針對PSO算法在移動(dòng)機(jī)器人的全局路徑規(guī)劃過程中容易出現(xiàn)由于過早收斂導(dǎo)致算法陷入局部最優(yōu)的問題，文獻(xiàn)[13]提出了一種帶擾動(dòng)機(jī)制的PSO算法。當(dāng)算法在搜索最優(yōu)解的過程中陷入局部最優(yōu)時(shí)，采用粒子修正方法產(chǎn)生新的粒子替代原來的粒子，以此來引導(dǎo)算法擺脫局部最優(yōu)值，搜索可行路徑。為了充分利用PSO算法的全局尋優(yōu)能力，文獻(xiàn)[14]采用罰函數(shù)法表示粒子適應(yīng)度函數(shù)，解決過早收斂的問題；并且為了縮短算法的執(zhí)行時(shí)間，在執(zhí)行過程中加入碰撞能量測試點(diǎn)，但沒有給出碰撞和距離能量函數(shù)的權(quán)重比，因此最佳路徑的尋優(yōu)無法保證。

針對當(dāng)前移動(dòng)機(jī)器人路徑規(guī)劃中的算法收斂速度慢和局部最優(yōu)的問題，本文將斥力勢場引入PSO算法，首先采用柵格法對機(jī)器人的移動(dòng)路徑進(jìn)行初步規(guī)劃，并將柵格法得到的初步路徑作為粒子的初始種群；然后根據(jù)粒子之間的相互協(xié)作實(shí)現(xiàn)對粒子的位置和速度的不斷更新；最后采用障礙物斥力勢場構(gòu)造高安全性適應(yīng)度函數(shù)，從而得到一條機(jī)器人從開始位置到目標(biāo)的最優(yōu)路徑。

1 柵格法實(shí)現(xiàn)路徑規(guī)劃的數(shù)學(xué)建模

1.1 柵格法表示機(jī)器人工作空間

柵格法將機(jī)器人的工作空間表示成一個(gè)二維區(qū)域，該二維區(qū)域進(jìn)行柵格劃分，分解成一系列的以基本元素為單元的最小柵格，在二維區(qū)域的自由區(qū)域基本元素取值為0，在圖1中用白色表示；障礙物區(qū)域取值為1，在圖中用灰色表示，如圖1所示為機(jī)器人工作空間的柵格法表示。

設(shè)機(jī)器人在平面上運(yùn)動(dòng)的二維區(qū)域?yàn)锳S，原點(diǎn)坐標(biāo)為(0,0)，任意柵格表示為g(x,y)∈AS，其中x表示該柵格所在的行號，y表示該柵格所在的列號；S={1,2,…,n}表示所有柵格的集合。x和y方向的最大值分別為xmax和ymax，機(jī)器人行走的步長為δ，則機(jī)器人工作空間中的每行和每列的柵格數(shù)分別為Nx=xmax/δ和Ny=ymax/δ。對于任意的柵格g(xi,yi)與柵格序號集合互為映射關(guān)系，則第i個(gè)柵格可表示為：

(1)

其中：mod為模運(yùn)算，int為向下取整運(yùn)算。

1.2 確定柵格

由圖1可見，當(dāng)劃分的柵格粒度越小時(shí)，障礙物的表示越精確，但是工作空間劃分得越細(xì)所占用的存儲空間會(huì)越大，同時(shí)會(huì)導(dǎo)致算法的復(fù)雜度增加；如果選擇的柵格粒度太大又容易造成路徑規(guī)劃不準(zhǔn)確。因此在柵格法的初步規(guī)劃中，粒度大小的選擇是柵格法面臨的主要問題。

在得到機(jī)器人工作空間的地圖之后，首先根據(jù)障礙物的不同的形狀進(jìn)行剖分，其中橢圓和不規(guī)則圖形按照能覆蓋的最小長方形計(jì)算，凸多邊形則進(jìn)行三角剖分，根據(jù)剖分的結(jié)果計(jì)算地圖中障礙物所占的總面積；然后根據(jù)障礙物所占的整個(gè)地圖的總面積的比例來決定柵格的粒度大小。柵格粒度大小的計(jì)算方法如下：

(2)

圖1 機(jī)器人工作空間柵格法表示Fig. 1 Robot working space represented by grid method

1.3 路徑規(guī)劃數(shù)學(xué)建模

在XOY地圖上建立以為p0為原點(diǎn)，pend為終點(diǎn)的新的X′軸，與之垂直的為Y′軸，則原坐標(biāo)系中的點(diǎn)在新坐標(biāo)系中的表示為：

(3)

其中α為X坐標(biāo)軸與X′的夾角。

將p0pend線段作m+1垂直等分處理，將pend寫為pm+1，其中與X′垂直的平行線簇(l1,l2,…,lm)與X′的交點(diǎn)的序列(p1,p2,…,pm)即為路徑的序列，如圖2所示。

規(guī)劃路徑的長度LP為：

(4)

圖2 路徑規(guī)劃坐標(biāo)變換Fig. 2 Path planning coordinate transformation

2 改進(jìn)的PSO算法實(shí)現(xiàn)路徑優(yōu)化

2.1 粒子速度與位置更新

PSO算法是模擬鳥類覓食行為的速度-位置搜索模型，其粒子的優(yōu)劣程度由粒子的適應(yīng)度函數(shù)f(x)決定，而且每一個(gè)粒子在運(yùn)行的過程根據(jù)自身的個(gè)體極值Pbest和整個(gè)種群目前最優(yōu)解的全局極值Gbest來更新位置和速度，以在搜索空間中向更好的位置運(yùn)動(dòng)，從而搜索全局最優(yōu)解[14]。

在1.3節(jié)介紹的路徑規(guī)劃方法中采用垂直等分的形式按照式(4)進(jìn)行處理，所以采用PSO算法時(shí)的粒子維數(shù)為m，而垂線li上點(diǎn)的Y′坐標(biāo)則構(gòu)成粒子的位置編碼。

由圖2可見可將粒子定義為由起始點(diǎn)p0經(jīng)過不同的連接線到達(dá)終點(diǎn)pend的距離，即每一個(gè)粒子代表一段距離。粒子的適應(yīng)度函數(shù)即為路徑長度表達(dá)式(4)，因此當(dāng)適應(yīng)度函數(shù)的值越小則得到的解即為最優(yōu)解。

在m維空間中，第i個(gè)粒子的位置可表示為向量Xi=(xi1,xi2,…,xim)，通過向量Xi可以確定每個(gè)粒子點(diǎn)在鏈接線上的坐標(biāo)，計(jì)算相鄰兩點(diǎn)之間的距離，從而計(jì)算適應(yīng)度值。根據(jù)適應(yīng)度值的大小決定當(dāng)前的解是否為局部最優(yōu)，如果是則替換歷史局部最優(yōu)Pbest。

局部最優(yōu)Pbest的適應(yīng)值隨著迭代的進(jìn)行不斷進(jìn)行更新;而全局最優(yōu)Gbest則是與各個(gè)Pbest進(jìn)行比較，如果局部最優(yōu)Pbest的適應(yīng)值小于全局最優(yōu)Gbest則更新全局最優(yōu)的值為該P(yáng)best的值。

為了得到移動(dòng)機(jī)器人的全局最優(yōu)路徑，需要在計(jì)算過程中不斷更新粒子的速度和位置，其中粒子i表示為向量Xi=(xi1,xi2,…,xim)，粒子的飛行速度為Vi=(νi1,νi2…,νim)。則粒子的速度和位置更新公式如下：

(5)

其中：vi, j(t+1)和xi, j(t)分別表示t時(shí)刻第i個(gè)粒子在j維的速度和位置；ω為慣性權(quán)重因子，ω取值越大則算法具有較高的全局搜索能力，反之則具有較強(qiáng)的局部搜索能力。慣性權(quán)重ω隨著迭代次數(shù)的增加線性減少，可以使粒子種群在開始時(shí)進(jìn)行大范圍的最優(yōu)解空間的搜索，然后隨著迭代次數(shù)的增加逐漸縮小搜索范圍，從而加強(qiáng)搜索現(xiàn)有解空間的能力。因此本文設(shè)計(jì)慣性權(quán)重ω的取值方法如下：

其中：ω的最大值和最小值在本文的實(shí)驗(yàn)中取ωmax=0.9，ωmin=0.4；ki為當(dāng)前的迭代次數(shù)，kmax為最大迭代次數(shù)。

c1、c2分別為個(gè)體和全局的加速因子，即每個(gè)粒子受到個(gè)體極值Pbest和全局極值Gbest位置吸引的加速度的權(quán)重。加速因子使得每個(gè)粒子都具有自我總結(jié)并向群體中其他優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而使粒子在前進(jìn)的過程中向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)的全局最優(yōu)點(diǎn)靠近。其中c1調(diào)節(jié)粒子飛向自身最好位置方向的步長，c2調(diào)節(jié)粒子飛向全局最好位置方向的步長。r1、r2為隨機(jī)數(shù)，一般取[0,1]。Pi, j(t)和Gj(t)分別表示到t時(shí)刻為止第i個(gè)粒子在j維分量搜索到的個(gè)體最優(yōu)位置以及整個(gè)種群粒子的第j維分量搜索到的最優(yōu)位置。

2.2 構(gòu)造高安全性適應(yīng)度函數(shù)

將人工勢場原理引入到適應(yīng)度函數(shù)的構(gòu)建中，使移動(dòng)機(jī)器人在人工勢場中移動(dòng)時(shí)，同時(shí)受到目標(biāo)位置的引力場的引力和障礙物的斥力場的斥力兩種力的共同作用。由于斥力場與障礙物有關(guān)，因此，機(jī)器人在運(yùn)動(dòng)的過程中距離障礙物越近則產(chǎn)生的斥力就越大，同時(shí)機(jī)器人碰觸障礙物的危險(xiǎn)系數(shù)越高。由于引力場的作用與機(jī)器人的運(yùn)動(dòng)目標(biāo)位置有關(guān)，因此從算法的復(fù)雜度考慮，本文構(gòu)建高安全性適應(yīng)度函數(shù)時(shí)只考慮斥力場的作用。

障礙物附近的斥力場函數(shù)表示為：

(6)

其中：η為障礙物的斥力系數(shù)；p為機(jī)器人在空間中移動(dòng)時(shí)的任意位置，ρ(p)為移動(dòng)機(jī)器人到障礙物的最短距離；ρ0為障礙物的斥力場的作用距離。

為了保證在整個(gè)勢力場中只有在目標(biāo)點(diǎn)位置時(shí)全局最小，因此在式(6)的基礎(chǔ)上引入機(jī)器人與目標(biāo)點(diǎn)的相對位置，即在原有的基礎(chǔ)上乘以一個(gè)距離因子:

Urep=

(7)

斥力為斥力勢函數(shù)的負(fù)梯度，則可得斥力為：

Frep=-grad(Urep)=

(8)

機(jī)器人在移動(dòng)過程中由于路徑點(diǎn)的安全性不僅與障礙物的遠(yuǎn)近有關(guān)，還與空間中障礙物的分布密集程度有關(guān)，因此由式(8)可得，移動(dòng)機(jī)器人在空間中的任意位置xi, j處的安全度為：

safei, j=

(9)

其中：s為模板窗口尺寸因子，并且窗口的實(shí)際尺寸為(2s+1)2，當(dāng)s減小時(shí)，窗口中會(huì)包含較少的障礙物信息，此時(shí)安全系數(shù)safei, j增大；sign(m,n)為點(diǎn)xi+m, j+n處的障礙物標(biāo)志，當(dāng)xi+m, j+n點(diǎn)為障礙物時(shí)sign(m,n)=1，否則，sign(m,n)=0。因此可由式(9)計(jì)算出機(jī)器人在移動(dòng)的過程中所處位置的安全性系數(shù)。

則由式(9)可得路徑Ppath的安全度為：

(10)

由式(4)和式(10)可得路徑Ppath的優(yōu)化函數(shù)為：

fP=ω1LP+ω2MP

(11)

通過調(diào)整加權(quán)因子ω1和ω2來調(diào)整LP和MP在路徑規(guī)劃中所占的比重，從而選擇路徑和安全性均適中的路線。

2.3 路徑優(yōu)化算法實(shí)現(xiàn)

設(shè)定義n個(gè)m維粒子，采用式(11)作為第i個(gè)粒子的適應(yīng)度函數(shù)：

(12)

利用適應(yīng)度函數(shù)對所得的路徑集合進(jìn)行優(yōu)化, 從而求解全局最優(yōu)路徑，適應(yīng)度函數(shù)得到的值越小，所得的解越優(yōu)。

算法實(shí)現(xiàn)的具體步驟如下：

(13)

由式(5)得到粒子的第i個(gè)粒子第j維的初始速度和位置為：

(14)

步驟5 對每個(gè)粒子按照式(5)中的位置和式(6)的速度進(jìn)行更新，注意粒子兩端和邊界的約束。

步驟7 如果達(dá)到了最大迭代次數(shù)或者是最小精度要求，則輸出最優(yōu)路徑，否則轉(zhuǎn)到步驟4繼續(xù)執(zhí)行。

算法流程如圖3所示。

圖3 本文算法流程Fig. 3 Flow chart of the proposed algorithm

3 仿真與分析

為了驗(yàn)證算法的有效性，以Visual studio 2010為平臺，C# 語言為編程環(huán)境進(jìn)行仿真。實(shí)驗(yàn)的硬件平臺為：Intel Core i5 3.20 GHz CPU；4 GB內(nèi)存；500 GB硬盤，Windows 10操作系統(tǒng)。

為了驗(yàn)證本文算法的有效性，在相同的環(huán)境模型下將本文方法與線性遞減慣性權(quán)重粒子群優(yōu)化算法(Linearly Decreasing Weight Particle Swarm Optimization, LDWPSO)[13]進(jìn)行對比實(shí)驗(yàn)。

3.1 最優(yōu)路徑與收斂性比較

采用1.2節(jié)的方法確定柵格，經(jīng)過多次對不同實(shí)驗(yàn)環(huán)境(包括本文的實(shí)驗(yàn)環(huán)境1、2以及圖8所示環(huán)境)的測試，取lmax=20，lmin=3時(shí)柵格粒度較適合實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)環(huán)境1和2相對障礙物較少，因此柵格粒度較大；而圖8中的實(shí)驗(yàn)環(huán)境下障礙物較密，因此柵格粒度較小。

實(shí)驗(yàn)環(huán)境1參數(shù)描述：實(shí)驗(yàn)環(huán)境采用15×15方格的環(huán)境，環(huán)境中障礙物數(shù)目為42，每一個(gè)方格表示一個(gè)障礙物。移動(dòng)機(jī)器人運(yùn)動(dòng)起點(diǎn)為(0,0)，終點(diǎn)位置為(14,14)。

如圖4所示為本文算法與LDWPSO的最優(yōu)解對比結(jié)果。LDWPSO算法在第32次迭代時(shí)找到了最優(yōu)解，本文算法則是在第25次迭代時(shí)已經(jīng)找到了符合終止條件的最優(yōu)解。因此從算法的收斂性上來看本文算法優(yōu)于LDWPSO算法，并且尋找的最優(yōu)路徑的柵格長度本文算法為17，LDWPSO算法為19。

圖4 環(huán)境1最優(yōu)路徑對比Fig. 4 Comparison of optimal path in environment 1

圖5給出了本文算法的避障過程，在由第17次向第18次迭代的過程中，能夠明顯地躲避障礙，并且在搜索的過程中搜索范圍較大，能夠跳出局部最優(yōu)。

圖5 本文算法的第17次迭代和第18次迭代的避障情況Fig. 5 Obstacle avoidance of 17th and 18th iterations by the proposed algorithm

實(shí)驗(yàn)環(huán)境2參數(shù)描述：實(shí)驗(yàn)環(huán)境采用10×10方格的環(huán)境，環(huán)境中障礙物數(shù)目為31，每一個(gè)方格表示一個(gè)障礙物，并且分布無序；移動(dòng)機(jī)器人的起始位置為(0,0)，終點(diǎn)位置為(9,9)。

由圖6可以看出本文算法克服了局部最優(yōu)的缺陷并成功搜索到了最優(yōu)路徑，本文算法搜索路徑的柵格長度為12，而LDWPSO算法則為14。

圖6 環(huán)境2最優(yōu)路徑對比Fig. 6 Comparison of optimal path in environment 2

圖7給出了兩種算法的收斂性比較，可以看出：本文算法在50次的迭代過程中都在第6次找到了局部最優(yōu)解，第12次迭代之后找到了最優(yōu)解，并穩(wěn)定在最優(yōu)解；而LDWPSO算法則在第17次達(dá)到了局部最優(yōu)并且沒有跳出局部最優(yōu)解。因此從算法的收斂性和克服局部最優(yōu)解方面本文算法優(yōu)于LDWPSO算法。

3.2 本文算法不同實(shí)驗(yàn)環(huán)境最優(yōu)路徑對比

在本實(shí)驗(yàn)中采用相同的實(shí)驗(yàn)地圖，但是實(shí)驗(yàn)環(huán)境中的障礙物數(shù)目、位置以及狀態(tài)不同。實(shí)驗(yàn)結(jié)果如圖8所示，由圖可以看出對于不同的實(shí)驗(yàn)環(huán)境，本文算法都能得到最優(yōu)的路徑規(guī)劃，說明本文算法對于復(fù)雜環(huán)境具有較高的適應(yīng)性。

圖7 兩種算法收斂性比較Fig. 7 Convergence comparison of two algorithms

圖8 不同環(huán)境的最優(yōu)路徑規(guī)劃Fig. 8 Optimal path planning in different environments

4 結(jié)語

本文針對傳統(tǒng)的粒子群優(yōu)化(PSO)算法實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)劃中的局部極值問題以及適應(yīng)度函數(shù)在計(jì)算過程中的粒子安全性問題，提出了斥力勢場下粒子群優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃算法，該算法為移動(dòng)機(jī)器人在復(fù)雜環(huán)境下的路徑規(guī)劃提供了一種有效的選擇。該算法主要有以下特點(diǎn)：1)該算法利用柵格法實(shí)現(xiàn)機(jī)器人路徑的初步規(guī)劃，并將初始規(guī)劃的路徑作為粒子的初始種群；2)根據(jù)粒子之間的相互協(xié)作實(shí)現(xiàn)對粒子的位置和速度的不斷更新，解決路徑規(guī)劃中的局部極值問題；3)采用障礙物斥力勢場構(gòu)造高安全性適應(yīng)度函數(shù)。通過實(shí)驗(yàn)仿真驗(yàn)證本文算法能獲得路徑尋優(yōu)的最優(yōu)解，并且算法的收斂速度快。

References)

[1] 朱大奇,顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述 [J].控制與決策,2010,25(7):961-967. (ZHU D Q, YAN M Z. Survey on technology of mobile robot path planning [J]. Control and Decision, 2010, 25(7): 961-967.)

[2] 蔡自興,賀漢根,陳虹.未知環(huán)境中移動(dòng)機(jī)器人導(dǎo)航控制理論與方法[M]. 北京：科學(xué)出版社,2009:8-12. (CAI Z X, HE H G, CHEN H, Mobile robot navigation in unknown environment control theory and method [M]. Beijing: Science Press,2009:8-12.)

[3] CLERC M, KENNEDY J. The particle swarm-explosion, stability and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computer, 2002, 6(1): 58-73.

[4] SHI P, HUA J N. Mobile Robot dynamic path planning based on artificial potential field approach [J]. Advanced Materials Research, 2012, 490-495: 994-998．

[5] SUD A, ANDERSEN E, CURTIS S, et al. Real-time path planning in dynamic virtual environments using multiagent navigation graphs [J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 4(3): 526-538.

[6] TAVARES R S, MARTINS T C, TSUZUKI M S G. Simulated annealing with adaptive neighborhood: a case study in off-line robot path planning [J]. Expert Systems with Applications, 2011, 38(4): 2951-2965.

[7] GHATEE M, MOHADES A. Motion planning in order to optimize the length and clearance applying a Hopfield neural network [J]. Expert Systems with Applications, 2009, 36(3): 4688-4695.

[8] 杜宗宗,劉國棟.基于遺傳模擬退火算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)仿真,2009,26(12):118-121. (DU Z Z, LIU G D. Path planning of mobile robot based on genetically simulated annealing algorithm[J]. Computer Simulation, 2009, 26(12): 118-121.)

[9] ZENG N, ZHANG H, CHEN Y, et al. Path planning for intelligent robot based on switching local evolutionary PSO algorithm [J]. Assembly Automation, 2016, 36(2): 120-126.

[10] 秦元慶,孫德寶,李寧，等.基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].機(jī)器人,2014,26(3):222-225. (QIN Y Q, SUN D B, LI N, et al. Path planning for mobile robot based on particle swarm optimization [J]. Robot, 2014, 26(3): 222-225.)

[11] SHENG J W, HE G H, GUO W B et al. An improved artificial potential field algorithm for virtual human path planning [C]// Proceedings of the 2010 International Conference on Entertainment for Education Digital Techniques & Systems, LNCS 6249. Berlin: Springer-Verlag, 2010: 592-601

[12] SETHANAN K, NEUNGMATCHA W. Multi-objective particle swarm optimization for mechanical harvester route planning of sugarcane field operations [J]. European Journal of Operational Research, 2016, 252(3): 969-984.

[13] TANG Z, ZHOU Y. A glowworm swarm optimization algorithm for uninhabited combat air vehicle path planning [J]. Journal of Intelligent Systems, 2014, 24(1): 69-83.

[14] TANG B, ZHU Z, LUO J. A convergence-guaranteed particle swarm optimization method for mobile robot global path planning [J]. Assembly Automation, 2017, 37(1): 114-129.

This work is partially supported by the Science and Technology Plan Projects of Hebei Province (15220327, 16222101D- 2), the Youth Topnotch Talent Program of Hebei Universities and Colleges (BJ2017105).

HANMing, born in 1984, Ph. D., lecturer. His research interests include intelligence robot, pattern recognition and control.

LIUJiaomin, born in 1958, Ph. D., professor. His research interests include intelligence control, pattern recognition.

WUShuomei, born in 1977, M. S., lecturer. Her research interests include pattern recognition, machine vision.

WANGJingtao, born in 1984, M. S., assistant. Her research interests include intelligence computing, pattern recognition.

Pathplanningalgorithmofmobilerobotbasedonparticleswarmoptimization

HAN Ming1,2*, LIU Jiaomin2, WU Shuomei1, WANG Jingtao1

(1.CollegeofComputerScienceandEngineering,ShijiazhuangUniversity,ShijiazhuangHebei050035,China；2.SchoolofInformationScienceandEngineering,YanshanUniversity,QinhuangdaoHebei066004,China)

Concerning the slow convergence and local optimum of the traditional robot path planning algorithms in complicated enviroment, a new path planning algorithm for mobile robots based on Particle Swarm Optimization (PSO)algorithm in repulsion potential field was proposed. Firstly, the grid method was used to give a preliminary path planning of robot, which was regarded as the initial particle population. The size of grids was determined by the obstacles of different shapes and sizes and the total area of obstacles in the map, then mathematical modeling of the planning path was completed. Secondly, the particle position and speed were constantly updated through the cooperation between particles. Finally, the high-security fitness function was constructed using the repulsion potential field of obstacles to obtain an optimal path from starting point to target of robot. Simulation experiment was carried out with Matlab. The experimental results show that the proposed algorithm can implement path optimization and safely avoid obstacles in a complex environment; the contrast experimental results indicat that the proposed algorithm converges fast and can solve the local optimum problem.

grid method; Particle Swarm Optimization (PSO); path planning; progress factor; fitness function

TP391; TP18

A

2017- 01- 17;

2017- 03- 05。

河北省科技計(jì)劃項(xiàng)目(15220327, 16222101D- 2)；河北省高等學(xué)校青年拔尖人才計(jì)劃項(xiàng)目(BJ2017105)。

韓明(1984—)，男，河北行唐人，講師，博士，CCF會(huì)員，主要研究方向：智能機(jī)器人、模式識別與控制； 劉教民(1958—)，男，河南西峽人，教授，博士生導(dǎo)師，博士，CCF會(huì)員，主要研究方向：智能控制、模式識別； 吳朔媚(1977—)，女，河北邢臺人，講師，碩士，主要研究方向：模式識別、機(jī)器視覺； 王敬濤(1984—)，女，河北邯鄲人，助教，碩士，主要研究方向：智能計(jì)算、模式識別。

1001- 9081(2017)08- 2258- 06

10.11772/j.issn.1001- 9081.2017.08.2258