改进粒子群算法在移动机器人路径规划中的应用研究

孙 冬，赵开新

（河南工学院 计算机科学与技术学院，河南 新乡 453003）

0 引言

目前常用的移动机器人路径规划方法主要有蚁群算法、神经网络算法[1-2]、人工势场法、遗传算法、模拟退火算法、粒子群算法等[3-4]。与其他算法相比，粒子群算法具有参数设置少、实现简单等优点[5-6]。但粒子群算法本身还存在着一些缺陷，如收敛速度慢、有早熟现象等，目前对粒子群算法的改进有基于动态调整惯性权重和基于收缩因子两种方法，但大多改进算法不能突破经典惯性权重呈线性递减的约束，粒子不能根据自我的位置动态调整对局部和全局信息的依赖度，导致粒子群算法效率低和次优路径的产生。文献[7]针对粒子收敛速度慢、搜索精度不高和算法性能过度依赖参数的选取等缺点，提出了一种非线性指数惯性权重粒子优化算法，使算法根据粒子最大、适应度值最小的指数函数更新惯性权重，突破了经典惯性权重呈线性递减的约束，该算法有利于粒子在寻优过程中跳出局部最优，使粒子较快地收敛到全局最优位置，但是算法收敛时迭代次数过多。本文通过优化粒子群算法的权重系数来动态调整粒子群算法的全局和局部搜索能力，通过优化学习因子来动态调整粒子对自我和群体的依赖程度，减少算法收敛时的迭代次数，并将改进后的粒子群算法应用到移动机器人路径规划中，引导机器人快速高效地寻找全局最优路径。

1 粒子群算法

粒子群算法（Particle swarm optimization algorithm, PSO）是根据鸟群的捕食和返巢活动提出的一种启发式算法[8]，可设置数学模型的过程如下：搜索空间为D维，种群粒子个数为N，各粒子在D维空间上第t次迭代后位置为每个粒子的速度为其中i[1,m]，通过公式（1）和（2）来更新各粒子的速度和位置。

公式（1）中c1为个人认知因子，c2为社会认知因子，为权重系数，表示粒子个体位置最优解，表示粒子群体位置最优解,r1和r2为介于0 和1 之间的两个随机数。

在粒子群算法中，个体位置最优解按公式（3）进行更新，群体位置最优解按公式（4）进行更新[9-10]。

2 粒子群算法的改进

在粒子群算法中，权重系数的值是恒定的，粒子不会根据自我位置的优劣来动态调整下一次迭代的速度和位置；个人认知因子1c和社会认知因子2c不会随着时间的推移动态调整下一次迭代的速度和位置，因此会导致算法局部收敛和收敛精度低的现象，本文通过动态调整权重系数和动态调整学习因子两个方面对粒子群算法进行改进。

2.1 动态调整权重系数

优化后的权重系数值由公式（5）得出。

式（5）中，i为第i个粒子在第t次迭代的惯性系数值，max_iter为第i个粒子的最大迭代次数，min和max分别为第i个粒子惯性系数的最小值和最大值，粒子i的适应度值为fi，当前粒子群适应度的平均值为favg、最小值为fmin。

2.2 动态调整学习因子

在粒子群算法中，个人认知因子1c和社会认知因子2c不会随着时间的推移动态调整下一次迭代的速度和位置，改进后的个人认知因子由式（6）得出，社会认知因子由式（7）得出。

式（6）中1ic介于c1max和c1min之间，为粒子的动态个人认知因子，2ic介于c2max和c2min之间，为粒子群的动态社会认知因子。从式（6）可以看出，随着时间的推移，1ic的值逐渐减小；从式（7）看出，随着时间的推移，2ic的值逐渐增大。

从改进后的个人认知因子和社会认知因子的算式可以看出，在搜索开始时，粒子的自我学习能力比较弱、向社会群体学习能力比较强，全局搜索能力比较强，保持了种群的多样性；在搜索将要结束时粒子的自我学习能力比较强、向社会群体学习能力比较弱，因此具有较强的局部搜索能力，从而提高了搜索的效率和精度。调整粒子群算法的权重系数和学习因子后粒子速度更新公式为（8）。

