Memetic算法在机器人路径规划中的应用研究_罗飞.pdf

《Memetic算法在机器人路径规划中的应用研究_罗飞.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、机械设计与制造第2期130MachineryDesign＆Manufacture2014年2月Memetic算法在机器人路径规划中的应用研究罗飞，汪永超，陈思旭（四川大学制造科学与工程学院，四川成都610065）摘要：针对机器人路径规划问题，采用memetic算法进行求解。算法采用全局搜索与局部搜索相结合的方式，即全局搜索策略融合了遗传算法的交叉与变异操作，局部搜索策略采用了爬山搜索。目标函数综合分析了路径规划中环境和机器人的实际约束条件，以期满足实际行走路径的最优方案。最后进行了机器人路径规划的仿真对比测试，证明

2、了Memetic算法在机器人路径规划问题中具有更高的规划效率，得到的行走路径较优。关键词：Memetic算法；机器人；路径规划中图分类号：TH16；TP24文献标识码：A文章编号：1001-3997（2014）02-0130-03TheApplicationofMemeticAlgorithmintheResearchonPathPlanningforRobotLUOFei，WANGYong-chao，CHENSi-xu（SchoolofManufacturingScienceandEngineering，Sich

3、uanUniversity，SichuanChengdu610065，China）Abstract：Forpathplanningofmobilerobot，theMemeticalgorithmwasadopted.Thiskindofalgorithmcombinedglobalplanningmethodwithlocalsearch.Thegeneticalgorithmwhichcontainedthecrossoverandmutationoperationwasselectedastheglobalp

4、lanningmethodwhilethemountain-climbsearchingalgorithmwasproposedinthelocalsearch.Fortheinfluenceofobjectivefunction，manypracticalconstraintofenvironmentandrobotwereanalyzedinthispathplanning.Finally，pathplanningcomparisonexperimentswasconducted.Simulationresul

5、tshowsthattheMemeticalgorithmcansolveandobtainthepathplanningofmobilerobotmoreeffective.KeyWords：MemeticAlgorithm；Robot；PathPlanning1引言用基于梯度信息的爬山搜索对单个解的领域进行搜索。路径规划是机器人自主导航的关键技术之一[1]，也是机器人2Memetic算法设计研究领域中的一个重要方向。机器人路径规划是指在某些特定的这里给出的求解移动机器人路径规划的Memetic算法，全约束条件下

6、，在工作空间中寻求一条从起始点到目标点的避开障局搜索策略采用二进制字符串编码的遗传算法，局部搜索策略采碍物的最优路径[2]。所谓最优是指工作代价最小、行走路径最短、用爬山算法。行走时间最短等。已经有很多算法来解决路径规划问题，比如人2.1编码工势场法、A*搜索、推理算法等，但这些算法会遇到诸如陷入局将问题的潜在解从解空间转换到遗传编码空间的过程称为编部最小、时空要求难以满足、不能获得全局最优等缺陷[3-4]。码。采用二进制字符串编码方式进行编码[6]。将机器人的工作环境用Memetic算法采用与遗传算法（genet

7、icalgorithm，GA）相似栅格法建模[1，7]，起点和终点可位于网格中的任意节点。机器人的每一的结构与操作流程[5]，并在此基础上通过局部领域搜索使每次迭条可行路径均由一系列相邻的子路径组成，如图1所示。二进制字符代的所有个体都达到局部最优。即Memetic算法在交叉和变异后串用于描述路径形状，0表示机器人沿网格的水平方向移动，1表示机加入一个局部搜索优化过程，是一种基于种群的全局搜索策略和基器人沿网格的垂直方向移动。不同的字符串构成不同的路径，反应于个体的局部启发式搜索策略的结合体。这种结合机制充分吸收遗

8、到生物学上即为不同染色体，如染色体“11000110001111001100”传算法和局部搜索算法的优点，它不仅具有很强的全局寻优能力，所表示的路径，如图2所示。路径起点（0，0），终点（1，1）。这样的编同时由于加入局部搜索，进而减少迭代次数，加快算法的求解速度，码方式直接简洁，稳定性好，有助于算法遍历整个解空间，且容易既保证了较高的收敛性，又能获得高质量