量子粒子群优化算法在移动机器人路径规划中的应用

杨 静

(安徽文达信息工程学院 艺术设计学院，安徽 合肥 230032)

移动机器人路径规划是找到一个从初始位置到终止位置的可行不交叉的途径，满足路径短、安全、高效率等要求[1-2].最近几年越来越多的研究者把蚁群法、神经系统、进化算法和粒子群优化等计算方法都运用到机器人路径研究中.移动机器人路径的理论研究状态慢慢转向到群体优化计算的途径，粒子群优化(PSO)计算方法是一类启发式优化方法[3]，此方法对于目标函数的特性是不作规范，已慢慢成为群体智能优化研究方法的一个潮流.移动机器人运用粒子群优化计算可以让规划更容易、计算方法简易，其缺点是对参数较大依赖，会陷入局部最优等问题.

已有很多研究者研究了基于启发式优化算法的机器人路径规划方法.如文献[4]提出了一种基于改进灰狼优化算法的机器人路径规划方法.文献[5]提出一种基于改进人工鱼群算法和MAKLINK图的机器人路径规划方法.文献[6]提出一种改进蚁群算法的移动机器人路径规划，解决了传统蚁群算法收敛慢，易产生局部最优的问题.文献[7]提出在随机扩展树算法中引入目标偏差搜索策略, 在度量函数中增加距离、角度因素, 用神经网络处理规划路径.文献[8]提出了在离散化环境下规划出初始路径，然后在连续环境中进行路径优化.该方法使算法独立于网格尺寸，并且创建了曲线路径，增加了路径的准确性和平滑性.近些年，机器人路径规划得到了迅速的发展, 以蚁群算法(ant colony optimization, ACO)、粒子群算法(particle swarm optimization, PSO)为代表的群体智能算法在解决复杂环境路径规划问题上表现出了突出的性能.文献[9]将A*算法与启发式优化算法相结合，运用复合路径规划算法在地图上搜索全局最优路径，然后运用模糊控制器调整移动机器人的角度.文献[10]提出运用Max-Min Ant系统优化算法在未知环境中规划路径.

粒子群计算方法传递信息多数依赖全局数值往全体粒子的传输，相比于其他计算方法，其速度更快，精度更高.缺点是会发生较早的局部最优情况.针对这一问题，本文提出一种基于量子粒子群优化(Quantum particle swarm optimization，QPSO)算法的移动机器人路径规划方法(QPSO法)，它运用的单个粒子优化进度和整体分散的动态运动比重，让惯性比重含有控制特征和适应特征，这个运算方法能快速提高计算的收敛进度、维持不同群里的特性.最终将新的计算方法运用到移动机器人的轨迹规划中，实验结果证明所提方法的优化路径明显优于其他方法.

按粒子群的特征性质，QPSO方法的搜索最优解的能力比PSO计算方法的更全面.

因此，本文对PSO计算方法展开优化，其计算公式如下：

(1)

Pi.j=φ·Pbesti,j(t)+(1-φ)·Gbest(t),(i=1,2…，N,j=1,2,…，M)

(2)

