王 慧， 王光宇， 潘德文

(1.遼寧工程技術(shù)大學 機械工程學院，遼寧 阜新 123000；2.沈陽職業(yè)技術(shù)學院，遼寧 沈陽 110045)

基于改進粒子群算法的移動機器人路徑規(guī)劃

王 慧1， 王光宇1， 潘德文2

(1.遼寧工程技術(shù)大學 機械工程學院，遼寧 阜新 123000；2.沈陽職業(yè)技術(shù)學院，遼寧 沈陽 110045)

為了提高復雜環(huán)境下移動機器人的精準導航作用，提出了移動機器人路徑規(guī)劃的改進粒子群優(yōu)化(PSO)算法，即利用粒子個體極值的加權(quán)平均值，同時加入慣性權(quán)重。建立了移動機器人工作環(huán)境的柵格模型，利用Matlab軟件進行移動機器人路徑規(guī)劃仿真分析。仿真結(jié)果表明:改進后的粒子群算法容易使粒子移動到最佳位置，加強了全局尋優(yōu)能力，在復雜環(huán)境中搜索路徑性能優(yōu)于傳統(tǒng)算法。

移動機器人； 路徑規(guī)劃； 改進粒子群算法

0 引 言

智能移動機器人導航任務(wù)包括定位、避障和路徑規(guī)劃。移動機器人路徑規(guī)劃是指機器人在工作環(huán)境中能夠躲開障礙，基于優(yōu)化準則從起始位置到目標位置的無碰撞、安全的運動路徑搜索[1]。粒子群算法是利用生物群落信息共享的進化優(yōu)勢思想，通過個體之間的相互合作來尋找全局最優(yōu)解[2]。近年來，傳統(tǒng)的粒子群算法在移動機器人路徑規(guī)劃中取得了很好的效果，但傳統(tǒng)的粒子群優(yōu)化算法早熟收斂，容易陷落局部最優(yōu)解和收斂速度慢等問題，很難找到全局最優(yōu)的移動機器人路徑規(guī)劃。

西安科技大學的李珊利用標準粒子群優(yōu)化算法對機器人路徑進行研究，在粒子速度更新公式中引入一個進步因子項，并對超出初始空間范圍的粒子重新進行隨機初始化。但實驗仿真的模擬環(huán)境比較簡單，不具實際工況[3]。燕山大學的陳衛(wèi)東利用模糊算法對移動機器人路徑進行規(guī)劃，仿真實驗同樣不具工廠實際工況[4]。

考慮到粒子群算法和移動機器人路徑規(guī)劃有著一種本質(zhì)上的關(guān)系，本文將粒子群算法引入到移動機器人路徑規(guī)劃，并將傳統(tǒng)粒子群算法進行改進，以此提高移動機器人路徑搜索的速度，并通過仿真驗證其有效性和可行性。

1 移動機器人路徑規(guī)劃模型的建立

1.1 移動機器人工作環(huán)境建模

移動機器人模型如圖1所示。

圖1 移動機器人模型

柵格法是一種平面移動機器人運動軌跡規(guī)劃的抽象模型，是研究平面移動機器人運動路徑規(guī)劃的最常用的方法之一[5～7]。本文采用柵格法建立工作環(huán)境模型，將粒子群優(yōu)化算法直接應(yīng)用于柵格法，獲得粒子群算法應(yīng)用于移動機器人的全局最優(yōu)路徑。

本文利用柵格地圖進行移動機器人路徑規(guī)劃，避免了在處理障礙物邊界時計算復雜的問題。從柵格法的原理可知，網(wǎng)格的尺寸越小，所表示的障礙越精確，也將占據(jù)較大的存儲空間，算法的搜索范圍按照指數(shù)增大。同時網(wǎng)格的尺寸越小，將大大增大計算量，不利于系統(tǒng)的實時性；網(wǎng)格尺寸太大，路徑規(guī)劃的準確性降低，將造成對環(huán)境描述的精確性大大增降低，甚至將造成路徑規(guī)劃無法完成。因此，網(wǎng)格尺寸的大小對柵格法的意義重大。確定網(wǎng)格尺寸的大小后，將移動機器人的運動空間離散化，最后，把不同的網(wǎng)格設(shè)定不同的值。

1.2 路徑規(guī)劃模型的建立

