基于栅格法和交通规则的路径规划

《基于栅格法和交通规则的路径规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：韵蔌El期：刀。分年6月厂El学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料

2、室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。学位论文作者签名：日期：年月日导师签名：允佐卒日期：Z．,yoO眸舌月，El基于栅格法和交通规则的路径规划第l章绪论第1章绪论本章主要介绍路径规划的发展现状，并对路径规划技术进行了总结，是全文的背景资料介绍与分析。在本章的最后论述了课题研究存在的意义与研究点，并介绍了本文的结构安排。1．1路径规划技术概念路径规划技术不仅是机器人研究领域的一个重要部分，它也应用于计算机仿真中，用来模拟移动实体的行走路线。典型的路径规划问题是指在有障碍物的工作环境中，按照一定的

3、评价标准(行走路线最短、所用时间最少等)为机器人寻找一条从起点到终点的运动路径，让机器人在运动过程中能安全、无碰撞地通过所有的障碍物。因而路径规划问题又可以称为避碰规划问题【l】。我们可以把路径规划归纳为主要解决三个问题：(1)使移动实体(机器人或者虚拟人)能从初始点运动到目标点；(2)用一定的算法使机器人或者虚拟人能够绕开障碍物，并且经过某些必须经过的点；(3)在完成以上任务的前提下，尽量优化机器人或者机器人的运行轨迹。1．2路径规划方法介绍对运动规划的研究是20世纪60年代出现的【2】。在过去的几十年中，路径规划技术己经有了很大的发展。在研究过程中

4、，人们逐步提出了基于各种思想的路径规划方法。根据对环境信息掌握的程度不同将路径规划分为两种类型[31：一种是基于环境先验信息完全的全局路径规划，另一种是基于传感器信息的局部路径规划。1．2．1全局路径规划全局路径规划是指在全局环境信息己知的情况下，为移动实体规划出一条从起点到终点的运动路径。全局路径规划需要知道关于环境的所有信息，根据环境基于栅格法和交通规则的路径规划第l章绪论地图进行大粒度的路径规划，并产生一系列关键点作为目标下达给局部路径规划系统。因为全局路径规划的一个特点是信息共享，所以可以对碰撞进行预测，避免走不必要的路程。全局路径规划的设计标

5、准是尽量使规划的效果达到最优，但由于需要预先知道全局的环境信息，计算量大，实时性差，不能较好地适应动态非确定环境。目前常用的全局路径规划方法有以下三种：(1)构型空间法在八十年代初，Lozan—Perz和WeSley提出了路径规划中构形空间【4】的概念。此后，构形空间成了路径规划的重要工具，其方法是把移动机器人压缩成一个构形点，而把障碍物拓展成充满空间的构形障碍物；路径规划问题就是寻找在构形空间中构形点避开构形障碍物的无冲突路径。但是构形空间法的主要缺点是从移动机器人空间和障碍物空间产生构形空间并发现无冲突空间需要大量的运算，从而降低控制的实时性。其中

6、研究较成熟的有：舔可视图法(V-C,raph)[51：可视图法的基本原理是使用多边形法描述虚拟环境，移动实体视为一点，将移动实体、目标点和多边形障碍物各顶点进行组合连接，并保证这些直线均不与障碍物相交(即直线是可视的)，这就形成了一张图，称为可视图。由于任意两直线的顶点都是可见的，从起点沿这些直线到达目标点的所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。运用优化算法可删除一些不必要的连线以简化可视图，缩短搜索时间．该方法的优点是概念直观，实现简单。但假设移动实体的尺寸大小忽略不计，会使移动实体通

7、过障碍物顶点时离障碍物太近甚至接触，并且搜索时间长。另外该方法缺乏灵活性，一旦移动实体的起点和目标点发生改变，就要重新构造可视图。已经证明用可视图法计算对于N条连线的搜索时间为0(N2)。典型的优化算法如Dijkstra法，A木搜索算法【6】等，此法可删除一些不必要的连线以简化可视图、缩短搜索时间，能够求得最短路径。利用可视图，A木算法能够在O(Ktnlogn)时间内进行最短欧氏距离搜索，其中K是图中边的数量，n是顶点的数量。·囊Voronoi图法：Voronoi图法对可视图法进行了改进。Voronoi图【7】己以多种方2基于栅格法和交通规则的路径规划

8、第1章绪论式用于路径规划，包括地图计算，样本生成，或者结合人工势场法。把一系列障碍物看作基点，