基于粒子群优化算法的机器人路径规划
来源:用户上传
作者:覃正祥 丁家付 张彦旻 蒋伟 王志翔
摘 要：文章提出一种机器人路径规划的有效算法，为机器人找到一条从起点到终点最短的无碰撞路径，主要是优化了粒子群的惯性权重，然而其在不同的阶段采用不同的权重值。通过实验发现，改进后粒子群能够收敛得更快，数据收敛得更精确。
关键词：优化粒子群;路径规划;移动机器人;环境模型
1 路径规划
移动型机器人[1]的路径规划[2]是机器人能够自主进行移动的必备先决条件之一，是指从起点到终点按照一定的约束条件，与环境中的障碍物无碰撞，达到研究者预设目标的最优规划路径。按照环境变量[3]划分，可以将路径规划模型分为环境变量全局未知、环境变量局部未知、环境变量全局已知。
粒子群算法[4]是指如果需要搜索的环境变量是一个n维向量，则粒子群中的每一个粒子也是一个n维的向量。假设粒子群中共有M个粒子，则粒子群中的第i个粒子即可表示为该目标环境下的一个解，粒子通过不断地改变自己的位置来寻求最优解。粒子的位置变化通过种群的粒子最优值、粒子自身的历史最优值、粒子的自身状态三者的共同叠加达到下一个位置点，并在最新点计算目标函数的值，刷新种群和个体的最优解，通过种群的迭代不断刷新种群和个体的最优解，当达到预设的迭代次数时或者达到最优解或最优解附近时，迭代即可停止。
2 数学模型
2.1 环境模型建立
路径规划是移动机器人完成在复杂环境下移动导航的重要必备条件之一，在确定的环境下，按照目标的约束条件寻求一条从起始点到目标点的、和障碍之间无碰撞最优路径。本文对二维平面上机器人的工作环境进行简单的建模，再对障碍物及其边界进行“圆形化”处理，避免了复杂的计算。环境模型的建立有多种方法，如：栅格法、人工势场法、树状图法等。为了避免过多复杂的讨论，本文决定以障碍物图形的几何中心为原点，最大距离为半径做圆，将障碍物全部囊括进所做的圆形中。
2.2 粒子群算法介绍
假设粒子群的搜索空间是一个n维的连续空间，则第i个粒子的向量表现为：xi=（xi1，xi2，…，xi*n-1，xin），代表粒子i的速度向量为Vi=（vi1，vi2，…，Vi*n-1，vin）。
粒子群算法的迭代公式如下。
速度向量迭代公式：
（1）
位置向量的更新公式：
（2）
在速度向量迭代公式中，Pbest（i）表示第i个粒子的历史最佳位置，Gbest体现种群历史的最佳地位。可以看出，粒子群可以通过不断地迭代学习自己和总粒子群的历史最佳值，不断规划出新的位置点直至找到最佳的适应值。然而，实验结果表明，由于粒子存在着随机的不确定量，虽然粒子的全局检索能力大大提高，但是会使其局部搜索能力较差。所以，在算法初期需要较强的全局搜寻能力，并在算法末期整个粒子种群应该有较强的部分搜索能力。在前期惯性权重应较大而在后期应较小，经过改动惯性权重修改了公式（1），从而提出了粒子群算法的惯性权重模型。
新的速度向量迭代公式为：
（3）
式（3）中，参数w是粒子群算法的惯性权重，是由函数随机生成介于[0，1]之间的某个数，一开始让w为0.98，使得粒子群优化算法（Particle Swarm Optimization，PSO）的全局搜寻能力较强，随着迭代的逐渐深入，该参数逐步减小，从而使PSO具备较强的部分收敛能力;当迭代快要结束时，可以使这个参数趋近于0。参数c1，c2被称为学习因子，通常被设置为1.5，参数rand（VarSize）的作用是产生一个随机数，范围为[0，1]。PSO算法的简单流程如图1所示。
2.3 关于粒子群算法的优化
目前主要有3大类粒子群算法的优化方法：参数优化类、算法更新方程改进类和其他算法相结合类的算法优化。
本文主要探讨第一类：参数优化改进类，以此改进粒子群算法。经过对前文的粒子群算法原理的介绍，了解到粒子群算法总共包含了3个参数：w，c1和c2。w是PSO的惯性权重，代表着粒子“按照自身意愿规划下一步路径”所占的比重，如果w较大，则利于全局寻找最优但是收敛较慢，不利于寻找局部的最优解，可能得不到最优解;如果w较小，则利于寻找局部最优解但不利于寻找全局最优解，易于陷入小范围的最优解当中。因而使用一种惯性权重的自适应办法，即在前期采用较大的w值，使之能够有较大的搜索范围，利于寻找全局最优，在后期采用较小的w值，让其能够在局部有较强的检索能力。综合两方面优点，得出的惯性权重自适应公式为：
w=w*sin（pi/2+（pi/2）*（it/MaxIt））+wmin（4）
式中，利用正弦函数的变化规律，产生w参数的自适应功能。式子右边的w表示上一次计算w的结果值，it表现为目前的迭代次数，MaxIt表示总的迭代次数，是预设的惯性权重的最小值，第一次的w值和wm均可根据条件的范围以及搜索空间的大小，给出设定值。公式（4）根据粒子群的迭代次数的改变发生相应的变化，通过实验观察具有良好的全局搜索能力和局部的优化性能，且能够快速收敛，比标准的粒子群收敛得更快、更精确。
3 仿真研究
預设在二维平面内搜索从起点（0，0）到终点（8，8）的有效路径，设定种群数量为150，总的迭代次数为200次，c1=1.5，c2=1.5，初始的w为2.5，惯性权重的最小值=0.05。实验结果如图2—3所示。
还可以公式进行改进：
w=w*sin（pi/2+（pi/2）*（it/MaxIt））+wm*it/MaxIt（5）
如图4所示，进行改进型惯性权重的适应度调节，发现收敛得更快、数据更精确。 4 结语
通过实验仿真可以看出，在未加惯性权重适应度的情况下，粒子群在100代才稳定收敛于13.17;当加上惯性权重的适应公式后，粒子群在40代就稳定收敛于11.93。可见，经过算法的优化改進后，粒子群收敛得更快，同时，避免了粒子群算法的“早熟”和堕入部分最优解的弊端。但是改进的粒子群算法的不足是预设的w和wm需要根据环境和条件的不同而变化，可能需要多次尝试。
[参考文献]
[1]黄辰.基于智能优化算法的移动机器人路径规划与定位方法研究[D].大连：大连交通大学，2018.
[2]康玉祥，姜春英，秦运海，等.基于改进PSO算法的机器人路径规划及实验[J].机器人，2018（12）：1-8
[3]黄超，梁圣涛，张毅，等.基于多目标蝗虫优化算法的移动机器人路径规划[J].计算机应用，2019（10）：2859-2864.
[4]贾会群.无人驾驶车辆自主导航关键技术研究[D].北京：中国科学院大学，2019.
Robot path planning based on particle swarm optimization
Qin Zhengxiang， Ding Jiafu， Zhang Yanmin， Jiang Wei， Wang Zhixiang
（School of Information Engineering， Yangzhou University， Yangzhou 225000， China）
Abstract：This paper proposes an effective algorithm for robot path planning， which can find the shortest path for robot from start to end. It mainly optimizes the inertia weight of particle swarm， but it uses different weight values in different stages. The experimental results show that the improved particle swarm optimization can converge faster and the data converges more accurately.
Key words：particle swarm optimization; path planning; mobile robot; environment model
转载注明来源:https://www.xzbu.com/8/view-15197331.htm