移動機器人在實際工作中的運動為二維平面，不考慮移動機器人的旋轉(zhuǎn)運動，移動機器人路徑規(guī)劃可表述為：機器人A在空間W=R2中運動，機器人在二維平面中的位置可表示為A(x，y)；將網(wǎng)格W劃分為若干個大小相等的網(wǎng)格，網(wǎng)格的大小不小于移動機器人外形的大??；移動機器人在移動過程中有若干個障礙物Bi，i=1，2，3，...，n。Bi代表第i個障礙物在空間W中所占據(jù)空間的多少。根據(jù)不同的狀況，在機器人移動的任意時刻，把障礙物Bi映射到空間W中，因此在空間W中，避障空間可表示為

Wf={q∈W|A(q)∩Bi=φ}

(1)

式中q為空間W的某一位置；A(q)為移動機器人所處的位置。

所以，移動機器人路徑規(guī)劃是機器人A尋到一條從初始位置S到目標位置T的避障路徑。運動空間中的任何一個柵格代表一個無障礙物空間或者障礙物空間，所有空間可表示為

f:W→{0,1}

(2)

若f(x)=1，說明x為障礙物；若f(x)=0，說明x不是障礙物。所以，所有空間轉(zhuǎn)換成一個二進制的方陣，即等價為一個二維數(shù)組，可表示為Circum。在移動機器人路徑規(guī)劃中，所有運動空間可劃分為若干個f(x)=1和f(x)=0的空間。

1.3 適應(yīng)度函數(shù)的建立

移動機器人路徑規(guī)劃就是搜索一條從S點到T點的無碰撞的最短路徑，其目標函數(shù)可表示為

(3)

式中 m為路徑點的數(shù)量；xi和yi為每個路徑點坐標。

2 粒子群算法的改進

由于粒子群算法易陷落局部極值，運算結(jié)尾時收斂速度慢，精度差[8]。本文從2個方面對粒子群優(yōu)化算法進行了改進，以達到收斂速度快和尋優(yōu)能力強。一方面，引入慣性權(quán)重，可平衡全局搜索和局部搜索，增大算法的搜索效率和收斂精度；另一方面，利用粒子群中粒子群的個體極值的加權(quán)平均值來代替速度更新公式中的粒子[9～12]。

2.1 引入慣性權(quán)重

為提升粒子群算法的收斂能力，在速度進化方程中加入慣性權(quán)重，即

vsr(t+1)=wvsr(t)+c1λ1r(t)(psr(t)-xsr(t))+

c2λ2r(t)(pgr(t)-xsr(t))

(4)

式中 w為慣性權(quán)重；vsr為粒子具有一個相應(yīng)瞬時速度向量；psr為粒子迄今為止搜索到的最優(yōu)位置；xsr為粒子的位置向量；pgr為整個粒子群迄今為止搜索到的最優(yōu)位置。慣性權(quán)重使粒子具有搜索未知空間的能力，合理地選取慣性權(quán)重，可平衡全局搜索和局部搜索，增大粒子群算法的搜索效率和收斂精度，迭代過程中w可表示為

(5)

式中wmax為慣性權(quán)重的最大值，通常取0.9；wmin為慣性權(quán)重的最小值，通常取0.4；τmax為最大迭代次數(shù)；τ為目前迭代次數(shù)。

2.2 權(quán)值模式的粒子群更新算法

(6)

式中 aid可表示為

(7)

(8)

3 仿真分析

為了分析改進粒子群算法的有效性和可行性，本文設(shè)計了移動機器人路徑規(guī)劃模型，并利用Matlab對其全局路徑規(guī)劃進行了仿真。在仿真開始時，將移動機器人的起始位置設(shè)為1，目標位置設(shè)為900。Matlab模擬了兩種不同的環(huán)境模型，仿真結(jié)果如圖2所示。

圖2 全局最優(yōu)路徑

分析圖2可得：移動機器人可以找到一條全局最優(yōu)路徑，同時完全避免了障礙物；與傳統(tǒng)粒子群算法相比，在相同環(huán)境下改進粒子群算法的運行速度快，且得到的路徑為最短路徑。分析圖3可得：在相同環(huán)境下，比較路徑規(guī)劃中的最優(yōu)適應(yīng)度和迭代次數(shù)，改進粒子群算法得到的穩(wěn)定迭代次數(shù)為60次，而傳統(tǒng)粒子群算法得到的穩(wěn)定迭代次數(shù)為75次，傳統(tǒng)粒子群優(yōu)化算法均比改進粒子群算法大。綜上所得：將改進粒子群算法應(yīng)用于移動機器人路徑規(guī)劃中，具有有效性和可行性，改進粒子群算法比傳統(tǒng)粒子群算法搜索全局最優(yōu)解的速度快，收斂精度高。

