模拟退火算法.pdf

《模拟退火算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于栅格法-模拟退火法的机器人路径规划123郑秀敏顾大鹏刘相术（1.北京航空材料研究院，北京100095；2.沧州师范专科学校，沧州061001；3.北京机械工业学院，北京，100085）摘要：路径规划是机器人技术中的重要组成部分，分全局路径规划和局部路径规划。本文将栅格法与模拟退火法结合，采用栅格法表示环境信息。局部路径规划主要基于模拟退火法，使路径跳出局部极小点，到达目标位置。关键词：机器人路径规划模拟退火法栅格法中图分类号：TP273文献标示码：ARobotPathPlanningBasedonGridMethodwithSimulatedAnnealingAbs

2、tract：Pathplanningisoneofimportanttopicsinrobotics.Ithastwoessentialsorts.Oneisglobalpathplanning,andtheotherislocalpathplanning.Inthepaperthegrid,methodiscombinedwithsimulatedannealing.Weusegridmethodtodenotetheenvironments’informationThelocalpathplanningchieflybasedonsimulatedannealing

3、,inordertoescapethelocalminimumandarrivetargetposition.Keywords：RobotPathPlanningSimulatedAnnealingGridMethod1引言[1]机器人路径规划是按着一定的法则搜索一条从起点到终点的安全最优行走路线，它是机器人导航技术中的重要组成部分。依据机器人对周围工作环境信息的感知程度，机器人路径规划分为两类：一类是基于环境信息完全知道的路径规划；一类是基于不确定环境下的路径规划。如果把机器人看作要研究的问题的某种状态，把障碍物看作问题的约束条件，而无碰撞路径则为满足约束条件的解，那

4、么路径规划就是一种多约束的问题求解过程。目前用于路径规划的算法很多主要有人工势场法、自由空间法、环境地图法、可视图法，此外近几年遗传算法、蚁群算法、人工智能也被用于机器人路径规划。这些算法存在一定的应用局限性，规划出来的结果也非全局最优。本文将栅格法与模拟退火法结合，采用栅格法表示环境信息，利用模拟退火法进行局部路径规划使路径跳出局部极小点，到达目标位置。2栅格法和模拟退火法的基本思想[2]栅格法是由W.E.Howden在1968年提出的.在进行路径规划时采以栅格(grid)为单位表示环境信息,在处理障碍物的边界时,避免了复杂的计算。可以看出栅格的大小直接影响着规划时间

5、的长短和精度,栅格划分越小,障碍物的表示会越精确,但同时会占用大量的存储空间,算法的搜索范围将按指数增加。栅格的划分太大,规划的路径会很不精确.[3]模拟退火算法是将退火思想引入组合优化领域，提出的一种大规模组合优化问题的有效近似算法，该算法模仿固体物质的退火过程。众所周知,高温物体降温时其内能随之下降,如果降温过程充分缓慢,则在降温过程中物质体系始终处于平衡状态,从而降到某一低温时其内能为最小；反之降温太快,则降到同一低温时会保持内能。模仿退火过程的寻优方法称为模拟退火算法。模拟退火法的基本步骤如下:(1)给定初始温度T,及初始点,计算该点的函数值f(x)。0'(2)

6、随机产生扰动∆x，得到新点x'=+∆xx，计算新点函数值f(x),及函数值差。∆=ffxfx(')−()(3)若∆≤f0，则接受新点,作为下一次模拟的初始点;⎛⎞∆f(4)若∆>f0，则计算新点接受概率:pf()∆=exp⎜⎟−产生[0,1]区间上均匀分布的伪随机数r，⎝⎠KT•r∈[0,1],如果p()∆≥fr,则接受新点作为下一次模拟的初始点;否则放弃新点,仍取原来的点作为下一次模拟的初始点，然后转（2）步，重复此过程。收稿日期：基金项目：北京市教委科技发展计划项目[KM200311232138]作者简介：郑秀敏(1976－)，女，河北唐山人，硕士，主要从事机械设计

7、及理论方面的研究。1模拟退火法具有以下的优点：（1）模拟退火法不依赖于初始解。尽管在开始计算时模拟退火法需要一个初始解，但它在求解过程中能接受坏解，因此它不会局限于初始解所在的收敛域内。（2）模拟退火法得到的解虽然不一定是最优解，但一定是全局的次优解。原因是在计算过程中，坏解始终都有可能被接受，，因此算法能跳出局部极小值点。3算法的实现首先作如下假设。（1）把机器人简化成长为L，宽为B的矩形，如图二所示。（2）机器人在二维空间内运动，机器人通过其视觉系统能感知自己目前的位姿和障碍物的位置。（3）所有的障碍物为凸多边形。（4）从起点到终点至