mbest=(M1(t),M2(t),…,MD(t)=

(3)

在进行优化的计算方法里，贴切的计算控制参数对计算的特征影响特别重，根据进化公式(1)和(3)展开研究可以增加粒子群运动路径的多样性，可以极大提高粒子群的全局搜索能力和收敛速度，依据粒子pi(t+1)的公式(2)，能够转换成公式

pi,j(t+1)=Gbesti,j(t)+φ(pbesti,j(t)-Gbesti,j(t))

(4)

从公式(1)和公式(4)中看出，转换粒子pi(t+1)是整体最佳关系Gbest(t)与当时粒子最佳关系pbest(t)的差距的总和，Xi(t+1)和当时粒子的均值关系mbest和当时位置X(t)的差也体现出这一关系.

本文利用个体粒子优化速度和整体分离的动态惯性比重，让惯性比例含有自我适应聚集度改变惯性比列，让惯性比列有自我适应能力，从而避开导致局部情况[11]，并且把随机选择的方法代入到最佳位置后解决.为了保证群多样性能和固定特征，增加了QPSO计算方法的整体搜索力度，同时提升计算方法的收敛效应.

定义1 个体粒子的优化速度，假如Fitness(Gbest(t))代表的是整体最佳情况的适应特征和Fitness(Pi(t))代表的是当前最佳情况的适应特征，从而可以得出单个粒子的优化进度公式为：

(5)

其中0

定义2 群体分散度代入到粒子公式(5)中，粒子最佳的关系差距∂p(t)可表为∂p(t)={∂p1(Pbesti,1(t)),∂p2(Pbesti,2(t)),…，∂PD(Pbesti,D(t)}，同时对进化公式的粒子群体离度可表为：

gst(t)={gsi,1(t),gsi,2(t),…，gsi,D(t)}=

(6)

以上公式可以总结出，gs代表粒子的离散优化进度和种群的不同特征.假设gs的数值增加，粒子的离散优化进度随即增大，粒子种群的不同性则变小.假如gs=1的时候，最佳情况Pbest和现状情况X一致，然而gs结果数值将继续变化.

粒子群算法中粒子代表移动机器人运动路径[12]，本文假设存在N条运动轨迹，粒子维度D表示出发点到终点间的路径条数.移动机器人路径规划过程可表示为各个路径规划下获得最优角度值的规划过程.

(1)考虑到移动机器人的工作环境，本文选用栅格法进行模型构建，使用的栅格法选择规格大小相同的栅格对移动机器人运动范围进行划分，运动环境可借用极坐标和直角坐标相结合进行表示，极坐标长度为移动机器人从初始点到终点间的距离，角度表示运动可达到的范围，栅格粒度大小需要根据移动机器人规格与障碍物规格进行设置.以极坐标和直角坐标为基础的关系探测法如图1所示.

图1 极坐标与直角坐标下移动机器人路径探测示意图

(2)设定粒子群参数值：D表示粒子维度；
M表示最大迭代次数；
N表示粒子群；
学习因子C1与C2以及扩张-收缩系数α，那么，本文粒子群的维度可表示为：

(7)

其中，distance(path)表示原始点到终点间的长度，lengthrobot表示移动机器人自身长度.

(3)极坐标的长度依赖于初始点与终点的距离，探测角度区间设定为[0,π/2]，则可得到：

(8)

其中，β=arccos(Ltarget/ρi)，αtop和αdown依次表示移动机器人运动可探测范围的最大值与最小值；
Ltarget表示移动机器人在直角坐标中的位置；
ρL表示极坐标下相应的运动长度，且条件设置为[13]：

(9)

(4)将粒子群设为均匀分布，其中，粒子群中粒子位置与运动速度在运动区域可表示如下：

αi，j=rand*(αtop-αdown)+αdown

(10)

(5)依据极坐标与直角坐标转换原理，可计算出移动机器人坐标值，根据粒子运动约束条件以判定规划路径是否可行与有效，如果判定为无效路径，则需要重新初始化，直到获得有效粒子位置.

3.1 路径规划仿真

为了验证本文提出算法的可行性，使用仿真软件Matlab2012b对QPSO算法进行仿真.在仿真系统中设定移动机器人的运动空间大小为10 m×10 m，选取的移动机器人底盘占地面积规格大小为0.3 m×0.4 m，运动的原始出发点为(0,0)，正态分布为N(30，45)，粒子群相应的维度值定为D=8，N=30，M=50，运动过程可以达到的最大线速度V为0.24 m/s，角速度W为0.2 rand/s，运动周期为0.4 s.

为了验证本文算法的优越性，将本文QPSO算法与PSO算法的仿真结果进行对比，设置相同的参数值，两种算法在初始化状态下运行50次，依次记录每次仿真获得的最优路径，并计算出50个最优路径选择代价值相应的平均代价、平均耗时以及标准差.

从表1的仿真结果可知，在均匀分布D=8的情况下，使用两种算法生成的路径相近，在正态分布D=16的情况下，PSO算法和QPSO算法生成的路径不相同，相比于PSO，本文方法的平均代价降低了约0.2 m，平均耗时降低了1.28 s.此种情况下，PSO算法无法找到最优路径，无法规划出路径最优解.根据图2和表2可知，移动机器人在正态分布N(45, 30)下粒子群的维度中对比PSO算法，本文使用的QPSO算法更加优越.

表1 均匀分布情况下移动机器人路径规划仿真结果

(a)最优路径规划仿真结果示意图 (b)最优路径代价值收敛曲线

表2 正态分布N(45,30)下移动机器人最优路径规划仿真结果

3.2 移动机器人平台的实验

为了测试本文算法在实际应用中的效果，将两轮移动机器人作为本次研究目标.其中，设定的轮式移动机器人相关参数值如表3所示.

表3 轮式移动机器人相关的机构特性值

本次实验次数设定为100次，测试得到的路径规划结果如图3所示.

图3 QSO算法与PSO算法最优路径结果对比

根据图3的实验结果可知，QPSO算法下移动机器人路径规划结果优于PSO算法，经过测量，规划路径长度为4.0253 m，而使用PSO算法下移动机器人运动路径长度为4.3813 m.主要原因为PSO在搜索路径过程容易陷入局部最优，但是将QPSO算法应用于移动机器人全局搜索中可以得到最优路径.

根据图4和图5的实验测试结果可知，移动机器人在PSO算法和QPSO算法下在149次迭代次数后均可以得到局部最优值.但是本文使用的QPSO算法在进行200次迭代后能够跳出局部最优值，大约在250次迭代调整后搜索到了全局最优路径，但是移动机器人在PSO算法下依旧陷入局部最优路径.根据以上分析可知，本文提出的QPSO算法在全局收敛速度上优于PSO算法.

图4 PSO算法收敛结果 图5 QPSO算法收敛结果

本文通过对传统PSO算法中个体粒子、群体离散度参数以及自然选择法进行改进，提出了一种移动机器人路径优化规划方法.在初始化分布时随着粒子维度的不断变化，通过分析QPSO算法下粒子群与迭代次数之间的关系，比较在不同粒子维度下传统PSO算法与QPSO算法的性能.最后通过仿真实验结果表明，与传统的PSO算法路径规划方法对比，QPSO算法在移动机器人路径规划中搜索能力更强、收敛速度更快，得到的运动路径最优.

推荐访问:子群 子粒 机器人