圖3 適應(yīng)度函數(shù)

4 結(jié) 論

仿真結(jié)果表明:改進后的粒子群算法與傳統(tǒng)算法相比，前者具有更高的精度，即使在復雜的環(huán)境中，有效地解決了路徑搜索的計算量過大，效率不高等問題。同時,也說明本文提出的改進粒子全算法應(yīng)用于移動機器人路徑規(guī)劃具有有效性和可行性。

[1] 康朝海，任偉建.機器人路徑探測方法研究[J].自動化技術(shù)與應(yīng)用，2016，35(2)：72-76.

[2] 王 娟，吳憲祥，郭寶龍.基于改進粒子群優(yōu)化算法的移動機器人路徑規(guī)劃[J].計算機工程與應(yīng)用，2012(15)：240-244.

[3] 李 珊.基于粒子群優(yōu)化算法的移動機器人路徑規(guī)劃研究[D].西安：西安科技大學，2011.

[4] 李寶霞.基于模糊算法的移動機器人路徑規(guī)劃[D].秦皇島：燕山大學，2010.

[5] 李 松，劉力軍，翟 曼.改進粒子群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預測[J].系統(tǒng)工程理論與實踐，2012(9)：2045-2049.

[6] 楊圣蓉，王劍平，王 思，等.基于粒子群優(yōu)化算法的無傳感器調(diào)速系統(tǒng)研究[J].傳感器與微系統(tǒng),2015,34(7):26-28，32.

[7] 張 琦.移動機器人的路徑規(guī)劃與定位技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學，2014.

[8] 蘇海鋒，張建華，梁志瑞，等.基于LCC和改進粒子群算法的配電網(wǎng)多階段網(wǎng)架規(guī)劃優(yōu)化[J].中國電機工程學報，2013(4)：16，118-125.

[9] Li Mingwei,Kang Haigui,Zhou Pengfei,et al.Hybrid optimization algorithm based on chaos,cloud and particle swarm optimization algorithm[J].Journal of Systems Engineering and Electro-nics,2013(2):324-334.

[10] Zhao Jiang,Zhou Rui.Particle swarm optimization applied to hypersonic reentry trajectories[J].Chinese Journal of Aeronautics,2015(3):822-831.

[11] 劉 嶺，閆光榮，雷 毅，等.基于改進粒子群算法的車輛轉(zhuǎn)向梯形機構(gòu)優(yōu)化[J].農(nóng)業(yè)工程學報，2013(10)：76-82.

[12] 盧 玲,謝佳華.萊維飛行的粒子群優(yōu)化算法在WSNs覆蓋增強中的應(yīng)用[J].傳感器與微系統(tǒng)，2015， 34(11)：157-160.

王光宇，通訊作者，E—mail：15134002759@163.com。

Mobile robot path planning based on modified particle swarm optimization algorithm

WANG Hui1, WANG Guang-yu1, PAN De-wen2

(1.College of Mechanical Engineering，Liaoning Technical University，F(xiàn)uxin 123000，China;2.Shenyang Polytechnic College，Shenyang 110045，China)

In order to improve precise navigation function of mobile robot in complex environment，mobile robot path planning based on improved particle swarm optimization(PSO)algorithm is proposed, namely using particle individual extremum weighted average value,while adding inertia weight.Establish grid model for working environment of the robot,and simulation analysis on path planning of mobile robot based on Matlab software.Simulation results show that the improved PSO algorithm is easy to move the particle to the best position,and enhance the ability of global optimization,and the performance of path searching is better than the traditional algorithm in complex environment.

mobile robot; path planning; improved particle swarm optimization(PSO)algorithm

10.13873/J.1000—9787(2017)05—0077—03

2016—05—09

TP 273； TP 242

A

1000—9787(2017)05—0077—03

王 慧(1960-)，男，教授，博士導師，主要從事人工智能及識別技術(shù)及應(yīng)用、智能自控制系統(tǒng)研究。