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

传感器与微系统（）年第卷第期：（）基于改进粒子群优化算法的移动机器人路径规划赵迪，何克勤，赵祖高（湖北工业大学机械工程学院，湖北武汉）摘要：针对机器人在障碍物数目不同的情况下，提出了一种改进的粒子群优化（）算法 算法来获得一条最佳路径。首先，基于原始的算法，新增了用于粒子搜索过程中局部信息和全局信息的交流项。该项用于迭代搜索过程中局部与全局信息的实时交流，可以提高深入搜索和避免陷入局部最优的能力，经过多组国际测试函数在不同情况下多次测试确定为递减函数时效果最好。然后，分别在少数障碍物下与多数障碍物下做了路径规划，利用惩罚函数驱使机器人进行路径规划时，能快速避开障碍物。同时用三次样条函数来平滑路径，与标准（）和遗传算法（）比较，最后结果均显示了加入交流项后的算法规划的全局路径更短，收敛精度更高，显示了该算法的有效性和优越性。关键词：粒子群优化算法；路径规划；机器人中图分类号：；文献标识码：文章编号：（），（，）：（），（），（）（），：（）；引言机器人路径规划的目的是为移动机器人寻找一条安全且最佳或者接近最佳的路径，为了能够在野外等危险环境起到搜救勘察等作用，需要避开障碍物，并从工作空间中根据一定的性能准则从初始状态搜索到目标状态的最优或次优路径。文献 使用了一种基于人工势场的几何空间方法来解决简化为矩形体非完整移动机器人的实际避障问题。文献 提出了一种反向传播神经网络用于解决路径规划的问题，利用神经网络从感知到行为空间的映射关系提高机器人路径规划器的效果。计算效率低和容易陷入局部极值的缺点使得传统路径规划算法已经不能满足解决问题，所以引入智能式算法来结合去解决要求更高更加精细的路径规划问题。文献在静态环境中用粒子群优化（，）算法规划出了无碰撞的折线路径；文献将免疫克隆和自适应两种算子结合起来，提高种群的收敛速度和减小了路径长度；文献提出了一种混沌蚁群系统来解决收稿日期：基金项目：军队后勤科研国家级项目（）第期赵迪，等：基于改进粒子群优化算法的移动机器人路径规划移动机器人的路径规划问题，有好的全局搜索能力，但早期阶段收敛速度慢；文献将差分进化算法与算法结合，利用前者能动态调整变异概率和缩放因子的特性解决搜索后期陷入停滞的问题；文献针对智能车辆路径规划问题，提出一种改进蚁群智能路径规划方法；文献将蚁群算法和算法融合，改进后加入了活跃因子提高了初始信息素的数量，加入的简化算子增强了寻优能力；文献 结合了算法和三次样条函数来平滑路径；文献 提出了非线性动态调整粒子惯性权重的算法，以路径长度为基础并引入安全度和平滑度概念，动态调整建立好的路径适应度函数；文献针对自适应的惯性权重做出改进，减少了无效的迭代数。算法实现简单、精度高、收敛速度快，是机器人路径规划中的高效方法，但仍具有路径不平滑、容易陷入局部最优、迭代时间过长等问题。本文提出一种基于搜索时全局与局部信息交流的改进（，）算法，根据实景建立了表示障碍物的地图环境和确定碰撞检测方法，提高了路径的收敛速度和减小了路径长度，提高了效率，一定程度上实现了机器人在多障碍物环境下的快速路径规划。地图建立与碰撞检测障碍物模型用不等式的方法对多个障碍物进行建模，路径的起点与终点用点集来表示。在运动过程中将粒子的每个坐标与障碍物做碰撞检测，若点在限制范围内说明点处于障碍物内部，若点在限制方位外说明障碍物外部。增加路径点与障碍物的数目并不会增加计算时间，只会扩大网络规模，所以路径与所有目标障碍物的碰撞检测过程是快速的。此处将障碍物的外缘继续扩展成机器人的，所以将机器人当做一个质点进行规划。机器人的运动空间为设有一定限制范围的二维笛卡尔坐标系，为了方便将障碍物近似用外接圆型来表示。地图以实际的地形为主要依据建立，如图所示。图实际地形障碍物碰撞检测运动过程时路径点与圆形障碍物的碰撞检测用表达式来表示，路径点需要与圆形障碍物的圆心坐标来做距离判断，完成与障碍物关系判断后的结果会赋值给，将该值作为表达式中的一部分。避障的方式是以一种施加一个很大的惩罚值系数的方式趋势运动过程中的路径点来远离圆形障碍物，表达式如下 （）（）（）（）槡）（）（）（）槡（）（）（）（），）（）式中 为施加的一个惩罚值系数，为当前点到圆点已经规划的路径大小，为路径点与障碍物圆心坐标的距离，式（）为路径点与每个障碍物做碰撞检测的结果集，平均后的值会赋予给。当不为时，说明该点是与障碍物发生碰撞导致值会变得很大从而使得该点的路径会被舍弃；当值为时，说明该点一定是位于障碍物的范围外，此时值会取得正常值的距离，该点的路径会被保留。以这种方式反复检测所有的点，快速地得到到达目标点的整个路径。算法的路径规划 算法使用携带有惯性权重的粒子来迅速进行路径的寻找。在寻找过程中同时对路径不断进行三次样条插值的处理，使得路径平滑。搜索开始和结束的起点与终点分别自定义来设置，算法的作用就是搜索得到中间的路径点的数目。粒子群规模和粒子维度分别定义为和。为了提高搜索时全局寻优的能力和避免陷入局部最优，在原本的算法的速度迭代公式上新增了第三项，该项是寻优过程中搜索得到的信息交流项，在搜索的每一代过程中均会产生局部和全局的搜索信息交流，算法速度和位置的迭代公式为（）（）（）（）式中 和分别为第个粒子在时刻时的速度和位置。和为 范围内的随机值，和为用作调节每个粒子个体经验和群体经验的权值，取值均在，范围内。和分别为粒子的局部极值和全局极值，为惯性权重，通常取，更新方式为式（），随着迭代次数递减，主要是保证粒子搜索的精细度（）改进后信息交流项系数的确定为使粒子在实时搜索的过程中能不断交换局部与全部之间的路径信息，引入了系数（）槡（）其中，取值为 的随机数，表达式为（）（）（）传 感 器 与 微 系 统第卷式中 和为开始值与结束值，分别取值为 和，为当前迭代次数，为最大迭代次数；的取值用个测试函数来分析，分别为、函数，它们的极值均为，取值范围前个均为，后个为，；分别在不同值下产生的为常数、递减函数、递增函数的情况下多次测试结果，如表，明显看出，当 时为递减函数时测试的结果更好。所以，式（）中取值最后为。表 组国际测试函数结果函数标准，搜索范围平均值 标准差 ，最优值 平均值 标准差 ，最优值 平均值 标准差 ，最优值 平均值 标准差 ，最优值 路径平滑处理对于第个粒子规划过程产生的路径，初始点为，目标点为，中间的为位置向量（，）。以这三部分作为型值点，两两相邻的点之间形成区间，在每一个区间内均做三次样条插值的平滑处理，其中以区间，为例，该区间的路径线段为，其中，；，；，将产生的 个子区间均做三次样条插值的平滑处理，并将处理后的曲线拼成平滑的曲线，该线为二阶可导，个系数则均需满足以下条件（），（）（，）（），（）（，）（），（），（），（）（，）每个子区间首尾点的一阶导数值作为已知值，可以求出对应的曲线方程的各个系数，最后获得完整的平滑曲线。适应度函数将平滑处理的得到的路径曲线进行等分，初始点为，终止点为，中间的等分点为。初始点与终止点与前面的 节的初始点和目标点相同。将路径的长度值作为适应度函数，则第个粒子的适应度函数为 （）改进算法流程算法在环境和地图建立完成后，通过惩罚函数来完成碰撞检测。步骤如下：）根据障碍物的信息建立地图；）完成好参数的设置；路径的初始点和目标点，以迭代次数初始值为的时候开始进行；）对粒子群进行初始随机化处理；）对产生的每个子区间均做三次样条函数的平滑处理，得到等分每一条曲线后的等分点；）用惩罚函数来对每一个粒子做与障碍物的碰撞检测并用式（）依次更新粒子的适应度值；）用式（）和式（）更新局部和全局极值；）式（）更新惯性权重；）判断是否满足迭代次数，和遍历所有粒子，完成则输出最优路径，不满足则回到步骤（）继续重复步骤（）直到满足条件。仿真实验与结果分析环境与参数设置在处于静止状态的环境下做少数障碍物和多数障碍物的仿真实验，实验均在中进行。参数设置如下：种群数目，迭代次数，前两项的学习因子，初始惯性权重值，作为每次迭代后惯性权重更新使用的系数，惩罚函数中系数，给一较大的惩罚促使减少碰撞。初始点为（，），目标点设为（，）。仿真结果图（），（）分别为在简单少量障碍物下使用和标准（，）算法来规划路径，以图（），（）中不同算法下规划的路径结果来看，下规划的路径明显比下规划的路径更加平滑，而且路径更短。从图（），（）中看出在代处就开始收敛，在代处就渐渐收敛完全。而在代处才开始收敛，在代处渐渐收敛完全。前者的收敛效果优于后者的收敛效果。两种算法最后收敛的路径长度分别为 ，实际测量的折线路径长度为 。500400300200100014161820222426迭代(b)?少数障碍物时 EXPSO 下的路径收敛情况L/m10864200246810 x/my/m(a)?少数障碍物时 EXPSO 下的路径1520253035L/m5004003002001000迭代(d)?多数障碍物时 SPSO下路径收敛情况10864200246810 x/my/m(c)?少数障碍物时 SPSO 下的路径图使用和算法的仿真结果 图（），（）为多障碍物下种算法的路径规划结果，第期赵迪，等：基于改进粒子群优化算法的移动机器人路径规划在多障碍物环境下时算法规划的路径与遗传算法（，）下规划的路径相比更加平滑，在拐角处也更贴合障碍物边缘，路径的长度分别 和 。实际测量的折线长度为 。通过图（），（）明显看出，在多障碍物的环境下算法在代开始收敛，代就开始趋于完成收敛的状态。而在代才开始收敛，代之后才慢慢收敛完成。所以算法下规划的路径优于的，也是最短的。10864200246810 x/my/m(a)?EXPSO 下的路径10864200246810 x/my/m(c)?GA 下的路径L/m5004003002001000迭代(b)?EXPSO 下路径收敛情况10203040L/m5004003002001000迭代(d)?GA下路径收敛情况102030405012图多数障碍时使用算法和的仿真结果方法对比针对多数障碍物的情形下，对，方法重复做组仿真实验，去掉最长和最短的路径值，然后取平均值并计算误差平方差来观察种情况下的稳定程度。通过表可以看出，平均路径为，种方法的多组数据计算得到的误差平方差中的平方差最小，为 。所以说明了算法的稳定性。表 种方法对比方法路径平均值平方差 结论本文提出了对移动机器人进行路径规划的算法，为了提高粒子寻优能力，新增引入了交流项，保证了粒子能在寻优过程时全部信息和局部信息的即使交流，提高了搜索时的收敛速度和获得了更短的全局路径。使用惩罚函数做与障碍物的碰撞检测，用三次样条函数做曲线的快速光滑处理，分别在较多障碍物和很多障碍物两种不同的情形下做的实验，与另外的种算法相比机器人使用算法做路径规划搜索到全局最优解的速度更快，收敛精度更高，避免搜索过程中陷入局部最优，验证了该算法的有效性和可行性。参考文献：熊昕霞，何利力基于混合粒子群算法的移动机器人路径规划计算机系统应用，（）：，：，：，：孙波，陈卫东，席裕庚基于粒子群优化算法的移动机器人全局路径规划控制与决策，（）：徐梦莹，王娇娇，刘宝，等基于改进遗传算法的机器人路径规划石河子大学学报，（）：，：魏勇，赵开新，王东署改进的粒子群算法在移动机器人路径规划中的应用火力与指挥制，（）：蓝丹，樊东红，陈强，等改进的蚁群算法在智能车辆路径规划中的运用组合机床与自动化加工技术，（）：，韩颜，许燕，周建平粒子群蚁群融合算法的机器人路径规划组合机床与自动化加工技术，（）：强宁，高洁，康凤举基于和三次样条插值的多机器人全局路径规划系统仿真学报，（）：张万绪，张向兰，李莹基于改进粒子群算法的智能机器人路径规划计算机应用，（）：，：，岳恒，张海军，柴天佑 算法在多模型自校正动态矩阵控制中的应用东北大学学报，（）：，敖永才，师奕兵，张伟自适应惯性权重的改进粒子群算法电子科技大学学报，（）：，作者简介：赵迪（），男，副教授，硕士研究生导师，研究领域为服务机器人，智能机器人。何克勤（），男，通讯作者，硕士研究生，研究方向为机器人预测仿真。