改进粒子群算法在机器人路径规划中的应用.pdf

ComputerEngineeringandApplications计算机工程与应用2011，47（25）241

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

马千知，雷秀娟
MAQianzhi，LEIXiujuan
陕西师范大学计算机科学学院，西安710062
CollegeofComputerScience，ShaanxiNormalUniversity，Xi’an710062，China

MAQianzhi，LEIXiujuan.Applicationofimprovedparticleswarmoptimizationalgorithminroboticpathplanning.
ComputerEngineeringandApplications，2011，47（25）：241-244.

Abstract：Accordingtothedefectofparticleswarmoptimizationthatitiseasilytofallintolocaloptimalsolution，combin-
ingwiththemodelofroboticpathplanning，anovelparticleswarmoptimizationwithperturbationmechanismisproposed.In
perturbationmechanism，thenewmodifiedparticlesareproducedtotakeplacesofthoseparticleswhichkeepnoevolution.
Thismethodleadsthealgorithmtofindthefeasiblepathandishelpfulforescapingthelocaloptimalsolution.Simulation
experimentsarealsodoneinthispaper，andtheresultsofcomputersimulationcomparedwithtraditionalalgorithmsdemon-
stratethesuperiorityoftheenhancedalgorithm.
Keywords：particleswarmoptimization；perturbationmechanism；roboticpathplanning

摘要：针对粒子群优化算法易过早收敛而陷入局部最优的缺陷，结合移动机器人全局路径规划问题模型，提出一种带扰动机制
的粒子群优化算法。对于进入进化停滞状态的个体，采用个体修正策略产生新个体将其替代，来引导算法搜索可行路径，帮助粒
子逃离局部极值。仿真实验表明，与其他算法相比，该算法具有更好的搜索精度和全局寻优能力。
关键词：粒子群优化；扰动机制；机器人路径规划
DOI：10.3778/j.issn.1002-8331.2011.25.064文章编号：1002-8331（2011）25-0241-04文献标识码：A中图分类号：TP242.6

1引言性与合理性。
路径规划是移动机器人应用中一项非常重要的技术，也
是移动机器人研究的焦点问题。它是指在有障碍物的工作环2问题描述与建模
境中，寻找一条从给定起始点到终止点的较优的运动路径，使在描述机器人路径规划之前，首先对机器人运动环境进
机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且行设定：（1）机器人在二维有限空间运动。（2）机器人运动空间
所走路径较短。已有路径规划方法包括人工势场法、可视图中分布着有限个已知的静态障碍物，这里障碍物用已知位置
法等，这些方法都存在一定的局限性，如人工势场法在相近的和大小的各种凸多边形和圆来表示。在实际问题中，可将障
障碍物面前不能发现路径，可视图法有搜索路径复杂、效率不碍物近似为这两种形状模型。（3）考虑到机器人本身有一定大
高的问题[1]。近年来，不少学者将仿生智能算法如遗传算法、小，将障碍物半径按机器人大小向外拓展，这样机器人就可以
蚁群算法[2]等用于机器人路径规划方法的研究，取得了显著的看作一个质点。
成果。粒子群优化算法作为新型仿生智能优化方法由于其搜移动机器人全局路径规划的任务是在一个已知障碍物的
索速度快、易于实现等优点也被尝试用于求解路径规划问题[3-5]，静态环境中，寻找一条从起始点到目标点的路径长度最短且
但由于其自身易于陷入局部最优，以及在此问题中受复杂约与障碍物无碰的路径。如图1所示。

束影响大等局限性，搜索结果并不理想。为防止种群过早收在坐标系X-O-Y中，实心物体表示障碍物，点S(xsys)

敛，本文在粒子群算法中引入了扰动机制，考虑到移动机器人为起始点，F(xfyf)为目标点，路径规划就是要在全局空间中寻
路径规划问题约