机器人路径规划方法研究

论文总字数：14734字

摘 要

关 键 词 : 机器人，最优路径，模拟退火算法

Abstract: With the development of science and technology, human beings begin to explore the unknown environment. Under this premise, the robot with high work efficiency, mass production, fear of environmental impact and other advantages, has become the main helper to explore the environment. In this case, to improve the efficiency of the robot exploration and planning to explore the path of the robot has become a major research problem. The method for robot path planning as the research subject, through the study of intelligent algorithms (simulated annealing algorithm) to the environment of path planning, and puts forward several improvement of simulated annealing algorithm, compares the advantages and disadvantages. Finally, through grid method practical modeling to verify its correctness, so as to get the optimal path, so that the robot can quickly and accurately reach the destination.

Key words: optimal path, robot, simulated annealing algorithm

目 录

1 引言…………………………………………………………………………4

2 机器人路径划………………………………………………………………4

2.1机器人路径规划的定义……………………………………………………4

2.2机器人路径规划的分类……………………………………………………4

2.3机器人路径规划的历史和现状……………………………………………4

2.4机器人路径规划的研究方向………………………………………………5

3 智能算法……………………………………………………………………5

3.1 智能算法的简介…………………………………………………………5

3.2 模拟退火算法的简介……………………………………………………5

3.3 模拟退火算法的原理……………………………………………………6

3.4模拟退火算法的基本思想…………………………………………………6

3.5模拟退火算法的步骤………………………………………………………8

4 改进模拟退火算法…………………………………………………………9

4.1 通过模型扰动改进………………………………………………………9

4.2通过接收概率改进………………………………………………………10

4.3通过降温方式改进………………………………………………………10

4.4其他不常见的改进方法…………………………………………………10

4.5栅格法建模………………………………………………………………11

5 货郎担问题的模拟退火算法的实现………………………………………12

5.1货郎担问题的描述………………………………………………………12

5.2货郎担问题的应用………………………………………………………13

5.3 TSP算法的流程…………………………………………………………14

结论……………………………………………………………………………16

参考文献………………………………………………………………………17

致谢……………………………………………………………………………18

附件：模拟退火算法的源程序………………………………………………19

1 引言

移动机器人的研究开始于上个世纪60年代末期，是机器人学、人工智能学、仿生学、控制理论和电子技术等多种技学科交叉研究的产物。随着科技的发展和社会的进步，机器人已经走出实验室，在深海勘测、汽车制造、医学科研、能源开采、军事现代化等领域中都占有着其不可取代的位置。随着机器人的应用越来越广,越来越深入，各行各业对机器人的要求也越来越高，因此移动机器人的研究逐渐步上正轨,成为高新技术应用领域的热点。 目前，对于移动机器人相关技术的研究，虽然已取得了大量的成果和突破性的进展，但是在很多关键理论和实际问题上，还有问题有待解决和完善。因此，进行移动机器人相关技术的研究，具有非常重要的现实意义。

本文讨论的是在静态全局环境已知的情况下，通过栅格法对已知的环境进行描述，建立环境的模型，并采用模拟退火算法，根据优化条件从中搜索出一条从起点到终点的最优或近似最优路径，即全局路径规划。机器人利用设计好的程序按照规划出的最优路径自动导航，无碰撞地移动到目标点。

2 机器人路径规划

2.1 定义

机器人路径规划是指在有障碍物的已知环境中,按照一定的规则,寻找一条从起始地点到目标地点的无碰撞路径。

2.2 分类

根据机器人对环境信息的了解程度不同，我们大体讲机器人路径规划分为两类：环境信息完全知道的全局路径规划，这种情况下计算效率更快，寻找路径更为方便；环境信息完全未知或者部分未知的局部路径计划，在这种情况下，必须要靠传感器或者摄像头之类的工具在线的对机器人的工作进行指导，先对未知环境进行探索，以获取障碍物的位置形状和尺寸，在了解到环境的全部图像之后再进行规划，以保障路径规划的可靠性。

2.3 历史和现状

在当今社会中，机器人的应用越来越广泛，几乎可以说已经渗透到了所有应用领域。机器人路径规划是机器人研究学中的一个重要分支。早在60年代，就已经开始了关于机器人路径规划的研究。关于机器人路径规划的研究涉及许多方面:首先，要考虑移动方式，可以是轮式的、履带式、腿式的，对于水下机器人，则是推进式。^[1]斯坦福研究院(SRI)的Nils Nilssen和Charles Rosen等人，早在1966年至1972年中研造出了取名为Shakey 的自主移动机器人，研究目的是应用人工智能技术，实现在复杂环境下机器人系统的自主推理、规划和控制。与此同时，最早的步行机器人也研制成功，实验结果引导了机器人步行机构方面的研究，目的是为了解决机器人在不平整地域内运动的问题，并由此设计并研制出了多足步行机器人。其中最著名的是名为General Electric Quadruped的步行机器人。70年代末，随着计算机技术的应用和传感技术的发展，机器人路径规划研究又出现了新的高潮，特别是在80年代中期，设计和制造机器人的浪潮席卷全世界。一大批世界著名的公司开始研制移动机器人平台，这些移动机器人平台主要是作为大学实验室及研究机构的移动机器人实验平台，从而促进了移动机器人学多种研究方向的出现。90年代以来，以研制高水平的环境信息传感器和信息处理技术为基础，以高适应性的移动机器人控制技术，以真实环境下的规划技术为标志，全球开展了冲向移动机器人路径规划的更高层次的研究。

2.4 研究方向

剩余内容已隐藏，请支付后下载全文，论文总字数：14734字