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  研究方向

机器人路径规划技术是机器人研究领域中的一个重要分支。所谓机器人的最优路径规 划问题，就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短、行走能量消耗最低等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划方法大致可以分为两类：传统方法和智能方法。

在这么多年的发展中，机器人路径规划的算法也在不断更新，最主要的目的还是为了能够更快更好的找到通往目的地的最优路径。就这种情况而言，机器人路径规划技术研究的主要方向是更快速、更准确的搜寻到前往目标点的无障碍路径。

3  智能算法

3.1 智能算法的简介

   在人类社会发展的过程中，大自然一直是我们最好的老师。人们受到自然界的启迪，根据其规律，学习到了解决问题的方法。现在已经有很多智能算法被研究出来并被应用到科学研究中，比如模拟退火算法、禁忌搜索算法、遗传算法、神经网络算法。文献综述

3.2 模拟退火算法的简介

模拟退火算法(Simulated Annealing，SA)最早的理论是由N. Metropolis等人在1953年的时候提出。1983 年,S.Kirkpatrick 等人成功地将退火思想引入到组合优化领域[2]。它是基于Monte-Carlo迭代求解策略所产生的一种新点随机寻优算法，其出发点是依据物理学中固体物质的退火过程与一般组合优化问题之间存在着的相似性。模拟退火算法讲的是从某一较高的初始温度出发，伴随着温度数据的不断下降，结合概率的突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解之中能够概率性地跳出局限并最终趋向于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率性的全局优化性能，目前已在工程实验中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。