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

王 慧， 王光宇， 潘德文

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

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

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

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

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

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

0 引 言

智能移動機器人導航任務包括定位、避障和路徑規(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ī)劃有著一種本質上的關系，本文將粒子群算法引入到移動機器人路徑規(guī)劃，并將傳統(tǒng)粒子群算法進行改進，以此提高移動機器人路徑搜索的速度，并通過仿真驗證其有效性和可行性。

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

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

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

圖1 移動機器人模型

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

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

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

移動機器人在實際工作中的運動為二維平面，不考慮移動機器人的旋轉運動，移動機器人路徑規(guī)劃可表述為：機器人A在空間W=R2中運動，機器人在二維平面中的位置可表示為A(x，y)；將網格W劃分為若干個大小相等的網格，網格的大小不小于移動機器人外形的大??；移動機器人在移動過程中有若干個障礙物Bi，i=1，2，3，...，n。Bi代表第i個障礙物在空間W中所占據空間的多少。根據不同的狀況，在機器人移動的任意時刻，把障礙物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不是障礙物。所以，所有空間轉換成一個二進制的方陣，即等價為一個二維數組，可表示為Circum。在移動機器人路徑規(guī)劃中，所有運動空間可劃分為若干個f(x)=1和f(x)=0的空間。

1.3 適應度函數的建立

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

(3)

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

2 粒子群算法的改進

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

2.1 引入慣性權重

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

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

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

(4)

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

(5)

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

2.2 權值模式的粒子群更新算法

(6)

式中 aid可表示為

(7)

(8)

3 仿真分析

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

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

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

圖3 適應度函數

4 結 論

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

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

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

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

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

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

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

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

[8] 蘇海鋒，張建華，梁志瑞，等.基于LCC和改進粒子群算法的配電網多階段網架規(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] 劉 嶺，閆光榮，雷 毅，等.基于改進粒子群算法的車輛轉向梯形機構優(yōu)化[J].農業(yè)工程學報，2013(10)：76-82.

[12] 盧 玲,謝佳華.萊維飛行的粒子群優(yōu)化算法在WSNs覆蓋增強中的應用[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-)，男，教授，博士導師，主要從事人工智能及識別技術及應用、智能自控制系統(tǒng)研究。