【《路径规划研究方法概述》2700字】

路径规划研究方法概述目录TOC\o"1-3"\h\u16001路径规划研究方法概述 1102901.1栅格法 164991.2环境地图法 2278931.3智能算法 2目前为止，在路径规划领域已有多种路径规划算法提出，对于移动机器人面对的任务环境，根据环境的复杂程度可以选用不同的路径规划方法，对于简单的环境可以只用一种路径规划方法解决问题，对于复杂的任务环境，需要组合多种方法，结合每种方法的优势，才能很好的解决问题。常用的路径规划方法，包括以下几类方法：栅格法地图法、实时环境地图法、智能路径规划算法等。1.1栅格法栅格法(grid)是对环境地图进行离散化建模的一种方法。就是将障碍物模拟成小方格的集合，相当于将场景中的所有事物进行二值化替代，障碍物为1，非障碍物为0。栅格法是环境地图建模的一种常用方法，其实质上是将机器人的工作环境离散化为大小相同的单元，也就是将移动机器人所在的规划空间按照给定的标准分解成独立的单元格。每个栅格相互连接，但不重叠。栅格大小的选取影响了环境精细化表达的程度，它是影响规划算法精度以及时间效率的一个非常重要的因素，规划精度和计算量与划分精度成反比。栅格化后，每个栅格会有一个通过因子，这个因子可以将问题简化，因此，路径规划问题在栅格地图环境下变成了寻找节点之间最短路径的问题，栅格由其是否包含障碍物分为自由栅格和障碍栅格，没有包含障碍物的栅格为自由栅格，包含障碍物的栅格为障碍栅格。一般情况下，栅格法作为一种地图的构建方式，不会单独作为一种算法来解决路径规划问题，一般将栅格构图法与其他路径规划算法结合使用，以达到预期的效果。表2.1显示了如何识别栅格。表2.1栅格标识方法栅格标识方法具体实现序号法从左上角的第一个栅格开始，按左-右、上-下的顺序显示。每个栅格对应一个唯一的标签n。也就是说，所有栅格都可以显示为它们自己独有的标签。直角坐标法栅格图的横纵方向分别为直角坐标系x轴和y轴，交点为坐标原点，右上方为x轴和y轴正方向，每一个栅格块的边长设为直角坐标系坐标轴的一个单位长度，这样任意栅格都有唯一坐标(x,y)表示图2.130*30栅格环境地图一旦确定了栅格标识，移动机器人就可以根据坐标号和栅格节点的序列号开始搜索路径。这种方法常常用于近乎长方形的室内地图模型中。栅格法将在本文后续路径仿真算法中采用，即建立30*30的栅格环境地图，如图2.1所示。1.2环境地图法在移动机器人路径规划的研究过程中，环境图法可以说是最为普遍的，经常被用于研究和分析，涵盖了方面极为广泛。通常，此类建模分析方法用于SLAM研究、土木工程建设、智能移动机器人定位和建筑工程等。移动机器人在导航研究中主要通过集成可感知环境信息得多种类型的传感器、具备一定计算功能的计算机处理器、结合各种数据处理算法进行信息采集。因此，对感知到的各种环境信息进行有效处理，选择环境地图的建模方法是非常有效且直接的。SLAM可以同时进行定位和环境构建，通过从传感器获取周围环境信息，通过计算处理，便可以准确得到当时的位置，也就是定位。在考察路线规划时，需要得到一个能够准确描述环境空间位置和属性的地图模型，即机器人工作环境地图。而环境地图的设置精度会直接影响到移动机器人定位的精度，因为在导航和规划路径过程中，移动机器人在环境中获取的信息或直接反映在环境地图中。也因为定位是移动机器人导航和路径规划的基础，因此，建立准确的环境地图尤为重要。1.3智能算法所谓“智能算法”，是在工程实践中普遍存在的一种“新”算法或理论。通常是指基于有机体的某些行为特性或某些自然过程。这些算法一般在工程学中的实践中使用居多，会有效解决许多复杂问题。有遗传算法（GeneticAlgorithm，GA）、蚁群优化算法(AntcolonyOptimzation,ACO)、粒子群算法(ParticleSwarmoptimization,PSO)、神经系统算法等，都属于智能算法。智能优化算法通常用于解决诸如局部优化之类的问题。蚁群算法：蚁群优化算法本质上是一种概率算法，常用来寻找优化路径的。最早由Dorigo、Maniezzo于1992年在他的博士论文中提出.文中提出蚁群算法的灵感来源于他在观测蚂蚁寻找食物的过程中，发现蚂蚁会自觉地发现觅食路径的行为。经过对蚂蚁觅食过程的研究表明，虽然通过观察一只蚂蚁我们无法查寻到其觅食的规律，但通过观察一群蚂蚁，我们可以概率性地得出蚁群觅食过程中路径规划的方法。通过观察蚁群觅食，得知蚂蚁在觅食的路径上会留下一定的信息素，随着通过的蚂蚁数量增加，随之留下的信息素的浓度也越高。这样一来，剩下的蚂蚁也会跟着信息素浓度高的路径往前走，直到找到食物。因此，环境和信息素在蚁群觅食过程中起着决定性的作用。而整个蚂蚁在觅食过程中留下的信息素类似于正反馈机制。通向食物的最短最优路径上往往留下的信息素最多。通过对这一现象的深入研究与分析，Drigo，Maniezzo等人提出了目前广为人知的蚁群算法。目前，蚁群算法经过大量学者的不断深究，得到了完善和改进，并成功应用于移动机器人路径规划。虽然蚁群算法在路径规划方面具有一定的优势，但也存在一些缺陷。蚂蚁简单如一的行为让其富有智能化多样性和正反馈。因为这种正反馈机制，使得移动机器人在规划路线时具有非常快的收敛速度、以及非常高的并行性和较强的对环境变化动态适应的鲁棒性。然而，正反馈机制是蚁群算法的主要优点的同时，也是它的主要缺点来源。虽然蚂蚁群觅食过程中，信息素浓度最高的路径肯定通往目标地点，但并不能确定这一路径就是最优路径。因为信息素浓度会随着时间的推移，慢慢减少，故最优路径可能会是其他路径。作为一种智能算法，它具有智能优化的效果，可以利用蚁群算法的迭代优化效果对其他路线规划算法进行改进和优化。本课题就是对传统A*算法的缺点进行迭代优化，兼顾蚁群算法的智能优化能力。此处不再赘述，将在第3章进行详细研究。遗传算法：遗传算法主要对达尔文提出的遗传进化过程进行了计算模拟，于20世纪70年代由美国的Johnholland提出。遗传算法着重模拟了生物在进化过程中的自然选择现象和遗传机理因素，是一种描述生物进化过程的计算模型。遗传算法在路径规划中使用的表达式并非完整形状，这会导致编码过程中出现较多无效路径。因此，遗传算法面临搜索效率低，最后搜索得到的路径不能有保障是最优路径。很多研究学者对这个缺点进行了研究，提出并通过引入自适应功能等改进措施对其进行改进。粒子群算法：粒子群算法,或者叫做粒子群优化，是通过观测鸟类觅食的行为而提出的一种仿生智能随机搜索算法，借鉴了鸟类群体协作的特性。粒子群优化算法最开始由J.Kennedy博士和R.C.Eberhart博士于1995年首先提出。PSO算法是一种并行算法，算法的初始化为一群随机粒子，通过反复迭代找到最优解。粒子群算法也可以理解