基于改进粒子群算法的移动机器人路径规划

王 慧， 王光宇， 潘德文

(1.辽宁工程技术大学 机械工程学院，辽宁 阜新 123000；2.沈阳职业技术学院，辽宁 沈阳 110045)

基于改进粒子群算法的移动机器人路径规划

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

(1.辽宁工程技术大学 机械工程学院，辽宁 阜新 123000；2.沈阳职业技术学院，辽宁 沈阳 110045)

为了提高复杂环境下移动机器人的精准导航作用，提出了移动机器人路径规划的改进粒子群优化(PSO)算法，即利用粒子个体极值的加权平均值，同时加入惯性权重。建立了移动机器人工作环境的栅格模型，利用Matlab软件进行移动机器人路径规划仿真分析。仿真结果表明:改进后的粒子群算法容易使粒子移动到最佳位置，加强了全局寻优能力，在复杂环境中搜索路径性能优于传统算法。

移动机器人； 路径规划； 改进粒子群算法

0 引 言

智能移动机器人导航任务包括定位、避障和路径规划。移动机器人路径规划是指机器人在工作环境中能够躲开障碍，基于优化准则从起始位置到目标位置的无碰撞、安全的运动路径搜索[1]。粒子群算法是利用生物群落信息共享的进化优势思想，通过个体之间的相互合作来寻找全局最优解[2]。近年来，传统的粒子群算法在移动机器人路径规划中取得了很好的效果，但传统的粒子群优化算法早熟收敛，容易陷落局部最优解和收敛速度慢等问题，很难找到全局最优的移动机器人路径规划。

西安科技大学的李珊利用标准粒子群优化算法对机器人路径进行研究，在粒子速度更新公式中引入一个进步因子项，并对超出初始空间范围的粒子重新进行随机初始化。但实验仿真的模拟环境比较简单，不具实际工况[3]。燕山大学的陈卫东利用模糊算法对移动机器人路径进行规划，仿真实验同样不具工厂实际工况[4]。

考虑到粒子群算法和移动机器人路径规划有着一种本质上的关系，本文将粒子群算法引入到移动机器人路径规划，并将传统粒子群算法进行改进，以此提高移动机器人路径搜索的速度，并通过仿真验证其有效性和可行性。

1 移动机器人路径规划模型的建立

1.1 移动机器人工作环境建模

移动机器人模型如图1所示。

图1 移动机器人模型

栅格法是一种平面移动机器人运动轨迹规划的抽象模型，是研究平面移动机器人运动路径规划的最常用的方法之一[5～7]。本文采用栅格法建立工作环境模型，将粒子群优化算法直接应用于栅格法，获得粒子群算法应用于移动机器人的全局最优路径。

本文利用栅格地图进行移动机器人路径规划，避免了在处理障碍物边界时计算复杂的问题。从栅格法的原理可知，网格的尺寸越小，所表示的障碍越精确，也将占据较大的存储空间，算法的搜索范围按照指数增大。同时网格的尺寸越小，将大大增大计算量，不利于系统的实时性；网格尺寸太大，路径规划的准确性降低，将造成对环境描述的精确性大大增降低，甚至将造成路径规划无法完成。因此，网格尺寸的大小对栅格法的意义重大。确定网格尺寸的大小后，将移动机器人的运动空间离散化，最后，把不同的网格设定不同的值。

1.2 路径规划模型的建立

移动机器人在实际工作中的运动为二维平面，不考虑移动机器人的旋转运动，移动机器人路径规划可表述为：机器人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)为移动机器人所处的位置。

所以，移动机器人路径规划是机器人A寻到一条从初始位置S到目标位置T的避障路径。运动空间中的任何一个栅格代表一个无障碍物空间或者障碍物空间，所有空间可表示为

f:W→{0,1}

(2)

若f(x)=1，说明x为障碍物；若f(x)=0，说明x不是障碍物。所以，所有空间转换成一个二进制的方阵，即等价为一个二维数组，可表示为Circum。在移动机器人路径规划中，所有运动空间可划分为若干个f(x)=1和f(x)=0的空间。

1.3 适应度函数的建立

