【作者】 张照生；

【导师】 连小珉；

【作者基本信息】 清华大学 ， 机械工程， 2013， 博士

【摘要】 路径规划是车辆导航系统的核心组成部分，随着我国地理信息数据的不断增加以及汽车保有量的迅速提高，国内交通复杂程度不断增大，驾驶员的个性化需求也越来越多，因此开发适应交通约束下的路径规划算法以满足车载导航系统的需求已成为一项亟待解决的问题。针对以上问题，文中提出了带交通预测的最优路径规划算法，区域约束下的通过性路径规划算法以及特殊路网约束下的目标引导算法。首先建立了浮动车样本量计算模型，验证当前浮动车数量是否满足动态路径规划的需求。在精度满足要求的情况下，应用阈值控制算法对接收的动态交通信息进行过滤，同时使用加权平均及指数平滑的方法对缺失数据进行补全，在此基础上结合路网拓扑特性用相邻路段数据补全缺失数据，最后应用主成分重建的方法对噪声数据进行修复。对修复后的交通数据采用聚类分析算法建立匹配模板，并利用多因子模式匹配和预测误差的自适应校正方法对交通数据进行短期预测，从而建立城市道路交通模型，使基于预测的时间最优路径规划成为可能。带交通预测的最优路径规划在原有静态路径规划的基础上考虑动态交通信息的约束，使驾驶员避开拥堵走最佳行驶路线。为实现动态交通数据的快速读取和更新，文中建立了动态交通数据库，为电子地图的动态更新提供快捷的底层支持。带交通预测的最优路径规划利用城市路网交通模型计算节点通行代价，并考虑车辆在路口的等待时间，实现了平面路网下的动态路径规划。通过性寻路提出了一种新的路径规划方法，可以由用户根据自己的趋好选择通过区域，实现了区域约束下的路径规划。算法建立了通过性路网模型，保证寻路结果通过指定区域，并分两步实现通过性寻路：虚终点寻路和变方向寻路。虚终点寻路通过设置虚终点并利用A*算法引导路径通过指定区域，变方向寻路通过更改寻路诱导代价引导路径从指定区域向终点规划。特殊路网约束下的目标引导路径规划在蛛式路网分块的基础上，以块为单位对路网数据进行预处理，计算路网中其它节点到达块边界节点的代价，从而判断有向节点对是否在到达该块的最优路上。目标引导寻路只拓展约束范围内有最优标志的节点，从而减少拓展节点，加快路径规划速度。更多还原

【Abstract】 Path planning is one of the most important parts of the vehicle navigation system.With the rapid increase of geographic information data and car ownership in China, thetransportation system becomes more and more complex, which makes it quitechallenging to meet the requirement of individualized demand of drivers. Therefore,developing the path planning algorithm under traffic restriction to meet therequirement of the vehicle navigation system has become a critical problem that needsto be solved. In this dissertation, the algorithms of transportation-forecast optimumpath planning, area-through path planning, and target guiding under the restraint ofspecial road net were proposed.A computation model that can evaluate whether the number of the floating car canmeet the requirement of the dynamic path planning was initially developed. Thethreshold control method was adopted to filter the received dynamic traffic informationon the premise that the accuracy can meet the requirement. At the same time, themethods of weighted average and exponential smoothing were first used to supplementthe missing data, then using the data from the adjacent road segment, together withtopo characteristics of the road net, to further complete the missing data. The noisedata was repaired using the method of reconstruction of the principal components. Theclustering analysis method was applied to the repaired traffic data to build thematching template, and short-term forecast on the traffic data was performed using themethods of multi-factor pattern matching and adaptive correction based on theforecasting error. The traffic model of the urban road net was then developed, whichmakes it possible to develop the time optimal path planning based on forecast.Compared with the original static path planning, the optimum vehicular pathplanning with traffic forecast can take the dynamic traffic restriction into consideration,thus it enables the driver travels along the optimum route avoiding the traffic jam. Inorder to rapidly read and update the dynamic traffic data, the dynamic traffic databasewas established in this dissertation, which can provide convenient basic support for thedynamic updates of the electronic map. The optimum path planning with traffic forecast can fulfill the dynamic path planning of the plane road net through calculatingthe cost between two nodes using traffic model of the urban road net and computingthe waiting time at the cross.The area-through path planning proposes a new method of path planning. Theusers can select the passing area according to their own needs. As a result of that, pathplanning under area restriction was realized. The algorithm proposed in thisdissertation develops the model of area-through path planning, enabling the results topass the designated area. The area-through path planning was fulfilled through twosteps: the virtual target path planning and the direction-changing path planning. Thevirtual target path planning is achieved by leading the car to pass the designated areaby setting the virtual-target point and using A*algorithm, while the direction-changingpath planning can lead the car to pass the target area through changing the pathplanning heuristic cost.Based on the basis of the spider-web road network the target guiding pathplanning restrained under the special road net preprocesses the road net data in block.It estimates whether the directional joint-node is on the optimum path to this blockthrough calculating the cost from other nodes to boundary nodes of the block. Thetarget guiding path planning only topo the nodes with optimal flags in the restraint area,thus it can reduce the topological nodes and increase the speed of path planning.更多还原