路径规划毕业设计VIP专享VIP免费

1引言1.1课题研究背景及意义1.2主要研究内容及关键问题2路径规划概述路径规划是智能交通系统研究的重要内容，同时也是车辆定位与导航系统的重要组成部分，智能交通系统是包含若干子系统的复杂系统，其每个子系统都具有不同的功能，车辆定位与导航系统是智能交通系统的一个主要的应用子系统而路径规划是车辆定位与导航系统的重要组成部分。所以可以用下图来描述三者之间的关系。2.1路径规划的概念路径规划是车辆定位系统与导航系统的重要组成部分，是它必不可少的核心功能之一。车辆定位与导航系统中的路径规划是在车辆行驶前或行驶过程中为司机提供从起始点到目标点的一条或若干条路线，来对司机的行车进行导航。路径规划可分为单车辆路径规划和多车辆路径规划，单车辆路径规划是在一个特定的道路网上根据一个车辆的当前位置和目标给出单个路径规划，属于用户优化问题；多车辆路径规划是在一个特定的道路网上为所有的车辆规划各自的目标路径，属于系统优化问题。在计算机科学中，通常把求解两点之间一条路径的问题和多源最短路径问题，这些算法可视为单车辆路径规划的问题，多车辆路径规划比单车辆路径规划更复杂，单用于解决单车辆路径规划问题的背景知识将有利于研究多车辆路径规划的情形。2.2路径规划问题的效率针对一个特定的应用，在进行路径规划是可以采用多种标准来优化路线，这取决于系统的设计和用户的意愿。一条路径的好坏取决于许多因素，有些司机可能选择行驶距离最短的路径，而有些司机宁愿行驶距离长些但必须行车条件好一些。这些路径选择标准可由设计决定，也可由司机通过一个用户界面来选定。在选择最好路径时，必须具备一个数字地图，来挑选使属性值如时间和距离最小的路径。计算机中存储的具有拓补结构的车市路网由节点、边及相应的拓补关系构成。其中节点是道路的交叉点、端点，边是两节点间的一段道路，用于表示分段道路，边的权值可以定义为道路的距离或距离与其它信息的综合信息，此时可以将数字道路地图转化为带权有向图，因此无论采用何种标准，求解路网中两点之间的路径问题就可以归结为带权有向图的路径问题。在图论中有许多比较成熟的最短路径算法可供采用，但在车辆定位与导航系统中，这些算法通常不能直接使用，原因有两个：一、对于实时车辆导航系统，路径规划必须在一定的时间内完成，这就要求路径规划算法具有较高的运算效率；二、对于车辆导航系统，负责路径规划的导航计算机系统受车载环境和成本制约，处理能力和存储资粮十分有限，而在实际应用中的数字道路数据库往往规模庞大。因此在车辆定位与导航系统中路径规划的研究目的和任务是改进图论中的算法或者构造新的算法，实现在尽可能短的时间内找到一条理想的路径。只考虑了路径规划的时效性，可能导致规划后的路径不是最优路径，但却是比较理想的次优路径，能够被人们所接受，此时达到了时效性和最优性的平衡。这也是车辆定位与导航系统所要求的。2.3路径规划的研究现状目前，国内外对路径规划方法的研究主要有两大类，传统方法与智能方法。传统方法主要包括：梯度法、栅格法、枚举法、可视图法、人工势场法、自由空间法、A*算法、随机搜索法等。其中人工势场法、梯度法易陷入局部最小点，枚举法、可视图法不易用于高维的优化问题。用于机器人路径规划的智能方法主要有：模糊逻辑、神经网络、遗传算法、蚁群算法、粒子群算法等。3.蚁群算法概述3.1蚁群算法原理在昆虫世界中，蚂蚁是一类群居昆虫。它们具有高度组织的社会性，不仅可以借助触觉和视觉的联系彼此沟通，而且可以借助于信息素进行大规模的协调行动。另外，蚂蚁还能够较快地适应环境的变化，比如：蚂蚁在搬运食物的过程中，路上突然碰到障碍物时，蚂蚁仍能够很快重新找到到达蚁穴的最短路径。蚂蚁究竟是如何完成这些复杂的任务呢?经大量研究发现，蚂蚁在发现食物后，如果食物较小则独自搬运，食物比较大时则会请求“外援”，同时，一路上会留下信息素，食物越大信息素的浓度越大，其它蚂蚁逐渐向信息素浓的方向靠近，以至足够多的蚂蚁最终找到食物并将食物搬回蚁穴。如果采用算法实现完成整个任务的过程，则遵循如下原则：(1)活动范...