移动机器人路径规划就是搜索一条从S点到T点的无碰撞的最短路径，其目标函数可表示为

(3)

式中 m为路径点的数量；xi和yi为每个路径点坐标。

2 粒子群算法的改进

由于粒子群算法易陷落局部极值，运算结尾时收敛速度慢，精度差[8]。本文从2个方面对粒子群优化算法进行了改进，以达到收敛速度快和寻优能力强。一方面，引入惯性权重，可平衡全局搜索和局部搜索，增大算法的搜索效率和收敛精度；另一方面，利用粒子群中粒子群的个体极值的加权平均值来代替速度更新公式中的粒子[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为粒子迄今为止搜索到的最优位置；xsr为粒子的位置向量；pgr为整个粒子群迄今为止搜索到的最优位置。惯性权重使粒子具有搜索未知空间的能力，合理地选取惯性权重，可平衡全局搜索和局部搜索，增大粒子群算法的搜索效率和收敛精度，迭代过程中w可表示为

(5)

式中wmax为惯性权重的最大值，通常取0.9；wmin为惯性权重的最小值，通常取0.4；τmax为最大迭代次数；τ为目前迭代次数。

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

(6)

式中 aid可表示为

(7)

(8)

3 仿真分析

为了分析改进粒子群算法的有效性和可行性，本文设计了移动机器人路径规划模型，并利用Matlab对其全局路径规划进行了仿真。在仿真开始时，将移动机器人的起始位置设为1，目标位置设为900。Matlab模拟了两种不同的环境模型，仿真结果如图2所示。

图2 全局最优路径

分析图2可得：移动机器人可以找到一条全局最优路径，同时完全避免了障碍物；与传统粒子群算法相比，在相同环境下改进粒子群算法的运行速度快，且得到的路径为最短路径。分析图3可得：在相同环境下，比较路径规划中的最优适应度和迭代次数，改进粒子群算法得到的稳定迭代次数为60次，而传统粒子群算法得到的稳定迭代次数为75次，传统粒子群优化算法均比改进粒子群算法大。综上所得：将改进粒子群算法应用于移动机器人路径规划中，具有有效性和可行性，改进粒子群算法比传统粒子群算法搜索全局最优解的速度快，收敛精度高。

图3 适应度函数

4 结 论

仿真结果表明:改进后的粒子群算法与传统算法相比，前者具有更高的精度，即使在复杂的环境中，有效地解决了路径搜索的计算量过大，效率不高等问题。同时,也说明本文提出的改进粒子全算法应用于移动机器人路径规划具有有效性和可行性。

[1] 康朝海，任伟建.机器人路径探测方法研究[J].自动化技术与应用，2016，35(2)：72-76.

[2] 王 娟，吴宪祥，郭宝龙.基于改进粒子群优化算法的移动机器人路径规划[J].计算机工程与应用，2012(15)：240-244.

[3] 李 珊.基于粒子群优化算法的移动机器人路径规划研究[D].西安：西安科技大学，2011.

[4] 李宝霞.基于模糊算法的移动机器人路径规划[D].秦皇岛：燕山大学，2010.

[5] 李 松，刘力军，翟 曼.改进粒子群算法优化BP神经网络的短时交通流预测[J].系统工程理论与实践，2012(9)：2045-2049.

[6] 杨圣蓉，王剑平，王 思，等.基于粒子群优化算法的无传感器调速系统研究[J].传感器与微系统,2015,34(7):26-28，32.

[7] 张 琦.移动机器人的路径规划与定位技术研究[D].哈尔滨：哈尔滨工业大学，2014.

[8] 苏海锋，张建华，梁志瑞，等.基于LCC和改进粒子群算法的配电网多阶段网架规划优化[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] 刘 岭，闫光荣，雷 毅，等.基于改进粒子群算法的车辆转向梯形机构优化[J].农业工程学报，2013(10)：76-82.

[12] 卢 玲,谢佳华.莱维飞行的粒子群优化算法在WSNs覆盖增强中的应用[J].传感器与微系统，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，Fuxin 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-)，男，教授，博士导师，主要从事人工智能及识别技术及应用、智能自控制系统研究。