基于栅格法的汽车路径规划

《基于栅格法的汽车路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、-------华中科技大学硕士学位论文1绪论1.1引言路径规划一直是机器人导航中非常重要的课题。机器人在工作时通常期望按照某一最优目标(如行走路线最短、耗费最少等)在工作空间行走，行走过程中机器人需要绕过静态或动态的障碍。机器人路径规划的任务就是在工作空间找到一条最优(或次优)路径。蒋新松[1]在文献中为路径规划作出了这样的定义：路径规划是自治式移动机器人的一个重要组成部分，它的任务就是在具有障碍物的环境内按照一定的评价标准，寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。障碍物在环境中的不同分布情况当然直接影响到规划的路径

2、，而目标位置的确定则是由更高一级的任务分解模块提供的。机器人路径规划主要有两类：全局路径规划和局部路径规划。全局路径规划指事先获得了作业环境的全部信息，通过建立适当的模型来搜索全局最优路径。而局部路径规划指作业环境的信息事先未知或不完全，通常通过传感器来获得局部信息。另外，机器人的移动范围可能是在同一平面或者三维空间。机器人全局路径规划的过程可以分为两个步骤：(1)建立环境模型：将现实的环境进行抽象后建立的相关模型；(2)路径搜索，即寻找符合条件的最优路径。不同的环境模型对路径搜索方法具有非常显著的影响。环境建模的方法主要有可视图法(V-graph)[2

3、]、自由空间法(FreeSpaceApproach)和栅格法(Grid)[3]等。模型建立完毕，需要搜索一条避障的最短路径。后期的搜索算法主要有Dijkstra算法、A*算法[4]以及最近研究较多的遗传算法、蚁群优化等搜索技术。可视图法的优势是从建模到求解的各个步骤都有比较成熟的算法。比如路径搜索可采用Dijkstra的最短路算法(时间复杂度为O(n2))，缺点是建模时间耗费过大，使之难以应用于实时系统。此外，一旦机器人的起点和目标点发生变化，就要重新构造可视图，影响了效率。自由空间法得到一个连通图，然后通过搜索连通图来进行路径规划，并且起点和目标点改变

4、时无需重新构图。但算法的复杂程度与障碍物的多少成正比，且不能保证总获得最1-----------华中科技大学硕士学位论文短路径。近来，由于进化计算的兴起，许多学者把遗传算法、蚁群算法引入到最短路求解中。文献[5]利用了遗传算法求网络的最短路径，但并没有充分的证据表明优于Dijkstra的最短路径搜索算法。另外的一些非栅格模型求解算法见文献[6-7]。栅格法把工作空间分割成规则而均匀的含二值信息的栅格。在机器人移动的过程中，栅格的尺寸和位置不变。二值信息分别表示该栅格处是否有障碍，没有障碍的栅格称为自由栅格，否则为障碍栅格。栅格的尺寸通常和机器人的基本移动

5、步长相适应，故机器人移动转化成从一个自由栅格移动到下一个自由栅格，机器人移动的路长对应于机器人爬过的栅格数。栅格法直观且建模相对较容易，因此得到了广泛的应用。栅格模型建立完毕后，我们需要找到一条最短路径。此时问题等价于求迷宫的最短路。传统的迷宫问题求解只是想办法找到一条通路见文献[8]，但不关心是否最优。在移动机器人路径规划中，我们需要找到最短的通路。把遗传算法和蚁群算法引入栅格模型求解的论文见文献[9-10]。这些算法使问题的求解速度和规模有不同程度的提高。但是，共同的缺陷仍然是求解时间过长，从而束缚了问题求解的规模。例如文献[7]中求解问题的规模最大

6、只达到了30×30，而时间耗费达到41.7s，也不适合对时间要求严格的实时系统。无论基于哪种模型，研究表明，遗传算法在求解最短路时，由于编码长度变化范围很大，尤其在问题的规模比较大时，求解效率并不高，故能有效求解的问题的规模比较小。而蚁群算法由算法本身的结构和特点决定了求解时间相对比较长，信息存贮量大。同时，在地形非常复杂、路线非常曲折的类似迷宫的情况下，这两种算法的搜索效率都比较低：每得到一条通路的过程就是一个走迷宫的过程，成功系数低：对遗传算法，容易产生大量的不可行解；对蚁群算法，会导致大量蚂蚁死亡或生成重复解，从而影响了搜索效率。本文提出了改进的栅

7、格法，并在此基础上用两种不同的搜索算法来实现路径搜索。1.1相关研究现状综述全局路径规划包括环境建模和路径搜索策略两个问题。其中，环境建模的主要方法有：可视图法、栅格法和自由空间法等。路径搜索策略的主要方法有：Dijkstra2-----------华中科技大学硕士学位论文算法、遗传算法和人工势场法等。1.1环境建模的方法（1）可视图法在C空间中，运动物体缩小为一点，障碍物边界相应地向外扩展为C-空间障碍。在二维的情况下，扩展的障碍物边界可有多个多边形表示，用直线将物体运动的起点S和所有C-空间障碍物的定点以及目标点C连接，并保证这些直线段不与C-空间障

8、碍物相交，就形成一张图，称之为可视图。由于任意两直线的顶点都是可见的，因此显然从