3 改进后粒子群算法在移动机器人路径规划中的应用

3.1 算法步骤

移动机器人路径规划的目的就是从初始节点到目标节点找到一条无碰撞的距离最短路径，而粒子群算法正是解决粒子从起始点到终点的最优路径问题，把改进后的粒子群算法应用到移动机器人路径规划中，可以协助机器人快速高效地搜索最优路径。具体步骤如下：

步骤1：设置机器人运动的初始环境，初始化粒子速度、位置等参数。

步骤2：通过适应度函数计算粒子群中各粒子适应度的值。

步骤3：由公式（3）更新粒子个体最优值，根据公式（4）更新种群最优值。

步骤4：由公式（5）求出该粒子权重系数的值。

步骤5：根据时间t和粒子自我因子的最大、最小值，由公式（6）求解个人认知因子的值。

步骤6：根据时间t和社会认知因子的最大最小值，由公式（7）求解社会认知因子的值。

步骤7：由公式（8）更新粒子的速度，由公式（2）更新粒子的位置。

步骤8：当达到算法结束的条件则终止搜索，否则转到步骤2 继续执行。

3.2 仿真实验

3.2.1 实验环境及参数

用 MATLAB 构建栅格环境的仿真平台如图1 所示，障碍物分布在已知的全局静态10×10 的栅格矩阵中并用黑色填充单元格表示。设置机器人起点坐标为S(0，0)，终点坐标为E（10,10）。粒子群算法中种群规模为100，粒子维数为10，迭代次数为40，权重系数最大值max 为0.9，权重系数最小值min 为0.4，个人认知因子最大值c1max为1.2，个人认知因子最小值c1min为0.6，社会认知因子最大值c2max为1.2，社会认知因子最小值c2min为0.6。在上述环境中分别采用粒子群算法PSO、文献[7]粒子群算法EIW-PSO 和本文改进的粒子群算法进行机器人路径规划。

图1 仿真栅格图

3.2.2 实验结果及分析

采用三种不同的算法进行移动机器人路径规划后仿真结果如图2 所示，可以看出本文算法搜索到的路径最短。各路径的详细距离长度如表1 所示，可以看出，在同一仿真环境下，采用粒子群算法求得的路径长度为18.4275，距离平均值为18.7543；采用EIW-PSO 算法求得的路径长度为17.8562，距离平均值为18.1278；采用本文改进的粒子群算法求得的路径长度为15.2471，距离平均值为16.6827；采用本文优化后的算法所得到的路径长度和距离平均值均比粒子群算法和文献[7]粒子群算法EIW-PSO 有了明显缩短。

图2 三种算法的路径规划对比

表1 三种算法的路径长度比较

三种算法找到路径所需要的迭代次数如图3 所示，可以看出采用本文改进的粒子群算法进行路径规划，当算法收敛时迭代次数明显小于粒子群算法PSO 和文献[7]粒子群算法EIW-PS0。算法收敛后，本文算法在相同的迭代次数下粒子适应度值最小。这正是由于通过优化粒子群算法的权重系数和学习因子后，搜索前期增强全局搜索能力，并增强了自我学习能力；搜索后期加大局部搜索能力，增强了向群体学习能力。仿真结果表明，应用本文算法进行路径搜索提高了搜索效率，加快了收敛速度。

图3 三种算法迭代次数比较

4 结语

随着智能机器人技术的快速发展，路径规划问题逐渐成为国内外许多学者研究的热点。本文从权重系数和学习因子两个方面对粒子群算法进行改进，改进的算法突破了经典惯性权重呈线性递减的约束，提高了收敛速度。把改进的粒子群算法应用在移动机器人路径规划中，结果表明该算法具有一定的优势，对未来移动机器人路径规划有一定的指导意义。